局部离群点挖掘算法研究_图文

1、第30卷第8期2007年8月计算机学报C HIN ESE J OU RNAL OF COM PU TERSVol.30No.8Aug.2007收稿日期:2007203205;修改稿收到日期:2007205228.本课题得到国家自然科学基金(60603041,江苏省高校自然科学基金(05K JB520017及江苏省自然科学基金(B K2006073的资助.薛安荣,男,1964年生,博士研究生,副教授,主要研究方向为数据挖掘、多媒体技术、时空数据库及地理信息系统.E 2mail :xuear .鞠时光,男,1955年生,博士,教授,博士生导师,主要研究方向为数据库、信息安全理论与技术.何伟华,男,

2、1974年生,硕士研究生,主要研究方向为数据挖掘.陈伟鹤,男,1974年生,博士,副教授,主要研究方向为信息安全、数据库管理系统原理及实现.局部离群点挖掘算法研究薛安荣鞠时光何伟华陈伟鹤(江苏大学计算机科学与通信工程学院江苏镇江212013摘要离群点可分为全局离群点和局部离群点.在很多情况下,局部离群点的挖掘比全局离群点的挖掘更有意义.现有的基于局部离群度的离群点挖掘算法存在检测精度依赖于用户给定的参数、计算复杂度高等局限.文中提出将对象属性分为固有属性和环境属性,用环境属性确定对象邻域、固有属性计算离群度的方法克服上述局限;并以空间数据为例,将空间属性与非空间属性分开,用空间属性确定空间邻域

3、,用非空间属性计算空间离群度,设计了空间离群点挖掘算法.实验结果表明,所提算法具有对用户依赖性少、检测精度高、可伸缩性强和运算效率高的优点.关键词离群点检测;局部离群系数;R 32树;数据挖掘;空间离群点;剔除平均中图法分类号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引言离群点检测是数据挖掘的基本任务之一122,故称为离群点挖掘,其目的是消除噪音

11、或发现潜在的、有意义的知识,广泛应用在电子商务犯罪和信用卡欺诈的侦查、网络入侵检测、生态系统失调检测、公共卫生、医疗和天文学上稀有的、未知种类的天体发现等领域中.早期的离群点挖掘算法是针对全部数据集的,挖掘的是全局离群点1.由于现实世界的复杂性和多变性,所获得的数据集往往是不完整的,而且在很多场合,用户只关心局部的不稳定,即局部离群点.局部离群点挖掘需要解决局部邻域的确定和对象与邻域的比较计算两个子问题.现有的挖掘算法一般对对象属性不加区分,采用对象的全部属性来解决上述两个子问题,致使计算复杂度高,检测结果难以解释.为此,我们可以通过区分对象属性性质,利用一部分属性确定对象邻域,用另一部分属性

12、进行对象与其邻域间计算的比较.事实上对象包含两类属性即固有属性和环境属性.固有属性决定对象的性质,而环境属性决定对象与其周围环境的关系,因此可用环境属性来确定对象的邻域,用固有属性进行对象与其邻域间计算比较.本文将以空间离群点的挖掘为例,探讨局部离群点挖掘的一般方法.在空间离群点挖掘中,将空间属性与非空间属性分开,利用空间属性及空间关系确定空间邻域,基于空间邻域和非空间属性计算对象与其邻域的距离,进而计算每个数据对象的空间离群度,从而解决空间离群点挖掘问题,实验结果表明该方法比现有算法有效.本文第2节讨论了局部离群点挖掘的相关研究工作,指出其局限;第3节阐述空间离群点挖掘算法;第4节是基于合成

13、数据和实际数据的实验测试与结果分析;第5节是结论与展望.2相关研究211局部离群点挖掘方法到目前为止,还没有一个广为接受的离群点的正式定义,但Hawkins的定义抓住了概念的精髓:“一个离群点是一个观察点,它偏离其它观察点如此之大以至引起怀疑是由不同机制生成的”2.由于这个定义是基于全部数据集的,是全局离群点定义.定义1.局部离群点是指在数据集中与其邻域表现不一致或大大地偏离其邻域的观测点.基于密度的离群点的定义是在基于距离定义3的基础上建立起来的,将点之间的距离和给定范围内点的个数这两个参数结合起来得到“密度”的概念.Breuning等学者引入一个专门的度量单位:离群系数(Outlier F

14、actor,O F,用局部离群系数(Lo2 cal Outlier Factor,LOF来表征一个对象的局部离群程度425.定义2.局部离群度是指对象与其局部邻域的偏离程度.自从LO F出现后,引起许多学者的关注,出现了许多离群度的度量方法,比较典型的有基于连接的离群系数(Connectivity2based Outlier Factor, COF6、多粒度偏差因子(Multi2granularity DEvi2 ation Factor,MDEF7、局部空间离群测度(Meas2 ure for Local Spatial Outlier,SLOM8等方法. 212离群度的计算现有的基于离群度

15、的局部离群点挖掘算法主要区别在于邻域的确定方法和离群度的计算方法不同.下面将具体分析.在LO F算法5中,根据给定的参数最少邻居数k和最近邻距离来确定邻域,通过计算对象的k2距离、可达距离和可达密度,用数据对象邻域的平均可达密度与数据对象自身的可达密度之比表示LO F. LOF算法可很好地解决局部离群点的挖掘问题.但该算法存在计算量大,计算结果受指定参数k影响大,如果修改k值,则需要重新构造数学模型和重新计算等不足.在CO F算法6中,根据给定的参数最少邻居数k和数据对象的连接性来确定邻域,计算与其邻域的平均连接距离,用平均连接距离比作为基于连接的离群系数COF.COF算法虽可克服LOF算法中

16、对于序列数据和低密度数据对象不能有效度量的缺陷,但仍如LOF算法那样,存在计算复杂度高、计算结果受指定参数k影响大,如果修改k值,则需要重新构造数学模型和重新计算的缺陷,而且COF增加了连接路径,因此时间复杂度比LOF更高.在MDEF算法7中,有两个邻域概念,即r2邻6541计算机学报2007年域和r2邻域,其中r>0,0<<1.n(p i,r和n(p i,r分别表示以pi为圆心、r为半径和r为半径的圆内的对象数目,n(p i,r,表示在p i的r2邻域内的所有对象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算法的优点是可以根据应用要求设置多级邻域,并用邻域中包含的对象数目替代距离计算,降低了计算复杂度,但r和很难确定,为了获得满意结果,需要反复修改参数.因此,MD EF算法的检测结果和计算复杂度取决于用户的经验.由此可见,上述算法存在以下问题:计算复杂度高,检测结果的精度和重复计算的次数依赖于用户给定的参数,如指定的参数k2邻居将决定邻域的范围,当k值过小时,在离群点彼此接近、形成一个小的离群簇的情况下,会将这个小的离群簇误判为正常数据簇,导致漏检;当k值太大时,接近稠密簇的离群点可能会被误判为正常数据点,也会导致漏检.为了得到满意结果,

18、需要反复调整参数k,而每次调整参数均须重新构造邻域,邻域构造非常费时,具有O(kn2的计算复杂度,其中k为邻居数,n为数据点总数.为了提高检测精度,降低复杂度,必须从模型的构造和阈值的指定上入手,利用数据的自身特点,减少算法对用户的依赖性.实际上,一个数据对象的存在包含两类不同性质的属性,一类是对象固有的本质属性,决定了对象的性质;另一类是对象存在的外部环境,我们称之为环境属性,如对象存在的时间、空间位置.环境属性决定了对象与其外部的关联,可用这类属性来确定对象的邻域,而用固有属性来计算对象的离群度.在空间离群点挖掘算法中,可将属性分为空间属性和非空间属性8210,利用空间属性和空间关系确定空

19、间邻域,利用非空间属性进行计算比较.此外对于大量空间数据,一般用R32树11索引来加快检索速度,设s为R32树中每个索引结点的最少项数,此时确定空间邻居的计算复杂度为O(n(k log s n,与O(kn2相比大为降低.SLOM算法8就是其中一例.在SLOM算法8中,将数据对象的属性分为空间属性和非空间属性,利用空间属性及空间邻接关系确定对象的邻域,以邻域距离d和波动因子的乘积为空间局部离群度,即S L OM=d×.SLOM算法与上述其它算法相比,在邻域的确定上不再依赖用户输入的参数,可从数据自身特点出发,利用空间数据的空间属性和空间关系确定空间邻域,解决了邻域的确定依赖于用户输入的

20、参数和由此带来的反复计算问题.利用空间索引技术,可极大地缩小数据搜索范围,减少对数据的访问次数,从而提高算法的效率.但在SLOM算法8中,由于波动因子仅由对称分布状况来决定,在空间邻居较少或波动幅度较小的情况下难以准确表现波动情况,因此出现较高的漏检和误检现象,甚至挖掘的不是局部离群点,而是全局离群点.为此,我们提出了基于空间局部离群系数(Spatial Local Outlier Factor,SLO F的新的空间离群点挖掘算法.3基于SLOF的空间离群点挖掘算法311SLOF的计算假设对象集O=o1,o2,o n由n个对象组成,对象oO的空间属性函数是s(o,非空间属性函数是f(o,f(o

21、的维度为d2维,c表示在指定条件c下的空间邻接关系.d2维非空间属性f(o表示为(f(o1,f(o2,f(o d.定义3(空间邻居.对象o的空间邻居是指与对象o在指定条件c下,存在空间邻接关系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(加权距离.设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维规一化属性,且0f(o ik,f(o jk1,w

22、 k是第k维的权值,且0w k1,则数据对象o i和o j之间的加权距离为dist(o i,o j,w=dk=1w k(f(o ik-f(o jk2(2其中,dk=1w k=1.值得注意的是,这里的对象间距离不是对象间的空间距离,而是对象间的d2维非空间属性距离.根据分析需要,如果不同属性对分析目标的贡献程度不同,则分配的权值也不同,贡献率大的权值大,75418期薛安荣等:局部离群点挖掘算法研究反之则小,权值一般由领域专家决定.定义6(邻域距离.对象o 的邻域距离是指对象o 与其空间邻域中所有对象的加权距离的平均值,即N dist (o,w =p N (o dist (p ,o ,w |N (

23、o |(3为了消除邻域中极值对邻域距离计算的影响,采用剔除平均的方法12,先剔除邻域中的极值距离,然后再计算对象与邻域的平均距离.设对象o 的邻域对象数为|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剔除极值距离后求均值,可避免因离群点的影响正常数据被误检为离群点.

24、将对象的邻域距离与其空间邻居进行比较得到对象在局部空间上的偏离程度,即为空间局部离群系数.定义7(空间局部离群系数.对象o 的空间局部离群系数定义为SL O F (o =N dist (o,w p N (o N dist (p ,w |N (o |(5为了避免S L O F 计算中分母为0的情况,设为非常小的正数,分子、分母同时加上,则式(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的计算中,所有非空间属性均规一化到0,1区间上,且dk =1w k =1,所以0N dist (o,w 1,故有1+S L O F (o 1+,的取值将决定S L O F 的取值范围.当对象的邻域距离=0时,表示对象与其邻域的非空间属性值相同,S L O F =0;当对象的邻域距离与邻域对象的平均邻域距离相同时,表示对象的非空间属性在有规律地变化,S

26、 L O F =1.所以当S L O F (o 1时,对象o 正常.当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 下的空间邻接关系,离群点个数m输出:空间离群点集算法过

27、程:1.根据对象的空间属性s (o 和空间关系,确定每个空间对象的空间邻域;2.规一化每个对象的非空间属性值.设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区间内;3.计算每个对象与其空间邻域间的距离.先运用式(2计算对象与其邻域中所有对象的距离;再运用式(4计算对象与其邻域的距离;4.运用式(6计算每个空间对象的空间局部离群系数SL O F;5.根据空间离群系数SL O F 将对象按降序排序;6.输出

28、前m 个对象,前m 个对象就是空间离群点.313算法复杂度分析在上述算法中,邻域的确定是非常费时的,但由于是空间数据,利用空间特性及空间索引R 32树来确定空间邻域,其计算复杂度大为降低.假设空间数据对象数目为n ,非空间属性维度为d 维,对象的邻居数为k (k 可变,s 为R 32树中每个索引结点的最少项数,则确定空间邻居的计算复杂度为O (n (k log s n ;规一化非空间属性为0,1的复杂度为O (dn ;计算对象与其邻域距离的复杂度为O (n (k log s n +k d ;计算S L O F 的复杂度是O (n (k log s n ;排序的计算复杂度为O (n log 2n

29、 ;取前m 个离群对象并输出的复杂度是O (m .故总的复杂度为O (n (k log s n +k d +log 2n ,当d n 时,算法的复杂度为O (kn log n .本算法与SLOM 算法复杂度相当,但对于高维数据,由于LO F 等算法采用全部属性确定邻8541计算机学报2007年域和进行比较计算,没有合适的索引结构可用,其算法的复杂度为O(kn2,因此采用属性二分算法的效率比采用全部属性算法的效率高.4实验结果与分析411合成数据集测试结果与分析下面对Z2Score9、SLOM8和SLOF算法进行比较.图1是一个30行×2列的数据点,X轴是数据点位置(这里假设空间维是一

30、维,Y轴是属性值(非空间属性值,假设也是一维,图2图4是以图1中数据为基本数据的检测结果.从空间离群点定义9可知,图1中S点和G点是离群点,且S点的离群程度最高.Z2Score算法9是将对象的属性值与其邻域的平均属性值的差:S(x=f(x-E yN(x(f(y作为比较函数,利用判别式Z S(x i=S(x i-SS>来确定数据对象是否为空间离群点,其中s和s分别是差函数S(x的均值和标准差,为给定的阈值,一般为3.图2是Z2Score算法对图1中数据的检测结果.若=3,则图中的S点是空间离群点.图3是SLOM算法对图1中数据的检测结果.图3中的A点和S点是空间离群点.图4是SLOF 算法

31、对图1中数据的检测结果.图4中将S L O F-1,且当S L O F0时,令S L O F=0,S点是空间离群点.从实验结果可以看到:(1在用户依赖性方面.Z2Score算法的检测结果依赖于用户,如=3时,S点为空间离群点,若=415时,则没有空间离群点,若=118时,则 S,Q,A点均是空间离群点.而SLOM和SLO F算法只需要将前m个最离群的对象提供给用户,用户可根据实际需要选取.(2计算复杂度.由于三种算法有效利用了空间属性和空间关系来确定空间邻域,极大改善了算法的复杂度,算法复杂度均为O(kn log n.(3检测精度.从表1和图1图4可以看出,我们所提算法SLOF的检测精度最高,

32、不仅正确检测出空间离群点S,也准确给出了其它数据对象的离群顺序;Z2Score算法正确检测出空间离群点S,但G点的离群顺序未能正确给出;SLOM算法未能正确给出空间离群点S的顺序,其主要原因就是因为邻居数太少影响了摆动因子的有效性.95418期薛安荣等:局部离群点挖掘算法研究1460 计 算 机 学 报 表1 检测结果比较 2007 年 序号 1 2 标准 S G 检测精度 100 % ( 4 可伸缩性 . Z2Score 算法仅适用于 1 维非空 间属性 ,而 SL OM 、 O F 算法可应用于多维非空间 SL 属性 ,所有 SL OM 、 O F 算法具有更好的伸缩性 . SL 综上所述

33、 , SL OM 、 O F 算法在用户的依赖性 SL 和可伸缩性上均好于 Z2Sco re 算法 , 代表了检测算 法的发展方向 , 在检测精度上 SL O F 算法又优于 SL OM 算法 . 41 2 实际数据集测试结果与分析 使用美国人口调查局网站 的人口统计和预测 县名称 ( 属性值/ % 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 权值 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 数据 , 包括美国所有县的空间和非空间信息 . 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 中 可以看出 , 所标出的 11 个离群点确实是离

38、群点 , 究 竟哪种算法取得的结果更准确呢 ?那就要从离群程 度上 分 析 . 图 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 三位学者 提出 ,简称为 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