局部離群點挖掘算法研究_圖文

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

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

3、,用非空間屬性計算空間離群度,設(shè)計了空間離群點挖掘算法.實驗結(jié)果表明,所提算法具有對用戶依賴性少、檢測精度高、可伸縮性強和運算效率高的優(yōu)點.關(guān)鍵詞離群點檢測;局部離群系數(shù);R 32樹;數(shù)據(jù)挖掘;空間離群點;剔除平均中圖法分類號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引言離群點檢測是數(shù)據(jù)挖掘的基本任務(wù)之一122,故稱為離群點挖掘,其目的是消除噪音

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

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

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

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

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

16、對于序列數(shù)據(jù)和低密度數(shù)據(jù)對象不能有效度量的缺陷,但仍如LOF算法那樣,存在計算復(fù)雜度高、計算結(jié)果受指定參數(shù)k影響大,如果修改k值,則需要重新構(gòu)造數(shù)學(xué)模型和重新計算的缺陷,而且COF增加了連接路徑,因此時間復(fù)雜度比LOF更高.在MDEF算法7中,有兩個鄰域概念,即r2鄰6541計算機學(xué)報2007年域和r2鄰域,其中r>0,0<<1.n(p i,r和n(p i,r分別表示以pi為圓心、r為半徑和r為半徑的圓內(nèi)的對象數(shù)目,n(p i,r,表示在p i的r2鄰域內(nèi)的所有對象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)點是可以根據(jù)應(yīng)用要求設(shè)置多級鄰域,并用鄰域中包含的對象數(shù)目替代距離計算,降低了計算復(fù)雜度,但r和很難確定,為了獲得滿意結(jié)果,需要反復(fù)修改參數(shù).因此,MD EF算法的檢測結(jié)果和計算復(fù)雜度取決于用戶的經(jīng)驗.由此可見,上述算法存在以下問題:計算復(fù)雜度高,檢測結(jié)果的精度和重復(fù)計算的次數(shù)依賴于用戶給定的參數(shù),如指定的參數(shù)k2鄰居將決定鄰域的范圍,當(dāng)k值過小時,在離群點彼此接近、形成一個小的離群簇的情況下,會將這個小的離群簇誤判為正常數(shù)據(jù)簇,導(dǎo)致漏檢;當(dāng)k值太大時,接近稠密簇的離群點可能會被誤判為正常數(shù)據(jù)點,也會導(dǎo)致漏檢.為了得到滿意結(jié)果,

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

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

20、參數(shù)和由此帶來的反復(fù)計算問題.利用空間索引技術(shù),可極大地縮小數(shù)據(jù)搜索范圍,減少對數(shù)據(jù)的訪問次數(shù),從而提高算法的效率.但在SLOM算法8中,由于波動因子僅由對稱分布狀況來決定,在空間鄰居較少或波動幅度較小的情況下難以準(zhǔn)確表現(xiàn)波動情況,因此出現(xiàn)較高的漏檢和誤檢現(xiàn)象,甚至挖掘的不是局部離群點,而是全局離群點.為此,我們提出了基于空間局部離群系數(shù)(Spatial Local Outlier Factor,SLO F的新的空間離群點挖掘算法.3基于SLOF的空間離群點挖掘算法311SLOF的計算假設(shè)對象集O=o1,o2,o n由n個對象組成,對象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(空間鄰居.對象o的空間鄰居是指與對象o在指定條件c下,存在空間鄰接關(guān)系c的對象.即oO,pOo,使得s(pc s(o為真,則對象p是對象o的空間鄰居.定義4(空間鄰域.對象o的空間鄰域N(o是指對象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ù)對象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.值得注意的是,這里的對象間距離不是對象間的空間距離,而是對象間的d2維非空間屬性距離.根據(jù)分析需要,如果不同屬性對分析目標(biāo)的貢獻程度不同,則分配的權(quán)值也不同,貢獻率大的權(quán)值大,75418期薛安榮等:局部離群點挖掘算法研究反之則小,權(quán)值一般由領(lǐng)域?qū)＜覜Q定.定義6(鄰域距離.對象o 的鄰域距離是指對象o 與其空間鄰域中所有對象的加權(quán)距離的平均值,即N dist (o,w =p N (o dist (p ,o ,w |N (

23、o |(3為了消除鄰域中極值對鄰域距離計算的影響,采用剔除平均的方法12,先剔除鄰域中的極值距離,然后再計算對象與鄰域的平均距離.設(shè)對象o 的鄰域?qū)ο髷?shù)為|N (o |,將對象o 與鄰域中所有對象的距離由小到大排序,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由離群點定義可知,對象與鄰域中離群點的距離最大,通過式(4剔除極值距離后求均值,可避免因離群點的影響正常數(shù)據(jù)被誤檢為離群點.

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

25、可以證明只要取足夠小,就能保證加后不改變S L O F 的原有順序,限于篇幅這里省去證明.定義8(空間離群點.給定n 個對象集O ,希望挖掘m 個離群點,計算每個對象的S L O F ,S L O F 最大的m 個對象就是空間離群點.由于式(2(6的計算中,所有非空間屬性均規(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)對象的鄰域距離=0時,表示對象與其鄰域的非空間屬性值相同,S L O F =0;當(dāng)對象的鄰域距離與鄰域?qū)ο蟮钠骄徲蚓嚯x相同時,表示對象的非空間屬性在有規(guī)律地變化,S

26、 L O F =1.所以當(dāng)S L O F (o 1時,對象o 正常.當(dāng)S L O F >1時,對象開始離群,隨著S L O F 值的增大,其離群度也增大.實驗中,取=min (min N dist (o 0,o O,時(其中為最小的計算精度要求,可滿足要求.312SLOF 的算法輸入:對象集O =o 1,o 2,o n 對象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)系,離群點個數(shù)m輸出:空間離群點集算法過

27、程:1.根據(jù)對象的空間屬性s (o 和空間關(guān)系,確定每個空間對象的空間鄰域;2.規(guī)一化每個對象的非空間屬性值.設(shè)max j 和min j 是第j 維非空間屬性的最大和最小值,f (o i j 是對象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.計算每個對象與其空間鄰域間的距離.先運用式(2計算對象與其鄰域中所有對象的距離;再運用式(4計算對象與其鄰域的距離;4.運用式(6計算每個空間對象的空間局部離群系數(shù)SL O F;5.根據(jù)空間離群系數(shù)SL O F 將對象按降序排序;6.輸出

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

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

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

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

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

33、 , SL OM 、 O F 算法在用戶的依賴性 SL 和可伸縮性上均好于 Z2Sco re 算法 , 代表了檢測算 法的發(fā)展方向 , 在檢測精度上 SL O F 算法又優(yōu)于 SL OM 算法 . 41 2 實際數(shù)據(jù)集測試結(jié)果與分析 使用美國人口調(diào)查局網(wǎng)站 的人口統(tǒng)計和預(yù)測 縣名稱 ( 屬性值/ % 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 個離群點及其鄰居 鄰居 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ù) , 包括美國所有縣的空間和非空間信息 . 2 2維空 間信息用于定義空間鄰域 . 對于每一個縣 , 所有與其 直接接壤的縣組成其鄰域 . 選擇 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 個離群點 . 從表中可以看出 , SL OM 算法和 L C K 算法求得的 5 個離群點中有 4 個是相同的 , 而且前兩個完全一樣 , 但與 SL O F 算法求得的完全不同 , 從表 2 表 4 中 可以看出 , 所標(biāo)出的 11 個離群點確實是離

38、群點 , 究 竟哪種算法取得的結(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é)者 提出 ,簡稱為 L C K 算法 . 8期 薛安榮等 : 局部離群點挖掘算法研究 表 3 SLOM 算法挖掘的 5 個離群點及其鄰居 縣名稱 ( 屬性值/ % 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 個離群點及其鄰居 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