楊 萌 聶鐵錚 申德榮 寇 月 于 戈

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽 110819)

1 引 言

隨著信息領(lǐng)域各項(xiàng)技術(shù)的飛速發(fā)展，數(shù)據(jù)呈爆炸式增長，以數(shù)據(jù)為中心的系統(tǒng)得到了廣泛的應(yīng)用。雖然各類應(yīng)用系統(tǒng)中存儲(chǔ)了大量數(shù)據(jù)，但這些信息并非總是正確無誤的，即可能存在各種問題。一個(gè)典型的問題就是不同的數(shù)據(jù)提供方對(duì)同一個(gè)事物及實(shí)體可能會(huì)有不同的描述(包括數(shù)據(jù)格式、表示方法等)，為此需要實(shí)體識(shí)別技術(shù)進(jìn)行數(shù)據(jù)清洗。實(shí)體識(shí)別也稱作實(shí)體解析，是從“引用集合”中解析并映射到現(xiàn)實(shí)世界中“實(shí)體”的過程。記錄鏈接則是一種面向結(jié)構(gòu)化數(shù)據(jù)的實(shí)體識(shí)別技術(shù)，目的是從數(shù)據(jù)集中識(shí)別和聚類表示同一實(shí)體的記錄。

現(xiàn)有研究工作中，有基于記錄的組鏈接[1]和基于記錄的實(shí)體鏈接。其中，組鏈接是指把表示同一類的實(shí)體放到相同的聚簇中；實(shí)體鏈接是把表示同一個(gè)實(shí)體的記錄方法放到相同的聚簇中。本文主要研究實(shí)體鏈接?；谒幚淼臄?shù)據(jù)對(duì)象，實(shí)體識(shí)別技術(shù)可以分為兩類：面向靜態(tài)數(shù)據(jù)的實(shí)體識(shí)別和面向演化數(shù)據(jù)的實(shí)體識(shí)別。

面向靜態(tài)數(shù)據(jù)的實(shí)體識(shí)別方法：從數(shù)據(jù)集中識(shí)別和聚類表示同一實(shí)體的記錄，對(duì)相似度達(dá)到一定閾值的記錄做聚類操作，從而獲得表示同一個(gè)實(shí)體的記錄簇，而不同簇中的記錄認(rèn)為表示不同的實(shí)體。實(shí)體間相似性一般根據(jù)領(lǐng)域知識(shí)設(shè)定匹配規(guī)則度量標(biāo)準(zhǔn)[2]，可通過編輯距離和歐氏距離計(jì)算[3]，也可以用機(jī)器學(xué)習(xí)訓(xùn)練分類器的方法實(shí)現(xiàn)[4]?；谙嗨菩詫?duì)實(shí)體進(jìn)行聚類的方法有鄰接性聚類[2]、相關(guān)性聚類[5,6]、密度聚類[7-9]。

面向靜態(tài)數(shù)據(jù)的實(shí)體識(shí)別方法在很多情況下并不適用。在現(xiàn)實(shí)應(yīng)用中，實(shí)體記錄的某些屬性值通常會(huì)隨時(shí)間或解釋的變化而發(fā)生演化，而面向靜態(tài)數(shù)據(jù)的實(shí)體識(shí)別方法無法根據(jù)屬性值的演化調(diào)整相似性的計(jì)算結(jié)果。

面向演化數(shù)據(jù)的實(shí)體識(shí)別，是考慮數(shù)據(jù)隨時(shí)間的變化而變化的特性即考慮時(shí)間特征，體現(xiàn)了數(shù)據(jù)的動(dòng)態(tài)性和演化性。Li 等[10]在計(jì)算記錄的相似性時(shí)考慮了記錄的時(shí)間特征：考慮時(shí)間的流逝對(duì)記錄改變的影響，基于延遲提出了 early binding、late binding、adjusted binding 三個(gè)聚類算法。之后 Hu 等[11]提出了基于時(shí)序特征的記錄鏈接的改進(jìn)方法；Chiang 等[12]提出了兩階段聚類的方法；Chiang 等[13]提出了 mutation 模型，用來檢測一個(gè)給定屬性的值經(jīng)過一段時(shí)間之后該值重復(fù)出現(xiàn)的概率；Li 等[14]提出了 source-aware temporal matching 算法，整合不同的數(shù)據(jù)源，豐富實(shí)體的信息。除此以外，還有基于增量的實(shí)體識(shí)別方法，從匹配規(guī)則的演化[11]及數(shù)據(jù)的演化[15-17]兩方面為依據(jù)探討記錄鏈接的增量問題。

對(duì)于演化數(shù)據(jù)，實(shí)體記錄的某些屬性值通常會(huì)發(fā)生變化。其中有些實(shí)體屬性會(huì)隨著時(shí)間的變化而發(fā)生規(guī)律性演化，但也有實(shí)體屬性的演化不具有規(guī)律性，因此很難抽取出其演化的規(guī)律。對(duì)于不規(guī)律演化的數(shù)據(jù)，基于演化的實(shí)體識(shí)別方法聚類的結(jié)果準(zhǔn)確度并不高。這是因?yàn)閷?duì)于這種不規(guī)律的變化也使用規(guī)律變化的準(zhǔn)則結(jié)果會(huì)產(chǎn)生偏差。為此，本文的工作將解決不規(guī)律演化實(shí)體的識(shí)別問題。

本文提出一個(gè)基于隨機(jī)森林的兩階段聚類實(shí)體識(shí)別模型：利用已有的數(shù)據(jù)集，訓(xùn)練出隨機(jī)森林。其中，隨機(jī)森林是由很多棵決策樹組成的，每棵樹的輸入是任意兩條記錄，輸出是兩個(gè)記錄的相似度結(jié)果。在最后的聚類結(jié)果，利用前面記錄的相似度結(jié)果，進(jìn)行兩階段聚類，其中保證簇內(nèi)的記錄盡可能完整，同時(shí)盡可能多的簇被發(fā)現(xiàn)，提高聚類結(jié)果的準(zhǔn)確性。主要貢獻(xiàn)如下：

(1)提出基于隨機(jī)森林的記錄相似度計(jì)算模型。該相似度模型充分考慮實(shí)體記錄變化的不規(guī)律性，從而動(dòng)態(tài)地、準(zhǔn)確地衡量記錄的相似性。

(2)提出一個(gè)新型的兩階段聚類算法。簇的聚類過程分為兩個(gè)階段：第一階段進(jìn)行核聚類，把盡可能多的已經(jīng)確定的記錄放在相同的簇中；第二階段進(jìn)行端點(diǎn)聚類，能夠?qū)⑹Ｓ嗟挠涗浐鸵阎拇睾喜⒒蛘吆喜⒁延械拇?，保證簇內(nèi)記錄盡可能完整，盡可能多的簇被發(fā)現(xiàn)。

(3)在真實(shí)的數(shù)據(jù)集上對(duì)提出的算法進(jìn)行充分的實(shí)驗(yàn)評(píng)價(jià)，驗(yàn)證算法的有效性。與已有的聚類算法對(duì)比，該算法能夠有效提高演化實(shí)體的識(shí)別準(zhǔn)確性。

本文組織結(jié)構(gòu)如下：第 2 節(jié)介紹準(zhǔn)備工作，包括實(shí)體識(shí)別模型和問題描述；第 3 節(jié)對(duì)連續(xù)值的決策樹和隨機(jī)森林進(jìn)行了定義；第 4 節(jié)介紹了基本的隨機(jī)森林計(jì)算相似度算法框架，并提出防止過擬合的優(yōu)化算法；第 5 節(jié)通過實(shí)驗(yàn)與分析將本文工作與已有工作進(jìn)行對(duì)比，證明其有效性；第 6 節(jié)總結(jié)全文。

2 準(zhǔn)備工作

2.1 實(shí)體識(shí)別模型

基于聚類方法的實(shí)體識(shí)別模型包括相似度計(jì)算模塊和聚類決定模塊，具體如圖 1 所示。整個(gè)模型輸入待判斷數(shù)據(jù)集，輸出識(shí)別結(jié)果。

圖1 實(shí)體識(shí)別模型Fig. 1 The similarity algorithm based random forest

2.1.1 相似度計(jì)算模塊

該模塊調(diào)用匹配函數(shù)得到候選記錄對(duì)的相似度[18]，得到的相似性結(jié)果介于[0，1]。相似度的值越大，表示兩個(gè)數(shù)據(jù)對(duì)象越有可能表示同一個(gè)實(shí)體。其中，最大值 1 代表兩個(gè)記錄表示同一個(gè)實(shí)體，最小值 0 代表兩條記錄表示不同實(shí)體。每個(gè)記錄包含多個(gè)屬性，不同屬性可能是不同類型的數(shù)據(jù)。在確定記錄對(duì)相似度之前，針對(duì)每個(gè)屬性調(diào)用特定的相似度函數(shù)來計(jì)算其相似度，確定記錄對(duì)的對(duì)應(yīng)屬性的相似性。在此基礎(chǔ)上需要設(shè)計(jì)恰當(dāng)?shù)慕M合函數(shù)來將這些相似度合理地融合成一個(gè)綜合相似度。組合函數(shù)可以是線性函數(shù)、非線性函數(shù)或者其他類型的函數(shù)[3-5]，如加權(quán)求和就是線性函數(shù)。在考慮時(shí)間屬性的實(shí)體識(shí)別方法中[10-13]，根據(jù)時(shí)間為每個(gè)屬性分配一個(gè)權(quán)值，綜合相似性則為所有屬性的加權(quán)和。綜合相似度能有效地估計(jì)一個(gè)候選記錄對(duì)是否對(duì)應(yīng)同一實(shí)體。除了使用上述綜合相似度方法來計(jì)算相似度外，也可以用機(jī)器學(xué)習(xí)中的監(jiān)督方法(如支持向量機(jī)、決策樹、EM 算法[3,19]和主動(dòng)學(xué)習(xí)[20])計(jì)算記錄對(duì)的相似性。相似度計(jì)算模塊的輸入是候選數(shù)據(jù)對(duì)象的集合，輸出是每個(gè)候選對(duì)與其相似度組成的三元組。

2.1.2 聚類決定模塊

該模塊基于候選記錄對(duì)的相似度，把表示同一個(gè)實(shí)體的記錄放到一個(gè)簇中。在前一階段作出表象局部相似性判斷后，可以對(duì)實(shí)體進(jìn)行鄰接性聚類、相關(guān)性聚類或密度聚類，利用相似度閾值以及傳遞閉包確定記錄是否屬于同一個(gè)簇。Li 等[10]逐個(gè)判斷每一個(gè)簇和記錄的相似度閾值，選擇相似度最大的記錄和簇：如果這個(gè)相似度的值大于預(yù)先設(shè)定好的閾值，則記錄和簇中表示同一個(gè)實(shí)體，從而把記錄和簇合并，否則為記錄新建一個(gè)簇。如果記錄與多個(gè)簇的相似度都大于閾值，則判斷是否將兩個(gè)簇合并。文獻(xiàn)[21-26]使用多個(gè)已有的聚類算法對(duì)數(shù)據(jù)集合進(jìn)行聚類來得到匹配結(jié)果，獲得了比基于閾值的匹配方法更好的識(shí)別結(jié)果。聚類決定模塊的輸入是相似對(duì)集合，輸出是識(shí)別結(jié)果。

本文重點(diǎn)研究相似度匹配問題以及匹配后的聚類問題，針對(duì)監(jiān)督的實(shí)體識(shí)別提出基于隨機(jī)森林的實(shí)體識(shí)別方法。

2.2 問題描述

真實(shí)世界的實(shí)體用E表示，一個(gè)實(shí)體可能被多個(gè)數(shù)據(jù)記錄(用r表示)所描述，每一個(gè)記錄都包括k個(gè)特征，屬性的特征集記作數(shù)據(jù)對(duì)象集合記對(duì)于任何一個(gè)記錄表示記錄的特征的值。任何一對(duì)數(shù)據(jù)記錄都是候選匹配對(duì)相似對(duì)是三元組，包括一個(gè)候選匹配對(duì)和它們的相似度Simij，記作相似對(duì)構(gòu)成一個(gè)集合

本文提出采用隨機(jī)森林方法計(jì)算記錄的相似性，根據(jù)相似性把表示同一個(gè)實(shí)體的記錄放到相同的簇中。因此，同一個(gè)簇中的記錄表示同一個(gè)實(shí)體，不同簇中的記錄表示不同的實(shí)體。

3 隨機(jī)森林

本文模型中采用余弦相似度來度量記錄屬性的相似度，在計(jì)算記錄的相似性時(shí)采用了隨機(jī)森林的方法。這是因?yàn)殡S機(jī)森林對(duì)有偏差的數(shù)據(jù)有很好的泛化能力。它是以決策樹為基學(xué)習(xí)器，可構(gòu)建多個(gè)基學(xué)習(xí)器，且每個(gè)基學(xué)習(xí)器都能得到記錄的相似性結(jié)果，綜合所有基學(xué)習(xí)器的結(jié)果，得到最終的相似性結(jié)果。

3.1 決策樹

決策樹是一個(gè)樹結(jié)構(gòu)，每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的判斷，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點(diǎn)開始，測試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果。在這個(gè)問題中，根節(jié)點(diǎn)的輸入是兩個(gè)記錄的屬性集合，中間節(jié)點(diǎn)表示對(duì)某個(gè)屬性的決策，葉節(jié)點(diǎn)的輸出結(jié)果表示兩條記錄是否對(duì)應(yīng)于同一個(gè)實(shí)體。

本文采用 ID3 方法。該方法以信息增益和信息增益率兩種方法選擇分裂特征。首先計(jì)算信息熵，用來衡量樣本集合純度的指標(biāo)，其中表示在集合D中第k類樣本所占的比例。則信息增益的計(jì)算公式為：

其次，給定樣本集D和連續(xù)屬性a，將屬性a上出現(xiàn)的n個(gè)值按從大到小排序，記為基于劃分點(diǎn)t將D分為子集和其中，包含那些在屬性a上取值小于t的樣本，而則包含那些在屬性a上取值大于t的樣本，即把的中位點(diǎn)作為候選劃分點(diǎn)。其中，劃分點(diǎn)集合為：

最后分別利用信息增益(Gain)和信息增益率(Gain_ratio)來考察這些劃分點(diǎn)，選擇使 Gain(D,a,t) 最大的劃分點(diǎn)t和對(duì)應(yīng)的特征a作為切分點(diǎn)；以及使 Gain_ ratio(D,a,t) 最大的劃分點(diǎn)t和對(duì)應(yīng)的特征a作為切分點(diǎn)。

3.2 隨機(jī)森林

到目前為止，基于隨機(jī)森林的方法解決了很多實(shí)際問題[27]。本文采用隨機(jī)森林的方法計(jì)算記錄的相似度。隨機(jī)森林是用隨機(jī)的方式建立一個(gè)森林，森林由很多決策樹組成，但決策樹之間不具有關(guān)聯(lián)性。當(dāng)有一個(gè)新的輸入樣本進(jìn)入時(shí)，用森林中的每一棵決策樹分別進(jìn)行判斷，得到該樣本應(yīng)該屬于哪一類(對(duì)于分類算法)；之后判斷哪一類被選擇得最多，據(jù)此預(yù)測該樣本為選擇最多的那一類。而本文提出的隨機(jī)森林的方法，輸入的是一個(gè)記錄對(duì)，通過決策樹判斷該記錄對(duì)是否表示同一個(gè)實(shí)體，整合所有決策樹的結(jié)果，得到記錄對(duì)最終的相似性。

建立決策樹的過程中，需要注意兩點(diǎn)：采樣和完全分裂。首先是兩個(gè)隨機(jī)采樣的過程，隨機(jī)森林對(duì)輸入的數(shù)據(jù)要進(jìn)行行、列采樣。對(duì)于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個(gè)，那么采樣的樣本為n(n＜N)個(gè)。這樣使得在訓(xùn)練的時(shí)候，每一棵樹的輸入樣本都不是全部的樣本，從而不容易出現(xiàn)過擬合。然后進(jìn)行列采樣，從M個(gè)特征中，選擇m個(gè)，一般地，令m＝log2M。之后對(duì)采樣的數(shù)據(jù)使用完全分裂的方式建立決策樹，這樣決策樹的葉子節(jié)點(diǎn)要么是無法繼續(xù)分裂的，要么里面的所有樣本都是指向同一個(gè)分類。

4 算法模型

4.1 基于隨機(jī)森林的相似性算法

計(jì)算兩條記錄的相似性是實(shí)體識(shí)別過程中的基礎(chǔ)。針對(duì)這個(gè)問題，本文提出了一個(gè)隨機(jī)森林算法來計(jì)算記錄的相似性。該算法的思想是，從樣本集N中隨機(jī)選擇n個(gè)樣本和m個(gè)屬性，利用所選的樣本和屬性構(gòu)建一棵決策樹，重復(fù)這個(gè)過程。決策樹的輸出結(jié)果用來計(jì)算兩個(gè)記錄是否表示同一個(gè)實(shí)體，構(gòu)建隨機(jī)森林的詳細(xì)算法見表1。

如算法 1 所示，先把記錄集中所有記錄兩兩配對(duì)，組成一個(gè)三元組其中，ri、rj表示兩條記錄；Simij表示匹配結(jié)果。如果兩個(gè)記錄對(duì)應(yīng)同一個(gè)實(shí)體，則Simij＝1；如果兩個(gè)記錄對(duì)應(yīng)不同實(shí)體，則Simij＝0。然后把這個(gè)三元組添加到集合N中(第 2 行)，有放回地從訓(xùn)練集R中隨機(jī)選擇n個(gè)樣本(每次隨機(jī)選擇一個(gè)樣本，然后返回繼續(xù)選擇)。將選擇好的n個(gè)樣本作為決策樹根節(jié)點(diǎn)處的樣本(第 4 行)，一般選擇N中的 80%，即n＝N×80%。接著，進(jìn)行列采樣，每次隨機(jī)地從所有特征中選擇m個(gè)特征滿足條件(第 5 行)。通過算法 1，已選擇每棵決策樹的數(shù)據(jù)集和特征，接下來就是利用算法2(如表2)對(duì)n個(gè)樣本記錄和m個(gè)特征構(gòu)建決策樹，此時(shí)的決策樹是多變量決策樹。

表1 隨機(jī)森林的算法Table 1 The algorithm of random forest

表2 連續(xù)值的多變量決策樹的訓(xùn)練算法Table 2 The training algorithm of continuous value and multivariable decision tree

多變量決策樹是指每次選擇完一個(gè)切分點(diǎn)aj時(shí)，并不將aj從原始的特征集A中剔除，下次選擇的時(shí)候仍然是從全部選中的特征集中選擇特征和特征值中選擇切分點(diǎn)，即每次都對(duì)所有的特征計(jì)算信息增益或信息增益率的值。

多變量決策樹的構(gòu)建由算法 2 實(shí)現(xiàn)。該算法基本思想是，利用公式(2)計(jì)算所有特征的劃分點(diǎn)集合，并計(jì)算特征和對(duì)應(yīng)劃分點(diǎn)的信息增益的值，最終選擇信息增益最大的值對(duì)應(yīng)的切分點(diǎn)(特征、特征值)，一步步構(gòu)建決策樹。在這個(gè)算法中，先判斷這些實(shí)例是否屬于同一個(gè)類，如果D中所有實(shí)例屬于同一類Ck，則置T為單節(jié)點(diǎn)樹，并將Ck作為該節(jié)點(diǎn)的類，返回T(第 1 行)；否則根據(jù)某特征的特征值對(duì)記錄排序，選擇兩個(gè)連續(xù)的特征值的中值作為切分點(diǎn)的特征值，選擇信息增益最大的切分(amax,t)(第 2～3 行)。如果切分點(diǎn)信息增益的值小于預(yù)先設(shè)定的θ，則此時(shí)樹不再分裂，返回T(第 4～6 行)；否則選擇對(duì)應(yīng)的特征和特征值作為切分點(diǎn)，根據(jù)切分點(diǎn)把數(shù)據(jù)集切分為兩部分(第 7～8 行)，對(duì)應(yīng)于一棵子樹的兩個(gè)分支，分別重復(fù)地在上面的分支上計(jì)算信息增益，選擇切分點(diǎn)、切分子樹，直到子樹不能再分裂(第 9 行)。

以上選用的是計(jì)算信息增益的最大值，同時(shí)還可以計(jì)算信息增益率的最大值，其過程除了計(jì)算公式與前者不同外，其他步驟完全相同。

通過上述過程，已經(jīng)構(gòu)建完k棵決策樹。在計(jì)算兩條記錄的相似性時(shí)，需要用所有決策樹的結(jié)果判斷每棵決策樹的結(jié)果是 1 或 0。因此，最后的相似性使用公式(3)計(jì)算。

其中，n1表示投票結(jié)果是 1 的決策樹個(gè)數(shù)。通過上式可知，Sim(r1,r2)的值越大，則兩個(gè)記錄的相似性越高；該值越小，則兩條記錄的相似性越低。其中，最高相似性的值為 1，表示所有的決策樹都認(rèn)為這兩個(gè)記錄對(duì)應(yīng)的是同一個(gè)實(shí)體；最低相似性的值是 0，表示所有的決策樹都認(rèn)為這兩個(gè)記錄不表示同一個(gè)實(shí)體。

4.2 記錄的聚類模型

通過上文的計(jì)算，可以得到任何兩條記錄的相似性。把具有高度相似性的記錄對(duì)合并成簇，即表示同一個(gè)實(shí)體的記錄合并；使表示同一個(gè)實(shí)體的記錄都放在相同的簇中，表示不同實(shí)體的記錄放在不同的簇中。這個(gè)過程分為兩個(gè)階段：第一階段是核聚類，該過程把能夠確定的具有高度相似的記錄放在同一個(gè)簇中；第二階段是邊緣聚類，或合并剩余的記錄和已知的簇，或合并兩個(gè)已知簇(如圖 2)。核聚類主要是指利用傳遞閉包的思想，如果Sim(r1,r2)＝1 且Sim(r1,r3)＝1，則可以判斷r1、r2、r3表示的是同一個(gè)實(shí)體，即r1、r2、r3位于同一個(gè)簇中。所有的記錄經(jīng)過上述判斷，把表示通過傳遞關(guān)系得到的相似度為1 的記錄對(duì)放在相同的簇中，可以得到幾個(gè)核心簇，每一個(gè)核心簇對(duì)應(yīng)著同一個(gè)實(shí)體，且每個(gè)記錄僅屬于一個(gè)實(shí)體。接著就是利用核心簇的結(jié)果進(jìn)行邊緣聚類。具體過程如算法 3(表3)所示。

圖2 邊緣聚類中合并兩個(gè)簇的情況Fig. 2 The case of merging two clusters

在以上的邊緣聚類算法中，主要處理記錄的相似性在e～1 的記錄對(duì)。將D中的所有結(jié)果分類，把相似度范圍為的三元添加到一個(gè)集合B中(第 2 行)。對(duì)于三元組中的數(shù)，如果r1、r2位于同一個(gè)簇中，則說明兩個(gè)記錄通過前面的傳遞閉包算法，已經(jīng)合并，無需再考慮兩個(gè)記錄(第 5～6 行)。如果r1、r2位于兩個(gè)不同簇中，則先暫時(shí)不考慮這兩個(gè)記錄，為兩個(gè)記錄對(duì)應(yīng)的簇新建一個(gè)三元組如果三元組或(m＞0)在F中已經(jīng)存在，則更新三元組中m值，令m＝m＋1；否則將三元組添加到F中(第 7～12 行)。如果兩個(gè)記錄r1、r2有一個(gè)記錄r1位于已知的簇ci中，另一個(gè)r2沒有位于任何一個(gè)已知的簇中，計(jì)算r2與ci中記錄相似度大于e的個(gè)數(shù)，記為p。如果，則將兩個(gè)記錄都和這個(gè)已知的簇合并，否則為r2新建一個(gè)簇(第 13～18 行)。如果兩個(gè)記錄r1、r2沒有位于任何一個(gè)已知的簇中，則為r1、r2新建一個(gè)簇(第 19～20 行)。接著對(duì)于F中的三元組遍歷，如圖 3 所示，如果中m的值為兩個(gè)簇中連接線的個(gè)數(shù)，且的值，則將兩個(gè)簇合并(第 25～28 行)并將三元組從集合F中刪除，直到F為空。

表3 邊緣聚類算法Table 3 The algorithm of edge clustering

4.3 基于隨機(jī)森林的相似性改進(jìn)算法

利用算法 2 構(gòu)建決策樹時(shí)，在一棵樹的分支部分可能會(huì)出現(xiàn)如圖 3(a)所示的情況。相似度小于 0.68 的記錄對(duì)表示同一個(gè)實(shí)體，而相似度大于0.68 的記錄對(duì)反而表示不是同一個(gè)實(shí)體，這顯然與實(shí)際是相悖的。

圖3 決策樹分裂后產(chǎn)生與事實(shí)相悖情況的子樹圖Fig. 3 The subtree is contrary to the facts in the decision tree

對(duì)于上圖中的問題，有多種解決辦法，本文采用了一個(gè)強(qiáng)制手段。如果按切分點(diǎn)劃分時(shí)出現(xiàn)了圖 3 中的這種情況，強(qiáng)制在該階段不能以該特征和特征值作為切分點(diǎn)。因此進(jìn)一步對(duì)算法 2 進(jìn)行改進(jìn)。在每一次選擇完切分點(diǎn)的時(shí)候進(jìn)行檢查，檢查該切分點(diǎn)中的部分會(huì)不會(huì)輸出結(jié)果為 1(表示同一個(gè)實(shí)體)，如果是，則需要重新選擇下一個(gè)信息增益最大的點(diǎn)，再判斷是否會(huì)產(chǎn)生這種現(xiàn)象。除此之外，還有一種情況如圖 3(b)，即部分的結(jié)果會(huì)輸出 0(表示不同實(shí)體)，即當(dāng)屬性的相似度大于某一個(gè)值時(shí)表示不同的實(shí)體，當(dāng)屬性的相似度小于某一個(gè)值時(shí)反而可能表示相同的實(shí)體。這種情況與前面采取的措施是一樣的，即對(duì)每一個(gè)分割點(diǎn)增加一次判斷。最終的算法如算法 4(表4)所示，該算法與算法 2 基本相同，只是在第 7 行后增加了一次判斷：對(duì)每一個(gè)部分判斷其結(jié)果是不是全是 0(表示不同實(shí)體)；對(duì)每個(gè)部分判斷其結(jié)果是不是全是1(表示相同實(shí)體)，如果不是才可以選擇該點(diǎn)作為切分點(diǎn)，否則重新選擇新的切分點(diǎn)并判斷。

表4 連續(xù)值的多變量決策樹的改進(jìn)算法Table 4 The improved training algorithm of continuous value and multivariable decision tree

5 實(shí)驗(yàn)評(píng)價(jià)

5.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)使用基于 DBLP 數(shù)據(jù)創(chuàng)建的數(shù)據(jù)集。該數(shù)據(jù)集包含了 12 401 條引文記錄，對(duì)應(yīng)于 1 239個(gè)實(shí)體，其屬性包含引文作者姓名、引文標(biāo)題、引文作者單位、引文的其他作者、引文發(fā)表時(shí)間。屬于同一個(gè)實(shí)體的某些屬性可能不同，但屬于不同實(shí)體的某些屬性值也有可能相同。本文通過在此數(shù)據(jù)集上實(shí)驗(yàn)，對(duì)本文提出的基于隨機(jī)森林的實(shí)體識(shí)別算法的性能進(jìn)行測試。

對(duì)算法的性能采用準(zhǔn)確率和召回率進(jìn)行評(píng)價(jià)，采用準(zhǔn)確率和召回率的調(diào)和平均數(shù)F評(píng)價(jià)實(shí)體識(shí)別結(jié)果的精度。

實(shí)驗(yàn)采用 Intel(R)Core(TM)i7-26003.4 GHz處理器，8 G 內(nèi)存，Microsoft Windows 864 位操作系統(tǒng)進(jìn)行數(shù)據(jù)處理。

本實(shí)驗(yàn)旨在解決，變化頻繁且變化與時(shí)間沒有規(guī)律的記錄的實(shí)體識(shí)別問題，從計(jì)算記錄的相似度，到最終的聚類算法都提供了一個(gè)新型的解決方案。

5.2 實(shí)驗(yàn)結(jié)果與分析

5.2.1 參數(shù)測試

在 DBLP 數(shù)據(jù)集上測試決策樹構(gòu)建算法(算法 2)中的信息增益和信息增益率的閾值參數(shù)θ對(duì)最終結(jié)果的影響。由圖 4 可以看出，隨著θ增加，準(zhǔn)確率(P)變化趨勢是先增高后下降，最終趨于穩(wěn)定：在開始階段逐漸增高，達(dá)到最大值后開始下降，最后基本保持不變。召回率(R)的值隨著θ的增大而增加，達(dá)到了最大值后隨著θ的增加緩慢減少。精確性(F)的走向基本和準(zhǔn)確率的一樣：在開始階段逐漸增高，達(dá)到最大值后開始下降，最終趨于穩(wěn)定。在信息增益的試驗(yàn)中，最終結(jié)果最好的θ取值為 0.001 6 時(shí)，準(zhǔn)確率、召回率和精確性都很高；當(dāng)θ＞0.005 時(shí)，準(zhǔn)確率、精度值都很低。在信息增益率的試驗(yàn)中，當(dāng)θ取值為 0.09 時(shí)，準(zhǔn)確率、召回率和精確性都很高；當(dāng)θ＞0.2 時(shí)，準(zhǔn)確率、精度值都很低。閾值較低時(shí)造成了過擬合，閾值較高時(shí)造成了欠擬合，造成了最終結(jié)果出現(xiàn)偏差，準(zhǔn)確率和F精度值都很低。

圖4 在 DBLP 數(shù)據(jù)集上測試參數(shù) θ 對(duì)聚類的影響Fig. 4 Tests of the parameter θ influence on clustering on DBLP

另外，還檢測了 DBLP 數(shù)據(jù)集上聚類算法(算法 4)中的相似度閾值參數(shù)e對(duì)算法效果的影響。從圖 5(a)可以看出，準(zhǔn)確率(P)在開始階段逐漸提高，當(dāng)P達(dá)到最大值后，隨著e的一直增大，P仍能保持較高的水平。召回率(R)隨著e的增大一直維持在較高的水平，之后隨著e的增加開始下降。精確性(F)的走向基本和準(zhǔn)確率是一樣的，隨著e的增大，精確性一直增大到最大值，之后隨著e的增大開始減小。從圖 5(b)可以看到 3 條曲線的走勢和圖 5(a)是一致的。產(chǎn)生這種現(xiàn)象的原因是，相似度閾值越高，越能保證同一個(gè)簇中的記錄越準(zhǔn)確，即準(zhǔn)確率越高，但是簇中發(fā)現(xiàn)的記錄越不全，即召回率越低。

圖5 在 DBLP 數(shù)據(jù)集上測試參數(shù) e 對(duì)聚類的影響Fig. 5 Tests of the parameter e influence on clustering on DBLP

5.2.2 算法性能對(duì)比

本文提出了一個(gè)隨機(jī)森林的相似度計(jì)算方法(RFBas)(見算法 2)以及基于該隨機(jī)森林的相似度算法的改進(jìn)算法(RF)。改進(jìn)算法考慮了事實(shí)情況，構(gòu)建決策樹時(shí)，當(dāng)按某個(gè)相似度分類時(shí)，相似度大于某一個(gè)值判斷為不同實(shí)體，相似度小于某一個(gè)值判斷為相同實(shí)體，把這些與事實(shí)相悖的分類情況剔除，得到最終的聚類結(jié)果。兩個(gè)算法的對(duì)比結(jié)果如圖 6 所示，可以看出改進(jìn)之后的算法，準(zhǔn)確率、召回率和精確性都有所提高。以信息增益為特征選擇方法改進(jìn)后提高了 0.6%，以信息增益率為特征選擇方法改進(jìn)后提高了2.8%，因此改進(jìn)后的決策樹構(gòu)建方法優(yōu)于改進(jìn)前的決策樹構(gòu)建方法。

圖6 基本隨機(jī)森林算法與改進(jìn)算法在 DBLP 數(shù)據(jù)集上對(duì)比Fig. 6 Comparisons between basic RF and improved RF on DBLP

5.2.3 隨機(jī)森林與決策樹方法對(duì)比

本文選擇了兩種劃分決策樹的方法：信息增益和信息增益率，即基于信息增益的決策樹方法和基于信息增益率的決策樹方法，與之對(duì)應(yīng)的是基于信息增益的隨機(jī)森林方法和基于信息增益率的隨機(jī)森林方法。基于這 4 種方法來計(jì)算記錄相似性，結(jié)果如圖 7 所示。由圖 7 可以看出，隨機(jī)森林的方法在準(zhǔn)確率、召回率、F精度值上都比相應(yīng)的決策樹方法要好。產(chǎn)生這種結(jié)果的原因是，隨機(jī)森林的方法綜合了所有結(jié)果的投票，防止了數(shù)據(jù)傾斜。在這個(gè)實(shí)驗(yàn)中，利用信息增益的方法比利用信息增益率方法的F值較高。并且使用信息增益的方法比使用信息增益率算法的P、R、F值都較高，這是因?yàn)樾畔⒃鲆媛矢舆m合于特征值種類比較多的情況。

圖7 基于信息增益和信息增益率的森林算法的對(duì)比Fig. 7 Comparisons between RF+Gain and RF+Gain_ratio

5.2.4 與已有工作對(duì)比

傳統(tǒng)的相似性一般根據(jù)特定匹配規(guī)則度量或利用編輯距離、歐式距離計(jì)算，在做出表象局部相似性判斷后，利用 Rodriguez 等[9]提出的密度聚類。該算法是經(jīng)典的K-mean 算法的改進(jìn)算法，不需要指定聚類中心k值，并且可以檢測非球面類別，通過計(jì)算可以確定k值，但該算法有一定的局限性。之后 Bie 等[28]又提出了該算法的改進(jìn)算法，此時(shí)確定k值不僅僅是依靠圖形，還能依靠計(jì)算公式直接計(jì)算，避免k值確定的偶然性。本文主要與 Bie 等[28]提出的算法(CFSFDP)進(jìn)行對(duì)比。同時(shí)還和傳統(tǒng)的 Partition(簡稱“Part”)方法對(duì)比，結(jié)果如圖 8 所示。

由圖 8 可以看出，在 DBLP 數(shù)據(jù)集上，RF＋Gain 算法的準(zhǔn)確率、召回率和F值都明顯高于其他算法，F(xiàn)值順序?yàn)椋篟F＋Gain＞RF＋Gain_ratio＞CFSFDP＞Part。本文提出的 RFES 算法明顯優(yōu)于其他 3 種算法，以 Part 為基礎(chǔ)，在F精度值上，CFSFDP 高出了 10%，RF＋Gain_ratio高出了 32%，RF＋Gain 算法高出 38%。可見，本文提出的基于隨機(jī)森林的相似度計(jì)算方法和聚類方法加一起比其他實(shí)體識(shí)別方法對(duì)于屬性值在變化，且變化和時(shí)間關(guān)系不規(guī)律的數(shù)據(jù)上更加準(zhǔn)確。分析其原因，本文提出的方法考慮到了屬性的改變，把許多弱分類器的投票綜合起來，使結(jié)果更加可靠可信，同時(shí)提出的聚類算法充分利用上一階段的結(jié)果。因此，對(duì)于數(shù)據(jù)的屬性一直在改變，并且這種改變和時(shí)間的相關(guān)性不大的問題，本文提出的 RF＋Gain 和 RF＋Gain_ratio 算法具有更大的優(yōu)越性。

圖8 改進(jìn)的隨機(jī)森林算法與已有聚類算法在 DBLP 上的對(duì)比Fig. 8 Comparisons between improved RF algorithm and existing clustering algorithm on DBLP

除此之外，本文還和 Li 等[10]提出的動(dòng)態(tài)記錄鏈接算法進(jìn)行比較。該算法中屬性的變化和時(shí)間是有規(guī)律的，某實(shí)體的某個(gè)屬性值，經(jīng)歷的時(shí)間越久，變化為不同值的可能性越大；不同實(shí)體記錄的屬性值，經(jīng)歷時(shí)間越久，變化為相同值的可能性越大。根據(jù)時(shí)間為每一個(gè)屬性分配一個(gè)權(quán)值，在此基礎(chǔ)上提出了 EARLY、LATE、ADJUST 三種聚類算法，這三種算法和本文算法對(duì)比結(jié)果如圖 9 所示。

從圖 9 可以看出，RF＋Gain_ratio 算法在準(zhǔn)確率、召回率和F值都明顯高于其他算法，F(xiàn)值的順序?yàn)椋篟F＋Gain_ratio＞RF＋Gain＞ADJUST＞LATE＞EARLY，本文提出的 RF＋Gain 和 RF＋Gain_ratio 算法明顯優(yōu)于其他三種算法。其原因?yàn)榭紤]時(shí)間特征的記錄鏈接算法，在計(jì)算屬性的權(quán)重時(shí)，某屬性在改變了一個(gè)值后，在很短一段時(shí)間內(nèi)又變回原來值的概率是很低的，即對(duì)屬性在一段時(shí)間內(nèi)反復(fù)變化或者屬性的變化跟時(shí)間關(guān)系不大的問題建模時(shí)是有問題的，它會(huì)為這種頻繁改變的屬性值分配一個(gè)很低的權(quán)重值，影響最后的聚類結(jié)果。因此在屬性變化和時(shí)間變化關(guān)聯(lián)性不大的時(shí)候，本文提出的算法更具有優(yōu)越性。

圖9 改進(jìn)的隨機(jī)森林算法與考慮時(shí)間特征的算法在 DBLP上的對(duì)比Fig. 9 Comparisons between improved RF algorithm and temporal records linking algorithm on DBLP

6 總 結(jié)

實(shí)體識(shí)別對(duì)于數(shù)據(jù)集成和數(shù)據(jù)分析是非常重要的。本文針對(duì)演化數(shù)據(jù)的實(shí)體識(shí)別問題，提出了一個(gè)基于隨機(jī)森林與兩階段聚類的實(shí)體識(shí)別模型。在該問題中，通過訓(xùn)練幾棵決策樹構(gòu)成隨機(jī)森林計(jì)算記錄對(duì)的相似性，并提出了一個(gè)兩階段的聚類算法。最后通過在 DBLP 數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比和分析，驗(yàn)證了該算法的有效性。

[1]Li P, Dong XL, Guo ST, et al. Robust group linkage[C]// International Conference on World Wide Web, 2015: 647-657.

[2]Hernández MA, Stolfo SJ. Real-world data is dirty:data cleansing and the merge/purge problem [J].Data Mining and Knowledge Discovery, 1998, 2(1):9-37.

[3]Elmagarmid AK, Ipeirotis PG, Verykios VS.Duplicate record detection: a survey [J]. IEEE Transactions on Knowledge and Data Engineering,2007, 19(1): 1-16.

[4]Sarawagi S, Bhamidipaty A. Interactive deduplication using active learning [C]// Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002: 269-278.

[5]Charikar M, Guruswami V, Wirth A. Clustering with qualitative information [J]. Journal of Computer and System Sciences, 2005, 71(3): 360-383.

[6]Bansal N, Blum A, Chawla S. Correlation clustering[J]. Machine Learning, 2004, 56(1-3): 89-113.

[7]Davies DL, Bouldin DW. A cluster separation measure [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224-227.

[8]Ester M, Kriegel HP, Sander J, et al. A densitybased algorithm for discovering clusters in large spatial databases with noise [C]// Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining, 1996: 226-231.

[9]Rodriguez A, Laio A. Clustering by fast search and fi nd of density peaks [J]. Science, 2014, 344(6191):1492-1496.

[10]Li P, Dong XL, Maurino A, et al. Linking temporal records [J]. Frontiers of Computer Science, 2012,6(3): 293-312.

[11]Hu YC, Wang Q, Vatsalan D, et al. Improving temporal record linkage using regression classi fi cation[C]// Pacific-Asia Conference on Knowledge Discovery & Data Mining, 2017: 561-573.

[12]Chiang YH, Doan AH, Naughton JF. Tracking entities in the dynamic world: a fast algorithm for matching temporal records [J]. Proceedings of the VLDB Endowment, 2014, 7(6): 469-480.

[13]Chiang YH, Doan AH, Naughton JF. Modeling entity evolution for temporal record matching [C]// ACM SIGMOD International Conference on Management of Data, 2014: 1175-1186.

[14]Li F, Lee ML, Hsu W, et al. Linking temporal records for profiling entities [C]// SIGMOD’15 Proceedings of the ACM SIGMOD International Conference on Management of Data, 2015: 593-605.

[15]Whang SE, Garcia-Molina H. Entity resolution with evolving rules [J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 1326-1337.

[16]Whang SE, Garcia-Molina H. Incremental entity resolution on rules and data [J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2014, 23(1): 77-102.

[17]Gruenheid A, Dong XL, Srivastava D. Incremental record linkage [J]. Proceedings of the VLDB Endowment, 2014, 7(9): 697-708.

[18]Cohen W, Ravikumar P, Fienberg S. A comparison of string metrics for matching names and records[C]// KDD Workshop on Data Cleaning & Object Consolidation, 2003: 73-78.

[19]K?pcke H, Thor A, Rahm E. Evaluation of entity resolution approaches on real-world match problems[J]. Proceedings of the VLDB Endowment, 2010,3(1-2): 484-493.

[20]Arasu A, G?tz M, Kaushik R. On active learning of record matching packages [C]// ACM Sigmod International Conference on Management of Data,2010: 783-794.

[21]Haveliwala T, Gionis A, Indyk P. Scalable techniques for clustering the Web [C]// Third International Workshop on the Web and Databases,2000: 129-134.

[22]Dongen S. Graph clustering by fl ow simulation [D].Utrecht: University of Utrecht, 2000.

[23]Brohée S, Van Helden J. Evaluation of clustering algorithms for protein-protein interaction networks[J]. BMC Bioinformatics, 2006, 7(1): 488.

[24]Flake GW, Tarjan RE, Tsioutsiouliklis K. Graph clustering and minimum cut trees [J]. Internet Mathematics, 2004, 1(4): 385-408.

[25]Cormen TH, Leiserson CE, Rivest RL. Introduction to Algorithms [M]. Cambridge: MIT Press, 1990.

[26]Bansal N, Chiang F, Koudas N, et al. Seeking stable clusters in the blogosphere [C]// VLDB’07 Proceedings of the 33rd International Conference on Very Large Data Bases, 2007: 806-817.

[27]Kim K, Giles CL. Financial entity record linkage with random forests [C]// International Workshop on Data Science for Macro-Modeling, 2016.

[28]Bie RF, Mehmood R, Ruan S. Adaptive fuzzy clustering by fast search and fi nd of density peaks[J]. Personal and Ubiquitous Computing, 2016,20(5): 785-793.