《幾種常用的異常數(shù)據(jù)挖掘方法》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《幾種常用的異常數(shù)據(jù)挖掘方法（27頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,幾種常用的異常數(shù)據(jù)挖掘方法,在數(shù)據(jù)挖掘的過(guò)程中,數(shù)據(jù)庫(kù)中可能包含一些數(shù)據(jù)對(duì)象,它們與數(shù)據(jù)的一般行為或模型不一致,這些數(shù)據(jù)對(duì)象被稱(chēng)為,異常點(diǎn),對(duì)異常點(diǎn)的查找過(guò)程稱(chēng)為,異常數(shù)據(jù)挖掘,它是數(shù)據(jù)挖掘技術(shù)中的一種,.,異常數(shù)據(jù)挖掘又稱(chēng)孤立點(diǎn)分析、異常檢測(cè)、例外挖掘、小事件檢測(cè)、挖掘極小類(lèi)、偏差檢測(cè)等,.,孤立點(diǎn)可能是“臟數(shù)據(jù)”,也可能是與實(shí)際對(duì)應(yīng)的有意義的事件,.,從知識(shí)發(fā)現(xiàn)的角度看,在某些應(yīng)用里,那些很少發(fā)生的事件往往比經(jīng)常發(fā)生的事件更有趣、也更有研究?jī)r(jià)值,例外的檢測(cè)能為我們提供比較重要的信息,使我們發(fā)現(xiàn)一些真實(shí)而

2、又出乎預(yù)料的知識(shí),.,因此,異常數(shù)據(jù)的檢測(cè)和分析是一項(xiàng)重要且有意義的研究工作。,異常數(shù)據(jù)挖掘的簡(jiǎn)介,異常數(shù)據(jù)挖掘有著廣泛的應(yīng)用,如,欺詐檢測(cè),用異常點(diǎn)檢測(cè)來(lái)探測(cè)不尋常的信用卡使用或者電信服務(wù),;,預(yù)測(cè)市場(chǎng)動(dòng)向,;,在市場(chǎng)分析中分析客戶(hù)的極低或極高消費(fèi)異常行為,;,或者在醫(yī)療分析中發(fā)現(xiàn)對(duì)多種治療方式的不尋常的反應(yīng)等等,.,通過(guò)對(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ì)象,.,聚類(lèi)數(shù)據(jù)集,序列數(shù)據(jù)集

3、,圖,1,數(shù)據(jù)集中異常點(diǎn)示例,異常點(diǎn)數(shù)據(jù)挖掘的任務(wù)可以分成兩個(gè)子問(wèn)題,:,(,1,),給出已知數(shù)據(jù)集的異常點(diǎn)數(shù)據(jù)的定義,;,(,2,),使用有效的方法挖掘異常點(diǎn)數(shù)據(jù),.,對(duì)數(shù)據(jù)模式的不同定義,以及數(shù)據(jù)集的構(gòu)成不同,會(huì)導(dǎo)致不同類(lèi)型的異常點(diǎn)數(shù)據(jù)挖掘,實(shí)際應(yīng)用中根據(jù)具體情況選擇異常數(shù)據(jù)的挖掘方法,.,基于統(tǒng)計(jì)的方法,利用統(tǒng)計(jì)學(xué)方法處理異常數(shù)據(jù)挖掘的問(wèn)題已經(jīng)有很長(zhǎng)的歷史了,并有一套完整的理論和方法,.,統(tǒng)計(jì)學(xué)的方法對(duì)給定的數(shù)據(jù)集合假設(shè)了一個(gè)分布或者概率模型,(,例如正態(tài)分布,),然后根據(jù)模型采用,不一致性檢驗(yàn),來(lái)確定異常點(diǎn)數(shù)據(jù),.,不一致性檢驗(yàn)要求事先知道數(shù)據(jù)集模型參數(shù),(,如正態(tài)分布,),分布參數(shù),

4、(,如均值、標(biāo)準(zhǔn)差等,),和預(yù)期的異常點(diǎn)數(shù)目,.,不一致性檢驗(yàn)是如何進(jìn)行的,?,工作假設(shè),(working hypothesis),即零假設(shè),:,H,。：,O,F,i=,1,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ì)顯著的

5、,則,Oi,是不一致的,拒絕工作假設(shè),反之,不能拒絕假設(shè),.,對(duì)立假設(shè)是描述總體性質(zhì)的另外一種想法,認(rèn)為數(shù)據(jù),Oi,來(lái)自另一個(gè)分布模型,G.,對(duì)立假設(shè)在決定檢驗(yàn)?zāi)芰?(,即當(dāng),Oi,真的是異常點(diǎn)時(shí)工作假設(shè)被拒絕的概率,),上是非常重要的,它決定了檢驗(yàn)的準(zhǔn)確性等,.,i,1,i,目前利用統(tǒng)計(jì)學(xué)研究異常點(diǎn)數(shù)據(jù)有了一些新的方法,如通過(guò)分析統(tǒng)計(jì)數(shù)據(jù)的散度情況,即數(shù)據(jù)變異指標(biāo),來(lái)對(duì)數(shù)據(jù)的總體特征有更進(jìn)一步的了解,對(duì)數(shù)據(jù)的分布情況有所了解,進(jìn)而通過(guò)數(shù)據(jù),變異指標(biāo),來(lái)發(fā)現(xiàn)數(shù)據(jù)中的異常點(diǎn)數(shù)據(jù),.,常用的數(shù)據(jù)變異指標(biāo)有極差、四分位數(shù)間距、均差、標(biāo)準(zhǔn)差、變異系數(shù)等等,變異指標(biāo)的值大表示變異大、散布廣,;,值小表示

6、離差小,較密集,.,用統(tǒng)計(jì)學(xué)的方法檢測(cè)異常點(diǎn)數(shù)據(jù)的有效性如何呢,?,一個(gè)主要的缺點(diǎn)是絕大多數(shù)檢驗(yàn)是針對(duì)單個(gè)屬性的,而許多數(shù)據(jù)挖掘問(wèn)題要求在多維空間中發(fā)現(xiàn)異常點(diǎn)數(shù)據(jù),.,而且,統(tǒng)計(jì)學(xué)方法要求關(guān)于數(shù)據(jù)集合參數(shù)的知識(shí),例如數(shù)據(jù)分布,.,但是在許多情況下,數(shù)據(jù)分布可能是未知的,.,當(dāng)沒(méi)有特定的分布檢驗(yàn)時(shí),統(tǒng)計(jì)學(xué)方法不能確保所有的異常點(diǎn)數(shù)據(jù)被發(fā)現(xiàn),或者觀(guān)察到的分布不能恰當(dāng)?shù)乇蝗魏螛?biāo)準(zhǔn)的分布來(lái)模擬,.,0,s,基于距離的方法,什么是基于距離的異常點(diǎn)檢測(cè),?,如果數(shù)據(jù)集合,S,中獨(dú)享至少有,p,部分與對(duì)象,o,的距離大于,d,則對(duì)象,o,是一個(gè)帶參數(shù)的,p,和,d,的基于距離的,(DB),的異常點(diǎn),即,DB

7、(p,d).,換句話(huà)說(shuō),不依賴(lài)于統(tǒng)計(jì)檢驗(yàn),我們可以將基于距離的異常點(diǎn)看作是那些沒(méi)有“足夠多”鄰居的對(duì)象,這里的對(duì)象是基于距給定對(duì)象的距離來(lái)定義的,.,與基于統(tǒng)計(jì)的方法相比,基于距離的異常點(diǎn)檢測(cè)拓廣了多個(gè)標(biāo)準(zhǔn)分布的不一致性檢驗(yàn)的思想,.,基于距離的異常點(diǎn)檢測(cè)避免了過(guò)多的計(jì)算,.,d,目前比較成熟的基于距離的異常數(shù)據(jù)挖掘的算法有,:,基于索引的算法,(Index-based):,給定一個(gè)數(shù)據(jù)集合,基于索引的算法采用多維索引結(jié)構(gòu),R-,樹(shù),k-d,樹(shù)等,來(lái)查找每個(gè)對(duì)象在半徑,d,范圍內(nèi)的鄰居,.,假設(shè),M,為異常點(diǎn)數(shù)據(jù)的,d,鄰,域,內(nèi)的最大對(duì)象數(shù)目,.,如果對(duì)象,o,的,M+,1,個(gè)鄰居被發(fā)現(xiàn),則

8、對(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)算法和基于索引的算法有相同的計(jì)算復(fù)雜度,但是它避免了索引結(jié)構(gòu)的構(gòu)建,試圖最小化,I/O,的次數(shù),.,它把內(nèi)存的緩沖空間分為兩半,把數(shù)據(jù)集合分為若干個(gè)邏輯塊,.,通過(guò)精心選擇邏輯塊裝入每個(gè)緩沖區(qū)域的順序,I/O,效率能夠改善,.,2,基于單元的算法,(cell-based):,在該方法中,數(shù)據(jù)空間被劃為邊長(zhǎng)等于,d/(,2,k ),的,單元,.,每個(gè)單元有兩個(gè)層圍

9、繞著它,.,第一層的厚度是一個(gè)單元,而第二層的厚度是,2,k -,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_+_1_cell_count),單元和兩個(gè)層次中的對(duì)象的數(shù)目,(cell_+_2_cell_count).,該算法將對(duì)數(shù)據(jù)集的每一個(gè)元素進(jìn)行異常點(diǎn)數(shù)據(jù)的檢測(cè)改為對(duì)每一個(gè)單元進(jìn)行異常點(diǎn)數(shù)據(jù)的檢測(cè),它提高了算法的效率,.,它的算法復(fù)雜度是,O(ck+n),這里的,c,是依賴(lài)于單元數(shù)目的常數(shù),k,是維數(shù),.,它是這樣進(jìn)行異常檢測(cè)的,:,若,cell

10、_+_1_cell_count,M,單元中的所有對(duì)象都不是異常,;,若,cell_+_2_cell_count =,M,單元中的所有對(duì)象都是異常,;,否則,單元中的數(shù)據(jù)某一些可能是異常,.,為了檢測(cè)這些異常點(diǎn),需要逐個(gè)對(duì)象加入處理,.,基于距離的異常數(shù)據(jù)挖掘方法要求用戶(hù)設(shè)置參數(shù),p,和,d,而尋找這些參數(shù)的合適設(shè)置可能涉及多次試探和錯(cuò)誤,.,1/2,1/2,基于偏差的方法,基于偏差的異常數(shù)據(jù)挖掘方法不采用統(tǒng)計(jì)檢驗(yàn)或者基于距離的度量值來(lái)確定異常對(duì)象,它是模仿人類(lèi)的思維方式,通過(guò)觀(guān)察一個(gè)連續(xù)序列后,迅速地發(fā)現(xiàn)其中某些數(shù)據(jù)與其它數(shù)據(jù)明顯的不同來(lái)確定異常點(diǎn)對(duì)象,即使不清楚數(shù)據(jù)的規(guī)則,.,基于偏差的異常

11、點(diǎn)檢測(cè)常用兩種技術(shù),:,序列異常技術(shù),和,OLAP,數(shù)據(jù)立方體技術(shù),.,序列異常技術(shù)模仿了人類(lèi)從一系列推測(cè)類(lèi)似的對(duì)象中識(shí)別異常對(duì)象的方式,.,它利用隱含的數(shù)據(jù)冗余,.,給定,n,個(gè)對(duì)象的集合,S,它建立一個(gè)子集合的序列,S,1,S,2,.,S m ,這里,2,m,n,由此,求出子集間的偏離程度,即“相異度”,.,該算法從集合中選擇一個(gè)子集合的序列來(lái)分析,.,對(duì)于每個(gè)子集合,它確定其與序列中前一個(gè)子集合的相異度差異,.,光滑因子最大的子集就是異常數(shù)據(jù)集,.,這里對(duì)幾個(gè)相關(guān)概念進(jìn)行解釋,:,(,1,),異常集,:,它是偏離或異常點(diǎn)的集合,被定義為某類(lèi)對(duì)象的最小子集,這些對(duì)象的去除會(huì)產(chǎn)生剩余集合的相

12、異度的最大減少,.,(,2,),相異度函數(shù),:,已知一個(gè)數(shù)據(jù)集,如果兩個(gè)對(duì)象相似,相異函數(shù)返回值較小,反之,相異函數(shù)返回值較大,;,一個(gè)數(shù)據(jù)子集的計(jì)算依賴(lài)于前個(gè)子集的計(jì)算,.,(,3,),基數(shù)函數(shù),:,數(shù)據(jù)集、數(shù)據(jù)子集中數(shù)據(jù)對(duì)象的個(gè)數(shù),.,(,4,),光滑因子,:,從原始數(shù)據(jù)集中去除子集,相異度減小的程度,光滑因子最大的子集就是異常點(diǎn)數(shù)據(jù)集,.,特點(diǎn),基于偏差的異常數(shù)據(jù)挖掘方法的時(shí)間復(fù)雜度通常為,O(n),n,為對(duì)象個(gè)數(shù),.,基于偏差的異常點(diǎn)檢測(cè)方法計(jì)算性能優(yōu)異,但由于事先并不知道數(shù)據(jù)的特性,對(duì)異常存在的假設(shè)太過(guò)理想化,因而相異函數(shù)的定義較為復(fù)雜,對(duì)現(xiàn)實(shí)復(fù)雜數(shù)據(jù)的效果不太理想,.,基于密度的方

13、法,基于密度的異常數(shù)據(jù)挖掘是在基于密度的聚類(lèi)算法基礎(chǔ)之上提出來(lái)的,.,它采用局部異常因子來(lái)確定異常數(shù)據(jù)的存在與否,.,它的主要思想是,:,計(jì)算出對(duì)象的局部異常因子,局部異常因子愈大,就認(rèn)為它更可能異常,;,反之則可能性小,.,(,1,),對(duì)象,p,的,k-,距離,(k-,distance):,對(duì)任意的自然數(shù),k,定義,p,的,k-,距離,(k-,distance,(p),為,p,和某個(gè)對(duì)象,o,之間的距離,這里的,o,滿(mǎn)足,:,至少存在,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).,(,2,),對(duì)象,p,

14、的,k-,距離鄰域,(,Nk,-,distance):,給定,p,的,k-,距離,k-,distance,(p),p,的,k-,距離鄰域包含所有與,p,的距離不超過(guò),k-,distance,(p),的對(duì)象,.,(,3,),對(duì)象,p,相對(duì)于對(duì)象,o,的可達(dá)距離,:,給定自然數(shù),k,對(duì)象,p,相對(duì)于對(duì)象,o,的可達(dá)距離為,reach-dist k(p,o)=,max,k-,distan,ce(o),d(p,o).,(4),對(duì)象,p,的局部可達(dá)密度,(,Local Reachable Distance):,對(duì)象,p,的局部可達(dá)密度為對(duì)象,p,與它的,MinPt,s-,鄰域的平均可達(dá)距離的倒數(shù),.,對(duì)

15、象,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,所示，該數(shù)據(jù)集是一個(gè),2,維數(shù)據(jù)集，包含,502,個(gè)對(duì)象，在聚類(lèi),C1,中有,400,個(gè)對(duì)象，在聚類(lèi),C2,中有,100,個(gè)對(duì)象，此外還有,2,個(gè)特殊的對(duì)象,O1,和,O2,，該例中，可以看出,C2,形成的聚類(lèi)要比,C1,稠密,對(duì)象,Ol,和,02,都應(yīng)被看作是,C2,數(shù)據(jù)集中的異常點(diǎn)

16、，且聚類(lèi),C1,和聚類(lèi),c2,中的對(duì)象都是聚類(lèi)中的數(shù)據(jù)，而不是異常點(diǎn)既然基于距離的異常點(diǎn)定義能夠統(tǒng)一異常點(diǎn)的概念，那么能否找到合適,P,和,d,，使得其滿(mǎn)足,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,來(lái)滿(mǎn)足使弓最近的鄰域中的對(duì)象間的距離大于,02,和,C2,間的距離，從而保證,02,是異常點(diǎn)的同時(shí)又能保證,c2,中的對(duì)象不是異常點(diǎn)從該例可看出,DB(P,，,d),在某些特定的情況下是準(zhǔn)確和充分的，但聚類(lèi)密度如果存在不同就會(huì)出現(xiàn)問(wèn)題，為了解決這個(gè)問(wèn)題，基于密度模型的局部異常點(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ù)異常檢測(cè)的方法,.,它把高維數(shù)據(jù)集映射到低維子空間,根據(jù)子空間映射數(shù)據(jù)的稀疏程度來(lái)確定異常數(shù)據(jù)是否存在,.,高維數(shù)據(jù)的異常點(diǎn)檢測(cè)的主要思想是,:,首先它將數(shù)據(jù)空間的每