陳旺虎，田 真，張禮智，梁小燕，高雅瓊

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院， 甘肅 蘭州 730070)

1 引言

數(shù)據(jù)驅(qū)動(dòng)方法在規(guī)律發(fā)掘、趨勢(shì)預(yù)測(cè)中發(fā)揮著越來(lái)越重要的作用。由于數(shù)據(jù)質(zhì)量對(duì)數(shù)據(jù)分析的結(jié)果有很大的影響，在對(duì)數(shù)據(jù)進(jìn)行分析前，往往需要過(guò)濾原始數(shù)據(jù)集中存在的異常數(shù)據(jù)。離群點(diǎn)通常被認(rèn)為是偏離其他對(duì)象的個(gè)體，以至于人們懷疑是由另一種機(jī)制產(chǎn)生的[1]。因此，離群點(diǎn)子集往往與其余數(shù)據(jù)表現(xiàn)得不一致[2]。離群點(diǎn)檢測(cè)是異常數(shù)據(jù)檢測(cè)中的核心問(wèn)題[2]，具有重要的研究意義。

監(jiān)督學(xué)習(xí)是當(dāng)前應(yīng)用較為廣泛的一類離群點(diǎn)檢測(cè)方法[3 - 5]。但是，在實(shí)際的離群點(diǎn)檢測(cè)任務(wù)中，異常樣本的提供或者選擇往往存在一定的難度。 如果樣本對(duì)于離群點(diǎn)特征的覆蓋不夠，則嚴(yán)重影響此類方法的檢測(cè)準(zhǔn)確率。無(wú)監(jiān)督的離群點(diǎn)檢測(cè)方法由于不依賴于標(biāo)簽數(shù)據(jù)，與有監(jiān)督的方法相比，其使用條件更為寬松，可應(yīng)用性也更強(qiáng)。在無(wú)監(jiān)督的離群點(diǎn)監(jiān)測(cè)中，基于聚類的方法一直以來(lái)是一個(gè)重要的研究分支。在此類方法中，當(dāng)前的研究方法大多依靠不同的策略，通過(guò)改進(jìn)初始聚類中心等手段來(lái)不斷改善聚類效果，從而提高離群點(diǎn)檢測(cè)的準(zhǔn)確率。

然而，從數(shù)據(jù)的空間分布角度來(lái)看，高維數(shù)據(jù)很多時(shí)候具有稀疏性。因此，基于距離或者密度思想的聚類，容易導(dǎo)致一些非離群點(diǎn)數(shù)據(jù)被排除在聚類所獲得的各個(gè)簇中，降低了離群點(diǎn)的召回率。另一方面，增加距離或者密度閾值雖然可以在一定程度上提高離群點(diǎn)的召回率，但又容易導(dǎo)致離群點(diǎn)數(shù)據(jù)與正常數(shù)據(jù)的交織，降低離群點(diǎn)檢測(cè)的準(zhǔn)確率。綜上，本文針對(duì)高維稀疏數(shù)據(jù)，基于空間數(shù)據(jù)插值的思想，引入空間樣本的遺傳變異策略，試圖探索一種無(wú)監(jiān)督的離群點(diǎn)檢測(cè)方法。

后續(xù)的內(nèi)容安排如下：第2節(jié)對(duì)當(dāng)前的相關(guān)工作進(jìn)行了介紹和分析；第3節(jié)提出了一種基于插值的高維稀疏數(shù)據(jù)離群點(diǎn)檢測(cè)方法，并在第4節(jié)中，對(duì)基于遺傳算法的插值方法進(jìn)行深入分析；第5節(jié)在對(duì)實(shí)驗(yàn)結(jié)果分析的基礎(chǔ)上，對(duì)所提方法進(jìn)行了比對(duì)評(píng)價(jià)；最后，在第6節(jié)中，給出了本文的結(jié)論以及對(duì)將來(lái)工作的展望。

2 相關(guān)工作

有監(jiān)督的離群點(diǎn)檢測(cè)方法通常從樣本數(shù)據(jù)中學(xué)習(xí)并建立正常樣本或者離群樣本的模型。通過(guò)建立假設(shè)模型h(x)并確定閾值ρ，當(dāng)給定樣本x，若h(x) ≥ρ，則認(rèn)為x是正常樣本，否則認(rèn)為其是離群值，而離群值在很多情況下也被認(rèn)為是異常樣本，并且閾值ρ往往根據(jù)經(jīng)驗(yàn)誤差設(shè)置[5]。現(xiàn)有的大多數(shù)離群點(diǎn)檢測(cè)方法都可認(rèn)為是基于該框架的，針對(duì)假設(shè)模型具體構(gòu)建方法不同，演化出了不同的有監(jiān)督離群點(diǎn)檢測(cè)，代表性的工作包括文獻(xiàn)[5 - 8]。

通常來(lái)講，基于監(jiān)督學(xué)習(xí)的離群點(diǎn)檢測(cè)方法具有較高的準(zhǔn)確率，但其準(zhǔn)確率對(duì)于樣本的數(shù)量和標(biāo)注質(zhì)量仍具有很高的依賴性。從某種程度上看，樣本的數(shù)量和標(biāo)注質(zhì)量，決定了此類方法的檢測(cè)效果。然而，大量樣本的標(biāo)注是一項(xiàng)很有挑戰(zhàn)性的工作，這對(duì)于有監(jiān)督的離群點(diǎn)檢測(cè)造成了諸多困難。在很多情況下，也限制了此類方法的實(shí)際應(yīng)用。

非監(jiān)督離群點(diǎn)檢測(cè)方法通常不需要樣本標(biāo)注，與基于監(jiān)督學(xué)習(xí)的離群點(diǎn)檢測(cè)方法相比，其應(yīng)用條件更為寬松。常見(jiàn)的一種思路是通過(guò)參數(shù)化或非參數(shù)化方法估計(jì)訓(xùn)練樣本的密度模型，并設(shè)置相應(yīng)的密度閾值，通過(guò)判斷局部的密度來(lái)確定離群點(diǎn)[9]。當(dāng)前的無(wú)監(jiān)督離群點(diǎn)檢測(cè)方法中，比較有代表性的包括基于相對(duì)密度估計(jì)的檢測(cè)方法、基于模型的檢測(cè)方法和基于支撐域的檢測(cè)方法。

基于相對(duì)密度的離群點(diǎn)檢測(cè)方法可以有效地解決數(shù)據(jù)對(duì)象密度分布不均勻的問(wèn)題[10]。在基于相對(duì)密度估計(jì)的方法中最具代表的是LOF(Local Outlier Factor)算法[11]，然而，這種方法有時(shí)對(duì)參數(shù)很敏感，并且密度估計(jì)方法對(duì)目標(biāo)類數(shù)據(jù)的稀疏區(qū)域很難做出正確的判斷。

基于模型的檢測(cè)方法根據(jù)模型可分為3種類型。點(diǎn)重構(gòu)方法利用樣本點(diǎn)到最近聚類中心的距離作為重構(gòu)誤差來(lái)進(jìn)行離群檢測(cè)，代表性工作包括基于K-means[12]和K-center[13]的離群點(diǎn)檢測(cè)。平面重構(gòu)方法利用最近鄰超平面的距離作為離群點(diǎn)檢測(cè)的重構(gòu)誤差。正是考慮到點(diǎn)重構(gòu)方法難以描述平面簇?cái)?shù)據(jù)，Bradley等人[14]提出了K-plane clustering算法，類似工作還包括基于曲線、曲面和子空間重構(gòu)的離群點(diǎn)檢測(cè)方法。主成分分析PCA(Principal Component Analysis)[15]就是一種基于線性降維的方法，也可以通過(guò)擴(kuò)展在非線性環(huán)境中使用(例如在文獻(xiàn)[16]中提出的KPCA(Kernel PCA)方法)。PCA的另一種非線性擴(kuò)展基于主曲線[17]，根據(jù)數(shù)據(jù)中每個(gè)點(diǎn)的重構(gòu)誤差以及一定經(jīng)驗(yàn)誤差約束下設(shè)定的閾值，構(gòu)造以主曲線為中心的柱形數(shù)據(jù)描述。

由于在實(shí)際的離群點(diǎn)檢測(cè)應(yīng)用中，通常只有一種類型的樣本，Scholkopf[18]利用單分類SVM提出了一種基于支撐域離群點(diǎn)檢測(cè)的方法。該方法為避免受到噪聲數(shù)據(jù)和孤點(diǎn)數(shù)據(jù)的影響，不嚴(yán)格要求訓(xùn)練樣本到球體中心的距離的平方小于或等于R2，但大于R2的點(diǎn)將受到懲罰。在此基礎(chǔ)上，Tax等[19]提出了支持向量數(shù)據(jù)的描述。

上述無(wú)監(jiān)督的離群點(diǎn)檢測(cè)方法，為本文的研究奠定了很好的基礎(chǔ)。但是，在樣本數(shù)量有限的情況下，數(shù)據(jù)的空間分布表現(xiàn)出很高的稀疏性，給基于密度、模型以及支撐域的離群點(diǎn)檢測(cè)造成了很大的困難。事實(shí)上，高維樣本在空間分布上往往具有天然的稀疏性。然而在當(dāng)前的研究中，針對(duì)高維稀疏數(shù)據(jù)的離群點(diǎn)檢測(cè)關(guān)注不多。因此，本文引入高維數(shù)據(jù)空間的插值思想，試圖探索一種針對(duì)高維稀疏數(shù)據(jù)的離群點(diǎn)檢測(cè)方法ODGA(Outlier Detection for Genetic Algorithm )。

3 基于插值的稀疏數(shù)據(jù)離群點(diǎn)檢測(cè)

通常認(rèn)為，離群點(diǎn)對(duì)象與其他對(duì)象存在較大的差異，以至于可懷疑其是由另一種機(jī)制產(chǎn)生的。因此，離群點(diǎn)檢測(cè)可被用于異常數(shù)據(jù)的檢測(cè)。假設(shè)對(duì)所有樣本數(shù)據(jù)進(jìn)行了聚類，則每一簇中的樣本具有相似的特征，而樣本點(diǎn)與質(zhì)心的距離超出一定范圍時(shí)，將很難被歸入到任何一個(gè)簇中，可認(rèn)為該樣本的產(chǎn)生機(jī)制可能與絕大多數(shù)樣本存在差異，從而在很大概率上屬于離群點(diǎn)。

無(wú)監(jiān)督聚類方法簡(jiǎn)單，依賴條件寬松。其中，K-means是具有代表性的基于距離的聚類算法，是當(dāng)前應(yīng)用最為廣泛的聚類算法之一。K-means以距離作為樣本相似性的評(píng)價(jià)依據(jù)，距離越近，認(rèn)為樣本的相似性越高，其可認(rèn)為是尋找緊湊的、獨(dú)立的簇。因此，本文的離群點(diǎn)檢測(cè)方法首先基于K-means聚類，通過(guò)判斷樣本點(diǎn)是否大于一定的閾值來(lái)檢測(cè)離群點(diǎn)。

然而，由于K-means算法以距離平均值作為聚類中心，并將其應(yīng)用到下一次迭代中，當(dāng)聚類中心是噪聲點(diǎn)或孤立點(diǎn)時(shí)，將使得聚類中心偏離數(shù)據(jù)集的密集區(qū)域。因此，如果數(shù)據(jù)集包含大量孤立點(diǎn)或噪聲數(shù)據(jù)，聚類結(jié)果受噪聲或孤立點(diǎn)的影響較大，導(dǎo)致聚類結(jié)果不準(zhǔn)確甚至不正確，從而導(dǎo)致分離出來(lái)的離群數(shù)據(jù)與正確的離群數(shù)據(jù)產(chǎn)生較大偏差。如果直接用傳統(tǒng)K-means算法進(jìn)行離群點(diǎn)檢測(cè)勢(shì)必會(huì)導(dǎo)致大量的離群點(diǎn)影響聚類結(jié)果，從而使得無(wú)法有效分離出離群值和正常值，在檢測(cè)出越多的離群點(diǎn)的同時(shí)增大正常點(diǎn)的損失。當(dāng)樣本數(shù)據(jù)比較稀疏時(shí)，這種情況表現(xiàn)得更為突出。

因此，本文在借鑒K-means算法的基本思想的基礎(chǔ)上，引入空間數(shù)據(jù)的插值思想，盡量阻止稀疏數(shù)據(jù)在聚類的時(shí)候被合并，以提高離群點(diǎn)的檢測(cè)效果。該方法的基本思想如下所示：

(1)將所有樣本作為現(xiàn)有樣本集中的初始總體，隨機(jī)選取初始聚類中心完成一輪聚類。

(2)在聚類產(chǎn)生的簇中，依靠適應(yīng)度函數(shù)找出子簇中聚類效果最差的一個(gè)類。

(3)對(duì)上述類的樣本空間進(jìn)行插值，并進(jìn)入下一輪聚類。

(4)在最終的聚類結(jié)果中，與質(zhì)心的距離過(guò)大的樣本點(diǎn)被認(rèn)為是可能的理論點(diǎn)。

ODGA方法的偽代碼可描述如下：

輸入?yún)?shù)：k,path,column,n,Runtimes,Gtimes,geneticrate。

1.variarate=readConfiguration();

2.foreachi

3.Initializedata() ;// 初始化數(shù)據(jù)

4.scope=k_means(K,path,column,n);

5.forj

6.Genetic_Algorithm(scope,geneticrate,variarate,column,n); /*遺傳變異算法*/

7.j++;

8.endfor

9.k_means(k,path,column,n);

10.Statistic(k,i); // 統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果

11.i++;

12.endfor

1.functionk_means(k,path,column,n)

2.scope=Getscope(path,column)；/*scope是一個(gè)二維數(shù)組，其值為數(shù)據(jù)中每個(gè)屬性的取值范圍*/

3.central=Greatingrandomcentral(scope,k)；/*隨機(jī)獲得簇中心*/

4.whileIstabilized()do

5.classify(central,path)；//按照簇中心分簇

6.central=Findnewcentral()；//尋找簇中心

7.endwhile

8.returnscope

9.endfunction

4 基于遺傳算法的稀疏數(shù)據(jù)插值

由于遺傳算法是一種全局優(yōu)化算法，因此選擇遺傳算法對(duì)K-means聚類算法進(jìn)行優(yōu)化。與傳統(tǒng)的優(yōu)化方法(枚舉、啟發(fā)式等)相比，遺傳算法以生物進(jìn)化為原型，具有較好的收斂性，具有計(jì)算時(shí)間短、魯棒性強(qiáng)等優(yōu)點(diǎn)。將遺傳算法應(yīng)用于本文方法的最大優(yōu)點(diǎn)是在高維稀疏樣本集的離群點(diǎn)檢測(cè)中，彌補(bǔ)了數(shù)據(jù)信息不完整的不足。通過(guò)合理產(chǎn)生新數(shù)據(jù)樣本來(lái)增加數(shù)據(jù)密度，幫助找到更有利的質(zhì)心。

遺傳算法是一種模擬自然環(huán)境中生物遺傳和進(jìn)化過(guò)程的自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法將搜索的變量看作有限長(zhǎng)度的字符串，這些字符串被稱為染色體，這些字符串的單個(gè)元素或特征被稱為基因，基因的值被稱為等位基因[20]。在ODGA方法中，我們使用二進(jìn)制編碼方式，將每條數(shù)據(jù)視為一條染色體，每條染色體由L個(gè)基因組成，其中基因L表示屬性。在二進(jìn)制情況下，編碼染色體的每一位都被初始化為隨機(jī)的0或1。

本文使用了單點(diǎn)交叉與固定交叉概率pc，這意味著群體首先隨機(jī)配對(duì)，然后隨即設(shè)置交叉點(diǎn)，最后選擇配對(duì)的2條染色體之間的部分基因進(jìn)行交換。在單點(diǎn)交叉中，在對(duì)應(yīng)點(diǎn)處將2個(gè)“父母”切割一次，并且交換切割后的基因片段。突變是為了有助于在后代染色體中引入多樣性，通過(guò)修改一些基因引入新的遺傳結(jié)構(gòu)。在二進(jìn)制情況下可以通過(guò)以小概率反轉(zhuǎn)每個(gè)基因的值來(lái)完成簡(jiǎn)單的突變，通常突變概率pm由pm=1/L得到，其中L為染色體長(zhǎng)度。

構(gòu)造恰當(dāng)?shù)倪m應(yīng)度函數(shù)對(duì)優(yōu)化算法的性能具有重要的影響，本文使用類內(nèi)距離與類間距離的比值來(lái)定義適應(yīng)度。顯然，如果每個(gè)類之間的距離越大，同一類內(nèi)的距離越小，適應(yīng)度函數(shù)值越小，則聚類效果越好。

如果將每個(gè)集群總體的樣本集表示為xc，s0,s1,…,sm-1為集群xc中的數(shù)據(jù)。

每個(gè)簇內(nèi)的平均距離dc(x)表示為：

其中，c表示質(zhì)心，m表示集群樣本數(shù)。適應(yīng)度函數(shù)為：

其中，ki,j表示類間距,n表示簇的個(gè)數(shù)，

本文通過(guò)遺傳變異和聚類這2個(gè)階段的融合迭代，對(duì)原始數(shù)據(jù)的稀疏部分進(jìn)行了插值處理，利用這些新數(shù)據(jù)填充原始樣本集的稀疏部分，改善了稀疏數(shù)據(jù)在進(jìn)行聚類的時(shí)候容易被合并的問(wèn)題，在得到更好的聚類結(jié)果后再進(jìn)行離群點(diǎn)的檢測(cè)。該部分的偽代碼描述如下所示：

1.functionGenetic_Algorithm(scope,geneticrate,variation,column,Gafile,Tfile)

2.gedata[][]=readData(Gafile,geneticrate);

3.parents[2][]=nextParents(gedata);

4.an=getAttributionNumber();

5.whileparents≠nulldo

6.crosspoint=random(0,an)//an表示數(shù)據(jù)的維度

7.newdata[][]=regroup(parents,crosspoint);

8.writeData(newdata,Tfile);

9.parents[2][]=nextParents(gedata);

10.endwhile

11.whilei

12.variapoint=random(0,an);

13.varieddata[i][variapoint]=random(scope[0][variapoint],scope[1]variapoint);

14.writeData(newdata,Tfile);

15.parents[2][]=nextParents(gedata);

16.endwhile

17.endfunction

5 實(shí)驗(yàn)分析

為驗(yàn)證本文方法對(duì)高維稀疏數(shù)據(jù)中離群點(diǎn)的檢測(cè)效果，從UCI公共數(shù)據(jù)集[21]中選取了Lymphography、WBC、Ionosphere和Parkinson 4個(gè)數(shù)據(jù)集，對(duì)文中方法的有效性進(jìn)行了實(shí)驗(yàn)分析，同時(shí)與當(dāng)前的離群點(diǎn)檢測(cè)方法進(jìn)行了對(duì)比分析。需要說(shuō)明的是，由于當(dāng)前沒(méi)有公認(rèn)的離群點(diǎn)檢測(cè)的公共數(shù)據(jù)集，通常的做法是對(duì)機(jī)器學(xué)習(xí)數(shù)據(jù)集進(jìn)行采樣，將離群點(diǎn)數(shù)量控制在總數(shù)據(jù)量的5%左右。本實(shí)驗(yàn)最終選擇和構(gòu)造的離群點(diǎn)檢測(cè)的數(shù)據(jù)集如表1所示。

Table 1 Outlier detection sample dataset表1 離群點(diǎn)檢測(cè)樣本數(shù)據(jù)集構(gòu)成

以Lymphography數(shù)據(jù)集為例，共包含148個(gè)實(shí)例，每個(gè)實(shí)例由18個(gè)屬性描述。該數(shù)據(jù)集總共有4類標(biāo)簽，分別表示該樣本描述的個(gè)體的淋巴為正常、轉(zhuǎn)移、惡性和纖維化4種情況。與文獻(xiàn)[22]類似，最小的2個(gè)類中的實(shí)例數(shù)僅占數(shù)據(jù)集中實(shí)例數(shù)的4.05%，其中的樣本將被認(rèn)為是離群點(diǎn)，相應(yīng)地，其他2個(gè)類中的實(shí)例被認(rèn)為是正常樣本值。WBC、Ionosphere、Parkinson 3個(gè)數(shù)據(jù)集中的離群點(diǎn)標(biāo)注采用了相同的方法。

從某種角度來(lái)看，離群點(diǎn)檢測(cè)可被看作二分類問(wèn)題。如果將離群點(diǎn)看作是異常值，其余點(diǎn)則為正常值，檢測(cè)方法就可以作為一個(gè)分類器將所有數(shù)據(jù)分為異常和正常2類。而對(duì)于二分類問(wèn)題，樣本可以分為真陽(yáng)性(TP)、假陽(yáng)性(FP)、真陰性(TN)和假陰性(FN)，由此可得出表2所示的混淆矩陣?；诨煜仃嚳梢杂?jì)算分類器的準(zhǔn)確率，而準(zhǔn)確率越高，則認(rèn)為分類結(jié)果越好。因此，該指標(biāo)也可用于評(píng)價(jià)異常檢測(cè)方法的準(zhǔn)確性，其計(jì)算方法如下所示：

Table 2 Confusion matrix表2 混淆矩陣

ORC(Outlier Removal Clustering)[23]、FindCBLOF(Find Cluster-Based Local Outlier Factor)[23]和ODC(Outlier Detection based Clusering)[22]方法都是基于改進(jìn)的聚類算法的異常檢測(cè)方法，本文在Lymphography數(shù)據(jù)集上，對(duì)上述3種方法與本文方法從分類器的角度進(jìn)行了比較，如表3所示。從圖1可以看出，本文方法ODGA的準(zhǔn)確率為83.11%，而ODC、FindCBLOF、ORC 3種方法的準(zhǔn)確率分別為66.22%,63.51%,50%，ODGA的準(zhǔn)確率(Accuracy)明顯高于其他3種方法的。

Table 3 Test results of four approaches表3 4種方法的檢測(cè)結(jié)果

Figure 1 Comparison of accuracy圖1 準(zhǔn)確率對(duì)比

如果以TPrate表示陽(yáng)性樣本被分成陽(yáng)性樣本的比例，F(xiàn)Prate表示陰性樣本被分成陰性樣本的比例，則Euc可用以表示分類器在ROC圖上與理想分類器之間的距離，Euc值越小表明分類器越好。也就是說(shuō)，可以用Euc表示離群點(diǎn)檢測(cè)方法的檢測(cè)精確度(Precision)，其中：

圖2表明，與其他3種方法相比，ODGA方法的Euc值最小，并且明顯優(yōu)于其他3種方法，進(jìn)一步說(shuō)明本文方法具有更好的分類效果。

Figure 2 Comparison of classification precision圖2 分類精確度對(duì)比

由于ODGA基于K-means聚類，并引入了插值思想，來(lái)提高稀疏數(shù)據(jù)的離群點(diǎn)檢測(cè)效果，實(shí)驗(yàn)中，將ODGA與傳統(tǒng)的基于K-means的離群點(diǎn)檢測(cè)方法進(jìn)行了比對(duì)分析。另外ODC[21]是典型的基于改進(jìn)的K-means的離群點(diǎn)檢測(cè)方法。該方法首先將每個(gè)點(diǎn)分配給距離最近的質(zhì)心，如果檢測(cè)到離群值，則將其從數(shù)據(jù)集中刪除，并且當(dāng)作離群點(diǎn)另外存儲(chǔ)，接下來(lái)重新計(jì)算質(zhì)心，直到?jīng)]有樣本點(diǎn)從一個(gè)類移動(dòng)到另一個(gè)類中時(shí)，迭代停止。該方法界定離群點(diǎn)時(shí)采用了如下原則：當(dāng)樣本點(diǎn)與質(zhì)心之間的距離是該簇中所有樣本點(diǎn)與質(zhì)心距離平均值的固定倍數(shù)時(shí)，則認(rèn)為該點(diǎn)為離群點(diǎn)。因此，本文對(duì)ODGA方法與ODC方法進(jìn)行了進(jìn)一步的比對(duì)分析。

鑒于Lymphography數(shù)據(jù)集不需要采樣就符合我們對(duì)離群點(diǎn)占比全部數(shù)據(jù)的5%的要求，本部分實(shí)驗(yàn)中使用了Lymphography數(shù)據(jù)集。如圖3所示，橫坐標(biāo)表示檢測(cè)后被標(biāo)記為離群點(diǎn)的所有點(diǎn)的數(shù)量，縱坐標(biāo)表示召回率?？梢钥吹?，當(dāng)K-means方法找到所有真正的離群點(diǎn)(召回率為100%)時(shí)，共標(biāo)記出110個(gè)離群點(diǎn)，其中誤判104個(gè)點(diǎn)；ODC方法共標(biāo)記28個(gè)，誤判22個(gè)。ODGA方法一共將13個(gè)樣本點(diǎn)標(biāo)記為離群點(diǎn)，其中只有7個(gè)點(diǎn)被誤判。從這個(gè)角度來(lái)看，ODGA方法的檢測(cè)準(zhǔn)確率明顯優(yōu)于基于K-means的離群點(diǎn)檢測(cè)方法和ODC方法的。

Figure 3 Recall comparison of three algorithm圖3 3種方法的召回率比較

由于K-means算法初始聚類中心是隨機(jī)選取的，因此每個(gè)算法的初始質(zhì)心都會(huì)發(fā)生變化。我們將ODC、ORC和FindCBLOF應(yīng)用于Lymphography數(shù)據(jù)集10次，初始簇中心均不同，且都是在數(shù)據(jù)集中隨機(jī)選取，實(shí)驗(yàn)表明這些離群點(diǎn)基本全都位于每個(gè)簇中距離質(zhì)心較遠(yuǎn)的位置。如圖4所示，ORC方法[23]在被認(rèn)為是離群點(diǎn)的40個(gè)點(diǎn)中準(zhǔn)確找到6個(gè)實(shí)際的離群點(diǎn)；FindCBLOF方法[23]在被標(biāo)記為離群點(diǎn)的30個(gè)點(diǎn)中找到6個(gè)真正的離群點(diǎn)；ODC方法[22]在標(biāo)記的28個(gè)點(diǎn)中找到6個(gè)真實(shí)的離群點(diǎn)。然而，ODGA方法僅標(biāo)記了13條數(shù)據(jù)為離群點(diǎn)，并包含有全部的6個(gè)離群點(diǎn)。由此可以得到結(jié)論，與其他3種方法相比，本文方法不僅達(dá)到了100%的召回率(查找所有稀疏類實(shí)例)，而且最大限度地縮小了標(biāo)識(shí)離群點(diǎn)的范圍。

Figure 4 Comparison of outlier detection approaches on Lymphography dataset圖4 在Lymphography數(shù)據(jù)集上離群點(diǎn)檢測(cè)方法的比較

為了觀察在面對(duì)不同數(shù)據(jù)集時(shí)，本文方法是否還能保持較好的檢測(cè)效率。針對(duì)表1中的WBC、Ionosphere和Parkinson 3個(gè)數(shù)據(jù)集，對(duì)本文方法進(jìn)行了進(jìn)一步的測(cè)試。從圖5可以看出，在WBC數(shù)據(jù)集上，被標(biāo)記為離群點(diǎn)的46條數(shù)據(jù)中涵蓋所有正確的離群點(diǎn)，Ionosphere數(shù)據(jù)集和Parkinson數(shù)據(jù)集上本文方法同樣均表現(xiàn)良好。

Figure 5 Test ODGA on multiple datasets圖5 在多個(gè)數(shù)據(jù)集上測(cè)試ODGA

綜合上述實(shí)驗(yàn)分析，通過(guò)利用遺傳算法對(duì)原始樣本數(shù)據(jù)集的稀疏部分進(jìn)行插值處理，解決了稀疏數(shù)據(jù)在聚類時(shí)容易被合并的問(wèn)題，明顯改善了聚類效果，從而提高了離群點(diǎn)檢測(cè)的準(zhǔn)確率和精確度。

6 結(jié)束語(yǔ)

本文探討了一種適用于高維稀疏數(shù)據(jù)集的離群點(diǎn)檢測(cè)方法。該方法借鑒生物學(xué)中種群繁衍的規(guī)律，引入插值思想，解決了K-means聚類中稀疏數(shù)據(jù)容易被合并的問(wèn)題。實(shí)驗(yàn)表明，該方法能夠有效檢測(cè)出離群點(diǎn)。

在將來(lái)的工作中，我們將進(jìn)一步探索檢測(cè)到的離群點(diǎn)的生成機(jī)制。