软件工程硕士论文-K-means聚类算法的研究.pdf

大连理工大学 硕士学位论文 k-means聚类算法的研究 姓名：冯超 申请学位级别：硕士 专业：软件工程 指导教师：吴国伟 20071215 大连理工大学硕士学位论文 摘要 聚类是数据挖掘领域中重要的技术之一，用于发现数据中未知的分类。聚类分析已 经有了很长的研究历史，其重要性已经越来越受到人们的肯定。聚类算法是机器学习、 数据挖掘和模式识别等研究方向的重要研究内容之一，在识别数据对象的内在关系方 面，具有极其重要的作用。聚类主要应用于模式识别中的语音识别、字符识别等，机器 学习中的聚类算法应用于图像分割，图像处理中，主要用于数据压缩、信息检索。聚类 的另一个主要应用是数据挖掘、时空数据库应用、序列和异常数据分析等。此外，聚类 还应用于统计科学，同时，在生物学、地质学、地理学以及市场营销等方面也有着重要 的作用。 本文是对聚类算法k - m e a n s 的研究。首先介绍了聚类技术的相关概念。其次重点对 k - m e a n s 算法进行了分析研究，k - m e a n s 算法是一种基于划分的方法，该算法的优点是 简单易行，时间复杂度为0 0 ) ，并且适用予处理大规模数据。但是该算法存在以下缺点： 需要给定初始的聚类个数k 以及k 个聚类中心，算法对初始聚类中心点的选择很敏感， 容易陷入局部最优，并且一般只能发现球状簇。本文针对聚类个数足的确定、初始k 个聚类中心的选定作了改进，给出了改进的算法m m d b k ( m a x m i na n dd a v i e s b o u l d i n i n d e xb a s e dk - m e a n s ，简称m m d b k ) 。算法的出发点是确保发现聚类中心的同时使同一 类内的相似度大，而不同类之间的相似度小。算法采用d a v i e s b o u l d i ni n d e x 聚类指标 确定最佳聚类个数，改进的最大最小距离法选取新的聚类中心，以及聚类中心的近邻查 找法来保证各个类之间的较小的相似度。文中最后使用k d d 9 9 数据集作为实验数据， 对k - m e a n s 算法以及m m d b k 算法进行了仿真实验。结果显示改进后的m m d b k 算法 在入侵检测中是有效的。 关键词：数据挖掘；聚类分析；k - m e a n s ；入侵检测 r e s e a r c ho f k - m e a n sc l u s t e d n g a l g o r i t h m a b s tr a c t c l l l s b e r i n gi so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e so fd a t am i n i n g ，w h i c hi su s e dt o d i s c o v e ru n k n o w nc l a s s i f i c a t i o ni nd a t as e t a si th a sa1 0 n gh i s t o r yo fr e s e a r c h ，t h e i m p o r t a n c eo fc l u s m i n gi sa f f m n e db yp e o p l e c l u s t e r i n ga l g o r i t h m si so n eo ft h em o s t i m p o r t a n ta l g o r i t h m sw h i c hi sr e s e a r c h e de x t e n s i v e l yi nm a c h i n el e a r n i n g ，d a t am i n i n ga n d p a t t e r nr e c o g n i t i o n i th a si m p o r t a n te f f e c to ni d e n t i f yi n t r a - c o n n e c t i o nb e 魄e e no b j e c t s c l u s t e r i n gi sa p p l i e di ns o u n dr e c o g n i t i o n , c h & r a c t 盯r e c o g n i t i o no f p a t t e r nr e c o g n i t i o na n ds o o n c l u s t e r i n ga l g o r i t h m si nm a c h i n el e a r n i n ga r ea p p l i e di ni m a g es e g m e n t a t i o na n di 1 1 a a g e p r o c e s s i n gw h i c hc a l lb eu s e dt od e a lw i t hd a t ac o m p r e s s i o na n di n f o r m a t i o ns e a r c h a n o t h e r i m p o r t a n ta p p l i c a t i o ni sa p p l i e di nd a t am i n i 丑g ，s p a c ed a t a b a s e ，s e q u e n c ea n da n o m a l yd a t a a n a l y s i sa n do t h e rf i e l d ss u c ha ss t a t i s t i c ，b i o l o g y ，g e o g n o s y ，g e o g r a p h ya n dm a r k e t t h i sp a p e ri sa b o u tt h er e s e a r c ho f k - m e a n s a tf i r s t , s o m er e l a t e dc o n c e p t so f c l u s t e r i n g a r eg i v e n 髓ec h i e fp o i n to ft h ep a p e ri st h er e s e a r c ho i lk - m e a n s k - m e a n s ，) t i m e c o m p l e x i t y i sap a r t i t i o nm e t h o dt h a ti ti se a s yt ou s ea n dc a l lw o r kw e l lw i t hl a r g ed a t as e t b t l tt h e r ea r es o m ed r a w b a c k sa sf o l l o w s ：d e f m e sc l u s t e r i n gn u m b e r ska n di n i t i a lc e n t r o i d s i nm v 锄c e ；s e n s i t i v et ot h es e l e c t e di n i t i a lc e n t r o i d s ；e a s i e rt og e ti n t ol o c a lo p t i m i z a t i o na n d c o m ei n t ob e i n gr o a n d s h a p ec l u s t e r s 1 1 1 i sp a p e rw o r k so nh o wt os o l v et h e s ep r o b l e m s i t p r o p o s e s a l li m p r o v e da l g o r i t h mm 玉d b k ( m a x - m i na n dd a v i e s b o u l d i ni n d e xb a s e d k m e a n s 卟d b kf o rs h o r t ) b a s e do nl i t t l ec o m p a r a b i l i t yb e l 3 v e e l ld i f f e r e n tc l u s t e r sa n d l a r g ec o m p a r a b i l i t yi nt h es 锄ec l u s t e r , t 0 s e tn u m b e rka n dt h ei n i t i a le e n t r o i d s d a v i e s - b o u l d i ni n d e xi su s e dt og e tt h em o s ts u i t a b l ec l u s t e rn u m b e rka n di m p r o v e d m a x - m i nd i s t a n c ei su s e dt oa s s u r el i t t l ec o m p a r a b i l i t yb 咖nd i f f e r e n tc l u s t e r s a tl a s t , k d d 9 9d a t as e ti su s e di nt h ee x p e r i m e n tt ot e s tt h ee m c i e n c yo f m d b k n 圮r e s u l ts h o w s t h a th n b ki se f f e c t i v ei ni n t r u s i o nd e t e c t i o n k e yw o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；k - m e a n s ：i n t r u s i o nd e t e c t i o n 一一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特剐加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：邋 导师毖鍪亟生 丝组年上l 月盟日 大连理工大学硕士学位论文 1绪论 1 1 研究背景和意义 面对信息技术的日新月异，人们利用信息技术生产和搜集数据的能力大幅度提高， 大量的数据库被用于商业管理、政府办公、科学研究和工程开发等等，要想使数据真正 成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否 则大量的数据可能成为包袱，数据挖掘和知识发现技术应运丽生，并得以蓬勃发展，越来 越显示出其强大的生命力。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含 在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。人们把原始数据 看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数 据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上 的异构型数据。发现知识的方法可以是数学的，也可以是非数学的可以是演绎的，也可 以是归纳的。挖掘出的知识可以被用于信息管理。查询优化、决策支持、过程控制等， 还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，涉及人工智能技术、统 计技术与数据库技术等多种技术。它汇聚了不同领域的研究者，尤其是数据库、人工智 能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 聚类是数据挖掘技术研究中的重要技术的一种，能有效的通过分析数据并从中发现 有用的信息。聚类将数据对象分组成为若干个类或簇，使得在同一个簇中的对象之间具 有较高的相似度，而不同簇中的对象差别很大，通过聚类，人们能够识别密集和稀疏的 区域，发现全局的分布模式以及数据属性之间有趣的相互关系。聚类分析在客户分类、 基因识别、文本分类、空间数据处理、卫星照片分析、医疗图像自动检测等领域有着广 泛的应用，而其本身的研究也是一个蓬勃发展的领域，数据挖掘、统计学、机器学习、 空间数据库技术、生物学和市场学的发展推动着聚类分析研究的进展，使它已成为数据 挖掘研究中的一个热点，在市场分析中，通过聚类分析能帮助决策者识别不同特征的客 户群以及各客户群的行为特征在生物工程研究中，聚类分析能够用于推导动植物的分 类，按照功能对基因进行划分并获取种群中的固有结构特征在非关系数据库领域如空间 数据库领域，聚类分析能够识别具有相同地理特征的区域以及该区域的环境和人的特征 在信息检索领域，聚类分析能够对文档进行分类，提高检索效率。聚类分析将大量数据 划分为性质相同的子类，便于了解数据的分布情况。与其他数据挖掘方法不同，在进行 k - m e s 聚类算法的研究 聚类分析前用户一般并不知道数据集的特征。因此，从某种角度看，聚类分析是一种无 监督的学习过程，是基于观察的学习而不是基于实例的学习。 1 2 国内外研究现状 聚类分析作为统计学的一个分支，已被广泛地研究了多年，主要集中在基于距离的 聚类分析。k - m e a n s 算法、k - m e d o i d s 算法和其他一些方法的聚类分析工具已经被加入 到许多统计分析软件包或系统中。 在机器学习领域，聚类是无指导学习的一个例子。与分类不同，聚类和无指导学习 不依赖预先定义的类和带类标号的训练实例，由于这个原因，聚类是观察式学习，而不 是示例式学习。在概念聚类中，一组对象只有当它们可以被一个概念描述时才形成一个 簇，这不同于基于几何距离度量相似度的传统聚类。 为了使聚类方法的性能得到更大地提高，将其他领域的方法与聚类方法相结合，弥 补了数据挖掘领域中聚类方法的某些缺陷，将聚类方法的最优性能发挥得更加充分。常 采用的著名方法有：遗传算法、免疫算法、蚂蚁算法等。近年来的人工免疫系统的研究 是一个崭新的应用领域，随着免疫计算的发展，给聚类分析领域带来新的活力。免疫算 法( i m m u n ea l g o r i t h m ) 来自模拟人体的免疫系统，并从体细胞理论和网络理论中得到启 发，实现了类似于免疫系统的自我调节功能和生成不同抗体的功能。 目前聚类算法的研究方向主要由以下几个方向： ( 1 ) 初始值的选择以及输入顺序对聚类结果影响 在数据挖掘领域中可采取的措施可以用多组不同的初始值并进行多次迭代，最终选 取其中最佳者作为计算结果，但是不能保证一定达到全局最优解。最优解聚类过程的本 质是一个优化的过程，通过一种迭代运算使得系统的目标函数达到一个最优解。然而这 个目标函数在状态空间中是一个非凸函数，它有许多极小值，而其中只有一个是全局最 小值，其它都是局部最小值。优化的目标就是达到全局最优，因此一个非凸函数的优化 问题是待解决的研究课题。 ( 2 ) 算法的效率问题 提高算法的效率问题是当前聚类领域中研究的又一个重要问题。通过改进现有的聚 类算法，使之具有增量聚类的能力，并具有较好的伸缩性，在处理大数据库时，对数据 库仅扫描一次，以提高算法的效率。 ( 3 ) 小波变换聚类算法的研究 目前有关聚类的研究成果大都是对均值算法、模糊均值算法的推广和改进，这些研 究成果对聚类的性能都有不同程度的提高。然而对小波聚类算法及其改进方法的研究文 一2 一 大连理工大学硕士学位论文 献极少。由于它符合一个好的聚类算法的许多要求，因此对小波聚类算法的进一步研究 与开发将会取得意想不到的成果。 基于不同媒体的挖掘目前大多数聚类挖掘算法都是基于关系数据库或事务数据库 的算法，设计应用于其它类型数据库如面向对象数据库、面向属性的数据库、时态数据 库、文本数据库、异质数据库、多维数据库、地理数据库、数据仓库等的聚类挖掘算法 也将是十分有意义的工作。 k - m e a m 算法是聚类分析中一种被广泛应用的启发式划分方法，具有简单、快速的 优点。但是k - m e a n s 算法对初值敏感，不同的初值常导致不同的聚类结果，没有良好的 稳定性，且容易陷入局部最优而非全局最优的不良结果。本文针对k - m e a n s 算法的缺陷， 给出了一种改进的聚类算法。 1 3 论文组织结构 本文针对k - m e a n s 聚类算法存在的缺陷，给出了一种改进的聚类算法，并通过仿真 实验证明其有效性，各章安排如下： 第一章为绪论，介绍了聚类算法的背景、国内外的研究现状以及本文的工作内容。 第二章介绍聚类算法技术的相关概念。 第三章介绍了k = m e a n s 聚类算法，对其进行了详细的分析，并给出了k m e a n s 存在 的缺陷以及现有的改进算法。 第四章介绍改进的算法m m d b k ，通过d a v i e s b o u l d i ni i l d e x 聚类指标和最大最小 距离法来确定聚类个数及聚类中心，详细介绍了算法改进的基本思想和算法的流程。 第五章介绍了聚类算法入侵检测中的应用，采用k d d 9 9 数据集对k - m e a n s 和 m m d b k 算法进行仿真实验，通过实验对比证明改进算法在入侵检测中的有效性。 2 聚类技术 2 1 聚类的定义 聚类是一个将数据集划分为着干个子集的过程，并使得同一集合内的数据对象具有 较高的相似度，而不同集合中的数据对象则是不相似的，相似或不相似的度量是基于数 据对象描述属性的取值来确定的，通常就是利用各个聚类间的距离来进行描述的。聚类 分析的基本指导思想是最大程度地实现类中对象相似度最大，类间对象相似度最小。 聚类与分类不同，在分类模型中，存在样本数据，这些数据的类标号是已知的，分 类的目的是从训练样本集中提取出分类的规则，用于对其他类标号未知的对象进行类标 识。在聚类中，预先不知道目标数据的有关类的信息，需要以某种度量为标准将所有的 数据对象划分到各个簇中。因此，聚类分析又称为无监督的学习。 聚类算法的目的就是获得能够反映维空间中这些样本点的最本质的“类”的性质。 这一步没有领域专家的参与，它除了集合知识外不考虑任何的领域知识，不考虑特征变 量在其领域中的特定含义，仅仅认为它是特征空间中的一维而己。 聚类主要包括以下几个过程【1 栩： ( 1 ) 数据准备 包括特征标准化和降维。 ( 2 ) 特征选择、提出 从最初的特征中选择最有效的特征，并将其存储于向量中。 ( 3 ) 特征提取 通过对所选择之特征进行转换形成新的突出特征。 ( 4 ) 聚类( 或分组) 首先选择合适特征类型的某种距离函数( 或构造新的距离函数) 进行接近程度的度 量。然后执行聚类或分组。 ( 5 ) 聚类结果评估 指对聚类结果进行评估。评估主要有3 种：外部有效性评估、内部有效性评估和相 关性测试评估。 动态的聚类过程如图2 1 所示。 ( 1 ) 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把 所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处 理法。 一4 一 大连理工大学硕士学位论文 ( 2 ) 选一批代表点后，依次计算其它样本的归类，当计算完第一个样本时，把它归于 最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心 的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处 理法。 ( 3 ) 直接用样本进行初始分类，先规定距离d ，把第一个样品作为第一类的聚类中 心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d ，就把第二个样本归 于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚 类中心距离大于还是小于d ，决定分裂还是合并。 图2 1 动态聚类 f i g 2 1d y n a m i cc l u s t e r i n g 2 2 聚类算法的要求 聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的领域包括：数据挖掘、统 计学、机器学习、空间数据库技术、生物学和市场学等。由于各应用数据库所包含的数 据量越来越大，聚类分析已成为数据挖掘研究中一个非常活跃的研究课题。 作为统计学的一个分支，聚类分析已有多年的研究历史，这些研究主要集中在基于 距离的聚类分析方面。许多统计软件包，诸如：s - p l u s 、s p s s 和s a s ，都包含基于k - m e a n s 、 k - m e d o i d s 等其它许多聚类分析工具。 在机器学习中，聚类分析属于一种无监督的学习方法。与分类学习不同，无监督学 习不依靠事先确定的数据类别，以及标有数据类别的学习训练样本集合。正因为如此， 聚类分析又是一种通过观察学习方法0 e a r n i n gb yo b s e r v a t i o n ) ，而不是示例学- 7 - j ( 1 e a r n i n g b ye x a m p l e ) 。在概念聚类方法中，仅当一组对象可以由一个概念所描述时，这些对象方 才能构成一个类。这与基于几何距离表示相似程度并进行聚类的传统聚类方法有所不 同。概念聚类方法主要包含两部分内容： n ) 发现适当的类。 ( 2 ) 根据每个类形成相应的特征描述，与在分类学习中的方法类似。 无论如何最大程度地实现类中对象相似度最大，类间对象相似度最小是聚类分析的 基本指导思想。 在数据挖掘中，大多数工作都集中在发现能够有效、高效地对大数据库进行聚类分 析的方法上。相关的研究课题包括：聚类方法的可扩展性、复杂形状和复杂数据类型的 聚类分析的有效高效性、高维聚类技术，以及混合数值属性与符号属性数据库中的聚类 分析方法等。 聚类分析是一个富有挑战的研究领域，有关每一个应用都提出了一个自己独特的要 求。以下就是对数据挖掘中的聚类分析的一些典型要求【3 l 。 ( 1 ) 可扩展性。许多聚类算法在小数据集( 少于2 0 0 个数据对象) 时可以工作很好； 但一个大数据库可能会包含数以百万的对象。利用采样方法进行聚类分析可能得到一个 有偏差的结果，这时就需要可扩展的聚类分析算法。 ( 2 ) 处理不同类型属性的能力。许多算法是针对基于区间的数值属性而设计的。但 是有些应用需要对其它类型数据，如：二值类型、符号类型、顺序类型，或这些数据类 型的组合。 ( 3 ) 发现任意形状的聚类。许多聚类算法是根据欧氏距离和m a n h a t t a n 距离来进行 聚类的。基于这类距离的聚类方法一般只能发现具有类似大小和密度的圆形或球状聚 类。而实际上一个聚类是可以具有任意形状的，因此设计出能够发现任意形状类集的聚 类算法是非常重要的。 ( 4 ) 需要( 由用户) 决定的输入参数最少。许多聚类算法需要用户输入聚类分析中 所需要的一些参数( 如；期望所获聚类的个数) 。而聚类结果通常都与输入参数密切相 关；而这些参数常常也很难决定，特别是包含高维对象的数据集。这不仅构成了用户的 负担；也使得聚类质量难以控制。 ( 5 ) 处理噪声数据的能力。大多数现实世界的数据库均包含异常数据、不明数据、 数据丢失和噪声数据，有些聚类算法对这样的数据非常敏感并会导致获得质量较差的数 据。 ( 6 ) 对输入记录顺序不敏感。一些聚类算法对输入数据的顺序敏感，也就是不同的 数据输入顺序会导致获得非常不同的结果。因此设计对输入数据顺序不敏感的聚类算法 也是非常重要的。 ( 7 ) 高维问题。一个数据库或一个数据仓库或许包含若干维或属性。许多聚类算法 在处理低维数据时( 仅包含二到三个维) 时表现很好。人的视觉也可以帮助判断多至三 大连理工大学硕士学位论文 维的数据聚类分析质量。然而设计对高维空间中的数据对象，特别是对高维空间稀疏和 怪异分布的数据对象，能进行较好聚类分析的聚类算法己成为聚类研究中的一项挑战。 ( 8 ) 基于约束的聚类。现实世界中的应用可能需要在各种约束之下进行聚类分析。 假设需要在一个城市中确定一些新加油站的位置，就需要考虑诸如：城市中的河流、高 速路，以及每个区域的客户需求等约束情况下居民住地的聚类分析。设计能够发现满足 特定约束条件且具有较好聚类质量的聚类算法也是一个重要聚类研究任务。 ( 9 ) 可解释性和可用性。用户往往希望聚类结果是可理解的、可解释的，以及可用 的。这就需要聚类分析要与特定的解释和应用联系在一起。因此研究一个应用的目标是 如何影响聚类方法选择也是非常重要的。 2 3 聚类算法分类 聚类算法可以分为划分的方法、层次的方法、基于密度的方法、基于网格的方法和 基于模型的方法。 ( 1 ) 划分的方法 给定行个对象，一个划分方法构建对象的k 个划分，每个划分表示一个聚簇，并且 k 甩。给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一种迭 代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是： 在同一个类中的对象之间有较高的相似性，而不同类中的对象之间的相似性较低。目前 比较流行的是k m c a n s 4 算法，k m c d o i d s 【5 1 算法两种启发式的划分方法。 但) 层次的方法 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解，层次的方法可 以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为 一个单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个，或者 达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一 个簇中，在迭代的每一步中，一个簇分裂为更小的簇，直到最终每个对象在单独的一个 簇中，或者达到一个终止条件。b i r c h 6 1 ，c u r e i n 和c h a m e l e o n t 8 1 等算法是层次聚 类的典型。 层次的方法中通常分为以下几种。 单连接法 单连接法也就是最短距离法。两个类之间的距离用从两个类中抽取的每对样本的最 小距离表示。作为距离度量，一旦最近的两个类的距离超过某个任意给定的阈值，算法 就自动结束。 一7 - k - m t m n s 聚类算法的研究 全连接法 全连接又称为最长距离法。全连接与单连接聚类方式相同，只是类与类之间的距离 定义不是选取最小距离，而是找两类数据对象之间距离最大者。 平均连接法 平均连接法的距离度量既不是选取最长距离，也不是选取最短距离，而是取平均距 离。 层次方法的缺陷就是在进行分解或合并之后，无法回溯。这一特点也是有用的，因 为在进行分解或合并时无须考虑不同选择所造成的组合爆炸问题。但这一特点也使得这 种方法无法纠正自己的错误决策。将循环再定位与层次方法结合起来使用常常是有效 的，即首先通过利用自下而上层次方法；然后再利用循环再定位技术对结果进行调整。 一些具有可扩展性的聚类算法，如：b i r c h 和c u r e ，就是基于这种组合方法设计的。 ( 3 ) 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的簇， 而在发现任意形状的簇时遇到困难，随之提出了基于密度的方法。其主要思想是：只要 临近区域的密度( 对象或者数据点的数目) 超过某个阙值，就继续聚类。d b s c 朋- 、 9 1 ， o p t i c s t l o 】和c l i q u e 1 1 】是其中三种有代表性的方法。 基于密度聚类方法的基本思想如下： 一个给定对象的g 半径内的近邻就称为该对象的s 一近邻； 若一个对象的s 一近邻至少包含一定数目( m i n p t s ) 的对象，该对象就称为核对象； 给定一组对象集d ，若对象p 为另一个对象g 的e 一近邻且g 为核对象，那么就 说p 是从口可以“直接密度可达”； 对于一个占而言，一个对象p 是从对象q 司严密度可达”；一组对象集d 有m i n p t s 个对象；若有一系列对象p l ，p 2 ，p 。，其中p l = 口_ x p 。= p ，从而使得( 对于8 和m i n p t s 来讲) p 是从n 可“直接密度可达”。其中有a d ，l s f n 。 对于s 和m i n p t s 来讲，若存在一个对象o ( o d ) ，使得从0 可“密度可达”对象 p 和对象口，对象p 是“密度连接”对象譬。 密度可达是密度连接的一个传递闭包。这种关系是非对称的。仅有核对象是相互“密 度可达”。而密度连接是对称的。 基于密度聚类就是一组“密度连接”的对象，以实现最大化的“密度可达”。不包 含在任何聚类中的对象就为噪声数据。 ( 4 ) 基于网格的方法 一8 一 大连理工大学硕士学位论文 基于网格的方法是把对象空间量化为有限数日的单元，形成了一个网格结构。所有 的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点是它的处 理速度很快，其处理时间独立于数据对象的数目，只与量化空间的每一维的单元数目有 关。s t i n t ；1 2 】是基于网格方法的一个典型算法。 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 是一种基于网格的多分辨率聚类技术，它将空间 区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单 元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单 元属性的统计信息( 用于回答查询) 被预先计算和存储。 s 1 r i n g 算法步骤如下： 在层次结构中选定一层作为查询处理的开始点。 对前层次的每个网格单元，计算出反映该单元与给定查询的关联程度的置信度 区间。 从上面计算的置信度区间中标识每个网格单元是否与给定查询相关。 如果当前层是底层，则执行，否则执行。 处理层次结构中的下一层，对于形成高层的相关网格单元执行。 如果查询要求被满足，则执行；否则，执行。 检索和进一步的处理落在相关单元中的数据，返回满足查询要求的结果。执行 第9 步。 寻找相关网格的区域，返回满足查询要求的相关单元的区域。执行。 算法结束。 w a v e c l u s t e r 方法的主要思想是把多维数据看作一个多维信号来处理。它首先将数 据空间划分成网格结构，然后通过小波变换将数据空间变换成频域空间，在频域空间通 过与一个核函数作卷积后，数据的自然聚类属性就显现出来。w a v e c i u s t e r 方法是一个 多分辨率的算法，高分辨率可以获得细节的信息，低分辨率可以获得轮廓信息。方法的 时间复杂度是d ( 疗) ，其中疗是数据库中对象的个数。 c l i q u e 方法是种密度与网格相结合的算法，它可以发现高维数据空间中的聚类 簇。c l i q u e 方法采用了先验方法在一个维空间中，如果一个区域是密集的，那么在一 维子空间它也是密集的。若是反过来思考一维空间的密集区域一定包含在维空间的密集 区域的候选区。c l i q u e 方法的工作过程是第一步将数据空间化成许多互不相交的网格， 第二步根据空间的每维度判定网格是否是密集的，第三步将所有密集的网格求交集， 检查交集的连通性，生成簇的最小覆盖。方法的复杂度是0 ( 丹) ，以是数据库中对象的个 数。 k - m e a n s 聚类算法的研究 ( 5 ) 基于模型的方法 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个 基于模型的算法可能通过构建反映数据点空间分布的密度的来定位聚类，也可能基于标 准的统计数字自动决定聚类的数目，考虑“噪声”数据或者孤立点从而产生健壮地聚类 方法。 、 s o m s ( s e l fo i 羽n i z i n gm a p ) “3 】是芬兰赫尔辛基大学神经网络专家k o h o n c n 教授在 1 9 8 1 年提出的一种基于神经网络模型的聚类方法，它模拟大脑神经系统自组织特征映射 的功能，在训练中能无监督地进行自组织学习。生物神经系统进化的过程是空间上相邻 的神经元功能慢慢演慢慢相近的过程，相应的，s o m 的训练过程，即将领域上相邻但 在行维欧氏空间并不相邻的权值向量w ，调整到在欧氏空间也相邻。神经元之间的距离 可以用欧几里德距离、位置向量之间距离、m a n h a t t a n 距离等来表示。s o m s 的优点为： 可以实时学习，具有稳定性，无须外界给出评价函数，能够识别向量空间中最有意义的 特征，抗噪音能力强。不足之出为：当网络的连接过多，节点数目庞大时，其计算量大； 需要较长的学习时间；网络连接权向量初值的选取对网络收敛性影响很大。 2 4 聚类分析中的数据结构 聚类算法通常都会用到以下两种数据结构： ( 1 ) 数据矩阵 数据矩阵是一个对象- 属性结构。现在假设有疗个对象，p 个属性，数据矩阵采用关 系表形式或刀p 矩阵来表示，如公式2 1 所示。 而， h ( 2 1 ) ( 2 ) 差异矩阵 差异矩阵是一个对象。对象结构。它存放所有打个对象彼此之间所形成的差异。它 一般采用n x 万矩阵来表示，如公式2 2 所示。 坼 大连理工大学硕士学位论文 ( 2 2 ) 其中d ( f ，) 表示对象i 和对象，之间的差异( 或不相似程度) 。通常娟，力为一个非负 数；当对象i 和对象，非常相似或彼此“接近”时，该数值接近0 ；该数值越大，就表 示对象i 和对象，越不相似。由于有娟，) = 砜_ ，f ) 且础，力= 0 ，因此就有公式2 2 所示 矩阵。 数据矩阵通常又称为双模式矩阵，而差异矩阵则称为单模式矩阵。因为前者行和列 分别表示不同的实体；而后者行和列则表示的是同一实体。许多聚类算法都是基于差异 矩阵进行聚类分析的。如果数据是以数据矩阵形式给出的，那么就首先需要转换为差异 矩阵，方可利用聚类算法进行处理。 2 5 聚类分析中的相似性度量 对象之间的差异( 或相似) 程度可以通过计算相应两个对象之间距离来确定。最常 用的距离计算公式就是欧氏距离( e u c l i d e a nd i s t a n c e ) ，具体公式内容如下： 砘，) = 忙r 1 2 + k _ ：1 2 + + k b 1 2 ) ( 2 3 ) 其中f = b 。，x 。，) ；，= b x 弘，) ；它们分别表示一个p 一维数据对象a m 加h a t a n 距离是另外一个常用的距离计算方法，它的具体计算公式定义如下： d o ，力= l 而。一工一i + l x ，：一_ ：i + + i 一b i ( 2 4 ) 欧氏距离和m a n h a t t a n 距离均满足距离函数的有关数学性质( 要求) ： d ( f ，j ) z 0 ，这表示对象之间距离为非负数的一个数值； d o ，) = 0 ，这表示对象自身之间距离为零； d o ，) = a ( j ，f ) 这表示对象之间距离是对称函数； d o ，力d ( f ， ) + a ( h ，j ) ，这表示对象自身之间距离满足“两边之和不小于第三边” 的性质，若将两个对象之间距离用一条边来表示的话，其中h 为第三个对象。 m i n k o w s k j 距离是欧式距离和m a n h a t t a n 距离的一个推广，它的计算公式定义如下： o 力 力o o屯。m 、，、j、，o：童：；似 d j d k - m e 锄s 聚类算法的研究 d ( f ，力：h 一砀1 9 + k 一_ ：1 9 + k 一1 4 严 ( 2 5 ) 其中4 为一个正整数；当q = 1 时，它代表m a n h a t t a n 距离计算公式；而当q = 2 时， 它代表欧式计算公式。 若每个变量均可被赋予一个权值，以表示其所代表属性的重要性。那么带权的欧氏 距离计算公式就是： d g - ，) = 、 w i i x l 。一。1 2 + w 2 i x , ：一_ ：1 2 + + w p l x 驴一1 2 ( 2 6 ) 同样，m a n h a t t a n 距离和m i n k o w s k i 距离也可以引入权值进行计算。 在聚类分析中，常用的聚类要素的数据处理方法有如下几种： ( 1 ) 总和标准化，分别求出各聚类要素所对应的数据的总和，以各要素的数据除以 该要素的数据的总和，即， ( f = 1 ，2 , - - - , m ；j = l ，2 ，坊 ( 2 7 ) 这种标准化方法所得到的新数据满足= 10 - - 1 ，2 ，功 ( 2 ) 标准差标准化，即 ；三址二三上( f ：1 ，2 ，脚；，：1 ，2 ，由 ( 2 8 ) j 由这种标准化方法所得到的新数据，各要素的平均值为0 ，标准差为1 ，即有 弓2 壶善x ；= o ( 2 9 ) _ = 摆1 备m 嘞, 一毛) 2 = 1 ( 2 1 。) ( 3 ) 极大值标准化，即 毛。南2 ，州“，2 ，而 q 。d 经过这种标准化所得的新数据，各要素的极大值为1 ，其余各数值小于1 。 丢酗 = 勤 大连理工大学硕士学位论文 ( 4 ) 极差的标准化，即， =瑞maxlx-min|x3(f=l2，一，m；，=-，2，。czz，2 i i 翮u 2 1 2 。一，m ；7 。1 2 ，砂 。乙1 2 经过这种标准差所得的新数据，各要素的极大值为l ，极小值为0 ，其余的数值均 在0 与1 之间。 样本相似性度量是聚类分析的基础，针对具体问题，选择适当的相似性度量是保证 聚类质量的重要问题。但有了相似性度量还不够，还必须有适当的聚类准则函数。聚类 准则函数对聚类质量也有重大影响。 2 6 聚类准则函数 ( 1 ) 误差平方和准则 最常用的聚类准则函数，误差平方和适用于各类样本比较密集且样本数目悬殊不大 的样本分布。 以= 窆矧以一脚f ( 2 1 3 ) 式中，肌，是类型m 中样本的均值：m ，2 i l ，智“ x - ，= 1 ，2 ，c 。 历，是c 个集合的中心，可以用来代表c 个类型。 ( 2 ) 加权平均平方距离和准则 以= 弓町 ( 2 1 4 ) 式中，譬是类内样本间平均平方距离。 巧2 南磊哥叫 亿 _ 中的样本个数为一，_ 中的样本两两组合共有生璺f 尘种。 b x 1 1 2 表示所有样本之间的距离之和。 ( 3 ) 类间距离和准则 k - m e a n s 聚类算法的研究 加权类间距离和： = 窆h 一矿h 一曲 厶= c 弓h 一矿h 一所) j - i ( 2 1 6 ) ( 2 1 7 ) 式中，= 古姜_ ，= l ，2 ，c ，肌= 吉砉坼，为类型的先验概率，可以用 生来估计。 类间距离和准则描述不同类型之间的分离程度，所以以的值越大，表示各类之间分 离性好，聚类质量高。 大连理工大学硕士学位论文 3k - m e a n s 聚类算法分析 3 1k - m e a n s 算法介绍 j b m a c q u e 既在1 9 6 7 年提出的k - m e a n s 算法，是一种被广泛应用于科学研究和工 业应用中的经典聚类算法。 k - m e a n s 算法的核心思想是把一个数据对象划分为k 个聚类，使每个聚类中的数据 点到该聚类中心的平方和最小，算法处理过程： 输入：聚类个数k ，包含九个数据对象的数据集。 输出：k 个聚类。 ( 1 ) 从疗个数据对象中任意选取k 个对象作为初始的聚类中心。 ( 2 ) 分别计算每个对象到各个聚类中心的距离，把对象分配到距离最近的聚类中。 ( 3 ) 所有对象分配完成后，重新计算k 个聚类的中心。 ( 4 ) 与前一次计算得到的k 个聚类中心比较，如果聚类中心发生变化，转( 2 ) ，否则 转( 5 ) 。 ( 5 ) 输出聚类结果。 k - m e a n s 算法的工作流程如图3 1 所示。 酋先从n 个数据对象中任意选择k 个对象作为初始聚类中心；而对于所剩下的其它 对象，则根据他们与这些聚类中心的相似度( 距离) ，分别将他们分配给与其最相似的 ( 聚类中心所代表的) 聚类。 然后再计算每个所新聚类的聚类中心( 该聚类中所有对象的均值) 。不断重复这一 过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义 如下： e = 二嘲i p 一1 2 ( 3 1 ) 其中e 为数据库中所有对象的均方差之和； p 为代表对象的空间中的一个点； m ，为聚类g 的均值( p 和m ，均是多维的) 公式3 1 所示聚类标准旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能 的紧凑，而各聚类间尽可能的分开。 k - m e o a l s 聚类算法的研究 图3 1k - m e a n s 流程图 f i g 3 1 k - m e a n sf l o w k - m e a n s 算法优点是可以处理大数据集，k - m e a n s 算法是相对可伸缩的和高效率 的，因为它的计算复杂度为o b 打) ，其中珂为对象个数，七为聚类个数，为迭代次数， 通常有r 疗，k r ，因此它的复杂度通常也用o b ) 表示。 下面以一组二维数据为例，简要说明k - m e a n s 的聚类过程。 大舰工大学硕士学位论文 表3 1 二维数据 t a b 3 1t w od i m e n s i o n sd a t a 空间分布如图3 2 所示。 051 01 5 2 0 图3 2 数据分布 f 追3 2 d a t ad i s t r i b u t i o n 输入七= 3 ，k l = x 1 ，k 2 = x 2 ，k 3 = x 3 算法初始分别选定前三个数据作为初始聚类中心，进行一次迭代后的聚类如图3 3 所示。 051 01 52 0 图3 3 一次迭代 f i g 3 3 o n ei t e r