幾種常用的異常數(shù)據(jù)挖掘方法

1、幾種常用的異常數(shù)據(jù)挖掘方法,在數(shù)據(jù)挖掘的過程中,數(shù)據(jù)庫中可能包含一些數(shù)據(jù)對(duì)象,它們與數(shù)據(jù)的一般行為或模型不一致,這些數(shù)據(jù)對(duì)象被稱為異常點(diǎn),對(duì)異常點(diǎn)的查找過程稱為異常數(shù)據(jù)挖掘,它是數(shù)據(jù)挖掘技術(shù)中的一種. 異常數(shù)據(jù)挖掘又稱孤立點(diǎn)分析、異常檢測、例外挖掘、小事件檢測、挖掘極小類、偏差檢測等.孤立點(diǎn)可能是“臟數(shù)據(jù)”,也可能是與實(shí)際對(duì)應(yīng)的有意義的事件. 從知識(shí)發(fā)現(xiàn)的角度看,在某些應(yīng)用里,那些很少發(fā)生的事件往往比經(jīng)常發(fā)生的事件更有趣、也更有研究價(jià)值,例外的檢測能為我們提供比較重要的信息,使我們發(fā)現(xiàn)一些真實(shí)而又出乎預(yù)料的知識(shí). 因此,異常數(shù)據(jù)的檢測和分析是一項(xiàng)重要且有意義的研究工作。,異常數(shù)據(jù)挖掘的簡介,異

2、常數(shù)據(jù)挖掘有著廣泛的應(yīng)用,如欺詐檢測,用異常點(diǎn)檢測來探測不尋常的信用卡使用或者電信服務(wù);預(yù)測市場動(dòng)向;在市場分析中分析客戶的極低或極高消費(fèi)異常行為;或者在醫(yī)療分析中發(fā)現(xiàn)對(duì)多種治療方式的不尋常的反應(yīng)等等. 通過對(duì)這些數(shù)據(jù)進(jìn)行研究,發(fā)現(xiàn)不正常的行為和模式,有著非常重要的意義. 對(duì)異常點(diǎn)數(shù)據(jù)的挖掘可以描述如下:給定一個(gè)n 個(gè)數(shù)據(jù)點(diǎn)或?qū)ο蟮募? 以及預(yù)期的異常點(diǎn)的數(shù)目k ,目標(biāo)是:發(fā)現(xiàn)與剩余的數(shù)據(jù)相比是顯著相異的、異常的或者不一致的頭k 個(gè)對(duì)象.,聚類數(shù)據(jù)集,序列數(shù)據(jù)集,圖1 數(shù)據(jù)集中異常點(diǎn)示例,異常點(diǎn)數(shù)據(jù)挖掘的任務(wù)可以分成兩個(gè)子問題: (1) 給出已知數(shù)據(jù)集的異常點(diǎn)數(shù)據(jù)的定義; (2) 使用有效的

3、方法挖掘異常點(diǎn)數(shù)據(jù). 對(duì)數(shù)據(jù)模式的不同定義,以及數(shù)據(jù)集的構(gòu)成不同,會(huì)導(dǎo)致不同類型的異常點(diǎn)數(shù)據(jù)挖掘, 實(shí)際應(yīng)用中根據(jù)具體情況選擇異常數(shù)據(jù)的挖掘方法.,基于統(tǒng)計(jì)的方法,利用統(tǒng)計(jì)學(xué)方法處理異常數(shù)據(jù)挖掘的問題已經(jīng)有很長的歷史了,并有一套完整的理論和方法.統(tǒng)計(jì)學(xué)的方法對(duì)給定的數(shù)據(jù)集合假設(shè)了一個(gè)分布或者概率模型(例如正態(tài)分布) , 然后根據(jù)模型采用不一致性檢驗(yàn)來確定異常點(diǎn)數(shù)據(jù). 不一致性檢驗(yàn)要求事先知道數(shù)據(jù)集模型參數(shù)(如正態(tài)分布) ,分布參數(shù)(如均值、標(biāo)準(zhǔn)差等) 和預(yù)期的異常點(diǎn)數(shù)目.,不一致性檢驗(yàn)是如何進(jìn)行的?,工作假設(shè)(working hypothesis) 即零假設(shè): H。： O F, i = 1 ,

4、2 , n; 替代假設(shè)(alternative hypothesis) 即對(duì)立假設(shè): H ： O F, i = 1 ,2 , n; 不一致性檢驗(yàn)驗(yàn)證Oi 與分布F 的數(shù)據(jù)相比是否顯著地大(或者小) . 假設(shè)某個(gè)統(tǒng)計(jì)量T 被選擇用于不一致性檢驗(yàn),對(duì)象Oi的該統(tǒng)計(jì)量的值為V i ,則構(gòu)建分布T ,估算顯著性概率S P (V i ) = Prob ( T V i ) . 如果某個(gè)S P (V i )足夠的小, 那么檢驗(yàn)結(jié)果不是統(tǒng)計(jì)顯著的, 則Oi是不一致的,拒絕工作假設(shè),反之,不能拒絕假設(shè).對(duì)立假設(shè)是描述總體性質(zhì)的另外一種想法, 認(rèn)為數(shù)據(jù)Oi 來自另一個(gè)分布模型G. 對(duì)立假設(shè)在決定檢驗(yàn)?zāi)芰?即當(dāng)Oi

5、 真的是異常點(diǎn)時(shí)工作假設(shè)被拒絕的概率) 上是非常重要的, 它決定了檢驗(yàn)的準(zhǔn)確性等.,i,1,i,目前利用統(tǒng)計(jì)學(xué)研究異常點(diǎn)數(shù)據(jù)有了一些新的方法,如通過分析統(tǒng)計(jì)數(shù)據(jù)的散度情況,即數(shù)據(jù)變異指標(biāo),來對(duì)數(shù)據(jù)的總體特征有更進(jìn)一步的了解,對(duì)數(shù)據(jù)的分布情況有所了解,進(jìn)而通過數(shù)據(jù)變異指標(biāo)來發(fā)現(xiàn)數(shù)據(jù)中的異常點(diǎn)數(shù)據(jù). 常用的數(shù)據(jù)變異指標(biāo)有極差、四分位數(shù)間距、均差、標(biāo)準(zhǔn)差、變異系數(shù)等等, 變異指標(biāo)的值大表示變異大、散布廣;值小表示離差小,較密集.,用統(tǒng)計(jì)學(xué)的方法檢測異常點(diǎn)數(shù)據(jù)的有效性如何呢?,一個(gè)主要的缺點(diǎn)是絕大多數(shù)檢驗(yàn)是針對(duì)單個(gè)屬性的,而許多數(shù)據(jù)挖掘問題要求在多維空間中發(fā)現(xiàn)異常點(diǎn)數(shù)據(jù). 而且,統(tǒng)計(jì)學(xué)方法要求關(guān)于數(shù)據(jù)

6、集合參數(shù)的知識(shí),例如數(shù)據(jù)分布. 但是在許多情況下,數(shù)據(jù)分布可能是未知的. 當(dāng)沒有特定的分布檢驗(yàn)時(shí),統(tǒng)計(jì)學(xué)方法不能確保所有的異常點(diǎn)數(shù)據(jù)被發(fā)現(xiàn),或者觀察到的分布不能恰當(dāng)?shù)乇蝗魏螛?biāo)準(zhǔn)的分布來模擬.,基于距離的方法,什么是基于距離的異常點(diǎn)檢測? 如果數(shù)據(jù)集合S 中獨(dú)享至少有p 部分與對(duì)象o 的距離大于d ,則對(duì)象o是一個(gè)帶參數(shù)的p 和d 的基于距離的( DB ) 的異常點(diǎn), 即DB ( p , d) . 換句話說, 不依賴于統(tǒng)計(jì)檢驗(yàn),我們可以將基于距離的異常點(diǎn)看作是那些沒有“足夠多”鄰居的對(duì)象, 這里的對(duì)象是基于距給定對(duì)象的距離來定義的. 與基于統(tǒng)計(jì)的方法相比,基于距離的異常點(diǎn)檢測拓廣了多個(gè)標(biāo)準(zhǔn)分布的

7、不一致性檢驗(yàn)的思想. 基于距離的異常點(diǎn)檢測避免了過多的計(jì)算.,目前比較成熟的基于距離的異常數(shù)據(jù)挖掘的算法有:,基于索引的算法( Index - based) : 給定一個(gè)數(shù)據(jù)集合,基于索引的算法采用多維索引結(jié)構(gòu)R- 樹, k - d樹等,來查找每個(gè)對(duì)象在半徑d范圍內(nèi)的鄰居. 假設(shè)M 為異常點(diǎn)數(shù)據(jù)的d 鄰域內(nèi)的最大對(duì)象數(shù)目. 如果對(duì)象o 的M + 1 個(gè)鄰居被發(fā)現(xiàn),則對(duì)象o 就不是異常點(diǎn). 這個(gè)算法在最壞情況下的復(fù)雜度為O( kn ) , k 為維數(shù), n 為數(shù)據(jù)集合中對(duì)象的數(shù)目. 當(dāng)k 增加時(shí),基于索引的算法具有良好的擴(kuò)展性. 嵌套- 循環(huán)算法(Nested - loop) :嵌套- 循環(huán)算法

8、和基于索引的算法有相同的計(jì)算復(fù)雜度,但是它避免了索引結(jié)構(gòu)的構(gòu)建,試圖最小化I/ O的次數(shù). 它把內(nèi)存的緩沖空間分為兩半,把數(shù)據(jù)集合分為若干個(gè)邏輯塊. 通過精心選擇邏輯塊裝入每個(gè)緩沖區(qū)域的順序, I/ O 效率能夠改善.,2,基于單元的算法(cell - based) :在該方法中,數(shù)據(jù)空間被劃為邊長等于d/ (2k ) 的單元. 每個(gè)單元有兩個(gè)層圍繞著它. 第一層的厚度是一個(gè)單元,而第二層的厚度是2k - 1 . 該算法逐個(gè)單元地對(duì)異常點(diǎn)計(jì)數(shù), 而不是逐個(gè)對(duì)象地進(jìn)行計(jì)數(shù). 對(duì)于一個(gè)給定的單元, 它累計(jì)三個(gè)計(jì)數(shù)單元中對(duì)象的數(shù)目(cell_count) ,單元和第一層中對(duì)象的數(shù)目(cell_ +

9、_1_cell_count) ,單元和兩個(gè)層次中的對(duì)象的數(shù)目(cell_ +_2_cell_count) . 該算法將對(duì)數(shù)據(jù)集的每一個(gè)元素進(jìn)行異常點(diǎn)數(shù)據(jù)的檢測改為對(duì)每一個(gè)單元進(jìn)行異常點(diǎn)數(shù)據(jù)的檢測,它提高了算法的效率. 它的算法復(fù)雜度是O( ck + n) ,這里的c 是依賴于單元數(shù)目的常數(shù), k 是維數(shù). 它是這樣進(jìn)行異常檢測的: 若cell_ + _1_cell_count M ,單元中的所有對(duì)象都不是異常;若cell_ + _2_cell_count = M ,單元中的所有對(duì)象都是異常;否則,單元中的數(shù)據(jù)某一些可能是異常. 為了檢測這些異常點(diǎn),需要逐個(gè)對(duì)象加入處理. 基于距離的異常數(shù)據(jù)挖掘

10、方法要求用戶設(shè)置參數(shù)p 和d , 而尋找這些參數(shù)的合適設(shè)置可能涉及多次試探和錯(cuò)誤.,1/2,1/2,基于偏差的方法,基于偏差的異常數(shù)據(jù)挖掘方法不采用統(tǒng)計(jì)檢驗(yàn)或者基于距離的度量值來確定異常對(duì)象, 它是模仿人類的思維方式,通過觀察一個(gè)連續(xù)序列后,迅速地發(fā)現(xiàn)其中某些數(shù)據(jù)與其它數(shù)據(jù)明顯的不同來確定異常點(diǎn)對(duì)象,即使不清楚數(shù)據(jù)的規(guī)則. 基于偏差的異常點(diǎn)檢測常用兩種技術(shù):序列異常技術(shù)和OLAP 數(shù)據(jù)立方體技術(shù). 序列異常技術(shù)模仿了人類從一系列推測類似的對(duì)象中識(shí)別異常對(duì)象的方式. 它利用隱含的數(shù)據(jù)冗余. 給定n 個(gè)對(duì)象的集合S ,它建立一個(gè)子集合的序列, S1 , S2 , . , S m ,這里2 m n

11、, 由此,求出子集間的偏離程度, 即“相異度”. 該算法從集合中選擇一個(gè)子集合的序列來分析. 對(duì)于每個(gè)子集合,它確定其與序列中前一個(gè)子集合的相異度差異. 光滑因子最大的子集就是異常數(shù)據(jù)集. 這里對(duì)幾個(gè)相關(guān)概念進(jìn)行解釋:,(1) 異常集:它是偏離或異常點(diǎn)的集合, 被定義為某類對(duì)象的最小子集, 這些對(duì)象的去除會(huì)產(chǎn)生剩余集合的相異度的最大減少. (2) 相異度函數(shù):已知一個(gè)數(shù)據(jù)集, 如果兩個(gè)對(duì)象相似,相異函數(shù)返回值較小, 反之, 相異函數(shù)返回值較大;一個(gè)數(shù)據(jù)子集的計(jì)算依賴于前個(gè)子集的計(jì)算. (3) 基數(shù)函數(shù):數(shù)據(jù)集、數(shù)據(jù)子集中數(shù)據(jù)對(duì)象的個(gè)數(shù). (4) 光滑因子:從原始數(shù)據(jù)集中去除子集, 相異度減小的

12、程度, 光滑因子最大的子集就是異常點(diǎn)數(shù)據(jù)集.,特點(diǎn),基于偏差的異常數(shù)據(jù)挖掘方法的時(shí)間復(fù)雜度通常為O( n) , n為對(duì)象個(gè)數(shù). 基于偏差的異常點(diǎn)檢測方法計(jì)算性能優(yōu)異, 但由于事先并不知道數(shù)據(jù)的特性,對(duì)異常存在的假設(shè)太過理想化,因而相異函數(shù)的定義較為復(fù)雜, 對(duì)現(xiàn)實(shí)復(fù)雜數(shù)據(jù)的效果不太理想.,基于密度的方法,基于密度的異常數(shù)據(jù)挖掘是在基于密度的聚類算法基礎(chǔ)之上提出來的. 它采用局部異常因子來確定異常數(shù)據(jù)的存在與否. 它的主要思想是:計(jì)算出對(duì)象的局部異常因子,局部異常因子愈大, 就認(rèn)為它更可能異常; 反之則可能性小.,(1) 對(duì)象p的k - 距離( k - distance) :對(duì)任意的自然數(shù)k ,定

13、義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ì)象oD p ,使得d ( p , o) d ( p , o) . (2) 對(duì)象p 的k - 距離鄰域( Nk - distance) :給定p 的k - 距離k - distance ( p) , p 的k - 距離鄰域包含所有與p 的距離不超過k - distance ( p)的對(duì)象. (3) 對(duì)象p 相對(duì)于對(duì)象o 的可達(dá)距離:給定自然數(shù)k ,對(duì)象p 相對(duì)于對(duì)象o 的可

14、達(dá)距離為 reach - dist k ( p , o) = max k - distance( o) , d( p , o) . (4) 對(duì)象p的局部可達(dá)密度(Local Reachable Distance) :對(duì)象p 的局部可達(dá)密度為對(duì)象p 與它的MinPt s - 鄰域的平均可達(dá)距離的倒數(shù). 對(duì)象p 的局部異常因子表示p 的異常程度,局部異常因子愈大,就認(rèn)為它更可能異常;反之則可能性小. 簇內(nèi)靠近核心點(diǎn)的對(duì)象的算局部異常點(diǎn)因素LOF 接近于1 ,那么不應(yīng)該被認(rèn)為是局部異常. 而處于簇的邊緣或是簇的外面的對(duì)象的LOF 相對(duì)較大 .,為了更好地理解，先看一個(gè)2-D數(shù)據(jù)集的例子，如圖4所示，

15、該數(shù)據(jù)集是一個(gè)2維數(shù)據(jù)集，包含502個(gè)對(duì)象，在聚類C1中有400個(gè)對(duì)象，在聚類C2中有100個(gè)對(duì)象，此外還有2個(gè)特殊的對(duì)象O1和O2，該例中，可以看出C2形成的聚類要比C1稠密,對(duì)象Ol和02都應(yīng)被看作是C2數(shù)據(jù)集中的異常點(diǎn)，且聚類C1和聚類c2中的對(duì)象都是聚類中的數(shù)據(jù)，而不是異常點(diǎn)既然基于距離的異常點(diǎn)定義能夠統(tǒng)一異常點(diǎn)的概念，那么能否找到合適P和d，使得其滿足DB(P，d)異常點(diǎn)的定義事實(shí)上，利用DB(P，d)的定義，只能發(fā)現(xiàn)01是一個(gè)異常點(diǎn)，這是因?yàn)閷?duì)C1中的每一個(gè)對(duì)象q，找不到一個(gè)合適的參數(shù)P和d來滿足使弓最近的鄰域中的對(duì)象間的距離大于02和C2間的距離，從而保證02是異常點(diǎn)的同時(shí)又能保

16、證c2中的對(duì)象不是異常點(diǎn)從該例可看出DB(P，d)在某些特定的情況下是準(zhǔn)確和充分的，但聚類密度如果存在不同就會(huì)出現(xiàn)問題，為了解決這個(gè)問題，基于密度模型的局部異常點(diǎn)挖掘算法被提出，從而保證01和02在數(shù)據(jù)集中都是異常點(diǎn),高維數(shù)據(jù)的方法,以上幾種異常數(shù)據(jù)挖掘算法一般都是在低維數(shù)據(jù)上進(jìn)行的,對(duì)于高維數(shù)據(jù)的效果并不是很好,基于這個(gè)原因,Aggarwal 和Yu提出一個(gè)高維數(shù)據(jù)異常檢測的方法. 它把高維數(shù)據(jù)集映射到低維子空間,根據(jù)子空間映射數(shù)據(jù)的稀疏程度來確定異常數(shù)據(jù)是否存在. 高維數(shù)據(jù)的異常點(diǎn)檢測的主要思想是:首先它將數(shù)據(jù)空間的每一維分成個(gè)等深度區(qū)間. 所謂等深度區(qū)間是指將數(shù)據(jù)映射到此一維空間上后,每一區(qū)間包含相等的f = 1/的數(shù)據(jù)點(diǎn). 然后在數(shù)據(jù)集的k 維子空間中的每一維上各取一個(gè)等深度區(qū)間,組成一個(gè)k 維立方體,則立方體中的數(shù)據(jù)映射點(diǎn)數(shù)為一個(gè)隨機(jī)數(shù). 設(shè)n( D) 為k 維立方體D 所包含點(diǎn)數(shù), N 為總的點(diǎn)數(shù).,定義稀疏系數(shù)s ( D) 如式所示: s ( D) 為負(fù)數(shù)時(shí), 說明立方體D 中數(shù)據(jù)點(diǎn)低于期望值, s ( D ) 越小,說明該立方體中數(shù)據(jù)越稀疏.,數(shù)據(jù)空間的任一模式可以用m1 m2 mi 來表示. mi 指此數(shù)據(jù)在第i 維子空間映射區(qū)間,可以取值1 到,或者3 ( 3 表示可以為任意映射值) .異常檢測問題可以