離群點挖掘研究

（中國石油大學 自動化研究所， 北京 102249）



摘 要：隨著人們對欺詐檢測、網絡入侵、故障診斷等問題的關注，離群點挖掘研究日益受到重視。在充分調研國內外離群點挖掘研究成果的基礎上，介紹了數據庫領域離群點挖掘的研究進展，并概要地總結和比較了已有的各種離群點挖掘方法，展望了離群點挖掘研究的未來發展方向和面臨的挑戰。

關鍵詞：離群點; 數據挖掘; 局部離群點; 高維數據; 數據流

中圖分類號：TP311.13; TP391 文獻標志碼：A

文章編號：10013695(2009)01003407



Research on outlier mining

XU Xiang， LIU Jianwei， LUO Xionglin



(Research Institute of Automation， China University of Petroleum， Beijing 102249， China)



Abstract:The problem of outlier mining attracts more and more interests in research when the research fields of fraud detection， intrusion detection， fault diagnosis and so on receive wide attentions. This paper presented a survey for the research results of outlier mining at home and abroad， and based on this survey， introduced the research process of outlier mining in the areas of database. It also presented a summary of the current state of the art of these techniques， a discussion on future research topics， and the challenges of the outlier mining.

Key words：outlier; data mining; local outlier; highdimensional data; data stream



一直以來，人們都比較重視數據集中的離群數據，通常認為這些數據改變了數據集的原有信息或數據產生機理。因此，發現離群點并減少其對數據分析的影響是一項很有意義的工作。然而，一個人的噪聲可能是另一個人的信號[1]；在欺詐檢測、故障診斷、網絡入侵等領域的應用中，罕見事件通常比常規事件更有吸引力。簡單地刪除離群點的做法可能導致一些重要信息的丟失，因此，在這些領域都十分注重離群點的研究。目前，離群點問題的研究是信息科學中一個較活躍的分支，在數據挖掘研究領域也備受關注。

1 離群點的定義與相關概念

1.1 離群點的定義

在不同的應用領域，離群點有不同的定義。一個經常被引用的定義首先由D.Hawkins提出。

定義1 離群點。一個離群點是這樣一個觀測值，它與其他觀測值偏離特別多，讓人們懷疑它是由不同的機理產生[2]。

圖1給出了幾種常見的數據集中離群點的例子。其中，圖1（a）聚類數據集中的點a和點b；（b）序列數據集中的幾個最大偏離和（c）三維數據集中突起的巖石都可以被認為是數據集中的離群點。

產生離群點的原因[3]很多，最主要有三種：a）數據來自不同的類。舉例來說，進行信用卡欺詐的人（即離群數據），與那些合法使用信用卡的人相比，屬于信用卡用戶的一個不同的類。b）數據的固有變化。觀測數據在樣本總體中發生了變化，這種變化是樣本總體自然發生的，并從側面反映了數據集的分布特征。c）數據測量和采集錯誤。人為操作錯誤、測量儀器的缺陷或故障也可能導致部分數據成為離群點。

根據不同的分類標準，可將離群點分成不同的類別[4]。圖2形象地給出了離群點的一種分類情況。圖2中，坐標軸表示分類標準；刻度表示相應標準下的分類情況。這樣的分類盡管不是很完備，但從一定程度上反映了數據集中離群數據的多樣性。因此，離群點的檢測是件很復雜的工作，需要采用有效的策略和算法。

1.2 離群點挖掘的概念

數據挖掘就是從大量的數據中自動/半自動地獲得有用信息的過程。隨著數據挖掘技術的不斷發展，其在金融、證券、通信、零售等行業的安全管理、客戶關系管理系統中得到了廣泛的應用。

數據挖掘的任務可以被分成四類[1，5，6]，即依賴性檢測、類型識別、類型描述和異常/離群點檢測。前三類任務對應著數據集中適用于絕大多數對象的模式。數據挖掘中大多數的研究，如關聯規則挖掘[7]、分類[8]、數據聚類[9，10]等都屬于這三類。相反地，第四類任務關注數據對象中一個非常小的部分，通常被忽略或被當成噪聲處理掉了。實際上，從知識發現的角度來看，罕見事件經常比普通事件更有價值。例如在信用卡欺詐檢測中，人們不關心那些正常的信用卡使用記錄，恰恰是異常的行為如異常的交易金額、交易時間和地點等，這些才是所關注的。所以，研究離群點挖掘方法是很有意義的一項工作。

離群點挖掘可描述如下[11]：給定一個有n個數據點或對象的數據集和期望的離群點數目k，找出與數據集中其余數據顯著不同的、異常的或不一致的前k個對象。離群點挖掘問題可以被看做兩個子問題：a）定義在給定的數據集中，什么樣的數據可以被認為是不一致的；b）找到一個有效的方法來挖掘所定義的離群點。

離群點挖掘的目標[12]是找出那些與數據集中大多數對象有非常不同的行為的罕見數據。研究離群點的異常行為可以幫助揭開隱藏的有價值的知識，輔助決策者作出決定，獲得利益或改進服務質量。因此，離群點挖掘是數據挖掘的一個重要分支，有著很廣泛的應用，包括信用卡欺詐檢測、發現電子商務中的犯罪行為、天氣預報和市場營銷等。

2 離群點挖掘研究現狀

離群點通常被當做聚類挖掘的副產物，所以許多聚類挖掘算法都將其作為噪聲刪除[9，10]。近年來，隨著人們對離群點挖掘重要性的認識不斷加深，以及其越來越廣泛的應用，離群點挖掘日益受到重視，成為數據挖掘領域的研究熱點之一。

2.1 離群點挖掘方法

先前的離群點挖掘方法大致可以分為以下幾種類型：a)基于統計學的方法，包括基于分布的方法、基于深度的方法。b）基于距離的方法，包括基于索引的算法、嵌套—循環算法、基于單元的算法。c）基于密度的方法。d）基于聚類的方法。e）基于偏離的方法，包括序列異常技術、OLAP數據立方體技術。這些方法之間的相互關系可以形象地用圖3表示。當然各種方法之間也有一定的重疊，這里不作詳細分析。

2.1.1 基于統計學的離群點挖掘方法

許多現有的離群點挖掘研究都集中在統計學領域[2，12~15]。Barnett給出了統計學領域的離群點定義。

定義2 離群點。一個離群點是這樣的數據點，基于某種度量，該數據點與數據集中其他的數據點有著明顯的不同[12]。

1）基于分布的離群點挖掘方法

統計學上基于分布的方法首先對給定的數據集假設一個分布或概率模型（如正態或泊松分布），然后使用不一致檢測辨識出關于這個模型的離群點。這個檢測要求事先知道數據集的參數（如假設的數據分布）、分布的參數（如均值和方差）和期望的離群點數目[12]。

一個統計學的不一致檢測需要檢查兩個假設，即工作假設和替代假設。一個工作假設H是這樣一個命題：有n個對象的整個數據集都來自一個初始的分布模型F，即

H∶oi∈F；i=1，2，…，n

如果沒有統計上顯著的證據支持拒絕工作假設，那么工作假設就被保留下來。不一致檢測校驗一個對象oi關于分布F是否顯著的大（或小）。已經有很多不同的檢驗統計量被提出來作為一個不一致檢測使用，這取決于數據的可利用的信息。假設一些統計量T已經被選來進行不一致檢測，且關于對象oi的統計量值為vi，然后構造出T的分布。估算出顯著性概率SP(vi)=Prob(T＞vi)。如果SP(vi)是充分小的，那么對象oi是不一致的，工作假設被拒絕。同時，一個聲明oi來自另一個分布模型G的替代假設H被采用，它說明數據對象oi來自另一個分布模型，所以該對象是一個離群點。結果在很大程度上取決于選擇的模型F，因為oi可能在一種模型下是離群點，而在另一種模型下是一個完全正確的值[11]。

在確定檢測的推翻假設的幾率方面，替代分布是非常重要的，也就是當oi真是一個離群點時，工作假設被拒絕的概率。替代分布主要有三種：固有替代分布、混合替代分布和滑動替代分布[11]。

有兩種基本類型的方法來檢測離群點：a）塊（block）方法。在這種情形下，所有可疑的對象或者都被視為離群點，或者都被認為是一致的。b）順序（sequential）方法。由里及外（inside out）的方法是其中的一個例子。其主要思想是首先檢測最不可能是離群點的對象。如果它被發現是一個離群點，那么所有更極端的對象也都被認為是離群點；否則，接著檢測下一個最不可能是離群點的對象，并重復上面的過程。這個方法比塊方法更有效率[11]。

統計學領域基于分布的離群點挖掘方法很多。Yamanishi等人[14]使用一個高斯混合模型來描述常規的行為，并且每個數據都被給定一個分數，這個分數基于數據點與模型的相異程度。現在已經有了一些對于這個方法的改進方法，其中有一個方法結合監督學習的方法來獲得離群點的一般模式[15]。這些統計學的方法都依賴于數據分布、分布的參數（均值和方差）、期望的離群點數目、期望的離群點類型。可是，這些方法都遭遇到兩個嚴重的問題：a）絕大多數不一致檢驗都是相對于單變量（也就是單屬性）的。這個局限使得這些方法不適合多維數據庫。b）它們都是基于分布的。在絕大多數情況下，不知道一個特殊的屬性符合一個正態分布、一個泊松分布等，則必須執行大量的測試來找到一個匹配這些屬性的分布[1]。為了改進這些不足之處，發展出了基于計算統計學的方法，被稱為基于深度的方法。

2）基于深度的離群點挖掘方法

基于某些深度的定義（例如，如果k是為了發現點P而必須要被移除掉的數據點的最小數目，那么P的深度就是k[16]），數據對象被組織在數據空間的層中。基于深度的方法的理論根據是：相比較于較深的層，較淺的層中更可能含有離群點。剝離（peeling）和等深線（depth contour）是在深度研究方面的兩個重要概念[17，18]。這些基于深度的方法避免了分布匹配的問題，并且理論上允許處理多維的數據對象。可是，實際上，k維層的計算依賴于k維凸包（convex hull）的計算。因為計算一個k維凸包的復雜性的下限是Ω（N「k/2），所以基于深度的方法對于超過四維的大數據集來說是不現實的。事實上，現有的基于深度的方法僅僅在k≤2時能夠提供可接受的性能[18]。

2.1.2 基于距離的離群點挖掘方法

基于距離的離群點概念和挖掘方法首先由Knorr和Ng提出，該方法能夠有效地處理五維以上的大數據集。下面介紹基于距離的離群點挖掘的概念及相關算法。

定義3 基于距離的離群點DB(p，d)。如果數據集中至少有p（分數，∈[0，1]）部分的對象與對象o的距離大于d，那么o就是一個基于距離的離群點，即DB(p，d)[1，5，6，19]。

DB(p，d)統一了其他關于離群點的定義[19]，所以又被稱為一致離群點（unified outliers）。例如，有一個正態分布數據集T，如果假設數據集中一個對象t與均值μ的偏差大于或等于3倍方差σ，則認為t就是一個離群點，那么這類離群點可以用DB(0.998，0.13σ)來定義[19]。

直觀而言，可將基于距離的離群點看做是那些沒有足夠多鄰居的對象。這里的鄰居是基于與給定對象間的距離來定義的。目前，研究人員已經提出了許多高效的基于距離的離群點挖掘算法，代表性的是：

a)基于索引的算法。給定一個數據集，基于索引的算法[6]使用多維的索引結構，如R樹或kd樹來搜索每個對象o的在半徑d之內的鄰居。假設M是一個離群點的d鄰域內的對象的最大數目。一旦對象o的M+1個鄰居被搜索到，則o就不是一個離群點。這種算法最差情況下的復雜性為O(n2k)。其中：n是數據集中對象的數目；k是維數。基于索引的算法隨著k的增加能夠很好地擴展。但即使這樣，這個復雜性估計也只考慮了搜索時間，而索引的建立是一個巨大的潛在花費，這通常致使基于索引的算法失去競爭力。

b)嵌套—循環算法。它與基于索引的算法有相同的計算復雜性，但避免了建立索引結構，且盡量地最小化I/O數目。它將存儲緩沖器空間分為兩半，并將數據集分成若干個邏輯塊；通過精心地選擇塊被裝載到每一半中的順序，能夠獲得較好的I/O效率。

Ghoting等人[20]對嵌套—循環算法進行了擴展，提出了一種適用于高維數據集的二段算法RBRP。該算法的第一階段使用一個如同k均值的聚類算法將數據集劃分成若干個小的聚類，每個聚類都可以看成是一個桶（bin）；第二階段使用擴展的嵌套—循環算法找出已經被劃分成若干個桶的數據集中的離群點。Bay等人[21]提出了一個改進的嵌套—循環算法，結合隨機化和一個簡單的修剪規則，在大型的真實數據集中有接近線性的時間性能，但是I/O花費卻是二次的。Tao Yufei等人[22]進一步改進了Bay等人的算法，提出了SNIF算法，改進了I/O效率，通過掃描數據庫最多兩次就能找出所有的離群點。

c)基于單元的算法[1，5，6，23]。對于內存常駐數據集，為了避免O(n2)的計算復雜性，發展出基于單元（cell）的算法[6，23]。其復雜性是O(ck+n)。其中：c是一個取決于單元數目的常量；k是維數。在這個方法中，數據空間被劃分成若干個邊長等于d/2k的單元。每個單元有圍繞在它周圍的兩層：第一層有一個單元厚；第二層有｜2k-1｜（趨于最近的整數）個單元厚。圖4為點數據的cell結構示意圖。這種算法在單元到單元的基礎上計算離群點，而不是在對象到對象的基礎上。對于一個給定的單元，它存儲三個計數：單元中的對象數目、單元中和第一層中的對象數目、單元中和兩個層中的對象數目。假設這些計數分別為cell_count、cell_+_1_layer_count和cell_+_2_layers_count，M是可能出現在一個離群點的d維鄰域內的對象的最大數目。

(a)在當前單元中的一個對象o，僅在cell_+_1_layer_count小于或等于M時，才被認為是一個離群點。如果這個條件不能保證，那么在這個單元中的所有對象就可以被移除掉，無須進一步研究，因為它們不可能是離群點。

(b)如果cell_+_2_layers_count小于或等于M，那么單元中的所有對象都認為是離群點；否則，如果這個數目大于M，那么可能單元中有一些對象是離群點。為了檢測出這些離群點，使用對象到對象的處理，對于單元中的每個對象o，檢查o的第二層中的對象。對于單元中的對象，僅僅那些在它們的鄰域中有不超過M個點的對象是離群點。一個對象的d鄰域由對象所在的單元、所有的第一層和一部分第二層所組成。

這種算法相對于前面算法的一個變化是關于n呈線性的，并保證掃描數據庫不超過三次。它適用于較大的內存常駐數據集，但是不能很好地測量高維數據庫。

基于距離的離群點挖掘方法對相對高維的數據集有較好的挖掘效果，但也存在兩個主要問題：a）距離函數和相關參數的選擇。基于距離的離群點挖掘方法需要用戶設置參數p和d，尋找這些參數的合適設置可能涉及到許多實驗并可能導致試錯。b）它只能發現全局（global）離群點而丟失局部（local）離群點。

2.1.3 基于密度的局部離群點挖掘方法

統計學上的和基于距離的離群點挖掘方法都是從全局的角度考慮給定的數據集，但是遇到不同的密度分布時，這些方法就不適用了。這里首先介紹局部離群點的概念。如圖5所示的二維數據集，C1和C2是數據集中兩個密度不同的聚類，可以直觀地看出C2比C1稠密。依照Hawkins的定義，o1和o2都應該是離群點，而聚類C1和C2中的對象不是離群點；相反地，依據基于距離的離群點定義，僅有o1可能是一個合理的DB(p，d)離群點。因為對于C1中的每個對象q，q與它的最近鄰之間的距離大于o2與C2之間的距離（即d(o2，C2)），實際上可以發現沒有合適的p和d值能使o2是一個DB(p，d)離群點而在C1中的對象卻不是離群點。從本例可以看出，基于距離的離群點在數據集中聚類密度存在不同時會出現問題。為了解決這個問題，Breunig等人[24]提出了基于密度的局部離群點挖掘方法，從而保證離群點o1和o2都能被發現。

如果一個對象相對于它的局部鄰域，特別是對于鄰域的密度是離群的，那么它就是一個局部離群點。根據這個觀點，圖4中的o2相對于C2的密度是一個局部離群點。o1也是一個離群點，而C1中沒有對象會被錯認為是離群點。這構成了基于密度的局部離群點挖掘的基礎。這個方法的另一個關鍵思想是：不同于先前的方法，它不確切地指明一個對象是否為離群點，而是評估一個對象可能是離群點的程度。這個離群的程度利用一個對象的局部離群因數（LOF）來計算。這個程度取決于對象相對于周圍的鄰域是多么的孤立。這個方法既可以檢測全局離群點，也可以檢測局部離群點。

基于密度的局部離群點的確切定義以及局部離群因數的計算方法比較復雜[24]，其基本思想來源于基于密度的聚類算法[9，25~27]。根據定義，如果一個對象p不是局部離群點，那么LOF(p)就近似等于1；如果p是一個局部離群點的可能性越大，LOF(p)的值也就越大。因此，決定一個點p是否為局部離群點就基于LOF(p)的計算。

Tang等人[28]介紹了一個基于連接的離群點因數（COF）方案，提高了LOF方案的效率。Jin等人[29]提出了一種LOF算法的改進算法，給定一個n，僅尋找數據集中前n個局部離群點（topn local outliers），避免計算絕大多數對象的LOF值。Papadimitriou等人[30]使用局部相關積分（LOCI）方法，進一步擴展了基于密度的方法。

基于密度的局部離群點挖掘方法即使在數據有不同密度的區域也能適用。在算法的時間復雜性方面，對于低維數據，可通過使用特殊的數據結構減少到O(n log n)；但在通常情況下，它與基于距離的方法類似，也有O(n2)的時間復雜性（n為對象的數目）。而且，相關參數的選擇也是一個難題。

2.1.4 基于聚類的離群點挖掘方法

聚類分析找到緊密相關的對象的群，而離群點挖掘是找出與其他對象不緊密相關的對象。通常離群點都是聚類挖掘算法的副產物，但是通過對聚類算法進行一定的改進，也可以應用于離群點挖掘。基于聚類的離群點定義[3]如下：

定義4 如果一個對象不嚴格地屬于任何聚類，那么這個對象就是一個基于聚類的離群點。

一個使用聚類來進行離群點挖掘的方法是將那些遠離其他聚類的小聚類作為離群點丟棄。這個方法能夠使用任何聚類技術，但是要求知道最小聚類的尺寸和一個小聚類與其他聚類之間距離的閾值。通常，這個過程被簡化成丟棄所有小于最小尺寸的聚類。這個方法對選擇的聚類數是很敏感的。Jiang等人[31]提出的兩階段聚類算法就使用這種思想。離群點被定義為遠離絕大多數點的小聚類。首先將數據點劃分成若干聚類，每個聚類中的點要么都是離群點，要么都不是。換句話說，當包含在同一個聚類中的點不是足夠靠近時，聚類就可能被分成兩個更小的聚類。在劃分完數據點之后，可以很容易地看出尋找離群聚類的時間復雜性減少了。這是因為相似的點被合并到相同的聚類中，并且被處理的是聚類而不是點。在算法的第一階段中，通過使用一個直觀推斷：“如果一個新的輸入模式足夠地遠離所有聚類的中心，那么就指定它為一個新的聚類中心”，來修改傳統的kMeans算法；然后在算法的第二階段中，構建階段中聚類的一個最小掃描樹（MST），并作為森林的一個成員，從森林中移除一個樹的最長的邊，并用兩個新生成的子樹代替原來的樹。小的聚類有較少數目的節點的樹，被選中并認為是離群點。此外，重復地從森林中移除最長的邊直到樹的數目足夠多。He等人[32]提出了基于聚類的局部離群點的概念。

一些聚類算法有線性的或接近線性的時間和空間復雜性，因此基于這樣的算法的一個離群點挖掘技術也是高效的。但是，通過這種算法生成的離群點的質量取決于生成的聚類的質量，而每個聚類算法僅適用于某一種特定類型的數據，因此需要謹慎地選取聚類算法。

2.1.5 基于偏離的離群點挖掘方法

基于偏離的離群點挖掘不使用統計測試或基于距離的度量來辨識異常對象，而是通過檢測一組對象的主要特征來辨識離群點，過分偏離給定描述的對象被認為是離群點[11]。基于偏離的離群點挖掘方法主要有兩種：

a)序列異常技術[33]。該技術模仿了人類可以從一系列類似的對象中識別出異常對象的行為。它使用隱含的數據冗余。給定一個包含n個對象的數據集D，建立一個子集合序列{D1，D2，…，Dm}。其中2≤m≤n，并有Dj-1Dj，這里DjD。評估序列中子集之間的差異度。這個技術介紹了如下幾個關鍵術語：

(a)異常集 就是偏離的集或離群點。它被定義為對象的最小子集，這個子集的移除導致數據集中剩余部分的差異度有最大量的減少。

(b)差異度函數 這個函數不要求對象間的一個度量距離。它可以是任何函數，只要滿足條件，即給定一個對象集，如果某個對象與另一個對象是相似的，那么就返回一個較低的值。對象之間的差異度越大，函數返回值也越大。

(c)平滑因子 對于序列中每個子集，這個函數都會被計算。它估價了從原始對象集中移除子集后，差異度能減少多少。這個值通過集的基數來測量。平滑因子最大的子集就是序列中的異常集。

這個算法選擇一個子集的序列來進行分析。對于每個子集，它確定這個子集與序列中前一個子集的差異度。為了避免輸入順序對結果的任何可能的影響，處理過程可以重復若干次，每一次都有子集的一個不同的隨機順序。在所有的迭代中，有最大平滑因子值的子集就是異常集。

b)OLAP數據立方體技術[34]。一個進行偏離檢測的OLAP方法使用數據立方體來辨識高維數據中的異常區域。為了提高效率，偏離檢測過程可以與立方體計算過程重疊進行。該方法是一種探索驅動的方法，預先計算的指示數據異常的度量，被用來在數據集合計算的所有層次上指導用戶進行數據分析。如果數據立方體中的一個單元值與基于一個統計模型的期望值顯著不同，那么這個單元值就被認為是一個異常。這個方法采用如背景顏色那樣的可視化提示來反映每個單元的異常程度。用戶可以選擇對標志為異常的單元進行向下鉆取。一個單元的度量值可能反映發生在該立方體上的更細節或更低層次上的異常，因為這些異常在當前層次上可能是不可見的。

這個模型考慮了一個單元所屬的所有維上的度量值的變化和模式。例如，假設有一個銷售數據的數據立方體，并且要查看每個月的銷售概況。在可視化提示的幫助下，注意到與其他月相比，十一月的銷售量有所增加，在時間維上這像是一個異常。可是，通過下載十一月來觀察這個月的每一項的銷售，可以注意到十一月中其他項的銷售也有一個相似的增加。因此，如果考慮到項目維，十一月的總銷售上的增加就不是一個異常。這個模型考慮了隱藏在所有數據立方體集合分組操作后面的異常。對于這樣的異常，因為搜索空間非常大，特別是當存在許多包含若干層的概念層次的維時，人工探測就非常困難了。為了改善以上不足，李翠平等人[35]通過在挖掘過程中引入約束條件，將數據立方體限制到一個小的多維空間中，然后再從中找出離群點，有效地改進了挖掘效率。

2.1.6 其他離群點挖掘方法

上面介紹了離群點挖掘的五種常用方法。最近，一些學者將其他研究領域的方法移植到離群點挖掘領域，提出了許多新穎的離群點挖掘方法。

一些研究者提出了基于子空間的離群點挖掘方法。Aggarwal等人[36]討論了一個新的離群點探測技術，通過研究數據集的投影密度分布來挖掘離群點。He等人[37]提出了一個基于頻繁模式的離群點檢測方法，旨在利用不同子空間中的頻繁模式來定義高維空間中的離群點。Li等人[38]介紹了一個基于超圖模型的離群點挖掘方法，并用來檢測分類數據集中的離群點。

一些研究者提出了基于支持向量的離群點挖掘方法。Tax等人[39]首次提出了支持向量新穎探測器（SVND）。Cao等人[40]提出了改良的SVND，在性能上有了較大提高。

還有一些研究者提出了基于神經網絡的離群點挖掘方法。Harkins等人[41]利用重復因子神經網絡（RNNs）提供了一個對于離群數據的度量；Williams等人[42]將RNN離群點挖掘方法與其他三種方法進行了對比。

以上介紹了檢測數據集中離群點的一些方法，這些挖掘方法主要從數據模型的角度出發。根據不同的分類標準，離群點挖掘方法可以分成不同的類型。比如可以分成參數方法和非參數方法，基于統計學的方法是參數方法，而基于距離、基于聚類、基于密度的方法等都屬于非參數方法；還可以分成一維的和多維的挖掘方法，這是根據適用的數據集維度來分類的。現在絕大多數的離群點挖掘方法都沒有考慮數據對象的類標簽，He等人[43]和Papadimitriou等人[44]研究了類離群點挖掘的問題，并提出了相應的算法。He等人[45]考慮了類離群點檢測問題：“給定一個有類標簽的對象集，在考慮類標簽的情況下，找到那些引起懷疑的對象”，發展了類離群點概念，提出的實用的解決方法是通過擴展現有的離群點挖掘算法到這種情況下來實現的。顯然，根據類標簽（異常或正常）是否可見，可以將離群點挖掘方法分成有監督、無監督和半監督的方法[3]。

2.2 離群點挖掘研究熱點

本節重點介紹離群點挖掘領域的研究熱點，從調研情況看，當前離群點挖掘的研究熱點主要集中在高維數據集、數據流和Web數據的離群點挖掘上。

2.2.1 高維數據集離群點挖掘

在大量實際應用中，需要尋找高維數據集中的離群點。這些高維數據集的數據維數通常高達上百維，這對已有的離群點挖掘算法是一個巨大的挑戰。目前，許多挖掘方法是利用數據集之間的關系相似度概念來挖掘離群點的，然而在高維數據集中，數據是相當稀疏的，相似度也就失去了意義。事實上，基于相似的定義，稀疏的高維數據集中的每一個點都可以看成是一個離群點。因此，對于高維數據集而言，挖掘出有意義的離群點變得十分復雜[8]。與數據挖掘中大量的其他問題相似，離群點挖掘算法在高維數據集中也將失去其有效性。盡管已有的離群點挖掘算法[5，6，21，33]可以部分或全部滿足高維數據集中離群點挖掘的要求，但實際上沒有一個算法可對高維數據集中離群點進行有效的挖掘[36]。

文獻[36]通過研究投影的密度分布進行離群點檢測。直觀而言，如果在某些低維的投影中，一個數據點出現在一個局部的區域，而該區域表現出了非正常的低密度，就稱這樣的點為離群點。基于這種思想，文獻[36]介紹了一種基于進化算法的高維數據集離群點挖掘方法。使用進化算法的主要目的是找到維的最優組合即降維，以及計算這些維組合單元的數據密度。文獻[36]還利用該方法對實際數據集進行測試，結果表明，采用進化算法的處理效果很好，甚至對具有279個屬性的高維數據集也能有效地進行離群點挖掘。另外，借鑒高維數據集的聚類算法，文獻[46]提出了一種通過閉頻繁項集及其產生的關聯規則來進行高維數據集離群點挖掘的方法。

2.2.2 數據流離群點挖掘

目前，在許多如網絡監控、通信服務、傳感網絡和金融服務等應用領域產生一種新型的數據——流數據。這些數據以網絡性能參數、電話記錄、傳感器的讀入值和金融數據等體現，它們是實時的、連續的、無限的，是按照數據項到達的順序控制的，一組有序的點x1，x2，…，xn的序列。它們不是存儲在磁盤上的有限數據集合，而是無限的、連續的、快速的、實時的、以流的形式出現的數據集合。流數據中每個數據單元是一個元組，元組的個數是無窮的。與傳統的數據相比，流數據的特點表現在量大、連續性、實時性，隨機存取采用的是單一線性數據掃描，完整地將數據流存儲到本地是不可行的。

數據流的諸多特征，以及算法上的有限存儲、一次遍歷等要求，使其成為近年來數據挖掘技術的研究熱點之一。數據流挖掘方面的研究很多[47~54]，文獻[47]認為挖掘數據流的變化特征是一個關鍵問題。對數據流變化的研究可分成三類，即變化的模型化和表示、挖掘方法和變化的交互式探查。從目前的研究現狀來看，以上問題還沒有進行過系統的研究，所以有關數據流變化的研究是數據流挖掘研究的一個十分重要的方向。數據流中離群點的出現是導致數據流變化的一個重要因素，所以研究數據流中離群點挖掘問題是十分必要的。

在數據流研究中，數據的變化一般對任何數據處理算法都有深遠的影響。例如在構建一個數據流挖掘模型時[51，54]，變化到達之前的數據可能偏離那些與不再保持的特征所相關的模型，如果想處理對于數據流的查詢，想再用到前期某一時間段內的數據就比較困難了。絕大多數現有的研究集中在通過丟棄舊數據或給其較小的權重來匹配變化分布的算法[51]，但沒有考慮分布的變化是何時發生的以及怎樣發生的。因此文獻[55]提出了檢測數據流什么時候發生變化的方法，并對變化進行量化和描述。它采用兩個數據窗口，分別稱為參照窗口(reference window)和滑動窗口(sliding window)。每當一個新數據點出現時，滑動窗口向前滑動一次，而參照窗口當且僅當檢測到數據流中出現變化時才進行更新。該算法的基本思想是，假設兩個數據集S1和S2，它們分別由兩個不同的分布P1和P2產生，根據數據集S1和S2判斷是P1=P2還是P1≠P2，從而利用兩個數據集分布的關系來判斷數據流的變化，并開發出一整套檢測數據流變化的算法。文獻[56]介紹了一個從數據流中挖掘報警事件(即離群點)的系統MAIDS。該系統的主要功能組件包括流查詢引擎、流數據分類器、流模式發現器、流聚類分析器和流挖掘觀測儀五部分；原理是利用已有的數據挖掘算法，通過組合優化來解決數據流中的離群點挖掘問題。文獻[57]提出了一種基于數據空間動態網格劃分的快速數據流離群點檢測算法。該算法利用動態網格對空間中的稠密和稀疏區域進行劃分，過濾處于稠密區域的大量主題數據，有效地減少算法需要考察的數據對象的規模；而對于稀疏區域中的候選離群點，采用近似方法計算其離群度，具有較高的離群度的數據就作為離群點輸出。文獻[58]在頻繁模式的離群因子概念基礎上，提出了類別屬性數據流離群度量——加權頻繁模式離群因子（WFPOF），并針對數據流特點提出了基于WFPOF的高維數據流離群點檢測算法FODFPStream。該算法通過動態發現和維護頻繁模式來計算離群度，能有效處理高維類別屬性數據流，并進一步擴展到數值屬性和混合屬性數據流；同時通過數據衰減系數的設定，可以有效地處理數據流數據中的概念轉移問題。

2.2.3 Web離群點挖掘

Web挖掘就是從Web數據中分析有趣的和有用的模式，但是，現有的Web挖掘算法處理的問題大多是發現Web中的頻繁模式，通常忽略被稱為噪聲或離群點的非頻繁模式。Web數據中的離群點被定義為這樣的觀測點：它偏離其他的觀測值太遠，以至于人們懷疑它源自不同的機理或該對象與數據集中其余的數據明顯不一致[59，60]。文獻[59]把Web離群點分為不同類別，如圖6所示。

Web數據主要由半結構化或非結構化類型的數據所構成，這對基于Web數據的信息發現提出了挑戰，將已有的離群點挖掘算法直接應用到Web數據中是一種不明智的做法。對Web離群點的挖掘首先需要對Web數據進行預處理，然后再進行離群點挖掘。文獻[59，60]分別給出了Web內容離群點挖掘的一個框架和比較初級的算法。文獻[61]提出了一種基于距離的Web使用離群點挖掘方法，利用Web使用數據，分析用戶的上網行為模式。

3 結束語

離群點挖掘是一個非常有應用價值的研究領域，近年來受到越來越多的關注，但由于離群點定義的主觀性和相對性，挖掘數據集中的離群點仍是相當復雜的，至今沒有通用的、高效的方法來解決這個問題。本文通過對該領域的深入研究，重點介紹了離群點挖掘方法中基于統計學的方法、基于距離的方法、基于密度的方法、基于聚類的方法和基于偏離的方法，還簡要介紹了其他一些新的離群點挖掘方法，并總結了它們各自的優缺點。同時，根據目前離群點挖掘方向的研究熱點，本文對高維數據集離群點挖掘、數據流離群點挖掘和Web離群點挖掘進行了簡要介紹。當然，這并不能代表目前離群點挖掘的所有研究趨勢，但它們確實是離群點挖掘研究的難點。

根據調研，認為以下幾個方面是未來離群點挖掘研究的發展方向：

a）采用接近人類思維的、智能化的挖掘算法來進行離群點挖掘，這將有效地減少離群點定義的主觀性和相對性帶來的影響。

b）數據可視化技術的應用將會大大地簡化離群點的挖掘工作。

c）研究高維數據集、數據流和Web數據中離群點挖掘的高效算法仍將是熱點，尤其是在欺詐檢測、網絡入侵等具體應用領域上。

d)重視對離群點挖掘的后期分析和處理。目前，在幾乎所有的離群點挖掘研究中都沒有關注這方面的問題，一般僅對發現的離群點進行簡要的說明，如果能夠結合實際的背景意義，對發現的離群點進行詳細的分析處理，將會帶來更大的實際應用價值。

參考文獻：

［1］KNORR E M， NG R T. Algorithms for mining distancebased outliers in large datasets[C]//Proc of VLDB’98. San Francisco， CA:Morgan Kaufmann Publishers， 1998:392403.

[2]HAWKINS D. Identification of outliers[M]. London: Chapman Hall， 1980.

[3]TAN Pangning， STEINBACH M， KUMAR V. Introduction to data mining[M]. Boston: Pearson AddisonWesley Education Inc， 2006.

[4]王宏鼎， 童云海， 譚少華， 等. 異常點挖掘研究進展[J]. 智能系統學報， 2006，1(1):6773.

[5]KNORR E， NG R. Finding intentional knowledge of distancebased outliers[C]//Proc of VLDB’99. Edinburgh: [s.n.]， 1999:211222.

[6]KNORR E M， NG R T， TUCAKOV V. Distancebased outliers: algorithms and applications[J]. The VLDB Journal， 2000，8(34):237253.

[7]AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc of SIGMOD’93. New York: ACM Press， 1993:207216.

[8]BREIMAN L， FRIEDMAN J H， OLSHEN R A， et al. Classification and regression trees[M]. New York: Chapman Hall， 1984.

[9]ESTER M， KRIEGEL H P， SANDER J， et al. A densitybased algorithm for discovering clusters in large spatial databases with noise[C]//Proc of KDD’96. Portland， Oregon: AAAI Press， 1996:226231.

[10]NG R T， HAN Jiawei. Efficient and effective clustering method for spatial data mining[C]//Proc of VLDB’94. Vancoaver， BC: University of British Columbia， 1994:144155.

[11]HAN Jiawei， KAMBER M. Data mining: concepts and techniques[M]. New York: Morgan Kaufmann Publishers， 2001.

[12]BARNETT V， LEWIS T. Outliers in statistical data[M]. 2nd ed.New York: Wiley， 1994.

[13]ROUSSEEUW P J， LEROY A M. Robust regression and outlier detection[M]. New York: Wiley， 1987.

[14]YAMANISHI K， TAKEUCHI J， WILLIAMS G， et al. Online unsupervised outlier detection using finite mixtures with discounting learning algorithms[C]//Proc of KDD’00.New York: ACM Press， 2000:320324.

[15]YAMANISHI K， TAKEUCHI J. Discovering outlier filtering rules from unlabeled datacombining a supervised learner with an unsupervised learner[C]//Proc of KDD’01. New York: ACM Press， 2001:389394.

[16]JOHNSON T， KWOK I， NG R. Fast computation of 2dimensional depth contours[C]//Proc of KDD’98. New York: [s.n.]， 1998:224228.

[17]PREPARATA F， SHAMOS M. Computational geometry: an introduction[M]. New York: SpringerVerlag， 1988.

[18]RUTS I， ROUSSEEUW P J. Computing depth contours of bivariate point clouds[J]. Computational Statistics Data Analysis， 1996，23(1): 153168.

[19]KNORR E， NG R. A unified motion of outliers: properties and computation[C]//Proc of KDD’97. California: AAAI Press， 1997:219222.

[20]GHOTING A， PARTHASARATHY S， ERIC M. Fast mining of distancebased outliers in highdimensional datasets， NGSCNS0406386[R]. Ohio: the Ohio State University， 2005.

[21]BAY S D， SCHWABACHER M. Mining distancebased outliers in near linear time with randomization and a simple pruning rule[C]//Proc of KDD’03. New York: ACM Press， 2003:2938.

[22]TAO Yufei， XIAO Xiaokui， ZHOU Shuigeng. Mining distancebased outliers from large databases in any metric space[C]//Proc of KDD’06. New York: ACM Press， 2006:394403.

[23]RAMASWAMY S， RASTOGI R， SHIM K. Efficient algorithms for mining outliers from large data sets[C]//Proc of SIGMOD’00. New York: ACM Press， 2000:427438.

[24]BREUNIG M M， KRIEGEL H P， NG R T， et al. LOF: identifying densitybased local outliers[C]//Proc of SIGMOD’00. New York: ACM Press， 2000: 93104.

[25]AGRAWAL R， GEHRKE J， GUNOPULOS D， et al. Automatic subspace clustering of high dimensional data for data mining applications[C]//Proc of SIGMOD’98. New York: ACM Press， 1998:94105.

[26]WANG Wei， YANG Jiong， MUNTZ R. STING: a statistical information grid approach to spatial data mining[C]//Proc of VLDB’97. Athens: [s.n.]， 1997:186195.

[27]HINNEBURG A， KEIM D A. An efficient approach to clustering in large multimedia databases with noise[C]//Proc of KDD’98. New York:AAAI Press， 1998:5865.

[28]TANG Jian， CHEN Zhixiang， FU A W，et al. Enhancing effectiveness of outlier detections for low density patterns[C]//Proc of PAKDD’02. London， UK:SpringerVerlag， 2002: 535548.

[29]JIN Wen， TUNG A K H， HAN Jiawei. Mining topn local outliers in large databases[C]//Proc of SIGKDD’01. New York:ACM Press， 2001:293298.

[30]PAPADIMITRIOU S， KITAGAWA H， GIBBONS P B，et al. IOCI: fast outlier detection using the local correlation integral[C]//Proc of ICDE’03. [S.l.]: IEEE Computer Society， 2003:315326.

[31]JIANG M F， TSENG S S， SU C M. Twophase clustering process for outlier detection[J]. Pattern Recognition Letters， 2001，22(67):691700.

[32]HE Zengyou， XU Xiaofei， DENG Shengchun. Discovering cluster based local outliers[J]. Pattern Recognition Letters， 2003，24(910):16411650.

[33]ARNING A， AGRAWAL R， RAGHAVAN P. A linear method for deviation detection in large databases[C]//Proc of KDD’96. Portland: AAAI Press， 1996:164169.

[34]SARAWAGI S， AGRAWAL R， MEGIDDO N. Discoverydriven exploration of OLAP data cubes[C]//Proc of EDBT’98. [S.l.]:SpringerVerlag， 1998:168182.

[35]李翠平， 李盛恩， 王珊， 等. 一種基于約束的多維數據異常點挖掘方法[J]. 軟件學報， 2003，14(9):15711577.

[36]AGGARWAL C C， YU P S. Outlier detection for high dimensional data[C]//Proc of SIGMOD’01. New York: ACM Press， 2001:3746.

[37]HE Zengyou， XU Xiaofei， HUANG J Z， et al. A frequent pattern discovery based method for outlier detection[C]//Proc of WAIM’04. Berlin:Springer， 2004: 726732.

[38]LI Wei， QIAN Weining， ZHOU Aoying， et al. HOT: hypergraphbased outlier test for categorical data[C]//Proc of PAKDD’03. Berlin:Springer， 2003: 399410.

[39]TAX D M J， DUIN R P W. Support vector data description[J]. Pattern Recognition Letters， 1999，20(1113):11911199.

[40]CAO Lijuan， LEE H P， CHONG W K. Modified support vector novelty detector using training data with outliers[J]. Pattern Recognition Letters， 2003，24(14):24782479.

[41]HARKINS S， HE Hongxing， WILLIAMS G J， et al. Outlier detection using replicator neural networks[C]//Proc ofDWKD. London，UK: SpringerVerlag， 2002:170180.

[42]WILLIAMS G J， BASTER R A， HE Hongxing， et al. A comparative study of RNN for outlier detection in data mining[C]//Proc of ICDM’02. Washington DC: IEEE Computer Society， 2002:709712.

[43]HE Zengyou， DENG Shengchun， XU Xiaofei. Outlier detection integrating semantic knowledge[C]//Proc of WAIM’02. London，UK: SpringerVerlag， 2002:126131.

[44]PAPADIMITRIOU S， FALOUTSOS C. Crossoutlier detection[C]//Proc of SSTD’03. Berlin: Springer， 2003: 199213.

[45]HE Zengyou， XU Xiaofei， HUANG J Z， et al. Mining class outlier: concepts， algorithms and application in CRM[J]. Expert System with Applications， 2004， 27(4): 681697.

[46]陸介平， 倪巍偉， 孫志輝. 基于關聯分析的高維空間異常點發現[J]. 應用科學學報， 2006， 24(1):6063.

[47]CHEN Zhiyuan， LI Chen， PEI Jian，et al. Recent progress on selected topics in database research: a report from nine young Chinese researchers working in united states[J]. Journal of Computer Science and Technology， 2003，18(5):538552.

[48]GUHA S， MISHRA N， MOTWANI R， et al. Clustering data streams[C]//Proc of FOCS’00. Redondo Beach: [s.n.]， 2000:359366.

[49]O’CALLAGHAM L， MISHRA N， MEYESON A，et al. Streamingdata algorithms for highquality clustering[C]//Proc of FOCS’01. Washington DC: IEEE Computer Society， 2002:685704.

[50]DOMINGOS P， HULTEN G. Mining highspeed data streams[C]//Proc of SIGKDD’00. New York: ACM Press， 2000:7180.

[51]HULTEN G， SPENCER L，DOMINGOS P. Mining timechanging data streams[C]//Proc of SIGKDD’01. New York:ACM Press， 2001:97106.

[52]MANKU G S， MOTWANI R. Approximate frequency counts over data streams[C]//Proc of VLDB’02. Hong Kong:VLDB Endowment， 2002:346357.

[53]CHARIKAR M， CHEN K， COLTON M F. Finding frequent items in data streams[C]//Proc of ICALP’02. London，UK: SpringerVerlag， 2002:693703.

[54]AGGARWAL C C， HAN Jiawei， WANG Jianyong， et al. A framework for clustering evolving data streams[C]//Proc of VLDB’03. Berlin:VLDB Endowment， 2003:8192.

[55]KIFER D， BENDAVID S， GEHRKE J. Detecting change in data streams[C]//Proc of VLDB’04. Toronto:VLDB Endowment， 2004:180191.

[56]CAI Y D， CLUTTER D， PAPE G， et al. MAIDS: mining alarming incidents from data streams[C]//Proc of ACM SIGMOD’International Conference on Management of Data. New York: ACM Press， 2004:919920.

[57]楊宜東， 孫志揮， 朱玉全， 等. 基于動態網格的數據流離群點快速檢測算法[J]. 軟件學報， 2006，17(8):17961803.

[58]周曉云， 孫志揮， 張柏禮， 等. 高維類別屬性數據流離群點快速挖掘算法[J]. 軟件學報， 2007，18(4):933942.

[59]AGYEMANG M， BARKER K， ALHAJJ R. Framework for mining Web content outliers[C]//Proc of ACM SAC’04. New York: ACM Press， 2004:590594.

[60]AGYEMANG M， BARKER K， ALHAJJ R. Mining web content outliers using structure oriented weighting techniques and Ngrams[C]//Proc of ACM SAC’05. New York:ACM Press， 2005:482487.

[61]趙澤茂， 何坤金， 陳鵬， 等. Web日志文件的異常數據挖掘算法及其應用[J]. 計算機工程， 2003，29(17):195197.

[62]YU Dantong， SHEIKHOLESLAMI G， ZHANG Aidong. FindOut: finding out outliers invery large datasets[J]. Knowledge and Information Systems， 2002，4(4):387412.