數(shù)據(jù)倉庫下基于學(xué)習(xí)的并行實體解析算法研究

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

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

關(guān)鍵詞：數(shù)據(jù)倉庫；數(shù)據(jù)質(zhì)量；實體解析；自主學(xué)習(xí)；并行計算

DOIDOI：10.11907/rjdk.172274

中圖分類號：TP312

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

0 引言

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

1 算法理論

1.1 實體解析概念

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

實體：對應(yīng)現(xiàn)實存在的數(shù)據(jù)對象。

元組：對實體的描述。

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

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

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

1.2 基于學(xué)習(xí)的實體解析算法設(shè)計

基于學(xué)習(xí)的實體解析算法設(shè)計如圖1所示。

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

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

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

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

1.3 基于Hadoop的并行實體解析算法設(shè)計

將算法運用于并行環(huán)境下，基于Hadoop框架實現(xiàn)基于學(xué)習(xí)的實體解析模型的并行處理[7-8]，算法具體實現(xiàn)步驟如下：

Step1：并行環(huán)境下實體分塊。

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：并行環(huán)境下實體相似度計算。

Map（）：

Input：

Output：

Output：

Reduce（）：

Input：

Input：

Output：

Output：

Step3：并行環(huán)境下實體匹配。

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 實驗及結(jié)果分析

本文利用某煙草集團數(shù)據(jù)中心的數(shù)據(jù)源，在基于學(xué)習(xí)的并行實體解析算法理論指導(dǎo)下進行了仿真驗證，如圖2所示。

2.1 實驗數(shù)據(jù)來源

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

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

圖中具體數(shù)據(jù)含義如表1所示。

集成后有質(zhì)量問題的數(shù)據(jù)如表2所示。

2.2 評價標準

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

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

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

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

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

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

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

其中，T1為單機環(huán)境下處理時間，TP為P個并行節(jié)點下的處理時間。

2.3 實驗環(huán)境

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

2.4 實驗結(jié)果分析

2.4.1 算法精確度分析

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

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

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

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

根據(jù)計算，發(fā)現(xiàn)在進行閾值規(guī)則識別、人工分配各屬性權(quán)值時，屬性1、2及5所占權(quán)重較大，屬性4對識別結(jié)果幾乎無影響。基于此分別采用兩種算法進行識別計算。

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

由此可見，基于學(xué)習(xí)算法的3種評價指標的平均值都明顯優(yōu)于基于閾值規(guī)則算法。

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

由表6可以看出，自主學(xué)習(xí)的F1值比閾值規(guī)則的F1值高，而且隨著元組對象數(shù)據(jù)量的增大，自主學(xué)習(xí)的F1值下降平緩，閾值規(guī)則的F1值則下降明顯。由此可見，基于學(xué)習(xí)算法優(yōu)于基于閾值規(guī)則算法。

2.4.2 并行處理效率分析

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

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

兩種環(huán)境下具體運行時間如表7所示。

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

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

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

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

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

3 結(jié)語

基于學(xué)習(xí)的實體解析算法在實體解析中降低了人工經(jīng)驗存在的誤差，減少了識別結(jié)果對人工經(jīng)驗的依賴，具有較高的準確性；基于Hadoop的并行實體解析算法，能夠?qū)Ａ繑?shù)據(jù)進行快速有效的處理；基于學(xué)習(xí)的并行實體解析算法以提高識別精度、減小計算時間為目標，克服了傳統(tǒng)實體解析算法中對于人工經(jīng)驗的依賴，同時改善了傳統(tǒng)算法對數(shù)據(jù)倉庫中海量數(shù)據(jù)不能快速有效地進行處理等問題，使在對海量數(shù)據(jù)進行快速有效處理的同時，還能取得較高的準確性和良好的時間效率。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] 王超文.面向結(jié)構(gòu)化數(shù)據(jù)的實體解析方法[D].哈爾濱：哈爾濱工程大學(xué)，2014.

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

[7] 湛文紅.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘?qū)嵗治鯷J].軟件導(dǎo)刊，2013（2）：99-102.

[8] 劉棟，王黎峰，張懷鋒.基于大數(shù)據(jù)的統(tǒng)計分析模型設(shè)計[J].軟件導(dǎo)刊，2016（7）：28-30.

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

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

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

[12] 黎玲利.實體識別關(guān)鍵技術(shù)的研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2015.endprint