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

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

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

DOIDOI：10.11907/rjdk.172274

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）002-0019-04

0 引言

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

1 算法理論

1.1 實(shí)體解析概念

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

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

元組：對(duì)實(shí)體的描述。

實(shí)體對(duì)：描述實(shí)體的兩個(gè)元組的組合。

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

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

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

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

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

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

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

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

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

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

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

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)境下實(shí)體相似度計(jì)算。

Map（）：

Input：

Output：

Output：

Reduce（）：

Input：

Input：

Output：

Output：

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

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 實(shí)驗(yàn)及結(jié)果分析

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

2.1 實(shí)驗(yàn)數(shù)據(jù)來源

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

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

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

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

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

為了評(píng)價(jià)模型，本文針對(duì)計(jì)算方法、處理框架、實(shí)體解析模型提出以下評(píng)價(jià)標(biāo)準(zhǔn)：

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

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

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

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

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

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

其中，T1為單機(jī)環(huán)境下處理時(shí)間，TP為P個(gè)并行節(jié)點(diǎn)下的處理時(shí)間。

2.3 實(shí)驗(yàn)環(huán)境

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

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

2.4.1 算法精確度分析

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

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

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

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

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

兩種算法的3種評(píng)價(jià)指標(biāo)具體實(shí)驗(yàn)結(jié)果如表5所示。

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

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

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

2.4.2 并行處理效率分析

首先對(duì)基于單機(jī)環(huán)境和并行環(huán)境下處理不同規(guī)模的數(shù)據(jù)集進(jìn)行試驗(yàn)，采用運(yùn)行時(shí)間作為評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行分析。

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

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

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

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

縱坐標(biāo)分別為計(jì)算時(shí)間和加速比，橫坐標(biāo)為節(jié)點(diǎn)個(gè)數(shù)，元組對(duì)象為50 000個(gè)數(shù)據(jù)。

不同節(jié)點(diǎn)個(gè)數(shù)下計(jì)算時(shí)間和加速比的具體實(shí)驗(yàn)結(jié)果如表8所示。

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

3 結(jié)語

基于學(xué)習(xí)的實(shí)體解析算法在實(shí)體解析中降低了人工經(jīng)驗(yàn)存在的誤差，減少了識(shí)別結(jié)果對(duì)人工經(jīng)驗(yàn)的依賴，具有較高的準(zhǔn)確性；基于Hadoop的并行實(shí)體解析算法，能夠?qū)Ａ繑?shù)據(jù)進(jìn)行快速有效的處理；基于學(xué)習(xí)的并行實(shí)體解析算法以提高識(shí)別精度、減小計(jì)算時(shí)間為目標(biāo)，克服了傳統(tǒng)實(shí)體解析算法中對(duì)于人工經(jīng)驗(yàn)的依賴，同時(shí)改善了傳統(tǒng)算法對(duì)數(shù)據(jù)倉庫中海量數(shù)據(jù)不能快速有效地進(jìn)行處理等問題，使在對(duì)海量數(shù)據(jù)進(jìn)行快速有效處理的同時(shí)，還能取得較高的準(zhǔn)確性和良好的時(shí)間效率。endprint

參考文獻(xiàn)：

[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ù)的實(shí)體解析方法[D].哈爾濱：哈爾濱工程大學(xué)，2014.

[6] 何峰權(quán)，李建中.基于屬性模式的實(shí)體識(shí)別框架[J].智能計(jì)算機(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)計(jì)分析模型設(shè)計(jì)[J].軟件導(dǎo)刊，2016（7）：28-30.

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

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

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

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