基于插值的高維稀疏數(shù)據(jù)離群點檢測方法*

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

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

1 引言

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

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

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

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

2 相關工作

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

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

非監(jiān)督離群點檢測方法通常不需要樣本標注，與基于監(jiān)督學習的離群點檢測方法相比，其應用條件更為寬松。常見的一種思路是通過參數(shù)化或非參數(shù)化方法估計訓練樣本的密度模型，并設置相應的密度閾值，通過判斷局部的密度來確定離群點[9]。當前的無監(jiān)督離群點檢測方法中，比較有代表性的包括基于相對密度估計的檢測方法、基于模型的檢測方法和基于支撐域的檢測方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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)計實驗結(jié)果

11.i++;

12.endfor

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

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

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

4.whileIstabilized()do

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

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

7.endwhile

8.returnscope

9.endfunction

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

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

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

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

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

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

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

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

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

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

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ù)據(jù)中離群點的檢測效果，從UCI公共數(shù)據(jù)集[21]中選取了Lymphography、WBC、Ionosphere和Parkinson 4個數(shù)據(jù)集，對文中方法的有效性進行了實驗分析，同時與當前的離群點檢測方法進行了對比分析。需要說明的是，由于當前沒有公認的離群點檢測的公共數(shù)據(jù)集，通常的做法是對機器學習數(shù)據(jù)集進行采樣，將離群點數(shù)量控制在總數(shù)據(jù)量的5%左右。本實驗最終選擇和構(gòu)造的離群點檢測的數(shù)據(jù)集如表1所示。

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

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

從某種角度來看，離群點檢測可被看作二分類問題。如果將離群點看作是異常值，其余點則為正常值，檢測方法就可以作為一個分類器將所有數(shù)據(jù)分為異常和正常2類。而對于二分類問題，樣本可以分為真陽性(TP)、假陽性(FP)、真陰性(TN)和假陰性(FN)，由此可得出表2所示的混淆矩陣?；诨煜仃嚳梢杂嬎惴诸惼鞯臏蚀_率，而準確率越高，則認為分類結(jié)果越好。因此，該指標也可用于評價異常檢測方法的準確性，其計算方法如下所示：

Table 2 Confusion matrix表2 混淆矩陣

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

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

Figure 1 Comparison of accuracy圖1 準確率對比

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

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

Figure 2 Comparison of classification precision圖2 分類精確度對比

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

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

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

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

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

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

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

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

6 結(jié)束語

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

在將來的工作中，我們將進一步探索檢測到的離群點的生成機制。