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

　　一、異常檢測方法的分類

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

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

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

　　(二)基于距離的方法

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

　　1.基于索引的算法

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

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

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

　　3.基于單元的方法

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

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

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

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

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

　　4.基于距離的算法的改進(jìn)

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

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

　
　 (三)基于偏差的方法

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

　　
(四)基于密度的方法

　　距離異常的缺陷，基于密度的方法的有關(guān)概念對象p的k-距離(k-distance) 對任意的自然數(shù)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)。 基于密度的方法的有關(guān)概念，

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

　　2.對象p相對于對象o的可達(dá)距離，給定自然數(shù)k，對象p相對于對象o的可達(dá)距離為：

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

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

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

　　二、算法小結(jié)

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

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