（管理科学与工程专业论文）空间聚类算法的研究.pdf

空间聚类算法的研究 摘要 信息技术的不断发展导致持续的数据收集和快速的数据积累。空间数据挖 掘是在空间数据库中提取隐藏的未知模式，而空间聚类是空间数据挖掘中一个 活跃的研究领域。 本文第一部分提出了一种新颖的启发式选择边界对象的快速空间聚类算法 d b s b 。通过一个启发式函数近似选择相对于某个已知核心对象边界区域中的核 心对象和边界对象，通过核心对象的序列来快速地扩展它们所在的簇，直至找到 一些较小的簇。在此基础上再通过边界对象快速地合并某些簇，即算法通过两步 聚类，达到最终的聚类。理论分析和实验结果表明该算法有效可行。 随着分布式计算环境的广泛应用，由于数据和计算能力分布在不同的节点， 本文第二部分设计了一种基于反向k 近邻的分布式聚类算法d c r k n n ，该算法 在分布式数据挖掘的框架下利用反向k 近邻的性质，分三个不同的阶段进行分 布式聚类。首先是局部模型的确立，通过局部模型来近似压缩局部站点的数据 集；其次在中央站点整合各分布的局部模型建立全局模型，最后根据全局模型 更新所有局部模型。同时d c r k n n 算法易于扩展到分布式离群数据挖掘中。理 论与实验分析说明该算法和集中式聚类结果的质量相当，且在一定程度上保护 了各局部站点的敏感数据，d c r k n n 算法执行效率高，分布节点之间的通信代 价小。 关键词；分布式数据挖掘，密度聚类，空间聚类，异常检测，反向k 近邻 r e s e a r c ho ns p a t i a lc l u s t e r i n g a l g o r i t h m s a b s t r a c t a d v a n c e si ni n f o r m a t i o nt e c h n o l o g i e sh a v el e dt ot h ee o n t i n u a lc o l l e c t i o na n d r a p i da c c u m u l a t i o no fd a t ai nr e p o s i t o r i e s s p a t i a ld a t am i n i n g ，o rk n o w l e d g e d i s c o v e r yi ns p a t i a ld a t a b a s e s ，r e f e r st oe x t r a c ti m p l i c i tr e g u l a r i t i e s ，r u l e s o r p a t t e r n sh i d d e ni nl a r g es p a t i a ld a t a b a s e s f i n d i n gc l u s t e r si ns p a t i a ld a t ai s a n a c t i v er e s e a r c ha r e ai ns p a t i a ld a t am i n i n g t h ef i r s tp a r to ft h i st h e s i sp r o p o s e san o v e ld e n s i t y b a s e ds p a t i a lc l u s t e r i n g m e t h o dw i t hh e u r i s t i c a l l ys e l e c t i n gb o r d e ro b j e c tc a l l e dd b s b t h ea l g o r i t h mf a s t e x p a n d st h ec l u s t e r sb yah e u r i s t i cf u n c t i o nt oc h o o s ec o r eo b j e c t si nt h eb o r d e r r e g i o no ft h ek n o w nc o r eo b j e c t ，a n dt h e nm e r g e ss o m ec l u s t e r sb yb o r d e ro b j c o t s t h a ti s ，t h ed b s ba l g o r i t h mg e t st h eu l t i m a t ec l u s t e r i n gr e s u l tt h r o u g ht w os t e p so f c l u s t e r i n g t h et h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t si n d i c a t et h a t t h e a l g o r i t h mi se f f e c t i v ea n de f f i c i e n t t h ec o n t i n u o u sd e v e l o p m e n t si nc o m p u t i n ga n dc o m m u n i c a t i o nt e c h n o l o g y o v e rw i r e da n dw i r e l e s sn e t w o r k sh a v er e c e n t l yl e dt om a n y p e r v a s i v ed i s t r i b u t e d c o m p u t i n ge n v i r o n m e n t s ，w h i c hc o m p r i s es e v e r a l ，a n dd i f f e r e n ts o u r c e so fl a r g e v o l u m e so fd a t aa n ds e v e r a lc o m p u t i n gu n i t sc o n n e c t e dt oe a c ho t h e rv i al o c a lo r w i d ea r e an e t w o r k s t h es e c o n dp a r to ft h i st h e s i sp r e s e n t sar e v e r s ekn e a r e s t n e i g h b o r ( r k n n ) b a s e dd i s t r i b u t e dc l u s t e r i n ga l g o r i t h m ，c a l l e dd c r k n nw h i c h c o n s i s t so ft h r e ed i f f e r e n ts t e p s ( 1 ) d e t e r m i n a t i o no fal o c a lm o d e lw h i c hc a n r e d u c et h es i z eo fd a t a s e to fl o c a ln o d e ；( 2 ) d e t e r m i n a t i o no fag l o b a lm o d e lw h i c h i sb a s e do na l ll o c a lm o d e l ；( 3 ) u p d a t i n go fa l ll o c a lm o d e l d c r k n nu t i l i z e st h e s t a t e o f - t h e - a r tp r o p e r t yo ft h er k n na n de m p l o y sd e c e n t r a l i z e dd a t am i n i n g f r a m e w o r k d c r k n nc a ne a s i l ye x t e n dt ot h ea l g o r i t h mo fd i s t r i b u t e do u t l i e r d e t e c t i o na n dp r o t e c tr a wp r i v a t e ，s e n s i t i v ed a t aa td i f f e r e n tn o d e st oac e r t a i n e x t e n t e x p e r i m e n t a le v a l u a t i o ni n d i c a t e st h a td c r k n na p p r o a c hb r i n g sh i g h q u a l i t yc l u s t e r s i nt h ed a t ar e s i d i n ga td i f f e r e n tn o d e so fn e t w o r kw i t hs c a l a b l e 仃a n s m i s s i o nc o s t k e y w o r d s ：d i s t r i b u t e dd a t am i n i n g ，d e n s i t y - b a s e dc l u s t e r i n g ，s p a t i a lc l u s t e r i n g ， o u t l i e rd e t e c t i o n ，r e v e r s ek n e a r e s tn e i g h b o r 插图清单 图1 1k d d 发现过程1 图1 2 数据挖掘和相关学科的关系一2 图2 1主要聚类算法的分类7 图2 2k d 树及其变种1 0 图2 3 r 树及其变种1 1 图2 4传统的基于数据仓库的数据挖掘框架1 4 图2 5分布式数据挖掘体系框架1 4 图3 1d b s b 算法的整体框架1 9 图3 2 簇相连接一2 0 图3 3环形区域2 0 图3 4参数 的确定2 l 图3 5 ( 左) 原始数据集( 右) d b s b 算法聚类结果2 4 图3 6算法性能比较2 5 图3 7两个点之间s n n 相似度计算2 6 图4 1分布式聚类框架。2 9 图4 2反向k 近邻查询示例。3 0 图4 3聚类分析与离群数据检测3 1 图4 4k n n 有向图3 2 图4 5r k n n 有向图一3 2 图4 6局部代表数据点生成算法框架3 5 图4 7全局模型生成算法3 5 图4 8分布式聚类与集中式聚类算法时间比较3 6 图4 9节点数与d c r k n n 算法运行时间关系3 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金目b 王些盍堂 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名 商劫 签字日期；7 ，矿年月厂日 ， 学位论文版权使用授权书 本学位论文作者完全了解金e b 王些盔堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金日b 工业盍堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 娩导师签名：5 留铆 签字日期：z 7 年占月j ，日 签字日期：舻7 年占月y 日 学位论文作者毕业后去向 工作单位： 通讯地址： 电话： 邮编： 致谢 首先感谢合肥工业大学接收了我，让我在学习生涯中有幸遇到了倪老师， 感谢倪老师三年多来的在学习上悉心的指导，感谢倪老师让我能在智能管理所 同师兄、师弟、师姐、师妹们共同度过了读研期间幸福的学习生活。 祝福刘晓在澳洲的学习和生活一帆风顺、名列前茅。 祝福李伟东在山东工行的工作前程似锦。 祝福赖建章去上海银联数据大大的赚钱。 祝福潘永刚在上海港的工作蒸蒸日上。 祝福忻凌在合肥生活和工作快快乐乐。 祝福刘志伟在深圳疯狂地挣大钱。 祝福刘烨和小师妹张伟莉工作轻松，生活幸福。 感谢在交大读博的师兄赖大荣，喜欢向师兄请教问题，师兄总是把他知道 的领域知识毫无保留地传授给我，让我受益匪浅。师兄生活简单，待人朴实无 华，在学习上不畏艰难、勇往直前，永远是我学习和生活中的榜样。 最后衷心地感谢父母，姐姐和姐夫，他们一直在物质，精神上给我鼓励、 支持和无微不至的关怀。祝福父母身体永远健康，姐姐和姐夫生活美满幸福。 h i 作者：陶亮 2 0 0 7 年5 月2 8 日 第一章绪论 随着数据收集和存储技术的迅速发展，各种组织机构在短时问内可以积累 海量数据。然而，提取有用的信息已经成为巨大的挑战。由于数据量太大，传 统的数据分析技术无法处理它们。有时，即使是较小的数据集，因为数据本身 的特点也不能使用传统的方法。在某些特定的情况下，需要解决的闯题也是已 有的数据分析方法无法解决的。因此必须开发出新的方法和技术数据挖掘 ( d a t am i n i n g ) 数据挖掘将传统的数据分析方法与处理海量数据的复杂算法相结合，广泛 的应用于很多领域。如：地球科学、科学与工程、商务智能、医学、生物信息 学和社会科学等领域。数据挖掘正以一种全新的概念改变着人类利用数据的方 式，该技术必将成为未来信息处理的骨干技术之一。 本章首先在1 。l 节介绍什么是数据挖掘、数据挖掘的起源及其发展，在1 2 节介绍数据挖掘的挑战，1 3 节介绍数据挖掘的研究现状，1 4 节概述本文研究 的主要内容和组织结构。 1 1 数据挖掘概述 1 1 1 数据挖掘定义 数据挖掘是在大型数据库中，自动发现有用的，先前未知信息的过程，是 知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 不可缺少的一部分，而k d d 是将原始数据转化为有用信息的整个过程。如图1 1 所示【。 图1 1k d d 发现过程 1 1 2 数据挖掘的起源及发展 数据挖掘的产生和发展一直是分析和理解数据的实际需求推动的。数据挖 掘是一个多学科交叉的研究领域，它融合了数据库技术、人工智能( a r t i f i c i a l i n t e l l i g e n c e ) 、机器学习( m a c h i n el e a r n i n g ) 、统计学( s t a t i s t i c s ) 、知识工程 ( k n o w l e d g ee n g i n e e r i n g ) 、信息检索( i n f o r m a t i o nr e t r i e v a l ) 、高性能计算( h i g h p e r f o r m a n c ec o m p u t i n g ) 、分布式并行计算( d i s t r i b u t e d & p a r a l l e lc o m p u t i n g ) 以 及数据可视化( d a t av i s u a l i z a t i o n ) 等最新学科的研究成果，从中汲取营养。如图 i 2 所示【l 】。特别地，利用了如下一些领域： ( 1 ) 来自统计学的抽样、估计和假设检验； ( 2 ) 人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论 最优化理论、计算复杂性理论( c o m p u t i n gc o m p l e x i t y ) 、进化计算、信息论、 信号处理、可视化和信息检索。一些其他领域也起到了重要的支撑作用。如： 高维的海量数据需要数据库系统提供有效的存储、索引和查找处理支持。高性 能并行计算在处理海量数据集也常常是十分重要的。尤其随着互联网、无线传 感器网络( w i r e l e s ss e n s o rn e t w o r k ) 、移动计算( m o b i l ec o m p u t i n g ) 以及对等计算 ( p e e r - t o p e e r ) 等技术的迅猛发展，数据无法集中到一起处理，这时分布式计算 技术将是至关重要的。 图1 2 数据挖掘和相关学科的关系 1 1 3数据挖掘任务 通常数据挖掘任务分为两大类： ( 1 ) 预测任务 该任务的目标是根据其他属性的值，称自变量( i n d e p e n d e n tv a r i a b l e ) ，预测 特定属性的值，称因变量( d e p e n d e n tv a r i a b l e ) 。如；预测建模( p r e d i c t i v em o d e l i n g ) 等。 ( 2 ) 描述任务 该任务是发现数据中潜在的模式。如：关联分析( a s s o c i a t i o na n a l y s i s ) 、分 类( c l a s s i f i c a t i o n ) 、聚类( c l u s t e r i n g ) 、异常检测( o u t l i e rd e t e c t i o n ) 等。 1 2 数据挖掘的挑战 ( 1 ) 伸缩性 由于数据产生、收集和存储技术的迅速发展，要处理海量数据集，算法必 须是可伸缩的( s c a l a b l e ) 。使用抽样技术( s a m p l i n g ) 或开发分布式并行算法也可 以提高可伸缩程度。 ( 2 ) 高维性 现在的数据常常是成百上千维的数据集，从而产生的维度灾难( c u r s eo f 2 d i m e n s i o n a l i t y ) 问题。如在生物信息学领域中的基因表达数据。为低维数据开 发的算法是不能很好地处理高维数据。随着维度、特征的增加，计算复杂性迅 速成指数级增长。 ( 3 ) 异构和复杂数据 传统的数据分析方法只处理包含相同类型属性的数据集，随着数据挖掘在 各种领域的应用，越来越需要能够处理异种和复杂数据的技术。如子图挖掘 ( s u b g r a p hm i n i n g ) 、联系发现( l i n kd i s c o v e r y ) 、点击数据流( c l i c ks t r e a m ) 、半 结构化文本和x m l 文档中元素问的关系等。 ( 4 ) 非集中式数据 随着分布式环境的发展，需要分析的数据并非存放在一个站点或网络中的 节点，而是地理上分布在多个机构或节点的资源中。这就需要分布式数据挖掘 技术。同时分布式数据挖掘技术也带来的一系列的问题。如：如何降低通信量、 如何处理数据安全性问题，从而也产生了基于隐私保护( p r i v a c y p r e s e r v i n g ) 的数 据挖掘技术。 1 3 数据挖掘的研究现状 数据挖掘领域冲破了当前数据分析技术在对现有新型数据集的局限，数据 挖掘将已有的数据分析技术当作其基础。许多学者和研究人员对这个新兴的交 叉学科表现了极大的兴趣。 现在有与许多数据挖掘相关的会议，都致力于该领域的研究，其中一些主 要的会议包括a c ms i g m o d 数据管理国际会议( s i g m o d ) 、a c ms i g k d d 知 识发现与数据挖掘国际会议( k d d ) 、i e e e 数据挖掘国际会议( i c d m ) 、s i a m 数 据挖掘国际会议( s d m ) 、欧洲数据库中知识发现原理与实践会议( p k d d ) 和亚太 知识发现与数据挖掘会议( p a k d d ) 。以及其它的一些会议如：v l d b 、i c d e 、 i c m l ，从a i 。数据挖掘相关的期刊包括i e e et r a n s a c t i o no nk n o w l e d g ea n d d a t ae n g i n e e r i n g ( t k d e ) 、d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ( d m k d ) 、 k n o w l e d g ea n di n f o m a t i o ns y s t e m s ( k a i s ) 。 美国佛蒙特大学x i n d o n gw u 2 1 和香港科技大学q i a n gy a n g 3 】为了准备 i c d m2 0 0 5 ，他们通过一段时间信息的收集与众多数据挖掘领域的专家共同提 出了数据挖掘中十大挑战性的问题【6 0 】： ( 1 ) 建立数据挖掘的统一理论； ( 2 ) 大大提升高维数据和高速数据流挖掘算法； ( 3 ) 挖掘序列和时序数据； ( 4 ) 从复杂数据中挖掘复杂的知识： ( 5 ) 各种网络中的数据挖掘； ( 6 ) 分布式数据挖掘和挖掘多a g e n t 数据； ( 7 ) 生物和环境问题中的数据挖掘； ( 8 ) 数据挖掘流程中的相关问题； ( 9 ) 数据挖掘中数据安全性、隐私性和完整性保护； ( 1 0 ) 数据挖掘中非静态、非平衡和代价敏感数据的处理。 同时，在i c d m2 0 0 6 专门小组的讨论中，由x i n d o n g w u 和明尼苏达大 学v i p i nk u m a r 6 1 1 作为组织协调者，专家小组成员通过提名候选算法、g o o g l e s c h o l a r 确认、投票3 步流程选出数据挖掘中十大算法的候选1 8 个算法，最后 通过k d d 2 0 0 6 、i c d m 2 0 0 6 、和s d m 2 0 0 6 程序委员会的成员们以及a c mk d d 创新奖和i e e ei c d m 研究贡献奖的获奖者们共同投票决定选出了位居前十位 的算法1 6 2 】： ( 1 ) c 4 5 ( 6 1 票1 ( 2 ) k m e a n s ( 6 0 票) ( 3 ) s v m ( 5 8 票) ( 4 ) a p r i o r i ( 5 2 票) ( 5 ) e m ( 4 8 票1 ( 6 ) p a g e g a n k ( 4 6 票) ( 7 ) a d a b o o s t ( 4 5 票) ( 7 ) k n n ( 4 5 票) ( 7 ) n a i v eb a y e s ( 4 5 票) ( 10 ) c a r t ( 3 4 票) 1 4 论文的研究目的及组织结构 本文主要目的是研究空间聚类相关的理论、方法和应用。如：带约束条件 ( o b s t a c l e sa n df a c i l i t a t o r s ) 的空间聚类、对非点状、复杂对象( n o n p o i n t 、c o m p l e x o b j e c t ) 的聚类以及子空间聚类( s u b s p a c ec l u s t e r i n g ) 。重点研究了基于密度、共 享最近邻以及反向k 近邻等技术相关的空间聚类方法，同时将分布式计算和反 向k 近邻技术相结合用来对高维数据集进行分布式数据挖掘。 第一章是绪论，介绍了数据挖掘的起源与发展，以及数据挖掘领域中的挑 战，并概要地叙述了当前数据挖掘的研究现状等。 第二章是空间聚类背景知识及其相关工作的介绍，概要介绍了当前现有的 空间聚类算法的种类。由于在空间聚类算法中为了减少聚类的时间复杂性，需 要引入的索引技术，本章适当地详述了相关的索引技术。最后，简述了分布式 并行计算相关技术以及将其与空间聚类算法相结合。 第三章提出了一种基于密度的启发式选择边界对象快速空间聚类算法 d b s b ，通过一个启发式函数近似选择相对于已知核心对象边界区域中的核心 对象和边界对象，其中通过核心对象的序列来快速地扩展它们所在的簇，直至找 4 到一些较小的簇。在此基础上再通过边界对象快速地合并某些簇，即该算法通过 两步聚类，达到最终的聚类。然后对该算法进行了相关理论分析和性能分析，同 时实验结果表明该算法有效可行，最后对d b s b 算法的进一步扩展作了相关分 析。 第四章基于反向k 近邻和分布式数据挖掘体系架构，提出一种分布式聚类 算法d c r k n n 。首先在各个局部站点根据反向k 近邻特点找到该局部站点簇的 边界以及离群点信息传输到中央节点作为对该局部站点的近似处理，因为在局 部是离群点有可能在全局的数据集上是属于某个簇的信息。这样传输到中央节 点的数据量就会大大的减少，有效地减少了通信代价。然后，中央节点根据各 个局部站点传输来的信息产生出全局的模型，发送至各局部站点以更新局部模 型，从而完成最终的分布式聚类。 第五章是本文的总结，以及对该领域课题的未来研究计划。 第二章空间聚类背景及其相关工作 聚类分析是一种无监督的学习方法，可以把数据集按定义的相似性进行分 类。聚类技术主要用于进行数据探索，并给出数据描述，而且还可以作为数据 预测、内容检索等其他方面应用的起点。聚类分析在生物学( 用来发现生物体 系统的类别以及分析遗传信息等) 、信息检索( 将搜索引擎产生的结果分成若 干个簇用来捕获查询的某个特定方面，用来方便用户进一步浏览查询结果等) 、 医学( 用来发现疾病的多个变种，检测疾病的时空分布模式等) 等领域【l j 有着 广泛应用。 本章首先概述了聚类定义以及主要聚类方法的分类。2 。2 节介绍了与空间 聚类密切相关的空间索引技术，2 3 节主要讨论了分布式计算以及在分布式环 境下空间聚类。 2 1 空闯聚类 2 1 1 聚类概述 对于一个给定的数据集，聚类就是将数据集中的对象划分为群或类，使得 一个类中的对象“类似”，而不同类中的对象“不类似”。即：簇类的相似性 越大，簇间差别越大，聚类越好【4 1 。 聚类分析问题形式化描述为：给定朋维空间中的数据集s ，设有厅个向 量，s = 阢，别，把每个向量归属到足个聚类中的某个，使得每个向量 与其聚类中心的“距离”最小换句话说，寻找一个映射f ts 一 1 ，2 ， k ，( k 有限，但不必事先指定) 5 3 1 。 聚类分析问题的实质是一个全局最优问题。此处，r n 可认为是样本参与聚 类的属性个数，一是样本的个数，置是将要得到的聚类个数。 对于坍维空间l p 中的向量蜀，局； x f = x i l tx 1 2 ，tx t 矗 x j = t x i l x i 2 ，x i 毒 向量蜀，乃之间的“距离”为：d p = m ( ( ) ( i 国溺k ) ) 。 面 其中 为运算符号，即相同属性之间的比较方式，其中i ，j e 【l ， r “仃，即i ， j 取遍所有的有效相关集，这里，i r 4 i = n 。相似性函数o ( x ，y ) 由记录墨y 之间的 距离来确定。假设 是由领域专家给出的阈值，并根据此值来确定类别，最终 的类别由特定的任务和 值的范围来确定。 6 2 1 2主要聚类方法的分类 现有文献中存在大量的聚类算法，大致可以分以下几大类：分裂法、层次法、 基于密度的方法、基于网格的方法和基于模型的方法等【”1 ，如图2 1 所示【5 】。 蓁二三三三二 w a v e c l u s t e r g r i dc l n s t e m g d e n c l u e b a n g c l i q u e c l u s t e r i n g o p ，兀c s d b s c a n c h a m e l e o n k - m e a n s k - m o d e s k - m e d o i d s i n g l el i n k p a m c u r e c l a r a b 珉c h c l a r a n s 分裂的分层的 、，- - - - - - - - 按照结果分类 图2 1 主要聚类算法的分类 1 分裂法( p a r t i t i o n i n gm e t h o d ) 给定一个有n 个元组或者纪录的数据集，分裂法将构造k 个分组，每一个 分组就代表一个聚类，k 一m i n c a r d 。 从定义3 2 中可以得出w c a r d 不仅可以对空间对象中的空间属性进行定义， 而且还可以扩展到非空间属性。 定义3 3 ：( 核心对象c o r e o b j e c t ) 根据定义3 1 、3 2 ，c o r e o b j e c t ( o ) 铮 w c a r d ( n n 。i ( o ) ) m i n c a r d 。 定义3 4 ：( 直接密度可达d i r e c td e n s i t y - r e a c h a b i l i t y ) 根据定义3 1 、3 2 、 3 3 ，给定空间d ，v ，牙，d i r e e t r e a c h ( q ，p ) c o r e o b j e e t ( q ) a p n m ( q ) 。 定义3 5 ：( 密度可达d e n s i t y r e a c h a b i l i t ”假设空间d 中对象p l ，p 。，p l = q ， p n = p ，r e a c h ( q ，p ) 亭3 p l ，p n d ：p l = q a p = p av i 1 ，n l ：d i r e c t r e a c h ( p i ，p i + 1 ) 。 定义3 6 ：( 密度连接d e n s i t y c o n n e c t i v i t y ) 对空间d 中任意对象q ，p ，如果存 在对象o ，使得p 和q 到o 都是密度可达的，则称q 与p 是密度连接的。即： c o n n e c t ( q ，p ) 曹3 0 d ：r e a c h ( o ，q ) a g e a c h ( o ，p ) 。 定义3 7 ：( 密度连接簇d e n s i t y - c o n n e c t e ds e t ) 假设空间d 中的非空子集 s d ，如果s 中的所以对象在d 中都是密度连接的，则称为密度连接簇。即：一 个密度连接簇定义为一个极大密度连接对象的集合。c o n n e c t e d s e t ( s ) 营v o ，q s ：c o n n e c t ( o ，q ) 。 定义3 8 ：( 噪音n o i s e ) 假设空间d ，c l u s t e r = c 1 ，c d ，显然有n o i s e = d 、 c l u u c k ) 3 2d b s b 算法 3 2 1d b s b 算法思想与框架 d b s b 算法受传统的基于密度聚类算法d b s c a n 和o p t i c s 的启发，通过 1 8 一个启发式函数近似选择相对于某个已知核心对象环形边界区域中的核心对象 和边界对象，通过核心对象序列来快速地扩展它们所在的簇，同时对数据空间 中一些丢失对象进行处理，直至找到一个完整的簇。由于这些簇的数量较少， 在此基础上通过d b s b 算法过程中保存的边界对象会快速地合并某些簇，达到 最终的聚类效果。为了提高d b s b 算法的效率在空间查询中采用了s r t r e e 索 引结构。由于该算法采用的是基于密度的思想，能够有效的屏蔽了噪音对算法的 影响，而且该算法大大减少了区域查询的次数，从而降低了聚类的时间以及 c p u 、i o 开销。特别地，在高密度的数据集下，d b s b 算法表现出了良好的性 能。算法的整体框架如图3 1 所示。 图3 1d b s b 算法的整体框架 3 2 2d b s b 算法的相关定义 下面为了方便地描述算法，以二维空间为例来分析d b s b 算法。首先泛化定 义3 1 中的邻域的概念，显然在二维空间中，可以定义基于欧氏距离的邻域。 即：n e p 。( o ) 奄 d e d0 0 - - 0 i s e p s ) 。 定义3 9 ：( 相交核心对象o v e r l a pc o r e o b j e c t s ) 对于任意两个核心对象q 、p ， 有q 、p 互为相交核心对象o v e r l a p c o r e o b j ( q ，p ) 营o e u c l i d d i s t a n c e ( q ，p ) 2 + e p s 。 定义3 1 0 ：( 相离核心对象d i s j o i n tc o r e o b j e c t s ) 对于v c o r e o b j e c t ( p ) 、 c o r e o b j e c t ( p ) ，有q , p 互为相离核心对象d i s j o i n t c o r e o b j ( q ，p ) e u c l i d d i s t a n c e ( q ，p ) 2 + e p s 定义3 1 1 ：( 共享边界对象s h a r e db o r d e r o b j e c t ) 若存在至少2 个核心对象 q , p ，q 和p 分别属于不同的，且0 分别从q 和p 密度可达，则称0 为“共享边界 对象”。 下面从二维空间中分析：假设m i n c a r d = 6 ，从图3 2 中可以得出c a r d ( n n e l ( o ) ) = 5 m i n c a r d 。所以显然有共享对象o 不会是核心对象，否则q 与p 就会经o 密度相连。即：共享对象o 位于簇的边缘。 定义3 1 2 ：( 簇相连接c l u s t e rc o n n e c t i v i t y ) 若簇c l 与簇c 2 拥有共享边界对 象o ，则认为c l 与c 2 相连接。如图3 2 所示，o 为簇连接对象，簇i ( 空心点构 1 9 成) 与簇2 ( 实心点构成) 相连接，其中m i n c a r d = 6 。 oo o o 图3 2 簇相连接 定义1 3 ：( 环形区域a n n u l a r a r e a ) 如图3 3 所示，外圈的半径( 实线所表示) 为e p s ，内圈的半径( 虚线所表示) 为九* e p s ，所以核心对象q 的中空邻域是 n e p s ( q ) n - e p s ( q ) 图3 3 环形区域 3 2 3 关键参数 的自动确定 在经典d b s c a n 算法中会作一些大量的没有价值的区域查询操作，而区域 查询操作是十分消耗时间的。通过分析得到，同一个邻域内的对象的邻域会相 互覆盖，当一个对象的邻域完全披其他对象的邻域所覆盖时，其邻域可以通过 对覆盖它的其他对象进行区域查询得到，这意味着该对象不必作为种子对象。 而这样的对象基本处于邻域的内圈，因此本文选取邻域的外圈( 即中空球形邻域) 中的对象作为种子对象。那么如何动态地确定环形区域中的对象将是十分重要 的工作。 如图3 4 所示，假设q 是核心对象，由上述定义9 可以得出，如果环形区 域中的种子对象p 是核心对象，那么q 与p 一定是相交核心对象，所以q 与p 一定在同一个簇内。如果对象p 不是核心对象，那么p 一定是边界对象，因为 在p 的邻域内一定有对象是核心对象。显然只有低密度对象邻域里的所有对象 都是低密度的，这时此低密度对象才一定是噪音。 2 0 图3 ，4 参数x 的确定 显然当核心对象q 的密度越大，参数 越大，即参数 与核心对象n b p 。( q ) 与m i n p t s 的比值成正比如图3 4 所示，假设对象p 在核心对象对象q 的以 * e p s 为半径的邻域上，n - e 口s ( q ) m i n p t s ，为了使n e v 。( p ) m i n p t s ，可得出 1 2 。为了加速簇的生成，尽量减少边界对象的个数，这时取x = 1 2 。所以作一 个启发式函数f ( n ) 来确定参数x 。 令i l = n e p s ( q ) m i n p t s ，经过分析有如公式3 1 所示的函数表达式，同时实 验结果表明如公式3 i 所示的函数表达式是可行的。 a = 饷，郴；叩1 嚣 - 3 2 4d b s b 算法描述 首先随机选择任一核心对象q ，计算出该核心对象q 的1 1 值，然后用欧氏 距离判断邻域内的每一个对象到核心对象q 的距离是否大于 e p s ，如果大于 x e p s ，则把该对象作为种子对象添加到用于扩展的种子对象集合中。同时建 立邻域内的对象到核心对象的映射。如果种子对象集合为空，采用随机查找一个 核心对象p ，然后判断该核心对象p 的邻域是否与已有的簇相交，即满足定义 3 9 相交核心对象的条件，这时把核心对象p 及其邻域合并到已有的簇中。具 体的详细步骤见算法3 1 、3 2 所示。 算法3 1 ；d b s b 算法框架。 d b s b ( s e t o f o b j e c t 8 ，n e i ，m i n c a r d ，w c a r d ) c l u s t e r l d = n e x t l d ( n o i s e ) ； f o r e a c h ( o b j e c to b ji ns e t o f o b j c o t s ) t f ( o b j c l l d = u n c l a s s i f i e d ) i f e x p a n d c l u s t e r ( o b j ，c l u s t e r i d ) 详见算法3 2 c l u s t e r l i s t a d d ( c l u s t e r i d ) ；添加簇的信息到c l u s t e r l i s t 中 c 1 u s t e r i d = n e x t i d ( c l u s t e r i d ) ； ) ) e n df o r e a c h 2 1 m e r g e c l u s t e f ( b o r d e r l i s t ，n e i ) 详见算法3 4 算法3 。2 ：形成簇的过程。 b o o l e a ne x p a n d c l u s t e r ( o b j e c t ，c l l d ) s e e d s = s e t o f o b j e c t s n e i g h b o r h o o d ( o b j e c t ，n e i ) ； e t a - - w c a r d ( s e e d s ) m i n c a r d ； i f ( e t a f ( e t a ) + e p s ) ； c u r r e n t o b j e c t = s e e d s l i s t f i r s t o b j e c t ； c o n s t r u c t c l u s t e r ( c u r r e n t o b j e c t ，c l i d ) ；详见算法3 3 r e t u r nt r u e ； ) 算法3 3 ；通过反复的区域查询操作构造某一族。 v o i dc o n s t r u c t c l u s t e r ( c u r r e n t o b j ，c i i d ) w h i l e ( ! c u r r e n t o b j e m p t y ) r e s u l t = s e t o f o b j e c t s n e i g h b o r h o o d ( c u r r e n t o b j ，n e i ) ； e t a = w c a r d ( s e e d s ) m i n c a r d ； i f ( e t a 1 ) f o r e a c h ( o b j c o toi nr e s u l t ) ( s w i t c h ( o c i i d ) c a s u n c l a s s i f i e d ： i f ( ( d i s t ( c u r r e n t o b j ，o ) f ( e t a ) + e p s ) ) s e e d s l i s t a d d ( r e s u l t p ) ； s e t o f o b j c o t s c h a n g e c l i d ( r e s u l t p ，c l l d ) ； b r e a k ； c a s en o i s e ： b o r d e r l i s t a d d ( r e s u l t p ) ；添加至边界对象列表中 s e t o f o b j c o t s c h a n g e c l l d ( o ，c i i d ) ； b r e a k ；