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

劉葉　吳晟　吳興蛟

摘要：

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

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

DOIDOI：10.11907/rjdk.172415

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

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：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é)點(diǎn)的互聯(lián)反饋關(guān)系實(shí)現(xiàn)復(fù)雜信息并行處理。這是一種依賴于系統(tǒng)復(fù)雜程度的網(wǎng)絡(luò)拓?fù)淅碚摲植际教幚砟Ｐ?，其中尤以BP神經(jīng)網(wǎng)絡(luò)研究應(yīng)用最為廣泛。該模型在理論以及實(shí)際運(yùn)用方面都比較成熟。但是，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)化路徑大概率型算法——蟻群算法，該算法具有正反饋特點(diǎn)[14]。

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

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

對(duì)于一個(gè)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個(gè)神經(jīng)元到第k層的第i個(gè)神經(jīng)元的權(quán)系數(shù)；f：每個(gè)神經(jīng)元的加權(quán)函數(shù)。

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

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

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

1.2蟻群算法基本原理

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

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

BP神經(jīng)網(wǎng)絡(luò)有一個(gè)缺點(diǎn)：由于其閾值與權(quán)值是隨機(jī)生成的，這就使得初始值的選擇很大程度上決定了算法的收斂程度。如果初始值選擇不好，就會(huì)導(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)化算法。使用魯棒性較好的蟻群算法對(duì)BP神經(jīng)網(wǎng)絡(luò)的閾值以及權(quán)值進(jìn)行訓(xùn)練，就可克服BP神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)。

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

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

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

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

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ò)實(shí)際輸出與期望輸出的誤差，主要含義為當(dāng)?shù)趉只螞蟻所選擇的權(quán)值、閾值作為神經(jīng)網(wǎng)絡(luò)的權(quán)值、閾值時(shí)，產(chǎn)生的值間偏差記為ek=|out實(shí)際-out期望|。誤差ek與包含的信息濃度成正比。

（3）更新信息素。伴隨著螞蟻運(yùn)動(dòng)的結(jié)束，迭代次數(shù)也會(huì)完成，即t←t+m；Nc←Nc+1。將螞蟻運(yùn)行集合中選擇的權(quán)值以及閾值放入神經(jīng)網(wǎng)絡(luò)，作為最優(yōu)解進(jìn)行實(shí)際輸出以及誤差計(jì)算，對(duì)路徑上信息素濃度進(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í)，說明所有螞蟻收斂到了相同路徑，也就是說迭代到了最大次數(shù)，終止計(jì)算，并保存求解結(jié)果。否則重復(fù)步驟（2）、步驟（3）。

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

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

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

3算法驗(yàn)證

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

本文運(yùn)用神經(jīng)網(wǎng)絡(luò)對(duì)非線性函數(shù)的特征進(jìn)行準(zhǔn)確近似，通過網(wǎng)絡(luò)研究動(dòng)態(tài)實(shí)現(xiàn)權(quán)重、閾值等參數(shù)屬性之間的內(nèi)在關(guān)系，調(diào)整實(shí)體，以判斷實(shí)體是否匹配。由于缺乏神經(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ù)集，計(jì)算得到屬性相似度特征向量，以Matlab編程對(duì)兩種算法進(jìn)行實(shí)驗(yàn)驗(yàn)證對(duì)比，結(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。相對(duì)來說，均方誤差更小，訓(xùn)練效果更接近于目標(biāo)值。由于傳統(tǒng)的BP算法在優(yōu)化過程中陷入局部最優(yōu)解，使得收斂效果不及優(yōu)化后的算法。因此，ACOBP算法在訓(xùn)練效果和收斂速度上都有著更好的性能和效率，能夠達(dá)到較小的均方誤差值，極大程度上節(jié)約了訓(xùn)練時(shí)間。

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

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

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

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

4結(jié)語

本文針對(duì)神經(jīng)網(wǎng)絡(luò)算法訓(xùn)練時(shí)間較長、收斂速度較慢以及易于陷入局部最優(yōu)解的問題，使用蟻群算法進(jìn)行彌補(bǔ)，結(jié)合蟻群算法的全局最優(yōu)解搜索及具有較強(qiáng)魯棒性優(yōu)點(diǎn)，建立蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)模型。詳細(xì)闡述了基于蟻群算法，采用全局信息素的更新機(jī)制優(yōu)化BP網(wǎng)絡(luò)的連接權(quán)值和閾值方法。實(shí)驗(yàn)仿真表明，優(yōu)化后的算法在訓(xùn)練效果及測(cè)試集上有著更好的性能，表明蟻群優(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實(shí)體識(shí)別方法[J].計(jì)算機(jī)應(yīng)用，2013，33（3）：776779.

[6]沈花玉，王兆霞，高成耀，等.BP神經(jīng)網(wǎng)絡(luò)隱含層單元數(shù)的確定[J].天津理工大學(xué)學(xué)報(bào)，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ì)算機(jī)科學(xué)，2006，33（1）：249251.

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

[10]王磊，曹菡，王長纓.蟻群算法的三種并行模型分析[J].計(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)計(jì)相似性知識(shí)的提取與應(yīng)用[J].計(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é)任編輯：杜能鋼）