呂國(guó)俊， 曹建軍， 鄭奇斌， 常宸， 翁年鳳， 彭琮

(1.陸軍工程大學(xué) 指揮控制工程學(xué)院， 江蘇 南京 210007；2.國(guó)防科技大學(xué) 第六十三研究所， 江蘇 南京 210007)

0 引言

隨著科技、經(jīng)濟(jì)的迅速發(fā)展，日益增長(zhǎng)的數(shù)據(jù)給人們的生活帶來(lái)便利，與此同時(shí)，數(shù)據(jù)質(zhì)量問(wèn)題也日漸突顯。數(shù)據(jù)清洗是通過(guò)檢測(cè)、分析和修正數(shù)據(jù)中的錯(cuò)誤或不一致來(lái)提高數(shù)據(jù)質(zhì)量的有效途徑[1]。由于字符錯(cuò)誤、重復(fù)錄入等原因，同一個(gè)數(shù)據(jù)源中可能包含多個(gè)相似重復(fù)記錄，導(dǎo)致數(shù)據(jù)質(zhì)量降低。針對(duì)相似重復(fù)記錄的普遍性、復(fù)雜性以及對(duì)后續(xù)數(shù)據(jù)利用的影響，如何檢測(cè)和消除相似重復(fù)記錄一直是數(shù)據(jù)清洗研究關(guān)注的熱點(diǎn)[2]。

現(xiàn)有的相似重復(fù)記錄檢測(cè)算法主要包括基于屬性相似度的方法和基于關(guān)聯(lián)關(guān)系的方法。其中基于屬性相似度的方法根據(jù)屬性信息的相似程度進(jìn)行記錄對(duì)的匹配。宋國(guó)興等[3]提出一種基于關(guān)鍵屬性組的相似重復(fù)記錄檢測(cè)方法，該方法首先通過(guò)屬性間的互信息進(jìn)行屬性選擇，然后將屬性值用內(nèi)碼表示，根據(jù)內(nèi)碼序值進(jìn)行聚類(lèi)，最后由同一類(lèi)中的內(nèi)碼之間的相似度進(jìn)行相似重復(fù)記錄匹配，該方法有效解決了記錄屬性維度過(guò)高帶來(lái)的問(wèn)題。針對(duì)高維數(shù)據(jù)噪聲對(duì)檢測(cè)造成的影響，宋國(guó)興等[4]又對(duì)傳統(tǒng)的基于空間距離的相似性度量進(jìn)行改進(jìn)，將屬性值的接近程度作為相似性度量的依據(jù)，實(shí)驗(yàn)證實(shí)了該度量方法具有較高的穩(wěn)定性。曹建軍等[5]采用有監(jiān)督的學(xué)習(xí)算法，利用支持向量機(jī)(SVM)對(duì)記錄對(duì)之間的屬性相似度向量進(jìn)行分類(lèi)，判定是否為相似重復(fù)記錄，實(shí)驗(yàn)表明該方法具有較高的查準(zhǔn)率和查全率，但該方法未考慮到真實(shí)數(shù)據(jù)集中相似重復(fù)記錄樣本稀少的問(wèn)題。針對(duì)大數(shù)據(jù)來(lái)源多、維度高、體量大的特點(diǎn)，宋人杰等[6]對(duì)傳統(tǒng)SimHash算法進(jìn)行改進(jìn)，利用倒排索引算法提高相似重復(fù)記錄的匹配效率，并用MapReduce模型在云環(huán)境下實(shí)現(xiàn)大數(shù)據(jù)相似重復(fù)記錄的并行檢測(cè)和直接輸出。Elziky等[7]將N-Gram索引字符串使用相應(yīng)的ASCII碼轉(zhuǎn)化為數(shù)值，在保證相似重復(fù)記錄檢測(cè)準(zhǔn)確性的條件下提高了檢測(cè)效率。Samiei等[8]提出一種基于聚類(lèi)的排序近鄰算法，該算法解決了對(duì)于動(dòng)態(tài)記錄進(jìn)行相似重復(fù)檢測(cè)的效率問(wèn)題。

基于關(guān)聯(lián)關(guān)系的方法相比基于屬性相似度的方法，還利用了屬性間的關(guān)聯(lián)關(guān)系信息(如作者和單位2個(gè)屬性之間的隸屬關(guān)系)，擁有更高的準(zhǔn)確性[9]。馬平全等[10]利用N-Gram語(yǔ)言模型對(duì)記錄間的潛在聯(lián)系計(jì)算N-Gram值并進(jìn)行排序，根據(jù)排序結(jié)果計(jì)算記錄間的相似度完成相似重復(fù)記錄檢測(cè)。Rabia等[11]提出基于訓(xùn)練數(shù)據(jù)的自適應(yīng)學(xué)習(xí)模型，學(xué)習(xí)了訓(xùn)練數(shù)據(jù)中的關(guān)系類(lèi)型，增強(qiáng)了對(duì)問(wèn)題模型的適應(yīng)性；在此基礎(chǔ)之上，譚明超等[12]提出了一種基于關(guān)系類(lèi)型自適應(yīng)學(xué)習(xí)方法，將權(quán)重放在關(guān)系類(lèi)型上，并給出一種基于有監(jiān)督學(xué)習(xí)的權(quán)重學(xué)習(xí)模型，用于降低權(quán)重學(xué)習(xí)對(duì)訓(xùn)練數(shù)據(jù)的要求，進(jìn)一步提高準(zhǔn)確性。

盡管當(dāng)今的數(shù)據(jù)總量龐大，增長(zhǎng)迅速。但在某些領(lǐng)域，數(shù)據(jù)稀缺問(wèn)題仍然是大數(shù)據(jù)質(zhì)量面臨的重大挑戰(zhàn)之一[13]，上述相似重復(fù)記錄檢測(cè)算法能夠完成在大數(shù)據(jù)背景下的相似重復(fù)記錄檢測(cè)工作，但這些算法并未考慮到真實(shí)數(shù)據(jù)源中相似重復(fù)記錄稀缺的問(wèn)題。不同于經(jīng)典SVM分類(lèi)器采用兩類(lèi)訓(xùn)練樣本“間隔最大”訓(xùn)練超平面實(shí)現(xiàn)最優(yōu)分類(lèi)，基于支持向量的單類(lèi)分類(lèi)器模型的特殊性在于只有一類(lèi)訓(xùn)練樣本，這對(duì)于一些由于復(fù)雜性高，獲取樣本的代價(jià)高昂，數(shù)據(jù)稀缺等原因只能獲取其中的一類(lèi)樣本的分類(lèi)問(wèn)題具有重要意義，如異常檢測(cè)、故障診斷等[14]。

基于支持向量的單類(lèi)分類(lèi)器有單類(lèi)支持向量機(jī)(OCSVM)和支持向量域描述(SVDD)兩個(gè)經(jīng)典模型[15]，Scholkopf等[16]提出的OCSVM算法將特征空間零點(diǎn)設(shè)置為非目標(biāo)類(lèi)唯一的實(shí)例來(lái)構(gòu)建超平面并使零點(diǎn)到超平面的距離最大化。Xue等[17]通過(guò)對(duì)比該分類(lèi)器和經(jīng)典二分類(lèi)SVM的分類(lèi)性能驗(yàn)證了OCSVM算法在進(jìn)行故障診斷中的優(yōu)越性。Tax等[18]提出一種軟間隔的最小超球SVDD方法，該方法從特征空間中找到能夠?qū)⑺杏?xùn)練樣本包含在其中的最小超球面，繼而通過(guò)測(cè)試樣本和超球面的位置關(guān)系進(jìn)行分類(lèi)。針對(duì)SVDD對(duì)非球型目標(biāo)樣本包裹緊湊性的問(wèn)題，Wei等[19]利用超橢球代替SVDD中的超球以適應(yīng)目標(biāo)樣本映射到特征空間后的結(jié)構(gòu)信息。Burnaev等[20]對(duì)OCSVM和SVDD等兩種方法在訓(xùn)練目標(biāo)樣本、構(gòu)建松弛變量時(shí)引入額外的信息(如圖像分類(lèi)時(shí)的文本描述信息、惡意軟件檢測(cè)時(shí)的源代碼信息等)來(lái)細(xì)化分離邊界的位置、提高異常檢測(cè)的準(zhǔn)確性。

針對(duì)真實(shí)數(shù)據(jù)源中相似重復(fù)記錄稀缺的問(wèn)題，使用OCSVM實(shí)現(xiàn)對(duì)相似重復(fù)記錄的分類(lèi)檢測(cè)。其中考慮到記錄的特征個(gè)數(shù)對(duì)于分類(lèi)效果的影響，利用多目標(biāo)蟻群算法進(jìn)行特征選擇，實(shí)現(xiàn)分類(lèi)效果優(yōu)化。

本文第1節(jié)介紹OCSVM單類(lèi)分類(lèi)器模型的方法并給出相似重復(fù)記錄檢測(cè)問(wèn)題描述；第2節(jié)結(jié)合單類(lèi)訓(xùn)練樣本特點(diǎn)，設(shè)計(jì)了求解最優(yōu)屬性子集的多目標(biāo)蟻群優(yōu)化算法，實(shí)現(xiàn)了對(duì)記錄屬性的特征選擇；第3節(jié)實(shí)驗(yàn)部分給出該重復(fù)記錄檢測(cè)方法的效果和效率驗(yàn)證；第4節(jié)進(jìn)行總結(jié)。

1 方法描述

1.1 基于OCSVM的單類(lèi)分類(lèi)器模型

OCSVM通過(guò)實(shí)現(xiàn)該類(lèi)樣本與特征空間零點(diǎn)之間的“間隔最大”構(gòu)造分離超平面，并且最大化分離超平面到零點(diǎn)的距離。模型如(1)式：

(1)

ξi≥0,

式中：w為高維空間分離超平面的法向量；Φ(xi)為一個(gè)將特征向量xi映射到高維特征空間中的特征投影函數(shù)；d為空間零點(diǎn)到分離超平面的距離；ξi為松弛變量；s為樣本總數(shù)；ν為正則化系數(shù)。采用拉格朗日乘子法對(duì)模型進(jìn)行求解，將核函數(shù)帶入得到最終函數(shù)模型：

(2)

式中：αi為拉格朗日乘子；K(x,xi)為核函數(shù)。本文采用徑向基核函數(shù)(RBF)，2個(gè)樣本xi和xj之間的核函數(shù)定義為

K(xi-xj)=exp (-γ‖xi-xj‖2),γ>0，

(3)

式中：γ為設(shè)置的內(nèi)核傳播參數(shù)。

OCSVM創(chuàng)建了一個(gè)參數(shù)為w和d的超平面，該超平面與特征空間中的零點(diǎn)距離最大，并且將零點(diǎn)與所有的訓(xùn)練數(shù)據(jù)點(diǎn)分開(kāi)，如圖1所示。圖1中：O為空間內(nèi)坐標(biāo)零點(diǎn)；l為OCSVM創(chuàng)建的超平面，能夠?qū)⒘泓c(diǎn)與訓(xùn)練樣本分開(kāi)且保證零點(diǎn)到超平面的距離最大；l1、l2為其他超平面。

圖1 OCSVM超平面構(gòu)造圖Fig.1 OCSVM hyperplane structure

利用基于OCSVM的單類(lèi)分類(lèi)器模型能夠在缺少負(fù)類(lèi)樣本情況下進(jìn)行有效分類(lèi)的特性，結(jié)合真實(shí)數(shù)據(jù)源中相似重復(fù)記錄樣本稀少的實(shí)際，將不相似重復(fù)記錄對(duì)的屬性相似度向量作為正類(lèi)樣本，輸入到分類(lèi)器中進(jìn)行訓(xùn)練，學(xué)習(xí)到不相似重復(fù)記錄對(duì)的統(tǒng)一特征，并具備對(duì)于不相似重復(fù)記錄對(duì)的分類(lèi)能力。然后用訓(xùn)練好的分類(lèi)器對(duì)樣本對(duì)的相似度向量進(jìn)行分類(lèi)，相似重復(fù)記錄對(duì)的向量由于不符合學(xué)習(xí)到的統(tǒng)一特征，會(huì)被分類(lèi)到超平面的另一側(cè)，因此完成對(duì)相似重復(fù)記錄的有效檢測(cè)。

1.2 問(wèn)題描述

對(duì)2條記錄進(jìn)行相似重復(fù)記錄檢測(cè)，首先計(jì)算2條記錄對(duì)應(yīng)屬性值的相似度，再根據(jù)各屬性值的相似度計(jì)算2條記錄的相似程度，并判斷它們是否相似重復(fù)(匹配或不匹配)。文獻(xiàn)[5]將該過(guò)程看成一個(gè)二分類(lèi)的過(guò)程，以一個(gè)記錄對(duì)的屬性相似度向量作為傳統(tǒng)二分類(lèi)SVM的輸入，將其分為相似重復(fù)(匹配)和不相似重復(fù)(不匹配)兩類(lèi)。但該方法需要足夠的相似重復(fù)記錄樣本對(duì)進(jìn)行訓(xùn)練，而真實(shí)數(shù)據(jù)集中相似重復(fù)記錄數(shù)量稀少，制約了傳統(tǒng)SVM的訓(xùn)練效果及分類(lèi)檢測(cè)性能。根據(jù)1.1節(jié)的單類(lèi)分類(lèi)器模型只需要一類(lèi)樣本參與訓(xùn)練的分類(lèi)特點(diǎn)，結(jié)合真實(shí)數(shù)據(jù)集中，相似重復(fù)記錄數(shù)量遠(yuǎn)小于不相似重復(fù)記錄數(shù)量的實(shí)際，提出基于OCSVM單類(lèi)分類(lèi)器的相似重復(fù)記錄檢測(cè)方法。相似重復(fù)記錄檢測(cè)流程如圖2所示。

圖2 相似重復(fù)記錄檢測(cè)流程圖Fig.2 Flow chart of similar duplicate record detection

本文提出的方法和文獻(xiàn)[5]的方法流程區(qū)別在于分類(lèi)器的選擇，文獻(xiàn)[5]使用的是傳統(tǒng)二分類(lèi)SVM進(jìn)行分類(lèi)，訓(xùn)練時(shí)需要相似重復(fù)記錄對(duì)和不相似重復(fù)記錄對(duì)兩類(lèi)樣本；本文考慮到真實(shí)數(shù)據(jù)集中相似重復(fù)記錄個(gè)數(shù)稀少的實(shí)際，采用OCSVM進(jìn)行分類(lèi)，只需不相似重復(fù)記錄對(duì)這一類(lèi)樣本進(jìn)行訓(xùn)練。

2 多目標(biāo)蟻群算法特征選擇

2.1 特征選擇模型

在高維度的特征集中，冗余特征的存在往往嚴(yán)重影響著分類(lèi)效率和效果[21]。在相似重復(fù)記錄檢測(cè)中亦是如此，冗余的屬性信息的存在給相似重復(fù)記錄的準(zhǔn)確分類(lèi)造成困難。特征選擇通過(guò)構(gòu)建最優(yōu)特征子集來(lái)消除數(shù)據(jù)中的冗余信息，減小運(yùn)算復(fù)雜度，實(shí)現(xiàn)分類(lèi)效率效果最優(yōu)。

對(duì)于相似重復(fù)記錄檢測(cè)算法效果的評(píng)價(jià)指標(biāo)主要有4個(gè)：查準(zhǔn)率P、查全率R、分類(lèi)正確率A和F1指標(biāo)。分別為

(4)

(5)

(6)

(7)

式中：TN為檢測(cè)出的真的相似重復(fù)記錄對(duì)數(shù)；TP為檢測(cè)出的真的不相似重復(fù)記錄對(duì)數(shù)；FN為檢測(cè)出的假的相似重復(fù)記錄對(duì)數(shù)；FP為檢測(cè)出的假的不相似重復(fù)記錄對(duì)數(shù)。

通常，查準(zhǔn)率和查全率不能同時(shí)達(dá)到最優(yōu)，對(duì)采用查準(zhǔn)率和查全率為主要評(píng)價(jià)指標(biāo)的相似重復(fù)記錄分類(lèi)檢測(cè)算法，可以將特征選擇問(wèn)題描述為：從屬性集A中選擇一個(gè)基數(shù)為q的屬性子集Aq，使由Aq所包含屬性生成的相似特征向量的相似重復(fù)檢測(cè)查準(zhǔn)率和查全率綜合達(dá)到最優(yōu)，同時(shí)Aq規(guī)模最小。即對(duì)相似特征向量的特征進(jìn)行選擇的過(guò)程，其數(shù)學(xué)模型為

(8)

(9)

minq，

(10)

s.t. |Aq|=q,1≤q≤q′，

式中：Λ(Aq)表示以屬性子集Aq生成的相似特征向量為輸入的分類(lèi)器Λ的分類(lèi)結(jié)果，根據(jù)(8)式和(9)式，由測(cè)試樣本計(jì)算可得；q′表示屬性集A中的屬性總數(shù)。(8)式～(10)式表示基于A(yíng)q的相似重復(fù)記錄檢測(cè)結(jié)果的查全率和查準(zhǔn)率最大，同時(shí)使Aq的規(guī)模最小，其中(8)式和(9)式的優(yōu)先級(jí)大于(10)式。因此，相似重復(fù)記錄的特征選擇是一個(gè)多目標(biāo)的子集問(wèn)題。

2.2 模型的蟻群算法求解

多目標(biāo)問(wèn)題通常并不存在各目標(biāo)都為全局最優(yōu)的解的情況，而存在一非劣解集，稱(chēng)為Pareto最優(yōu)解集，多目標(biāo)優(yōu)化的目的是力求找出一組解，盡可能全面地逼近Pareto解集，決策者可按需求進(jìn)行評(píng)價(jià)，選出適用的滿(mǎn)意解[22]。

一類(lèi)基于元啟發(fā)式算法全局搜索的次優(yōu)子集求法得到了快速發(fā)展與應(yīng)用，如蟻群算法、模擬退火算法、遺傳算法、人工免疫算法、粒子群算法、蝙蝠算法、螢火蟲(chóng)算法等[23]。

蟻群算法是一種元啟發(fā)式算法，由于其具有很強(qiáng)的求解較好解的能力、較好的魯棒性、信息正反饋、并行分布式計(jì)算及易于與其他啟發(fā)式方法相結(jié)合等優(yōu)點(diǎn)[24]，在短期內(nèi)得到迅速發(fā)展，應(yīng)用領(lǐng)域也不斷擴(kuò)大，特別是在求解復(fù)雜多目標(biāo)組合優(yōu)化問(wèn)題方面顯示了其優(yōu)越性。Dorigo等[25]將蟻群算法與模擬退火、進(jìn)化規(guī)劃、遺傳算法、模擬- 遺傳算法進(jìn)行了比較，發(fā)現(xiàn)蟻群算法在解決經(jīng)典的組合最優(yōu)化問(wèn)題——旅行商問(wèn)題時(shí)優(yōu)于其他算法。

本節(jié)中以相似重復(fù)記錄檢測(cè)的查準(zhǔn)率和查全率作為優(yōu)化目標(biāo)，對(duì)于給定的q值，求出(8)式、(9)式模型的滿(mǎn)意解，采用多目標(biāo)蟻群算法求解，步驟如下：

步驟1引入基于圖的螞蟻系統(tǒng)[26]，根據(jù)相似重復(fù)記錄檢測(cè)特征選擇問(wèn)題構(gòu)造有向圖。螞蟻根據(jù)有向圖邊上的信息素值與靜態(tài)啟發(fā)式信息構(gòu)建可行解。如圖3所示的特征選擇問(wèn)題的構(gòu)造圖中，在t時(shí)刻v1處生成M只螞蟻。每只螞蟻根據(jù)邊的信息素和啟發(fā)式信息獨(dú)立的選擇某一條路徑向下一個(gè)節(jié)點(diǎn)移動(dòng)，其中c為特征總數(shù)，n為螞蟻在一次搜索中尋找解的個(gè)數(shù)，eij表示螞蟻在第j步選擇第i個(gè)特征。

圖3 特征選擇問(wèn)題構(gòu)造圖Fig.3 Construction diagram of feature selection

步驟2引用文獻(xiàn)[5]中螞蟻選擇路徑的路徑轉(zhuǎn)移概率公式來(lái)實(shí)現(xiàn)圖3中螞蟻的概率轉(zhuǎn)移,如(11)式所示，

(11)

式中：ebj表示螞蟻在第j步選擇第b個(gè)特征；禁忌表tabum為第m只螞蟻?zhàn)哌^(guò)的邊，即螞蟻已經(jīng)選擇的特征；α和β分別為信息素重要程度和啟發(fā)式信息重要程度的系數(shù)；τij(t-1)為在t-1(t=1,2,3,…)時(shí)刻的邊eij上的信息素量；τbj(i-1)為在t-1(t=1,2,3,…)時(shí)刻的邊ebj上的信息素量；ηb為選擇第b個(gè)特征的期望程度。由于需要同時(shí)優(yōu)化查準(zhǔn)率和查全率2個(gè)目標(biāo)，對(duì)其分別設(shè)置信息素矩陣，在計(jì)算轉(zhuǎn)移概率中的τij(t-1)時(shí)，采用(12)式2個(gè)信息素矩陣進(jìn)行聚合：

(12)

(13)

式中：σi為不相似重復(fù)類(lèi)內(nèi)第i個(gè)相似特征值的標(biāo)準(zhǔn)差。在只有一類(lèi)樣本的條件下，無(wú)法像線(xiàn)性判別分析那樣通過(guò)度量多類(lèi)情況中利用類(lèi)間信息選擇特征，(13)式表明，只通過(guò)類(lèi)內(nèi)散度的最小化來(lái)選擇特征，即算法優(yōu)先選擇最小化單類(lèi)訓(xùn)練樣本離散程度(即標(biāo)準(zhǔn)差小)的特征。

步驟3當(dāng)螞蟻每次迭代完畢后，按照(14)式和(15)式分別對(duì)查準(zhǔn)率信息素矩陣和查全率信息素矩陣進(jìn)行更新：

(14)

(15)

式中：ρ為信息素?fù)]發(fā)系數(shù)；tabut為t時(shí)刻選擇的特征路徑；Δ′(tabut)為信息素更新增量，計(jì)算公式為

(16)

F(tabut)為對(duì)應(yīng)更新的信息素矩陣的目標(biāo)函數(shù)值，Q為常數(shù)(根據(jù)ρ值確定，主要調(diào)節(jié)信息素增量的大小)。

通過(guò)對(duì)于不同q值求得的Pareto解集進(jìn)行比較更新，移除支配解，在最后的Pareto解集中選取特征個(gè)數(shù)最少的解，保證特征規(guī)模的最小化。

求解多目標(biāo)蟻群算法優(yōu)化模型的算法描述如下：

算法1. 多目標(biāo)蟻群算法進(jìn)行特征選擇

輸入：候選特征集，待求特征子集中特征個(gè)數(shù)范圍、蟻群算法相關(guān)初始化參數(shù)

輸出：特征子集的Pareto解集

Begin

初始化

forq=1∶10

{fori=1:ite

{生成M只螞蟻用于搜索

form=1∶M

{根據(jù)(11)式計(jì)算轉(zhuǎn)移路徑概率，選擇特征；

用被選的特征進(jìn)行OCSVM訓(xùn)練和測(cè)試；

保存解；

}

移除非支配解

fornum=1∶2

{根據(jù)(14)式和(15)式更新信息素矩陣；

}

}

Pareto解集存儲(chǔ)

}

不同q值的Pareto解集比較更新，移除非支配解

輸出Pareto解集

End.

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

3.1 實(shí)驗(yàn)數(shù)據(jù)及預(yù)處理

本文的實(shí)驗(yàn)數(shù)據(jù)來(lái)源于文獻(xiàn)[5]中的某信息系統(tǒng)的人員基本情況表pst和UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的adult數(shù)據(jù)集。按照相似重復(fù)記錄的比例不同，對(duì)這兩個(gè)數(shù)據(jù)集分別以10%、5%、2%的相似重復(fù)記錄占比進(jìn)行數(shù)據(jù)集劃分。

對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，引用文獻(xiàn)[5]中對(duì)記錄內(nèi)字符串型、枚舉型、日期型等不同類(lèi)型屬性的相似度計(jì)算方法，計(jì)算數(shù)據(jù)集中記錄對(duì)之間的相似特征向量。

3.2 仿真結(jié)果及分析

3.2.1 參數(shù)設(shè)置

實(shí)驗(yàn)中所用各個(gè)算法的參數(shù)信息如表1所示。

表1 參數(shù)信息表Tab.1 Algorithm parameters

注:k為訓(xùn)練數(shù)據(jù)的特征個(gè)數(shù)。

3.2.2 實(shí)驗(yàn)設(shè)置及結(jié)果分析

為選擇較好的分類(lèi)方式，實(shí)驗(yàn)對(duì)比OCSVM[16]和SVDD[18]這兩種基于支持向量的單類(lèi)分類(lèi)算法的相似重復(fù)記錄檢測(cè)結(jié)果，其中，不相似重復(fù)記錄對(duì)為正類(lèi)樣本，相似重復(fù)記錄對(duì)為負(fù)類(lèi)樣本。實(shí)驗(yàn)采用5重交叉檢驗(yàn)取均值的方法[27]，以消除由于訓(xùn)練集和測(cè)試集劃分所得結(jié)果的偶然性，有助于評(píng)估模型的穩(wěn)定性。評(píng)價(jià)指標(biāo)為F1值、查準(zhǔn)率、查全率和分類(lèi)正確率。對(duì)于兩個(gè)單類(lèi)分類(lèi)器模型，通過(guò)采用網(wǎng)格搜索的方法得到各算法的參數(shù)如表1所示，確保OCSVM和SVDD算法能夠在實(shí)驗(yàn)過(guò)程中達(dá)到較優(yōu)的分類(lèi)效果。

表2中的實(shí)驗(yàn)結(jié)果均為5重交叉檢驗(yàn)后的均值。對(duì)其進(jìn)行分析，發(fā)現(xiàn)數(shù)據(jù)集不同，得到的F1值的結(jié)果也不一樣，對(duì)比發(fā)現(xiàn)，使用OCSVM分類(lèi)效果略好于使用SVDD的分類(lèi)效果，每一個(gè)數(shù)據(jù)集測(cè)試結(jié)果的查準(zhǔn)率和查全率能夠同時(shí)取得較優(yōu)的結(jié)果。但是，對(duì)于數(shù)據(jù)集pst5%而言，SVDD的結(jié)果略好于OCSVM，尤其在查準(zhǔn)率指標(biāo)上，SVDD能夠得到最優(yōu)的結(jié)果1.000 0，可能是因?yàn)樵摂?shù)據(jù)集具有更特殊的數(shù)據(jù)分布(正類(lèi)樣本更趨于球體分布)。

通過(guò)對(duì)比不同相似重復(fù)比率進(jìn)行數(shù)據(jù)劃分后的分類(lèi)結(jié)果，可以發(fā)現(xiàn)，數(shù)據(jù)中正負(fù)類(lèi)的不平衡程度對(duì)于OCSVM和SVDD這樣的單類(lèi)分類(lèi)器分類(lèi)結(jié)果影響不大，各個(gè)指標(biāo)上的小幅波動(dòng)是由于劃分后的數(shù)據(jù)集中數(shù)據(jù)分布不同所導(dǎo)致。

為測(cè)試單類(lèi)分類(lèi)器OCSVM、SVDD在解決相似重復(fù)記錄檢測(cè)問(wèn)題的有效性，實(shí)驗(yàn)對(duì)比了OCSVM、SVDD和在訓(xùn)練數(shù)據(jù)中不同正負(fù)類(lèi)樣本數(shù)目比例下的傳統(tǒng)二分類(lèi)SVM的分類(lèi)結(jié)果。在pst數(shù)據(jù)集上，采用5重交叉檢驗(yàn)取均值的方法，其中OCSVM、SVDD采用80個(gè)正類(lèi)樣本進(jìn)行訓(xùn)練，傳統(tǒng)SVM在此基礎(chǔ)上隨機(jī)加入不同比例個(gè)數(shù)的負(fù)類(lèi)樣本進(jìn)行訓(xùn)練。所得分類(lèi)結(jié)果的F1值對(duì)比如圖4所示。圖4中：橫坐標(biāo)N表示傳統(tǒng)SVM訓(xùn)練樣本中正負(fù)類(lèi)樣本的比率，N越大表示訓(xùn)練樣本中正負(fù)類(lèi)的數(shù)目越不平衡(負(fù)類(lèi)樣本的數(shù)目相比正類(lèi)樣本越少)；縱坐標(biāo)表示(7)式中的F1值；F1值越大說(shuō)明分類(lèi)效果越好。從圖4中可以看出：OCSVM的分類(lèi)效果要優(yōu)于SVDD的分類(lèi)效果；其次，當(dāng)N≥8時(shí)，OCSVM和SVDD的分類(lèi)效果要優(yōu)于傳統(tǒng)SVM的分類(lèi)效果，且這個(gè)優(yōu)勢(shì)在N=16，N=20時(shí)更加明顯，而當(dāng)N=40，N=80時(shí)，由于訓(xùn)練時(shí)負(fù)類(lèi)樣本數(shù)目過(guò)少，不能分類(lèi)出負(fù)類(lèi)樣本，才出現(xiàn)F1值最小的情況。結(jié)果表明，當(dāng)對(duì)數(shù)據(jù)進(jìn)行分類(lèi)時(shí)，如果能夠用于訓(xùn)練的負(fù)類(lèi)樣本數(shù)很少，采用OCSVM、SVDD的單類(lèi)分類(lèi)器的分類(lèi)效果要遠(yuǎn)好于采用傳統(tǒng)SVM的二分類(lèi)器的分類(lèi)效果。有效彌補(bǔ)了文獻(xiàn)[5]中在用傳統(tǒng)SVM分類(lèi)解決真實(shí)數(shù)據(jù)集時(shí)負(fù)類(lèi)樣本少，難獲取的問(wèn)題。

表2 OCSVM對(duì)比SVDD仿真結(jié)果Tab.2 Comparison of simulated results of OCSVM and SVDD

圖4 OCSVM、SVDD和傳統(tǒng)SVM的F1值比較Fig.4 Comparison of F1 values of OCSVM, SVDD and traditional SVM

圖5 OCSVM、SVDD和SVM的正確率比較Fig.5 Comparison of classification accuracies of OCSVM, SVDD and traditional SVM

類(lèi)似的結(jié)論從圖5中也可以得出，相較于F1值，圖5的縱坐標(biāo)為分類(lèi)正確率。當(dāng)N≥8時(shí)，OCSVM的分類(lèi)正確率要優(yōu)于傳統(tǒng)SVM；當(dāng)N=40，N=80時(shí)，由于缺少負(fù)類(lèi)信息，導(dǎo)致傳統(tǒng)SVM不能分類(lèi)出負(fù)類(lèi)樣本。

3種算法的時(shí)間效率由圖6給出，從圖6中可以看出，OCSVM算法的時(shí)間效率要小于SVDD，N越小時(shí)，傳統(tǒng)SVM的訓(xùn)練時(shí)間越大，這是因?yàn)镹越小時(shí)，訓(xùn)練樣本的總個(gè)數(shù)越大，算法所消耗的時(shí)間也越大。

圖6 OCSVM、SVDD和傳統(tǒng)SVM的時(shí)間效率比較Fig.6 Comparison of time efficiencies of OCSVM, SVDD and traditional SVM

針對(duì)相似重復(fù)記錄的樣本數(shù)遠(yuǎn)小于不相似重復(fù)記錄的樣本數(shù)N≥8，采用傳統(tǒng)SVM分類(lèi)需要一定量的相似重復(fù)類(lèi)樣本，不符合真實(shí)數(shù)據(jù)集中相似重復(fù)記錄個(gè)數(shù)稀少的實(shí)際，故使用OCSVM、SVDD分類(lèi)相比傳統(tǒng)SVM分類(lèi)更行之有效。

4 結(jié)論

本文根據(jù)數(shù)據(jù)源中樣本記錄對(duì)是否相似，將相似重復(fù)記錄檢測(cè)看成二分類(lèi)問(wèn)題，針對(duì)相似重復(fù)記錄樣本稀少的實(shí)際，利用OCSVM單類(lèi)分類(lèi)器分類(lèi)，并使用多目標(biāo)蟻群算法進(jìn)行特征選擇優(yōu)化。得到主要結(jié)論如下：

1)利用OCSVM單類(lèi)分類(lèi)器進(jìn)行分類(lèi)，解決了真實(shí)數(shù)據(jù)源中相似重復(fù)記錄樣本少、難獲取的問(wèn)題。

2)設(shè)計(jì)啟發(fā)式因子為類(lèi)內(nèi)散度最小化約束的多目標(biāo)蟻群算法特征選擇優(yōu)化模型，綜合考慮算法的查準(zhǔn)率、查全率和特征規(guī)模，得到了較優(yōu)的分類(lèi)效果。

3)本文方法在數(shù)據(jù)源中相似重復(fù)記錄樣本稀少情況下的效果優(yōu)于傳統(tǒng)二分類(lèi)SVM分類(lèi)方法，具有更好的適用性。

在當(dāng)今大數(shù)據(jù)發(fā)展的背景之下，數(shù)據(jù)稀缺問(wèn)題仍然是大數(shù)據(jù)質(zhì)量不可忽視的挑戰(zhàn)之一。本文提出的方法能有效解決數(shù)據(jù)源中相似重復(fù)記錄樣本稀缺的問(wèn)題，實(shí)現(xiàn)相似重復(fù)記錄檢測(cè)。