徐曉丹

(浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004)

0 引 言

異常點挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個重要分支，其目的是在數(shù)據(jù)集中找出那些明顯偏離常規(guī)數(shù)據(jù)對象的點，這些點往往表現(xiàn)為由不同的機制產(chǎn)生[1].目前對異常點沒有統(tǒng)一的定義，一般是指那些行為模式明顯區(qū)別于普通數(shù)據(jù)的點.在某些文獻[1-4]中,異常點也被稱為離群點、不一致點(discordant object)、例外點(exception)、 差錯點(aberration)、特色點(peculiarity)和驚奇點(surprise)等.不同的術(shù)語反映了在不同的情形下，研究者對待這類數(shù)據(jù)的不同方式.

隨著數(shù)據(jù)挖掘需求的深入，那些包含重要信息的異常點正受到越來越多的重視.實際上，在很多應用中，人們更關(guān)注的是那一小部分表現(xiàn)異常的數(shù)據(jù)，因為這些數(shù)據(jù)中往往包含著重要信息.例如，異常網(wǎng)絡(luò)傳輸行為預示著黑客或病毒入侵，異常的地質(zhì)活動有可能是地震或海嘯的前兆，異常的天氣數(shù)據(jù)有可能預示著極端天氣的發(fā)生等等.這些偏離常規(guī)的數(shù)據(jù)，可能正是某種規(guī)律的真實反映，往往比正常數(shù)據(jù)更有價值.因此，對異常點的檢測研究在信用卡欺詐、網(wǎng)絡(luò)入侵檢測、疾病診斷、突發(fā)事件檢測、時空數(shù)據(jù)異常等領(lǐng)域已成為數(shù)據(jù)分析的主要對象，越來越彰顯其價值[4-9].

傳統(tǒng)的異常點檢測算法面對高維復雜數(shù)據(jù)時效率明顯降低，為了解決這個問題，出現(xiàn)了很多新的算法，這些算法能有效地處理高維數(shù)據(jù).這些最新算法主要包括基于近鄰的方法、基于子空間的方法和基于集成的方法.

基于近鄰的方法主要是根據(jù)一個點在其近鄰的排序值來獲得異常度值,這些近鄰包括k近鄰[10]、反向近鄰[11]和共享近鄰[12].在k值的選擇上，文獻[13]提出了一種基于迭代隨機采樣策略的排序算法，該方法定義了一個可觀測因子(observability factor,OF)來衡量一個點的異常值，為了確定最佳的k值，該方法還定義了OF的信息熵，使OF的熵值達到最大的k值，就是最佳的k值，因為此時OF值的區(qū)分性最大，即每個點的Outlier的排序能力最大.基于近鄰方法都是在所有的維度空間中進行計算，然而隨著維度的不斷增加，很多異?，F(xiàn)象只在由少部分維度組成的子空間中體現(xiàn)，如果在所有維度中進行計算，那么那些不相關(guān)的維度就會干擾計算結(jié)果，影響算法的效率.因此，查找和異常特性相關(guān)的有效子空間，是高維空間異常點檢測的一個關(guān)鍵,也是當前研究的一個熱點.

基于子空間的異常點檢測方法主要可以歸納為兩類：一是基于稀疏子空間查找方法[14-16]；二是相關(guān)子空間查找方法[17-23].基于稀疏子空間方法根據(jù)用戶給定的稀疏系數(shù)的閾值，將整個數(shù)據(jù)集映射到稀疏子空間中，那些在子空間中出現(xiàn)的數(shù)據(jù)被認定為異常點.基于相關(guān)子空間方法的基本原理是找到和異常特性相關(guān)的子空間，在這些子空間中計算點的異常值.基于相關(guān)子空間的異常點檢測算法是一種精確查找策略，為了得到算法最優(yōu)需要遍歷所有可能的子空間，就不可避免地存在子空間組合爆炸問題.隨機采樣子空間的方法不需要遍歷所有的子空間，但由于采樣的不完整性可能會造成一些異常點不能被識別出來.

基于集成的方法是對現(xiàn)有的這些算法進行有效集成.目前，在合適的子空間上集成異常點算法越來越受到研究者的關(guān)注[24].隨機子空間集成方法[25]的原理是每次隨機選擇d維數(shù)據(jù)生成子空間，在子空間內(nèi)使用LOF算法得到異常點值，將這些異常點值合成后得到最終的結(jié)果.該方法存在的一個問題是對算法的選擇順序較為敏感,導致算法的穩(wěn)定性得不到保障.文獻[26]提出的方法不是采樣特征維度，而是通過隨機采樣數(shù)據(jù)集中的數(shù)據(jù)對點進行局部密度估計，以減少集成算法的時間開銷.為了提高算法的準確率并降低時間開銷，文獻[27]提出了一種基于特征集成和數(shù)據(jù)采樣的異常點檢測方法，該算法是對文獻[25-26]提出方法的綜合：使用文獻[25]提出的Feature Bagging獲得集成算法中每次迭代的子空間，在計算異常點時使用文獻[26]的子采樣Subsample方法獲取計算所需要的數(shù)據(jù).此算法中每次迭代使用隨機采樣特征得到子空間的方法提供了集成算法部件的多樣性，在獲取一個點的局部區(qū)域時添加Subsample方法可以有效提高算法的精度并節(jié)省計算時間.

為了更好地分析上述算法的特性，本文對上述算法進行了深入的分析，相較于以往文獻[3-9]中只提供部分算法比較而言，本文通過一系列實驗，使用不同評價指標提供了較為全面、系統(tǒng)的算法比較，同時，本文采用的10種算法是上述這3類最新算法的典型代表，更能綜合地分析算法的性能，以期為新算法的研究提供一定的參考.

1 實驗結(jié)果及分析

本文在ELKI[28]提供的平臺上對10種代表性算法在8個數(shù)據(jù)集上進行測試比較，這些算法包括基于統(tǒng)計的方法GUMM[29]、k近鄰相關(guān)算法(kNN,kNNW,ODIN,LOF,FASTABOD,LoOP)、基于子空間的方法(COP，SOD)和基于集成的算法(HiCS).本實驗采用的數(shù)據(jù)集來源于UCI數(shù)據(jù)集，異常點的預處理采用文獻[30]的方法.表1列出了實驗中使用的數(shù)據(jù)集，每個數(shù)據(jù)集包括數(shù)據(jù)集名稱、數(shù)據(jù)大小、異常點的個數(shù)、屬性值及異常點的類別.例如,SpamBase數(shù)據(jù)集中包含4 601個數(shù)據(jù)，其中異常點的個數(shù)有1 813 個，實驗中把non-spam這一類作為異常點處理.

表1 實驗用數(shù)據(jù)集

精度是衡量異常點檢測算法的一個常用指標.圖1列出了10種算法在8個數(shù)據(jù)集上的精度r-precision[31](下文用r表示)的比較結(jié)果.

圖1 不同數(shù)據(jù)集上精度r值比較

從圖1可得到，基于近鄰的算法在各個數(shù)據(jù)集中的結(jié)果較為穩(wěn)定，在Arrhythmia,Cardiotography,SpamBase和Ann-thyriod這4個數(shù)據(jù)集中精度r的值為最優(yōu).而HiCS算法和FASTABOD算法在不同的數(shù)據(jù)集上差異較大,例如,HiCS算法在WDBC和Waveform中效果最好，在PenDigits,KDDCup99和Ann-thyroid 這3個數(shù)據(jù)集中效率最低；對FASTABOD算法來說，在 PenDigits數(shù)據(jù)集上得到了最優(yōu)值，而在SpamBase 和 Ann-thyroid 上的值最低，其部分原因在于這些數(shù)據(jù)集中異常點的個數(shù)相對于正常點來說比例太低，從而導致r值偏低.

另一個值得注意的是，在PenDigits數(shù)據(jù)集中，F(xiàn)ASTABOD算法要顯著高于其他算法，其原因在于該數(shù)據(jù)集的屬性描述的是0～9的數(shù)字信息，這些屬性是相關(guān)聯(lián)的，因此,采用余弦相似度計算的FASTABOD算法能夠得到較好的效果，而對于WDBC 和 Waveform等包含較多不相關(guān)的屬性的數(shù)據(jù)集來說，基于子空間的方法SOD及子空間集成方法HiCS表現(xiàn)突出.

基于高斯的異常點檢測算法主要依賴于數(shù)據(jù)的分布，因此,在WDBC數(shù)據(jù)集上獲得了較好的效果，而在Arrhythmia,Ann-thyriod等數(shù)據(jù)分布無規(guī)律性的數(shù)據(jù)集上效率較低.

除了精度值r外，AUC(area under the corresponding curve)[8]是評價異常點檢測算法的另一個常用指標,它計算的是ROC(receiver operating characteristic)曲線的面積，ROC曲線的每個點是不同概率下真正類率(true positive rate)和負正類率(false positive rate)的比值.圖2給出了FASTABOD,kNN,kNNW,ODIN,LOF,LoOP和HiCS這些算法在AUC上的值，同時為了分析k值對算法的影響，給出了k從3變化到50的曲線.

從圖2可以得到，kNN,kNNW算法在各個數(shù)據(jù)集上的AUC值普遍較好，而HiCS算法在各個數(shù)據(jù)集上的差異較大.例如,在WDBC和Waveform數(shù)據(jù)集上，HiCS的值要明顯優(yōu)于其他算法，而在Arrhythmia數(shù)據(jù)集上效率最低.值得注意的是，F(xiàn)ASTABOD算法在SpamBase數(shù)據(jù)集上的AUC值異常低，幾乎為0，部分原因是數(shù)據(jù)集中異常點個數(shù)比例偏小，還有部分原因和數(shù)據(jù)集本身的特點相關(guān)：SpamBase數(shù)據(jù)集描述的是電子郵件文檔中單詞和字符出現(xiàn)的頻率，這些數(shù)字化的頻率信息幾乎沒有組的屬性，并且本質(zhì)上沒有相似的性質(zhì).因此,FASTABOD算法不適合這樣的數(shù)據(jù)集，因為它是通過余弦來計算對象的相似性.

為了分析k值對算法的影響，圖2給出了k值取3到50時，各個基于k近鄰算法的AUC值比較結(jié)果.由于HiCS在高維數(shù)據(jù)和較大數(shù)據(jù)集上運行較慢，所以該算法在Ann-thyriod和KDDCup99中的運行結(jié)果在圖2中不顯示，F(xiàn)ASTABOD算法在數(shù)據(jù)集KDDCup99運算中由于內(nèi)存不足問題終止了計算，其計算結(jié)果也沒有在圖2中顯示.

從圖2可以看出，受k值影響最小的是FASTABOD算法，它在這些數(shù)據(jù)集中的值隨k值的變化非常??；受k值影響最大的是HiCS算法.就基于距離的算法而言，kNNW由于進行了加權(quán)調(diào)整比kNN更加穩(wěn)定，而對基于密度的算法來說，采用局部密度統(tǒng)計的算法LoOP受k值的影響比LOF算法要小得多.

同時可以觀察到的另一個現(xiàn)象是，所有的算法在KDDCup99 和 PenDigits這2個數(shù)據(jù)集上的AUC值變化幅度明顯要高于其他數(shù)據(jù)集.這是由于這2個數(shù)據(jù)的異常點比例值要明顯小于其他數(shù)據(jù)集(其中KDDCup99為0.4%，PenDigits為0.2%).同理，對SpamBase(39.4%的異常點)和Arrhythin (45.7%的異常點)這2個數(shù)據(jù)集來說，由于包含的異常點比例較高，因此,這2個算法受k值的影響相對小一些.

算法效率是衡量異常點檢測方法實際應用的一個重要方面，表2給出了這10種算法在不同數(shù)據(jù)集上的運行時間.由于KDDCup99數(shù)據(jù)集包含6萬多條數(shù)據(jù)，因此,其運行時間明顯大于其他數(shù)據(jù)集，本次不列入表2進行比較.從表2可以看出，基于近鄰的方法(kNN,kNNW，ODIN,LOF,LoOP)的效率明顯高于其他算法，另外，HiCS算法在每一個數(shù)據(jù)集上的時間復雜度都高于其他算法，這是因為算法本身需要遍歷所有可能的子空間.

圖2 不同數(shù)據(jù)集上AUC值比較(k從3到50)

2 結(jié) 語

表2 異常點檢測算法在各個數(shù)據(jù)集上的運行時間

在以上分析中給出了最新的高維數(shù)據(jù)異常點檢測方法的實驗分析比較及算法特性分析.在異常點檢測領(lǐng)域，面對日益復雜的數(shù)據(jù)，新的問題不斷涌現(xiàn)，主要體現(xiàn)在以下幾個方面：

1)基于近鄰的異常點檢測算法通常對鄰居數(shù)目k值的選擇較為敏感，如何找到最合適的k值是基于近鄰算法的一個難題.

2)異常點(離群值)往往表現(xiàn)出局部的異常行為.然而，在高維空間中對特征進行局部相關(guān)性分析并非一件易事，同時，如何準確測量相關(guān)性便成為更具挑戰(zhàn)性的問題.

3)集成算法是提高算法效率的有效途徑，而高維數(shù)據(jù)中部分維度與異常點的檢測任務(wù)無關(guān)，因此在子空間上作特征的集成是一種較為有效的集成方法.利用窮舉法獲取的子空間雖然精度高但存在組合爆炸的問題，使用隨機子空間的方法，如何保證隨機子空間方法的精度是目前面臨的一個問題；此外，集成方法中一個關(guān)鍵是如何針對異常特性選擇準確率高的算法，如何來評價這些算法的優(yōu)劣，對這些問題的深入研究值得期待.

4)由于異常點在數(shù)據(jù)集中所占的比例非常低，缺乏評價的統(tǒng)一標準，因此,如何對異常點檢測算法進行有效的評價也是一個懸而未決的問題.

異常點挖掘作為數(shù)據(jù)挖掘領(lǐng)域的一個熱門分支已在越來越多的領(lǐng)域展開研究.本文針對當前異常點挖掘所面臨的數(shù)據(jù)高維和復雜問題展開深入分析，通過實驗詳細分析了當前最新的相關(guān)技術(shù)的特性，并對當前面臨的主要問題及進一步研究方向進行了有效探討.

參考文獻：

[1]Chandola V,Banerjee A,Kumar V.Anomaly detection:A survey[J].ACM Computing Surveys,2009,41(3):1-58.

[2]Hodge V,Austin J.A survey of outlier detection methodologies[J].Artificial Intelligence Review,2004,22(2):85-126.

[3]Zhang Y,Meratnia N,Havinga P.Outlier detection techniques for wireless sensor networks:A survey[J].IEEE Communications Surveys and Tutorials,2010,12(2):159-170.

[4]Gogoi P,Bhattacharyya D K,Borah B,et al.A survey of outlier detection methods in network anomaly identification[J].Computer Journal,2011,54(4):570-588.

[5]Kaur G,Saxena V,Gupta J P.Anomaly detection in network traffic and role of wavelets[C]//International Conference on Computer Engineering and Technology.Chengdu:IEEE,2010:46-51.

[6]Phua C,Lee V,Smith K,et al.A comprehensive survey of data mining-based fraud detection research[J].Artificial Intelligence Review,2010,21(3):60-74.

[7]Gupta M,Gao J,Aggarwal C C,et al.Outlier detection for temporal data:A survey[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(9):2250-2267.

[8]Zimek A,Schubert E,Kriegel H P.A survey on unsupervised outlier detection in high-dimensional numerical data[J].Statistical Analysis and Data Mining the Asa Data Science Journal,2012,5(5):363-387.

[9]Aggarwal C C.Outlier analysis[M].New York:Springer,2013:50-89.

[10]Huang H,Mehrotra K,Mohan C K.Rank-based outlier detection[J].Journal of Statistical Computation and Simulation,2013,83(3):518-531.

[11]Radovanovic M,Nanopoulos A,Ivanovic M.Reverse nearest neighbors in unsupervised distance-based outlier detection[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1369-1382.

[12]Pan Z M,Chen Y L.Local outlier detection algorithm based on shared reversek-nearest neighbor[J].Computer Simulation,2013,30(2):269-273.

[13]Ha J,Seok S,Lee J S.A precise ranking method for outlier detection[J].Information Sciences and International Journal,2015,324(S):88-107.

[14] Zhang J F,Zhang S L,Chang K H,et al.An outlier mining algorithm based on constrained concept lattice[J].International Journal of Systems Science,2014,45(5):1170-1179.

[15]Aggarwal C C,Yu S.An effective and efficient algorithm for high-dimensional outlier detection[J].The VLDB Journal,2005,14(2):211-221.

[16]Zhang J,Jiang Y,Chang K H,et al.A concept lattice based outlier mining method in low-dimensional subspaces[J].Pattern Recognition Letter,2009,30(15):1434-1439.

[17]Dutta J,Banerjee B,Reddy C K.RODS:Rarity based outlier detection in a sparse coding framework[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(2):483-495.

[18]Kriegel H P,Kroger P,Schubert E,et al.Outlier detection in axis-parallel subspaces of high dimensional data[C]// Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Berlin:Springer-Verlag,2009:831-838.

[19]Emmanuel M,Schiffer M,Seidl T.Adaptive outlierness for subspace outlier ranking[C]//ACM Conference on Information and Knowledge Management.Toronto:ACM, 2010:1629-1632.

[20]Emmanuel M,Schiffer M,Seidl T.Statistical selection of relevant subspace projections for outlier ranking[C]//Proceedings of the 27th International Conference on Data Engineering.Hannover:IEEE Computer Society,2011:434-445.

[21]Keller F,Emmanuel M,Bohm K.HiCS:High contrast subspaces for density-based outlier ranking[C]//Proceedings of the 28th International Conference on Data Engineering.Arlington:IEEE,2012:1037-1048.

[22]Stein B V,Leeuwen M V,Back T.Local subspace-based outlier detection using global neighbourhoods[C]//International Conference on Big Data.Washington:IEEE,2016:43-53.

[23]Zhang J,Yu X,Li Y,et al.A relevant subspace based contextual outlier mining algorithm[J].Knowledge-Based Systems,2016,99(S):1-9.

[24]Aggarwal C C.Outlier ensembles[J].Acm Sigkdd Explorations Newsletter,2017,14(2):49.

[25]Lazarevic A,Kumar V.Feature bagging for outlier detection[C]//Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining.Chicago:ACM,2005:157-166.

[26]Zimek A,Gaudet M,Campello R J G B.Subsampling for efficient and effective unsupervised outlier detection ensembles[C]//Proceedings of the 19th International Conference on Knowledge Discovery and Data Mining.Chicago:ACM,2013:428-436.

[27]Pasillas-Diaz J R,Ratte S.Bagged subspaces for unsupervised outlier detection[J].Computational Intelligence,2016,33(3):507-523.

[28]Achtert E,Kriegel H P,Reichert L,et al.ELKI data mining[EB/OL].(2010-03-01)[2010-08-10].https://elki-project.github.io/releases/.

[29]Eskin E.Anomaly detection over noisy data using learned probability distributions[C]//Proceedings of the 17th International Conference on Machine Learning.San Francisco:ACM,2000:255-262.

[30]Campos G O,Zimek A,Campello R J,et al.On the evaluation of unsupervised outlier detection:Measures,datasets,and an empirical study[J].Data Mining and Knowledge Discovery,2016,30(4):891-927.

[31]Craswell N.Encyclopedia of database systems[M].Berlin:Springer,2009:2453-2455.