基于插值的高維稀疏數據離群點檢測方法*

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

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

1 引言

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

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

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

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

2 相關工作

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

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

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

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

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

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

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

3 基于插值的稀疏數據離群點檢測

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

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

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

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

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

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

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

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

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

輸入參數：k,path,column,n,Runtimes,Gtimes,geneticrate。

1.variarate=readConfiguration();

2.foreachi

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

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); // 統計實驗結果

11.i++;

12.endfor

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

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

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

4.whileIstabilized()do

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

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

7.endwhile

8.returnscope

9.endfunction

4 基于遺傳算法的稀疏數據插值

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

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

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

構造恰當的適應度函數對優化算法的性能具有重要的影響，本文使用類內距離與類間距離的比值來定義適應度。顯然，如果每個類之間的距離越大，同一類內的距離越小，適應度函數值越小，則聚類效果越好。

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

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

其中，c表示質心，m表示集群樣本數。適應度函數為：

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

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

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表示數據的維度

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 實驗分析

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

Table 1 Outlier detection sample dataset表1 離群點檢測樣本數據集構成

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

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

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數據集上，對上述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種方法的檢測結果

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

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

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

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

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

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

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

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

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

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

Figure 5 Test ODGA on multiple datasets圖5 在多個數據集上測試ODGA

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

6 結束語

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

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