什么是異常(outlier)?Hawkins(1980)給出了異常的本質性的定義：異常是在數據集中與眾不同的數據，使人懷疑這些數據并非隨機偏差，而是產生于完全不同的機制。聚類算法對異常的定義：異常是聚類嵌于其中的背景噪聲。異常檢測算法對異常的定義：異常是既不屬于聚類也不屬于背景噪聲的點。它的行為與正常的行為有顯著的不同。在某個季節(jié)里，某一天的氣溫很高或很低，這個溫度數據就是一個異常。異常檢測和分析是數據挖掘中一個重要方面，也是一個非常有趣的挖掘課題。它用來發(fā)現“小的模式”(相對于聚類)，即數據集中間顯著不同于其它數據的對象。異常檢測具有廣泛的應用，如電信和信用卡欺騙、貸款審批、藥物研究、醫(yī)療分析、消費者行為分析、氣象預報、金融領域客戶分類、網絡入侵檢測等 。
 

　　一、異常檢測方法的分類

　　異常數據挖掘是一個非常有趣的研究課題，國內外關于這方面的已提出的算法文獻非常多，這些方法大致分為四類：基于統(tǒng)計(statistical-based)的方法、基于距離(distance-based)的方法、基于偏差(deviation-based)的方法、基于密度(density-based)的方法。

　　(一)基于統(tǒng)計的方法

　　假設給定的數據集服從一個隨機分布(如正態(tài)分布等)，用不一致性測試(discordancy test)識別異常。存在問題是，在許多情況下，用戶并不知道這個數據分布;而且現實數據也往往不符合任何一種理想狀態(tài)的數學分布;即使在低維(一維或二維)時的數據分布已知，在高維情況下，估計數據點的分布是極其困難的。

　　(二)基于距離的方法

　　Knorr和Ng(VLDB’1998)提出一種基于距離的異常檢測方法，基于距離的異常定義：數據集S中一個對象O稱為DB(p,D)-outlier，如果它滿足下列性質：數據集S中至少p*100%的對象與O的距離大于距離D。簡單的說，基于距離的異常點就是那些沒有“足夠多”的鄰居的對象。采取不同的參數p和D ， DB(p,D)-outlier可以表示所有的基于統(tǒng)計的異常。基于距離的異常檢測的算法又分為三個基本類型：基于索引(index-based)的算法、嵌套循環(huán)(nested-loop)算法、基于單元(cell-based)的方法。

　　1.基于索引的算法

　　尋找所有的DB(p,D)-outlier可以通過對最近鄰查詢或以O為中心的范圍查詢的回答來實現。基于多維索引結構R-Tree或kd-Tree算法復雜度是O(kN2 )，其中k為維數，N為數據點數。缺點：需要建立多維索引結構，時間復雜度大。

　　2.嵌套循環(huán)算法NL

　　將內存緩沖區(qū)空間劃分成相等的兩部分，數據集分成幾個大小和每部分緩沖區(qū)相等的邏輯塊，通過認真選擇調入每一部分緩沖區(qū)的次序，使I/O次數最小算法復雜度是O(kN2)其中k為維數，N為數據點數。 特點：不需要建立多維索引結構，時間復雜度較大。

　　3.基于單元的方法

　　數據空間被劃分為邊長為D/(2k1/2)的單元;每個單元有兩個包圍層第一層為1倍的單元厚，第二層為int(2k1/2 -1)+1倍的單元厚確定異常，

　　若cell_+_1_layer_count>M，單元中的對象都不是異常;

　　若cell_+_2_layer_count<=M，單元中的所有對象都是異常;

　　否則，單元中的一些對象可能為異常，逐個對象進行處理。算法復雜度是O(ck+N)。

　　由于索引建立的開銷很大，簡單索引算法沒有競爭性當k<=4時，基于單元的算法在N越大時優(yōu)越性越明顯當k>=5之后，嵌套循環(huán)算法開始顯現出優(yōu)勢。

　　4.基于距離的算法的改進

　　Knorr和Ng(VLDB’1998)基于距離的異常檢測方法的缺陷輸入參數p與D很難確定，并且對于不同參數，結果有很大不穩(wěn)定性。這就需要用戶反復輸入p與D進行測試，以確定一個滿意解;不能給定異常的程度;算法的復雜度較高。Rastogi和Ramaswamy(SIGMOD’2000)提出了一個新的基于距離異常定義

　　：Dnk 異常，用Dk(p)表示點p和它的第k個最近鄰的距離，給定d維空間中包含N個點的數據集，參數n和k(自然數)，如果滿足Dk(p’)>Dk(p)的點p’不超過n-1個，那么稱p為Dnk 異常。如果對數據點根據它們的Dk(p)距離進行排序，那么前n個點就被看作異常。循環(huán)嵌套算法(Nested-loop Algorithm)，對每個點p，計算它的第k個最近鄰的距離Dk(p)，把具有極大Dk值前n個點作為異常。上面的算法每次處理一個點p，那么需要掃描一遍數據庫，總共需要掃描N遍(N為數據點數)。 基于索引的算法(Index-based Algo?鄄rithm)，用如R*-樹的空間索引結構存儲。基于劃分的算法(partition-based Algorithm) ，如果某個點的Dk(p)較小的話，那么不可能是Dnk 異常，可以先對數據集進行劃分，然后估計每個劃分的Dk(p)的上、下界，如果能判定某個劃分不可能包含異常的話，那么就可以直接把它刪除掉;然后再從剩下的劃分(侯選劃分)來計算異常。現有的許多聚類算法可以用來劃分數據集，如BIRCH。

　
　 (三)基于偏差的方法

　　Argrawal和Ragaran(KDD’1995)提出一種“序列異常”(sequential exception)的概念。算法介紹給定n個對象的集合S，建立一個子集序列{S1,S2,…,Sm},這里2≤m≤n,滿足Sj-1

　　
(四)基于密度的方法

　　距離異常的缺陷，基于密度的方法的有關概念對象p的k-距離(k-distance) 對任意的自然數k，定義p的k-距離(k-distance(p))，為p和某個對象o之間的距離，這里的o滿足：

　　至少存在k個對象o’∈D\{p}，使得d(p, o’) d(p, o)，并且至多存在k-1個對象o’ ∈D\{p}，使得d(p, o’) < d(p, o)。 基于密度的方法的有關概念，

　　1.對象p的k-距離鄰域(Nk-distance)， 給定p的k-距離k-distance(p)，p的k-距離鄰域包含所有與p的距離不超過k-distance(p)的對象。

　　2.對象p相對于對象o的可達距離，給定自然數k，對象p相對于對象o的可達距離為：

　　3. 對象p的局部可達密度(Local Reachable Dis?鄄tance)，對象p的局部可達密度為對象p與它的MinPts-鄰域的平均可達距離的倒數。

　　4.對象p的局部異常因子(Local Outlier Factor)， 局部異常的性質對象p的局部異常因子表示p的異常程度，局部異常因子愈大，就認為它更可能異常;反之則可能性小。簇內靠近核心點的對象的LOF接近于1，那么不應該被認為是局部異常。而處于簇的邊緣或是簇的外面的對象的LOF相對較大。

　　局部異常因子計算：第一步先產生所有點的MinPts-鄰域(同時得到MinPts-距離)，并計算到其中每個點的距離; 對低維數據，可以利用網格(Grid)來作k-NN查詢，整個計算時間為 O(n );對中維或中高維數據，必須采用索引結構如X-樹等，使得作k-NN查詢的時間為O(logn) ，整個計算時間為 O(n logn);對特高維數據，索引結構不再有效，時間復雜度提高到O(n2)。第二步計算每個點的局部異常因子。
 

　　二、算法小結

　　基于統(tǒng)計的異常檢測應用主要局限于科研計算，這主要是因為必須事先知道數據的分布特征這就限制了它的應用范圍。 序列異常檢測算法提出的序列異常的概念并沒有得到普遍的認同。這是因為序列異常在概念上仍然有一定缺陷，遺漏了不少的異常數據。基于距離的算法跟基于統(tǒng)計的算法相比，不需要用戶擁有任何領域知識。與“序列異常”相比，在概念上更加直觀。更重要的是，距離異常更接近Hawkins的異常本質定義。基于密度的異常觀點比基于距離的異常觀點更貼近Hawkins的異常定義，因此能夠檢測出基于距離異常算法所不能識別的一類異常數據———局部異常。局部異常觀點擯棄了以前所有的異常定義中非此即彼的絕對異常觀念，更加符合現實生活中的應用。

　　上述的異常檢測算法是以靜態(tài)數據集為研究對象，需要對數據集進行多次掃描，才能得到輸出結果。在現實生活中，對動態(tài)的數據集，即流數據的在線處理的需求更為迫切，因此，只需進行一次掃描便得到結果的數據流異常檢測算法，成為當前的研究熱點。