大型數據庫重復記錄檢測與優化研究

唐吉深 覃少華

摘? 要： 研究大型數據庫重復記錄檢測與優化，利用Jaro算法以及TF?IDF算法計算大型數據庫不同記錄字段相似度量函數，所獲取字段相似度量函數作為記錄特征向量，經過人工標記后設置為BP神經網絡期望輸出。構建BP神經網絡學習樣本，設置變參數量子粒子群初始連接權值與閾值作為粒子，利用BP神經網絡依據學習訓練樣本獲取量子粒子群適應度函數值，確定粒子此刻最優位置以及全局最優位置。將全局最優位置粒子設置為BP神經網絡初始連接閾值以及權值，重復更新粒子位置，利用所獲取訓練集學習結果建立大型數據庫重復記錄檢測模型，檢測模型輸出結果大于檢測門限值時，該記錄為大型數據庫內重復記錄，否則為非重復記錄。實驗結果表明，采用該方法檢測包含100 000條記錄的大型數據庫，檢測召回率以及準確率均高于98.5%。

關鍵詞： 大型數據庫; 重復記錄檢測; 重復記錄優化; 學習樣本構建; 最優位置確定; 權值設置

中圖分類號： TN911.1?34; TP311? ? ? ? ? ? ? ? ? ?文獻標識碼： A? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）17?0077?05

Abstract： The detection and optimization of duplicated records in large databases are studied. The Jaro algorithm and TF?IDF algorithm are used to calculate the similarity measure functions of different record fields in large databases. The obtained field similarity measure functions are taken as the feature vectors of the records， which is set as the expected output of the BP neural network after being manually marked， so as to construct a learning sample of BP neural network. The initial connection weight and threshold value of variable parameter quantum particle swarm are set as the particles. The BP neural network is used to obtain the fitness function value of quantum particle swarm according to the learning and training samples， so as to determine the optimal position at the moment and global optimal position for the partials. The particle at the global optimal position is set as the initial connection threshold value and weight of BP neural network. The particle positions are repeatedly updated. The acquired learning results of the training sets are used to establish a detection model of large database duplicated records. When the output result of the detection model is greater than the detection threshold value， the record is a duplicated record in the large database， otherwise it is a non?duplicated record. The experimental results show that the recall rate and accuracy rate of the detection with the proposed method are higher than 98.5% in the detection of large databases with 100 000 records.

Keywords： large database; duplicated record detection; duplicated record optimization; learning sample construction; optimal position determination; weight setup

0? 引? 言

隨著信息技術不斷發展，數據庫集成已成為廣泛應用于不同領域的重要技術，網絡中大量數據庫數據實際應用中形成大量的重復以及相似記錄[1]，重復記錄占用大量數據庫空間，直接影響數據庫的使用效率，數據庫中重復數據檢測是整理數據庫大量數據的重要步驟。檢測大型數據庫中重復數據已成為數據庫領域急需解決的問題。

提取大型數據庫中重復數據的字段相似度是檢測大型數據庫重復記錄的重要步驟[2]。目前針對數據庫重復記錄檢測算法主要有字符串度量、距離函數模型以及排序合并等方法，以上方法雖然可以解決大型數據庫重復數據檢測問題，但需要耗費大量時間，算法運行復雜度較高[3]。

數據庫中不同記錄中各字段相似度是復雜的非線性關系，采用傳統算法無法獲取最優結果，處理效率較低。隨著科技不斷進步，采用神經網絡算法以及支持向量機等算法應用于數據庫重復記錄檢測中，提升了重復記錄檢測精度以及檢測效率[4?6]。

以上算法雖可以有效檢測數據庫中的重復記錄，但對于大型數據庫大量樣本數據，需要較長訓練時間，算法運行時間以及計算難度大。

神經網絡算法具有學習速度快的優勢，但極易出現過擬合現象，導致無法獲取最優解，而粒子群算法具有全局尋優能力[7]。研究大型數據庫重復記錄檢測與優化，利用量子粒子群算法對神經網絡算法進行優化，使其適用于大型數據庫海量重復記錄檢測中，提升重復記錄檢測精度以及檢測效率。

1? 大型數據庫重復記錄檢測與優化方法設計

1.1? 大型數據庫重復記錄檢測原理

大型數據庫重復記錄檢測時需要先采集數據庫內記錄，利用提取數據庫記錄字段的相似性特征函數建立訓練樣本集，利用訓練樣本集建立大型數據庫重復記錄檢測模型。

通過計算數據庫記錄相似度值設置檢測閾值[8]，將所計算相似度結果與所設置閾值對比，通過對比結果檢測該記錄是否屬于重復記錄。[T]與[B]分別表示大型數據庫內記錄集合以及不同記錄屬性向量，記錄字段相似特征函數提取公式如下：

通過式（3）可獲取大型數據集記錄[Ai]與[Aj]的相似度值，將所獲取相似度與設置閾值比較[9]，利用比較結果獲取大型數據庫重復記錄檢測結果。

為改善傳統檢測方法檢測效率，將量子粒子群算法利用字段相似度量函數優化神經網絡，獲取精準的大型數據庫重復記錄檢測結果。

1.2? 字段相似度量

現實世界中的實體在數據庫中利用存在相同或相似的不同記錄表示，數據庫由字符串類型組成字段，字符串數據間存在微小差異造成數據庫中重復記錄存在差異[10]，重復記錄檢測需要獲取數據庫字段相似度。選取Jaro算法以及TF?IDF算法計算大型數據庫中不同記錄字段相似度量函數。

1.2.1? Jaro算法

Jaro算法是計算不同字符串相似度的有效方法，是依據不同字符串互相存在的字符數量與順序計算相似度的方法。通過Jaro可有效識別字符串拼寫錯誤，便于檢查大型數據庫中存在極為相似的重復記錄[11]。設大型數據庫中存在兩個字符串分別為[z1]以及[z2]，采用Jaro算法獲取相似度量函數公式如下：

1.2.2? TF?IDF算法

建立不同字符串關系，關系表中，其中1個字段內全部單詞集合用[O]表示。[z1]，[z2]與[q]分別表示字符串型字段值以及字段值[z1]內單詞，依據TF?IDF算法可得單詞[q]的權值如下：

通過以上公式可得：

1.2.3? 字段最終相似度量函數

結合Jaro算法以及TF?IDF算法的相似度量函數，由于[q∈z1]，[v∈z2]，可知集合[closeθ，z1，z2]可用[q，v]表示，不同記錄的最終字段相似度量函數公式如下：

1.3? 量子粒子群算法優化神經網絡

BP神經網絡通常選取隨機方式建立連接初始閾值與權值進行學習，采用BP神經網絡容易出現局部最優以及收斂速度慢的缺陷，無法獲取最優神經網絡大型數據庫重復記錄檢測結果[12]。

將量子粒子群算法與BP神經網絡相結合，利用量子粒子群算法選取BP神經網絡初始權值和閾值，提升大數據庫重復記錄的檢測精度。量子粒子群算法是基于量子力學角度發展而來的粒子群算法[13]，通過量子粒子群算法可保證大型數據庫中重復記錄檢測過程快速收斂至全局最優解。

設量子粒子群內全部粒子的最優位置用[mbest]表示，[mbest]計算公式如下：

量子粒子群算法中選取[β]作為影響算法收斂速度唯一控制參數。為提升量子粒子群算法應用于大型數據庫重復記錄檢測的適應性[14]，將量子粒子群算法優化為變參數量子粒子群優化算法，其中，參數[β]取值如下：

利用變參數量子粒子群優化算法優化BP神經網絡，獲取的大型數據庫重復記錄檢測步驟如下：

1） 采集大型數據庫內數據，利用Jaro算法以及TF?IDF算法字段相似度量方法獲取記錄特征向量，利用人工標記方法標記記錄類型，并將所標記記錄類型設置為BP神經網絡期望輸出，構建BP神經網絡學習樣本。

2） 變參數量子粒子群內形成初始量子，設置初始連接權值與初始連接閾值作為量子粒子群內的粒子，利用BP神經網絡依據訓練樣本學習，通過學習獲取量子粒子群的適應度函數值，依據適應度函數值獲取粒子此刻最優位置以及全局最優位置。

3） 將個體粒子歷史最優位置以及粒子群群體最優位置實時更新。

4） 依據式（9）獲取量子粒子群內全部粒子的最優位置。

5） 實時更新量子粒子群內粒子位置。

6） 設置理想輸出值，當BP神經網絡輸出值符合理想輸出值時，結束訓練[15]。此時全局最優位置粒子設置為BP神經網絡的初始連接閾值以及初始連接權值;否則轉回步驟3）繼續訓練。

7） 將所獲取訓練集利用BP神經網絡重新學習，利用重新學習結果建立大型數據庫重復記錄檢測模型，利用該檢測模型檢測訓練集中的訓練數據。設置檢測門限值為0.6，當輸出結果大于所設置檢測門限值時，則認為該記錄為大型數據庫內的重復記錄，否則為非重復記錄。

8） 重復以上步驟，直至大型數據庫內全部記錄檢測完成為止。

2? 仿真實驗

為檢測本文研究大型數據庫重復記錄檢測與優化有效性，在CPU為AMD瑞龍三代R7 3700X，內存為4 GB，操作系統為Windows XP的計算機中利用Matlab仿真軟件進行仿真實驗。

選取網絡中SQL Server 2008作為數據庫軟件，選取某新聞網站中的大型新聞數據庫，該數據庫中共包括980 000萬條記錄，其中每條記錄均包括4個字段， 在該大型數據庫中人工添加20 000條重復記錄，并將所添加記錄隨機分為訓練集以及測試集。選取召回率以及檢測準確率作為本文方法檢測重復記錄的評價指標。

式中：[X]表示所檢測重復記錄正確的數量;[Y]表示大型數據庫內存在重復記錄總數;[Z]表示所檢測大型數據庫重復記錄數量。

統計采用本文方法檢測該大型數據庫重復記錄數量。為直觀展示本文方法的檢測性能，將本文方法與支持向量機方法以及決策樹方法進行對比，結果如表1所示。

統計不同方法檢測大型數據庫重復記錄檢測召回率，統計結果如圖1所示。

統計不同方法檢測大型數據庫重復記錄檢測準確率，統計結果如圖2所示。

結合表1、圖1、圖2統計結果可以看出：采用本文方法可有效檢測大型數據庫中重復記錄，且重復記錄檢測召回率以及檢測準確率明顯高于支持向量機方法以及決策樹方法。本文方法由于使用Jaro算法以及TF?IDF算法的字段相似度量方法獲取數據集內記錄字段間的相似度量函數，可有效提取不同記錄字段的相似度特征向量，并將所提取向量應用于重復記錄檢測中，保證大型數據庫重復記錄檢測效率。

為進一步檢測本文方法的檢測性能，統計采用三種方法檢測大型數據庫重復記錄的查全率，結果如表2所示。

通過表2實驗結果可以看出，采用本文方法檢測包含100 000條記錄大型數據庫重復記錄查全率為99.45%，具有較高的查全率，本文方法檢測大型數據庫重復記錄查全率統計結果明顯高于支持向量機方法以及決策樹方法，再次驗證了本文方法檢測性能。

統計采用不同方法檢測大型數據庫重復記錄的檢測迭代次數以及檢測時間，統計結果如表3所示。

通過表3實驗結果可以看出，采用本文方法檢測大型數據庫重復記錄具有較高的檢測效率，檢測迭代次數以及檢測時間明顯低于支持向量機方法以及決策樹方法。本文方法具有大型數據庫重復記錄檢測整體有效性的主要原因是：本文方法將量子粒子群算法與BP神經網絡相結合，提升了大型數據庫重復記錄檢測的整體有效性。

3? 結? 論

數據庫重復記錄檢測對于提升網絡中數據庫質量具有重要意義，尤其是大型數據庫，采用以往方法檢測重復記錄時，檢測結果并不理想。利用變參數量子粒子群算法優化BP神經網絡，可有效提升大型數據庫重復記錄檢測精度以及檢測效率。

通過某新聞網站中大型數據庫中980 000條記錄，以及人工添加20 000條重復記錄作為實驗對象，仿真實驗結果驗證了本文方法的重復記錄檢測精度以及檢測性能，該方法適用于記錄數量較多的大型數據庫，可應用于實際數據庫重復記錄檢測中。

注：本文通訊作者為覃少華。

參考文獻

[1] 袁超，岳敏，馬濤，等.基于Fusion Compute虛擬化平臺的HIRFL數據庫遷移及性能優化[J].原子能科學技術，2019，53（9）：1697?1701.

[2] 孟小峰，馬超紅，楊晨.機器學習化數據庫系統研究綜述[J].計算機研究與發展，2019，56（9）：1803?1820.

[3] 丁嘉偉，劉秀磊，白雪瑞，等.一種基于決策樹的數據庫本體學習優化方法[J].電視技術，2019，43（4）：6?10.

[4] 吳川徽，黃仕靖，儲節旺，等.基于集成科研項目數據庫的計量分析[J].情報科學，2019，37（6）：151?156.

[5] 焦守濤，周永章，張旗，等.基于GEOROC數據庫的全球輝長巖大數據的大地構造環境智能判別研究[J].巖石學報，2018，34（11）：3189?3194.

[6] 葉鷗，李占利.視頻數據質量與視頻數據檢測技術[J].西安科技大學學報，2017，37（6）：919?926.

[7] 趙剛，鄭軍，封二強.基于虛擬設備的數據記錄軟件測試環境研究[J].微電子學與計算機，2019，36（7）：70?75.

[8] 劉宇，蘇攀，金升平.新建住宅虛擬重復交易數據的生成方法[J].統計與決策，2018，34（1）：81?84.

[9] 吳剛，阿卜杜熱西提·熱合曼，李梁，等.NUMA架構下數據熱度的內存數據庫日志恢復技術[J].計算機科學與探索，2019，13（6）：941?949.

[10] 張建坤，禹思敏.面向混合型位置大數據的差分隱私聚類算法[J].計算機工程與設計，2019，40（9）：2451?2455.

[11] 曾海峰，王淑營，董欽鈺，等.傳統RDBMS向非關系型MongoDB數據模型轉換與數據遷移方法研究[J].計算機應用研究，2017，34（11）：3339?3344.

[12] 武慧娟.知識聚類視角下國際大數據領域前沿演進研究[J].情報科學，2019，37（5）：173?177.

[13] 楊文陽，于曉.大數據和學習分析在高?；旌蠈W習環境中的應用機理探究[J].高校教育管理，2018，12（3）：72?79.

[14] 韓莎莎，吳鑫淼，郄志紅，等.基于BIM技術的大型渡槽管理信息系統研究[J].水電能源科學，2018，36（6）：96?99.

[15] 徐斌.基于GIS的水文生態空間數據庫及管理系統研發[J].水生態學雜志，2018，39（5）：7?12.