◆陳 姍

?

一種基于屬性值分布的異構(gòu)數(shù)據(jù)對象的相似度計算方法

◆陳 姍

（北京天廣匯通科技有限公司 北京 100097）

現(xiàn)有的算法無法計算不同類型的對象之間的相似度，本文提出一種基于屬性值分布的異構(gòu)數(shù)據(jù)對象的相似度計算方法，通過計算異構(gòu)數(shù)據(jù)的屬性值分布之間的相關(guān)度，作為相關(guān)屬性的權(quán)值，再對兩個對象逐對計算其屬性之間的相似度，使用相關(guān)屬性的權(quán)值進(jìn)行加權(quán)后取和，作為對象之間的相關(guān)度。實驗證明，本算法在通用性、健壯性，召回率方面都優(yōu)于現(xiàn)有的方法

異構(gòu)數(shù)據(jù)；相似度

0 引言

在機(jī)器學(xué)習(xí)領(lǐng)域，對象相似度作為一個重要課題，被廣泛應(yīng)用在鏈接預(yù)測、欺詐檢測等眾多實際問題中。隨著大數(shù)據(jù)技術(shù)的發(fā)展，數(shù)據(jù)的構(gòu)成越來越復(fù)雜，在比較不同類型的對象時，現(xiàn)有的判斷對象之間相似度的方法往往受到對象的屬性結(jié)構(gòu)的限制，只能判斷屬性類型相同或者相近的對象之間的相似度，不能判斷異構(gòu)類型的對象之間的相似度。因此，研究如何對不同類型的對象進(jìn)行比較，計算其相似度，從而為各種諸如聚類、分類等后續(xù)工作提供基礎(chǔ)，有著重要的意義。

1 相關(guān)工作

目前計算對象相似度的算法主要有以下幾種：明可夫斯基距離[1]，包含特例歐幾里得距離、曼哈頓距離、以及切比雪夫距離，cosine相似度[2]，Jaccard相似度[3]。這些方法都是針對相同類型的對象，需要2個對象的屬性構(gòu)成相同，不能計算那些無屬性信息的對象之間的相似度。因此，對于由不同屬性構(gòu)成的異構(gòu)對象，如何計算其相似度，是一個值得研究的課題。

2 算法描述

本算法包含以下4個步驟：

2.1 計算屬性的SimHash值

（1）將對象的所有屬性轉(zhuǎn)換為文本格式；

（2）用詞向量的形式表示屬性值

對屬性轉(zhuǎn)換得到的文本進(jìn)行詞元化和分詞處理。如對象x的屬性a取值為v，經(jīng)過詞干化和分詞處理后，得到n個詞t1，t2，...，tn，那么v可表示為詞向量T；

（3）將詞轉(zhuǎn)換成64位長整數(shù)

選擇一個哈希函數(shù)f，將詞t轉(zhuǎn)換成64位長整數(shù)型的哈希值h：

那么使用(1)可以將v的詞向量表示T轉(zhuǎn)換成哈希值表示：T；

（4）計算每個哈希值的權(quán)重

設(shè)數(shù)據(jù)集中的對象數(shù)量為n，哈希值h在m個對象中出現(xiàn)過，則哈希值h的權(quán)重wh的計算方法如下：

（5）計算屬性值的SimHash值

①設(shè)屬性值v表示為哈希值的向量T，對應(yīng)的權(quán)重向量為T，將h1,h2,...hn轉(zhuǎn)成n個長度為64的整數(shù)數(shù)組a1,a2,...an：

②修改每個數(shù)組中的每個元素值，如果為1，修改為其對應(yīng)的哈希值的權(quán)重，如果為0，修改為其對應(yīng)的哈希值的權(quán)重的負(fù)值

③對于屬性值v創(chuàng)建另一個64位的整數(shù)數(shù)組s，其每個元素等于所有數(shù)組a的相應(yīng)位置的元素的加和：

2.2 計算兩個屬性之間的相關(guān)度

（1）計算某個屬性中的某個屬性值的出現(xiàn)概率

設(shè)對象類型X包含N個對象，X的屬性類型A出現(xiàn)了N個不相同的屬性值，第i個屬性值v的SimHash值在對象類型X的屬性類型A中出現(xiàn)了n次，那么屬性值v在對象類型X的屬性類型A中的出現(xiàn)概率的計算方法如下：

（2）計算兩個屬性的分布的散度

（3）計算兩個屬性的相關(guān)度

屬性類型A和B的相關(guān)度計算方法如下：

2.3 計算兩個屬性之間關(guān)系的權(quán)重

設(shè)對象類型X包含N個對象，對象類型Y包含N個對象，X的屬性類型A和對象類型Y的屬性類型B中出現(xiàn)了N個不相同的屬性值，第i個屬性值v的SimHash值SimHash在X的屬性類型A和對象類型Y的屬性類型B中共出現(xiàn)了n次，那么屬性值v在對象類型X的屬性類型A以及對象類型Y的屬性類型B中的出現(xiàn)概率p的計算方法如下：

2.4 計算兩個對象之間的相似度

3 實驗

為了驗證本方法地有效性，我們從某信息系統(tǒng)的數(shù)據(jù)庫中抽取了描述對象“人物”的關(guān)于“基本信息”、“教育”、“職業(yè)”、“社團(tuán)”等方面信息的4張表，從每張表中隨機(jī)抽取了1000行記錄，首先使用人工的方式標(biāo)記出相同人物，再使用本方法計算“基本信息”表中的每行數(shù)據(jù)和其他3個表中每行數(shù)據(jù)的相似度，選擇“基本信息”表中的某行和其他表中與其相似度最大的行做為候選項，如果相似度大于某閾值，則判度是同一人物。同時，我們也使用歐幾里得距離、cosine相似度，Jaccard相似度按照上述方式判斷是否為同一人物，以驗證本方法的性能。

由于歐幾里得距離、cosine距離，Jaccard相似度均需要識別相同維度，我們采用的方法是：如果2個表中列名相同則認(rèn)為是相同屬性，否則認(rèn)為是不同屬性，另外，由于很多屬性均是文本類型，我們判斷屬性值相同的方法是，在去掉停用詞之后，如果2個字符串所包含的詞相同，則認(rèn)為這2個屬性值相同，否則認(rèn)為是不同的。

我們統(tǒng)計所發(fā)現(xiàn)的同一人物的查準(zhǔn)率P和召回率R，其計算公式如下，其中TP表示識別出的樣本數(shù)，F(xiàn)P表示未識別出的樣本數(shù)，F(xiàn)N表示識別出的錯誤樣本數(shù)：

實驗結(jié)果如表1。

表1 實驗結(jié)果

對于基本信息表-教育表，基本信息表-職業(yè)表，基本信息表-社交表等3種類型的人物匹配，由于其他3種對照方法錯誤使用了description屬性進(jìn)行判斷，導(dǎo)致了查準(zhǔn)率和召回率較低，本文提出的方法對各種屬性綜合考慮，如地址，活動社團(tuán)等，查準(zhǔn)率和召回率都較高。

4 結(jié)論

本文提出了一種基于屬性值分布的異構(gòu)數(shù)據(jù)對象的相似度計算方法，通過計算異構(gòu)數(shù)據(jù)的屬性值分布之間的相關(guān)度，作為相關(guān)屬性的權(quán)值，再對兩個對象逐對計算其屬性之間的相似度，使用相關(guān)屬性的權(quán)值進(jìn)行加權(quán)后取和，作為對象之間的相關(guān)度。在與目前已有的相似度計算方法相比，本方法在通用性、健壯性，召回率方面都有顯著地提高

[1]吳麗娟,李陽,梁京章.一種基于明可夫斯基距離的加殼PE文件識別方法[J].現(xiàn)代電子技術(shù),2016.

[2]劉妍.基于Lucene的余弦距離檢測文檔相似度方法的研究[J].信息系統(tǒng)工程,2014.

[3]潘磊,雷鈺麗,王崇駿,謝俊元.基于權(quán)重的Jaccard相似度度量的實體識別方法[J].北京交通大學(xué)學(xué)報,2009