局部離群點(diǎn)挖掘算法研究_圖文

1、第30卷第8期2007年8月計(jì)算機(jī)學(xué)報(bào)C HIN ESE J OU RNAL OF COM PU TERSVol.30No.8Aug.2007收稿日期:2007203205;修改稿收到日期:2007205228.本課題得到國(guó)家自然科學(xué)基金(60603041,江蘇省高校自然科學(xué)基金(05K JB520017及江蘇省自然科學(xué)基金(B K2006073的資助.薛安榮,男,1964年生,博士研究生,副教授,主要研究方向?yàn)閿?shù)據(jù)挖掘、多媒體技術(shù)、時(shí)空數(shù)據(jù)庫(kù)及地理信息系統(tǒng).E 2mail :xuear .鞠時(shí)光,男,1955年生,博士,教授,博士生導(dǎo)師,主要研究方向?yàn)閿?shù)據(jù)庫(kù)、信息安全理論與技術(shù).何偉華,男,

2、1974年生,碩士研究生,主要研究方向?yàn)閿?shù)據(jù)挖掘.陳偉鶴,男,1974年生,博士,副教授,主要研究方向?yàn)樾畔踩?shù)據(jù)庫(kù)管理系統(tǒng)原理及實(shí)現(xiàn).局部離群點(diǎn)挖掘算法研究薛安榮鞠時(shí)光何偉華陳偉鶴(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院江蘇鎮(zhèn)江212013摘要離群點(diǎn)可分為全局離群點(diǎn)和局部離群點(diǎn).在很多情況下,局部離群點(diǎn)的挖掘比全局離群點(diǎn)的挖掘更有意義.現(xiàn)有的基于局部離群度的離群點(diǎn)挖掘算法存在檢測(cè)精度依賴于用戶給定的參數(shù)、計(jì)算復(fù)雜度高等局限.文中提出將對(duì)象屬性分為固有屬性和環(huán)境屬性,用環(huán)境屬性確定對(duì)象鄰域、固有屬性計(jì)算離群度的方法克服上述局限;并以空間數(shù)據(jù)為例,將空間屬性與非空間屬性分開(kāi),用空間屬性確定空間鄰域

3、,用非空間屬性計(jì)算空間離群度,設(shè)計(jì)了空間離群點(diǎn)挖掘算法.實(shí)驗(yàn)結(jié)果表明,所提算法具有對(duì)用戶依賴性少、檢測(cè)精度高、可伸縮性強(qiáng)和運(yùn)算效率高的優(yōu)點(diǎn).關(guān)鍵詞離群點(diǎn)檢測(cè);局部離群系數(shù);R 32樹(shù);數(shù)據(jù)挖掘;空間離群點(diǎn);剔除平均中圖法分類(lèi)號(hào)TP311Study on Algorithms for Local Outlier DetectionXU E An 2Rong J U Shi 2Guang H E Wei 2Hua CH EN Wei 2He(S chool of Com p uter Science and Telecomm unication Engineering ,J iangsu Univ

4、ersit y ,Zhenj iang ,J i angsu 212013Abstract Outlier detection has att racted much attention recently.There are two kinds of outli 2ers :global outliers and local outliers.In many scenario s ,t he detection of local outliers is more valuable t han t hat of global outliers.To mine local outliers ,it

5、 is more meaningf ul to assign to each object a degree of being an outlier.Some existing rep resentative algorit hms currently used for solving t his p roblem are compared in detail ,and t heir disadvantages are pointed out such as poor efficiency and t he detection accuracy depending on t he parame

6、ters given by t he user.In gen 2eral ,t he att ributes of each data object can be categorized as t he inherent att ributes and t he con 2text att ributes ,t he inherent att ributes characterize t he data object while t he context attributes embody t he relatio nship between t his data object and t h

7、e neighbor data object s.The context at 2t ributes is not intrinsic to t he data object.In order to overcome t hose disadvantages mentioned a 2bove ,t his paper proposes to use t he context att ributes to determine t he object neighborhood and use t he inherent att ributes to comp ute t he o utlier

8、score.For spatial data ,t he attributes comp rise t he no n 2spatial dimensions and t he spatial dimensions.The spatial att ributes provide a location index to t he data object.The neighborhood in t he Euclidean space plays a very important role in t he analysis of spatial data.The spatial att ribut

9、es are used to determine spatial neighborhood and t he non 2spatial dimensions are used to comp ute t he spatial outlier score.This paper also proposes a novel measure ,spatial local outlier factor (SLOF ,which capt ures t he local behavior of dat um in it s spatial neighborhood.The experimental res

10、ult s show t hat p roposed SLOF algorit hm out 2performs t he ot her existing algorit hms in detection accuracy ,user dependency ,scalability and ef 2ficiency.K eyw ordso utlier detection;local outlier factor;R32t ree;data mining;spatial outlier;t rimmed mean1引言離群點(diǎn)檢測(cè)是數(shù)據(jù)挖掘的基本任務(wù)之一122,故稱為離群點(diǎn)挖掘,其目的是消除噪音

11、或發(fā)現(xiàn)潛在的、有意義的知識(shí),廣泛應(yīng)用在電子商務(wù)犯罪和信用卡欺詐的偵查、網(wǎng)絡(luò)入侵檢測(cè)、生態(tài)系統(tǒng)失調(diào)檢測(cè)、公共衛(wèi)生、醫(yī)療和天文學(xué)上稀有的、未知種類(lèi)的天體發(fā)現(xiàn)等領(lǐng)域中.早期的離群點(diǎn)挖掘算法是針對(duì)全部數(shù)據(jù)集的,挖掘的是全局離群點(diǎn)1.由于現(xiàn)實(shí)世界的復(fù)雜性和多變性,所獲得的數(shù)據(jù)集往往是不完整的,而且在很多場(chǎng)合,用戶只關(guān)心局部的不穩(wěn)定,即局部離群點(diǎn).局部離群點(diǎn)挖掘需要解決局部鄰域的確定和對(duì)象與鄰域的比較計(jì)算兩個(gè)子問(wèn)題.現(xiàn)有的挖掘算法一般對(duì)對(duì)象屬性不加區(qū)分,采用對(duì)象的全部屬性來(lái)解決上述兩個(gè)子問(wèn)題,致使計(jì)算復(fù)雜度高,檢測(cè)結(jié)果難以解釋.為此,我們可以通過(guò)區(qū)分對(duì)象屬性性質(zhì),利用一部分屬性確定對(duì)象鄰域,用另一部分屬性

12、進(jìn)行對(duì)象與其鄰域間計(jì)算的比較.事實(shí)上對(duì)象包含兩類(lèi)屬性即固有屬性和環(huán)境屬性.固有屬性決定對(duì)象的性質(zhì),而環(huán)境屬性決定對(duì)象與其周?chē)h(huán)境的關(guān)系,因此可用環(huán)境屬性來(lái)確定對(duì)象的鄰域,用固有屬性進(jìn)行對(duì)象與其鄰域間計(jì)算比較.本文將以空間離群點(diǎn)的挖掘?yàn)槔?探討局部離群點(diǎn)挖掘的一般方法.在空間離群點(diǎn)挖掘中,將空間屬性與非空間屬性分開(kāi),利用空間屬性及空間關(guān)系確定空間鄰域,基于空間鄰域和非空間屬性計(jì)算對(duì)象與其鄰域的距離,進(jìn)而計(jì)算每個(gè)數(shù)據(jù)對(duì)象的空間離群度,從而解決空間離群點(diǎn)挖掘問(wèn)題,實(shí)驗(yàn)結(jié)果表明該方法比現(xiàn)有算法有效.本文第2節(jié)討論了局部離群點(diǎn)挖掘的相關(guān)研究工作,指出其局限;第3節(jié)闡述空間離群點(diǎn)挖掘算法;第4節(jié)是基于合成

13、數(shù)據(jù)和實(shí)際數(shù)據(jù)的實(shí)驗(yàn)測(cè)試與結(jié)果分析;第5節(jié)是結(jié)論與展望.2相關(guān)研究211局部離群點(diǎn)挖掘方法到目前為止,還沒(méi)有一個(gè)廣為接受的離群點(diǎn)的正式定義,但Hawkins的定義抓住了概念的精髓:“一個(gè)離群點(diǎn)是一個(gè)觀察點(diǎn),它偏離其它觀察點(diǎn)如此之大以至引起懷疑是由不同機(jī)制生成的”2.由于這個(gè)定義是基于全部數(shù)據(jù)集的,是全局離群點(diǎn)定義.定義1.局部離群點(diǎn)是指在數(shù)據(jù)集中與其鄰域表現(xiàn)不一致或大大地偏離其鄰域的觀測(cè)點(diǎn).基于密度的離群點(diǎn)的定義是在基于距離定義3的基礎(chǔ)上建立起來(lái)的,將點(diǎn)之間的距離和給定范圍內(nèi)點(diǎn)的個(gè)數(shù)這兩個(gè)參數(shù)結(jié)合起來(lái)得到“密度”的概念.Breuning等學(xué)者引入一個(gè)專門(mén)的度量單位:離群系數(shù)(Outlier F

14、actor,O F,用局部離群系數(shù)(Lo2 cal Outlier Factor,LOF來(lái)表征一個(gè)對(duì)象的局部離群程度425.定義2.局部離群度是指對(duì)象與其局部鄰域的偏離程度.自從LO F出現(xiàn)后,引起許多學(xué)者的關(guān)注,出現(xiàn)了許多離群度的度量方法,比較典型的有基于連接的離群系數(shù)(Connectivity2based Outlier Factor, COF6、多粒度偏差因子(Multi2granularity DEvi2 ation Factor,MDEF7、局部空間離群測(cè)度(Meas2 ure for Local Spatial Outlier,SLOM8等方法. 212離群度的計(jì)算現(xiàn)有的基于離群度

15、的局部離群點(diǎn)挖掘算法主要區(qū)別在于鄰域的確定方法和離群度的計(jì)算方法不同.下面將具體分析.在LO F算法5中,根據(jù)給定的參數(shù)最少鄰居數(shù)k和最近鄰距離來(lái)確定鄰域,通過(guò)計(jì)算對(duì)象的k2距離、可達(dá)距離和可達(dá)密度,用數(shù)據(jù)對(duì)象鄰域的平均可達(dá)密度與數(shù)據(jù)對(duì)象自身的可達(dá)密度之比表示LO F. LOF算法可很好地解決局部離群點(diǎn)的挖掘問(wèn)題.但該算法存在計(jì)算量大,計(jì)算結(jié)果受指定參數(shù)k影響大,如果修改k值,則需要重新構(gòu)造數(shù)學(xué)模型和重新計(jì)算等不足.在CO F算法6中,根據(jù)給定的參數(shù)最少鄰居數(shù)k和數(shù)據(jù)對(duì)象的連接性來(lái)確定鄰域,計(jì)算與其鄰域的平均連接距離,用平均連接距離比作為基于連接的離群系數(shù)COF.COF算法雖可克服LOF算法中

16、對(duì)于序列數(shù)據(jù)和低密度數(shù)據(jù)對(duì)象不能有效度量的缺陷,但仍如LOF算法那樣,存在計(jì)算復(fù)雜度高、計(jì)算結(jié)果受指定參數(shù)k影響大,如果修改k值,則需要重新構(gòu)造數(shù)學(xué)模型和重新計(jì)算的缺陷,而且COF增加了連接路徑,因此時(shí)間復(fù)雜度比LOF更高.在MDEF算法7中,有兩個(gè)鄰域概念,即r2鄰6541計(jì)算機(jī)學(xué)報(bào)2007年域和r2鄰域,其中r>0,0<<1.n(p i,r和n(p i,r分別表示以pi為圓心、r為半徑和r為半徑的圓內(nèi)的對(duì)象數(shù)目,n(p i,r,表示在p i的r2鄰域內(nèi)的所有對(duì)象p的n(p,r的平均值.MD EF的定義如下MD E F(p i,r,=n(p i,r,-n(p i,rn(p

17、i,r,=1-n(p i,rn(p i,r,(1MD EF算法的優(yōu)點(diǎn)是可以根據(jù)應(yīng)用要求設(shè)置多級(jí)鄰域,并用鄰域中包含的對(duì)象數(shù)目替代距離計(jì)算,降低了計(jì)算復(fù)雜度,但r和很難確定,為了獲得滿意結(jié)果,需要反復(fù)修改參數(shù).因此,MD EF算法的檢測(cè)結(jié)果和計(jì)算復(fù)雜度取決于用戶的經(jīng)驗(yàn).由此可見(jiàn),上述算法存在以下問(wèn)題:計(jì)算復(fù)雜度高,檢測(cè)結(jié)果的精度和重復(fù)計(jì)算的次數(shù)依賴于用戶給定的參數(shù),如指定的參數(shù)k2鄰居將決定鄰域的范圍,當(dāng)k值過(guò)小時(shí),在離群點(diǎn)彼此接近、形成一個(gè)小的離群簇的情況下,會(huì)將這個(gè)小的離群簇誤判為正常數(shù)據(jù)簇,導(dǎo)致漏檢;當(dāng)k值太大時(shí),接近稠密簇的離群點(diǎn)可能會(huì)被誤判為正常數(shù)據(jù)點(diǎn),也會(huì)導(dǎo)致漏檢.為了得到滿意結(jié)果,

18、需要反復(fù)調(diào)整參數(shù)k,而每次調(diào)整參數(shù)均須重新構(gòu)造鄰域,鄰域構(gòu)造非常費(fèi)時(shí),具有O(kn2的計(jì)算復(fù)雜度,其中k為鄰居數(shù),n為數(shù)據(jù)點(diǎn)總數(shù).為了提高檢測(cè)精度,降低復(fù)雜度,必須從模型的構(gòu)造和閾值的指定上入手,利用數(shù)據(jù)的自身特點(diǎn),減少算法對(duì)用戶的依賴性.實(shí)際上,一個(gè)數(shù)據(jù)對(duì)象的存在包含兩類(lèi)不同性質(zhì)的屬性,一類(lèi)是對(duì)象固有的本質(zhì)屬性,決定了對(duì)象的性質(zhì);另一類(lèi)是對(duì)象存在的外部環(huán)境,我們稱之為環(huán)境屬性,如對(duì)象存在的時(shí)間、空間位置.環(huán)境屬性決定了對(duì)象與其外部的關(guān)聯(lián),可用這類(lèi)屬性來(lái)確定對(duì)象的鄰域,而用固有屬性來(lái)計(jì)算對(duì)象的離群度.在空間離群點(diǎn)挖掘算法中,可將屬性分為空間屬性和非空間屬性8210,利用空間屬性和空間關(guān)系確定空

19、間鄰域,利用非空間屬性進(jìn)行計(jì)算比較.此外對(duì)于大量空間數(shù)據(jù),一般用R32樹(shù)11索引來(lái)加快檢索速度,設(shè)s為R32樹(shù)中每個(gè)索引結(jié)點(diǎn)的最少項(xiàng)數(shù),此時(shí)確定空間鄰居的計(jì)算復(fù)雜度為O(n(k log s n,與O(kn2相比大為降低.SLOM算法8就是其中一例.在SLOM算法8中,將數(shù)據(jù)對(duì)象的屬性分為空間屬性和非空間屬性,利用空間屬性及空間鄰接關(guān)系確定對(duì)象的鄰域,以鄰域距離d和波動(dòng)因子的乘積為空間局部離群度,即S L OM=d×.SLOM算法與上述其它算法相比,在鄰域的確定上不再依賴用戶輸入的參數(shù),可從數(shù)據(jù)自身特點(diǎn)出發(fā),利用空間數(shù)據(jù)的空間屬性和空間關(guān)系確定空間鄰域,解決了鄰域的確定依賴于用戶輸入的

20、參數(shù)和由此帶來(lái)的反復(fù)計(jì)算問(wèn)題.利用空間索引技術(shù),可極大地縮小數(shù)據(jù)搜索范圍,減少對(duì)數(shù)據(jù)的訪問(wèn)次數(shù),從而提高算法的效率.但在SLOM算法8中,由于波動(dòng)因子僅由對(duì)稱分布狀況來(lái)決定,在空間鄰居較少或波動(dòng)幅度較小的情況下難以準(zhǔn)確表現(xiàn)波動(dòng)情況,因此出現(xiàn)較高的漏檢和誤檢現(xiàn)象,甚至挖掘的不是局部離群點(diǎn),而是全局離群點(diǎn).為此,我們提出了基于空間局部離群系數(shù)(Spatial Local Outlier Factor,SLO F的新的空間離群點(diǎn)挖掘算法.3基于SLOF的空間離群點(diǎn)挖掘算法311SLOF的計(jì)算假設(shè)對(duì)象集O=o1,o2,o n由n個(gè)對(duì)象組成,對(duì)象oO的空間屬性函數(shù)是s(o,非空間屬性函數(shù)是f(o,f(o

21、的維度為d2維,c表示在指定條件c下的空間鄰接關(guān)系.d2維非空間屬性f(o表示為(f(o1,f(o2,f(o d.定義3(空間鄰居.對(duì)象o的空間鄰居是指與對(duì)象o在指定條件c下,存在空間鄰接關(guān)系c的對(duì)象.即oO,pOo,使得s(pc s(o為真,則對(duì)象p是對(duì)象o的空間鄰居.定義4(空間鄰域.對(duì)象o的空間鄰域N(o是指對(duì)象o的所有空間鄰居的集合,即oO, N(o=p|s(pc s(o=true,pOo.定義5(加權(quán)距離.設(shè)o i,o jO,o i和o j的d2維非空間屬性是f(o i和f(o j,其中f(o ik和f(o jk是第k(k=1,2,d維規(guī)一化屬性,且0f(o ik,f(o jk1,w

22、 k是第k維的權(quán)值,且0w k1,則數(shù)據(jù)對(duì)象o i和o j之間的加權(quán)距離為dist(o i,o j,w=dk=1w k(f(o ik-f(o jk2(2其中,dk=1w k=1.值得注意的是,這里的對(duì)象間距離不是對(duì)象間的空間距離,而是對(duì)象間的d2維非空間屬性距離.根據(jù)分析需要,如果不同屬性對(duì)分析目標(biāo)的貢獻(xiàn)程度不同,則分配的權(quán)值也不同,貢獻(xiàn)率大的權(quán)值大,75418期薛安榮等:局部離群點(diǎn)挖掘算法研究反之則小,權(quán)值一般由領(lǐng)域?qū)＜覜Q定.定義6(鄰域距離.對(duì)象o 的鄰域距離是指對(duì)象o 與其空間鄰域中所有對(duì)象的加權(quán)距離的平均值,即N dist (o,w =p N (o dist (p ,o ,w |N (

23、o |(3為了消除鄰域中極值對(duì)鄰域距離計(jì)算的影響,采用剔除平均的方法12,先剔除鄰域中的極值距離,然后再計(jì)算對(duì)象與鄰域的平均距離.設(shè)對(duì)象o 的鄰域?qū)ο髷?shù)為|N (o |,將對(duì)象o 與鄰域中所有對(duì)象的距離由小到大排序,dist (p i ,o,w ,p i N (o o|N (o |i =1,剔除極大、極小值的比率為%,一般取=520,r =%|N (o |,因此修改式(3為N dist (o,w =n -r i =r +1dist (pi,o,w |N (o |-2r(4由離群點(diǎn)定義可知,對(duì)象與鄰域中離群點(diǎn)的距離最大,通過(guò)式(4剔除極值距離后求均值,可避免因離群點(diǎn)的影響正常數(shù)據(jù)被誤檢為離群點(diǎn).

24、將對(duì)象的鄰域距離與其空間鄰居進(jìn)行比較得到對(duì)象在局部空間上的偏離程度,即為空間局部離群系數(shù).定義7(空間局部離群系數(shù).對(duì)象o 的空間局部離群系數(shù)定義為SL O F (o =N dist (o,w p N (o N dist (p ,w |N (o |(5為了避免S L O F 計(jì)算中分母為0的情況,設(shè)為非常小的正數(shù),分子、分母同時(shí)加上,則式(5修改為SL O F (o =N dist (o ,w +p N (o N dist (p ,w |N (o |+(6S L O F 表示對(duì)象在局部空間上的離群程度,計(jì)算所有對(duì)象的S L O F ,并按降序排列,離群度最大的前m 個(gè)對(duì)象就是所求的空間離群點(diǎn).

25、可以證明只要取足夠小,就能保證加后不改變S L O F 的原有順序,限于篇幅這里省去證明.定義8(空間離群點(diǎn).給定n 個(gè)對(duì)象集O ,希望挖掘m 個(gè)離群點(diǎn),計(jì)算每個(gè)對(duì)象的S L O F ,S L O F 最大的m 個(gè)對(duì)象就是空間離群點(diǎn).由于式(2(6的計(jì)算中,所有非空間屬性均規(guī)一化到0,1區(qū)間上,且dk =1w k =1,所以0N dist (o,w 1,故有1+S L O F (o 1+,的取值將決定S L O F 的取值范圍.當(dāng)對(duì)象的鄰域距離=0時(shí),表示對(duì)象與其鄰域的非空間屬性值相同,S L O F =0;當(dāng)對(duì)象的鄰域距離與鄰域?qū)ο蟮钠骄徲蚓嚯x相同時(shí),表示對(duì)象的非空間屬性在有規(guī)律地變化,S

26、 L O F =1.所以當(dāng)S L O F (o 1時(shí),對(duì)象o 正常.當(dāng)S L O F >1時(shí),對(duì)象開(kāi)始離群,隨著S L O F 值的增大,其離群度也增大.實(shí)驗(yàn)中,取=min (min N dist (o 0,o O,時(shí)(其中為最小的計(jì)算精度要求,可滿足要求.312SLOF 的算法輸入:對(duì)象集O =o 1,o 2,o n 對(duì)象o i (s (o i ,f (o i 的空間屬性為s (o i ,非空間屬性為f (o i ,d 2維非空間屬性f (o i 表示為(f (o i 1,f (o i 2,f (o i d ;c 表示在指定條件c 下的空間鄰接關(guān)系,離群點(diǎn)個(gè)數(shù)m輸出:空間離群點(diǎn)集算法過(guò)

27、程:1.根據(jù)對(duì)象的空間屬性s (o 和空間關(guān)系,確定每個(gè)空間對(duì)象的空間鄰域;2.規(guī)一化每個(gè)對(duì)象的非空間屬性值.設(shè)max j 和min j 是第j 維非空間屬性的最大和最小值,f (o i j 是對(duì)象o i 的第j 維非空間屬性值,f (o i j =(f (o i j -min j /(max j -min j ,從而保證f (o i j 在0,1區(qū)間內(nèi);3.計(jì)算每個(gè)對(duì)象與其空間鄰域間的距離.先運(yùn)用式(2計(jì)算對(duì)象與其鄰域中所有對(duì)象的距離;再運(yùn)用式(4計(jì)算對(duì)象與其鄰域的距離;4.運(yùn)用式(6計(jì)算每個(gè)空間對(duì)象的空間局部離群系數(shù)SL O F;5.根據(jù)空間離群系數(shù)SL O F 將對(duì)象按降序排序;6.輸出

28、前m 個(gè)對(duì)象,前m 個(gè)對(duì)象就是空間離群點(diǎn).313算法復(fù)雜度分析在上述算法中,鄰域的確定是非常費(fèi)時(shí)的,但由于是空間數(shù)據(jù),利用空間特性及空間索引R 32樹(shù)來(lái)確定空間鄰域,其計(jì)算復(fù)雜度大為降低.假設(shè)空間數(shù)據(jù)對(duì)象數(shù)目為n ,非空間屬性維度為d 維,對(duì)象的鄰居數(shù)為k (k 可變,s 為R 32樹(shù)中每個(gè)索引結(jié)點(diǎn)的最少項(xiàng)數(shù),則確定空間鄰居的計(jì)算復(fù)雜度為O (n (k log s n ;規(guī)一化非空間屬性為0,1的復(fù)雜度為O (dn ;計(jì)算對(duì)象與其鄰域距離的復(fù)雜度為O (n (k log s n +k d ;計(jì)算S L O F 的復(fù)雜度是O (n (k log s n ;排序的計(jì)算復(fù)雜度為O (n log 2n

29、 ;取前m 個(gè)離群對(duì)象并輸出的復(fù)雜度是O (m .故總的復(fù)雜度為O (n (k log s n +k d +log 2n ,當(dāng)d n 時(shí),算法的復(fù)雜度為O (kn log n .本算法與SLOM 算法復(fù)雜度相當(dāng),但對(duì)于高維數(shù)據(jù),由于LO F 等算法采用全部屬性確定鄰8541計(jì)算機(jī)學(xué)報(bào)2007年域和進(jìn)行比較計(jì)算,沒(méi)有合適的索引結(jié)構(gòu)可用,其算法的復(fù)雜度為O(kn2,因此采用屬性二分算法的效率比采用全部屬性算法的效率高.4實(shí)驗(yàn)結(jié)果與分析411合成數(shù)據(jù)集測(cè)試結(jié)果與分析下面對(duì)Z2Score9、SLOM8和SLOF算法進(jìn)行比較.圖1是一個(gè)30行×2列的數(shù)據(jù)點(diǎn),X軸是數(shù)據(jù)點(diǎn)位置(這里假設(shè)空間維是一

30、維,Y軸是屬性值(非空間屬性值,假設(shè)也是一維,圖2圖4是以圖1中數(shù)據(jù)為基本數(shù)據(jù)的檢測(cè)結(jié)果.從空間離群點(diǎn)定義9可知,圖1中S點(diǎn)和G點(diǎn)是離群點(diǎn),且S點(diǎn)的離群程度最高.Z2Score算法9是將對(duì)象的屬性值與其鄰域的平均屬性值的差:S(x=f(x-E yN(x(f(y作為比較函數(shù),利用判別式Z S(x i=S(x i-SS>來(lái)確定數(shù)據(jù)對(duì)象是否為空間離群點(diǎn),其中s和s分別是差函數(shù)S(x的均值和標(biāo)準(zhǔn)差,為給定的閾值,一般為3.圖2是Z2Score算法對(duì)圖1中數(shù)據(jù)的檢測(cè)結(jié)果.若=3,則圖中的S點(diǎn)是空間離群點(diǎn).圖3是SLOM算法對(duì)圖1中數(shù)據(jù)的檢測(cè)結(jié)果.圖3中的A點(diǎn)和S點(diǎn)是空間離群點(diǎn).圖4是SLOF 算法

31、對(duì)圖1中數(shù)據(jù)的檢測(cè)結(jié)果.圖4中將S L O F-1,且當(dāng)S L O F0時(shí),令S L O F=0,S點(diǎn)是空間離群點(diǎn).從實(shí)驗(yàn)結(jié)果可以看到:(1在用戶依賴性方面.Z2Score算法的檢測(cè)結(jié)果依賴于用戶,如=3時(shí),S點(diǎn)為空間離群點(diǎn),若=415時(shí),則沒(méi)有空間離群點(diǎn),若=118時(shí),則 S,Q,A點(diǎn)均是空間離群點(diǎn).而SLOM和SLO F算法只需要將前m個(gè)最離群的對(duì)象提供給用戶,用戶可根據(jù)實(shí)際需要選取.(2計(jì)算復(fù)雜度.由于三種算法有效利用了空間屬性和空間關(guān)系來(lái)確定空間鄰域,極大改善了算法的復(fù)雜度,算法復(fù)雜度均為O(kn log n.(3檢測(cè)精度.從表1和圖1圖4可以看出,我們所提算法SLOF的檢測(cè)精度最高,

32、不僅正確檢測(cè)出空間離群點(diǎn)S,也準(zhǔn)確給出了其它數(shù)據(jù)對(duì)象的離群順序;Z2Score算法正確檢測(cè)出空間離群點(diǎn)S,但G點(diǎn)的離群順序未能正確給出;SLOM算法未能正確給出空間離群點(diǎn)S的順序,其主要原因就是因?yàn)猷従訑?shù)太少影響了擺動(dòng)因子的有效性.95418期薛安榮等:局部離群點(diǎn)挖掘算法研究1460 計(jì) 算 機(jī) 學(xué) 報(bào) 表1 檢測(cè)結(jié)果比較 2007 年 序號(hào) 1 2 標(biāo)準(zhǔn) S G 檢測(cè)精度 100 % ( 4 可伸縮性 . Z2Score 算法僅適用于 1 維非空 間屬性 ,而 SL OM 、 O F 算法可應(yīng)用于多維非空間 SL 屬性 ,所有 SL OM 、 O F 算法具有更好的伸縮性 . SL 綜上所述

33、 , SL OM 、 O F 算法在用戶的依賴性 SL 和可伸縮性上均好于 Z2Sco re 算法 , 代表了檢測(cè)算 法的發(fā)展方向 , 在檢測(cè)精度上 SL O F 算法又優(yōu)于 SL OM 算法 . 41 2 實(shí)際數(shù)據(jù)集測(cè)試結(jié)果與分析 使用美國(guó)人口調(diào)查局網(wǎng)站 的人口統(tǒng)計(jì)和預(yù)測(cè) 縣名稱 ( 屬性值/ % Bexar , TX (01 1503 ,01 1639 ,01 1687 ,01 04755 ,01 6727 ,01 8622 L ubbock , TX (01 0253 ,01 0255 ,01 0312 , 01 0049 ,01 6263 ,01 7774 Tul sa , O K (

34、01 0573 ,01 0611 ,01 0895 , 01 0206 ,01 5958 ,01 7208 J efferson , KY (01 0704 ,01 0641 ,01 1194 , 01 0169 ,01 6195 ,01 7915 Allen , IN (01 0344 ,01 0339 ,01 0461 ,01 0101 ,01 6255 ,01 7951 SLO F 值 171 24 131 37 111 44 111 23 101 36 Z2Score S Q SLOM A S SLO F S G 權(quán)值 70 % 30 % 100 % 70 % 30 % 100 % 表

35、2 SLOF 算法挖掘的 5 個(gè)離群點(diǎn)及其鄰居 鄰居 Kendall , TX Comal , TX Bandera , TX Guadalupe , TX Medina , TX Wilson , TX Atasco sa , TX Lamb , TX Hale , TX Floyd , TX Cro sby , TX Hockley , TX Garza , TX Lynn , TX Terry , TX Washington , O K Osage , O K Rogers , O K Pawnee , O K Creek , O K Wagoner , O K Okmulgee , O

36、 K Clark , IN Oldham , KY Harrison , IN Floyd , IN Shelby , KY Spencer , KY Bullitt , KY Hardin , KY De Kalb , IN Noble , IN Defiance ,O H Whitley , IN Paulding ,O H Huntington , IN Van Wert ,O H Adams , IN Wells , IN 數(shù)據(jù) , 包括美國(guó)所有縣的空間和非空間信息 . 2 2維空 間信息用于定義空間鄰域 . 對(duì)于每一個(gè)縣 , 所有與其 直接接壤的縣組成其鄰域 . 選擇 6 2維非空間

37、屬性 : POPESTIMATE2004 , BIRTHS2004 , DEATHS2004 , IN TERNATIONALMIG2004 Net , IN TERNALMIG 2 2004 ,RESIDUAL 2004. 8 表 2表 4 分別是基于 SL O F 算法 、 OM 算 SL 10 法 和 L C K 算法 求得的最離群的 5 個(gè)離群點(diǎn) . 從表中可以看出 , SL OM 算法和 L C K 算法求得的 5 個(gè)離群點(diǎn)中有 4 個(gè)是相同的 , 而且前兩個(gè)完全一樣 , 但與 SL O F 算法求得的完全不同 , 從表 2 表 4 中 可以看出 , 所標(biāo)出的 11 個(gè)離群點(diǎn)確實(shí)是離

38、群點(diǎn) , 究 竟哪種算法取得的結(jié)果更準(zhǔn)確呢 ?那就要從離群程 度上 分 析 . 圖 5 和 圖 6 分 別 是 SL O F 算 法 及 SL OM 屬性值/ % (01 0027 ,01 0021 ,01 0043 ,01 0022 ,01 6380 ,01 7668 (01 0092 ,01 0071 ,01 0128 ,01 0029 ,01 6538 ,01 7173 (01 0020 ,01 0014 ,01 0023 ,01 0020 ,01 6353 ,01 7686 (01 0100 ,01 0078 ,01 0110 ,01 0037 ,01 6445 ,01 7403 (0

39、1 0042 ,01 0036 ,01 0050 ,01 0019 ,01 6362 ,01 7650 (01 0037 ,01 0027 ,01 0044 ,01 0019 ,01 6407 ,01 7615 (01 0043 ,01 0041 ,01 0046 ,01 0021 ,01 6370 ,01 7615 (01 0015 ,01 0016 ,01 0030 ,01 0020 ,01 6326 ,01 7686 (01 0036 ,01 0038 ,01 0047 ,01 0027 ,01 6341 ,01 7721 (01 0007 ,01 0008 ,01 0009 ,01 0

40、018 ,01 6327 ,01 7668 (01 0007 ,01 0006 ,01 0009 ,01 0018 ,01 6331 ,01 7650 (01 0023 ,01 0021 ,01 0037 ,01 0021 ,01 6328 ,01 7703 (01 0005 ,01 0004 ,01 0008 ,01 0018 ,01 6341 ,01 7686 (01 0006 ,01 0006 ,01 0009 ,01 0018 ,01 6334 ,01 7668 (01 0013 ,01 0013 ,01 0015 ,01 0023 ,01 6332 ,01 7668 (01 0049

41、 ,01 0038 ,01 0099 ,01 0025 ,01 6332 ,01 7686 (01 0045 ,01 0031 ,01 0073 ,01 0020 ,01 6334 ,01 7845 (01 0079 ,01 0062 ,01 0107 ,01 0021 ,01 6417 ,01 7615 (01 0017 ,01 0014 ,01 0032 ,01 0018 ,01 6335 ,01 7703 (01 0069 ,01 0056 ,01 0138 ,01 0019 ,01 6330 ,01 7774 (01 0063 ,01 0050 ,01 0069 ,01 0022 ,0

42、1 6389 ,01 7668 (01 0040 ,01 0036 ,01 0076 ,01 0019 ,01 6336 ,01 7703 (01 0101 ,01 0085 ,01 0173 ,01 0027 ,01 6385 ,01 7827 (01 0052 ,01 0035 ,01 0046 ,01 0020 ,01 6405 ,01 7597 (01 0037 ,01 0030 ,01 0054 ,01 0019 ,01 6366 ,01 7703 (01 0072 ,01 0054 ,01 0124 ,01 0019 ,01 6344 ,01 7845 (01 0037 ,01 0

43、036 ,01 0045 ,01 0032 ,01 6383 ,01 7633 (01 0015 ,01 0013 ,01 0011 ,01 0018 ,01 6359 ,01 7650 (01 0067 ,01 0050 ,01 0065 ,01 0018 ,01 6407 ,01 7562 (01 0097 ,01 0104 ,01 0116 ,01 0025 ,01 6308 ,01 7739 (01 0042 ,01 0038 ,01 0058 ,01 0019 ,01 6346 ,01 7721 (01 0048 ,01 0045 ,01 0067 ,01 0034 ,01 6330

44、 ,01 7756 (01 0039 ,01 0032 ,01 0053 ,01 0019 ,01 6325 ,01 7650 (01 0032 ,01 0027 ,01 0048 ,01 0019 ,01 6340 ,01 7739 (01 0020 ,01 0012 ,01 0031 ,01 0018 ,01 6327 ,01 7650 (01 0038 ,01 0031 ,01 0066 ,01 0019 ,01 6326 ,01 7703 (01 0029 ,01 0023 ,01 0055 ,01 0018 ,01 6336 ,01 7686 (01 0034 ,01 0040 ,0

45、1 0051 ,01 0018 ,01 6326 ,01 7633 (01 0028 ,01 0019 ,01 0040 ,01 0018 ,01 6336 ,01 7703 http :/ / www. census. gov/ OL 由 L u Chang2 Tien ,Chen Dechang 和 Kou Yufeng 三位學(xué)者 提出 ,簡(jiǎn)稱為 L C K 算法 . 8期 薛安榮等 : 局部離群點(diǎn)挖掘算法研究 表 3 SLOM 算法挖掘的 5 個(gè)離群點(diǎn)及其鄰居 縣名稱 ( 屬性值/ % Lo s Angeles , CA (1 , 1 , 1 , 1 , 0 , 01 682 縣名稱 (

46、 屬性值/ % Lo s Angeles , CA (1 , 1 , 1 , 1 , 0 , 01 682 SLOM 值 11 36 11 168 01 483 01 386 01 326 942 809 770 667 1461 Coo k , IL (01 5361 ,01 5310 ,01 7630 ,01 4409 ,01 0897 ,01 1714 Harris , TX (01 3667 ,01 4374 ,01 3445 ,01 3631 ,01 4619 ,01 9929 Maricopa , AZ (01 3523 ,01 3866 ,01 3915 ,01 2599 ,01

47、 9123 ,01 4894 Dallas , TX (01 2309 ,01 2828 ,01 2311 ,01 2901 ,01 3864 ,01 4382 Coo k , IL (01 5361 ,01 5310 ,01 7630 ,01 4409 ,01 0897 ,01 1714 Maricopa , AZ (01 3523 ,01 3866 ,01 3915 ,01 2599 ,01 9123 ,01 4894 Miami2Dade , FL (01 2378 ,01 2237 ,01 3099 ,01 4146 ,01 4740 ,01 6678 Harris , TX (01

48、3667 ,01 4374 ,01 3445 ,01 3631 ,01 4619 ,01 9929 表 4 LCK 算法挖掘的 5 個(gè)離群點(diǎn)及其鄰居 Mahanobis 距離 鄰居 屬性值/ % 1611 San Bernardinol , CA (01 1933 ,01 1994 ,01 1960 ,01 0780 ,01 8125 ,01 4876 (01 0739 ,01 0818 ,01 0867 ,01 0348 ,01 6929 ,01 7014 Kern , CA (01 0803 ,01 0762 ,01 0804 ,01 0455 ,01 6111 ,01 8163 Vent

49、 ura , CA (01 3006 ,01 2905 ,01 2866 ,01 2798 ,01 4825 ,01 6890 Orange , CA Lake , IL Mc Henry , IL Kane , IL DuPage , IL Will , IL Lake , IN Yavapai , A Z Gila , A Z La Paz , AZ Pinal , AZ Yuma , AZ Pima , AZ Collier , FL Broward , FL Monroe , FL Mont go mery , TX Libert y , TX Waller , TX Chambers

50、 , TX Fort , TX Brazoria , TX Galveston , TX (01 0697 ,01 0665 ,01 0664 ,01 0420 ,01 6361 ,01 9240 (01 0298 ,01 0262 ,01 0273 ,01 0100 ,01 6582 ,01 8163 (01 0475 ,01 0527 ,01 0455 ,01 0337 ,01 6640 ,01 7880 (01 0934 ,01 0820 ,01 0994 ,01 0601 ,01 5904 ,01 7633 (01 0618 ,01 0576 ,01 0561 ,01 0142 ,01

51、 7532 ,01 5760 (01 0494 ,01 0461 ,01 0822 ,01 0086 ,01 6330 ,01 8286 (01 0192 ,01 0132 ,01 0344 ,01 0056 ,01 6654 ,01 6767 (01 0052 ,01 0052 ,01 0114 ,01 0023 ,01 6333 ,01 7739 (01 0020 ,01 0015 ,01 0035 ,01 0024 ,01 6345 ,01 7650 (01 0216 ,01 0187 ,01 0291 ,01 0084 ,01 6784 ,01 6484 (01 0177 ,01 02

52、17 ,01 0196 ,01 0135 ,01 6459 ,01 7350 (01 0913 ,01 0836 ,01 1290 ,01 0370 ,01 6745 ,01 7862 (01 0298 ,01 0243 ,01 0403 ,01 0286 ,01 6704 ,01 6201 (01 1766 ,01 1542 ,01 2814 ,01 1637 ,01 6500 ,01 9735 (01 0079 ,01 0049 ,01 0126 ,01 0061 ,01 6276 ,01 7827 (01 0365 ,01 0340 ,01 0351 ,01 0147 ,01 7075

53、,01 6219 (01 0075 ,01 0071 ,01 0114 ,01 0030 ,01 6349 ,01 7809 (01 0035 ,01 0036 ,01 0039 ,01 0029 ,01 6324 ,01 7686 (01 0028 ,01 0027 ,01 0031 ,01 0024 ,01 6361 ,01 7650 (01 0445 ,01 0384 ,01 0265 ,01 0221 ,01 7239 ,01 5654 (01 0273 ,01 0289 ,01 0281 ,01 0097 ,01 6557 ,01 7438 (01 0273 ,01 0256 ,01

54、 0393 ,01 0106 ,01 6478 ,01 7703 鄰居 屬性值/ % San Bernardinol , CA (01 1933 ,01 1994 ,01 1960 ,01 0780 ,01 8125 ,01 4876 (01 0739 ,01 0818 ,01 0867 ,01 0348 ,01 6929 ,01 7014 Kern , CA (01 0803 ,01 0762 ,01 0804 ,01 0455 ,01 6111 ,01 8163 Vent ura , CA (01 3006 ,01 2905 ,01 2866 ,01 2798 ,01 4825 ,01 6

55、890 Orange , CA Lake , IL Mc Henry , IL Kane , IL DuPage , IL Will , IL Lake , IN Mont go mery , TX Libert y , TX Waller , TX Chambers , TX Fort , TX Brazoria , TX Galveston , TX Yavapai , A Z Gila , A Z La Paz , AZ Pinal , AZ Yuma , AZ Pima , AZ Denton , TX Collin , TX Tarrant , TX Rockwall , TX Ka

56、uf man , TX Ellis , TX (01 0697 ,01 0665 ,01 0664 ,01 0420 ,01 6361 ,01 9240 (01 0298 ,01 0262 ,01 0273 ,01 0100 ,01 6582 ,01 8163 (01 0475 ,01 0527 ,01 0455 ,01 0337 ,01 6640 ,01 7880 (01 0934 ,01 0820 ,01 0994 ,01 0601 ,01 5904 ,01 7633 (01 0618 ,01 0576 ,01 0561 ,01 0142 ,01 7532 ,01 5760 (01 049

57、4 ,01 0461 ,01 0822 ,01 0086 ,01 6330 ,01 8286 (01 0365 ,01 0340 ,01 0351 ,01 0147 ,01 7075 ,01 6219 (01 0075 ,01 0071 ,01 0114 ,01 0030 ,01 6349 ,01 7809 (01 0035 ,01 0036 ,01 0039 ,01 0029 ,01 6324 ,01 7686 (01 0028 ,01 0027 ,01 0031 ,01 0024 ,01 6361 ,01 7650 (01 0445 ,01 0384 ,01 0265 ,01 0221 ,

58、01 7239 ,01 5654 (01 0273 ,01 0289 ,01 0281 ,01 0097 ,01 6557 ,01 7438 (01 0273 ,01 0256 ,01 0393 ,01 0106 ,01 6478 ,01 7703 (01 0192 ,01 0132 ,01 0344 ,01 0056 ,01 6654 ,01 6767 (01 0052 ,01 0052 ,01 0114 ,01 0023 ,01 6333 ,01 7739 (01 0020 ,01 0015 ,01 0035 ,01 0024 ,01 6345 ,01 7650 (01 0216 ,01 0187 ,01 0291 ,01 0084 ,01 6784 ,01 6484