大型數(shù)據(jù)庫重復(fù)記錄檢測與優(yōu)化研究

唐吉深 覃少華

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

關(guān)鍵詞： 大型數(shù)據(jù)庫; 重復(fù)記錄檢測; 重復(fù)記錄優(yōu)化; 學(xué)習(xí)樣本構(gòu)建; 最優(yōu)位置確定; 權(quán)值設(shè)置

中圖分類號： TN911.1?34; TP311? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： 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? 引? 言

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

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

數(shù)據(jù)庫中不同記錄中各字段相似度是復(fù)雜的非線性關(guān)系，采用傳統(tǒng)算法無法獲取最優(yōu)結(jié)果，處理效率較低。隨著科技不斷進(jìn)步，采用神經(jīng)網(wǎng)絡(luò)算法以及支持向量機(jī)等算法應(yīng)用于數(shù)據(jù)庫重復(fù)記錄檢測中，提升了重復(fù)記錄檢測精度以及檢測效率[4?6]。

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

神經(jīng)網(wǎng)絡(luò)算法具有學(xué)習(xí)速度快的優(yōu)勢，但極易出現(xiàn)過擬合現(xiàn)象，導(dǎo)致無法獲取最優(yōu)解，而粒子群算法具有全局尋優(yōu)能力[7]。研究大型數(shù)據(jù)庫重復(fù)記錄檢測與優(yōu)化，利用量子粒子群算法對神經(jīng)網(wǎng)絡(luò)算法進(jìn)行優(yōu)化，使其適用于大型數(shù)據(jù)庫海量重復(fù)記錄檢測中，提升重復(fù)記錄檢測精度以及檢測效率。

1? 大型數(shù)據(jù)庫重復(fù)記錄檢測與優(yōu)化方法設(shè)計

1.1? 大型數(shù)據(jù)庫重復(fù)記錄檢測原理

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

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

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

為改善傳統(tǒng)檢測方法檢測效率，將量子粒子群算法利用字段相似度量函數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)，獲取精準(zhǔn)的大型數(shù)據(jù)庫重復(fù)記錄檢測結(jié)果。

1.2? 字段相似度量

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

1.2.1? Jaro算法

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

1.2.2? TF?IDF算法

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

通過以上公式可得：

1.2.3? 字段最終相似度量函數(shù)

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

1.3? 量子粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)通常選取隨機(jī)方式建立連接初始閾值與權(quán)值進(jìn)行學(xué)習(xí)，采用BP神經(jīng)網(wǎng)絡(luò)容易出現(xiàn)局部最優(yōu)以及收斂速度慢的缺陷，無法獲取最優(yōu)神經(jīng)網(wǎng)絡(luò)大型數(shù)據(jù)庫重復(fù)記錄檢測結(jié)果[12]。

將量子粒子群算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合，利用量子粒子群算法選取BP神經(jīng)網(wǎng)絡(luò)初始權(quán)值和閾值，提升大數(shù)據(jù)庫重復(fù)記錄的檢測精度。量子粒子群算法是基于量子力學(xué)角度發(fā)展而來的粒子群算法[13]，通過量子粒子群算法可保證大型數(shù)據(jù)庫中重復(fù)記錄檢測過程快速收斂至全局最優(yōu)解。

設(shè)量子粒子群內(nèi)全部粒子的最優(yōu)位置用[mbest]表示，[mbest]計算公式如下：

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

利用變參數(shù)量子粒子群優(yōu)化算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，獲取的大型數(shù)據(jù)庫重復(fù)記錄檢測步驟如下：

1） 采集大型數(shù)據(jù)庫內(nèi)數(shù)據(jù)，利用Jaro算法以及TF?IDF算法字段相似度量方法獲取記錄特征向量，利用人工標(biāo)記方法標(biāo)記記錄類型，并將所標(biāo)記記錄類型設(shè)置為BP神經(jīng)網(wǎng)絡(luò)期望輸出，構(gòu)建BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)樣本。

2） 變參數(shù)量子粒子群內(nèi)形成初始量子，設(shè)置初始連接權(quán)值與初始連接閾值作為量子粒子群內(nèi)的粒子，利用BP神經(jīng)網(wǎng)絡(luò)依據(jù)訓(xùn)練樣本學(xué)習(xí)，通過學(xué)習(xí)獲取量子粒子群的適應(yīng)度函數(shù)值，依據(jù)適應(yīng)度函數(shù)值獲取粒子此刻最優(yōu)位置以及全局最優(yōu)位置。

3） 將個體粒子歷史最優(yōu)位置以及粒子群群體最優(yōu)位置實(shí)時更新。

4） 依據(jù)式（9）獲取量子粒子群內(nèi)全部粒子的最優(yōu)位置。

5） 實(shí)時更新量子粒子群內(nèi)粒子位置。

6） 設(shè)置理想輸出值，當(dāng)BP神經(jīng)網(wǎng)絡(luò)輸出值符合理想輸出值時，結(jié)束訓(xùn)練[15]。此時全局最優(yōu)位置粒子設(shè)置為BP神經(jīng)網(wǎng)絡(luò)的初始連接閾值以及初始連接權(quán)值;否則轉(zhuǎn)回步驟3）繼續(xù)訓(xùn)練。

7） 將所獲取訓(xùn)練集利用BP神經(jīng)網(wǎng)絡(luò)重新學(xué)習(xí)，利用重新學(xué)習(xí)結(jié)果建立大型數(shù)據(jù)庫重復(fù)記錄檢測模型，利用該檢測模型檢測訓(xùn)練集中的訓(xùn)練數(shù)據(jù)。設(shè)置檢測門限值為0.6，當(dāng)輸出結(jié)果大于所設(shè)置檢測門限值時，則認(rèn)為該記錄為大型數(shù)據(jù)庫內(nèi)的重復(fù)記錄，否則為非重復(fù)記錄。

8） 重復(fù)以上步驟，直至大型數(shù)據(jù)庫內(nèi)全部記錄檢測完成為止。

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

為檢測本文研究大型數(shù)據(jù)庫重復(fù)記錄檢測與優(yōu)化有效性，在CPU為AMD瑞龍三代R7 3700X，內(nèi)存為4 GB，操作系統(tǒng)為Windows XP的計算機(jī)中利用Matlab仿真軟件進(jìn)行仿真實(shí)驗(yàn)。

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

式中：[X]表示所檢測重復(fù)記錄正確的數(shù)量;[Y]表示大型數(shù)據(jù)庫內(nèi)存在重復(fù)記錄總數(shù);[Z]表示所檢測大型數(shù)據(jù)庫重復(fù)記錄數(shù)量。

統(tǒng)計采用本文方法檢測該大型數(shù)據(jù)庫重復(fù)記錄數(shù)量。為直觀展示本文方法的檢測性能，將本文方法與支持向量機(jī)方法以及決策樹方法進(jìn)行對比，結(jié)果如表1所示。

統(tǒng)計不同方法檢測大型數(shù)據(jù)庫重復(fù)記錄檢測召回率，統(tǒng)計結(jié)果如圖1所示。

統(tǒng)計不同方法檢測大型數(shù)據(jù)庫重復(fù)記錄檢測準(zhǔn)確率，統(tǒng)計結(jié)果如圖2所示。

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

為進(jìn)一步檢測本文方法的檢測性能，統(tǒng)計采用三種方法檢測大型數(shù)據(jù)庫重復(fù)記錄的查全率，結(jié)果如表2所示。

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

統(tǒng)計采用不同方法檢測大型數(shù)據(jù)庫重復(fù)記錄的檢測迭代次數(shù)以及檢測時間，統(tǒng)計結(jié)果如表3所示。

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

3? 結(jié)? 論

數(shù)據(jù)庫重復(fù)記錄檢測對于提升網(wǎng)絡(luò)中數(shù)據(jù)庫質(zhì)量具有重要意義，尤其是大型數(shù)據(jù)庫，采用以往方法檢測重復(fù)記錄時，檢測結(jié)果并不理想。利用變參數(shù)量子粒子群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，可有效提升大型數(shù)據(jù)庫重復(fù)記錄檢測精度以及檢測效率。

通過某新聞網(wǎng)站中大型數(shù)據(jù)庫中980 000條記錄，以及人工添加20 000條重復(fù)記錄作為實(shí)驗(yàn)對象，仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的重復(fù)記錄檢測精度以及檢測性能，該方法適用于記錄數(shù)量較多的大型數(shù)據(jù)庫，可應(yīng)用于實(shí)際數(shù)據(jù)庫重復(fù)記錄檢測中。

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

參考文獻(xiàn)

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

[2] 孟小峰，馬超紅，楊晨.機(jī)器學(xué)習(xí)化數(shù)據(jù)庫系統(tǒng)研究綜述[J].計算機(jī)研究與發(fā)展，2019，56（9）：1803?1820.

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

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

[5] 焦守濤，周永章，張旗，等.基于GEOROC數(shù)據(jù)庫的全球輝長巖大數(shù)據(jù)的大地構(gòu)造環(huán)境智能判別研究[J].巖石學(xué)報，2018，34（11）：3189?3194.

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

[7] 趙剛，鄭軍，封二強(qiáng).基于虛擬設(shè)備的數(shù)據(jù)記錄軟件測試環(huán)境研究[J].微電子學(xué)與計算機(jī)，2019，36（7）：70?75.

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

[9] 吳剛，阿卜杜熱西提·熱合曼，李梁，等.NUMA架構(gòu)下數(shù)據(jù)熱度的內(nèi)存數(shù)據(jù)庫日志恢復(fù)技術(shù)[J].計算機(jī)科學(xué)與探索，2019，13（6）：941?949.

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

[11] 曾海峰，王淑營，董欽鈺，等.傳統(tǒng)RDBMS向非關(guān)系型MongoDB數(shù)據(jù)模型轉(zhuǎn)換與數(shù)據(jù)遷移方法研究[J].計算機(jī)應(yīng)用研究，2017，34（11）：3339?3344.

[12] 武慧娟.知識聚類視角下國際大數(shù)據(jù)領(lǐng)域前沿演進(jìn)研究[J].情報科學(xué)，2019，37（5）：173?177.

[13] 楊文陽，于曉.大數(shù)據(jù)和學(xué)習(xí)分析在高?；旌蠈W(xué)習(xí)環(huán)境中的應(yīng)用機(jī)理探究[J].高校教育管理，2018，12（3）：72?79.

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

[15] 徐斌.基于GIS的水文生態(tài)空間數(shù)據(jù)庫及管理系統(tǒng)研發(fā)[J].水生態(tài)學(xué)雜志，2018，39（5）：7?12.