應用量子粒子群算法優化神經網絡的數據庫重復記錄檢測

徐亮

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

0 引言

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

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

為了提高數據庫重復記錄檢測效果，針對當前BP神經網絡的參數優化問題，提出了量子粒子群算法優化神經網絡的數據庫重復記錄檢測方法(QPSO-BPNN)，采用量子粒子群算法對神經網絡的連接權值和閾值的初值進行優化，建立全局最優的數據庫重復記錄檢測模型，并提高數據庫重復記錄檢測效率。

1 QPSO-BPNN的數據庫重復記錄檢測方法

1.1 提取數據庫重復記錄檢測特征向量機

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

(1)

式中，d表示字段匹配字符數，t表示字段不匹配字符數。

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

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

(2)

1.2 BP神經網絡

BP神經網絡輸入層第k個樣本的輸入以及其期望輸出可以表示為式(3)、式(4)。

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

(3)

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

(4)

根據輸入層的輸入，基于隱含層的神經元節點連接權值wih和映射函數f(·)，可以得到隱含層神經元節點輸入和輸出計算式分別為式(5)和式(6),

(5)

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

(6)

式中，p表示隱含層的神經元節點數，bh表示隱含層的神經元節點閾值。

根據隱含層的神經元節點輸出，以及輸出層的神經元節點的連接權值who和映射函數g(·)，輸出層的神經元節點的輸入和輸出計算式具體為式(7)和式(8),

(7)

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

(8)

式中，m表示輸出層的神經元節點數，bo表示隱含層的神經元節點閾值。

計算輸出層的神經元節點的輸出和期望輸出之間的誤差具體為式(9),

(9)

式中，q表示訓練數量。

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

(10)

(11)

根據Δwho(k)和Δwih(k)對連接權值who和wih進行更新操作，即式(12)和式(13)。

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

(12)

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

(13)

不斷重復上述過程，當輸出層誤差小于預設值，那么BP神經網絡學習過程終止。

由于bh、wih和bo、who的初值直接影響BP神經網絡學習性能，為此本文采用量子粒子群算法優化bh、wih和bo、who的初值。

1.3 量子粒子群算法

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

(14)

式中，d表示粒子的維數。

第i個粒子的當前位置為式(15),

(15)

式中，rid表示量子系統的第i個基態，uid表示一個隨機數，Kid的計算式為式(16),

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

(16)

式中，β表示收縮-擴張系數。

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

(17)

1.4 QPSO-BPNN的數據庫重復記錄檢測步驟

Step1：收集數據庫記錄，并提取數據庫重復記錄檢測特征向量，并對數據庫重復記錄進行相應的標記。

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

Step3：初始化量子粒子群，每一個粒子位置向量與一組連接權值和閾值的初始值相對應。

Step4：BP神經網絡根據連接權值和閾值的初始值對數據庫重復記錄檢測訓練樣本集合進行訓練，并計算每一個粒子的適應度函數值，本文選擇數據庫重復記錄檢測準確度作為適應度函數。

Step5：確定每一個粒子的當前最優位置和量子粒子群的最優位置。

Step6：對粒子位置進行更新。

Step7：量子粒子群的迭代次數增加，如果迭代次數達到最大迭代次數或者BP神經網絡輸出誤差小于預設值，那么此時得到了BP神經網絡最優的連接權值和閾值的初始值。

Step8：BP神經網絡采用最優的連接權值和閾值初始值對數據庫重復記錄檢測的訓練樣本進行重新學習，建立最優的對數據庫重復記錄檢測模型。

Step9：采用訓練樣本集合對數據庫重復記錄檢測模型的性能進行驗證測試，并輸出數據庫重復記錄檢測結果。

2 仿真實驗

2.1 實驗平臺

為了測試量子粒子群算法優化神經網絡的數據庫重復記錄檢測方法(QPSO-BPNN)的有效性和優越性，選擇當前經典數據庫重復記錄檢測方法進行對比實驗，具體為遺傳算法優化神經網絡的數據庫重復記錄檢測方法(GA-BPNN)、經驗法確定神經網絡參數的數據庫重復記錄檢測方法(BPNN)，選擇數據庫重復記錄檢測準確率、召回率以及平均檢測時間對結果進行衡量，其中準確率、召回率定義分別為式(18)和式(19),

(18)

(19)

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

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

表1 數據庫重復記錄檢測的仿真測試平臺

2.2 數據庫重復記錄檢測的樣本數據

選擇不同規模的數據庫重復記錄檢測的樣本數據作為實驗對象，具體如表2所示。

表2 數據庫重復記錄檢測的實驗數據

2.3 數據庫重復記錄檢測結果分析

統計3種方法的數據庫重復記錄檢測準確率和召回率，結果如圖1和圖2所示。從圖1和圖2的數據庫重復記錄檢測準確率和召回率進行對比和分析可以發現，QPSO-BPNN的數據庫重復記錄檢測準確率和召回率平均值分別為91.06%和94.23%，GA-BPNN的數據庫重復記錄檢測準確率和召回率均值分別為88.14%和89.73%，BPNN的數據庫重復記錄檢測準確率和召回率均值分別為86.15%和84.47%。相對于對比方法，QPSO-BPNN的數據庫重復記錄檢測效果得到了明顯的提升，減少了數據庫重復記錄檢測錯誤率，數據庫重復記錄拒檢測率也得到了下降，獲得了更加理想的數據庫重復記錄檢測結果。

圖1 不同方法的數據庫重復記錄檢測準確率

圖2 不同方法的數據庫重復記錄檢測召回率

2.4 數據庫重復記錄檢測效率分析

統計不同方法的數據庫重復記錄檢測時間，具體結果如表3所示。對表3的數據庫重復記錄檢測時間進行分析可以發現，QPSO-BPNN的數據庫重復記錄檢測時間最少，GA-BPNN的數據庫重復記錄檢測時間次之，BPNN的數據庫重復記錄檢測時間最長。這表明連接權值和閾值的初值能夠對BP神經網絡的學習過程產生直接影響，BPNN采用經驗方法確定連接權值和閾值的初值，使得BP神經網絡的學習過程迭代次數增多，而QPSO算法對權值和閾值的初值進行優化后，可以減少BP神經網絡的學習過程迭代次數，提升了數據庫重復記錄檢測效率，能夠滿足數據庫重復記錄向大規模方向發展的要求。

表3 不同方法的數據庫重復記錄檢測時間

3 總結

重復記錄直接影響數據庫檢索效率，同時浪費了存儲空間，為了節約數據庫的存儲空間，加快數據庫檢索速度，滿足數據庫向大規模發展方向的要求，針對當前BP神經網絡在數據庫重復記錄檢測過程中存在的問題，提高了量子粒子群算法優化神經網絡的數據庫重復記錄檢測方法，仿真測試結果表明，本文設計方法可以改善數據庫重復記錄檢測效果，克服了當前數據庫重復記錄檢測方法存在的局限性，提升了數據庫重復記錄檢測效率，為大規模數據庫重復記錄檢測提供了一種新的研究方向。