數據倉庫下基于學習的并行實體解析算法研究

劉葉+吳晟+吳興蛟+周海河+李英娜+張晶

摘 要：為了改善傳統實體解析算法在單機環境下采用人為方式設定屬性權值及閾值難以對海量數據進行快速有效處理的缺點，基于Hadoop框架使用MapReduce計算模型，在多節點分布式環境下，通過不斷調整網絡學習屬性之間的內在關系以及屬性權值、閾值等參數后，再將模型放在Hive數據倉庫中的真實數據集上進行有效性驗證。分別使用5 000及9 000條數據進行實驗，實驗結果表明，基于學習的并行實體解析算法準確率、召回率和F1值較高。因此，基于學習的并行實體解析算法對于海量數據不僅能進行快速有效的處理，而且能有效降低人工經驗中存在的誤差，同時也能提高識別結果的準確度，提升識別效率。

關鍵詞：數據倉庫；數據質量；實體解析；自主學習；并行計算

DOIDOI：10.11907/rjdk.172274

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）002-0019-04

0 引言

目前實體解析的研究工作主要包括概率、規則、聚類、學習以及集體等多種方法[1-4]?；诟怕实姆椒ㄊ亲钤鐟糜趯嶓w解析的技術，然而該模型需要在先驗概率情況下，對條件概率分布進行獨立性假設，因此很難在實際應用中進行實踐?；陂撝档膶嶓w解析是傳統的實體匹配方法，也是目前應用最廣泛的實體匹配技術。然而由于元組相似度和屬性相似度之間是一種非線性映射關系，所以這種方法往往不能取得較好的識別效果。近年來，基于統計學和機器學習的實體解析匹配技術被提出并實現，如何獲取訓練數據集以及如何對數據進行處理是整個算法性能的關鍵。本文為了提高實體解析的效率及準確率，降低識別處理時間，同時實現高效地解析數據倉庫中的海量數據實體，提出了基于學習的并行實體解析算法。

1 算法理論

1.1 實體解析概念

首先給出實體解析在本文的部分基本模型概念[5]：

實體：對應現實存在的數據對象。

元組：對實體的描述。

實體對：描述實體的兩個元組的組合。

屬性：對實體某一特征或性質的描述。

關鍵屬性：描述在同一實體中，具有相同或相似屬性特征的不同元組。

1.2 基于學習的實體解析算法設計

基于學習的實體解析算法設計如圖1所示。

對實體解析算法的研究主要抽象為實體分塊、元組對比較和實體匹配3個方面[6]。算法步驟如下：

Step1-Step4（實體分塊）：對實體進行分塊。通過一定規則，把指代不同實體的元組對劃分到不同集合中，降低元組對比較的復雜度。

Step5-Step9（元組對比較）：對元組對進行比較。通過實體分塊后形成相似元組對集合，計算元組詞特征相似度，提取元組對的特征向量。通過設定的相似度比較函數，計算元組之間的相似程度，為進一步識別不同元組是否代表相同實體提供依據。

Step10（實體匹配）：對實體進行匹配。為識別它們是否代表同一實體，需要對數據集中相似的元組對進行匹配。

1.3 基于Hadoop的并行實體解析算法設計

將算法運用于并行環境下，基于Hadoop框架實現基于學習的實體解析模型的并行處理[7-8]，算法具體實現步驟如下：

Step1：并行環境下實體分塊。

Map（）：

CV=[]

CV=random（CS）

While CS is not null

DV=random（CS）

Canopy（set）={（CV，DV）：

DV in CS and Sim（CV，DV）>=T1}

Merge（CV，DV）

Canopy（set）={（CV，DV）：

DV in CS and S （CV，DV）>=T2}

CS=CS-{DV}

return CV

Reduce（）：

While CV is not null

Sim（CV，CV）>=T1

Merge（CV，CV）

Step2：并行環境下實體相似度計算。

Map（）：

Input：

Output：

Output：

Reduce（）：

Input：

Input：

Output：

Output：

Step3：并行環境下實體匹配。

Map（）：

random（L_i）

for i in range（nmax）

for j in range（M）

selectPher （qmax）

updatePher （q）

calcTransprob（）

Output（key，value）

Reduce（）：

for T in range（tmax）

for Et>emin

for each data in ω[i]

getBackweight（self）

updateWeight（b_w，l_r，t）

calcWeight（key=ω[i]，value=∑ni=1Δω/n）

Output（key=ω，value=∑ni=1Δω/n）

2 實驗及結果分析

本文利用某煙草集團數據中心的數據源，在基于學習的并行實體解析算法理論指導下進行了仿真驗證，如圖2所示。

2.1 實驗數據來源

實驗數據源包括集團不同下屬分廠以及部門提供的62 122條供應商數據，利用本文所述模型及算法對其進行實驗評價。

不同來源的數據按照一定規則，通過ETL抽取到數據倉庫中，使大部分的數據質量問題得到解決，但是表示同一實體的數據冗余問題還有待進一步解決，如圖3所示。

圖中具體數據含義如表1所示。

集成后有質量問題的數據如表2所示。

2.2 評價標準

為了評價模型，本文針對計算方法、處理框架、實體解析模型提出以下評價標準：

（1）性能指標。本實驗采用了信息處理和統計分類領域中常用的準確率、召回率和F1值指標體系對實驗結果進行性能評價[9-11]。一般令真實結果為S，實驗結果為R。

準確率計算為所有“正確被檢索的”占所有“實際被檢索到的”數據的比例，其計算公式可表示為：

召回率計算的是所有“正確被檢索的”占所有“應該檢索到的”數據的比例，其計算公式可表示為：

F1值表示準確率和召回率的調和平均值，其計算公式可表示為：

（2）并行處理效率。加速比是指在單處理器系統和并行處理器系統中，同一任務運行消耗的時間比率。

以SP表示加速比，其計算公式可表示為：

其中，T1為單機環境下處理時間，TP為P個并行節點下的處理時間。

2.3 實驗環境

本文基于Hadoop框架搭建分布式計算環境。其部分軟硬件環境如表3所示。

2.4 實驗結果分析

2.4.1 算法精確度分析

實驗數據使用供應商名稱、供應商簡稱、供應商類型、城市、通訊地址等屬性，在數據量分別為5 000與9 000條的環境下進行對比。其中冗余元組對有1 658條。

利用所述算法對數據集進行驗證[12]。首先以屬性4作為關鍵屬性，結合Python分詞庫算法，分別對數據集和屬性值進行初步的分塊處理和分詞處理，同時利用TF-IDF算法，獲取屬性中每個單詞的權重信息。計算元組對的余弦相似度和屬性值的位置編碼相似度，并使用神經網絡進行訓練。其中設置神經網絡期望輸出值：當輸出為1時代表元組對匹配，輸出為0時代表元組對不匹配。

設置目標函數的誤差為0.01，學習率為0.2，設置輸入節點為5個，輸出節點為2個，隱含層單元為6層，最大迭代次數為500，訓練樣本占2/3，其余為測試樣本，螞蟻數目定義為20。隨機賦予初始權值閾值進行訓練。

計算后部分元組對屬性相似度值如表4所示。

根據計算，發現在進行閾值規則識別、人工分配各屬性權值時，屬性1、2及5所占權重較大，屬性4對識別結果幾乎無影響?；诖朔謩e采用兩種算法進行識別計算。

兩種算法的3種評價指標具體實驗結果如表5所示。

由此可見，基于學習算法的3種評價指標的平均值都明顯優于基于閾值規則算法。

兩種算法的F1值具體實驗結果如表6所示。

由表6可以看出，自主學習的F1值比閾值規則的F1值高，而且隨著元組對象數據量的增大，自主學習的F1值下降平緩，閾值規則的F1值則下降明顯。由此可見，基于學習算法優于基于閾值規則算法。

2.4.2 并行處理效率分析

首先對基于單機環境和并行環境下處理不同規模的數據集進行試驗，采用運行時間作為評價標準進行分析。

選擇一個節點作為單機環境，分析5個不同數量的實體對象運行時間，再選擇兩個節點作為并行環境，采用1個主節點和4個計算節點對相似元組對進行實體解析實驗。運行時間分別如圖6所示。

兩種環境下具體運行時間如表7所示。

由此可見，在單機環境下，隨著數據集合中數據量的增大，識別相似元組對所花費的時間也會明顯增加，同時識別每一個相似元組對花費的平均時間明顯減少。在并行環境下，當數據量較小時，單機環境和并行環境下的運行時間差別相對較小，計算效率沒有明顯提高；隨著數據量不斷增大，單機環境下的運行時間明顯增加。

針對基于單節點和多節點模式下處理相同規模的數據集進行實驗，采用加速比衡量實體解析結果的性能和效果。實驗結果如圖7所示。

縱坐標分別為計算時間和加速比，橫坐標為節點個數，元組對象為50 000個數據。

不同節點個數下計算時間和加速比的具體實驗結果如表8所示。

因此可見，計算時間隨著節點數目的增加而不斷減少，當節點數目為1時，即為單機環境下的運行時間。當節點數目增大時，計算時間減少相對明顯；但是當節點數成倍地參與計算時，其計算時間并沒有減小到一半，這可能是因為數據不均勻分布以及節點交互需要消耗一定的處理時間。因此，可以在多節點模型下充分利用分布式處理的擴展性優勢，調動多個節點對任務的并行計算，提高計算的性能和效率。

3 結語

基于學習的實體解析算法在實體解析中降低了人工經驗存在的誤差，減少了識別結果對人工經驗的依賴，具有較高的準確性；基于Hadoop的并行實體解析算法，能夠對海量數據進行快速有效的處理；基于學習的并行實體解析算法以提高識別精度、減小計算時間為目標，克服了傳統實體解析算法中對于人工經驗的依賴，同時改善了傳統算法對數據倉庫中海量數據不能快速有效地進行處理等問題，使在對海量數據進行快速有效處理的同時，還能取得較高的準確性和良好的時間效率。endprint

參考文獻：

[1] NEWCOMBE H B， KENNEDY J M， AXFORD S J， et al. Automatic linkage of vital records[J]. Science，1959，130（3381）：954-959.

[2] FELLEGI I P， SUNTER A B. A Theory for record linkage[J]. Journal of the American Statistical Association，1969，64（328）：1183-1210.

[3] WANG Y R， MADNICK S E. The inter-database instance identification problem in integrating autonomous systems[C].International Conference on Data Engineering，1989.Proceedings.IEEE，1989：46-55.

[4] BAMFORD R， BUTLER D， KLOTS B， et al. Architecture of oracle parallel server[C].International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1998：669-670.

[5] 王超文.面向結構化數據的實體解析方法[D].哈爾濱：哈爾濱工程大學，2014.

[6] 何峰權，李建中.基于屬性模式的實體識別框架[J].智能計算機與應用，2014，4（1）：65-68.

[7] 湛文紅.數據倉庫與數據挖掘實例分析[J].軟件導刊，2013（2）：99-102.

[8] 劉棟，王黎峰，張懷鋒.基于大數據的統計分析模型設計[J].軟件導刊，2016（7）：28-30.

[9] 燕彩蓉，張洋舜，徐光偉.支持隱私保護的眾包實體解析[J].計算機科學與探索，2014，8（7）：802-811.

[10] 黃敏.大數據下基于塊依賴的實體解析方法[D].北京：北京交通大學，2015.

[11] 甄靈敏，楊曉春，王斌，等.基于屬性權重的實體解析技術[J].計算機研究與發展，2013，50（S1）：281-289.

[12] 黎玲利.實體識別關鍵技術的研究[D].哈爾濱：哈爾濱工業大學，2015.endprint