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

◆陳 姍

?

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

◆陳 姍

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

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

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

0 引言

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

1 相關(guān)工作

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

2 算法描述

本算法包含以下4個(gè)步驟：

2.1 計(jì)算屬性的SimHash值

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

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

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

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

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

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

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

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

（5）計(jì)算屬性值的SimHash值

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

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

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

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

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

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

（2）計(jì)算兩個(gè)屬性的分布的散度

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

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

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

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

2.4 計(jì)算兩個(gè)對(duì)象之間的相似度

3 實(shí)驗(yàn)

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

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

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

實(shí)驗(yàn)結(jié)果如表1。

表1 實(shí)驗(yàn)結(jié)果

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

4 結(jié)論

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

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

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

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