（计算机应用技术专业论文）空间离群点挖掘技术的研究.pdf

江苏大学博士学位论文 摘要 空间离群点是与其空间邻域中其它空间对象的非空间属性值存在明显差异 的空间对象。空间离群点挖掘是空间数据挖掘的一个重要分支，在交通控制、遥 感图像分析、气象预报和人口统计数据分析等应用中可揭示重要现象。 随着传感器设备技术的发展，数据采集设备的数量越来越多，精度越来越高， 采集的项目也越来越多，因此数据量越来越大，维数越来越高。然而现有的空间 离群点挖掘算法主要是针对单维或中低维的中小规模数据量的挖掘，难以适应高 维大数据量的挖掘，并且现有算法没有充分考虑空问数据的特点，挖掘的不是真 正意义上的空间离群点，而是全局离群点。算法存在用户依赖性大。检测精度低， 挖掘效率低等局限。此外，随着网络技术、传感器技术和无线通信技术的发展， 数据的采集、收集、保存和处理都呈现分散状态，因此，基于分布环境的数据挖 掘也引起人们的关注，但基于分布环境的空间离群点挖掘算法还未见报道。 本文将根据空间数据自身的特点，研究属性划分方法和属性的权值设置方 法，空间离群程度的度量方法，实现挖掘精度高、用户依赖性少的高效的空间离 群点挖掘算法。针对现有算法主要局限在数值型属性数据处理上的不足，通过将 非数值型数据转化为数值型数据，实现基于混合型属性的统一算法。针对高维大 数据量，采用剪枝策略、基于子空间的离群点挖掘和集成学习的方法实现高维大 数据量的挖掘；针对分布环境下的空间离群点挖掘，提出了基于隐私保护的空间 离群点挖掘算法。论文的主要贡献如下： ( 1 ) 提出基于属性划分的方法解决局部离群点的挖掘问题。一般的局部离群 点的挖掘采用的是满维属性的挖掘方法，如l o f ( l o c a lo u t l i e rf a c t o r ) 方法，其结 果是局部邻域的确定非常耗时，由于所有维属性不加区分地等同看待，所以离群 度度量的准确性受到影响，影响了挖掘的精度和速度。提出将数据对象的属性划 分为标识属性、环境属性和固有属性，标识属性起着标识对象的作用，如数据对 象名称等；环境属性决定了对象所处环境，如地理位置、时间、序列等，可利用 环境属性确定邻域；固有属性是数据对象特有属性，包括行为属性和状态属性， 决定了对象的行为和状态特征，可利用该类属性确定对象的离群程度。 ( 2 ) 提出空间数据对象的离群程度的新的度量方法，即基于空间数据特性的 空间局部离群系数s l o f ( s p a t i a ll o c a l o u t l i e rf a c t o o 的度量方法；提出基于空间 离群度的空间离群点挖掘算法a s l o f ( a l g o r i t h mb a s e do ns l o f ) 。将数据对象的 江苏大学博士学位论文 属性分为标识属性、空间属性和非空间属性，利用空间属性确定空间邻域、建立 空间索引，利用非空间属性确定对象的离群程度，并在离群度的度量中引入属性 的权值，提高度量精度，据此提出了基于空间离群度的空间离群点挖掘算法。理 论证明和实验测试结果表明，a s l o f 在挖掘的精度、用户依赖性和算法性能上 均优于现有算法。 ( 3 ) 提出混合属性的统一的空间离群度的度量方法和挖掘算法。从离群点性 质入手，通过统计分类属性的频度，将分类属性转化为数值型，并通过属性的权 值设置和属性的标准化等处理后，实现基于混合属性的空间离群点的统一挖掘算 法。实验结果表明，算法可有效实现混合属性的空间离群度的统一度量计算和有 效挖掘。 ( 4 ) 提出基于集成学习的子空间离群点集成的高维大数据量的空间离群点 快速挖掘算法s 2 0 e a h l ( s u b s p a c es p a t i a lo u t l i e re n s e m b l ea l g o r i t h mb a s e dh i e , h - d i m e n s i o n a ll a r g ed a t as e t s ) 。由于很多空间数据对象的标识属性中含有空间对象 所在的地域标识，根据地域标识构建对象的层次编码树，基于层次编码树，实现 数据的分区和对象的快速检索，通过计算分区的上下界和使用包围盒检测方法， 剪除明显不含有离群点的分区，保留可能含有离群点的分区作为候选分区，实现 了分区的快速剪枝，从而降低数据处理数量。对候选分区采用子空间挖掘方法， 为避免与属性维度成指数关系的大量搜索，采用指定子空间挖掘和基于子空间权 值的集成融合方法来解决高维数据的离群点挖掘问题。算法的实现中采用了基于 单维子空间的离群系数挖掘方法，并利用优化计算的方法求得被检测对象所对应 的各属性的权值，在此基础上通过集成融合函数求得被检测对象的离群度，根据 离群度的排序可获得所求离群点。理论证明和实验结果均表明算法的有效性和计 算的高效性。 ( 5 ) 提出基于分布环境的隐私保护的空间离群点挖掘算法d p p a s l o f ( d i s t r i b u t e dp r i v a c yp r e s e r v i n ga l g o r i t h mb a s e do ns l o f ) 。算法中利用空间数据的 局部性，发挥各数据方的主动参与的能力，借助于空间索引技术和隐私保护协议 以提高搜索能力和隐私保护能力。理论证明算法的安全性，计算的高效性和低通 信代价。 关键词：属性划分，局部离群系数，空间离群点，集成学习，空间索引，剪枝策 略，隐私保护，数据挖掘 江苏大学博士学位论文 a b s t r a c t as p a t i a lo u t l i e ri sas p a t i a l l yr e f e r e n c e do b j e c tw h o s en o n - s p a t i a la t t r i b u t e v a l u e sa r es i g n i f i c a n t l yd i f f e r e n tf r o mt h ev a l u e so fi t sn e i g h b o r h o o d s p a t i a lo u t l i e r m i n i n gi sa ni m p o r t a n tb r a n c ho fs p a t i a ld a t am i n i n g i tc a nr e v e a li m p o r t a n t p h e n o m e n o ni nt h ea p p l i c a t i o n so ft r a 伍cc o n t r o l ，s e n s e di m a g ea n a l y s i s ，w e a t h e r f o r e c a s t i n ga n da n a l y s i so fd e m o g r a p h i cd a t aa n do t h e r s ： w i t ht h ed e v e l o p m e n to fs e n s o rt e c h n o l o g y , t h en u m b e ro fe q u i p m e n tf o rd a t a a c q u i s i t i o ni sm o r ea n dm o r e ，t h ed e s i r e dp r e c i s i o ni sh i 曲e r m o r ea n dm o r ep r o j e c t s c o l l e c t e d ，t h e r e f o r ei n c r e a s i n gt h ea m o u n to fd a t a , t h eh i g h e rd i m e n s i o n h o w e v e r , t h e e x i s t i n gs p a t i a lo u t l i e rm i n i n ga l g o r i t h mi sm a i n l yf o rt h es m a l la n dm e d i u m s i z e d d a t a s e t sw h i c hi so n e d i m e n s i o n a lo rl o w d i m e n s i o n a l d i 伍c u l tt oa d a p tt ot h el a r g e h i g h - d i m e n s i o n a ld a t am i n i n g ，a n dd i dn o tf u l l yc o n s i d e rt h ec h a r a c t e r i s t i c so fs p a t i a l d a t a , t h ed a t ai tm i n e di sn o tt h et r u es p a t i a lo u t l i e r s b u tt h eg l o b a lo u t l i e r s t h e i r d i s a d v a n t a g e sa r et h eh i g hu s e r - d e p e n d e n c y , l o wd e t e c t i o na c c u r a c y , l o we m c i e n c yo f m i n i n g i na d d i t i o n ，w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y , s e n s o rt e c h n o l o g y a n dw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g y , t h ea c q u i s i t i o n , c o l l e c t i o n ，p r e s e r v a t i o na n d p r o c e s s i n go fd a t aa p p e a ras t a t eo fd e c e n t r a l i z a t i o n ，s ot h ed a t am i n i n gb a s e do nt h e d i s t r i b u t e de n v i r o n m e n ti sa l s oc a u s ef o rc o n c e r n h o w e v e r , s p a t i a lo u t l i e rm i n i n g a l g o r i t h mb a s e do nt h ed i s t r i b u t e de n v i r o n m e n th a s n tb e e nr e p o r t e d a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fs p a t i a ld a t a , t h i sa r t i c l ew i l lr e s e a r c ho nt h e m e t h o d so fa t t r i b u t ep a r t i t i o na n dw e i g h tv a l u es e t u p ，t h em e a s u r e m e n to fs p a t i a l o u t l i e rs c o r e a c h i e v i n gt h eh i g h p e r f o r m a n c es p a t i a lo u t l i e rm i n i n ga l g o r i t h m sw i t l l l l i g l lm i n i n gp r e c i s i o n , l e s su s e r - d e p e n d e n c y t h ed i s a d v a n t a g e so fe x i s t i n ga l g o r i t h m sm a i n l yl i m i t e dt on u m e r i c a ld a t a ，b y t r a n s f o r m i n gt h en o n - n u m e r i c a ld a t ai n t on u m e r i c a ld a t a , m a k et h eu n i f i e da l g o r i t h m b a s e do nt h em i x e da t t r i b u t ec o m et r u e f o rh i g h d i m e n s i o n a ll a r g ea m o u n to fd a t a , u s ep r u n i n gs t r a t e g y , t h eo u t l i e rm i n i n gb a s e do ns u b s p a c ea n de n s e m b l el e a r n i n g m e t h o d st oa c h i e v et h ed a t am i n i n go fh i 酿d i m e n s i o n a ll a r g ea m o u n to fd a t as e t s ： f o rt h es p a t i a lo u t l i e rm i n i n go fd i s t r i b u t e de n v i r o n m e n t ，t h ep r i v a c yp r e s e r v i n g s p a t i a lo u t l i e rm i n i n ga l g o r i t h m sw e r ep r o p o s e d t h em a i nc o n t r i b u t i o no ft h ep a p e ri s 勰f o l l o w s ： ( 1 ) p r o p o s et h em e t h o db a s e do nt h ea t t r i b u t ed i v i s i o nt or e s o l v et h ep r o b l e mo f l o c a lo u t l i e rm i n i n g t h e g e n e r a ll o c a l o u t l i e r m i n i n gu s e st h em e t h o d o f 向1 1 d i m e n s i o n a la t t r i b u t e s ，s u c ha sl o f ( l o c a lo u t l i e rf a c t o r ) m e t h o d a sar e s u l t ，i t i sv e r yt i m e - c o n s u m i n gi nd e t e r m i n i n gt h el o c a ln e i g h b o r h o o d ，s i n c ea 1 1 d i m e n s i o n a l a t t r i b u t e sa r ei n d i s c r i m i n a t e l ye q u a t e d ，t h ea c c u r a c yo ft h em e a s u r e m e n to fo u t l i e r s c o r ea f f e c t e d ，t h em i n i n ga c c u r a c ya n ds p e e do fd a t am i n i n ga l s oa f f e c t e d t h e a t t r i b u t e so fd a t ao b i e c tc a nb ec a t e g o r i z e da st h ei da t t r i b u t e s ，c o n t e x ta t t r i b u t e sa n d i n h e r e n ta t t r i b u t e s t h ei da t t r i b u t e sp l a yt h er o l eo fm a r k i n gt h ed a t ao b j e c t ，s u c ha s t h en a m eo fd a t ao b j e c ta n ds oo n t h ec o n t e x ta t t r i b u t e sd e c i d et h ee n v i r o n m e n to f t h eo b j e c t ，s u c ha s1 0 c a t i o n ，t i m e ，s e q u e n c e ，i tc a nb eu s e dt oi d e n t i f yn e i g h b o r h o o d t h ei n h e r e n ta t t r i b u t e si st h eu n i q u ea t t r i b u t e so fd a t ao b j e c t ，i n c l u d i n gb e h a v i o r a t t r i b u t e sa n ds t a t u sa t t r i b u t e s ，d e c i d et h eb e h a v i o ra n dc h a r a c t e r i s t i c so ft h es t a t u so f t h eo b j e c t ，w ec a i lu s ei tt od e t e r m i n et h es p a t i a lo u t l i e rs c o r eo fd a t ao b j e c t s ( 2 ) p r o p o s ean e wm e t h o df o rt h em e a s u r e m e n to ft h es p a t i a lo u t l i e rs c o r eo fd a t a i i i 江苏大学博士学位论文 o b j e c t s t h a ti s t h em e a s u r e m e n tm e t h o do fs l o f ( s p a t i a ll o c a lo u t l i e rf a c t o r ) w h i c hi sb a s e do nt h ec h a r a c t e r i s t i c so fs p a t i a ld a t a p r o p o s et h es p a t i a lo u t l i e rm i n i n g a l g o r i t h ma s l o f ( a l g o r i t h mb a s e do ns l o n t h ea t t r i b u t e so fd a t ao b j e c tc a nb e c a t e g o r i z e da st h ei da t t r i b u t e s ，s p a t i a la t t r i b u t e sa n dn o n s p a t i a la t t r i b u t e s ，u s et h e s d a t i a la t t r i b u t e st od e t e r m i n et h es p a t i a ln e i g h b o r h o o d ，e s t a b l i s ht h es p a t i a li n d e x ，u t h en o n s p a t i a la t t r i b u t e st od e t e r m i n et h es p a t i a lo u t l i e rs c o r e ，a n di n t r o d u c et h e w e i g h tv a l u eo fa t t r i b u t e si nt h em e a s u r e m e n to fo u t l i e rs c o r c ，i m p r o v i n gt h e m e a s u r e m e n ta c c u r a c y b a s e do nt h e s e ，p r o p o s et h es p a t i a lo u t l i e rm i n i n ga l g o r i t h m b a s e do nt h es p a t i a lo u t l i e rs c o r e t h et h e o r ya n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h e p r o p o s e da s l o fa l g o r i t h mo u t p e r f o r m st h eo t h e re x i s t i n ga l g o r i t h m si nm i n i n g a c c u r a c y ，u s e r - d e p e n d e n c y ，a n de f f i c i e n c y f 3 ) p r o p o s eau n i f i e dm e a s u r e m e n to ft h es p a t i a lo u t l i e rs c o r ea n dm i n i n g a l g o r i t h mo fm i x e da t t r i b u t e s s t a r tw i t ht h en a t u r eo fo u t l i e r s ，t h r o u g hc o u n t i n gt h e f r e q u e n c yo fc l a s s i f i e da t t r i b u t e s ，t r a n s f o r mt h ec l a s s i f i e da t t r i b u t e si n t on u m e r i c a t t r i b u t e s a n dt h r o u g hw e i g h tv a l u es e t u pa n ds t a n d a r d i z a t i o no ft h ea t t r i b u t e s ，a f t e r t h ea b o v em e n t i o n e dd e a l m a k et h eu n i f i e dm i n i n ga l g o r i t h mo fs p a t i a lo u t l i e rw h i c h b a s e do nt h em i x e da t t r i b u t ec o m et r u e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a ti tc a r l e f f e c t i v e l ya c h i e v et h eu n i f i e dm e a s u r e m e n to fs p a t i a lo u t l i e rs c o r ew i t hm i x e d a t t r i b u t e sa n dm i n i n g f 4 ) p r o p o s et h es u b s p a c es p a t i a lo u t l i e re n s e m b l ea l g o r i t h mb a s e dh i g h d i m e n s i o n a ll a r g ed a t as e t s ( s 2 0 e a h l ) d u et oal o to fg e o g r a p h i c a li d e n t i t y c o n t a i n e di nt h ei da t t r i b u t e so ft h es p a t i a ld a t ao b j e c t s a c c o r d i n gt ot h eg e o g r a p h i c a l i d e n t i t yt oc o n s t r u c to ft h eh i e r a r c h yc o d i n gt r e eo fo b j e c t ，b a s e do nt h et r e e ，a c h i e v e t h ed i v i s i o no fd a t aa n dr a p i d l ys e a r c ho ft h eo b j e c t ，b yc a l c u l a t i n gt h eu p p e ra n d l o w e rb o u n do ft h ed i v i s i o na n dm i n i m u mb o u n d i n gr e c t a n g l e ( m b r ) m e t h o d ，c u t t i n g t h ed i v i s i o nw h i c ho b v i o u s l yn o tc o n t a i no u t l i e r s ，r e s e r v i n gt h ed i v i s i o nw h i c hm a y c o n t a i no u t l i e r sa sac a n d i d a t ed i v i s i o n ，i tr e a l i z e st h er a p i dp r u n i n go ft h ed i v i s i o n ， c o n s e q u e n t l yr e d u c et h en u m b e ro fd a t ap r o c e s s i n g a d o p t i n gt h es u b s p a c em i n i n g m e t h o df o rt h ec a n d i d a t ed i v i s i o n i no r d e rt oa v o i dal a r g en u m b e ro fs e a r c hw h i c h h a sa ne x p o n e n t i a lr e l a t i o n s h i pw i t ht h ed i m e n s i o no ft h ea t t r i b u t e s ，u s i n ga s u b s p a c e - b a s e dm i n i n ga n de n s e m b l el e a r n i n gb a s e do ns u b s p a c e - w e i g h tt oa d d r e s s t h ei s s u eo fo u t l i e rm i n i n go fh i g h d i m e n s i o n a ld a t a a l g o r i t h mu s et h eo u t l i e rf a c t o r m i n i n gm e t h o do fo n e - d i m e n s i o n a ls u b s p a c e ，a n du s et h eo p t i m i z a t i o n a lm e t h o do f c a l c u l a t i o nt oa c h i e v et h ec o r r e s p o n d i n gw e i g h to fa t t r i b u t e so ft h ed e t e c t e do b j e c t o nt h i sb a s i s ，t h eo u t l y i n g - n e s so fe a c hd a t ao b j e c ti sm e a s u r e db yf u s i n go u t l i e r f a c t o r si nd i f f e r e n ts u b s p a c e su s i n gac o m b i n a t i o nf u n c t i o n a c c o r d i n gt ot h es o r to f o u t l i e rf a c t o r sw ec a na c q u i r et h eo u t l i e r s t h et h e o r ya n de x p e r i m e n t a lr e s u l t ss h o w t h ee f f e c t i v e n e s so ft h ea l g o r i t h ma n dt h eh i g he m c i e n c yo fc a l c u l a t i o n ( 5 ) p r o p o s et h es p a t i a lo u t l i e rm i n i n ga l g o r i t h md p p a s l o f ( d i s t r i b u t e dp r i v a c y p r e s e r v i n ga l g o r i t h mb a s e do ns l o f ) o ft h ep r o t e c t i o n o fp r i v a c yb a s e do n d i s t r i b u t e de n v i r o n m e n t t h ea l g o r i t h mu s i n gt h el o c a l i wo fs p a t i a ld a t a , e x e r tt h e a b i l i t vo fa c t i v ep a r t i c i p a t i o no fe v e r yd a t ah o l d e rp a r t y , w i t ht h es p a t i a li n d e x t e c h n o l o g ya n dp r i v a c yp r e s e r v i n gp r o t o c o l si no r d e rt oi m p r o v et h ea b i l i t yt os e a r c h a n d p r i v a c yp r e s e r v i n g t h e o r y s h o w st h e s a f e t y o ft h e a l g o r i t h m ，t h e h i g h - p e r f o r m a n c eo fc o m p u t i n ga n dt h el o wc o s to fc o m m u n i c a t i o n s k e y w o r d ：a t t r i b u t ep a r t i t a t i o n ；l o c a lo u t l i e rf a c t o r ；, s p a t i a lo u t l i e r ；e n s e m b l el e a r n i n g ； s p a t i a li n d e x ；p r u n i n gs t r a t e g y ；p r i v a c yp r e s e r v i n g ；d a t am i n i n g i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口， 在年解密后适用本授权书。 本学位论文属于 不保密囹。 学位论文作者签名：导师签名： 伶卜z ， 签字日期：炒绛，2 月力p 日签字日期：加稻年12 - 月乃日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位敝储虢薛嘛 日期：枷子年，z 月2 - oe l 江苏大学硕士学位论文 1 1 研究背景 第一章绪论 数据收集和数据存储技术的快速发展使得各组织机构积累了海量复杂数据， 而从中提取有用的信息面临巨大的挑战。由于传统的数据分析工具和处理技术难 以有效从大量数据中提取知识，造成了信息过量与知识贫乏的矛盾，由此推动了 数据挖掘( d a t am i n i n g , d m ) 技术的发展【卜3 】。数据挖掘就是从大量数据中自动发 现知识的过程【l o 】，它通过关联规则、分类与聚类等方法实现从数据集中挖掘出 潜在的有用知识。 离群点检测( o u t l i e rd e t e c t i o n ) 是数据挖掘的基本任务之一阻9 1 ，故称为离群点 挖掘( o u t l i e rm i n i n g , o m ) ，其目的是为了消除噪音或发现潜在的、有意义的知识。 离群点检测在欺诈检测、入侵检测、故障检测、生态系统失调、公共卫生中的异 常疾病的爆发、公共安全中的突发事件的发生、异常自然气候的发现、人口的异 常分布或变化的检测等应用中有着广阔的应用前景。 空间离群点挖掘作为离群点挖掘的一个重要研究方向，已经引起了许多学者 的关注，取得了一些成果【m 一9 1 。但现有的研究没有有效利用空间数据的自相关性 和空间分布的异质性，研究的数据对象主要集中在单维、中低维的数值型数据上， 并且数据集中在单台计算机上。因此，本文在现有工作的基础上，结合空间数据 的特点，重新设计空间离群度的度量方法及挖掘算法，从离群点的定义入手，将 非数值型属性有效转化为数值型属性，实现数值型属性与非数值型属性算法的离 群度度量方法与挖掘算法的统一，从而提高挖掘的精度和算法的通用性。通过自 动设置属性的权值和子空间挖掘方法，解决高维空间的离群度的度量和离群点的 挖掘问题，利用空间索引技术、剪枝技术和集成学习技术提高挖掘效率，通过研 究基于分布环境下的隐私数据的保护技术实现基于分布环境的隐私保护的空间 离群点挖掘。 江苏大学博士学位论文 1 2 论文的主要研究内容及创新之处 1 2 1 论文的主要研究内容 针对现有空间离群点挖掘算法存在检测精度低、用户依赖性大、算法复杂度 高、难以处理高维大数据量的混合类型分布数据的局限，通过以下几个方面的研 究解决高维大数据量混合型分布数据的离群点有效挖掘问题。 ( 1 ) 通过对空间数据特性的分析研究，确定与空间数据集特性及规模相适应 的离群度的有效度量方法。空间数据具有空间自相关性和空间分布的异质性特 点，利用空间数据的局部性特点，采用基于空间邻域的离群度度量方法，并根据 空间数据的特点将其属性区分为标识属性、空间属性和非空间属性。标识属性起 着标识作用，以及空间属性和非空间属性问的关联，其中一部分标识属性也包含 了地理位置信息，可利用这类标识属性在粗粒度上确定数据对象的空间位置。利 用空间属性确定邻域，非空间属性包含行为属性和状态属性，以下统称为行为属 性，用非空问属性来度量数据对象的离群程度。实际应用中各个行为属性对数据 点的离群程度的度量的贡献程度并不相同，因此通过设置属性的权值来细化每个 属性对离群程度的贡献。属性的权值的设置对于中低维属性可以由领域专家设 置，但对于中高维属性，由领域专家设置不大可行，可根据数据的特点自动设置。 据此，实现数据点离群度的精确度量以便有效挖掘。 ( 2 ) 在确定离群度度量方法的基础上，通过对现有的典型离群点挖掘算法的 分析比较，确定与空间数据集特性及规模相适应的基于离群度的高效离群点挖掘 算法。利用空间属性确定空间邻域，非空间属性计算离群度，利用空间索引技术 加快数据搜索，通过对离群度排序，取t o p n 个离群点，避免挖掘依赖于用户指 定阈值的局限，从而实现对用户依赖性小、挖掘精度高的高效挖掘算法。 ( 3 ) 研究处理不同类型属性的统一的离群点挖掘方法。现有的离群点挖掘算 法主要集中在数值型属性数据的挖掘和少部分基于分类属性数据的挖掘上，综合 处理不同类型数据属性的挖掘算法很少，而且还是采用的将数值型属性与分类属 性分开处理的方法来处理，因此，根据离群点特性，采用h a s h 表和频度计算的 方法对分类属性进行预处理，在转化为数值型数据后与原有的数值型属性数据采 用统一的计算方法进行计算处理，从而实现统一的计算处理方法。 2 江苏大学博士学位论文 ( 4 ) 研究高维大数据量的离群点快速挖掘算法。需要解决两方面问题：一是 高维问题，二是大数据量的快速挖掘问题。由于高维数据的稀疏性，解决高维数 据的“维灾”问题是数据挖掘中必须解决的问题。目前解决的方法趋向于采用基 于子空间挖掘的方法解决，但子空间搜索与维数成指数关系。研究采用在指定子 空间挖掘和设置子空间的权值，然后通过集成融合技术融合各子空间的离群系 数，从而获得数据对象在整个空间上的离群系数的方法，解决高维离群点挖掘问 题。子空间的指定：对于特定的挖掘，可由领域专家指定，领域专家可直接指定 子空间，也可指定样本离群点，然后根据样本离群点获得子空间；对于一般挖掘， 最简单的办法就是单维子空间。而与之对应的子空间的权值的设置，可由领域专 家给定，也可根据数据特性求取。对于低维数据，领域专家确定数据对象的属性 的权值还是可行的，但对于高维数据，数据对象的属性的权值不可能由领域专家 确定。可根据数据对象属性值的偏差，通过优化计算方法，确定各属性的权值。 对于大数据量的快速挖掘问题，可通过研究分区划分、剪枝等技术解决。 ( 5 ) 研究基于分布环境的隐私数据保护的空间离群点挖掘方法。由于已有的 空间离群点挖掘算法主要集中在集中数据集的挖掘上，很少有基于分布环境的离 群点挖掘算法，基于分布环境的空间数据的离群点挖掘算法还未见报道，因此通 过研究分布挖掘算法和隐私保护算法实现基于分布环境的隐私保护的空间离群 点挖掘算法，从而适应基于网络的分布数据挖掘需要。为了提高挖掘效率和有效 保护各数据方隐私数据，需要充分利用空间数据的局部性，发挥各数据方主动参 与的能力，借助于空间索引技术和隐私保护协议以提高搜索能力和隐私保护能 力。 1 2 。2 论文主要贡献点 本文的创新之处主要在于： 提出基于属性划分的方法解决局部离群点的挖掘问题。一般的局部离群 点的挖掘采用的是满维属性的挖掘方法，如l o f 方法，其结果是局部邻 域的确定非常耗时，由于所有维属性不加区分地等同看待，所以离群度 度量的准确性受到影响，影响了挖掘的精度和速度。其实数据对象的属 性可区分为标识属性、环境属性和固有属性，标识属性仅起标识作用， 如数据对象名称等；环境属性决定了对象所处环境，如地理位置、时间、 江苏大学博士学位论文 序列等，可利用环境属性确定邻域；固有属性是数据对象特有属性，包 括行为属性和状态属性( 为简便起见，以下将行为和状态属性简称为行为 属性_ ) ，行为属性决定了一个数据对象的行为和状态特征，可利用行为属 性确定对象的离群程度。 提出基于空间离群度的空间离群点挖掘算法。基于上述思想，在空间离 群点的挖掘中，首先将数据对象的属性分为标识属性、空间属性和非空 间属性，利用空间属性确定空间邻域、建立空间索引，利用非空间属性 确定对象的离群度，据此提出了基于空间离群度的空间离群点挖掘算 法。在空间离群点挖掘算法设计中充分利用空间数据的自相关性和空间 异质性所表现出来的空间局部特性，利用空间属性确定空间邻域，在空 间离群度的度量上两次用到空间邻域，其离群程度反映了对象与其邻 域，以及邻居与其邻域间的关系，克服了现有算法中仅考虑对象与其邻 域间的单层关系，获得了真正意义上的空间离群点。 提出混合属性的统一的空间离群度的度量方法和挖掘算法。现有研究主 要集中在数值型属性上和少量的非数值型属性上，两者结合在一起处理 的很少，有限的几篇 2 0 - 2 2 1 对非数值型属性的处理也仅仅是采用简单匹配 的原则，因此处理比较简单，难以满足应用需要。从离群点本质特点出 发，对非数值型属性进行预处理转化为数值型数据，然后与数值型数据 一起采用统一的处理方法，提高了挖掘精度和算法的通用性。有关基于 混合属性的空间离群点挖掘的研究尚未见报道，通过上述预处理，提高 了基于空间离群系数挖掘算法的通用性和实用性。 提出基于集成学习的高维大数据量的空间离群点快速挖掘算法。利用标 识属性中含有的空间区域标识信息，构建层次编码树，利用层次编码树 结构实现快速分区和数据对象的快速搜索。对分区采用包围盒技术和剪 枝策略实现分区的剪枝，保留可能含有离群点的分区以便精确度量和挖 掘。对候选分区采用子空间挖掘和基于子空间权值的集成融合技术获得 每个数据对象的最终的离群值。利用优化技术解决了属性的权值的自动 提取和设置问题，有效解决了高维问题和大数据量的快速挖掘问题，避 免了大量搜索和大量计算工作，减少了对用户的依赖性。 4 江苏大学博士学位论文 提出基于分布环境的隐私保护的空间离群点挖掘算法。随着网络的发 展，数据呈现分布状态，采用集中式分析处理不大可行，需要研究基于