徐亮

(解放軍廬山康復(fù)療養(yǎng)中心，信息科，江西，九江 332000)

0 引言

隨著信息處理技術(shù)的不斷發(fā)展，每天會(huì)產(chǎn)生大量的數(shù)據(jù)，為了對(duì)數(shù)據(jù)進(jìn)行有效管理，各單位都建立了相應(yīng)的數(shù)據(jù)庫管理系統(tǒng)。隨著數(shù)據(jù)管理系統(tǒng)使用時(shí)間不斷的增加，數(shù)據(jù)庫中存在大量的重復(fù)記錄，這些重復(fù)記錄不僅影響數(shù)據(jù)庫運(yùn)行效率，同時(shí)會(huì)占用太多的存儲(chǔ)空間，使得數(shù)據(jù)庫運(yùn)行成本提高[1-3]。對(duì)數(shù)據(jù)庫重復(fù)記錄進(jìn)行檢測，適當(dāng)刪除一部分重復(fù)記錄，不僅可以節(jié)約一定的存儲(chǔ)空間，提高存儲(chǔ)空間利用率，而且可以改善數(shù)據(jù)庫數(shù)據(jù)檢索速度，因此數(shù)據(jù)庫重復(fù)記錄檢測研究具有一定的理論意義，同時(shí)具有一定的實(shí)際應(yīng)用價(jià)值[4-6]。

近十多年來，一些學(xué)者對(duì)數(shù)據(jù)庫重復(fù)記錄檢測問題進(jìn)行了深入研究，提出了許多行之有效的數(shù)據(jù)庫重復(fù)記錄檢測方法[7]。當(dāng)前最常用的數(shù)據(jù)庫重復(fù)記錄檢測方法為決策樹算法和人工神經(jīng)網(wǎng)絡(luò)算法。決策樹算法主要針對(duì)小規(guī)模數(shù)據(jù)庫重復(fù)記錄檢測問題，無法適應(yīng)數(shù)據(jù)庫發(fā)展要求[8-9]。人工神經(jīng)網(wǎng)絡(luò)算法逼近問題解的精度高，不僅可以擬合數(shù)據(jù)庫重復(fù)記錄之間的關(guān)系，而且數(shù)據(jù)庫重復(fù)記錄檢測速度要快于決策樹算法，成為當(dāng)前數(shù)據(jù)庫重復(fù)記錄檢測的主要工具，其中BP神經(jīng)網(wǎng)絡(luò)的應(yīng)用范圍更加廣泛[10-12]。在BP神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫重復(fù)記錄檢測過程中，連接權(quán)值和閾值的初值對(duì)數(shù)據(jù)庫重復(fù)記錄檢測效果具有重要影響，最初人們采用經(jīng)驗(yàn)方法確定連接權(quán)值和閾值的初值，使得BP神經(jīng)網(wǎng)絡(luò)的迭代次數(shù)多，數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間長，對(duì)于大規(guī)模連數(shù)據(jù)庫，無法在有效時(shí)間內(nèi)得到數(shù)據(jù)庫重復(fù)記錄檢結(jié)果，隨后有學(xué)者引入遺傳算法優(yōu)化連接權(quán)值和閾值的初值，但是遺傳算法自身存在收斂速度慢的缺限，到了進(jìn)化后期，停滯不前，無法獲得全局最優(yōu)的連接權(quán)值和閾值的初值，影響了BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)性能，使得數(shù)據(jù)庫重復(fù)記錄檢測不理想。

為了提高數(shù)據(jù)庫重復(fù)記錄檢測效果，針對(duì)當(dāng)前BP神經(jīng)網(wǎng)絡(luò)的參數(shù)優(yōu)化問題，提出了量子粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫重復(fù)記錄檢測方法(QPSO-BPNN)，采用量子粒子群算法對(duì)神經(jīng)網(wǎng)絡(luò)的連接權(quán)值和閾值的初值進(jìn)行優(yōu)化，建立全局最優(yōu)的數(shù)據(jù)庫重復(fù)記錄檢測模型，并提高數(shù)據(jù)庫重復(fù)記錄檢測效率。

1 QPSO-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測方法

1.1 提取數(shù)據(jù)庫重復(fù)記錄檢測特征向量機(jī)

在數(shù)據(jù)庫存在大量的記錄，每一個(gè)記錄包括多個(gè)字段，當(dāng)字段之間數(shù)據(jù)的相似度超過一定的值，那么認(rèn)為這些記錄是重復(fù)記錄，不然就認(rèn)為不是重復(fù)記錄，因此首先提取數(shù)據(jù)庫重復(fù)記錄檢測特征向量，本文采用數(shù)據(jù)庫記錄字段相似度量作為特征向量，設(shè)數(shù)據(jù)庫記錄2個(gè)字段分別為y1和y2，采用Jaro算法[13]計(jì)算2個(gè)字段的相似度值，具體為式(1),

(1)

式中，d表示字段匹配字符數(shù)，t表示字段不匹配字符數(shù)。

設(shè)2條記錄共有Z個(gè)字段，fi表示2條記錄的第i個(gè)字段相似度值，所有字段的相似度值組成特征量式(2),

F=(f1,f2,…,fi,…,fz}

(2)

1.2 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)輸入層第k個(gè)樣本的輸入以及其期望輸出可以表示為式(3)、式(4)。

x(k)=(x(k)1,x2(k),…,xn(k))

(3)

do(k)=(d1(k),d2(k),…,dm(k))

(4)

根據(jù)輸入層的輸入，基于隱含層的神經(jīng)元節(jié)點(diǎn)連接權(quán)值wih和映射函數(shù)f(·)，可以得到隱含層神經(jīng)元節(jié)點(diǎn)輸入和輸出計(jì)算式分別為式(5)和式(6),

(5)

hoh(k)=f(hik(k)),h=1,2,…,p

(6)

式中，p表示隱含層的神經(jīng)元節(jié)點(diǎn)數(shù)，bh表示隱含層的神經(jīng)元節(jié)點(diǎn)閾值。

根據(jù)隱含層的神經(jīng)元節(jié)點(diǎn)輸出，以及輸出層的神經(jīng)元節(jié)點(diǎn)的連接權(quán)值who和映射函數(shù)g(·)，輸出層的神經(jīng)元節(jié)點(diǎn)的輸入和輸出計(jì)算式具體為式(7)和式(8),

(7)

yoo(k)=g(yio(k)),o=1,2,…,m

(8)

式中，m表示輸出層的神經(jīng)元節(jié)點(diǎn)數(shù)，bo表示隱含層的神經(jīng)元節(jié)點(diǎn)閾值。

計(jì)算輸出層的神經(jīng)元節(jié)點(diǎn)的輸出和期望輸出之間的誤差具體為式(9),

(9)

式中，q表示訓(xùn)練數(shù)量。

計(jì)算輸出層和隱含層的偏導(dǎo)數(shù)，它們分別為δo(k)和δh(k)，根據(jù)δo(k)和δh(k)計(jì)算wih和who的增量，計(jì)算式為式(10)和式(11),

(10)

(11)

根據(jù)Δwho(k)和Δwih(k)對(duì)連接權(quán)值who和wih進(jìn)行更新操作，即式(12)和式(13)。

wih(k)=wih(k)+Δwih(k)

(12)

who(k)=who(k)+Δwho(k)

(13)

不斷重復(fù)上述過程，當(dāng)輸出層誤差小于預(yù)設(shè)值，那么BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)過程終止。

由于bh、wih和bo、who的初值直接影響B(tài)P神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)性能，為此本文采用量子粒子群算法優(yōu)化bh、wih和bo、who的初值。

1.3 量子粒子群算法

量子粒子群算法是一種基于量子力學(xué)理論的人工智能算法，具有較快的收斂能力，可以大概率找到全局最優(yōu)解，粒子最優(yōu)位置為mbest，具體為式(14),

(14)

式中，d表示粒子的維數(shù)。

第i個(gè)粒子的當(dāng)前位置為式(15),

(15)

式中，rid表示量子系統(tǒng)的第i個(gè)基態(tài)，uid表示一個(gè)隨機(jī)數(shù)，Kid的計(jì)算式為式(16),

Kid(t}=2β(t}|mbestid(t}-xid(t}|

(16)

式中，β表示收縮-擴(kuò)張系數(shù)。

粒子位置更新方式用式(17),

(17)

1.4 QPSO-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測步驟

Step1：收集數(shù)據(jù)庫記錄，并提取數(shù)據(jù)庫重復(fù)記錄檢測特征向量，并對(duì)數(shù)據(jù)庫重復(fù)記錄進(jìn)行相應(yīng)的標(biāo)記。

Step2：建立數(shù)據(jù)庫重復(fù)記錄檢測樣本集合，其中選擇50%樣本組成數(shù)據(jù)庫重復(fù)記錄檢測訓(xùn)練樣本集合，其他50%樣本組成數(shù)據(jù)庫重復(fù)記錄檢測的測試樣本集合。

Step3：初始化量子粒子群，每一個(gè)粒子位置向量與一組連接權(quán)值和閾值的初始值相對(duì)應(yīng)。

Step4：BP神經(jīng)網(wǎng)絡(luò)根據(jù)連接權(quán)值和閾值的初始值對(duì)數(shù)據(jù)庫重復(fù)記錄檢測訓(xùn)練樣本集合進(jìn)行訓(xùn)練，并計(jì)算每一個(gè)粒子的適應(yīng)度函數(shù)值，本文選擇數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確度作為適應(yīng)度函數(shù)。

Step5：確定每一個(gè)粒子的當(dāng)前最優(yōu)位置和量子粒子群的最優(yōu)位置。

Step6：對(duì)粒子位置進(jìn)行更新。

Step7：量子粒子群的迭代次數(shù)增加，如果迭代次數(shù)達(dá)到最大迭代次數(shù)或者BP神經(jīng)網(wǎng)絡(luò)輸出誤差小于預(yù)設(shè)值，那么此時(shí)得到了BP神經(jīng)網(wǎng)絡(luò)最優(yōu)的連接權(quán)值和閾值的初始值。

Step8：BP神經(jīng)網(wǎng)絡(luò)采用最優(yōu)的連接權(quán)值和閾值初始值對(duì)數(shù)據(jù)庫重復(fù)記錄檢測的訓(xùn)練樣本進(jìn)行重新學(xué)習(xí)，建立最優(yōu)的對(duì)數(shù)據(jù)庫重復(fù)記錄檢測模型。

Step9：采用訓(xùn)練樣本集合對(duì)數(shù)據(jù)庫重復(fù)記錄檢測模型的性能進(jìn)行驗(yàn)證測試，并輸出數(shù)據(jù)庫重復(fù)記錄檢測結(jié)果。

2 仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)平臺(tái)

為了測試量子粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫重復(fù)記錄檢測方法(QPSO-BPNN)的有效性和優(yōu)越性，選擇當(dāng)前經(jīng)典數(shù)據(jù)庫重復(fù)記錄檢測方法進(jìn)行對(duì)比實(shí)驗(yàn)，具體為遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫重復(fù)記錄檢測方法(GA-BPNN)、經(jīng)驗(yàn)法確定神經(jīng)網(wǎng)絡(luò)參數(shù)的數(shù)據(jù)庫重復(fù)記錄檢測方法(BPNN)，選擇數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率、召回率以及平均檢測時(shí)間對(duì)結(jié)果進(jìn)行衡量，其中準(zhǔn)確率、召回率定義分別為式(18)和式(19),

(18)

(19)

式中，A表示檢測重復(fù)記錄正確的數(shù)量，B表示檢測到的重復(fù)記錄數(shù)；Total表示重復(fù)記錄總數(shù)。

3種方法仿真測試平臺(tái)是一致的，具體如表1所示。

表1 數(shù)據(jù)庫重復(fù)記錄檢測的仿真測試平臺(tái)

2.2 數(shù)據(jù)庫重復(fù)記錄檢測的樣本數(shù)據(jù)

選擇不同規(guī)模的數(shù)據(jù)庫重復(fù)記錄檢測的樣本數(shù)據(jù)作為實(shí)驗(yàn)對(duì)象，具體如表2所示。

表2 數(shù)據(jù)庫重復(fù)記錄檢測的實(shí)驗(yàn)數(shù)據(jù)

2.3 數(shù)據(jù)庫重復(fù)記錄檢測結(jié)果分析

統(tǒng)計(jì)3種方法的數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率和召回率，結(jié)果如圖1和圖2所示。從圖1和圖2的數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率和召回率進(jìn)行對(duì)比和分析可以發(fā)現(xiàn)，QPSO-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率和召回率平均值分別為91.06%和94.23%，GA-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率和召回率均值分別為88.14%和89.73%，BPNN的數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率和召回率均值分別為86.15%和84.47%。相對(duì)于對(duì)比方法，QPSO-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測效果得到了明顯的提升，減少了數(shù)據(jù)庫重復(fù)記錄檢測錯(cuò)誤率，數(shù)據(jù)庫重復(fù)記錄拒檢測率也得到了下降，獲得了更加理想的數(shù)據(jù)庫重復(fù)記錄檢測結(jié)果。

圖1 不同方法的數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率

圖2 不同方法的數(shù)據(jù)庫重復(fù)記錄檢測召回率

2.4 數(shù)據(jù)庫重復(fù)記錄檢測效率分析

統(tǒng)計(jì)不同方法的數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間，具體結(jié)果如表3所示。對(duì)表3的數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間進(jìn)行分析可以發(fā)現(xiàn)，QPSO-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間最少，GA-BPNN的數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間次之，BPNN的數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間最長。這表明連接權(quán)值和閾值的初值能夠?qū)P神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程產(chǎn)生直接影響，BPNN采用經(jīng)驗(yàn)方法確定連接權(quán)值和閾值的初值，使得BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程迭代次數(shù)增多，而QPSO算法對(duì)權(quán)值和閾值的初值進(jìn)行優(yōu)化后，可以減少BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程迭代次數(shù)，提升了數(shù)據(jù)庫重復(fù)記錄檢測效率，能夠滿足數(shù)據(jù)庫重復(fù)記錄向大規(guī)模方向發(fā)展的要求。

表3 不同方法的數(shù)據(jù)庫重復(fù)記錄檢測時(shí)間

3 總結(jié)

重復(fù)記錄直接影響數(shù)據(jù)庫檢索效率，同時(shí)浪費(fèi)了存儲(chǔ)空間，為了節(jié)約數(shù)據(jù)庫的存儲(chǔ)空間，加快數(shù)據(jù)庫檢索速度，滿足數(shù)據(jù)庫向大規(guī)模發(fā)展方向的要求，針對(duì)當(dāng)前BP神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)庫重復(fù)記錄檢測過程中存在的問題，提高了量子粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫重復(fù)記錄檢測方法，仿真測試結(jié)果表明，本文設(shè)計(jì)方法可以改善數(shù)據(jù)庫重復(fù)記錄檢測效果，克服了當(dāng)前數(shù)據(jù)庫重復(fù)記錄檢測方法存在的局限性，提升了數(shù)據(jù)庫重復(fù)記錄檢測效率，為大規(guī)模數(shù)據(jù)庫重復(fù)記錄檢測提供了一種新的研究方向。