（计算机软件与理论专业论文）基于密度的子空间聚类算法研究.pdf

摘要聚类分析是数据挖掘领域最重要的研究热点之一，旨在将数据对象分组成为多个簇类，有着广阔的应用前景。随着技术进步，聚类分析许多应用领域的数据具有很高的维度。这些数据集中存在大量无关的属性，使得在所有维中存在簇的可能性几乎为零；同时，产生“维度效应”现象：数据分布变得稀疏，数据间距离几乎相等非常普遍，传统的距离度量方式将失去作用。因此，为面向高维大规模数据集的聚类分析寻找适当的方法已经成为研究工作的重点。子空间聚类正是基于上述背景提出的，用于在数据集的不同子空间上查找簇类，具备传统聚类方法很难实现的优点。本文着重对基于密度的子空间聚类算法进行研究，主要工作包括以下几个方面：对聚类分析领域的基本概念做了深入的分析，研究了目前聚类技术中的主要算法，并介绍了面向高维数据的聚类分析技术，同时还给出了常用的子空间聚类算法，分析了它们的优缺点。针对传统方法产生大量冗余簇的不足，本文提出了一种查找无冗余簇的基于密度子空间聚类算法n r s c 。该算法使用贪心策略将每个对象自动地分配到维度最大的子空间上，对簇类做了进一步过滤，从而有效地减少了冗余簇，同时也增强了聚类结果的可理解性。针对许多基于密度的子空间聚类算法存在内存消耗太大的困扰，本文提出了一种基于密度和极大团的子空间聚类改进算法d m a x c 。该算法使用极大团的方法划分数据空间，采用分治策略解决数据维度很高而内存空间不足的矛盾；利用基于参考点的聚类概念来描述数据空间几何特征，有效降低了算法时间复杂度。关键词：聚类分析；高维数据；子空间聚类a b s t r a c tc l u s t e ra n a l y s i si so n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d si nd a t am i n i n g i ta i m sa tg r o u p i n gas e to fd a t ao b j e c t si n t oc l a s s e so fs i m i l a ro b j e c t s ，a n dh a s 谢d ea p p l i c a t i o np r o s p e c t s w i t l ld e v e l o p m e n to ft e c h n o l o g y , t h ed a t ai nm a n ya p p l i c a t i o nf i e l d sa r ea l w a y so fh i g hd i m e n s i o n s m a n yo ft h ed i m e n s i o n sa r eo f t e ni r r e l e v a n t t h e s ei r r e l e v a n td i m e n s i o n sc a nc o n f u s ec l u s t e r i n ga l g o r i t h m sb yh i d i n gc l u s t e r si nn o i s yd a t a m o r e o v e r , w h e nd i m e n s i o n a l i t yi n c r e a s e s ，d a t au s u a l l yb e c o m ei n c r e a s i n g l ys p a r s et h a ti ss oc a l l e dc u r s eo fd i m e n s i o n a l i t y w h e nt h ed a t ab e c o m er e a l l ys p a r s e ，d a t ap o i n t sl o c a t e da td i f f e r e n td i m e n s i o n sc a nb ec o n s i d e r e da sa l le q u a l l yd i s t a n c e d ，a n dt h ed i s t a n c em e a s u r e ，w h i c hi se s s e n t i a lf o rc l u s t e ra n a l y s i s ，b e c o m e sm e a n i n g l e s s s u b s p a c ec l u s t e r i n gi so n eo ft h es o l u t i o n st ot h i sc h a l l e n g e i ts e a r c h e sf o rg r o u p so fc l u s t e r sw i t h i nd i f f e r e n ts u b s p a c e so ft h es a m ed a t a s e t s u b s p a c ec l u s t e r i n gh a sm a n ya d v a n t a g e st h a tt r a d i t i o n a lc l u s t e r i n gm e t h o d sd on o tp o s s e s s t h i sd i s s e r t a t i o nf o c u s e so nd e n s i t y - b a s e ds u b s p a c ec l u s t e r i n ga l g o r i t h m s ，a n di tc o n t a i n ss o m ec o n t e n t sa sf o l l o w s ：f i r s t ，b a s i cc o n c e p t s ，p r i m a r ya l g o r i t h m so fc l u s t e ra n a l y s i s ，a n dt e c h n i q u e sf o rc l u s t e r i n gh i g hd i m e n s i o n a ld a t aa r ei n t r o d u c e d t h e n , c o n v e n t i o n a ls u b s p a c ec l u s t e r i n gm e t h o d sa n dr e l a t i v em e r i t so ft h e ma r ed i s c u s s e d m a n yt r a d i t i o n a lm e t h o d se n u m e r a t ec l u s t e r si na l ls u b s e t so fa t t r i b u t e s t h e s em e t h o d sp r o d u c em a n yr e d u n d a n tc l u s t e r s t h i sd i s s e r t a t i o np r o p o s e sas u b s p a c ec l u s t e r i n ga l g o r i t h mn a m e dn r s ct h a tc a nf i n dn o n - r e d u n d a n tc l u s t e r s i ta s s i g n se a c ho b j e c tt ot h ec l u s t e ri nt h eh i g h e s td i m e n s i o n a ls u b s p a c e ，a n dr e d u c e sc l u s t e r sa u t o m a t i c a l l y t h er e s u l tc l u s t e r sc a nb em o r ee a s i l yc o m p r e h e n d e d m a n yd e n s i t y - b a s e ds u b s p a c ec l u s t e r i n gm e t h o d ss u f f e rf r o mh u g em e m o r yc o n s u m p t i o n a n o t h e rn o v e la l g o r i t h mc a l l e dd m a x ci sp r o p o s e dt oa l l e v i a t et h em e m o r yp r o b l e m d m a x cp a r t i t i o n sf e a t u r es p a c ev i am a x i m u mc l i q u e ，t h e ni ts e a r c h e sc l u s t e r sb a s e do nt h ep a r t i t i o n s t h ec o n f l i c tb e t w e e nm e m o r ya n dh i 曲d i m e n s i o n so fd a t ai sr e s o l v e d d m a x cc a p t u r e st h es h a p ea n de x t e n to fac l u s t e rb yr e f e r e n c e s s e a r c hc o s t sa r er e d u c e de f f e c t i v e l y k e y w o r d s ：c l u s t e ra n a l y s i s ；h i g hd i m e n s i o n a ld a t a ；s u b s p a c ec l u s t e r i n g厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。本人在论文写作中参考其他个人或集体己经发表的研究成果，均在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学术活动规范( 试行) 。另外，该学位论文为() 课题( 组)的研究成果，获得() 课题( 组) 经费或实验室的资助，在() 实验室完成。( 请在以上括号内填写课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特别声明。)声明人。签孙裘德出刁年j 月刁日厦门大学学位论文著作权使用声明本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于：() 1 经厦门大学保密委员会审查核定的保密学位论文，于年月日解密，解密后适用上述授权。，( ) 2 不保密，适用上述授权。( 请在以上相应括号内打“”或填上相应内容。保密学位论文应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权。)声明人：曼偌丸姗7 年r 月2 7 日第一章绪论1 1 研究背景及其意义第一章绪论1 1 1 数据挖掘技术随着数据收集技术的发展，在商业和科学研究等诸多不同的领域，经常会产生大量的数据。传统的数据分析方法和技术只适用于对小规模数据库作一些简单的分析，面对快速增长的海量数据和比较复杂的高层分析任务，过去所采用的数据分析方法显得无能为力，这就导致了人们虽然拥有丰富的数据，却对数据中知识的掌握仍停留在过去的水平，即所谓的“数据丰富，但信息贫乏”现象1 】【2 】。人们迫切地需要有一种分析技术能从这些数据集中发现隐含的、事先未知的，但是又潜在有用的并最终可理解的信息和知识。要解决这些问题，就需要一种强大的数据分析工具。在这种情况下，基于数据库的知识发现( k d d ，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 ) 和数据挖掘( d m ，d a t am i n i n g ) 应运而生并显示出强大的生命力。数据挖掘，顾名思义就是从大量的数据中挖掘出有用的信息，即从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律性的、人们事先未知的、但又是潜在有用的并且最终可理解的信息和知识的过程【3 1 。数据挖掘是一门综合性的交叉学科，它涉及到机器学习、模式识别、统计学、数据库技术、数据可视化、高性能计算等技术等多种领域和学科，如图1 1所示。数据挖掘从一开始就是面向应用的，它对数据库中的数据进行微观、中观甚至宏观的统计、分析、综合和推理，用来指导实际问题的求解，企图发现事件之间的关联，利用已有的数据对未来的活动进行预测。这样一来，人们对数据的应用就从低层次的末端查询操作提高到为决策者提供决策支持。基于密度的子空间聚类算法研究回 叵巨回图1 1 数据挖掘相关技术数据挖掘不是经过次处理就能得出结果的，它是一个反复循环的过程，这个过程是由许多相互联系的步骤组成的，比如建立挖掘目标，数据选择及预处理、进行数据挖掘、结果分析、知识应用等。图1 2 表述了数据挖掘的一般过程。数据源图1 2 数据挖掘的一般过程第一章绪论( 1 ) 建立挖掘目标：清楚定义挖掘对象，认清数据挖掘的目标是数据挖掘的第一步工作。数据挖掘的最后结果往往是不可预测的，但是要探索的问题应该是具有预见性的。如果为了数据挖掘而进行数据挖掘一般不会成功，因为带有一定的盲目性。在定义挖掘对象时，需要确定这样一些问题：从何入手、需要挖掘什么数据、要用到哪些数据、数据挖掘要进行到什么程度等。( 2 ) 数据选择及预处理：数据挖掘处理的对象是大量的数据，这些数据一般存储在数据库系统中，是长期积累的结果，但往往不适合直接挖掘，需要做一些准备工作。从数据源中抽取可用于挖掘的变量和数据的子集，也就是要从大量的数据中取出那些与系统要挖掘的目标相关的样本数据子集，一般包括数据的选择、净化、转换等，同时要保证这些数据的准确性和完整性。首先要进行的就是数据的选择工作。需要搜索所有的与挖掘目标相关的内部和外部数据，从中选出适合于应用的那些数据。这就意味着要集成和合并到同一个库中，并且协调来自多个数据源的数据在数值上的差异。同时还要根据数据挖掘的需要，分析清楚哪些是比较重要的数据源。其次，要对数据进行预处理，清除噪声和脏的数据。对数据进行清洗，解决数据中的缺值、冗余、数据不一致等问题。有时还要对数据分组，以提高数据挖掘的效率。数据挖掘过程中的数据选择和预处理是数据准备的核心工作，要花费大量的时间和精力做好这项工作。( 3 ) 数据挖掘：这一阶段进行实际的挖掘工作。首先是算法规划，即决定采用何种类型的数据挖掘方法，如数据总结、分类、聚类、关联规则发现或序列模式发现等。然后，针对该挖掘方法选择一种算法。而算法的选择直接影响着所挖掘模式的质量。完成了上述的准备工作后，就可以进行数据挖掘了。这个阶段是数据挖掘分析者和相关领域专家最关心的阶段，也可以称之为真正意义上的数据挖掘。( 4 ) 结果分析：对挖掘出的结果进行解释和评估。具体的解释和评估方法一般根据数据挖掘操作结果所制定的决策来定，通常在使用数据挖掘结果之前1 基于密度的子空间聚类算法研究希望能够对挖掘的结果进行评估，以保证挖掘结果在实际应用中的成功率。通常应用可视化技术进行结果分析。( 5 ) 知识应用：挖掘的结果经过业务决策者的认可后方可投入实际应用。要将数据挖掘得到的预测模式和各领域的专家知识结合到一起，构成一个可供不同人使用的结果。1 1 2 聚类分析聚类分析是数据挖掘的一种重要的挖掘任务和挖掘方法，它将对象划分为一系列的子对象( 或类) ，使得每一类中的数据尽量的相似，不同类尽可能的有较大差异。聚类分析是一种新兴的多元统计的方法，最早被运用在分类学中，形成了数值分类学这个学科。统计学中常用的分类统计方法主要是聚类分析和判别分析。而后，随着统计软件的发展，聚类分析被引进到统计分析中来，形成了聚类分析这样一种多元分析方法。目前较广泛使用的聚类方法有k - m e a n s 【4 1 ，肛m e d o i d s 5 1 ，f c m ( f u z z yc m e a n s ) 【6 1 等。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题，并在很多领域中有着广泛的应用，如模式识别、图像处理、数据压缩、空间数据分析、市场研究、w w w 上的文本分类、对w e b 的日志数据聚类以后发现相似的访问模式等。随着聚类分析应用的领域不断扩展和深入，我们经常会碰到一些数据集，它们少则数十维，多则上千维，这给传统的聚类分析技术带来了困难，现有的多数算法基于数据集的全空间进行聚类，往往不能满足高维数据的分析需要。随着数据维度的增加，数据点极其稀疏，而且数据集中存在大量无关的属性，使得在所有维中存在簇的可能性几乎为零；同时，数据维度的增加还将产生“维度效应，【7 】( c u r s eo fd i m e n s i o n a l i t y ) 现象：数据分布变得稀疏，数据间距离几乎相等非常普遍，传统的距离度量方式将失去作用。因此，为面向高维大规模数据集的聚类分析寻找适当的方法已经成为聚类分析领域的研究重点。4 第一章绪论1 2 研究和应用现状从2 0 世纪8 0 年代末至今，k d d 和数据挖掘技术得到了很大的发展。k d d这一术语首先出现在1 9 8 9 年在美国底特律召开的第1 1 届国际人工智能联合会议的专题研讨会上。1 9 9 5 年提出了数据挖掘概念作为知识发现过程的核心步骤，但是现在一般不对这两个概念加以区分，常用数据挖掘来表示知识发现。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议，以后每年召开一次。1 9 9 8 年筹备了a c ms i g k d d 兴趣组，并于1 9 9 9 年将k d d 国际会议纳入a c m 兴趣小组的系列重要会议中。此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊，都将数据挖掘列为重要的研究专题，为数据挖掘的研究和发展提供了很好的平台。目前，国外数据挖掘研究的发展趋势主要有：对知识发现方法的研究进一步发展；传统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。数据挖掘商业用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心进行这方面的工作。随着国外知识发现的兴起，我国也很快跟上了国际步伐。计算机世界报技术专题版于1 9 9 5 年3 月发表了由中国电子设备系统工程公司研究所李德毅教授组织的k d d 专题；于1 9 9 5 年4 月发表了由中国科学院史忠植研究员组织的“机器学习、神经网络”专题；于1 9 9 5 年1 2 月发表了由国防科技大学陈文伟教授组织的“机器发现和机器学习”专题。1 9 9 9 年和2 0 0 7 年p a k d d 会议在北京和南京召开，对我国开展知识发现的研究起到了一定的推动作用【2 。近几年，国内各计算机学术刊物也纷纷刊登有关知识发现和数据挖掘的论文，涉及的研究领域集中于学习算法和有关数据挖掘的理论研究。高维数据的聚类分析方法是近年来数据挖掘的一个较为活跃的研究领域，基于密度的子空间聚类算法研究涉及多方面的内容，主要有以下六个方面：( 1 ) 维度约简：通过降维将原高维属性规约到较低维空间，从而可以利用传统的方法在规约后的空间完成挖掘。包括特征提取( f e a t u r et r a n s f o r m a t i o n ) 和特征选择( f e a t u r es e l e c t i o n ) 两类方法【7 】【5 2 1 。( 2 ) 高维数据索引：构造高效的高维索引结构和改进高维相似性查询的性能。r - t r e e 和b t r e e 等多维索引结构随维数增长其搜索和查询性能急剧下降，为此已提出了a t r e e 、i q t r e e 等【5 3 】【5 4 1 。( 3 ) 高维离群点检测：高维数据的稀疏分布特征使得高维离群点的检测变得困难【5 5 】【5 6 】，传统的基于深度、偏差、距离或密度的方法阳性能受到影响，为此文献 5 8 1 等提出基于超图模型的方法；文献【5 9 】使用遗传算法在子空间中搜索高维离群点等。( 4 ) 高维聚类算法：可通过改进相似度度量可将传统聚类算法用于高维数据的聚类分析，例如s p h e r i c a l k m e a l l s 【6 3 1 用c o s i n e 度量改进了k - m e a n s算法，用于文本聚类。另一类算法基于空间变换的方法将高维空间的对象映射到低维空间进行聚类，如文献 6 4 【6 5 】等；核聚类方法【删利用核函数将对象映射到更高维空间进行聚类。以上方法的特点是，认为特征对所有的簇类具有相同的重要性。与之对应的是子空间聚类( s u b s p a c ec l u s t e r i n g ) 7 1 、协同聚类( c o c l u s t e r i n g ) 6 7 】【6 引、投影聚类( p r o j e c t i v ec l u s t e r i n g ) 1 2 】【叫和b i c l u s t e r i n g l 5 0 1 等，它们共同特点是认为特征对不同的簇类其重要性是有差异的，或者说簇类只与特定的特征子集相关联。( 5 ) 聚类有效性：指对聚类算法结果进行量化评价的方法 6 0 1 ，已提出外部有效性( e x t e r n a lc l u s t e rv a l i d i t y ) 、相对有效性( r e l a t i v ec l u s t e rv a l i d i t y ) 和内部有效性( i n t e r n a lc l u s t e rv a l i d i t y ) 等方法【6 0 】【6 l 】。( 6 ) 高维聚类结果表示方法：高维数据聚类结果的可视化表达是另一个难题，难点在于如何同时表达各维数性的分布，已提出的有d n f t 8 】【9 】、属6 第一章绪论性空间聚类知识表剥蚓等。1 3 本文的主要工作和结构安排本文着重就基于密度的子空间聚类算法展开研究，从提高算法执行的时间效率、空间效率、聚类结果的质量和可理解性等方面提出解决方案并通过实验验证方法的有效性。针对现有基于密度的子空间聚类算法所存在的问题，提出了两种新的子空间聚类算法：一种是查找无冗余簇的基于密度的子空间聚类算法n r s c ，另一种是基于密度和极大团的子空间聚类改进算法d m a x c 。此外，本文还实现了子空间聚类分析系统原型，系统的设计和实现充分考虑了系统的完整性、协调性和高效性。本文在结构上共分为六章，如图1 3 所示。图1 3 ：论文结构图基于密度的子空间聚类算法研究具体内容为：第一章，介绍数据挖掘的基本概念、一般过程和高维聚类分析的由来及其现实意义，回顾国内外的研究现状，最后给出本文研究的主要内容和结构安排。第二章，概述聚类分析的基本概念，研究目前聚类技术中的主要算法，并对高维数据的聚类分析技术和常用的子空间聚类算法进行介绍。第三章，分析传统方法在寻找簇类时的缺点，提出一种查找无冗余簇的基于密度的子空间聚类算法n r s c ，对相关概念和算法流程进行描述，与传统子空间聚类算法进行比较分析。第四章，针对现有基于密度的子空间聚类算法所存在的问题，提出一种基于密度和极大团的子空间聚类改进算法d m a x c ，通过实验验证算法的执行效果。第五章，简要介绍子空间聚类分析系统的设计与实现，对系统设计架构和功能实现进行描述。第六章，对本文的研究工作进行总结，并展望后续的研究工作。第二章聚类分析方法2 1 聚类分析概述第二章聚类分析方法聚类分析又称为点群分析、群分析、簇分析等，是按研究对象在性质上的亲疏关系进行分类的一种多元统计方法，能够反映样本间的内在组合关系。聚类分析直接比较各事物之间的性质，主要用于辨认具有相似性的事物，并根据彼此不同的特性加以“聚类”，使同一类的事物具有高度的相同性。简单说来，就是把事物按其相似程度进行分类，并寻找不同类别事物特征的分析工具。2 1 1 聚类的定义一个能产生高质量聚类的算法必须满足下面两个条件：类内( i n t r a - c l a s s )数据或对象的相似性最强，以紧致度描述；类间( i n t e r - c l a s s ) 数据或对象的相似性最弱，以分离度描述。聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法和实现方式，同时也取决于该算法能否发现部分或全部隐藏的模式。下面给出聚类问题的形式化定义【3 2 】：定义2 1 ：给定一个数据集合x ( 而，而，吒) ，其中薯= ( t 1 ，而2 ，妇)( i = l ，2 ，1 ) 为数据点。根据数据点间的相似程度将数据集分成k 个分割g( f = 1 ，2 ，k ) 和噪声砌，且x = c iuc 2u u qu 乞栅，cr 、c ，= 囝的过程称为聚类。其中g ( 净1 , 2 ，助称为簇。2 1 2 聚类分析中的数据表示对于聚类分析中的数据表示，通常采用都以下两种数据结构【2 】：( 1 ) 数据矩阵( d a t am a t r i x ) ，用p 个变量( 也称为度量或属性) 来表示刀个对象，这种数据结构是关系表的形式，或者看成 xp 的矩阵。基于密度的子空间聚类算法研究x l l：x 够：x 时( 2 1 )( 2 ) 相异度矩阵( d i s s i m i l a r i t ym a t r i x ) ，存储1 1 个对象两两之间的近似性，表现形式是一个力以维的矩阵。0d ( 2 ，1 ) 0d ( 3 ，1 ) d ( 3 ，2 ) 0；d ( n ，1 ) d ( n ，2 ) 0( 2 2 )其中项f ，力是对象f 和对象之间相异性的量化表示，通常它是一个非负的数值，当对象f 和对象，越相似或“接近”，其值越接近o ；两个对象越不同，其值越大。同时，显然有政f ，力= d o ，力，吠f ，d = 0 。数据矩阵经常被称为二模矩阵，而相异度矩阵被称为单模矩阵。这是因为前者的行和列代表不同的实体，而后者的行和列代表相同的实体。许多聚类算法以相异度矩阵为基础。如果数据是用数据矩阵的形式表现的，在使用该类算法之前要将其转化为相异度矩阵。2 1 3 相似度的度量关于聚类定义的核心概念是数据点之间的相似性，即数据点之间在形态上的亲疏远近关系，它是数据聚类的根本依据。为了使聚类过程在定量的范畴上得以实现，必须恰当地对样本之间的相似性加以定义。设两个p 一维向量薯= ( 五。，薯：，嘞) r 和= ( 乃。，x j ：，) 7 分别表示两个对象，采用距离和相似系数来度量它们的相似度h 6 1 。1 距离距离是描述数据对象间差异性的测度，因此，数据对象之间距离的定义是有效地组织数据并加以聚类分析的前提条件。数据对象之间的距离建立后，两，pp砩；lll而；确；矗第二章聚类分析方法者之间的距离越小，其相似性越大，否则相似性越小。常见的有关距离的定义有：( 1 ) 明考斯基( m i n k o w s k i ) 距离：吃瓴，x j ) = | l x , 一一l l = ( 圭k = l f 垓一尸 i( 2 3 )吃瓴，一一l l = i f 垓一尸l ( 2 3 )其中g 1 ，o o ) 。明考斯基距离是无限个距离度量的概化，当q = l 时为曼哈坦距离，当q = 2 时为欧几里得距离，当口叶时为切比雪夫距离。( 2 ) 曼哈坦( m a n h a t t a n ) 距离：嘎( 薯，x j ) - = i l 而一_ f i _ 圭f 磁一瓠l( 3 ) 欧几里得( e u c l i d ) 距离：( 2 4 )吃瓴，x j ) = 1 1 x , - x ji k = ( 兰k = l i 一1 2 ) i( 2 5 )吃瓴，i k = l i 一1 2j ( 2 5 )( 4 ) 切比雪夫( c h e b y s h e v ) 距离：丸( 薯，_ ) 爿i 薯一x ji l - 州m a x ，内l 一i( 2 6 )一般地，距离函数应满足如下条件：( 1 ) 非负性：x j 一一i i 0 ，i 司b 寸l lx , - x ji i = 0 ，当且仅当x i = x j ；( 2 ) 对称性：i i x , 一x ji 1 = 1 1 x j 一i i ( 3 ) 三角不等式：i i x , 一_ | | 纠l t - x , i i + l l x , 一一l i 。前面定义的距离适用于一般的欧几里得空间，还有很多形式的距离度量定义。例如，马哈拉诺比斯( m a h a l a n o b i s ) 距离：a o ( x , ，_ ) = ( 墨一) r 么( 而一一)( 2 7 )其中a 为正定矩阵。这种形式的距离度量适用于对力维特征空间中的凸形区域建模。还可以根据每个变量的重要性为其赋一个权值，如加权的欧几里得距离形基于密度的子空间聚类算法研究式为：也( 薯，_ ) = l lx , - x j1 1 2 = ( 童k = l 雌i 一1 2 ) j( 2 8 )加权也可用于其他形式的距离。在聚类分析中需要根据数据类型、应用目标等因素来选择合适的距离函数。2 相似系数和相关系数相似系数是描述数据对象之间相似性的测度，两个样本点之间越相似，则它们之间的相似系数越接近1 ；否则，两个样本点越不相似，它们之间的相似系数越接近0 。常见的相似系数包括数据点间的夹角余弦和相关系数：( 1 ) 夹角余弦：劬= c o s ( e , j ) =，vr r厶一“i k “j kk = l( 2 9 )夹角余弦函数忽略两数据点( 向量) 间的绝对长度而考虑它们在方向上的相互关系。两数据点间的相似性反映了它们在状态空间方向上的一致性，当它们在方向上一致时，夹角余弦为1 ；而在它们之间毫无可比性( 正交) 时，夹角余弦为0 。( 2 ) 相关系数：2丢pc 磁一吉喜，c 一刍喜，( 2 1 0 )相关系数是关于向量标准差的夹角余弦，它表示两个向量线性相关的程度。2 1 4 对聚类分析的典型要求聚类分析是一个富有挑战的研究领域，每一个应用都有其特定的要求。现在通用的聚类标准都是从几个方面来衡量的，而没有完全使用量化的客观要求第二章聚类分析方法和标准。下面就是数据挖掘中对聚类分析的一些典型要求：( 1 ) 可扩展性许多聚类算法在小数据集上可以工作得很好，但一个大数据集可能会包含数以百万计的对象。利用采样的方法进行聚类分析很可能会得到一个有偏差的结果，这时就需要可扩展的聚类分析算法。( 2 ) 处理不同类型属性的能力许多算法是针对数值属性设计的。但是有些应用需要对其他类型数据，如二值类型( b i n a r y ) 、类属类型( c a t e g o r i c a l ) 、序数类型( o r d i n a l ) ，或者这些数据类型的组合进行处理。( 3 ) 发现任意形状的簇类许多聚类算法是基于欧几里得距离和曼哈坦距离来进行聚类的。基于这些距离的聚类方法一般只能发现具有类似大小和密度的圆形或球状簇类。然而，在实际应用中的数据集可能具有不同粒度和密度的簇，这些簇也可能是任意形状的，因此，识别数据集中任意形状的簇也是衡量聚类算法的一个重要标准。( 4 ) 预设定参数较少许多聚类算法需要用户输入聚类分析中所需要的一些参数，聚类结果通常都与输入参数密切相关，而这些参数常常也很难决定，要求用户输入参数不仅增加了用户的负担，也使得聚类质量难以控制，特别对于高维对象的数据集更是如此。( 5 ) 处理噪声数据的能力大多数现实世界的数据集均包含异常数据、不明数据、丢失数据和噪声数据，有些聚类算法对这样的数据非常敏感并会导致获得质量较差的簇类。( 6 ) 对输入记录顺序不敏感一些聚类算法对数据输入的顺序敏感，也就是不同的输入顺序会导致获得完全不同的结果。因此设计对输入数据顺序不敏感的聚类算法也是非常重要的。1 二i 基于密度的子空间聚类算法研究( 7 ) 高维眭许多聚类算法在处理低维数据时表现很好，然而设计对高维空间中的数据对象，特别是对高维空间稀疏和怪异分布的数据对象，能较好的进行聚类分析的算法已成为聚类研究中的一项挑战。( 8 ) 基于约束的聚类现实中的应用可能需要在各种约束之下进行聚类分析。假设需要在一个城市中确定一些新加油站的位置，就需要考虑诸如城市中的河流、高速公路，以及每个区域的客户需求等约束情况下居民住地的聚类分析。设计能够发现满足特定约束条件且具有较好聚类质量的聚类算法也是聚类研究的一个重要任务。( 9 ) 可解释性和可用性用户往往希望聚类结果是可解释的、可理解的以及可用的。这就需要聚类分析要与特定的解释和应用联系在一起。2 2 主要聚类方法迄今为此，研究者已经提出了大量的聚类分析方法，算法的选择取决于数据的类型、聚类的目的和应用。大体上，主要的聚类分析方法可以分为【2 1 【2 5 1 ：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法。除上述五大类以外，还存在大量的聚类方法，如处理高维数据的聚类方法，处理动态数据的聚类方法，以及将基本聚类方法与各种新技术相结合的聚类方法等。( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d )划分方法是在数据挖掘出现以前就很流行的聚类算法。其基本思想是：给定一个包含n 个办维点的数据点集d ，以及要生成的簇数目k ，首先构建数据点集的k 个初始划分，每个划分表示一个簇类，然后采用一种迭代的重定位技术，通过对象在划分区间的移动来改进划分，通常会采用一个划分准则，称为相似度函数( s i m i l a r i t yf u n c t i o n ) ，来评价划分的质量。即一个划分算法将 个对1 4 第二章聚类分析方法象划分成k 个簇，使得每个对象离它的簇中心的距离达到最小。而每个簇由其质心来代表( k - m e a n s 算法) ，或者由该簇中最靠近中心的一个对象来代表( 肛m e d o i d s 算法) 。划分聚类算法收敛速度快，对少量的数据样本并且是球状簇很有用，但对大量数据以及处理复杂形状的簇需要进一步扩充，同时它要求类别数目k 必须合理地估计，并且初始中心的选择和噪声对会对聚类结果产生很大影响。主要的划分聚类算法有k - m e a n s 、k - m e d o i d s 、c l a r a 5 1 和c l a r a n s 3 3 】等。( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d )一个层次的聚类方法将数据对象组成一棵聚类树，这棵树迭代地将数据库d 划分为一些小的数据集，直到每个子集中仅包含一个对象，在这样的层次结构中，每一层表示d 的一个聚类结果。根据层次分解是自底向上还是自顶向下形成，层次的聚类方法可以进一步分为凝聚的( a g g l o m e r a t i v e ) 和分裂的( d i v i s i v e ) 层次聚类，如图2 1 所示。凝聚的垄!垄!当!当!垄!，万1 f 3 2 了1 五0 - 分裂的步4步步步步万裂网图2 1 在数据对象集合 口，b ，c ，磊p ) 上的凝聚和分裂层次聚类凝聚的层次聚类是一种自底向上的策略，首先将每个对象作为一个簇，然基于密度的子空问聚类算法研究后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类方法属于这一类，他们只是在簇间相似度的定义有所不同。与凝聚的层次聚类相反，分裂的层次聚类是一种自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件，例如达到了某个希望的簇数目，或者两个最近的簇之间的距离超过了某个阈值。层次聚类方法简单，但经常会遇到合并或分裂点选择的困难，一旦一个合并或分裂被执行，已做的操作就不可撤消，同时聚类之间也不能交换对象。最近的研究集中于凝聚层次聚类和迭代重定位方法的集成。主要的层次聚类算法有a g n e s t 5 1 、d i a n a 5 1 、b i r c h l 3 6 1 、c u r e d 7 1 、r o c k d 8 1 和c h a m e l e o n 3 9 1 等。( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d )很多算法都是用距离来描述数据之间的相似性，但是，对于非凸数据集，只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于密度的聚类算法。基于密度的聚类方法主要思想是：只要临近区域的密度( 对象或数据点的数目) 超过某个阈值，就继续聚类，也就是说，对给定簇中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这类方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。d b s c a n 1 7 】【1 9 】就是一种经典的基于密度的聚类算法。它采用参数m i n p t s来比较簇间的相似度，认为两个簇能够合并的前提是它们之间的对象联系密切，且连接的对象的数量大于阈值。因此，算法所设定的参数较少，完全基于数据集的自然状态。o p t i c s 1 8 】是d b s c a n 的扩展，算法生成了数据集的序列来表示数据的基于密度的聚类结构，这一序列包含了数据集每一阶段的聚类信息。o p t i c s 的局限在于，它只适用于数值型数据，而且用户仍旧需要设定m i n p t s 。基于密度的聚类方法主要有d b s c a n 、o p t i c s 和d e n c l u e 7 1 1 等。( 4 ) 基于网格的方法( g r i d b a s e dm e t h o d )1 6 第二章聚类分析方法基于网格的方法采用一个多分辨率的网格数据结构。这类算法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关；缺点是只能发现边界是水平或垂直的簇，而不能检测到斜边界。所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和数目，单元数目太少时精度就会很低，而单元数目太多时算法的复杂度就会变大；二是怎样对每个单元中对象的信息进行汇总。在s t i n g 3 4 1 算法中，每个单元都保存一系列统计信息，包括均值、方差、最大值、最小值、分布类型等，而c l i q u e 8 1 1 9 1 算法中，仅记录每个单元中的对象数目。基于网格的聚类方法主要有s t i n g 、w a v e c l u s t e r l 3 5 】和c l i q u e 等。( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d )基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。这样的方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要有两类：统计学方法和神经网络方法。统计学方法的典型应用是c o b w e b 4 0 1 ，它是一种流行的简单增量概念聚类算法。它的输入对象用分类属性值对来描述，以一个分类树的形式创建层次聚类。神经网络方法【4 1 】比较著名的有：竞争学习( c o m p e t i t i v el e a r n i n g ) 【4 2 l 和自组织特征映射( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) 4 3 1 1 4 4 。神经网络方法将每个簇描述为一个样本，样本作为簇类的原型，不一定对应一个特定的数据实例或对象。根据某些距离度量，新的对象可以被分配给样本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的样本的属性来预测。2 3 高维数据的聚类分析技术高维数据的聚类分析方法是近年来聚类分析技术的一个较为活跃的研究领域。各种类型的交易数据、文档数据、基因表达数据、网络通信数据等数据的基于密度的子空间聚类算法研究维度( 属性) 可以达到几十、几百或成千上万维，若将这些对象表示成高维属性空间的点，这样客观世界中的对象就可以用高维数据的集合来表示，对这种数据进行挖掘就是高维数据挖掘问题。研究表明【4 7 1 ，在数据维度高于2 0 时，传统聚类分析方法和索引方法的性能急骤下降，甚至无法完成聚类任务。例如，许多空间聚类算法会依赖于空间数据库的索引，以便快速搜索最近邻。索引的性能优劣直接受到“维度效应”的影响。在维度d 1 6 时，它们的性能会降低到顺序搜索的水平。面对大规模高维度的数据，多数传统聚类方法无法获得好的聚类效果，其原因归结起来有以下几个方面【2 2 】：( 1 ) 距离函数难以定义：聚类操作的基础是数据对象之间相似性的度量，将相似度高的对象归为一类。低维空间中通常使用厶距离来度量相似性，但在高维情况下由于相似性没有传递性，这样的距离函数失效。( 2 ) 近邻点查询问题：基于距离的聚类方法通常需要计算近邻点，但在高维情况下，大多数数据点之前的差异近似于相等，使得按距离计算的近邻点变得不稳定。( 3 ) 子空间聚类分析：在高维空间中，簇往往只存在于由少数特征组成的子空间中，聚类算法不仅需要对数据集进行划分，还要给出每个簇所处的子空间，而不同的簇其子空间可能是不同的，传统聚类方法没有考虑子空间聚类的情况。( 4 ) 算法复杂度：由于高维度和大数据量，许多传统聚类方法因过高的计算复杂度其应用领域受到限制。对于高维数据的聚类问题，目前主要有以下两种解决方法1 7 1 ：( 1 ) 特征提取特征提取就是用映射( 或称变换) 的方法把原始特征空间变换到低维空间来表示样本【州。映射后的特征n t t - 次特征，它们是原始特征的某种组合( 通常1 窖第二章聚类分析方法是线性组合) 。所谓特征提取在广义上就是指一种变换，包括主成分分析( p r i n c i p l ec o m p o n e n ta n a l y s i s ) 和奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n )等策略。该方法通常是预处理步骤，将原数据空间映射