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

(東北大學計算機科學與工程學院 沈陽 110819)

1 引 言

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

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

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

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

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

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

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

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

(2)提出一個新型的兩階段聚類算法。簇的聚類過程分為兩個階段：第一階段進行核聚類，把盡可能多的已經(jīng)確定的記錄放在相同的簇中；第二階段進行端點聚類，能夠將剩余的記錄和已知的簇合并或者合并已有的簇，保證簇內記錄盡可能完整，盡可能多的簇被發(fā)現(xiàn)。

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

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

2 準備工作

2.1 實體識別模型

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

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

2.1.1 相似度計算模塊

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

2.1.2 聚類決定模塊

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

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

2.2 問題描述

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

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

3 隨機森林

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

3.1 決策樹

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

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

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

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

3.2 隨機森林

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

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

4 算法模型

4.1 基于隨機森林的相似性算法

計算兩條記錄的相似性是實體識別過程中的基礎。針對這個問題，本文提出了一個隨機森林算法來計算記錄的相似性。該算法的思想是，從樣本集N中隨機選擇n個樣本和m個屬性，利用所選的樣本和屬性構建一棵決策樹，重復這個過程。決策樹的輸出結果用來計算兩個記錄是否表示同一個實體，構建隨機森林的詳細算法見表1。

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

表1 隨機森林的算法Table 1 The algorithm of random forest

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

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

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

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

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

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

4.2 記錄的聚類模型

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

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

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

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

4.3 基于隨機森林的相似性改進算法

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

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

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

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

5 實驗評價

5.1 實驗設置

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

對算法的性能采用準確率和召回率進行評價，采用準確率和召回率的調和平均數(shù)F評價實體識別結果的精度。

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

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

5.2 實驗結果與分析

5.2.1 參數(shù)測試

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

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

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

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

5.2.2 算法性能對比

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

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

5.2.3 隨機森林與決策樹方法對比

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

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

5.2.4 與已有工作對比

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

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

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

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

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

圖9 改進的隨機森林算法與考慮時間特征的算法在 DBLP上的對比Fig. 9 Comparisons between improved RF algorithm and temporal records linking algorithm on DBLP

6 總 結

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

[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.