離群點(diǎn)檢測算法研究

（晉中學(xué)院信息技術(shù)與工程學(xué)院晉中030619）

離群點(diǎn)檢測算法研究

李俊麗蘆彩林

（晉中學(xué)院信息技術(shù)與工程學(xué)院晉中030619）

離群檢測作為數(shù)據(jù)挖掘中一項(xiàng)重要內(nèi)容，已經(jīng)應(yīng)用于許多領(lǐng)域，因此引起廣泛關(guān)注。介紹了傳統(tǒng)的離群點(diǎn)檢測算法的分類，針對傳統(tǒng)算法無法適用于新興數(shù)據(jù)模型的問題，首先詳細(xì)討論了高維數(shù)據(jù)的離群點(diǎn)檢測算法，并提出了離群組合技術(shù)的方法以解決與高維數(shù)據(jù)相關(guān)聯(lián)的問題，其次描述了不確定數(shù)據(jù)和數(shù)據(jù)流離群檢測算法，最后對離群檢測算法的性能評價進(jìn)行了討論，并指出了進(jìn)一步的研究方向。

高維數(shù)據(jù)；離群檢測；不確定數(shù)據(jù)；數(shù)據(jù)流

Class NumberTP311

1 引言

傳統(tǒng)離群檢測算法大致可以分為四類：基于分布的、基于距離的、基于密度的和基于聚類的。隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)的收集更快也更容易，從而導(dǎo)致更復(fù)雜的數(shù)據(jù)形式出現(xiàn)了。

高維數(shù)據(jù)的特征完全不同于傳統(tǒng)數(shù)據(jù)，傳統(tǒng)離群檢測算法都不能很有效地應(yīng)用于高維數(shù)據(jù)。在高維數(shù)據(jù)中，數(shù)據(jù)變得稀疏，數(shù)據(jù)集中的對象幾乎是等距離彼此分開，數(shù)據(jù)在高維空間中的表現(xiàn)相對于低維空間有很大的差異。而且由于數(shù)據(jù)集變得更多樣化，在高維數(shù)據(jù)中許多屬性通常是不相關(guān)的，這些不相關(guān)的屬性能夠混淆離群算法。

除了高維數(shù)據(jù)，還出現(xiàn)了不確定性數(shù)據(jù)、流數(shù)據(jù)等新興數(shù)據(jù)模型，同時也出現(xiàn)了一些新的離群檢測算法，因此關(guān)于新型數(shù)據(jù)領(lǐng)域的離群檢測算法的研究更有意義。

2 高維數(shù)據(jù)離群檢測算法

高維數(shù)據(jù)離群檢測是近年來數(shù)據(jù)挖掘的一個較為活躍的研究領(lǐng)域。目前，高維數(shù)據(jù)離群檢測算法己在文本挖掘、生物信息學(xué)、信息安全等領(lǐng)域得到廣泛應(yīng)用。根據(jù)高維數(shù)據(jù)離群檢測所采用的基本思想可以分為基于降維的、基于子空間的和離群聯(lián)合技術(shù)。

2.1 降維

高維數(shù)據(jù)降維技術(shù)主要通過從數(shù)據(jù)集中提取重要特征來實(shí)現(xiàn)，其中主要包括特征變換和特征選擇兩種。

特征變換通常用于高維數(shù)據(jù)集，這種方式通過創(chuàng)建屬性的線性組合發(fā)現(xiàn)潛在的結(jié)構(gòu)。文獻(xiàn)［1］利用Hilbert空間填充曲線將數(shù)據(jù)集線性化，文獻(xiàn)［2］利用小波變換從原始數(shù)據(jù)集中消除聚類，從而達(dá)到發(fā)現(xiàn)離群點(diǎn)的目的。文獻(xiàn)［3］使用主成分分析方法獲得能代表數(shù)據(jù)的δ維屬性的d個最正交向量（屬性），投影變化后再進(jìn)行挖掘。文獻(xiàn)［4］采用分形的思想得到非整數(shù)值的分?jǐn)?shù)維數(shù)，為進(jìn)一步降維提供參考。

特征選擇也是一種常用的減少數(shù)據(jù)集維數(shù)的技術(shù)，它試圖發(fā)現(xiàn)一個數(shù)據(jù)集最相關(guān)的屬性。這種方法不用變換，而是從維度中啟發(fā)式地選取一部分維，刪除不相關(guān)或冗余的屬性（維），目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能接近使用所有屬性得到的原分布。這種方法避免了挖掘結(jié)果難以解釋的問題，并且由于屬性數(shù)目的減少，使得模式更易于理解。基于啟發(fā)式方法的技術(shù)包括逐步向前選擇、逐步向后刪除、向前選擇和向后刪除的結(jié)合和決策樹歸納［5］等。

2.2 子空間離群檢測方法

子空間離群檢測方法不是在全維空間中尋找離群點(diǎn)，而是在相關(guān)的子空間中。要確定哪些子空間是相關(guān)的也開發(fā)了很多技術(shù)，下面介紹一些重要的算法。

文獻(xiàn)［6］提出了一個動態(tài)子空間搜索系統(tǒng)，稱為HOS-Miner。該算法使用固定的閾值來識別異常值，對于給定的數(shù)據(jù)點(diǎn)，能有效確定其離群子空間。HOS-Miner存在的問題是在不同維度的子空間中離群點(diǎn)得分無法比較。文獻(xiàn)［7］提出OutRank（outlier ranking）方法，通過引入新的離群點(diǎn)得分函數(shù)評估子空間聚類分析確定的其余部分?jǐn)?shù)據(jù)對象的偏差。OutRank存在的問題是離群值作為基于密度的聚類所產(chǎn)生的副產(chǎn)物可導(dǎo)致一大組的離群值。文獻(xiàn)［8］提出軸平行子空間，文獻(xiàn)［9］提出在多個子空間中同時評估每個對象的偏差，文獻(xiàn)［10］提出一個處理局部屬性相關(guān)的多維空間，文獻(xiàn)［11］提出只適合基于密度離檢測的高對比度子空間等。

盡管基于子空間的離群檢測技術(shù)很多，但還是局限在特定數(shù)據(jù)類型或特定背景環(huán)境下。下面介紹以離群組合技術(shù)這樣一種方式以減少算法的復(fù)雜性和使計(jì)算成本更低。

2.3 離群組合技術(shù)

在一般情況下，組合技術(shù)有潛力解決與高維數(shù)據(jù)相關(guān)聯(lián)的問題，組合分析方法通常是用于降低模型的具體的數(shù)據(jù)集或數(shù)據(jù)局部的依賴性，這極大地增加了數(shù)據(jù)挖掘過程的魯棒性，組合技術(shù)常用于聚類和分類中。但在某些情況下，組合分析技術(shù)已經(jīng)隱含在許多離群分析算法中。

文獻(xiàn)［12］可以被認(rèn)為是順序組合的例子，順序組合是一個給定的算法或算法集被順序地應(yīng)用于分析基本數(shù)據(jù)的修改或算法的具體選擇，從而使算法將來的應(yīng)用能被前面的應(yīng)用影響。最終結(jié)果是一個加權(quán)的組合或離群值的最后一個應(yīng)用程序的最終結(jié)果分析算法。在獨(dú)立組合中，不同算法或相同算法的不同實(shí)例被應(yīng)用于完整數(shù)據(jù)或部分?jǐn)?shù)據(jù)中。關(guān)于數(shù)據(jù)和算法的選擇應(yīng)用是從這些不同的算法執(zhí)行得到的獨(dú)立結(jié)果。不同的算法執(zhí)行的結(jié)果組合在一起，以獲得更健壯的離群值。例如，文獻(xiàn)［13］從底層數(shù)據(jù)得到的示例子空間以確定每一個獨(dú)立執(zhí)行得到的離群值。文獻(xiàn)［14］嘗試將構(gòu)建在相同的數(shù)據(jù)集上不同模型的離群得分結(jié)合起來，這在許多經(jīng)典離群分析算法中已經(jīng)做了很多，這種模式的主要挑戰(zhàn)是，不同模型的離群得分彼此之間通常不能直接進(jìn)行比較。數(shù)據(jù)為中心的組合對數(shù)據(jù)的不同部分和不同功能進(jìn)行分析，數(shù)據(jù)是抽樣的隨機(jī)子空間，在這些預(yù)測子空間確定離群值，最后確定的離群值為來自不同的子空間離群值的組合。

這些方法很顯然并不全面，但它們代表了組合算法中重要的一部分，組合分析已有效用于高維離群檢測，其中經(jīng)常使用數(shù)據(jù)的多個子空間以發(fā)現(xiàn)離群值。這些情況表明，正確使用組合分析技術(shù)對算法的改進(jìn)有明顯提高。

3 離群點(diǎn)檢測研究熱點(diǎn)

3.1 不確定數(shù)據(jù)離群檢測

近年來，由于越來越多地使用傳感器、無線射頻識別（RFID）、GPS和類似的設(shè)備進(jìn)行數(shù)據(jù)收集，不確定數(shù)據(jù)變得很常見。不確定性的原因包括測量的局限性，包括噪聲、電源電壓不一致和傳輸延遲或數(shù)據(jù)丟失。為了管理、查詢或挖掘這樣的數(shù)據(jù)，需要考慮數(shù)據(jù)的不確定性。傳統(tǒng)的離群檢測算法在確定性數(shù)據(jù)中已經(jīng)應(yīng)用很廣，但在新興的不確定數(shù)據(jù)領(lǐng)域卻是一項(xiàng)新的研究課題。發(fā)現(xiàn)不確定數(shù)據(jù)中的離群對象是很困難的，因此，很多研究者開始開發(fā)新的數(shù)據(jù)處理和挖掘技術(shù)來探尋不確定數(shù)據(jù)中的離群點(diǎn)，不確定數(shù)據(jù)中的離群檢測同樣也會遭遇到隨著維度增大而難以標(biāo)識離群點(diǎn)的難題。

針對不確定數(shù)據(jù)離群檢測，Aggarwal等首次提出了基于子空間的不確定性數(shù)據(jù)挖掘技術(shù)［15］，該算法假設(shè)在低密度異常子空間出現(xiàn)離群值，并在指定對象的子空間計(jì)算每個點(diǎn)的密度，然后判斷是否為離群點(diǎn)。文獻(xiàn)［16］從一個全面的模型考慮不確定對象和它們的實(shí)例，一個不確定的對象包含一些固有的屬性和一組由概率密度分布建模的實(shí)例。通過假設(shè)具有相似屬性的不確定對象往往有相似的實(shí)例來學(xué)習(xí)對每個不確定對象使用具有相似屬性的對象實(shí)例。因此，通過和正常實(shí)例進(jìn)行比較可以檢測到異常實(shí)例，進(jìn)一步可以檢測到大多數(shù)實(shí)例是離群值的離群對象。技術(shù)上使用貝葉斯推理算法來解決這個問題，并開發(fā)了一個近似算法和一個過濾算法來加快計(jì)算速度。文獻(xiàn)［17］實(shí)現(xiàn)了一個使用基于密度抽樣方法的不確定對象的離群檢測方法，雖然密度抽樣法是一個很好理解和相對簡單的離群檢測技術(shù)，但其應(yīng)用在不確定數(shù)據(jù)上會產(chǎn)生很高的計(jì)算工作量。該算法使用一個廉價的GPU（圖形處理器）大大降低了運(yùn)行時間。文獻(xiàn)［18］提出基于距離的top-k不確定數(shù)據(jù)對象離群檢測方法，基于距離的離群檢測最基本的方法是利用嵌套循環(huán)，這種方法的代價是非常大的，因?yàn)閮蓚€不確定的對象之間的距離函數(shù)花費(fèi)很大。而該方法中，一個不確定對象通過高斯分布的概率密度函數(shù)建模，數(shù)據(jù)的離群點(diǎn)檢測算法只需要考慮一小部分?jǐn)?shù)據(jù)，因此數(shù)據(jù)集對象能快速確定候選對象的top-k離群點(diǎn)。

隨著更復(fù)雜的不確定數(shù)據(jù)模型的出現(xiàn)，未來需要對不確定數(shù)據(jù)做進(jìn)一步研究以便于找到快速、高效的離群檢測算法。

3.2 數(shù)據(jù)流離群點(diǎn)檢測

最近，數(shù)據(jù)流挖掘的研究得到越來越多的關(guān)注。數(shù)據(jù)流是信息技術(shù)快速發(fā)展出現(xiàn)的一類新的數(shù)據(jù)模型，數(shù)據(jù)量大、不可預(yù)測、連續(xù)快速和短暫易逝是此類數(shù)據(jù)的特點(diǎn)。很多傳統(tǒng)數(shù)據(jù)挖掘技術(shù)無法推廣到數(shù)據(jù)流挖掘上，因此，數(shù)據(jù)流離群檢測是數(shù)據(jù)挖掘的一個新興課題，是一個非常具有挑戰(zhàn)性的問題。這是因?yàn)閿?shù)據(jù)流不能被多次掃描，而且新概念也在不斷發(fā)展。

為了解決數(shù)據(jù)流的異常檢測問題，Yang等提出一個新的快速的離群檢測算法［19］。該方法基于動態(tài)網(wǎng)格分區(qū)數(shù)據(jù)空間，過濾處于密集區(qū)域的大量主體數(shù)據(jù)，大大降低了算法應(yīng)考慮對象的大小。在稀疏區(qū)域的候選離群點(diǎn)，采用近似方法計(jì)算其離群度，具有高離群度的數(shù)據(jù)作為離群點(diǎn)輸出。周曉云等給出一種快速數(shù)據(jù)流離群點(diǎn)檢測算法［20］，該算法通過動態(tài)發(fā)現(xiàn)和維護(hù)頻繁模式來計(jì)算離群度，能夠有效地處理高維類別屬性數(shù)據(jù)流，并可進(jìn)一步擴(kuò)展到數(shù)值屬性和混合屬性數(shù)據(jù)流。Elahi等人提出一個基于聚類的方法［21］，把流分成塊并使用k均值算法使用固定數(shù)量的簇聚類每個塊。通過使用前一個數(shù)據(jù)流塊的平均值與當(dāng)前數(shù)據(jù)流塊的平均值以決定數(shù)據(jù)流對象中更好的離群值。Cao等提出了一種新的基于反向最近鄰居的數(shù)據(jù)流異常檢測算法SODRNN［22］，在該算法中插入或刪除的更新只需要掃描一次當(dāng)前窗口，從而提高了效率。

數(shù)據(jù)流異常檢測的主要目的是在合理時間準(zhǔn)確找到數(shù)據(jù)流異常值。現(xiàn)有的離群點(diǎn)檢測算法不適用于動態(tài)數(shù)據(jù)流，并不能找到有效的異常數(shù)據(jù)。由于實(shí)時檢測和動態(tài)調(diào)整的要求以及現(xiàn)有的數(shù)據(jù)流離群檢測算法的不適用性，下一步的研究要能夠?qū)崟r發(fā)現(xiàn)數(shù)據(jù)中的異常數(shù)據(jù)流并動態(tài)調(diào)整檢測結(jié)果，使算法具有更好的可擴(kuò)展性。

3.3 離群檢測方法性能評價

離群檢測目前正專注于新方法的研究和改進(jìn)，但同時也忽略了一個問題，那就是由不同的方法所提供的離群得分的性能評價?，F(xiàn)有的離群檢測方法經(jīng)常采用精確度進(jìn)行評價，即包含k個離群點(diǎn)的數(shù)據(jù)集中前k個結(jié)果的真正正確率，這是評價結(jié)果的一個很單純的方式。

評價的另一種常用方法是ROC曲線（receiver operating characteristic curve）和AUC曲線（ROC曲線下的面積），這種方法基本上失去了離群得分信息。

但是離群檢測需要接受的“基本事實(shí)”可能是不完整的，而且現(xiàn)實(shí)世界的數(shù)據(jù)可能包括合理的離群只是還不知道或者被認(rèn)為是沒有意義的，當(dāng)比較或者組合不同子空間的結(jié)果后，有意義的離群得分比離群排名包含更多的信息。因此，離群檢測方法評價要更注重以下幾個方面：

1）已知的（或估計(jì)的）異常值權(quán)重更高。

2）允許非二進(jìn)制的基本事實(shí)。

3）通過組合（不同的）得分向量提高離群檢測，這個方向的研究從長遠(yuǎn)看將標(biāo)準(zhǔn)化離群得分。

4 結(jié)語

離群檢測在現(xiàn)代生活中已經(jīng)得到廣泛應(yīng)用，離群檢測許多應(yīng)用領(lǐng)域的數(shù)據(jù)具有很高的維度，而維度災(zāi)難一直是處理高維數(shù)據(jù)時面臨的一個關(guān)鍵問題。為了解決這個問題，本文從高維數(shù)據(jù)離群檢測所采用的基本思想出發(fā)，將它們分為基于降維的、基于子空間的和離群聯(lián)合技術(shù)。但由于現(xiàn)有的一些檢測算法自身的各種缺陷，所以還需要進(jìn)一步的研究和改進(jìn)。文中還就目前離群檢測研究的熱點(diǎn)——不確定數(shù)據(jù)和數(shù)據(jù)流的離群檢測以及離群檢測性能評價進(jìn)行了討論，并指出了下一步研究的方向。

［1］Angiulli F，Basta S，Pizzuti C.Distance-based detection and prediction of outliers［J］.Knowledge&Data Engineering IEEE Transactions on，2006，18（2）：145-160.

［2］Yu D，Sheikholeslami G，Zhang A.FindOut：Finding Outliers in Very Large Datasets［J］.Knowledge&Information Systems，2002，4（4）：387-412.

［3］Dutta H，Giannella C，Borne K D，et al.Distributed Top-K Outlier Detection from Astronomy Catalogs using the DEMAC System［C］//Proceedings of the Seventh SIAM International Conference on Data Mining，April 26-28，2007，Minneapolis，Minnesota，USA.2007.

［4］孫金花，胡健，李向陽.基于分形理論的離群點(diǎn)檢測［J］.計(jì)算機(jī)工程，2011，37（3）：33-35. SUN Jinhua，HU Jian，LI Xiangyang.Outlier Detection Based on Fractal Theory［J］.Computer Engineering，2011，37（3）：33-35.

［5］Jiawei Han，Micheline kamber，Jian pei.數(shù)據(jù)挖掘：概念與技術(shù)，第3版［M］.北京：機(jī)械工業(yè)出版社，2012. Jiawei Han，Micheline kamber，Jian pei.Data Mining Concepts and Techniques（Third Edition）［M］.Beijing：China Machine Press，2012.

［6］Zhang J，Lou M，Ling T W，et al.HOS-Miner：A System for Detecting Outlying Subspaces of High-dimensional Data［C］//Thirtieth International Conference on Very Large Data Bases.VLDB Endowment，2004：1265-1268.

［7］E.Müller，I.Assent，U.Steinhausen，and T.Seidl.Out-Rank：ranking outliers in high dimensional data［C］//Proceedings of the 24th International Conference on Data Engineering（ICDE）Workshop on Ranking in Databases（DBRank），Cancun，Mexico，2008：600-603.

［8］Kriegel H P，Ger P，Schubert E，et al.Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data［C］// Advances in Knowledge Discovery and Data Mining，Pacific-Asia Conference，PAKDD 2009，Bangkok，Thailand，April 27-30，2009，Proceedings，2009：831-838.

［9］Müller E，Schiffer M，Seidl T.Adaptive outlierness for subspace outlier ranking［C］//International Conference on Information and Knowledge Management，2010：1629-1632.

［10］Nguyen H V，Gopalkrishnan V，Assent I.An Unbiased Distance-BasedOutlierDetectionApproachfor High-Dimensional Data［C］//Database Systems for Advanced Applications.Springer Berlin Heidelberg，2011：138-152.

［11］Keller F，Muller E，Bohm K.HiCS：High Contrast Subspaces for Density-Based Outlier Ranking［J］.IEEE，2012，41（4）：1037-1048.

［12］Yoav Freund，Robert E Schapire.A Decision-Theoretic Generalization of On-Line Learning and An Application to Boosting［C］//European Conference on Computational Learning Theory，Springer Berlin Heidelberg，1995：119-139.

［13］Lazarevic A，Kumar V.Feature bagging for outlier detection.［C］//In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2005：157-166.

［14］Papadimitriou S，Kitagawa H，Gibbons P B，et al.LOCI：Fast Outlier Detection Using the Local Correlation Integral［J］.Proc Icde，2003：315-326.

［15］Aggarwal C C，Yu P S.Outlier Detection with Uncertain Data.［C］//Proceedings of the SIAM International Conference on Data Mining，SDM 2008，April 24-26，2008，Atlanta，Georgia，USA，2008：483-493.

［16］Jiang B，Pei J.Outlier detection on uncertain data：Objects，instances，and inferences［J］.IEEE，2011，6791（4）：422-433.

［17］Matsumoto T，Hung E.Accelerating Outlier Detection with Uncertain Data Using Graphics Processors［C］//Pacific-Asia Conference on Advances in knowledge Discovery and Data Mining，Springer Berlin Heidelberg，2012：169-180.

［18］Shaikh S A，Kitagawa H.Top-k Outlier Detection from Uncertain Data［J］.International Journal of Automation &Computing，2014，11（2）：128-142.

［19］楊宜東，孫志揮，朱玉全，等.基于動態(tài)網(wǎng)格的數(shù)據(jù)流離群點(diǎn)快速檢測算法［J］.軟件學(xué)報(bào)，2006，17（8）：1796-1803.

YANG Yidong，SUN Zhihui，ZHU Yuquan，et al.A Fast Outlier Detection Algorithm for Data Streams Based on Dynamic Grids［J］.Journal of Software，2006，17（8）：1796-1803.

［20］周曉云，孫志揮，張柏禮，等.高維類別屬性數(shù)據(jù)流離群點(diǎn)快速檢測算法［J］.軟件學(xué)報(bào)，2007，18（4）：933-942.

ZHOU Xiaoyun，SUN Zhihui，ZHANG Baili，et al.A Fast Outlier Detection Algorithm for High Dimensional Categorical Data Streams［J］.Journal of Software，2007，18（4）：933-942.

［21］Elahi M，Li K，Nisar W，et al.Efficient Clustering-Based Outlier Detection Algorithm for Dynamic Data Stream.［C］//International Conference on Fuzzy Systems and Knowledge Discovery，F(xiàn)skd 2008，18-20 October 2008，Jinan，Shandong，China，Proceedings，Volume.2008：298-304.

［22］Cao L，Liu X，Zhou T，et al.A Data Stream Outlier Delection Algorithm Based On Reverse K Nearest Neighbors［C］//International Symposium on Computational Intelligence and Design.IEEE，2010：236-239.

Research on Algorithms for Outlier Detection

LI JunliLU Cailin
（School of Information Technology and Engineering，Jinzhong College，Jinzhong030619）

Outlier detection as an important item of data mining has been used in many areas thus caused wide public concern. This paper introduces traditional classification of outlier detection algorithm，aiming at the problem that traditional algorithm is not suitable for new data models，the paper firstly discusses the outlier detection methods of high-dimensional data detailed，and points out outlier ensembles for solving the problems associated with high-dimensional data.Secondly，outlier detection algorithms of uncertain data and data streams are described，and finally the evaluation of the outlier detection methods are discussed，and the direction for further research is pointed out.

high-dimensional data，outlier detection，uncertain data，data streams

TP311

10.3969/j.issn.1672-9722.2017.06.007

2016年12月18日，

2017年1月23日

國家青年科學(xué)基金項(xiàng)目（編號：61602335）資助。

李俊麗，女，博士研究生，講師，研究方向：數(shù)據(jù)挖掘。蘆彩林，男，碩士，副教授，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)。