單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,幾種常用的異常數(shù)據(jù)挖掘方法,在數(shù)據(jù)挖掘的過程中,數(shù)據(jù)庫中可能包含一些數(shù)據(jù)對象,它們與數(shù)據(jù)的一般行為或模型不一致,這些數(shù)據(jù)對象被稱為,異常點,對異常點的查找過程稱為,異常數(shù)據(jù)挖掘,它是數(shù)據(jù)挖掘技術(shù)中的一種,.,異常數(shù)據(jù)挖掘又稱孤立點分析、異常檢測、例外挖掘、小事件檢測、挖掘極小類、偏差檢測等,.,孤立點可能是“臟數(shù)據(jù)”,也可能是與實際對應(yīng)的有意義的事件,.,從知識發(fā)現(xiàn)的角度看,在某些應(yīng)用里,那些很少發(fā)生的事件往往比經(jīng)常發(fā)生的事件更有趣、也更有研究價值,例外的檢測能為我們提供比較重要的信息,使我們發(fā)現(xiàn)一些真實而又出乎預(yù)料的知識,.,因此,異常數(shù)據(jù)的檢測和分析是一項重要且有意義的研究工作。,異常數(shù)據(jù)挖掘的簡介,異常數(shù)據(jù)挖掘有著廣泛的應(yīng)用,如,欺詐檢測,用異常點檢測來探測不尋常的信用卡使用或者電信服務(wù),;,預(yù)測市場動向,;,在市場分析中分析客戶的極低或極高消費異常行為,;,或者在醫(yī)療分析中發(fā)現(xiàn)對多種治療方式的不尋常的反應(yīng)等等,.,通過對這些數(shù)據(jù)進行研究,發(fā)現(xiàn)不正常的行為和模式,有著非常重要的意義,.,對異常點數(shù)據(jù)的挖掘可以描述如下,:,給定一個,n,個數(shù)據(jù)點或?qū)ο蟮募?以及預(yù)期的異常點的數(shù)目,k,目標是,:,發(fā)現(xiàn)與剩余的數(shù)據(jù)相比是顯著相異的、異常的或者不一致的頭,k,個對象,.,聚類數(shù)據(jù)集,序列數(shù)據(jù)集,圖,1,數(shù)據(jù)集中異常點示例,異常點數(shù)據(jù)挖掘的任務(wù)可以分成兩個子問題,:,(,1,),給出已知數(shù)據(jù)集的異常點數(shù)據(jù)的定義,;,(,2,),使用有效的方法挖掘異常點數(shù)據(jù),.,對數(shù)據(jù)模式的不同定義,以及數(shù)據(jù)集的構(gòu)成不同,會導(dǎo)致不同類型的異常點數(shù)據(jù)挖掘,實際應(yīng)用中根據(jù)具體情況選擇異常數(shù)據(jù)的挖掘方法,.,基于統(tǒng)計的方法,利用統(tǒng)計學(xué)方法處理異常數(shù)據(jù)挖掘的問題已經(jīng)有很長的歷史了,并有一套完整的理論和方法,.,統(tǒng)計學(xué)的方法對給定的數(shù)據(jù)集合假設(shè)了一個分布或者概率模型,(,例如正態(tài)分布,),然后根據(jù)模型采用,不一致性檢驗,來確定異常點數(shù)據(jù),.,不一致性檢驗要求事先知道數(shù)據(jù)集模型參數(shù),(,如正態(tài)分布,),分布參數(shù),(,如均值、標準差等,),和預(yù)期的異常點數(shù)目,.,不一致性檢驗是如何進行的,?,工作假設(shè),(working hypothesis),即零假設(shè),:,H,。：,O,F,i=,1,2,n;,替代假設(shè),(alternative hypothesis),即對立假設(shè),:,H,：,O,F,i=,1,2,n;,不一致性檢驗驗證,Oi,與分布,F,的數(shù)據(jù)相比是否顯著地大,(,或者小,).,假設(shè)某個統(tǒng)計量,T,被選擇用于不一致性檢驗,對象,Oi,的該統(tǒng)計量的值為,V i,則構(gòu)建分布,T,估算顯著性概率,S P(V i)=,Prob,(T V i).,如果某個,S P(V i),足夠的小,那么檢驗結(jié)果不是統(tǒng)計顯著的,則,Oi,是不一致的,拒絕工作假設(shè),反之,不能拒絕假設(shè),.,對立假設(shè)是描述總體性質(zhì)的另外一種想法,認為數(shù)據(jù),Oi,來自另一個分布模型,G.,對立假設(shè)在決定檢驗?zāi)芰?(,即當,Oi,真的是異常點時工作假設(shè)被拒絕的概率,),上是非常重要的,它決定了檢驗的準確性等,.,i,1,i,目前利用統(tǒng)計學(xué)研究異常點數(shù)據(jù)有了一些新的方法,如通過分析統(tǒng)計數(shù)據(jù)的散度情況,即數(shù)據(jù)變異指標,來對數(shù)據(jù)的總體特征有更進一步的了解,對數(shù)據(jù)的分布情況有所了解,進而通過數(shù)據(jù),變異指標,來發(fā)現(xiàn)數(shù)據(jù)中的異常點數(shù)據(jù),.,常用的數(shù)據(jù)變異指標有極差、四分位數(shù)間距、均差、標準差、變異系數(shù)等等,變異指標的值大表示變異大、散布廣,;,值小表示離差小,較密集,.,用統(tǒng)計學(xué)的方法檢測異常點數(shù)據(jù)的有效性如何呢,?,一個主要的缺點是絕大多數(shù)檢驗是針對單個屬性的,而許多數(shù)據(jù)挖掘問題要求在多維空間中發(fā)現(xiàn)異常點數(shù)據(jù),.,而且,統(tǒng)計學(xué)方法要求關(guān)于數(shù)據(jù)集合參數(shù)的知識,例如數(shù)據(jù)分布,.,但是在許多情況下,數(shù)據(jù)分布可能是未知的,.,當沒有特定的分布檢驗時,統(tǒng)計學(xué)方法不能確保所有的異常點數(shù)據(jù)被發(fā)現(xiàn),或者觀察到的分布不能恰當?shù)乇蝗魏螛藴实姆植紒砟M,.,0,s,基于距離的方法,什么是基于距離的異常點檢測,?,如果數(shù)據(jù)集合,S,中獨享至少有,p,部分與對象,o,的距離大于,d,則對象,o,是一個帶參數(shù)的,p,和,d,的基于距離的,(DB),的異常點,即,DB(p,d).,換句話說,不依賴于統(tǒng)計檢驗,我們可以將基于距離的異常點看作是那些沒有“足夠多”鄰居的對象,這里的對象是基于距給定對象的距離來定義的,.,與基于統(tǒng)計的方法相比,基于距離的異常點檢測拓廣了多個標準分布的不一致性檢驗的思想,.,基于距離的異常點檢測避免了過多的計算,.,d,目前比較成熟的基于距離的異常數(shù)據(jù)挖掘的算法有,:,基于索引的算法,(Index-based):,給定一個數(shù)據(jù)集合,基于索引的算法采用多維索引結(jié)構(gòu),R-,樹,k-d,樹等,來查找每個對象在半徑,d,范圍內(nèi)的鄰居,.,假設(shè),M,為異常點數(shù)據(jù)的,d,鄰,域,內(nèi)的最大對象數(shù)目,.,如果對象,o,的,M+,1,個鄰居被發(fā)現(xiàn),則對象,o,就不是異常點,.,這個算法在最壞情況下的復(fù)雜度為,O(,kn,),k,為維數(shù),n,為數(shù)據(jù)集合中對象的數(shù)目,.,當,k,增加時,基于索引的算法具有良好的擴展性,.,嵌套,-,循環(huán)算法,(Nested-loop):,嵌套,-,循環(huán)算法和基于索引的算法有相同的計算復(fù)雜度,但是它避免了索引結(jié)構(gòu)的構(gòu)建,試圖最小化,I/O,的次數(shù),.,它把內(nèi)存的緩沖空間分為兩半,把數(shù)據(jù)集合分為若干個邏輯塊,.,通過精心選擇邏輯塊裝入每個緩沖區(qū)域的順序,I/O,效率能夠改善,.,2,基于單元的算法,(cell-based):,在該方法中,數(shù)據(jù)空間被劃為邊長等于,d/(,2,k ),的,單元,.,每個單元有兩個層圍繞著它,.,第一層的厚度是一個單元,而第二層的厚度是,2,k -,1,.,該算法逐個單元地對異常點計數(shù),而不是逐個對象地進行計數(shù),.,對于一個給定的單元,它累計三個計數(shù),單元中對象的數(shù)目,(,cell_count,),單元和第一層中對象的數(shù)目,(cell_+_1_cell_count),單元和兩個層次中的對象的數(shù)目,(cell_+_2_cell_count).,該算法將對數(shù)據(jù)集的每一個元素進行異常點數(shù)據(jù)的檢測改為對每一個單元進行異常點數(shù)據(jù)的檢測,它提高了算法的效率,.,它的算法復(fù)雜度是,O(ck+n),這里的,c,是依賴于單元數(shù)目的常數(shù),k,是維數(shù),.,它是這樣進行異常檢測的,:,若,cell_+_1_cell_count,M,單元中的所有對象都不是異常,;,若,cell_+_2_cell_count =,M,單元中的所有對象都是異常,;,否則,單元中的數(shù)據(jù)某一些可能是異常,.,為了檢測這些異常點,需要逐個對象加入處理,.,基于距離的異常數(shù)據(jù)挖掘方法要求用戶設(shè)置參數(shù),p,和,d,而尋找這些參數(shù)的合適設(shè)置可能涉及多次試探和錯誤,.,1/2,1/2,基于偏差的方法,基于偏差的異常數(shù)據(jù)挖掘方法不采用統(tǒng)計檢驗或者基于距離的度量值來確定異常對象,它是模仿人類的思維方式,通過觀察一個連續(xù)序列后,迅速地發(fā)現(xiàn)其中某些數(shù)據(jù)與其它數(shù)據(jù)明顯的不同來確定異常點對象,即使不清楚數(shù)據(jù)的規(guī)則,.,基于偏差的異常點檢測常用兩種技術(shù),:,序列異常技術(shù),和,OLAP,數(shù)據(jù)立方體技術(shù),.,序列異常技術(shù)模仿了人類從一系列推測類似的對象中識別異常對象的方式,.,它利用隱含的數(shù)據(jù)冗余,.,給定,n,個對象的集合,S,它建立一個子集合的序列,S,1,S,2,.,S m ,這里,2,m,n,由此,求出子集間的偏離程度,即“相異度”,.,該算法從集合中選擇一個子集合的序列來分析,.,對于每個子集合,它確定其與序列中前一個子集合的相異度差異,.,光滑因子最大的子集就是異常數(shù)據(jù)集,.,這里對幾個相關(guān)概念進行解釋,:,(,1,),異常集,:,它是偏離或異常點的集合,被定義為某類對象的最小子集,這些對象的去除會產(chǎn)生剩余集合的相異度的最大減少,.,(,2,),相異度函數(shù),:,已知一個數(shù)據(jù)集,如果兩個對象相似,相異函數(shù)返回值較小,反之,相異函數(shù)返回值較大,;,一個數(shù)據(jù)子集的計算依賴于前個子集的計算,.,(,3,),基數(shù)函數(shù),:,數(shù)據(jù)集、數(shù)據(jù)子集中數(shù)據(jù)對象的個數(shù),.,(,4,),光滑因子,:,從原始數(shù)據(jù)集中去除子集,相異度減小的程度,光滑因子最大的子集就是異常點數(shù)據(jù)集,.,特點,基于偏差的異常數(shù)據(jù)挖掘方法的時間復(fù)雜度通常為,O(n),n,為對象個數(shù),.,基于偏差的異常點檢測方法計算性能優(yōu)異,但由于事先并不知道數(shù)據(jù)的特性,對異常存在的假設(shè)太過理想化,因而相異函數(shù)的定義較為復(fù)雜,對現(xiàn)實復(fù)雜數(shù)據(jù)的效果不太理想,.,基于密度的方法,基于密度的異常數(shù)據(jù)挖掘是在基于密度的聚類算法基礎(chǔ)之上提出來的,.,它采用局部異常因子來確定異常數(shù)據(jù)的存在與否,.,它的主要思想是,:,計算出對象的局部異常因子,局部異常因子愈大,就認為它更可能異常,;,反之則可能性小,.,(,1,),對象,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).,(,2,),對象,p,的,k-,距離鄰域,(,Nk,-,distance):,給定,p,的,k-,距離,k-,distance,(p),p,的,k-,距離鄰域包含所有與,p,的距離不超過,k-,distance,(p),的對象,.,(,3,),對象,p,相對于對象,o,的可達距離,:,給定自然數(shù),k,對象,p,相對于對象,o,的可達距離為,reach-dist k(p,o)=,max,k-,distan,ce(o),d(p,o).,(4),對象,p,的局部可達密度,(,Local Reachable Distance):,對象,p,的局部可達密度為對象,p,與它的,MinPt,s-,鄰域的平均可達距離的倒數(shù),.,對象,p,的局部異常因子表示,p,的異常程度,局部異常因子愈大,就認為它更可能異常,;,反之則可能性小,.,簇內(nèi)靠近核心點的對象的算局部異常點因素,LOF,接近于,1,那么不應(yīng)該被認為是局部異常,.,而處于簇的邊緣或是簇的外面的對象的,LOF,相對較大,.,為了更好地理解，先看一個,2-D,數(shù)據(jù)集的例子，如圖,4,所示，該數(shù)據(jù)集是一個,2,維數(shù)據(jù)集，包含,502,個對象，在聚類,C1,中有,400,個對象，在聚類,C2,中有,100,個對象，此外還有,2,個特殊的對象,O1,和,O2,，該例中，可以看出,C2,形成的聚類要比,C1,稠密,對象,Ol,和,02,都應(yīng)被看作是,C2,數(shù)據(jù)集中的異常點，且聚類,C1,和聚類,c2,中的對象都是聚類中的數(shù)據(jù)，而不是異常點既然基于距離的異常點定義能夠統(tǒng)一異常點的概念，那么能否找到合適,P,和,d,，使得其滿足,DB(P,，,d),異常點的定義事實上，利用,DB(P,，,d),的定義，只能發(fā)現(xiàn),01,是一個異常點，這是因為對,C1,中的每一個對象,q,，找不到一個合適的參數(shù),P,和,d,來滿足使弓最近的鄰域中的對象間的距離大于,02,和,C2,間的距離，從而保證,02,是異常點的同時又能保證,c2,中的對象不是異常點從該例可看出,DB(P,，,d),在某些特定的情況下是準確和充分的，但聚類密度如果存在不同就會出現(xiàn)問題，為了解決這個問題，基于密度模型的局部異常點挖掘算法被提出，從而保證,01,和,02,在數(shù)據(jù)集中都是異常點,高維數(shù)據(jù)的方法,以上幾種異常數(shù)據(jù)挖掘算法一般都是在低維數(shù)據(jù)上進行的,對于高維數(shù)據(jù)的效果并不是很好,基于這個原因,Aggarwal,和,Yu,提出一個高維數(shù)據(jù)異常檢測的方法,.,它把高維數(shù)據(jù)集映射到低維子空間,根據(jù)子空間映射數(shù)據(jù)的稀疏程度來確定異常數(shù)據(jù)是否存在,.,高維數(shù)據(jù)的異常點檢測的主要思想是,:,首先它將數(shù)據(jù)空間的每