大數據環境下一種基于模式匹配的實體統一方法

熊安萍 詹 妮 鄒 毅 龍林波

1(重慶郵電大學計算機科學與技術學院 重慶 400065)2(重慶郵電大學軟件學院 重慶 400065)3(重慶市公安局網安總隊 重慶 401121)

0 引 言

隨著互聯網、移動互聯網、物聯網的蓬勃發展，數據產生的方式不斷在擴展，數據之間的關系變得千絲萬縷，呈現出大規模數據關聯、交叉和融合的局面[1]。數據融合的概念最初來源于多傳感器數據融合，主要集中于軍事領域。在信息檢索領域也存在數據融合的概念，旨在將多個獨立的數據集上的檢索結果合并成一個統一的結果，使得合并后的檢索效果盡可能接近在一個集中數據集上進行檢索的效果。大數據融合更為具體和形象的解讀在于：通過對融合數據進行實體統一、沖突解決、數據關聯，形成以目標實體為中心的多側面全景視圖[2]。實體統一一直以來都是數據融合和數據清洗中的重點研究內容，是指將表示同一現實世界實體的不同記錄識別出來，并進行合并，從而達到消除數據冗余，提高數據質量的目的，其結果影響著數據質量[3-4]。

1 相關概念

當前實體統一主要有三種基本的解決思路，第一種是窮盡式的實體統一即傳統的實體統一方法，通過兩兩比較數據集中的所有實體即實體匹配操作，判斷兩個實體是否為同一個實體。這種傳統實體統一算法計算代價是相當高的，其主要針對小數據集，重點關注統一結果的準確性。隨著大數據時代的到來，傳統的實體統一方法由于時間復雜度較高，難以處理大規模數據。

第二種思路是基于分塊[5]的實體統一，例如標準分塊(Standard Blocking)[6]方法定義了塊的鍵值，具有相同塊鍵值的實體同屬于一個塊中，初步將較為相似的實體劃分到同一個塊中，大大減少了匹配次數，時間復雜度由O(n2)降低為O(θ×n)，但其匹配操作僅在塊內進行，忽略了塊間存在同屬于一個實體的實體。近鄰排序(Sorted Neighborhood Blocking)[7]的分塊方法解決了塊間匹配的問題，先將記錄按照特定的屬性值進行排序，然后對排序的記錄利用固定長度的滑動窗口進行掃描，只有在同一窗口中的記錄才進行匹配。該方法的一個主要不足在于滑動窗口的大小是固定的，如何確定窗口的大小成為一個關鍵的問題。如果窗口較大會影響效率，如果窗口較小又會導致相似但距離較遠的實體無法被包括在同一個滑動窗口下。Yan等[8]對近鄰排序法進行了優化，提出一種動態改變滑動窗口大小的算法。Baxter等[9]運用基于q-gram的索引方法，將每個實體根據它的塊鍵值所生成的變形被插入到多個塊中。Canopy聚類[10]算法通過快速計算塊鍵值的距離，將每條記錄插入到一個或多個重疊的塊中。該算法雖然精度較低，但在速度上具有很大優勢，適用于對待實體統一數據的預處理。

第三種則是基于分布式架構的實體統一，采用MapReduce模型提高實體統一計算效率成為目前較為流行的研究方向[11-12]。文獻[11]提出依賴度的概念，篩選出與原分塊中依賴度較低的實體進行二次匹配，并通過設定跨度距離來控制二次匹配的實體數量，雖然能有效提高時間效率，但在二次匹配中若設置較大的跨度距離，則會忽略需要二次匹配的實體對。

綜上所述，現有的實體統一算法往往統一結果準確性高則時間開銷就會較大，且大規模數據下仍然時間效率不高。而基于分布式架構的實體統一方法盡管還不夠成熟，但已成為海量數據環境下數據融合處理的有效途徑。本文提出一種大數據環境下基于模式匹配的實體統一方法，在一定程度上確保結果有效性的同時，提高實體統一計算效率，能夠從大規模數據中更快速地篩選出有價值的數據。

2 實體統一算法模型

在大數據平臺下如何高效實現實體統一往往成為某些業務應用的重要標準。Spark是一個分布式并行處理模型，有效結合了Hadoop和自身的優點，能夠快速地進行迭代計算。本文提出的算法模型以Spark集群為基礎，結合分塊計算、塊內實體迭代匹配計算，并考慮到塊間存在同一實體的情況，從這三個方面來控制和減少匹配的計算量，并保持實體統一結果的精度。

2.1 算法模型

本文實體統一算法模型包括3個模塊——數據分塊模塊、模式匹配和抽取模塊、模式合并模塊，如圖1所示。

圖1 實體統一算法模型

(1) 數據分塊模塊 由于標準分塊算法[6]能大大控制后續計算量，因此該模塊利用標準分塊算法初步將較為相似的數據劃分到同一個塊中。輸入為待統一數據，輸出為實體集合R={R1,R2,…,Ri,…,Rn},1≤i≤n，每個實體集合對應到相應的塊集B中B={B1,B2,…,Bi,…,Bn},1≤i≤n。

(2) 模式匹配和抽取模塊 本文在基于編輯距離的模式匹配算法IterER[15]基礎上提出一種基于模式快速掃描的實體統一算法 PRSER (Entity Resolution Based on Pattern Rapid Scanning)來計算實體對相似度。首先運用PRSA算法(Pattern Rapid Scanning Algorithm)對實體對進行快速掃描，再利用模式抽取算法PEA(Pattern Extract Algorithm)，即將匹配的實體對通過IterER算法進行回溯，得到相似實體的模式。輸入為記錄集合R，輸出每塊中的模式集合，例如塊Bi內模式集M={Mi1,Mi2,…,Mix},x∈C。

(3) 模式合并模塊 該模塊再次利用PRSER算法，將塊間的模式進行匹配，并對相似的模式進行合并。輸入為每塊中的模式集合，輸出為匹配后的模式集合，每一個匹配后的模式集合對應一個實體。

2.2 相似度計算

判斷兩個實體是否為同一個實體，通常需要計算實體間的相似度。一般而言，一個實體包含多個屬性，而每個屬性可能存在不同的數據類型，針對不同類型的數據其相似度計算方法也有所不同，比如數值型數據間相似度計算可以利用數學公式設計相應的相似度函數。大數據環境下，文本型數據居多且相比于其他類型屬性相似度計算困難，因此本文將重點討論基于文本類型的實體相似度計算方法。然后，通過各屬性相似度加權求和的方式得出一個綜合相似度值，并與設定閾值相比較，各屬性權值可以由領域內專家分配，也可以通過機器學習獲得。常見的基于文本類型相似度計算方法有編輯距離算法、Jaro-Winkler算法、TF-IDF算法等。其中編輯距離算法[13]廣泛應用于實體統一。該算法通過插入、替換和刪除操作將一個字符串轉化為另一個字符串所需要的最少操作次數，即兩個字符串的距離。文獻[14]對傳統的編輯距離算法進行了優化，提出Damerau-Levenshtein編輯距離增加了一個相鄰字符調換的操作。

(1)

式中：

(2)

(3)

(4)

2.3 模式快速掃描算法(PRSA)

每一個塊中的實體之間都有一定相似性。首先通過標準分塊算法進行預處理，將較為相似的實體劃分到了一個塊中。基于這種特性，可以對塊內實體相同的部分進行統一，不同的部分進行保留，從而形成特定的涵蓋具有相似性實體的一個模式。例如利用文獻[15]中基于編輯距離的模式生成算法使得塊內實體集合R:{halloword,helloworld}的對應模式為M:h{e,a}llowor{l,ε}d。

現在可以將實體間的匹配操作轉換成其對應的模式之間的匹配操作。設兩個模式M1=M1[1]，M1[2]，…，M1[x]和M2=M2[1]，M2[2]，…，M2[y]，其中，x和y分別為M1和M2的長度，且x≥y。首先將它們進行快速掃描，算法描述如算法1所示。

算法1模式快速掃描算法PRSA。

輸入：兩個不同的模式M1、M2和各自的長度x、y，且x≥y；

1.初始化i和index

/*假設數組下標i從1開始，下標數組index*/

2.whilei<=ydo

3. ifM1[i]∩M2[i]≠φthen

/*兩個模式對應位置元素存在交集*/

4.M12[i]←M1[i]∪M2[i]

/*將對應位置元素的并集插入合并模式M12對應位置元素中*/

5. else

6. 將i插入index中

8.i←i+1

9.fori←y+1 toxdo

10.M12[i]←M1[i]∪ε

/*將不與M2對應的元素

/與ε求并集，并插入合并模式M12對應位置元素中*/

11.returnM

2.4 模式抽取算法(PEA)

(5)

算法2模式抽取算法PEA。

輸出：模式M1、M2的共同模式M12；

1.初始化i

/*假設數組下標i從1開始*/

2.ifsim(M1,M2)>=ζthen

4. fori←index.lengthto 1 do

6.endif

7.returnM12

3 實驗及結果分析

實驗部署的Spark集群環境由6個節點(1個主節點)構成，每個節點的內存為6 GB，Intel(R) Xeon(TM) CPU X5560@2.80 GHz，實驗程序運用Scala編寫。本文使用DBLP數據集和CiteSeer數據集作為實驗數據。其中DBLP數據集是公用的實體統一測試數據集，且數據集中對需要被識別出的同一篇論文的不同記錄作了標注，有助于對實驗結果進行有效評價。CiteSeer論文數據庫包含近1 400萬條文獻引用，包括作者、標題、出版社、日期、卷號等屬性，為了方便，設置標題屬性作為一個實體。實驗中實體對個數達到107數量級。本文從算法的有效性和效率兩方面與IterER算法進行比較，驗證其在保證實體統一精度的情況下的計算量。由于DBLP擁有標準的匹配準則，因此采用準確率(Precision)、召回率(Recall)和F-值(F-measure)來評估算法的有效性。效率方面，通過算法執行的記錄比較次數和運行時間來比較其性能。

圖2、圖3所示是本文提出的基于模式快速掃描的實體統一PRSER算法與IterER算法分別在DBLP和CiteSeer上比較的結果。可看出在不同數據集上，隨著閾值的變化兩個算法的有效性即準確率、召回率、F-值曲線圖非常接近。PRSER算法的F-值普遍略低于IterER算法的F-值，這是由于PRSER算法在進行模式抽取的時候會引入更多不相關的實例，從而使得PRSER算法的準確率略低于IterER算法，但是在可接受范圍內。從結果可以看出隨著閾值越來越低，不匹配的實體就越來越容易被合并在一起，使得召回率不斷升高的同時準確率不斷降低，當閾值取0.3和0.4時，其召回率趨近于1，而準確率也變得非常低，使得F-值也隨之降低。由此可推斷出當閾值繼續降低趨近于0時，F-值會越來越低，實體統一的效果也變得越來越差，不具有參考意義。在DBLP上閾值取0.5和0.6時，CiteSeer上閾值取0.6和0.7時，F-值相對最高。

圖2 DBLP數據量為1 GB，有效性隨閾值變化情況對比

圖3 CiteSeer實體對數為1×107，有效性隨閾值變化情況對比

圖4、圖5為PRSER算法與IterER算法分別在DBLP和CiteSeer上運行時間的比較結果，可以看出在不同數據集上，隨著閾值的變化兩個算法的運行時間的走勢較為相似，隨著閾值的降低運行時間有所下降，這是因為閾值的減小導致模式的合并操作有所增加，使得形成的實體集共同模式的總數減少，因此比較次數也會減少。但隨著閾值的繼續降低，每輪需要迭代合并的實體增多，迭代的輪數也有可能增加，實體集的共同模式也會變得更加繁瑣，導致模式間的相似度計算變得更復雜，從而使得運行時間產生回升。當在DBLP上閾值降低到0.3和0.4時，CiteSeer上閾值降低到0.3時，運行時間下降比較明顯，這是因為模式中引入了較多不相關的實例，使得實體集共同模式的總數明顯減少。從圖4、圖5中可以看出，由于本文提出的PRSER算法在相似度計算時節省了一定的時間計算開銷，所以其運行時間總體來說比IterER算法要少。

圖4 DBLP數據量為1 GB，運行時間隨閾值變化情況對比

圖5 CiteSeer實體對數為1×107，運行時間隨閾值變化情況對比

通過增加數據量，并選取各數據量下最高的F-值，得到兩個算法分別在DBLP和CiteSeer上F-值和運行時間的比較，如圖6、圖7所示。從圖6中可以看出，在不同數據集上隨著數據量大小不斷擴大，PRSER算法的F-值總體略微低于IterER算法，但兩個算法均保持在0.9以上。圖7反映了兩算法隨著數據量大小的增加，迭代次數也急劇增加，圖7(a)運行時間呈指數級的增長，圖7(b)呈線性增長，但PRSER算法的增長速度始終小于IterER算法，同時也說明PRSER算法在處理大數據的實體統一更有優勢。

(a) DBLP

(b) CiteSeer圖6 F-值隨數據量大小變化情況對比

(a) DBLP

上述實驗表明，本文提出的實體統一算法模型能夠有效處理大數據下的實體統一，同時基于模式快速掃描的實體統一算法能夠在盡量保證統一結果準確性的前提下，提高實體統一的效率。

4 結 語

在大數據環境下，實體統一算法對時間效率的要求越來越高。本文在一定程度上確保結果有效性的同時，重點關注如何更快速地從大數據集中得到我們需要的數據實體。因此提出了一種大數據環境下實體統一算法模型，在現有方法的基礎上提高實體統一的效率。通過在Spark平臺進行實驗，驗證了該方法在確保實體統一有效性的同時，獲得了良好的時效性。在模塊負載平衡策略基礎上，進一步提高實體統一效率是本文的下一步工作。