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

　　一、異常檢測(cè)方法的分類

　　異常數(shù)據(jù)挖掘是一個(gè)非常有趣的研究課題，國(guó)內(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)分布等)，用不一致性測(cè)試(discordancy test)識(shí)別異常。存在問(wèn)題是，在許多情況下，用戶并不知道這個(gè)數(shù)據(jù)分布;而且現(xiàn)實(shí)數(shù)據(jù)也往往不符合任何一種理想狀態(tài)的數(shù)學(xué)分布;即使在低維(一維或二維)時(shí)的數(shù)據(jù)分布已知，在高維情況下，估計(jì)數(shù)據(jù)點(diǎn)的分布是極其困難的。

　　(二)基于距離的方法

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

　　1.基于索引的算法

　　尋找所有的DB(p,D)-outlier可以通過(guò)對(duì)最近鄰查詢或以O(shè)為中心的范圍查詢的回答來(lái)實(shí)現(xiàn)。基于多維索引結(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ū)相等的邏輯塊，通過(guò)認(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ù)空間被劃分為邊長(zhǎng)為D/(2k1/2)的單元;每個(gè)單元有兩個(gè)包圍層第一層為1倍的單元厚，第二層為int(2k1/2 -1)+1倍的單元厚確定異常，

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

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

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

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

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

　　Knorr和Ng(VLDB’1998)基于距離的異常檢測(cè)方法的缺陷輸入?yún)?shù)p與D很難確定，并且對(duì)于不同參數(shù)，結(jié)果有很大不穩(wěn)定性。這就需要用戶反復(fù)輸入p與D進(jìn)行測(cè)試，以確定一個(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’不超過(guò)n-1個(gè)，那么稱p為Dnk 異常。如果對(duì)數(shù)據(jù)點(diǎn)根據(jù)它們的Dk(p)距離進(jìn)行排序，那么前n個(gè)點(diǎn)就被看作異常。循環(huán)嵌套算法(Nested-loop Algorithm)，對(duì)每個(gè)點(diǎn)p，計(jì)算它的第k個(gè)最近鄰的距離Dk(p)，把具有極大Dk值前n個(gè)點(diǎn)作為異常。上面的算法每次處理一個(gè)點(diǎn)p，那么需要掃描一遍數(shù)據(jù)庫(kù)，總共需要掃描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 異常，可以先對(duì)數(shù)據(jù)集進(jìn)行劃分，然后估計(jì)每個(gè)劃分的Dk(p)的上、下界，如果能判定某個(gè)劃分不可能包含異常的話，那么就可以直接把它刪除掉;然后再?gòu)氖Ｏ碌膭澐?侯選劃分)來(lái)計(jì)算異常。現(xiàn)有的許多聚類算法可以用來(lái)劃分?jǐn)?shù)據(jù)集，如BIRCH。

　
　 (三)基于偏差的方法

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

　　
(四)基于密度的方法

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

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

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

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

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

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

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

　　二、算法小結(jié)

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

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