蟻群BP神經(jīng)網(wǎng)絡(luò)實體解析匹配研究

劉葉　吳晟　吳興蛟

摘要：

為了改進(jìn)BP神經(jīng)網(wǎng)絡(luò)收斂速度慢、不能得到全局最優(yōu)解的缺點，選擇具有全局優(yōu)化、支持并行且具有自適應(yīng)特性的蟻群算法，優(yōu)化神經(jīng)網(wǎng)絡(luò)初始權(quán)重和閾值。將算法運用于實體解析元組對的匹配加以驗證，結(jié)果表明：在相同最大迭代次數(shù)下，BP神經(jīng)網(wǎng)絡(luò)迭代490次可尋找到最優(yōu)解，其均方誤差為0.078，ACOBP神經(jīng)網(wǎng)絡(luò)同樣迭代487次可尋找到最優(yōu)解，均方誤差為0.013，相對來說均方誤差更小，訓(xùn)練效果更接近于目標(biāo)值，表明蟻群優(yōu)化的神經(jīng)網(wǎng)絡(luò)算法可以改善傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)收斂速度慢、學(xué)習(xí)效率低和易陷入局部最優(yōu)等缺點。

關(guān)鍵詞：數(shù)據(jù)倉庫；數(shù)據(jù)質(zhì)量；實體解析；BP神經(jīng)網(wǎng)絡(luò)；蟻群算法

DOIDOI：10.11907/rjdk.172415

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）003003704

英文摘要Abstract：In order to improve BP neutral network for its slow convergence rate and incapability for getting global optimal solution. Thus we can choose ant colony algorithm with global optimal solution， parallelism support and adaptive feature to optimize the initial weight and threshold of neutral network and utilize the algorithm in tuple matching of entity analysis.The verify result shows under the same maximum number of iterations， BP neural network has found the optimal result after iterating for 490 times with mean square error 0.078， while ACOBP neural network got the result 487 times with mean square error 0.013， relatively speaking， closer to the target value. Thus we can draw the conclusion that ant colony optimization neural network algorithm can improve the disadvantages of traditional BP neural network， i.e. slower convergence rate， lower learning efficiency and easier local optimum.

英文關(guān)鍵詞Key Words：data warehouse； data quality； entity analysis； BP neutral network； ant colony algorithm

0引言

人工神經(jīng)網(wǎng)絡(luò)是人工智能中一種極為重要的算法，通過調(diào)節(jié)組成各節(jié)點的互聯(lián)反饋關(guān)系實現(xiàn)復(fù)雜信息并行處理。這是一種依賴于系統(tǒng)復(fù)雜程度的網(wǎng)絡(luò)拓?fù)淅碚摲植际教幚砟Ｐ停渲杏纫訠P神經(jīng)網(wǎng)絡(luò)研究應(yīng)用最為廣泛。該模型在理論以及實際運用方面都比較成熟。但是，BP神經(jīng)網(wǎng)絡(luò)存在學(xué)習(xí)效率較低、收斂速度慢、容易陷入局部最優(yōu)解的缺陷。

為解決這一問題，嘗試使用一種能夠進(jìn)行啟發(fā)式的全局優(yōu)化進(jìn)化算法?？紤]到算法應(yīng)該具有全局優(yōu)化、并行以及自適應(yīng)特性，因此采用能尋找優(yōu)化路徑大概率型算法——蟻群算法，該算法具有正反饋特點[14]。

基于以上考慮，本文使用蟻群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，并提出一種蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)（ACOBP）算法。將算法運用于實體解析的元組對匹配進(jìn)行驗證。蟻群算法可以找到一組解空間中的最優(yōu)解，找到之后使用神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化。該算法不僅解決了BP容易陷入局部解的問題，同時算法收斂速度也得到了提升。

1蟻群改進(jìn)BP神經(jīng)網(wǎng)絡(luò)基本原理

1.1BP神經(jīng)網(wǎng)絡(luò)算法原理

BP是一種前饋多層網(wǎng)絡(luò)學(xué)習(xí)算法[5]，其結(jié)構(gòu)如圖1所示。

輸入、隱含以及輸出3個神經(jīng)元層是BP神經(jīng)網(wǎng)絡(luò)特有的標(biāo)志[6]。其中隱單元作為隱含層中的神經(jīng)元狀態(tài)，影響著輸入以及輸出層關(guān)系，不與外界聯(lián)系。但隱單元在一定程度上決定著整個多層神經(jīng)網(wǎng)絡(luò)的性能，通過改變其系數(shù)就可以決定多層神經(jīng)網(wǎng)絡(luò)的作用。

對于一個m層的神經(jīng)網(wǎng)絡(luò)，樣本X被添加到輸入層。多層神經(jīng)網(wǎng)絡(luò)表述如下：

Xki=f（Uki）（1）

Uki=∑WijXk-1j（2）

U＼+k＼-i：第k層的i神經(jīng)元的輸入總和；X＼+k＼-i：輸出；Wij：第k—1層的第j個神經(jīng)元到第k層的第i個神經(jīng)元的權(quán)系數(shù)；f：每個神經(jīng)元的加權(quán)函數(shù)。

BP神經(jīng)網(wǎng)絡(luò)有兩個重要特征[78]：

（1）正向信息傳播：輸入樣本通過隱含層逐層傳播到輸出層。每一層的傳播總是由上一層神經(jīng)元狀態(tài)影響下一層狀態(tài)，同時在每一層輸出過程中總是將數(shù)據(jù)與上層得到的數(shù)據(jù)進(jìn)行比較，如果和預(yù)期不符就進(jìn)入誤差傳播。

（2）逆向誤差傳播：按照正向傳播的反向路徑進(jìn)行回傳，并且在回傳過程中修改隱含層權(quán)重系數(shù)，用來矯正模型。

1.2蟻群算法基本原理

蟻群算法原理：在螞蟻搜索食物過程中會留下一種叫做信息素的東西，而且信息素的產(chǎn)生是隨著螞蟻尋找食物路徑的加長而減弱的，也就是說，信息素隨著離螞蟻巢穴越遠(yuǎn)越少。螞蟻尋找食物就是基于信息素濃度選擇的，但信息素具有一定揮發(fā)性[911]。大致可以歸納為以下方式描述螞蟻的尋找原則：①如果螞蟻沒有收到信息素信息，螞蟻隨機(jī)選擇找食路徑；②如果周圍有多個信息素信息，螞蟻根據(jù)信息素濃度選擇路徑；③螞蟻會在找食過程中使用不同信息進(jìn)行交換，例如從家出去留下信息A，找到食物后留下信息B；④隨著時間的推進(jìn)，老的信息素?fù)]發(fā)。

1.3蟻群算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合

BP神經(jīng)網(wǎng)絡(luò)有一個缺點：由于其閾值與權(quán)值是隨機(jī)生成的，這就使得初始值的選擇很大程度上決定了算法的收斂程度。如果初始值選擇不好，就會導(dǎo)致得不到全局最優(yōu)解。產(chǎn)生的原因是由于出現(xiàn)修改網(wǎng)絡(luò)權(quán)值或閾值的振蕩，使算法不收斂或者收斂緩慢，這使得網(wǎng)絡(luò)性能下降，學(xué)習(xí)速度慢。BP神經(jīng)網(wǎng)絡(luò)采用梯度下降算法找到解，也是其易陷入局部最優(yōu)解的原因。為了解決這一問題，就不得不找到一種具有全局最優(yōu)解的搜索優(yōu)化算法。使用魯棒性較好的蟻群算法對BP神經(jīng)網(wǎng)絡(luò)的閾值以及權(quán)值進(jìn)行訓(xùn)練，就可克服BP神經(jīng)網(wǎng)絡(luò)的缺點。

2蟻群與改進(jìn)BP神經(jīng)網(wǎng)絡(luò)算法設(shè)計

為了獲得理想的學(xué)習(xí)效果和更有效的收斂速度，神經(jīng)網(wǎng)絡(luò)的初始權(quán)重應(yīng)該盡可能地靠近全局最小值。然而，通常該值是隨機(jī)選擇的，且在神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)訓(xùn)練中會反向傳播誤差信息，不斷地動態(tài)調(diào)整，導(dǎo)致難以保持合理狀態(tài)。本文利用神經(jīng)網(wǎng)絡(luò)具有數(shù)據(jù)融合和易于與其它算法相結(jié)合的特點，利用蟻群算法的全局優(yōu)化功能，優(yōu)化神經(jīng)網(wǎng)絡(luò)的初始權(quán)重和閾值。

全局信息素更新機(jī)制是優(yōu)化過程中必不可少的機(jī)制[1213]，具體思想如下：

首先給出神經(jīng)網(wǎng)絡(luò)的權(quán)重和初始閾值。利用蟻群算法查找和構(gòu)建閾值的最優(yōu)值，從而使網(wǎng)絡(luò)權(quán)值由于誤差反向傳播而易陷入局部最優(yōu)的問題得以解決；然后以蟻群算法構(gòu)建的較優(yōu)解輸入神經(jīng)網(wǎng)絡(luò)作進(jìn)一步尋優(yōu)訓(xùn)練，尋找網(wǎng)絡(luò)權(quán)值閾值最優(yōu)解。上述方式不僅可以提高神經(jīng)網(wǎng)絡(luò)收斂的速度，提高學(xué)習(xí)效率，而且可以提高學(xué)習(xí)精度。引入網(wǎng)絡(luò)梯度信息也避免了蟻群算法在短時間內(nèi)難以找到閾值最優(yōu)解的問題。算法流程如下：

（1）訓(xùn)練樣本。使用期望輸出對蟻群參數(shù)進(jìn)行初始化。神經(jīng)網(wǎng)絡(luò)參數(shù)pi（1≤i≤n）為N個非0的隨機(jī)數(shù)值，并且構(gòu)建集合Ipi。集合Ipi中第j個元素Pj（Ipi）的信息量可以表示為τj（Ipi）。迭代次數(shù)為Nc，時間設(shè)定為t，約定初始時刻為0。最大迭代次數(shù)為Ncmax，集合中所有元素的信息素濃度相等，且τj（Ipi）=C，Δτj（Ipi）表示元素j包含的信息素濃度的增量，Δτj（Ipi）=0設(shè)為初始值，Δτj（Ipi）=0表示在運動過程中螞蟻k殘留在元素j上的信息素濃度。隨機(jī)放置所有螞蟻在神經(jīng)網(wǎng)絡(luò)參數(shù)上。

（2）啟動所有螞蟻。選擇螞蟻開始運動，并從集合Ipi中隨機(jī)選擇路徑。路徑選擇使用狀態(tài)轉(zhuǎn)移概率以及信息元素濃度作為參考，同時將選擇的元素集合作為神經(jīng)網(wǎng)絡(luò)權(quán)重。螞蟻k在集合Ipi中的狀態(tài)轉(zhuǎn)移概率計算如下：

Pj（τkj（IPi））=[τj（Ipi）]α×[ηj（Ipi）]β∑s∈allowedk[τs（Ipi）]α×[ηs（Ipi）]β，if j∈allowedk

0，else

（3）

設(shè)置ηj（Ipi）=1ek為啟發(fā)函數(shù)，ek表示網(wǎng)絡(luò)實際輸出與期望輸出的誤差，主要含義為當(dāng)?shù)趉只螞蟻所選擇的權(quán)值、閾值作為神經(jīng)網(wǎng)絡(luò)的權(quán)值、閾值時，產(chǎn)生的值間偏差記為ek=|out實際-out期望|。誤差ek與包含的信息濃度成正比。

（3）更新信息素。伴隨著螞蟻運動的結(jié)束，迭代次數(shù)也會完成，即t←t+m；Nc←Nc+1。將螞蟻運行集合中選擇的權(quán)值以及閾值放入神經(jīng)網(wǎng)絡(luò)，作為最優(yōu)解進(jìn)行實際輸出以及誤差計算，對路徑上信息素濃度進(jìn)行更新：

τj（Ipi）（t+m）=（1-ρ）τj（Ipi）（t）+Δτj（Ipi）（4）

Δτj（Ipi）=∑hk=1Δτkj（Ipi）（5）

Δτkj（Ipi）=Qek，k→Pj（Ipi）

0，else（6）

ρ表示信息素?fù)]發(fā)系數(shù)，Q表示信息素濃度。

（4）當(dāng)Nc=Ncmax時，說明所有螞蟻收斂到了相同路徑，也就是說迭代到了最大次數(shù)，終止計算，并保存求解結(jié)果。否則重復(fù)步驟（2）、步驟（3）。

（5）利用學(xué)習(xí)獲得的神經(jīng)網(wǎng)絡(luò)對測試數(shù)據(jù)進(jìn)行識別計算。

蟻群神經(jīng)網(wǎng)絡(luò)算法訓(xùn)練流程見圖2。

螞蟻的數(shù)目在蟻群神經(jīng)網(wǎng)絡(luò)中通過對N和N2的計算得到，也就是計算初始連接權(quán)值以及閾值總數(shù)。

3算法驗證

通常，數(shù)據(jù)倉庫中一個元組包含多個屬性，在計算元組對的相似性時，需要比較所有屬性的相似度值。因為不同屬性對所屬元組有不同程度的影響，屬性相似度和元組相似度是一個非線性映射關(guān)系[14]，因此，需要用一個非線性分類器識別元組對是否指代同一個實體。通過網(wǎng)絡(luò)學(xué)習(xí)屬性間的內(nèi)在關(guān)系調(diào)整閾值、權(quán)值等參數(shù)。利用神經(jīng)網(wǎng)絡(luò)能以任意情況以及任意精度逼近非線函數(shù)的特性，采用優(yōu)化后的算法判斷實體匹配是否完成。算法的提出在一定程度上彌補(bǔ)了傳統(tǒng)實體匹配方法中根據(jù)屬性相似度的加權(quán)求和缺點，改進(jìn)了用人工閾值的比較來判斷元組對是否屬于同一實體的不足。

本文運用神經(jīng)網(wǎng)絡(luò)對非線性函數(shù)的特征進(jìn)行準(zhǔn)確近似，通過網(wǎng)絡(luò)研究動態(tài)實現(xiàn)權(quán)重、閾值等參數(shù)屬性之間的內(nèi)在關(guān)系，調(diào)整實體，以判斷實體是否匹配。由于缺乏神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程，故采用蟻群算法進(jìn)行優(yōu)化。

比較傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)算法和蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)算法的權(quán)值訓(xùn)練誤差。設(shè)置訓(xùn)練誤差精度為0.01，學(xué)習(xí)率為0.2，最大迭代次數(shù)為500。利用某煙草集團(tuán)數(shù)據(jù)中心供應(yīng)商數(shù)據(jù)集，計算得到屬性相似度特征向量，以Matlab編程對兩種算法進(jìn)行實驗驗證對比，結(jié)果如圖3所示。

在相同的最大迭代次數(shù)下，BP神經(jīng)網(wǎng)絡(luò)在迭代490次尋找到最優(yōu)解，其均方誤差為0.078，ACOBP神經(jīng)網(wǎng)絡(luò)同樣在487次迭代尋找到最優(yōu)解，均方誤差為0.013，見表1。相對來說，均方誤差更小，訓(xùn)練效果更接近于目標(biāo)值。由于傳統(tǒng)的BP算法在優(yōu)化過程中陷入局部最優(yōu)解，使得收斂效果不及優(yōu)化后的算法。因此，ACOBP算法在訓(xùn)練效果和收斂速度上都有著更好的性能和效率，能夠達(dá)到較小的均方誤差值，極大程度上節(jié)約了訓(xùn)練時間。

本實驗采用準(zhǔn)確率、召回率兩個指標(biāo)體系對實驗結(jié)果進(jìn)行性能評價[1517]。

本文針對傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)和蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)進(jìn)行準(zhǔn)確率、召回率對比實驗，分6組數(shù)據(jù)集對兩種算法進(jìn)行比較，訓(xùn)練及測試相同屬性的相似度值，實驗結(jié)果如圖4所示。當(dāng)數(shù)據(jù)量較小時，兩種識別模型的性能指標(biāo)值差別不大，當(dāng)數(shù)據(jù)為1 000個元組時，BP和ACOBP算法的準(zhǔn)確度分別為0.94和0.95。隨著數(shù)據(jù)量的增加，兩種模型的準(zhǔn)確率和召回率都有所降低。當(dāng)數(shù)據(jù)為50 000個元組對象時，BP和ACOBP算法的準(zhǔn)確度分別為0.76和0.84，但ACOBP算法的識別準(zhǔn)確率高于傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)，下降速度慢于傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)，這主要是因為蟻群算法獲得了更優(yōu)的神經(jīng)網(wǎng)絡(luò)權(quán)值和閾值，實體解析的準(zhǔn)確性相應(yīng)得到了提高。

同樣，隨著數(shù)據(jù)規(guī)模的增加，兩種算法的運行時間也不斷增加，但蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)的運行時間相對更短，如圖5所示。對比結(jié)果表明，蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)提高了實體解析的效率，較好地滿足了海量數(shù)據(jù)的實體解析性能要求。

經(jīng)過實驗仿真，優(yōu)化后的算法在訓(xùn)練效果及測試集上有著更好的性能，表明蟻群優(yōu)化算法可以改善傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)收斂速度慢、學(xué)習(xí)效率低和易陷入局部最優(yōu)等缺點。

4結(jié)語

本文針對神經(jīng)網(wǎng)絡(luò)算法訓(xùn)練時間較長、收斂速度較慢以及易于陷入局部最優(yōu)解的問題，使用蟻群算法進(jìn)行彌補(bǔ)，結(jié)合蟻群算法的全局最優(yōu)解搜索及具有較強(qiáng)魯棒性優(yōu)點，建立蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)模型。詳細(xì)闡述了基于蟻群算法，采用全局信息素的更新機(jī)制優(yōu)化BP網(wǎng)絡(luò)的連接權(quán)值和閾值方法。實驗仿真表明，優(yōu)化后的算法在訓(xùn)練效果及測試集上有著更好的性能，表明蟻群優(yōu)化算法可以改善傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)收斂速度慢、學(xué)習(xí)效率低和易陷入局部最優(yōu)等不足。

參考文獻(xiàn)參考文獻(xiàn)：

[1]RANDALL M，LEWIS A.A parallel implementation of ant colony optimization[J].Journal of Parallel and Distributed Computing，2002，62（9）：14211432.

[2]BEMD B，GABRIEL E K，CHRISTINE S.Parallelization Strategies for the Ant System[M].Vienna，Austria：University of Vienna，1997.

[3]MANFRIN M，BIRATTARI M，STUTZLE T，et a1.Parallel ant colony optimization for the Traveling Salesman Problem[R].Universite Libre de BmxeUes，Belgium，Technical Report：TR/IRIDIAJ 2006007，2006.

[4]DORIGO M，MANIEZZO V，COLORNI A.The ant system：optimization by a colony of cooperating agents[J].IEEE Transcations on Systems，Man and Cybernetics，1996，26（1）：2941.

[5]徐紅艷，黨曉婉，馮勇，等.基于BP神經(jīng)網(wǎng)絡(luò)的Deep Web實體識別方法[J].計算機(jī)應(yīng)用，2013，33（3）：776779.

[6]沈花玉，王兆霞，高成耀，等.BP神經(jīng)網(wǎng)絡(luò)隱含層單元數(shù)的確定[J].天津理工大學(xué)學(xué)報，2008，24（5）：1315.

[7]馬銳.人工神經(jīng)網(wǎng)絡(luò)原理[M].北京：機(jī)械工業(yè)出版社，2010.

[8]強(qiáng)保華，陳凌，余建橋，等.基于BP神經(jīng)網(wǎng)絡(luò)的屬性匹配方法研究[J].計算機(jī)科學(xué)，2006，33（1）：249251.

[9]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

[10]王磊，曹菡，王長纓.蟻群算法的三種并行模型分析[J].計算機(jī)工程，2011，37（12）：170172.

[11]柏建普，吳強(qiáng).蟻群混合遺傳算法的研究及應(yīng)用[J].電子科技，2011，24（4）：2023.

[12]黃美玲.蟻群優(yōu)化算法的研究及其應(yīng)用[D].南昌：南昌大學(xué)，2007：1213.

[13]白磊.蟻群算法的改進(jìn)及其應(yīng)用研究[D].合肥：安徽大學(xué)，2015：2224.

[14]韓柯，李德毅.元組統(tǒng)計相似性知識的提取與應(yīng)用[J].計算機(jī)研究與發(fā)展，1997（1）：312316.

[15]JIN L， LI C， MEHROTRA S. Efficient record linkage in large data sets[C]. Eighth International Conference on Database Systems for Advanced Applications. IEEE， 2003：137146.

[16]KIRSTEN T， KOLB L， HARTUNG M， et al. Data partitioning for parallel entity matching[J]. Computer Science， 2010（1）：12541266.

[17]T F SMITH， M S WATERMAN. Identification of common molecular subsequences[J]. Journal of molecular biology， 1981，147（1）：195197.

責(zé)任編輯（責(zé)任編輯：杜能鋼）