本科毕业论文-数据挖掘K均值算法实现.doc

本科生毕业论文设计 数据挖掘数据挖掘K-K-均值算法实现均值算法实现 作者姓名： 指导教师： 所在学院：数学与信息科学学院 专业（系）：计算机科学与技术 班级（届）：2013届计算机班 二零一三年五月二日 目 录 中文摘要、关键字 . 1 1 绪论 . 3 1.1 本文研究的背景和意义 . 3 1.2 聚类分析国内外研究现状 . 5 1.3 本文所做的主要工作 . 7 2 聚类算法的分析与研究 . 8 2.1 数据挖掘简介 . 8 2.2 聚类的基本知识 . 8 2.2.1 类的定义及表示 . 9 2.2.2 聚类的相似度量方法 . 9 2.2.3 聚类间的距离测度函数 . 11 2.2.4 聚类分析的一般步骤 . 12 2.3 常用的聚类分析的方法介绍 . 13 2.3.1 基于划分的方法 . 13 2.3.2 基于密度的方法 . 13 2.3.3 基于层次的算法 . 13 2.3.4 基于模型的算法 . 14 2.3.5 基于网格的算法 . 14 2.4 常用的划分聚类算法的分析 . 14 2.4.1 K-均值聚类算法 . 15 2.4.2 K-中心聚类法 . 15 2.5 本章小结 . 16 3 K一均值聚类算法的研究 . 17 3.1 K-均值聚类算法介绍 . 17 3.1.1 K一均值聚类算法基本思想 . 17 3.1.2 K一均值聚类算法主要流程 . 17 3.2 K-均值聚类算法的主要缺陷及分析 . 18 3.3 本章小结 . 19 4 K-均值聚类算法的实验 . 20 4.1 实验结果分析 . 20 4.2 本章小结 . 25 5 总结与展望 . 26 5.1 总结 . 25 5.2 展望 . 26 参考文献 . 28 英文摘要、关键字 . 31 1 1 论文题目：数据挖掘K均值算法实现 数学与信息科学学院 计算机科学与技术专业 指导教师：郭瑞强 作者：郝蓓 摘要：随着互联网技术的迅速发展，现在的人们每一天都会面临例如文本、图像、 视频、音频等各种数据形式，这些数据的数据量的大小是很惊人的。怎样能够很快的并 且高效地从这些大量数据中挖掘提炼出它所蕴含的价值，成为现在人们特别关注并且需 要马上解决的问题。数据挖掘(Data Mining，DM)正是因为这个才慢慢诞生出来。数据挖掘经过一段时间的迅猛发展，诞生出 了大量的理论结果和现实使用成果，它提供了许多工具和卓有成效的方法来解决问题。 数据挖掘中有一项是很重要的研究领域，那就是聚类分析，这是一种对数据进行按照不 同的依据将数据进行分组或者将数据进行划分的方式。聚类无论在生物科学研究，还是 在商务贸易中、图像分析处理、网页内容分类等其他日常生活的领域都得到了很好的应 用。 根据使用的数据类型、使用的功能的不同、聚类需求的不同，目前的聚类算法大概 有以下几种：基于划分的算法、基于层次的算法、基于密度的的算法、基于模型的算法 以及基于网格的算法。在这之中，基于划分的K- 均值聚类算法是目前研究最成熟传统经典的算法。K- 均值算法的应用领域特别广泛，覆盖范围涉及语音频率压缩还有图像及文本聚类，另外 在数据预处理和神经网络结构的任务分解等也发挥其重要用途。本文所做的工作有： 本文第一部分：详细介绍了本次论文研究的背景和目的，以及所选题目的考虑思路 ，还有在当前国际形式下，聚类分析在国际上的地位及国内外研究成果综述，最后介绍 了本论文算法实现的内容和论文整体布局安排。 第二部分：首先详细描述了数据挖掘的来源发展还有它的概念定义，下面主要介绍 聚类分析，包括聚类的基本概念原理等基础性知识，介绍了聚类算法的内部特性，详细 描述了几种目前聚类分析的方法，总结比较各个方法的特点及其长短处。最后对本论文 所研究的基于划分的聚类算法进一步讨论都有哪几种算法。 2 2 第三部分：这是本论文的重点，本论文所要讨论的K- 均值算法，从它的概念基本思想算法流程等方面对K- 均值算法进行详细系统的介绍，并且详细分析了它的优缺点。K- 均值算法对初始值的选取比较敏感和对数据的输入顺序不同也会影响聚类等问题，所以 本文针对该问题进行了验证，通过实验证明了这两个因素对聚类结果会有哪些影响。实 验表明，K- 均值算法对初始值和数据输入顺序很敏感，但是这两个对聚类结果影响的方面不同。本 文通过六个实验结果分析得出，改变初始点，对聚类结果的影响不大，只是会改变迭代 次数，而且选取初始的连续的几个数据为初始点迭代次数最少，虽然中间间隔的几个数 据作为初始点也出现了最小的迭代次数，但这对数据集来说有太多的不确定性，所以还 是选择最开始那几个数据为数据聚类初始点；对于改变数据集的输入顺序，聚类结果与 之前的有很大的改变，实验结果说明输入顺序不同既影响了聚类结果也影响了迭代次数 。通过这些结论为以后用户使用K- 均值算法提供了很好的帮助，也为该算法的改进提供了参考。 关键词：数据挖掘 聚类分析 K-means算法 实验验证 3 3 1 绪论 1.1 本文研究的背景和意义 近年来，随着科技的进步以及互联网的普及，以计算机为代表的信息技术有了巨大 发展，人们产生、发现、整理、利用数据的能力不断提升。到目前为止，数据在我们的 日常生活中无处不在，它广泛应用于科学研究、政府日常办公、军事力量分析、企业管 理电子商务、统计学分析等等各个领域。虽然我们知道这些数据的重要性，但是随着时 间越来越久，我们积累的数据量是不断地在加大，相应的我们分析处理这些数据的能力 也要增加，但是后来数据量的增长速度已经超出了我们的能力范围，所以我们必将面临 的严峻问题是数据爆炸。难道真的没有办法可以很科学的处理这些海量数据吗？事实并 非如此，人类的智慧是无穷的，人们已经通过理性的思维和恰当的技术，将这些海量数 据充分利用，使它们成为社会发展进步的强大的力量源泉。目前，广泛使用的数据库系 统虽然具有高效率的录入所有数据查询所需数据统计数据类别等功能，但是并不能发现 这些海量数据中蕴藏的内部关联规则，也无法从当前现在的数据情况去预测未来的数据 内容的发展趋势，更不可能做出决策判断，使得人们逼不得已去面对“数据丰富而知识 缺乏”的困镜1。所以数据挖掘（Data Mining）技术因此就慢慢诞生了，并且快速的发展应用社会的各个领域，表现了其坚韧 的生命力与适应力。该技术就是从“数据矿山”中发现“知识的宝藏”。 数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提 取发掘出来隐含在当中的、人们在这之前不是特别了解的、但又是隐含有用的信息内容 和知识内容的非平凡过程2 。原始的数据类型可以是多样的，比如数据库中的数据结构化数据类型，那些图像图形 资料及文字类资料是半结构化的数据类型，当然也包括网络互联网上的那些数据我们称 它们为半结构化的数据类型。我们可以通过归纳演绎等方法来发现知识，也可以用统计 4 4 学的数学或非数学的方法总结数据来得到我们想要的信息。这些我们得到的信息内容和 知识内容的过程就是挖掘的一个过程，我们把挖掘的知识可以应用到我们的生活中，包 括未来决策规划、优化信息管理方案、调整控制模式、改进查询方案等等来更好的维护 和利用我们现有的数据。所以数据挖掘涉及到的学科很广泛，它是各个学科的交叉，它 用到了人工智能数学统计学与数据库等技术来实现它自己的目的，需要这些领域的工程 技术人员来共同配合，尤其是数据库管理人员。 现在的数据挖掘技术已经开始走向科技产品研发及技术应用，不再是之前的单纯的 搞一下研究而已，我国市场经济制度在不断地完善与发展，经济实力也在不断进步，现 在我们的社会对数据挖掘技术的需求越来越强烈，目前我国很多的有眼光的软件企业已 经将目光聚集于此，来研发更多适应市场需求的数据挖掘软件产品，随着市场日趋成熟 ，广大消费者的应用需求也是慢慢变大，相信将来会有更多成熟的中国数据挖掘软件面 向市场。 聚类分析是数据挖掘的一个发现信息的方法，已经被人们深入的研究了很长时间， 主要的是对基于距离的聚类分析的研究。聚类是一种无监督的学习，分类正好与它相反 ，分类是一种有监督的学习，聚类主要是划分无标记的对象，使这些无标记的对象变的 有意义，对预先定义的类与带类标记的训练实例不具有依赖性。所以聚类分析在我们的 日常生活中的应用范围非常广泛： 在商业上，聚类可以根据消费者数据库里面所记录的数据信息，对消费者进行划分，根 据各个消费者的特征，以帮助市场营销员按照市场需求及时调整货物的摆放次序等一系 列营销计划的实施； 在社会学中，聚类用来发现目前社会结构组成中潜在的社会结构； 在网络挖掘中对互联网上批量的数据信息进行有效的划分与分类，实现信息的有效利用 ，对数据信息检索效率方面有显著提高； 在生物信息学中，在大量的基因群中发现功能相似的基因组，对基因因功能不同进行划 分对其固有的结构特征进行分析，来更好的为我们的医学发展提供有利条件； 5 5 在空间数据库领域，聚类分析能对相似地理特征区域及它们的人和环境的不同特征进行 识别，来研究地域文化提供条件。 本文主要选择聚类分析中基于划分的K- means算法并实现它的应用，对数据集的数据进行聚类分析。本文在实现它的基础上， 对该算法对初始值和数据输入顺序敏感的问题进行了验证，通过六次试验，分别对这个 两个方面进行验证，并对聚类结果进行分析比较，从而得出结论。本文通过对不同输入 条件的实验验证，得出K- 均值算法对初始值得选择和数据输入顺序是很敏感的结论，通过实验结果可得出在今后 使用K- 均值算法时我们应该怎样避免其聚类出不准确的聚类结果和今后改进算法应该改进的方 向等问题。 1.2 聚类分析国内外研究现状 目前，国内对于数据挖掘聚类分析的研究的集中部门还是科研单位和各大高校，国 内还没有公司企业专门从事聚类分析的研究，相对于外国来说起步较晚。各大科研机构 与高校对聚类的研究主要是对数据集聚类算法的设计并实现，以研究出来的算法为基础 对算法改进。目前人们已经在统计分析软件中应用一些聚类分析工具，如SAS等软件。 为大型的数据库寻求有效的聚类分析方法是目前聚类分析的主要研究工作，目前研 究方向包括以下几个方向： （1）可伸缩性：目前的聚类算法针对小型数据库，数据量是几百范围内的，对于有 很庞大数据量的数据库会造成结果的不稳定性，可伸缩性强的算法就亟待的研发出来。 （2）属性不同情况下的处理能力：现在开发出来的聚类算法所针对的数据类型都是 数值型，但实际上的聚类类型的信息是不确定的，如二元数据、序数型的、分类型的等 或者是所已知的各种数据类型的混合。 （3）聚类形状：在欧几里得距离的基础上发现所得的簇的形状是球状簇，它们有相 近的距离与密度，形成一个簇，但是我们更希望能够有一种算法实现各个不同形状的簇 。 6 6 （4）决定结果的输入参数：聚类算法的实现过程中相当多的是必须让用户提前输入 想要聚类出来的簇数K，当前的算法对这些K的值是相当敏感的，大型的数据流对这些要 求很严格，对结果的影响很明显，使用户在输入时加大了分析的工作难度，很难控制。 （5）输入数据的顺序问题：有的聚类算法对输入数据的顺序是有要求的，不同的输 入次序会有不同的聚类结果，这就特别需要对数据顺序不敏感的算法开发出来，更好的 适应人们的要求。 （6）高维数据的处理：含有若干维数据属性的数据库是很常见的，但是擅长处理两 维或三维的聚类算法才是目前成熟的应用的算法，一旦高维数据需要聚类处理，这就是 一个难题，这就需要算法有很强的实用性。 （7）污染数据的发现：数据是一个不确定而且无限性的群体，我们不能保证数据集 中的数据是完全集中的，难免会有个别的孤立点造成污染数据，影响整个结果，应该开 发出能智能识别这些孤立点的数据的算法，来优化聚类结果，目前大部分是通过对目前 算法进行改进来实现。 （8）有约束条件的聚类：实际的聚类情况是有很多限制的条件的，在实现这些聚类 时，既要按约束条件又要按聚类要求实现，是很有压力和挑战的一项任务。 （9）可使用性和可解释性：大多情况下的聚类结果，对于客户来说都希望它们简单 易懂，一目了然，所以我们要优化聚类结果界面的研究，选择适合每个客户需求的聚类 方法来满足他们的需求。 同时聚类分析算法主要着手于以下的几个问题的解决3： （1）初始值的选取及输入顺序对结果有何影响 在数据挖掘的学科范围内寻找最优解的过程是通过迭代不同的初始值实现，但是这 个办法不是很可靠，它的意思就是表示不能百分之百的确定找到最优解。其实寻找最优 解就是在优化原来的聚类的结果，通过重复聚类找到所设计的目标函数的最优解，但是 这个目标函数一般都不是有最值的函数，所以它的最小值并不是很容易确定，因为它并 不唯一，有可能找到的这个只是局部最小值，而不是全局最小，所以这种非完全单调函 数的全局最小值的查找是目前最急着等待解决的问题。 （2）以小波变换为基础的聚类算法 因为当前主要是对均值算法与模糊算法的研究改进而得到的研究成果，这些研究成 果使得目前的聚类分析算法提高了它的性能属性。小波变换聚类算法同样符合好的聚类 7 7 算法的各项要求，目前对小波聚类的研究还有很大程度的空白，如果花大的精力进一步 研究会有更加深入的突破。 （3）算法的效率改善提高的问题 聚类的效率问题是目前一个很棘手的问题，因为人类在进步，数据量会越来越庞大 ，应该增强目前聚类算法对更大数据库的处理能力，即增量聚类，使聚类算法在聚类的 数量上有更好的弹性，尽量减少在工作时对庞大数据库的扫描次数，进一步提高它的工 作效率。 （4）数据库类型 目前，基于聚类算法的数据库比较单一，仅仅包括关系或事务数据库，应该着眼于 其他数据库类型应用算法的研究，比如面向以属性为内容的数据库、以文本为内容的数 据库、各个不同时态为内容的数据库、地理数据库多维数据库等的算法开发，这是一项 非常艰巨而且有意义的研究任务。 聚类分析中的算法有很多种，详细分析比较了各个算法的优缺点，本文着重介绍了 K- 均值算法，分析它本身的算法优点与不足，并对算法实现，着力于对影响该算法聚类结 果的不同初始条件进行验证，以更好在以后的实际应用中使用它。 K-均值算法是聚类分析最常用的算法之一。K- 均值算法的应用范围非常广泛，因为它的操作简单，适合处理庞大的数据集，但是它同 时也暴露出自身的不足，如易陷入局部最优解的结果里面、需要用户提前输入参数、发 现簇的形状比较单一等，已经有很多专家对这些问题进行了改进，文献4作者通过最大 最小距离和DBI聚类指标解决了K- 均值算法对初始值K的选择问题，能够确定出最佳的聚类数目。文献5的作者用K- 均值算法与层次聚类算法进行混合出一种新的聚类算法，充分发挥了层次聚类的精确性 和K- 均值的高效性。文献6的作者对遗传算法提出一种改进算法，基于比变长编码，利用这 种算法与K- 均值结合解决了对初值选择的敏感问题等等，目前已经有很多被发表出来的对K- 均值的改进的算法。 1.3 本文所做的主要工作 8 8 首先对数据挖掘这门学科的背景和发展前景做了分析，本文主要研究数据挖掘的聚 类分析，所以介绍了聚类分析目前国内外的地位与发展方向，以为下文展开作铺垫，这 方面阅读了许多聚类相关文献，许多新的聚类分析方法先后被各国的科研工作者提出并 应用，这些在本文有详细列举。除此之外本文对聚类分析中的常用的五种方法做了简要 介绍，列举了五种方法中目前比较常用的算法，并分析了每个算法的适用领域与基本思 想。 本文着重讨论的是基于划分的聚类分析方法中的K- means方法，对KM方法进行了详细的介绍，包括基本思路工作流程等，本文通过分析K M算法的缺点，通过实验验证了对初始点的选取和数据输入顺序敏感的验证，通过两个 实验分别得出这两个因素对聚类结果产生怎样的影响并得出结论，实验表明初始点不同 只是影响聚类迭代的次数，对聚类结果的影响不明显，只是少数数据的聚类结果发生改 变；数据输入顺序的不同，不仅会改变数据聚类的迭代次数，也会让聚类的结果发生明 显改变。 2 聚类算法的分析与研究 2.1 数据挖掘简介 数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提 取发掘出来隐含在当中的、人们在这之前不是特别了解的、但又是隐含有用的信息内容 和知识内容的非平凡过程2。其实数据挖掘就是通过各种分析算法工具从巨大数量的数 据中挖掘所需要的数据与模型两者关系的一个过程，可以通过得到的这些关系，对未来 的数据与模型关系进行预测。通常根据不同用户的需求，和他们所提供的数据类型，数 据挖掘的数据库的类型也是不一样的，通常包括关系数据库类型、事物数据库类型、多 媒体数据库类型等。其中关系数据库实际上就是使用数学学科上的方法来处理数据之间 的关系，我们生活中随处可见关系数据库，比如交通部的车辆数据库、银行的客户记录 9 9 等。事务数据库一般是将几个事务数据库的数据一起导入到只能用来读数据的数据挖掘 库中，做成一个数据集市，然后把其作为挖掘的对象。多媒体数据库顾名思义就是包含 大量视频音频文件，模式识别技术被用于该领域。 数据挖掘包含很多类别，包括分类分析、聚类分析、关联分析孤立点分析等其他分 析。其中分类分析包括分类和回归，分类分析是一种预测模型，通过现有数据预测将来 的数据，如果预测的数据是离散的即叫做分类，如果是连续的即叫做回归。聚类分析则 是将大量数据中形似的数据分到一组，一个数据集大概包括几组数据，聚类没有明显的 属性目标，而是挖掘隐藏的属性来进行聚类，聚类分析中的基于划分的K- 均值算法是本文的研究对象。关联分析分析数据与数据之间关联关系还有它与其他数据 的派生关系。孤立点分析是针对那些远离数据集的点，对不同的客户，别人的孤立点可 能对于他来说是很重要的信息，孤立点分析就是对这些远离数据集中心的数据信息进行 挖掘。孤立点的研究是将来我们必须重点研究的领域，因为几个孤立点就会影响全局的 聚类结果，这是不容忽视的。 2.2 聚类的基本知识 2.2.12.2.1 类的定义及表示类的定义及表示 （1）类的定义 要想聚类操作首先要明确类的定义。世界错综复杂事物存在的方式也不尽相同，所 以类的定义并不唯一。以下将列举出常用的类的定义： 设：含有K个样本的集合A，Mi是其中的某个样本，T和C是范围阀值，那么：如果 任意的Mi，Mj A，都有D（Mi，Mj）T，则A称为一类； （2）类的表示； 聚类的表示方法也是有不同的，一般用以下三种： 自然语言表示：直接用自然语言直观的描述出这些数据是属于哪个簇的； DNF表示：用析取范式表示明了、简洁、易懂。例如： (36PT70)V(345AM1234)； 聚类谱系图：目前使用的聚类算法输出结果大部分都是这种，这种方法表示非常详细， 它能表示出这些样本自成一类的所有中间情况，而且都会有各个类的平台高度，我们叫 这种图为标度聚类谱系图。 1010 2.2.22.2.2 聚类的相似度量方法聚类的相似度量方法 聚类分析按照数据样本性质的相似程度的大小进行划分，确定这些相似程度的大小 必须有一个准则来判断它们的程度大小，这个判断准则叫做相似度方法，主要是在距离 和相似系数的不同。 距离：样本点之间的相似性我们就用某种距离函数表示，距离近的表示样本点相似 ，具体计算时可以把样本看做有M个属性的变量，即这个样本就是在一个M维的空间中 的一个点。 距离函数：设P是所有样本集合的集合名称，如果满足： 正定性D(M，N)0，if MN D(M，N)=0，if M=N 对称性D(M，N)=D(M，N) 三角不等式D(M,N)+D(N，L)D(M，L) 我们称它们为距离函数。 聚类分析中经常使用的的距离函数有： 明氏(Minkowski)距离 (2.1) 1 1 (,)() p m m ijikjk k d x xxx 当m取1时，则表示绝对距离，当m取2时就表示欧式(Euclid)距离，当m取无穷大时 就表示切比雪夫(Chebyshev)距离。 如：欧氏距离 (2.2) 1 2 2 1 (,)() p ijikjk k d x xxx 马氏(Mahalanois)距离 1 1 2 (,)()() T ijijij d x xxxSxx (2.3) 其中 S 是由样品集N（）算得的协方差矩阵： 12 , . , . , jn xxxx 11 11 ,()() 1 nn T iii ii xxSxxxx nn (2.3.1) 1111 样品聚类一般情况下被叫做Q型聚类，是以距离矩阵为出发点的。明氏距离改进后 得到了马氏距离，所有的线性变换对于马氏距离来说是不变的，多重相关性马氏距离也 把它克服了。 方差加权距离 (2.4) 1 2 2 2 1 () (,) p ikjk ij k k xx d x x s 其中 . (2.4.1) 22 11 11 ,() . 1 nn ikkikk ii xxsxx nn 在聚类分析中除了对样本点聚类，对特征变量也要根据实际情况进行聚类，所以对 于特征向量而言，不必非用距离函数来确定它们的相似测度，还可以用相似系数。 相似系数：当对含有k个指标的变量的数据集进行聚类时，就用相似系数来作为判断 所有变量之间的相似程度（或关联程度）的标准指标。一般地，若表示Cab变量Xa,Xb之 间的相似系数，应满足： 1）| Cab|1且Cab=1； 2）Cab=1或Cab=1Xa=CXb； 3）Cab=Cba； Cab的绝对值越与1接近，越说明变量Xa,Xb之间的关联性越大。 相似系数中相关系数和夹角余弦是目前最经常被使用的。 （1）相关系数 变量之间的相关系数我们可以这样定义为： , xx . (2.5) 1 22 11 ()() , ()() n ii i nn ii ii xxxx s r ss xxxx 实际上，只是变量之间的观测值之间 r , xx 1212 (,.,)(,.,) TT nn xxxxxx 与 与 的相关系数而已。相关系数表示两个向量的相关程度是多少。 （2）夹角余弦 1212 变量的观测值 , xx ，其夹角余弦我们可以这样定义为： 1212 (,.,)(,.,) TT nn xxxxxx 与 与 1 22 11 n ii i nn ii ii x x c xx (2.6) 变量聚类一般情况下被叫作为 R 型聚类。一般R 型聚类，相似系数矩阵 C 是数据集聚类的出发点，相似系数矩阵不仅能够使用相关矩阵，而且能够使用夹角余弦 矩阵。 2.2.32.2.3 聚类间的距离测度函数聚类间的距离测度函数 对于不同的两个类，如果他们之间距离可定义，那么就用如下几种定义方式来定义 他们的距离： （1）最短距离法：顾名思义它表示两个类中的元素，相离最近的两个元素的距离来 表示这两个类之间距离，公式表示为： min, rkpkqk DDD (2.7) （2）最长距离法：跟最短距离法类似，表示两类之间距离的是两类中距离最远的元 素，公式为： . max, rkpkqk DDD (2.8) （3）类平均法：求出两个类中任意两个数据的平均距离，用求出来的这个数据来表 示这两个类的平均距离，这就是类平均法，我们可以用下面的公式来表示： (2.9) pq rkpkqk rr nn DDD nn （4）重心距离法：它的定义表示两个类之间重心相邻的距离为类距离,公式表示为 ： (2.10) 2222 pqpq rkpkqkpq rrrr nnnn DDDD nnnn 1313 其中类的重心公式为： （也就是各元素的平均向量之间的距离） (,) pqpq Dd xx （5）离差平方和距离：用类中各元素的离差平方和的总和得到两个类Gr和Gk的直 径分别是Dr和Dk,类Gr+k=Gr Y Gk,用这种方法尽量让类间的离差平方和大，而类内部的元素间的值小，公式表示为： . (2.11) 2222 pkqk k rkpkqkpq rkrkrk nnnn n DDDD nnnnnn 其中类直径：有的把类中相距最远的两个元素的距离作为直径，也有的将类中各元 素指标的离差平方和的和作为直径，离差平方和的计算公式为： 2 () () pq T pqpqpq pq n n Dxxxx nn (2.12) 2.2.42.2.4 聚类分析的一般步骤聚类分析的一般步骤 聚类分析的步骤大体可以分为四步9-10： （1）数据的预处理：就是在拿到一个数据集的时候，首先分析对这个数据的聚类分 析要求，并根据这个要求对现在的数据集做降维或者特征标准化等初步的处理操作，也 就是去掉没用的特征值。 （2）特征的选择及提取：对于第一步得到的信息，进一步细分，就是将预处理后的 信息再选择最有效的特征，并将选择出来的特征用向量的方法转换成新的有效突出特征 ，以供聚类分组时作为分组判定的条件。 （3）聚类：这就要用到前面的相似性度量函数，选择距离函数还是选择相似系数等 方法来度量选出来的有效特征值的相似度，进而完成对该数据集的聚类分析。 （4）评估结果：结果进行分析，看有没有完成预定的要求，并根据聚类方法的评价 标准对结果进行科学评估，即聚类分析的九个方面的要求是否满足，然后根据评估结果 判断是否对本次的分析过程进行改进，以及怎样改进。 2.3 常用的聚类分析的方法介绍 目前聚类分析算法的应用技术日趋成熟，已经有很多的聚类算法被提出来，但是算 法种类增多，同时这些算法的融合会越来越明显，使得各种算法的界限不明显，但是目 前大家默认的有五种划分方法,分别是：以划分为基础的算法(Partitioning Methods)、以密度为基础的算法(DensitybasedMethods)、以层次的为基础的算法(Hierar 1414 chicalMethods)、以模型为基础的算法(Modelbased Methods)、以网格为基础的算法(Gridbased Methods)。 2.3.12.3.1 基于划分的方法基于划分的方法 划分算法11的基本思想就是通过迭代的方法将含有M个数据对象的数据集分成K个 簇。具体步骤是，用户首先给定所要划分的簇的个数K，算法先进行初步划分为K组，然 后用迭代的方法反复再进行分组，每次新得到的分组比前一次要优化，是否优化的判定 标准是同组数据之间以及不同组数据之间的相似程度，同组相似程度越大组间相似程度 越小分组越优化，目前常用的算法有K-means算法、K- medoid算法以及以它们为基础的算法的各种改进。以划分为基础的聚类算法将在后面的 章节做重点介绍。 2.3.22.3.2 基于密度的方法基于密度的方法 基于密度的算法12与其他的算法最大的不同在于不是以元素间的距离作为判断标准 ，而是根据数据对象的分布密度来判断，正因为如此该算法有助于发现数据集中的噪声 数据，减少噪声数据对聚类结果的影响，所以密度的方法可以对任意形状的簇聚类，基 本思想是将密度较大的区域识别出来，形成连在一起的密度域，并将他们归为一类。目 前比较传统的的以密度为基础的聚类的方法有三种，这三种算法包括是：GDBSCAN算 法、OPTICS算法、DENCLUE算法。其中OPTICS算法不是直接进行聚类，而是计算出 一个簇的次序，以方便自动聚类和交互聚类分析。DBSCAN算法是检验数据对象周围的 数据个数是否超过了用户规定的范围。DENCLUE算法是通过影响函数来判断空间密度 的方法，这就对处理高维数据非常方便有效，所以该方法对用户的参数的个数与种类非 常敏感。 2.3.32.3.3 基于层次的算法基于层次的算法 层次聚类算法1有两种不同的分解形式，分别是分裂和凝聚，它们的区别是聚类的 方向不同。其中分裂的层次算法也是一种自顶向下的聚类方法，顾名思义分裂的过程就 是将一个分裂为多个，一开始是将所有的数据放进一个初始的簇中，对这个簇进行分裂 ，每次迭代都会有一个更小的簇被分裂出来，最终结果是每个数据只单一的对应唯一的 一个簇结束。而凝聚的层次算法正好与分裂相反，是自底向上将小的簇聚类为大的簇， 在一开始的时候数据集中每一个数据对象为一个小的簇，逐步的与相邻的簇合并最终成 1515 为一个簇时终止。比较经常被使用的以层次为基础的的聚类算法有：BIRCH算法 、CURE算法 、ROCK算法、CHAMELEON算法等。 2.3.42.3.4 基于模型的算法基于模型的算法 基于模型的聚类分析算法1中的模型指的是数学模型，该算法是将数据集与某种算 法形成最佳的拟合，该算法能够利用统计学的方法，根据拟合的数据模型自动确定聚类 的个数K，该算法的鲁棒性很强。基于模型算法包括神经网络方法13和统计方法，神经 网络方法的思想是将每一个聚类描述为某个标本，通过度量函数的计算，将新的数据对 象分到相对应的标本中，最终完成聚类。而统计方法将每一个聚类结果通过概率描述的 方式表示出来，该方法比较适用于概念聚类。 2.3.52.3.5 基于网格的算法基于网格的算法 网格的算法14的基本思想是将数据空间划分为一定数量的格子，每次对数据的各种 操作就在格子中进行操作，该算法的处理难易程度只与网格的数目有关，这是网格聚类 算法的特点，常用的网格聚类算法有STING算法、WAVECLUSTER算法、CLIQUE算法 。STING算法的主要思想是先在分层的结构中存储网格的统计信息，这些统计信息是提 前计算出来的，数据对象的空间被分成许多格子，这些格子是按层次排列，高层的格子 信息被划为许多低层次的格子信息。CLIQUE算法是网格与密度结合的算法，它的工作 过程是将数据空间划分成不相关的网格，然后判断网格是否是密集的，判断标准是空间 中的每一个维度，再将判断出来的属于密集的网格进行求交的操作，并检查这些交集是 否连通良好，然后生成最小覆盖的簇。WAVECLUSTER算法是通过把数据比作信号来判 断，多维数据对应的是多维的信号，首先要做的也是将数据空间划分为网格，该算法利 用的是小波变换算法，使数据空间成为频域空间，在数据空间中利用某一函数对这些数 据做卷积，最终就能得到聚类结果。 2.4 常用的划分聚类算法的分析 划分的算法中最常用的就是K- 均值算法和K中心值聚类算法和基于它们的改进算法，分别详细介绍这两种算法，本章 的距离函数选取的是使用目前最常用的欧氏距离。 2.4.12.4.1 K-K-均值聚类算法均值聚类算法 1616 K-均值算法是利用算法迭代的思想15- 16，通过多次迭代改变不同簇的重心并将数据元素放到新的簇中，直到最终的聚类函数 收敛时停止即可得到最终的聚类结果。本算法的计算公式表示为： KM(X,C)=j=1xjcj|Xi-Wj|2(j=k) ； (2.13) Wj=xjcj(xi/|cj|),j=1,2,.,K；. (2.14) 这个定义的公式是假设每个数组只有唯一的数据型的属性值。该算法要用户期望的 聚类结果的组数作为输入值K，而每个簇内的初始数据是根据电脑随机分配的，也可以 依次取前K个元素，该迭代算法直到没有数据元素再被分到不同的组中时就是算法结束 的时候。KM算法的时间复杂性为0(xKM),x表示本次实验一共迭代了多少次，K是聚类所 生成的簇数，M是数据集的个数。因为该算法是定义在数值型的属性上的，对该数据集 假如还有其他属性是不能识别的，所以该算法所得的并不是全局最优解，而是局部的， 而且也不能处理其他形状的簇，只对凸形簇敏感。 K- 均值算法多次迭代的最终结果就是使目标函数KM（）最小值，通过该公式我们发现该 算法必须预先选好初始点，对初始点有很强烈的依赖性，如果该初始点选取不合适会影 响整个结果，这是该算法的一个缺点，可以改进的地方是用层次聚类等方法能够提前计 算出比较合适的初始点，再开始聚类。除此之外K- 均值算法还有其他缺点，它在时间上并不具备高效性。为了找到全局最优解，必须谨慎 选取初值和簇数，还可以计算簇内的方差，如果方差值很大就可以选择将该簇分裂为两 个簇来提高有效性，方差值过小而且比设置的最小值还要小就要考虑合并两个簇。 2.4.22.4.2 K-K-中心聚类法中心聚类法 已经介绍过KM算法对簇中心的选取非常敏感，选取不恰当会对聚类结果产生影响 ，这是KM算法的缺陷，如果有一个与簇中心点相距很远的点被选为初始点就会非常明 显的影响聚类质量。但是数据集中这种孤立点难免会出现，所以为了减少这种噪音数据 对聚类结果的影响，K-中心聚类算法17- 20出现，它与KM算法最大的区别是它是用最接近中心的那个数据对象来代表这个簇，而 不是用所有数据对象的均值来代表该簇，这样有效的避免了噪音数据的干扰，这也是K- 1717 中心聚类算法与KM算法唯一的区别，其他的步骤大相径庭，没有太大的区别。它所用 的目标函数公式是： J=j=1xWi|x-mj| (2.15) 其中Wi表示数据集中的人一个对象，mj表示该簇的中心，该算法除了不受孤立点影 响之外还不受数据输入顺序的影响。 K- 中心算法中的最早的PAM算法只适用小规模数据集聚类的算法，该算法的主要的思想是 电脑自动随机选出数据集中的K个数据对象为初始簇中的初始数据，然后根据距离函数 计算剩余数据跟各个初始数据的距离，并挑选出距离最小的初始簇，将该点归入到该簇 中，并计算新的簇代表，即迭代这些操作，持续到没有非代表的数据对象替换现在的簇 代表对象为止，从而实现中心点聚类算法的聚类。 PAM算法对大数据集不具备高效性，一种新的算法也被人们提出来，它就是CLAR A算法，该算法是对大的数据集进行N次的抽取小数据集样本，并依次对这些小的数据集 使用PAM算法，充分发挥PAM算法的优势，得到N个聚类结果，然后再从这N个聚类结 果中选择一个最优解作为最终整个数据集的结果。为了保证最终结果的可靠，抽样过程 中必须遵循随机性，除此之外还要掌握好抽样的规模大小，要适度，不能盲目抽取浪费 时间，把握效率和效果的充分平衡。 2.5 本章小结 本章详细介绍了聚类分析相关的基础知识，分析了它的定义，属性，表示方法，相 似性测量度，距离函数等方面。并对常用的五种聚类分析的方法：划分的方法、密度方 法、层次的方法、网格的方法、模型的方法，进行详细介绍，并简要叙述了各方法中常 用算法的基本思想和优缺点，最后着重详细的介绍了基于划分的两种聚类分析算法：K- 均值算法和K-中心值算法。 1818 3 K一均值聚类算法的研究 3.1 K-均值聚类算法介绍 k-means算法21-23是在1967年MacQueen第一次发现并提出来的，也被称为K- 平均或K- 均值聚类算法。为应用最广泛的一种聚类方法。主要特点为将每个群集子集内的所有数 据样本的平均值作为集群的代表点。算法的主要思想为通过采取一种反复的过程使数据 集被分成不同的类别，进而使用评价结果的聚类性能标准的功能来实现的，从而使产生 的每个群集的紧凑及独立。这种算法不适合处理离散属性，可是对于连续性具有较好的 集聚效应。 3.1.13.1.1 K K一均值聚类算法基本思想一均值聚类算法基本思想 K- means算法的工作原理可以总结为：首先，要从数据集中自动随机选择K个点作为初始聚 类中心，然后分别将每种样品计算其与集群的距离，样品分类的标准为其与聚类中心的 距离。利用距离函数计算出每一个新生成的所要作聚类的数据对象的平均距离值，并用 这个平均距离值来作为新的聚类中心，倘若相邻两次计算所得到的聚类中心点并没有发 生一点的改变，那么就能够证明样本调整过程就算完成了，也就是表示聚类准则函数目 前达到了收敛。本算法有一个明显的特点，就是在迭代过程中要对每个样本的分类结果 进行验证观察是不是正确。假如是不正确的，那么则需要对聚类进行调整。等所有的样 本调整完成以后，然后下一步就是对聚类中心的修改，从而开始进入下一次迭代过程中 去。倘若在某一次迭代算法过程中，所有样本的分类结果是正确的，无需调整，聚类中 心也没会出现有一点任何变化，那么这表明该聚类函数收敛，从而算法就结束了。 3.1.23.1.2 K K一均值聚类算法主要流程一均值聚类算法主要流程 输入：含有n个数据对象个数的数据库和所需要的簇的数目k。 1919 输出：k个簇。平方误差准则达到最小。 算法描述： （1） 从 n个数据对象中自动随机的选择 k 个对象来作为初始状态的的聚类中心； （2） 根据各个聚类对象的均值（即每个簇的中心点），来计算各个数据对象与所有中心对象 之间的距离。并以最短距离的为依据要求对相应的对象进行再一次的划分； （3） 重新计算各个发生了变化的聚类的均值（即距离中心对象）； （4） 循环过程（2）到（3）直至各个聚类不再发生变化为止。 算法步骤： 1.为各个聚类确定一个初始的聚类中心，这样就可以产生K 个初始聚类中心。 2.按最小距离的原则把样本集中的样本分配到最邻近聚类。 3.把各聚类中的样本均值规定为新的聚类中心。 4.重复执行步骤2、3直至聚类中心不再发生变化。 5.结束过程，得到K个聚类。