K均值聚类算法研究与改进（可编辑）

K均值聚类算法研究与改进（可编辑） K均值聚类算法研究与改进 学校代号: 学 号: 密 级:公开 长沙理工大学硕士学位论文 一均值聚类算法的研究与改进 学位申请人姓名 欧隧委 导币姓名及职称 堕堕塾壑 培养单位 篓鲨里三盔堂 专业名称 盐篁垫廛旦垫查 论文提交日期 ;生圣旦 论文答辩日期 兰生墨旦 答辩委员会主席 奎生基数援 ..? & ,长沙理工大学 学位论文原创性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人 或集体已经发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 或撰写的成果作品。对本文的研究做出重要贡献的个人和集体, 均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 日期:厶、’年岁月曲日 作者签名:庄是飞李 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 、保密口,在 年解密后适用本授权书。 ‘ 、不保密冈。 请在以上相应方框内打“” 作者签名: 日期:洳年岁月如 毒啦奎 导师签名: 日期:~年月如日 伊戢摘要 随着计算机技术的飞快发展,人们每天都会面临诸如文本、图像、音频、视频 等各种形式的数据,这些数据的数量是极其庞大的,如何快速有效地从这些海量数 据中提炼出其间所隐含的有价值的信息,成为人们十分关注且亟待解决的问题。数 据挖掘 ,由此而诞生。它为人们解决这个问题提供了许多卓有成 效的方法和工具。聚类分析就是其中最为重要的方法之一,它是数据挖掘技术的重 要组成部分。随着近年来对聚类分析技术的研究逐渐深入,其重要性已越来越得到 人们的认可。近年来,无论在理论方面还是在实际应用方面,聚类分析技术的研究 都取得了丰硕的成果。目前,聚类分析技术已在机器学习、模式识别、图像处理、 文本分类、市场营销及统计科学等领域得到了广泛的应用。 根据数据类型、聚类目的及应用的不同,目前已有的聚类算法大致可以分为以下 几种:划分的算法、层次的算法、基于网格的算法、基于密度的算法以及基于模型 的算法。其中,研究最为成熟最为经典的就是基于划分的一均值聚类算法。本文深 入研究和分析了一均值聚类算法的优缺点,并针对其聚类结果易受初始中心影响的 特点,对一均值聚类算法进行了改进。本文所做的主要工作有: .针对一均值聚类算法对初始聚类中心存在依赖性的缺陷,本文提出一种新的选 取一均值聚类算法初始聚类中心的方法,实验表明,该方法可有效解决由于初始聚 类中心选取的过于邻近而导致聚类结果不稳定的问题,提高了聚类结果的有效性和 稳定性。 .针对一均值聚类算法存在对初始中心的选择敏感且易陷入局部最优解的缺点, 本文将全局寻优能力强的差分进化算法引入聚类中。本文提出了一种改进的差分进 化算法,并将改进的差分进化算法和一均值聚类算法相结合,较好地解决了一均值 聚类算法初始中心的优化问题,实验表明,该方法有效提高了聚类质量和收 敛速度。 关键词:聚类算法;一均值算法;差分进化算法 . . . . . . .,. . , , ,. ,,. ,, , ? ,? . . .. : . ? . ,?. . .. . .. : ; ; 目 录 摘要. .............................................................?... .............................................. 第一章绪论 .研究的背景及意义??. .国内外研究现状??。 .本文所做的主要工作.. .本文的组织结构??.. 第二章聚类算法的分析与研究 .聚类简介??一 ..聚类的定义??. ..聚类的主要步骤. .聚类算法的评价指标一 .聚类分析中涉及到的数据结构??.. .聚类算法中常用的相似性度量方法 .聚类算法中的聚类准则函数一 .常见聚类算法的分类 .划分的聚类算法介绍 .本章小结??. 第三章一均值聚类算法的研究及一种改进算法 . 均值聚类算法介绍一 .. 一均值聚类算法基本思想.. 一均值聚类算法主要流程. 一均值聚类算法的主要缺陷及分析.. 一种改进一均值聚类算法? ..问题的提出??.. ..改进算法的详细描述..改进算法的基本流程? ..算法的实验结果及分析 .本章小结第四章基于差分进化的一均值聚类算法的研究及改进 .差分进化算法 ..差分进化算法的研究现状..差分进化算法的关键操作..差分进化算法的 基本框架.基于差分进化的一均值聚类算法? ..问题的提出..基于差分进化的一均值聚类算法描述??. ..基于差分进化的一均值聚类算法流程??.. .一种基于改进差分进化的均值聚类算法 ..问题的提出..改进 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ..基于改进差分进化的均值聚类算法描述. ..基于改进差分进化的一均值聚类算法流程. ..实验结果及分析 .本章小结 第五章 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 与展望 .总结??。 .展望??.. 参考文献?. 致谢??. 附录攻读硕士学位期间发表录用论文??.第一章 绪论 .研究的背景及意义 近年来,随着以英特网为代表的计算机信息技术的迅猛发展,人们生产、搜集、处 理数据的能力不断提高。人们将大量的数据广泛地应用于军事研究、科学实验、政府办 公、企业管理、电子商务及工程开发等各个领域,这些数据和人们的社会生活息息相关, 在各个领域发挥着重要的作用。但是随着人们积累的数据越来越多,甚至超出了人们的 处理能力时,信息爆炸成为当今时代人们不得不面临的严峻问题。难道人们积累的这些 海量数据真的无法再使用,只能成为所谓的数字垃圾吗其实不然,只要通过合理的思 想引导和适当的技术手段,就能使这些庞大的数据得到最大限度的利用,成为推动社会 发展的动力,成为孕育知识和财富的宝贵资源。目前,人们广泛使用的数据库系统虽然 具有高效的数据录入、查询及统计等功能,但却无法发现隐藏在这些海量数据中有价值 的联系和规则,也无法根据现有的数据实现对未来的发展趋势的有效预测,这使得人们 不得不面临“数据丰富而知识匮乏的窘境【。那么,如何从这些汪洋般的庞大数据中 快速有效地找出蕴藏的有意义有价值的知识和信息成为人们高度关注和亟待解决的难 题。数据挖掘 ,技术在这种需求的驱动下应运而生,并在社会生活 的各个领域得以迅速发展,显示出了极其强大的生命力。数据挖掘为人们解决上述问题 提供了诸多有效的方法和技术。数据挖掘技术将是未来几年全球范围内受到重点关注和 重点投资的十大新兴技术之一,是计算机科学技术研究和应用领域的热点问题。 数据挖掘常用的技术有决策树、关联规则、神经网络、聚类分析、粗糙集等】,聚 类分析是其中应用最广最成熟的数据挖掘技术之一。它是人们快速从数据中发现有用信 息的重要手段之一。聚类将由一定数量的数据对象组成的数据集分成若干个不同的组, 使同一组内的数据对象之间的差异尽可能的小,数据对象间尽可能的紧凑,而不同组中 的数据对象之间的差异度尽可能的大,数据对象间尽可能的分离。聚类分析是一种典型 的无监督的学习过程,由于它不需要事先知道所依据的对象特征,所以,在很多时候, 聚类分析可以被用来作为一种数据预处理的过程。目前,聚类分析在机器学习、模式识 别、图像处理、商业决策、文档分类和数据压缩等诸多应用领域得到了广泛的应用。 在商业应用中,聚类分析可以被用来帮助决策者发现不同的客户群并刻画不同客户群的于距离的聚类算法的研究,这期间有大量的适用于数据挖掘的聚类算法被提出来,但是 这些聚类算法所适用的问题和用户均有一定的特殊性,且这些算法在理论上和方法上仍 存在一些缺陷,有的甚至存在严重的不足之处。因此,对聚类算法进行更深一步的优化 研究,将有利于算法理论上的进一步完善及算法的应用和推广。如何 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出性能稳定且 简单实用的聚类算法将是研究人员的最终目标和富有挑战性的工作。 目前,聚类算法还存在如下主要问题【,急需深入研究解决。 算法对初始值选择敏感的问题:现有的很多聚类算法对初始值的选择是敏 感的,初始值的选择往往对算法的最终聚类结果有较大的影响。在数据挖掘中可以 采用多组互不相同的初始值分别进行聚类,选取其中聚类质量最好的作为最终的聚 类结果,但是这样做加大了计算的复杂度,且不能保证达到全局最优解。因此,对 初始值进行优化并找到聚类的全局最优解是一个具有重要意义的研究课题。 提高算法效率的问题:如何提高现有聚类算法的执行效率是目前聚类分析 领域中又一个值得研究的问题。对现有聚类算法进行有效改进,使其具有良好的可 伸缩性及较好的增量聚类的性能,对大规模数据库进行处理时可实现对数据库的一 次扫描。 基于不同数据库的算法研究:目前,我们应用于数据挖掘的聚类算法大都只适 用于关系数据库或者事务数据库,但在实际应用中我们往往会遇到诸如面向对象的、面 向属性的、文本的、时态的等各种形式的数据库,研究并设计出适用于这些不同类型数 据库聚类挖掘算法将是一项十分有意义的研究课题。 目前,聚类算法的研究成果大都是通过对均值算法、模糊均值算法进行改进而获得 的,这些成果都在一定程度上提高了聚类算法的性能。小波变换聚类算法由于满足一个 好的聚类算法的诸多要求,将使得对它的研究具有十分重要的意义。然而目前对小波变 换聚类算法及其改进方法的研究成果还比较少,因此,这将是一个值得进一步深入研究 的领域。 同国外的研究相比,国内从事聚类分析方面的研究起步较晚,且研究大多集中在科 研单位及高校,到目前为止,国内基本没有专门从事聚类分析方面设计及实现的公司或 企业。国内目前在这一方面的研究方向主要集中在对聚类算法的设计和实现,并在此基 础上进行改进创新。目前,人们已经成功地实现了将一些应用成熟的聚类分析工具加入 到统计分析软件中,如、等。 将聚类算法和其他领域的方法相结合可以达到改善聚类算法的一些缺陷和不足从 而提高聚类算法性能的目的。近些年来,人工智能技术的快速发展,为聚类分析领域 注入了新的活力。目前,已经被人们成功应用于聚类分析的实例有:基于遗传算法的聚 类方法、基于粒子群算法的聚类方法、基于差分进化算法的聚类方法、基于蚁群算法的 聚类方法等。 .均值聚类算法是最常见的聚类算法之一。因结构简单、快速高效且适用于 处理大 数据集,在众多科研领域得到广泛应用。但它同时存在一些缺陷和不足,例如聚类数目 值需事先给定、聚类结果对初始聚类中心的选取敏感、易陷入局部最优解、难以发现 球状簇以外其他形状的簇、对孤立点数据敏感等。在.均值聚类算法的发展过程中, 为了弥补它的缺陷和不足,研究人员提出了各种各样的有效改进措旌。文献】的作者通 过聚类指标和最大最小距离方法来自动确定最佳聚类数目,较好地解决了一均值 聚类算法中聚类数目值的确定问题。文献】的作者在深入分析均值聚类算法和层 次聚类算法各自优缺点的基础上,结合均值聚类算法的高效性和层次聚类算法聚类 精度高的优势,提出一种有效的混合聚类算法,在一定程度上克服了均值聚类算法 和层次聚类算法各自的缺陷。文献【】提出一种基于变长编码的改进遗传算法,并将该 改进遗传算法和.均值聚类算法有机融合,兼顾初始聚类中心的优化及最佳聚类数目 值的学习机制,有效地解决了.均值聚类算法对初始中心选取敏感及聚类数 目值需 事先人工给定的问题。文献】提出了一种基于加权方法的改进.均值聚类算法,该改 进算法可以有效消除噪声数据和孤立点数据对聚类结果的影响,且可以处理具有符号属 性的数据。文献】提出了一种基于密度及最近邻相似度的初始聚类中心选取方法,实 验表明,该方法可大大提高聚类结果的稳定性,且产生的聚类结果的质量较高。文献】 提出了一种基于数据对象在空间分布规律的新的初始聚类中心选取方法,该方法可有效 解决由于初始中心选取的随机性而导致的聚类结果不稳定的问题。文献【】采用一种基 于密度敏感的相似度量方法来计算数据对象的密度,生成最佳初始聚类中心,并设计出 均衡化准则函数,自动生成聚类数目,该方法可以得到稳定性较好的聚类结果。为了 克服.均值聚类算法的聚类结果对初始中心的选取存在严重依赖性的缺陷,文献】 提出一种基于粒子群的均值算法,将粒子群算法用于对初始聚类中心的优化,实验 表明,该算法具有较强的全局寻优能力,可有效提高聚类结果的质量。 已经被提出来的.均值聚类算法的具体改进措施还有很多。本文主要针对.均值 聚类算法对初始聚类中心选取敏感的缺陷,分别提出一种新的初始中心选取方法及一种 基于改进差分进化算法的初始中心优化方法,并通过实验验证了这两种方法的有效性。 .本文所做的主要工作 在对均值聚类算法进行研究和改进的过程中,本文主要做了以下两个方面的工 作: 一均值聚类算法的个初始聚类中心是随机选取的,聚类结果很不稳定。针对 .均值聚类算法对初始中心值的选取存在严重依赖性的缺陷,本文提出一种新的选取. 均值聚类算法初始中心的方法,实验结果表明,该方法可较好地解决由于初始中心选取 的过于邻近而导致聚类结果不稳定的问题。 由于.均值聚类算法存在对初始中心的选取敏感且易陷入局部最优解的缺陷, 本文将全局寻优能力强的差分进化算法引入聚类中,并将现有的差分进化算法进行改 进,并将改进后的差分进化算法和.均值聚类算法相结合,较好地解决了.均值聚类 算法初始中心的优化问题,实验结果表明,该方法显著地提高了聚类结果的质量。 .本文的组织结构 本文主要对.均值聚类算法及其改进方法进行研究,具体组织结构如下: 第一章简要介绍了本课题的研究背景及研究意义、国内外的研究现状以及本文所 做的主要工作。 第二章系统地介绍了与聚类算法相关的一些基础知识,如聚类的定义、聚类算法 的评价指标、聚类分析中的数据结构及相似性度量、聚类准则函数、常见聚类算法的 分类等,并对划分的聚类算法进行简要介绍。 第三章首先简要介绍了均值聚类算法,包括均值聚类算法的基本概念、操作 步骤等,并深入分析了均值聚类算法的主要缺陷,紧接着针对.均值聚类算法对初 始值选择较敏感的缺陷,提出一种新的初始中心选取方法,该方法较好地解决了由于 初始中心选取的过于邻近而导致聚类结果不稳定的问题,实验表明该改进方法有效提 高了聚类结果的质量。 第四章该章节是本文的重点内容,详细介绍了差分进化算法的相关概念、操作流 程及差分进化算法的优缺点等,提出了一种改进的差分进化算法,并将改进差分进化 算法应用于.均值聚类算法初始中心的优化。实验结果表明,该方法对初始中心进行 了有效优化,显著改善了聚类结果的质量。 第五章对本文所做的主要工作进行简要总结,并对下一步的研究工作进行展望。第二章聚类算法的分析与研究 .聚类简介 ..聚类的定义 聚类,简单的讲就是将一个给定的数据集分成若干个不同簇的过程。 聚类算法中的簇指的是数据对象的集合,且这种数据对象集合必须满足条件:同一簇中 的数据对象间具有较大的相似性,而不同簇中的数据对象间具有较小的相似性‘。聚类 的主要指导思想就是尽可能使同一簇内对象相似度达到最大,且不同簇间对象相异度达 到最大。 , 聚类和分类既有相似之处,又有不同之处,二者相似之处在于都是对给定数据集中 的数据对象进行分组,不同之处是二者的方法和过程不同:分类是首先从由类标识已知 的数据对象构成的训练样本集中提取出分类的模式,然后利用提取出的分类模式对没有 类标号的数据对象进行类标识,从而达到数据分组的目的;聚类则不需要依靠事先定义 好的类或预先标记好的训练样本,只需要依照某种度量相似性的度量标准如常用的基 于距离的度量标准将给定的数据集中的所有数据对象分到各个簇中从而达到数据分组 的目的。由此可见,分类是一种有指导的学习过程,而聚类是一种无指导的学习过程。 ..聚类的主要步骤 聚类的主要步骤由以下几个方面组成【每】: 数据预处理:根据聚类分析的要求,对输入数据集进行特征标准化及降维等 操作。 特征选择及特征提取:将由数据预处理过程得到的最初始的特征中的最有效 的特征选择出来,并将选取出来的最有效特征存放于特定的向量中,然后对这些有效特 征进行相应的转换,得到新的有效突出特征。 聚类分组:根据需要选择合适的相似性度量函数对数据集中的数据对象相 似程度进行度量,以此进行数据对象的聚类分组。 对聚类结果进行评估:依据特定的评价标准对聚类的结果进行有效评估,评 估聚类结果的优劣,以此对聚类分析过程进行进一步的改进和完善。 聚类的主要步骤可以用图.来表示。 评估聚类 输入给定 数据预处 理 结果 的数据集 叫鲨茎鍪 图.聚类的主要步骤 .聚类算法的评价指标 聚类分析是一个涉及数据挖掘、模式识别、机器学习、统计学等交叉学科的富有生 命力的研究领域。近年来,随着聚类分析技术的迅速发展及其应用的不断扩展推广,聚 类分析越来越成为数据挖掘中的一个备受关注且极富挑战性的研究课题。不同的应用领 域,人们对聚类算法有着不同的具体应用要求,也即有着不同的评价指标。根据目前现 有的应用情况,人们对数据挖掘中的聚类算法的要求即评价指标主要包含如下几个 方面: 算法的可解释性与可用性 通常人们的科研技术和成果都是面向社会的生产和生活的,最终要能为人们的生产 和生活提供服务和帮助,聚类分析的发展也是如此。聚类的最终结果要具有较好的可解 释性,能被用户所理解接受,且要较好地符合用户的应用需求,能被用户有效应用,这 样的聚类技术才有实际你的应用意义和应用前景。 算法的可伸缩性 现有的很多聚类算法在处理小规模数据集数据对象的个数不超过。的聚类问 题时得到的聚类结果是比较理想的,但在处理较大规模的数据集的聚类问题时却会出现 计算时间大大延长,聚类结果出现较大偏差,这种情况下我们通常认为聚类算法的可伸 缩性较差。而现实应用中,随着数据库技术的不断发展,各种数据库所包含的数据对象 的数量越来越大,这就迫切要求人们研究并设计出具有良好伸缩性的聚类算法来解决日 益增多的大规模数据集的聚类问题。 发现任意形状簇的能力 目前已有的聚类算法对于数据集中的数据对象间的相似程度的判定绝大部分都是 , 采用基于距离的度量方法,尤其是基于欧式距离的度量方法,这种方法直观易理解,但 是这种方法却有一个最大的缺陷就是只适合发现球形簇,发现其他形状簇的能力有限。 我们在现实应用中所遇到的聚类不仅仅具有像球形等规则形状,更有可能是各种各样的 任意形状,因此,深入研究并设计出具有发现任意形状簇能力的聚类算法将是一个十分 有意义的工作。 对记录输入顺序的敏感性 现有的很多聚类算法对记录的输入顺序是敏感的,即用同一个聚类算法处理同一个 数据集的聚类问题时,当数据集中的数据对象以不同的顺序输入时得到的聚类结果会有 差异,这样将会影响聚类质量的控制,因此,在实际应用中为了得到更高质量的聚类结 果,研究出对记录输入顺序不敏感的聚类算法十分必要。 具有处理高维数据的能力 目前的很多聚类算法对于处理两到三维的低维数据的聚类问题比较有效,得到的聚 类结果比较理想,但当处理维数较高的高维数据的聚类时会出现计算时间大大增加,聚 类质量下降的问题,在实际应用中维数达到十几维、几十维甚至更高维的高维数据集比 比皆是,因此,研究适应于处理高维数据的聚类算法是十分有意义的。 用户输入参数最小化 现有的很多聚类算法往往在执行前需要用户输入一些特定的参数,如最终的聚类数 目等。而这些参数往往难以确定,且对聚类结果往往有较大的影响,这导致了用户负担 的加重。一个好的聚类算法要求用户输入的参数应该尽可能的少,最好是不需要用户输 入任何参数。所有的应用开发都是面向市场需求的,因此研究设计使用户输入参数最小 化的聚类算法具有十分重要的价值。 具有处理不同类型数据的能力 目前很多聚类算法是用来处理数值型数据的,但在实际应用中,我们往往会遇到很 多非数值型数据需要被处理,譬如二元型、序数型数据等。这就对聚类算法提出了要能 够处理非数值型或混合型数据的新的需求。 对噪声数据的敏感性 在现实应用中我们所遇到的很多数据集中的数据并不是如我们所想象的那样“干 净,其中不乏掺杂了一定数量的未知的错误的噪声数据,目前所用的聚类算法大多是 基于距离的度量方法,这使得这些噪声数据往往对聚类结果有较大的影响。一个好的聚 类算法应该可以控制甚至屏蔽噪声数据对聚类结果的影响。 处理基于约束条件聚类的能力 我们在实际应用中所遇到的很多聚类问题往往不像理想状态下那样死板,往往会有 许多实际存在的约束条件对聚类问题进行限制,这就要求人们能够在充分考虑约束条件 的情况下得到最佳的聚类结果。在满足特定约束条件的情况下能够得到最佳的聚类结果 的聚类算法才是一个好的聚类算法。 .聚类分析中涉及到的数据结构 聚类分析中通常用到的数据结构有两种类型:数据矩阵和差异矩阵,下面分别介绍。 .数据矩阵 假设有由个数据对象构成的数据集,?。,每个数据对象由个属性构 成,即任意一个数据对象。,..一,那么数据集可以用如下的矩阵来表示, 即通常所说的数据矩阵。这种数据矩阵是一种对象一属性结构。该数据矩阵的各列分别 表示数据对象的一个属性,而各行可以看作是表示相应数据对象的一个向量。例如,将 一个班的所有学生的信息看成一个数据集,把每个学生看成一个数据对象, 这样的数据 对象又是由性别、年龄、学号、成绩等属性所组成的。 , 而 ~... ~... 。明/。, 一。.. ~... ~ 一 ‰;; 靠;%;靠 ,? 其中而是第个数据对象的第个属性的值。 .差别矩阵 由个数据对象构成的数据集为,也?。,用,?表示数据对象和? 之间的相异程度。薯,一的计算方法下一节中将详细介绍。则可以用如下的 表示所有 数据对象两两间差异程度的矩阵来表示该数据集,这样的矩阵称为差别矩 阵。 , ‖毛,‘, ‖%,‘。,.. 通常,,/为一非负数,其值大小直接反映数据对象,和?之间的相异程度。其 值越大,反映两数据对象间相异程度越大,相反,其值越小,则反映两数据对象间相异 程度越小,当两数据对象无限“接近时,则薯,无限趋于。显而易见: ,,,,一,,,。因此,差别矩阵是一个斜三角矩阵。它也被称为对象 一对象结构。 由于数据矩阵的行表示的是相应的数据对象,而它的列表示的是数据对象的属性, 行和列表示的实体不同,因此,数据矩阵被称为双模矩阵;由于差别矩阵的行和列表示 相同的实体,即都表示数据对象间的相似程度,因此,差别矩阵被称为单模矩阵。聚类 算法中到底采用哪种类型的数据结构,要根据聚类分析的具体应用要求而定,如果需要 采用差别矩阵进行聚类分析,则首先要将数据矩阵转换为差别矩阵方可聚类。 .聚类算法中常用的相似性度量方法 假设数据集“,,...,。中有两个数据对象薯和,,它们都是由个属性值构 成,即:“”..,和,缸,,?,,那么,如何衡量这两个数据对象间的相似接 近程度呢在聚类算法中通常是通过计算这两个数据对象之间的距离,,来判定 这两个数据对象间的相似程度。在聚类算法中,用来计算数据对象间距离的距离函数通 常要满足如下要求: 正定性要求:。,,?,这表明数据对象间的距离为一非负值,特别地,当 碍时,。,,,这表明数据对象自身间的相似程度最大。 对称性要求:,,,,,这表明数据对象间的距离满足对称性要求。 三角不等式要求:,一?,,,?,其中%为不同于和?数据 对象。即把两数据对象间的距离看成一条边的话,则要满足两条边之和大于 等于第三边 的性质。 衡量两个数据对象和之间相似度的距离,,的计算方法有很多,常用的 计算方法有如下几种。 明氏距离 明氏距离的计算公式如下式.: . 薯,。一.而一:,...%一,‘ 其中,为一个正整数。 欧氏距离 欧式距离的计算公式如式.: . ‘,。薯一:...%一, 显而易见,当公式.中时,就得到公式.,所以欧式距离可以看作是明氏距离 的一个特例。欧式距离是聚类算法中用来度量数据对象间相异性最常用的方 法之一。 象间距离的计算中去,可使得对数据对象间相似程度的度量更加科学合理,可以根据每 一个属性的重要程度为其赋一个权值,将这些权值引入到距离的计算中去,如引入权值 的欧式距离的计算公式如下式.: . ‘, ‘一。%‘一:?雌而一, 其中,,:?,分别是衡量各属性重要程度的权值,同样道理,曼哈顿距离、明氏距 离等也可以将权值引入距离的计算中去,因篇幅原因,在此不一一叙述。数据样本间相似度度量方法是聚类算法的基础,相似度度量方法选择的是否恰当对 最终的聚类质量有着重要的影响,应该针对具体问题,选择恰当的相似度度量方法。 .聚类算法中的聚类准则函数 数据对象间相似性度量方法是聚类分析的基础,但是光有相似性度量方法还是不够 的,要实现数据样本集中属于同二类的样本聚合,而不同类的样本分离的目标,还需要 借助于适当的聚类准则函数。聚类准则函数对聚类分析的最终聚类结果有着重要的影 响。聚类准则函数选择的恰当与否,将直接影响聚类质量的高低。 误差平方和函数以圆 假设有数据样本集,,...,。,被分成个簇%,%,...,%,各个簇分别包含的 样本数为啊,/,...,,则误差平方和函数以可以定义为式.: .. 以:量劾,一朋石『 以??’一朋石 其中,?’,,...,‰;,,...,表示第个类%中的任一样本,‰表示类 %中的样本个数,置表示第个类%的聚类中心,是通过计算类%中所有样本的均 值而得到的,即士鼍。 ‘ 误差平方和准则函数描述的是把含有个数据对象的数据集划分成个类时,所有 数据样本与其所在类的中心的误差平方和。以值的大小与聚类中心有关,显然,以越 大,说明各类内数据对象与其所在类的中心间误差约大,各类内数据对象间相异程度越 大,聚类的质量就越差;反之,以越小,说明各类内数据对象与其中心间误差越小,各 类内数据对象间相似程度越大,聚类质量也就越好。因此,通常采用误差平方和准则函 数的聚类算法的目标就是要找到使得以达到最小的最佳聚类结果。该聚类准则函数对于 各类所含样本的数目大致相当且各类的样本分布比较集中的数据集的聚类比较有效,聚 类结果比较理想,但是当不同类所含样本的数目悬殊较大时,如果采用误差平方和准则 得到的聚类结果可能会不尽如人意,因为为了使总误差平方的值以达到最小,有可能会 把原来属于同一类的数据样本分离开形成不同的类,从而使聚类的效果下降。 加权平均平方距离和函数 假设有数据样本集彳?,,...,矗,被分成个簇形,%,%,各个簇分别包含的样 如下式.: 本数为啊,,...,,加权平均平方距离和函数以的定义【 . ‘?乓?.., : 其中,作为加权的先验概率最是由其所在类%中的样本数‰及数据集彳中数据对 象总个数计算得到,最的计算公式如下式.: . &鲁,,..., 式.中,表示类%内所有数据对象间的平均平方距离,其定义如下式. 所不: 。南磊割一舻足,,?,. 类%内数据对象两两组合共有丝哮尘种组合,式.中瓦丽 和类畋内数据对 象两两组合的种数互为倒数,显而易见,表示的是%内数据对象间平均平方距离。 把式.代入式.可得式.如下: . ‘击荟‰,,..?, 和误差平方和函数以相比,加权平均平方距离和函数‘更适合于处理各类数据样本数目 悬殊较大的数据集的聚类,它可以有效防止同一个类分裂成多个类。 类间距离和函数以。及加权类间距离和函数以 类间距离和函数以四及加权类间距离和函数以【的定义如下: ?.., . 以。?%朋 :,,?, . ,‰一磊%一鬲 以::? 其中,,‰表示类%的聚类中心,即类畋中所有数据样本的均值。表示数据集中 所有数据样本的均值向量。足是加权的先验概率,计算如上式.所示。 类间距离和函数以。或加权类间距离和函数以描述的是数据集聚类形成的不同类 间的分离程度,显然,以。、以:的值越大,说明不同类间的分离程度越大,不同类间的 分隔边界越明显,则聚类的质量就越高;反之,以。、以:的值越小,说明不同类 间的分 离程度越小,不同类间的分隔边界越模糊,则聚类的质量就越低。.常见聚类算法的分类 随着聚类分析技术的应用和推广越来越广泛,大量的聚类算法被研究人员提出来并 得以应用。由于聚类算法错综复杂,不同聚类算法问可能存在交叉结合,这使得对目前 文献中现有的聚类算法进行精确划分非常困难。目前,对常见聚类算法比较统一的可以 被大家接受的划分是:划分的算法 、层次的算法 、基于网格的算法. 、基于密度的算法. 、基于模型的算法. 。常见的聚类算法大概可以分为这五 种。 划分的算法就是将一个给定的含有个数据对象的数据集,采用目标函数最小化策 略,通过迭代将数据集分成个分组。对于事先给定的聚类数目,首先算法给出一个 初始分组,然后通过反复迭代的方法改变分组,且要使得每一次迭代后的分组效果都要 比前一次的分组效果更优,而分组效果的优劣取决于同一分组中的数据对象问的远近程 度以及不同分组中数据对象间的远近程度,同一分组中的数据对象相互间越近越好,而 不同分组中的数据对象相互间越远越好。常见的划分的算法有.均值聚类算法、.中 心聚类算法及基于这两种算法的改进算法。 根据层次的分解形式的不同,层次的算法通常可以分为分裂的层次算法和凝聚的层 次算法两种。分裂的层次算法也称为自顶向下的算法,在算法一开始的时候将所有的数 据对象放在同一个簇中。在迭代过程中,每一次的循环都会将一个簇分裂为更小的簇, 直到每个数据对象在一个单独的簇中或满足算法终止条件为止。凝聚的层次算法也称为 自底向上的算法,算法在一开始的时候将每个数据对象都看做是一个单独的簇,然后逐 步将相邻的簇合并,直到所有的簇合并为一个簇或满足算法的终止条件为止。常见的层 次的算法有算法【、算法【、算法【和算法【等。 将数据样本空间划分成有限个网格结构,然后在这些单元式的网格结构上进行聚类 操作,这样的聚类算法就是基于网格的聚类算法。由于该算法的处理时间与数据集中数 据对象个数无关,而只与网格的数目有关,因此它的处理速度较快,这是基于网格的算 法的突出优势。常见的基于网格的算法有算法、算法【和 算法【】等。 基于密度的算法是根据数据集中数据对象的分布情况,将具有足够大密度的区域连 起来,形成相连的密度域,将处于相连密度域中的数据对象归成一类。不以距离作为分 类的衡量标准,这是基于密度的算法和其他聚类算法的最大不同。也正是由于这个原因, 使得该算法可以有效消除数据集中噪声数据的影响,有助于发现具有任意形状的簇。常 见的基于密度的算法有算法、算法和算法【等。 基于模型的算法就是试图将给定的数据集与某种 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 模型形成最佳拟合的方法。该 算法可以根据标准统计方法通常能自动确定聚类的数目,因此,是一种鲁棒性较强的算 法。常见的基于模型的算法有统计方法及神经网络方法【。统计方法通常应用于概念聚 类,主要通过概率描述来表示每个所获得的聚类。神经网络方法通常将每个聚类描述为 一个标本。根据某种度量方法,将新的对象分配到与其最相似的标本所代表 的聚类中。 .划分的聚类算法介绍 均值聚类算法是一种经典的划分的算法,本文的主要工作就是对均值聚类算 法进行研究并改进,这里将对划分的聚类算法进行着重介绍。 在聚类准则函数最小化策略的指导下,划分的算法将数据集, ...中的 个数据对象划分为个簇%,%,...,%,这个簇满足条件:同一簇内数据对象间的相 异度尽可能的低,而不同簇数据对象间的相异度尽可能的高。划分的算法的基础是相异 度的定义。通常采用的准则函数如式.所示:” . ,去??‰? ’‘丘; 其中,而数据集中的任一数据对象,,‰表示簇‰的中心。缸的值决定了数据集中 对象与簇的从属关系:当时,不属于簇%;当‰时,属于簇%。采用 式.作为准则函数的聚类算法得到的聚类结果具有特性:同一簇内数据对象尽可能 的紧凑,而不同簇数据对象间尽可能的分离开。 这种方法必须满足的条件有两个:聚类形成的各个簇均不是空簇,至少含一个 数据对象;数据集中的任一数据对象最终都会被划分到某个确定的簇中,且 只能属 于某个确定的簇而不能同时属于两个或两个以上的簇。 基于划分的算法中,应用最广最基本的就是均值聚类算法和.中心聚类算法, 其他基于划分的算法大都是由这两种算法改进和变异出来的,下面分别作简要介绍。 ..均值聚类算法首先,要求用户输入参数,即用户希望得到的聚类数目,将含有个数据对象的 数据集“,而通过特定的处理步骤划分成个簇,使得同一簇内数据对象间的 相异度尽可能的低,而不同簇数据对象间的相异度尽可能的高。而相异度的高低通常是 通过计算数据对象间的距离来度量的。 通常,.均值聚类算法是按如下过程操作的:第一步,从含有个数据对象的数据 集中随机挑选出个通常“对象作为初始簇的聚类中心,紧接着,计算数据集中 每个数据对象与这个初始中心间的距离,依据最近邻原则将各个数据对象划分到离其 最近的初始中心所属的簇中,然后通过计算簇中所有数据对象的均值获得新的聚类中 心,然后根据数据集中数据对象与新聚类中心间的距离对所有数据对象进行重新分配, 然后再更新聚类中心,此过程不断循环迭代,直到聚类中心和前一次得到的聚类中心相 比不再发生为止或是定义的目标函数达到收敛的条件为止,最后输出聚类结果。 我们通常采用误差平方和函数作为均值算法的目标函数,其定义如下.式。芝?聊川 产 氍 其中,表示聚类的数目,%,,...,表示聚类的第个簇,表示簇%中 的任一数据对象,,表示簇形,的中心值。.均值聚类算法的目标就是要找到使误差平 方和达到最小的个簇。当各簇中数据样本分布比较密集,簇间的边界区分明显时,应 用.均值聚类算法进行聚类效果比较理想。当同簇中数据样本分布不够集中且簇与簇 间边界模糊时,均值聚类算法聚类效果较差。 .均值聚类算法由于其原理简单易操作且处理大规模数据集时效率较高而得以广 泛应用。.均值聚类算法不是全局最优算法,它得到的通常是局部最优解,应用.均 值聚类算法求一个数据集的聚类全局最优解往往是一个难题。如果各簇的中心,即 簇内数据对象的平均值不能确切定义的话,则无法应用.均值聚类算法处理数据集的 聚类问题。例如,数据集中数据对象的属性为分类属性时就无法应用均值聚 类算法 进行聚类。这限制了.均值聚类算法的应用范围。由于均值聚类算法对数据对象相 似度度量采用的是基于距离的度量方法,因此,它只适合于发现形状呈凸面的簇及大小 相差不大的簇。另外,.均值聚类算法需要用户事先输入希望生成的簇的数目,这显 然加重了用户的负担。该算法对数据集中的噪声数据是敏感的,噪声数据对最终的聚类 结果有较大影响。 差。 为了弥补算法不适于处理大数据集的缺陷,人们提出了算法。该算法 的基本原理是对整个原始数据集依据随机原则进行多次抽样,用采样取得的数据集替代 原始数据集,然后利用算法对各个抽样集分别进行处理,分别得到聚类结果,然后 从这些聚类结果中选出最佳解作为整个原始数据集的最终聚类结果。对原始数据集的抽 样需要按照完全随机原则进行,只有这样,才能使得从抽样集中获得的中心点与从整个 原始数据集中得到的中心点较为接近。算法的性能和聚类质量和抽样规模的大 小有密切的关系。要想在效率和有效性之间进行较好的平衡,就必须按适度的规模对原 始数据集进行抽样。 .本章小结 本章简要介绍了聚类算法的一些基础知识,主要包括聚类的定义、聚类的主要步骤、 聚类算法的评价指标、聚类分析中涉及到的数据结构、聚类算法中常用的相似性度量方 法、聚类算法中的聚类准则函数、以及聚类算法的分类等,使我们对聚类算法有一个初 步的了解,为下面章节的介绍做好铺垫。 第三章一均值聚类算法的研究及一种改进算法 均值聚类算法是由..在年提出的。均值聚类算法是一种经 典的划分的聚类算法,是到目前为止应用最广泛最成熟的一种聚类分析方法。因该算法 具有简单快速、适于处理大数据集等优点,目前,已被广泛应用于科学研究和工业应用 中。 . 一均值聚类算法介绍 ?均值聚类算法是一种典型的基于距离的硬聚类算法,算法通常采用误差平方和函 数作为优化的目标函数,误差平方和函数的定义如.式所示: 足 . ??卜% ? 其中,表示聚类的数目,,,,?,表示聚类的第个簇,表示簇,中 的任一数据对象,,表示簇,的均值。显然,表示数据样本与簇中心间差异度平方 之和,值的大小取决于个聚类中心点。显然,越小的值,聚类结果的质量就越好。 因此,我们应该设法找到使聚类准则函数的值达到最小的聚类结果。 .. 一均值聚类算法基本思想 均值算法的基本思想是首先从含有个数据对象的数据集中随机选择个数据对 象作为初始中心,然后计算每个数据对象到各中心的距离,根据最近邻原则,所有数据 对象将会被划分到离它最近的那个中心所代表的簇中,接着分别计算新生成的各簇中数 据对象的均值作为各簇新的中心,比较新的中心和上一次得到的中心,如果新的中心没 有发生变化,则算法收敛,输出结果,如果新的中心和上一次的中心相比发生 变化,则 要根据新的中心对所有数据对象重新进行划分。直到满足算法的收敛条件为止。 .. 一均值聚类算法主要流程 均值聚类算法的主要流程描述如下: 输入:值及含有个数据对象的数据集。 输出:使误差平方和达到最小的个类。 更新各个簇的中心。并计算新的值 / \ 兰查 图. .均值聚类算法流程图 . 一均值聚类算法的主要缺陷及分析 均值聚类算法虽然具有过程简单易理解、快速有效、适于处理大数据集等优点, 但是其自身仍然存在一些不足和缺陷,在一定程度上限制了它的的应用和发展。主要体 现在以下几个方面: 均值聚类算法对初始中心点的选取非常敏感,算法易陷入局部最优解。 一均值聚类算法的个初始聚类中心是完全按照随机的原则选取的,这导致聚类结 果的波动范围较大,稳定性较差。通常,均值聚类算法采用的聚类目标函数是误差平 方和函数,该函数是一种非凸函数,通常这种函数同时存在很多局部最优值,而全局最 优值只有一个。一均值聚类算法是基于误差平方和函数的梯度下降算法。一种初始中心 的选取方式就代表一种搜索方式。均值聚类算法的初始中心是随机选取的,那么初始 中心的选取方式会有很多,算法的搜索方式也就会有很多。当搜索进行到误差平方和准 则函数的值不再减小的时候算法就结束。那么,沿着不同的搜索方向不同的初始聚类 中心选取方式进行搜索,当算法结束时得到的聚类结果往往会是局部最优解,而非全 局最优解。文献】将混合粒子群算法结合到均值聚类算法中,用于对均值聚类算 法的初始中心进行优化,大大提高了算法的全局寻优能力和收敛速度,增强了算法摆脱 陷入局部最优解的能力,有效降低了均值聚类算法对初始中心值的敏感度。在文献】 中,免疫机理被成功引入遗传算法中,提出了一种改进遗传算法,并将该改进遗传算法 用于对.均值聚类算法的初始聚类中心的优化,大大降低了.均值聚类算法对初始中心 值的依赖性,从而有效提高了聚类结果的质量。文献】提出一种基于粒子群优化的 均值聚类算法,该算法有效地克服了.均值聚类算法对初始中心值的选择存在严重依赖 性的缺陷,大大增强了算法找到全局最优解的能力,收敛速度快,聚类结果的稳定性较 好。针对一均值算法的聚类结果对初始中心值选取敏感的问题进行改进,是对均值 聚类算法进行改进的重要的方式之一。 .均值聚类算法对噪声数据和孤立点数据较为敏感。从.均值聚类算法的聚 类过程我们知道,簇的中心的每一次更新都是通过计算簇内所有数据对象的均值获得 的,而噪声数据和孤立点数据通常是远离数据样本空间的密集区域,如果将噪声数据和 孤立点数据加入到簇的中心的更新计算中,则势必对簇的中心的计算产生重要影响,甚 至有可能使新计算出来的簇中心严重偏离数据样本空间的密集区域,以这样的簇中心进 行聚类将对聚类结果产生极为不利的影响。这就是一均值聚类算法对噪声数据和孤立点 数据敏感的原因。