基于深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法

陶姿邑

(陜西中醫(yī)藥大學(xué) 信息化建設(shè)管理處， 陜西 咸陽(yáng) 712046)

0 引言

隨著數(shù)據(jù)挖掘技術(shù)不斷發(fā)展，每天都會(huì)出現(xiàn)大量的數(shù)據(jù)，為了對(duì)這些數(shù)據(jù)進(jìn)行有效管理，出現(xiàn)了數(shù)據(jù)管理系統(tǒng)，由于數(shù)據(jù)的規(guī)模越來(lái)越大，數(shù)量也急劇增大，出現(xiàn)了一些大型數(shù)據(jù)庫(kù)[1]。在數(shù)據(jù)庫(kù)管理系統(tǒng)的實(shí)際應(yīng)用中，由于數(shù)據(jù)庫(kù)本身的冗余特性，存在一些重復(fù)的記錄，當(dāng)重復(fù)記錄數(shù)量過(guò)大時(shí)，導(dǎo)致數(shù)據(jù)庫(kù)存儲(chǔ)的空間變大，成本增加，同時(shí)對(duì)數(shù)據(jù)庫(kù)中的記錄查詢和檢索產(chǎn)生不利影響，無(wú)法在有效的時(shí)間內(nèi)找到用戶真正需要的記錄，因此如何減少重復(fù)記錄是當(dāng)前數(shù)據(jù)庫(kù)管理系統(tǒng)中的一個(gè)關(guān)鍵研究問題[2-3]。

數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)是減少重復(fù)記錄數(shù)量的關(guān)鍵技術(shù)，為此，許多學(xué)者和研究機(jī)構(gòu)對(duì)其進(jìn)行分析，最初學(xué)者們引入文本分析方法實(shí)現(xiàn)數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)，但是相對(duì)于普通文本，數(shù)據(jù)庫(kù)記錄有自身的特殊性，因此數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)錯(cuò)誤率比較高[4]。近年來(lái)，一些學(xué)者將數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)問題看作是一種二分類問題，即將數(shù)據(jù)庫(kù)記錄劃分為重復(fù)和不重復(fù)兩類，通過(guò)引入灰色模型、人工神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等建立數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的分類器[5-7]，灰色模型是一種線性建模方法，而數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)具有較高的非線性變化特點(diǎn)，使得數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)時(shí)間長(zhǎng)，而且數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)精度低，人工神經(jīng)網(wǎng)絡(luò)雖然是一種非線性學(xué)習(xí)算法，但是其易收斂到局最優(yōu)解，使得數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)結(jié)果出現(xiàn)過(guò)擬合或者欠學(xué)習(xí)現(xiàn)象，導(dǎo)致數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)結(jié)果不可靠[8]。支持向量機(jī)是一種深度學(xué)習(xí)算法，具有學(xué)習(xí)速度快、擬合精度高等優(yōu)點(diǎn)，在數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)中得到了廣泛的應(yīng)用，但是其參數(shù)直接影響數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)結(jié)果，目前參數(shù)優(yōu)化問題還沒有得到有效的解決[9]。

為了提高數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)效果，提出了基于深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法。引入支持向量機(jī)對(duì)數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)進(jìn)行建模，并采用量子粒子群算法優(yōu)化支持向量機(jī)參數(shù)，最后通過(guò)數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)仿真實(shí)驗(yàn)驗(yàn)證了本文算法的性能。

1 深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法

1.1 深度學(xué)習(xí)算法

支持向量機(jī)是新型的深度學(xué)習(xí)算法，相對(duì)于傳統(tǒng)深度學(xué)習(xí)算法，其泛化能力更強(qiáng)，學(xué)習(xí)結(jié)果更加可靠，根據(jù)工作原理，支持向量機(jī)可以劃分為兩類：一類是支持向量分類機(jī)，其用于對(duì)一些分類問題進(jìn)行求解；另一類是支持向量回歸機(jī)，主要用于預(yù)測(cè)問題的建模與分析，而數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)是一種分類問題，因此采用支持向量分類機(jī)進(jìn)行。支持向量機(jī)的分類原理，如圖1所示。

在圖1中，中間粗線為所有樣本的最優(yōu)分類平面，黃色矩形的兩邊為樣本和最優(yōu)分類平面之間的最近距離，兩類樣本應(yīng)該處于黃色矩形之外。

圖1 支持向量分類機(jī)的工作原理

設(shè)數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)訓(xùn)練樣本集合為：{xi,yi}，xi∈Rn，i=1,2,…,l，xi為數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的輸入向量，yi為數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的輸出，那么基于支持向量機(jī)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的最優(yōu)分類平面，如式(1)。

y=ωTΦ(x)+b=ω·φ(x)+b

(1)

式中，ω和b為權(quán)值和偏向量。

要找到數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的最優(yōu)分類平面，首先確定最合理的ω和b值，通常情況下，對(duì)式(1)無(wú)法求解，因?yàn)榍蠼獾臅r(shí)間相當(dāng)長(zhǎng)，有時(shí)難以實(shí)現(xiàn)。為了簡(jiǎn)化ω和b值的求解過(guò)程，通過(guò)采用松弛因子ξi對(duì)式(1)進(jìn)行相應(yīng)的轉(zhuǎn)換，得到式(1)的等價(jià)形式，如式(2)。

s.t.yi(ω·Φ(xi)+b)≥1-ξi

ξi≥0,i=1,2…,n

(2)

式中，C表示支持向量機(jī)的懲罰參數(shù)，主要用于評(píng)價(jià)數(shù)據(jù)庫(kù)重復(fù)記記錄檢測(cè)結(jié)果誤差和計(jì)算時(shí)間的復(fù)雜度。

為了進(jìn)一步優(yōu)化式(1)求解過(guò)程，引入拉格朗日乘子(αi)對(duì)式(2)進(jìn)行變換，如式(3)。

s.t.

(3)

式中，l表示數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的訓(xùn)練樣本數(shù)量。

通過(guò)對(duì)式(3)的求解，可以得到ω的計(jì)算公式，如式(4)。

ω=∑αiyi(Φ(xi)·Φ(x))

(4)

支持向量機(jī)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)分類形式，如式(5)。

f(x)=sgn(αiyi(Φ(xi)·Φ(x))+b)

(5)

式中，Φ(xi)·Φ(x)表示點(diǎn)積運(yùn)算，sgn()表示符號(hào)函數(shù)。

當(dāng)數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)具有隨機(jī)性、非線性變化特點(diǎn)，Φ(xi)·Φ(x)運(yùn)行過(guò)程十分復(fù)雜，這樣影響數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)效率，為此采用核函數(shù)k(x,xi)代替Φ(xi)·Φ(xj)，加快數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的速度，如式(6)。

f(x)=sgn(αiyik(x,xi)+b)

(6)

式中，k(x,xi)的表達(dá)式，如式(7)。

(7)

式中，σ表示核寬度。

支持向量機(jī)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)過(guò)程中，參數(shù)C和σ直接影響建模效果，傳統(tǒng)方法采用經(jīng)驗(yàn)方式確定它們的值，這樣難以獲得高正確率的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)結(jié)果，為此本文引入量子粒子群算法確定參數(shù)C和σ的最優(yōu)值。

1.2 量子粒子群算法

量子粒子群算法是一種改進(jìn)粒子群算法，量子粒子群的當(dāng)前最優(yōu)位置為mbest，式(8)[10]。

(8)

第i個(gè)粒子的d維坐標(biāo)，如式(9)。

(9)

式中，uid為一個(gè)隨機(jī)數(shù)，Kid計(jì)算方式，如式(10)

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

(10)

式中，t表示迭代次數(shù)。

粒子位置更新方式，如式(11)。

xid(t+1)=rid±β(t)×|mbest(t)-Xid(t)|×

ln(1/uid(t))

(11)

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

當(dāng)前粒子的最優(yōu)位Ri，如式(12)。

(12)

式中，f()為目標(biāo)函數(shù)。

1.3 量子粒子群算法優(yōu)化支持向量機(jī)參數(shù)步驟

Setp1：初始量子粒子群算法的量子，將參數(shù)C和σ的初始值作為粒子；

Setp2：確定量子粒子群的適應(yīng)度函數(shù)值，并根據(jù)適應(yīng)度函數(shù)值確定當(dāng)前粒子和量子粒子群的最優(yōu)位置；

Setp3：迭代次數(shù)增加，并對(duì)量子粒子群的個(gè)體位置進(jìn)行更新；

Setp4：計(jì)算新種群個(gè)體的適應(yīng)度函數(shù)值，并根據(jù)適應(yīng)度函數(shù)值對(duì)當(dāng)前粒子和量子粒子群的最優(yōu)位置進(jìn)行更新操作；

Setp5：如果達(dá)到最大迭代次數(shù)，就終止近代，不然返回到Setp3；

Setp6：根據(jù)量子粒子群的最優(yōu)位置得到參數(shù)C和σ的最優(yōu)值。

1.4 深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法的工作原理

深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法的工作原理為：首先采用數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)數(shù)據(jù)，并從中提取記錄的特征，采用人工方法對(duì)數(shù)據(jù)庫(kù)記錄類型進(jìn)行標(biāo)記，產(chǎn)生數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的學(xué)習(xí)樣本；然后引入量子粒子群算法確定參數(shù)C和σ的最優(yōu)值，最后采用支持向量機(jī)對(duì)數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)的學(xué)習(xí)樣本進(jìn)行訓(xùn)練，建立數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)模型，如圖2所示。

圖2 深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)原理

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

2.1 實(shí)驗(yàn)環(huán)境

為了分析本文設(shè)計(jì)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法的有效性，采用仿真實(shí)驗(yàn)環(huán)境為CPU(AMD 銳龍R5-3550)，內(nèi)存為16 GB，硬盤為512 GB SSD，操作系統(tǒng)為Win10，編程軟件為Matlab 2017。采用一個(gè)大型數(shù)據(jù)庫(kù)作為實(shí)驗(yàn)對(duì)象，共進(jìn)行5次仿真實(shí)驗(yàn)，隨機(jī)從中選擇部分記錄進(jìn)行仿真測(cè)試，它們均存在一定數(shù)量的重復(fù)記錄，記錄總數(shù)量，如表1所示。

表1 五次仿真實(shí)驗(yàn)的記錄數(shù)量

2.2 數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)正確率分析

在相同實(shí)驗(yàn)環(huán)境下，選擇量子粒子算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)(QPSO-BP)、支持向量機(jī)(SVM)，其參數(shù)采用隨機(jī)方式確定，作為參比模型，將表1中的數(shù)據(jù)庫(kù)記錄根據(jù)5∶1的方式劃分為訓(xùn)練樣本集和測(cè)試樣本集，統(tǒng)計(jì)3種算法的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)正確率，如圖3所示。

圖3 數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)正確率對(duì)比

對(duì)圖3進(jìn)行分析可以得到如下結(jié)論。

(1) QPSO-BP的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)正確率要低于本文算法，這是因?yàn)殡m然兩者都采用量子粒子群算法對(duì)參數(shù)進(jìn)行了優(yōu)化，但是由于BP神經(jīng)網(wǎng)絡(luò)本身的缺陷，使得QPSO-BP無(wú)法建立最優(yōu)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)模型，導(dǎo)致QPSO-BP的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)錯(cuò)誤率較高。

(2) SVM的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)正確率同樣低于本文算法，這是因?yàn)镾VM采用隨機(jī)方式確定參數(shù)，而本文算法采用量子粒子群算法對(duì)參數(shù)進(jìn)行了優(yōu)化，建立了更優(yōu)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)模型，減少了數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)錯(cuò)誤率，對(duì)比實(shí)驗(yàn)結(jié)果體現(xiàn)了本文算法的優(yōu)越性。

2.3 數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)效率分析

由于當(dāng)前數(shù)據(jù)庫(kù)向超大規(guī)模方向進(jìn)行發(fā)展，重復(fù)記錄數(shù)量相當(dāng)大，使得數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)效率十分關(guān)鍵，成為算法的一個(gè)重要評(píng)價(jià)標(biāo)準(zhǔn)，統(tǒng)計(jì)3種算法的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)時(shí)間，如圖4所示。

圖4 數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)效率對(duì)比

從圖4的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)時(shí)間可以看出，本文算法的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)時(shí)間要明顯少于對(duì)比算法，大幅度提升了數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)效率，可以用于大型數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)，具有更高的實(shí)際應(yīng)用價(jià)值。

3 總結(jié)

重復(fù)記錄檢測(cè)對(duì)于提升數(shù)據(jù)庫(kù)檢索效率，找到用戶真正需要的數(shù)據(jù)具有重要意義，針對(duì)當(dāng)前方法檢測(cè)重復(fù)記錄時(shí)檢測(cè)結(jié)果不理想的問題，提出基于深度學(xué)習(xí)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)和優(yōu)化方法，仿真實(shí)驗(yàn)結(jié)果表明，本文算法是一種精度高、效率快的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)算法，為解決大型數(shù)據(jù)庫(kù)重復(fù)記錄問題提供了一種新的研究工具。