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

　　一、異常檢測方法的分類

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

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

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

　　(二)基于距離的方法

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

　　1.基于索引的算法

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

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

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

　　3.基于單元的方法

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

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

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

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

　　由于索引建立的開銷很大，簡單索引算法沒有競爭性當(dāng)k<=4時(shí)，基于單元的算法在N越大時(shí)優(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)行測試，以確定一個(gè)滿意解;不能給定異常的程度;算法的復(fù)雜度較高。Rastogi和Ramaswamy(SIGMOD’2000)提出了一個(gè)新的基于距離異常定義

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

　
　 (三)基于偏差的方法

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

　　
(四)基于密度的方法

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

　　至少存在k個(gè)對象o’∈D\{p}，使得d(p, o’) d(p, o)，并且至多存在k-1個(gè)對象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)靠近核心點(diǎn)的對象的LOF接近于1，那么不應(yīng)該被認(rèn)為是局部異常。而處于簇的邊緣或是簇的外面的對象的LOF相對較大。

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

　　二、算法小結(jié)

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

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