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

1、本科生毕业论文设计数据挖掘K-均值算法实现作者姓名：郝蓓指导教师：郭瑞强所在学院：数学与信息科学学院专业（系）：计算机科学与技术班级（届）：2013届计算机班二零一三年五月二日目 录中文摘要、关键字 11 绪论 31.1 本文研究的背景和意义 31.2 聚类分析国内外研究现状 51.3 本文所做的主要工作 72 聚类算法的分析与研究 82.1 数据挖掘简介 82.2 聚类的基本知识 82.2.1 类的定义及表示 92.2.2 聚类的相似度量方法 92.2.3 聚类间的距离测度函数 112.2.4 聚类分析的一般步骤 122.3 常用的聚类分析的方法介绍 132.3.1 基于划分的方法 132.

2、3.2 基于密度的方法 132.3.3 基于层次的算法 132.3.4 基于模型的算法 142.3.5 基于网格的算法 142.4 常用的划分聚类算法的分析 142.4.1 K-均值聚类算法 152.4.2 K-中心聚类法 152.5 本章小结 163 K一均值聚类算法的研究 173.1 K-均值聚类算法介绍 173.1.1 K一均值聚类算法基本思想 173.1.2 K一均值聚类算法主要流程 173.2 K-均值聚类算法的主要缺陷及分析 183.3 本章小结 194 K-均值聚类算法的实验 204.1 实验结果分析 204.2 本章小结 255 总结与展望 265.1 总结 255.2 展望

3、26参考文献 28英文摘要、关键字 31论文题目：数据挖掘K均值算法实现数学与信息科学学院 计算机科学与技术专业指导教师：郭瑞强作者：郝蓓摘要：随着互联网技术的迅速发展，现在的人们每一天都会面临例如文本、图像、视频、音频等各种数据形式，这些数据的数据量的大小是很惊人的。怎样能够很快的并且高效地从这些大量数据中挖掘提炼出它所蕴含的价值，成为现在人们特别关注并且需要马上解决的问题。数据挖掘(Data Mining，DM)正是因为这个才慢慢诞生出来。数据挖掘经过一段时间的迅猛发展，诞生出了大量的理论结果和现实使用成果，它提供了许多工具和卓有成效的方法来解决问题。数据挖掘中有一项是很重要的研究领域，那

4、就是聚类分析，这是一种对数据进行按照不同的依据将数据进行分组或者将数据进行划分的方式。聚类无论在生物科学研究，还是在商务贸易中、图像分析处理、网页内容分类等其他日常生活的领域都得到了很好的应用。根据使用的数据类型、使用的功能的不同、聚类需求的不同，目前的聚类算法大概有以下几种：基于划分的算法、基于层次的算法、基于密度的的算法、基于模型的算法以及基于网格的算法。在这之中，基于划分的K-均值聚类算法是目前研究最成熟传统经典的算法。K-均值算法的应用领域特别广泛，覆盖范围涉及语音频率压缩还有图像及文本聚类，另外在数据预处理和神经网络结构的任务分解等也发挥其重要用途。本文所做的工作有：本文第一部分：详

5、细介绍了本次论文研究的背景和目的，以及所选题目的考虑思路，还有在当前国际形式下，聚类分析在国际上的地位及国内外研究成果综述，最后介绍了本论文算法实现的内容和论文整体布局安排。第二部分：首先详细描述了数据挖掘的来源发展还有它的概念定义，下面主要介绍聚类分析，包括聚类的基本概念原理等基础性知识，介绍了聚类算法的内部特性，详细描述了几种目前聚类分析的方法，总结比较各个方法的特点及其长短处。最后对本论文所研究的基于划分的聚类算法进一步讨论都有哪几种算法。第三部分：这是本论文的重点，本论文所要讨论的K-均值算法，从它的概念基本思想算法流程等方面对K-均值算法进行详细系统的介绍，并且详细分析了它的优缺点。

6、K-均值算法对初始值的选取比较敏感和对数据的输入顺序不同也会影响聚类等问题，所以本文针对该问题进行了验证，通过实验证明了这两个因素对聚类结果会有哪些影响。实验表明，K-均值算法对初始值和数据输入顺序很敏感，但是这两个对聚类结果影响的方面不同。本文通过六个实验结果分析得出，改变初始点，对聚类结果的影响不大，只是会改变迭代次数，而且选取初始的连续的几个数据为初始点迭代次数最少，虽然中间间隔的几个数据作为初始点也出现了最小的迭代次数，但这对数据集来说有太多的不确定性，所以还是选择最开始那几个数据为数据聚类初始点；对于改变数据集的输入顺序，聚类结果与之前的有很大的改变，实验结果说明输入顺序不同既影响了

7、聚类结果也影响了迭代次数。通过这些结论为以后用户使用K-均值算法提供了很好的帮助，也为该算法的改进提供了参考。关键词：数据挖掘 聚类分析 K-means算法 实验验证1 绪论1.1 本文研究的背景和意义近年来，随着科技的进步以及互联网的普及，以计算机为代表的信息技术有了巨大发展，人们产生、发现、整理、利用数据的能力不断提升。到目前为止，数据在我们的日常生活中无处不在，它广泛应用于科学研究、政府日常办公、军事力量分析、企业管理电子商务、统计学分析等等各个领域。虽然我们知道这些数据的重要性，但是随着时间越来越久，我们积累的数据量是不断地在加大，相应的我们分析处理这些数据的能力也要增加，但是后来数据

8、量的增长速度已经超出了我们的能力范围，所以我们必将面临的严峻问题是数据爆炸。难道真的没有办法可以很科学的处理这些海量数据吗？事实并非如此，人类的智慧是无穷的，人们已经通过理性的思维和恰当的技术，将这些海量数据充分利用，使它们成为社会发展进步的强大的力量源泉。目前，广泛使用的数据库系统虽然具有高效率的录入所有数据查询所需数据统计数据类别等功能，但是并不能发现这些海量数据中蕴藏的内部关联规则，也无法从当前现在的数据情况去预测未来的数据内容的发展趋势，更不可能做出决策判断，使得人们逼不得已去面对“数据丰富而知识缺乏”的困镜1。所以数据挖掘（Data Mining）技术因此就慢慢诞生了，并且快速的发展

9、应用社会的各个领域，表现了其坚韧的生命力与适应力。该技术就是从“数据矿山”中发现“知识的宝藏”。数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提取发掘出来隐含在当中的、人们在这之前不是特别了解的、但又是隐含有用的信息内容和知识内容的非平凡过程2 。原始的数据类型可以是多样的，比如数据库中的数据结构化数据类型，那些图像图形资料及文字类资料是半结构化的数据类型，当然也包括网络互联网上的那些数据我们称它们为半结构化的数据类型。我们可以通过归纳演绎等方法来发

10、现知识，也可以用统计学的数学或非数学的方法总结数据来得到我们想要的信息。这些我们得到的信息内容和知识内容的过程就是挖掘的一个过程，我们把挖掘的知识可以应用到我们的生活中，包括未来决策规划、优化信息管理方案、调整控制模式、改进查询方案等等来更好的维护和利用我们现有的数据。所以数据挖掘涉及到的学科很广泛，它是各个学科的交叉，它用到了人工智能数学统计学与数据库等技术来实现它自己的目的，需要这些领域的工程技术人员来共同配合，尤其是数据库管理人员。现在的数据挖掘技术已经开始走向科技产品研发及技术应用，不再是之前的单纯的搞一下研究而已，我国市场经济制度在不断地完善与发展，经济实力也在不断进步，现在我们的社

11、会对数据挖掘技术的需求越来越强烈，目前我国很多的有眼光的软件企业已经将目光聚集于此，来研发更多适应市场需求的数据挖掘软件产品，随着市场日趋成熟，广大消费者的应用需求也是慢慢变大，相信将来会有更多成熟的中国数据挖掘软件面向市场。聚类分析是数据挖掘的一个发现信息的方法，已经被人们深入的研究了很长时间，主要的是对基于距离的聚类分析的研究。聚类是一种无监督的学习，分类正好与它相反，分类是一种有监督的学习，聚类主要是划分无标记的对象，使这些无标记的对象变的有意义，对预先定义的类与带类标记的训练实例不具有依赖性。所以聚类分析在我们的日常生活中的应用范围非常广泛： 在商业上，聚类可以根据消费者数据库里面所记

12、录的数据信息，对消费者进行划分，根据各个消费者的特征，以帮助市场营销员按照市场需求及时调整货物的摆放次序等一系列营销计划的实施； 在社会学中，聚类用来发现目前社会结构组成中潜在的社会结构； 在网络挖掘中对互联网上批量的数据信息进行有效的划分与分类，实现信息的有效利用，对数据信息检索效率方面有显著提高； 在生物信息学中，在大量的基因群中发现功能相似的基因组，对基因因功能不同进行划分对其固有的结构特征进行分析，来更好的为我们的医学发展提供有利条件； 在空间数据库领域，聚类分析能对相似地理特征区域及它们的人和环境的不同特征进行识别，来研究地域文化提供条件。本文主要选择聚类分析中基于划分的K-mean

13、s算法并实现它的应用，对数据集的数据进行聚类分析。本文在实现它的基础上，对该算法对初始值和数据输入顺序敏感的问题进行了验证，通过六次试验，分别对这个两个方面进行验证，并对聚类结果进行分析比较，从而得出结论。本文通过对不同输入条件的实验验证，得出K-均值算法对初始值得选择和数据输入顺序是很敏感的结论，通过实验结果可得出在今后使用K-均值算法时我们应该怎样避免其聚类出不准确的聚类结果和今后改进算法应该改进的方向等问题。1.2 聚类分析国内外研究现状目前，国内对于数据挖掘聚类分析的研究的集中部门还是科研单位和各大高校，国内还没有公司企业专门从事聚类分析的研究，相对于外国来说起步较晚。各大科研机构与高

14、校对聚类的研究主要是对数据集聚类算法的设计并实现，以研究出来的算法为基础对算法改进。目前人们已经在统计分析软件中应用一些聚类分析工具，如SAS等软件。为大型的数据库寻求有效的聚类分析方法是目前聚类分析的主要研究工作，目前研究方向包括以下几个方向：（1）可伸缩性：目前的聚类算法针对小型数据库，数据量是几百范围内的，对于有很庞大数据量的数据库会造成结果的不稳定性，可伸缩性强的算法就亟待的研发出来。（2）属性不同情况下的处理能力：现在开发出来的聚类算法所针对的数据类型都是数值型，但实际上的聚类类型的信息是不确定的，如二元数据、序数型的、分类型的等或者是所已知的各种数据类型的混合。（3）聚类形状：在欧

15、几里得距离的基础上发现所得的簇的形状是球状簇，它们有相近的距离与密度，形成一个簇，但是我们更希望能够有一种算法实现各个不同形状的簇。（4）决定结果的输入参数：聚类算法的实现过程中相当多的是必须让用户提前输入想要聚类出来的簇数K，当前的算法对这些K的值是相当敏感的，大型的数据流对这些要求很严格，对结果的影响很明显，使用户在输入时加大了分析的工作难度，很难控制。（5）输入数据的顺序问题：有的聚类算法对输入数据的顺序是有要求的，不同的输入次序会有不同的聚类结果，这就特别需要对数据顺序不敏感的算法开发出来，更好的适应人们的要求。（6）高维数据的处理：含有若干维数据属性的数据库是很常见的，但是擅长处理两

16、维或三维的聚类算法才是目前成熟的应用的算法，一旦高维数据需要聚类处理，这就是一个难题，这就需要算法有很强的实用性。（7）污染数据的发现：数据是一个不确定而且无限性的群体，我们不能保证数据集中的数据是完全集中的，难免会有个别的孤立点造成污染数据，影响整个结果，应该开发出能智能识别这些孤立点的数据的算法，来优化聚类结果，目前大部分是通过对目前算法进行改进来实现。（8）有约束条件的聚类：实际的聚类情况是有很多限制的条件的，在实现这些聚类时，既要按约束条件又要按聚类要求实现，是很有压力和挑战的一项任务。（9）可使用性和可解释性：大多情况下的聚类结果，对于客户来说都希望它们简单易懂，一目了然，所以我们要

17、优化聚类结果界面的研究，选择适合每个客户需求的聚类方法来满足他们的需求。同时聚类分析算法主要着手于以下的几个问题的解决3：（1）初始值的选取及输入顺序对结果有何影响在数据挖掘的学科范围内寻找最优解的过程是通过迭代不同的初始值实现，但是这个办法不是很可靠，它的意思就是表示不能百分之百的确定找到最优解。其实寻找最优解就是在优化原来的聚类的结果，通过重复聚类找到所设计的目标函数的最优解，但是这个目标函数一般都不是有最值的函数，所以它的最小值并不是很容易确定，因为它并不唯一，有可能找到的这个只是局部最小值，而不是全局最小，所以这种非完全单调函数的全局最小值的查找是目前最急着等待解决的问题。（2）以小波

18、变换为基础的聚类算法因为当前主要是对均值算法与模糊算法的研究改进而得到的研究成果，这些研究成果使得目前的聚类分析算法提高了它的性能属性。小波变换聚类算法同样符合好的聚类算法的各项要求，目前对小波聚类的研究还有很大程度的空白，如果花大的精力进一步研究会有更加深入的突破。（3）算法的效率改善提高的问题聚类的效率问题是目前一个很棘手的问题，因为人类在进步，数据量会越来越庞大，应该增强目前聚类算法对更大数据库的处理能力，即增量聚类，使聚类算法在聚类的数量上有更好的弹性，尽量减少在工作时对庞大数据库的扫描次数，进一步提高它的工作效率。（4）数据库类型目前，基于聚类算法的数据库比较单一，仅仅包括关系或事务

19、数据库，应该着眼于其他数据库类型应用算法的研究，比如面向以属性为内容的数据库、以文本为内容的数据库、各个不同时态为内容的数据库、地理数据库多维数据库等的算法开发，这是一项非常艰巨而且有意义的研究任务。聚类分析中的算法有很多种，详细分析比较了各个算法的优缺点，本文着重介绍了K-均值算法，分析它本身的算法优点与不足，并对算法实现，着力于对影响该算法聚类结果的不同初始条件进行验证，以更好在以后的实际应用中使用它。K-均值算法是聚类分析最常用的算法之一。K-均值算法的应用范围非常广泛，因为它的操作简单，适合处理庞大的数据集，但是它同时也暴露出自身的不足，如易陷入局部最优解的结果里面、需要用户提前输入参

20、数、发现簇的形状比较单一等，已经有很多专家对这些问题进行了改进，文献4作者通过最大最小距离和DBI聚类指标解决了K-均值算法对初始值K的选择问题，能够确定出最佳的聚类数目。文献5的作者用K-均值算法与层次聚类算法进行混合出一种新的聚类算法，充分发挥了层次聚类的精确性和K-均值的高效性。文献6的作者对遗传算法提出一种改进算法，基于比变长编码，利用这种算法与K-均值结合解决了对初值选择的敏感问题等等，目前已经有很多被发表出来的对K-均值的改进的算法。1.3 本文所做的主要工作首先对数据挖掘这门学科的背景和发展前景做了分析，本文主要研究数据挖掘的聚类分析，所以介绍了聚类分析目前国内外的地位与发展方向

21、，以为下文展开作铺垫，这方面阅读了许多聚类相关文献，许多新的聚类分析方法先后被各国的科研工作者提出并应用，这些在本文有详细列举。除此之外本文对聚类分析中的常用的五种方法做了简要介绍，列举了五种方法中目前比较常用的算法，并分析了每个算法的适用领域与基本思想。本文着重讨论的是基于划分的聚类分析方法中的K-means方法，对KM方法进行了详细的介绍，包括基本思路工作流程等，本文通过分析KM算法的缺点，通过实验验证了对初始点的选取和数据输入顺序敏感的验证，通过两个实验分别得出这两个因素对聚类结果产生怎样的影响并得出结论，实验表明初始点不同只是影响聚类迭代的次数，对聚类结果的影响不明显，只是少数数据的聚

22、类结果发生改变；数据输入顺序的不同，不仅会改变数据聚类的迭代次数，也会让聚类的结果发生明显改变。2 聚类算法的分析与研究2.1 数据挖掘简介数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提取发掘出来隐含在当中的、人们在这之前不是特别了解的、但又是隐含有用的信息内容和知识内容的非平凡过程2。其实数据挖掘就是通过各种分析算法工具从巨大数量的数据中挖掘所需要的数据与模型两者关系的一个过程，可以通过得到的这些关系，对未来的数据与模型关系进行预测。通常根据不同

23、用户的需求，和他们所提供的数据类型，数据挖掘的数据库的类型也是不一样的，通常包括关系数据库类型、事物数据库类型、多媒体数据库类型等。其中关系数据库实际上就是使用数学学科上的方法来处理数据之间的关系，我们生活中随处可见关系数据库，比如交通部的车辆数据库、银行的客户记录等。事务数据库一般是将几个事务数据库的数据一起导入到只能用来读数据的数据挖掘库中，做成一个数据集市，然后把其作为挖掘的对象。多媒体数据库顾名思义就是包含大量视频音频文件，模式识别技术被用于该领域。数据挖掘包含很多类别，包括分类分析、聚类分析、关联分析孤立点分析等其他分析。其中分类分析包括分类和回归，分类分析是一种预测模型，通过现有数

24、据预测将来的数据，如果预测的数据是离散的即叫做分类，如果是连续的即叫做回归。聚类分析则是将大量数据中形似的数据分到一组，一个数据集大概包括几组数据，聚类没有明显的属性目标，而是挖掘隐藏的属性来进行聚类，聚类分析中的基于划分的K-均值算法是本文的研究对象。关联分析分析数据与数据之间关联关系还有它与其他数据的派生关系。孤立点分析是针对那些远离数据集的点，对不同的客户，别人的孤立点可能对于他来说是很重要的信息，孤立点分析就是对这些远离数据集中心的数据信息进行挖掘。孤立点的研究是将来我们必须重点研究的领域，因为几个孤立点就会影响全局的聚类结果，这是不容忽视的。2.2 聚类的基本知识2.2.1 类的定义

25、及表示（1）类的定义要想聚类操作首先要明确类的定义。世界错综复杂事物存在的方式也不尽相同，所以类的定义并不唯一。以下将列举出常用的类的定义：设：含有K个样本的集合A，Mi是其中的某个样本，T和C是范围阀值，那么：如果任意的Mi，Mj A，都有D（Mi，Mj）T，则A称为一类；（2）类的表示；聚类的表示方法也是有不同的，一般用以下三种： 自然语言表示：直接用自然语言直观的描述出这些数据是属于哪个簇的； DNF表示：用析取范式表示明了、简洁、易懂。例如：(36<PT<70)V(345<AM<1234)； 聚类谱系图：目前使用的聚类算法输出结果大部分都是这种，这种方法表示非常

26、详细，它能表示出这些样本自成一类的所有中间情况，而且都会有各个类的平台高度，我们叫这种图为标度聚类谱系图。2.2.2 聚类的相似度量方法聚类分析按照数据样本性质的相似程度的大小进行划分，确定这些相似程度的大小必须有一个准则来判断它们的程度大小，这个判断准则叫做相似度方法，主要是在距离和相似系数的不同。距离：样本点之间的相似性我们就用某种距离函数表示，距离近的表示样本点相似，具体计算时可以把样本看做有M个属性的变量，即这个样本就是在一个M维的空间中的一个点。距离函数：设P是所有样本集合的集合名称，如果满足： 正定性D(M，N)0，if MND(M，N)=0，if M=N 对称性D(M，N)=D(

27、M，N) 三角不等式D(M,N)+D(N，L)D(M，L) 我们称它们为距离函数。聚类分析中经常使用的的距离函数有： 明氏(Minkowski)距离 (2.1)当m取1时，则表示绝对距离，当m取2时就表示欧式(Euclid)距离，当m取无穷大时就表示切比雪夫(Chebyshev)距离。 如：欧氏距离 (2.2) 马氏(Mahalanois)距离 (2.3) 其中 S 是由样品集N（）算得的协方差矩阵： (2.3.1)样品聚类一般情况下被叫做Q型聚类，是以距离矩阵为出发点的。明氏距离改进后得到了马氏距离，所有的线性变换对于马氏距离来说是不变的，多重相关性马氏距离也把它克服了。 方差加权距离 (2

28、.4)其中 . (2.4.1)在聚类分析中除了对样本点聚类，对特征变量也要根据实际情况进行聚类，所以对于特征向量而言，不必非用距离函数来确定它们的相似测度，还可以用相似系数。相似系数：当对含有k个指标的变量的数据集进行聚类时，就用相似系数来作为判断所有变量之间的相似程度（或关联程度）的标准指标。一般地，若表示Cab变量Xa,Xb之间的相似系数，应满足：1）| Cab|1且Cab=1；2）Cab=1或Cab=1Xa=CXb；3）Cab=Cba；Cab的绝对值越与1接近，越说明变量Xa,Xb之间的关联性越大。相似系数中相关系数和夹角余弦是目前最经常被使用的。（1）相关系数变量之间的相关系数我们可以

29、这样定义为：. (2.5)实际上，只是变量之间的观测值之间的相关系数而已。相关系数表示两个向量的相关程度是多少。（2）夹角余弦变量的观测值 ，其夹角余弦我们可以这样定义为： (2.6)变量聚类一般情况下被叫作为 R 型聚类。一般R 型聚类，相似系数矩阵 C 是数据集聚类的出发点，相似系数矩阵不仅能够使用相关矩阵，而且能够使用夹角余弦矩阵。2.2.3 聚类间的距离测度函数对于不同的两个类，如果他们之间距离可定义，那么就用如下几种定义方式来定义他们的距离：（1）最短距离法：顾名思义它表示两个类中的元素，相离最近的两个元素的距离来表示这两个类之间距离，公式表示为： (2.7)（2）最长距离法：跟最短

30、距离法类似，表示两类之间距离的是两类中距离最远的元素，公式为： . (2.8)（3）类平均法：求出两个类中任意两个数据的平均距离，用求出来的这个数据来表示这两个类的平均距离，这就是类平均法，我们可以用下面的公式来表示： (2.9)（4）重心距离法：它的定义表示两个类之间重心相邻的距离为类距离,公式表示为： (2.10)其中类的重心公式为： （也就是各元素的平均向量之间的距离）（5）离差平方和距离：用类中各元素的离差平方和的总和得到两个类Gr和Gk的直径分别是Dr和Dk,类Gr+k=Gr Y Gk,用这种方法尽量让类间的离差平方和大，而类内部的元素间的值小，公式表示为： . (2.11)其中类直

31、径：有的把类中相距最远的两个元素的距离作为直径，也有的将类中各元素指标的离差平方和的和作为直径，离差平方和的计算公式为： (2.12)2.2.4 聚类分析的一般步骤聚类分析的步骤大体可以分为四步9-10：（1）数据的预处理：就是在拿到一个数据集的时候，首先分析对这个数据的聚类分析要求，并根据这个要求对现在的数据集做降维或者特征标准化等初步的处理操作，也就是去掉没用的特征值。（2）特征的选择及提取：对于第一步得到的信息，进一步细分，就是将预处理后的信息再选择最有效的特征，并将选择出来的特征用向量的方法转换成新的有效突出特征，以供聚类分组时作为分组判定的条件。（3）聚类：这就要用到前面的相似性度量

32、函数，选择距离函数还是选择相似系数等方法来度量选出来的有效特征值的相似度，进而完成对该数据集的聚类分析。（4）评估结果：结果进行分析，看有没有完成预定的要求，并根据聚类方法的评价标准对结果进行科学评估，即聚类分析的九个方面的要求是否满足，然后根据评估结果判断是否对本次的分析过程进行改进，以及怎样改进。2.3 常用的聚类分析的方法介绍目前聚类分析算法的应用技术日趋成熟，已经有很多的聚类算法被提出来，但是算法种类增多，同时这些算法的融合会越来越明显，使得各种算法的界限不明显，但是目前大家默认的有五种划分方法,分别是：以划分为基础的算法(Partitioning Methods)、以密度为基础的算法

33、(DensitybasedMethods)、以层次的为基础的算法(HierarchicalMethods)、以模型为基础的算法(Modelbased Methods)、以网格为基础的算法(Gridbased Methods)。2.3.1 基于划分的方法划分算法11的基本思想就是通过迭代的方法将含有M个数据对象的数据集分成K个簇。具体步骤是，用户首先给定所要划分的簇的个数K，算法先进行初步划分为K组，然后用迭代的方法反复再进行分组，每次新得到的分组比前一次要优化，是否优化的判定标准是同组数据之间以及不同组数据之间的相似程度，同组相似程度越大组间相似程度越小分组越优化，目前常用的算法有K-mean

34、s算法、K-medoid算法以及以它们为基础的算法的各种改进。以划分为基础的聚类算法将在后面的章节做重点介绍。2.3.2 基于密度的方法基于密度的算法12与其他的算法最大的不同在于不是以元素间的距离作为判断标准，而是根据数据对象的分布密度来判断，正因为如此该算法有助于发现数据集中的噪声数据，减少噪声数据对聚类结果的影响，所以密度的方法可以对任意形状的簇聚类，基本思想是将密度较大的区域识别出来，形成连在一起的密度域，并将他们归为一类。目前比较传统的的以密度为基础的聚类的方法有三种，这三种算法包括是：GDBSCAN算法、OPTICS算法、DENCLUE算法。其中OPTICS算法不是直接进行聚类，而

35、是计算出一个簇的次序，以方便自动聚类和交互聚类分析。DBSCAN算法是检验数据对象周围的数据个数是否超过了用户规定的范围。DENCLUE算法是通过影响函数来判断空间密度的方法，这就对处理高维数据非常方便有效，所以该方法对用户的参数的个数与种类非常敏感。2.3.3 基于层次的算法层次聚类算法1有两种不同的分解形式，分别是分裂和凝聚，它们的区别是聚类的方向不同。其中分裂的层次算法也是一种自顶向下的聚类方法，顾名思义分裂的过程就是将一个分裂为多个，一开始是将所有的数据放进一个初始的簇中，对这个簇进行分裂，每次迭代都会有一个更小的簇被分裂出来，最终结果是每个数据只单一的对应唯一的一个簇结束。而凝聚的层

36、次算法正好与分裂相反，是自底向上将小的簇聚类为大的簇，在一开始的时候数据集中每一个数据对象为一个小的簇，逐步的与相邻的簇合并最终成为一个簇时终止。比较经常被使用的以层次为基础的的聚类算法有：BIRCH算法 、CURE算法 、ROCK算法、CHAMELEON算法等。2.3.4 基于模型的算法基于模型的聚类分析算法1中的模型指的是数学模型，该算法是将数据集与某种算法形成最佳的拟合，该算法能够利用统计学的方法，根据拟合的数据模型自动确定聚类的个数K，该算法的鲁棒性很强。基于模型算法包括神经网络方法13和统计方法，神经网络方法的思想是将每一个聚类描述为某个标本，通过度量函数的计算，将新的数据对象分到相

37、对应的标本中，最终完成聚类。而统计方法将每一个聚类结果通过概率描述的方式表示出来，该方法比较适用于概念聚类。2.3.5 基于网格的算法网格的算法14的基本思想是将数据空间划分为一定数量的格子，每次对数据的各种操作就在格子中进行操作，该算法的处理难易程度只与网格的数目有关，这是网格聚类算法的特点，常用的网格聚类算法有STING算法、WAVECLUSTER算法、CLIQUE算法。STING算法的主要思想是先在分层的结构中存储网格的统计信息，这些统计信息是提前计算出来的，数据对象的空间被分成许多格子，这些格子是按层次排列，高层的格子信息被划为许多低层次的格子信息。CLIQUE算法是网格与密度结合的算

38、法，它的工作过程是将数据空间划分成不相关的网格，然后判断网格是否是密集的，判断标准是空间中的每一个维度，再将判断出来的属于密集的网格进行求交的操作，并检查这些交集是否连通良好，然后生成最小覆盖的簇。WAVECLUSTER算法是通过把数据比作信号来判断，多维数据对应的是多维的信号，首先要做的也是将数据空间划分为网格，该算法利用的是小波变换算法，使数据空间成为频域空间，在数据空间中利用某一函数对这些数据做卷积，最终就能得到聚类结果。2.4 常用的划分聚类算法的分析划分的算法中最常用的就是K-均值算法和K中心值聚类算法和基于它们的改进算法，分别详细介绍这两种算法，本章的距离函数选取的是使用目前最常用

39、的欧氏距离。2.4.1 K-均值聚类算法 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个元素，该迭代算法直到没有数据元素再被分到不同的组中时就是算法结束的时候。

40、KM算法的时间复杂性为0(xKM),x表示本次实验一共迭代了多少次，K是聚类所生成的簇数，M是数据集的个数。因为该算法是定义在数值型的属性上的，对该数据集假如还有其他属性是不能识别的，所以该算法所得的并不是全局最优解，而是局部的，而且也不能处理其他形状的簇，只对凸形簇敏感。K-均值算法多次迭代的最终结果就是使目标函数KM（）最小值，通过该公式我们发现该算法必须预先选好初始点，对初始点有很强烈的依赖性，如果该初始点选取不合适会影响整个结果，这是该算法的一个缺点，可以改进的地方是用层次聚类等方法能够提前计算出比较合适的初始点，再开始聚类。除此之外K-均值算法还有其他缺点，它在时间上并不具备高效性。

41、为了找到全局最优解，必须谨慎选取初值和簇数，还可以计算簇内的方差，如果方差值很大就可以选择将该簇分裂为两个簇来提高有效性，方差值过小而且比设置的最小值还要小就要考虑合并两个簇。2.4.2 K-中心聚类法已经介绍过KM算法对簇中心的选取非常敏感，选取不恰当会对聚类结果产生影响，这是KM算法的缺陷，如果有一个与簇中心点相距很远的点被选为初始点就会非常明显的影响聚类质量。但是数据集中这种孤立点难免会出现，所以为了减少这种噪音数据对聚类结果的影响，K-中心聚类算法17-20出现，它与KM算法最大的区别是它是用最接近中心的那个数据对象来代表这个簇，而不是用所有数据对象的均值来代表该簇，这样有效的避免了噪

42、音数据的干扰，这也是K-中心聚类算法与KM算法唯一的区别，其他的步骤大相径庭，没有太大的区别。它所用的目标函数公式是：J=j=1xWi|x-mj| (2.15)其中Wi表示数据集中的人一个对象，mj表示该簇的中心，该算法除了不受孤立点影响之外还不受数据输入顺序的影响。 K-中心算法中的最早的PAM算法只适用小规模数据集聚类的算法，该算法的主要的思想是电脑自动随机选出数据集中的K个数据对象为初始簇中的初始数据，然后根据距离函数计算剩余数据跟各个初始数据的距离，并挑选出距离最小的初始簇，将该点归入到该簇中，并计算新的簇代表，即迭代这些操作，持续到没有非代表的数据对象替换现在的簇代表对象为止，从而实

43、现中心点聚类算法的聚类。PAM算法对大数据集不具备高效性，一种新的算法也被人们提出来，它就是CLARA算法，该算法是对大的数据集进行N次的抽取小数据集样本，并依次对这些小的数据集使用PAM算法，充分发挥PAM算法的优势，得到N个聚类结果，然后再从这N个聚类结果中选择一个最优解作为最终整个数据集的结果。为了保证最终结果的可靠，抽样过程中必须遵循随机性，除此之外还要掌握好抽样的规模大小，要适度，不能盲目抽取浪费时间，把握效率和效果的充分平衡。2.5 本章小结本章详细介绍了聚类分析相关的基础知识，分析了它的定义，属性，表示方法，相似性测量度，距离函数等方面。并对常用的五种聚类分析的方法：划分的方法、

44、密度方法、层次的方法、网格的方法、模型的方法，进行详细介绍，并简要叙述了各方法中常用算法的基本思想和优缺点，最后着重详细的介绍了基于划分的两种聚类分析算法：K-均值算法和K-中心值算法。3 K一均值聚类算法的研究3.1 K-均值聚类算法介绍k-means算法21-23是在1967年MacQueen第一次发现并提出来的，也被称为K-平均或K-均值聚类算法。为应用最广泛的一种聚类方法。主要特点为将每个群集子集内的所有数据样本的平均值作为集群的代表点。算法的主要思想为通过采取一种反复的过程使数据集被分成不同的类别，进而使用评价结果的聚类性能标准的功能来实现的，从而使产生的每个群集的紧凑及独立。这种算

45、法不适合处理离散属性，可是对于连续性具有较好的集聚效应。3.1.1 K一均值聚类算法基本思想K-means算法的工作原理可以总结为：首先，要从数据集中自动随机选择K个点作为初始聚类中心，然后分别将每种样品计算其与集群的距离，样品分类的标准为其与聚类中心的距离。利用距离函数计算出每一个新生成的所要作聚类的数据对象的平均距离值，并用这个平均距离值来作为新的聚类中心，倘若相邻两次计算所得到的聚类中心点并没有发生一点的改变，那么就能够证明样本调整过程就算完成了，也就是表示聚类准则函数目前达到了收敛。本算法有一个明显的特点，就是在迭代过程中要对每个样本的分类结果进行验证观察是不是正确。假如是不正确的，那

46、么则需要对聚类进行调整。等所有的样本调整完成以后，然后下一步就是对聚类中心的修改，从而开始进入下一次迭代过程中去。倘若在某一次迭代算法过程中，所有样本的分类结果是正确的，无需调整，聚类中心也没会出现有一点任何变化，那么这表明该聚类函数收敛，从而算法就结束了。3.1.2 K一均值聚类算法主要流程输入：含有n个数据对象个数的数据库和所需要的簇的数目k。输出：k个簇。平方误差准则达到最小。算法描述：（1） 从 n个数据对象中自动随机的选择 k 个对象来作为初始状态的的聚类中心； （2） 根据各个聚类对象的均值（即每个簇的中心点），来计算各个数据对象与所有中心对象之间的距离。并以最短距离的为依据要求对

47、相应的对象进行再一次的划分； （3） 重新计算各个发生了变化的聚类的均值（即距离中心对象）； （4） 循环过程（2）到（3）直至各个聚类不再发生变化为止。算法步骤： 1.为各个聚类确定一个初始的聚类中心，这样就可以产生K 个初始聚类中心。 2.按最小距离的原则把样本集中的样本分配到最邻近聚类。3.把各聚类中的样本均值规定为新的聚类中心。4.重复执行步骤2、3直至聚类中心不再发生变化。5.结束过程，得到K个聚类。3.2 K-均值聚类算法的主要缺陷及分析主要优点：（1）作为解决聚类问题而出现的一种传统经典算法，具有简单、快速的特点。对于较大数据集的聚类分析来说，该算法相比较而言是可伸缩和高效率的。

48、因为它的时间复杂度是0 (n k x ) 。其中, n 是所有对象的个数, k 是所需要的簇的个数, x 是迭代发生了多少次。通常情况下有k <<n 且x <<n 。（2）当结果簇是密集的，而且簇与簇之间的区别较为明显时, 它的效果比较较好。主要缺点：（1）K-均值算法只是在簇的平均值已经提前被定义了的情况时才能被使用，而这个前提对于处理符号属性的数据并不适用。在 K-means 算法中，首先要根据初始的聚类中心来确定一个适合的初始划分，接着要对初始划分开始进行进一步的优化操作。聚类结果对这个初始点的选择是相当敏感的。倘若初始值选择的不合适很可能造成不能得到准确的聚类结

49、果的后果。这也是K-means算法目前存在的一个主要问题。对于该问题的解决，许多算法采用遗传算法GA，例如可以采用遗传算法GA来进行初始化操作，而且内部聚类准则被当做评价指标。（2）必须事先给出k值（想要生成的簇的个数）。并且对初值很敏感：不同的初始K值，也许将导致不同结果。在 K-means 算法中K值是要求提前必须给定的，但是这个值的选择是相当难以估计的。实际情况下大部分时候提前是并不能确定给定的数据集应划分成多少个类别才最适合这个数据集。这也是该算法的一个缺点。有的算法是通过采用类的自动识别它的初始数据集的分类和合并来得到较为合适聚类的簇数。例如 ISODATA 算法。对 K-means

50、 算法中的聚类数目K 值的确定有很多方法，有的是根据方差分析理论结合应用混合 F 统计量来得到最合适分类数，并且采用模糊划分熵的方法来验证其合理性。有的使用一种结合了全协方差矩阵的RPCL算法，而且逐步删去那些仅仅包含很少数据量的训练数据的类。还有的使用一种名为次胜者受罚的学习竞争规从而自动决定类的合理数目。它的思想为：对于每个输入来说，不但获胜单元的权值被加以修正以便适应输入值。而且对于次胜单元则采用惩罚的方法以使其远离输入值。（3）该算法对“噪声数据”以及孤立的点数据是相当敏感的，即使少量的该类数据也可以对平均值产生相当大的影响。（4）从 K-means 算法流程中可以清楚的看到，该算法的

51、实现原理要求必须不断地对样本进行分类，并且必须不断地计算更新调整后的新的聚类中心。所以当数据量很大时，算法的时间复杂度是非常大的。因此需要对算法的时间复杂度时刻进行关注、审查以满足时间等的要求。例如可以利用一定的相似性准则来排除一些近似的聚类中心的侯选集。3.3 本章小结本章主要是针对K-均值算法作了系统的分析，介绍了它的基本定义、基本思想、主要流程，最后详细分析了该算法在实际应用中的优点和不足。K-均值算法是数据挖掘聚类划分算法中最基本的算法，虽然它本身在实际应用的过程中存在不足，但是我们不能忽视它本身对数据集聚类的优点，在有的实践应用中也取得了理想的效果，很多的算法也是以此为依据进行改进的

52、，主要是对距离计算的改进，如P-CLUSTER算法，就是基于K-均值算法的一种改进，是启发知识来判断该数据集聚类对象M的最近的簇中心是否改变。4 K-均值聚类算法的实验4.1 实验结果分析 实验一：本文测试采用的是从数据堂下载的c-fat500-10.txt数据集，对K-均值算法进行了验证，经过实验分别对150个数据的数据集选取不同初始点分别进行聚类，验证不同的初始条件对最终聚类结果的影响情况，得到的聚类结果分别如下图：令前三个数据p1p2p3作为初始聚类中心，如图4.1所示：图4.1 初始点为第1 2 3序号的聚类图把第p4p5p6个数据作为初始聚类中心，得到的聚类结果如图4.2所示：图4.

53、2 初始点为第4 5 6序号的聚类图把第p100p101p102个数据作为初始聚类中心，得到的聚类结果如图4.3所示：图4.3 初始点为第100 101 102序号的聚类图 把第p1p10p100个数据作为初始聚类中心，结果如图4.4所示：图4.4 初始点为第1 10 100序号的聚类实验分析与结论：分析：由以上聚类结果发现，不同的初始值的选取对聚类结果并不是造成很大影响，比较图4.1和图4.2可得，初始值选取的不同，只是造成聚类结果中极少数的数据发生变化，如数据20、27，聚类的迭代次数发生了改变由5次变为7次，还有不同点就是，聚类结果的输出顺序也发生了变化；对比图4.3和图4.2的聚类结果

54、图可得，选择第100、101、102个数据与选择第4、5、6个数据作为初始点的聚类结果是一样的，不同之处就是数据聚类的输出顺序有所改变，可是图4.3的迭代次数又比图4.2的迭代次数增多，变为9次；前三次的实验是选取连续的数据作为初始点，在第四次的实验中，选取第1、10、100个数据不连续的这三个数据作为初始值，从结果图可以看出，本次实验与第一次的聚类结果和迭代次数都相同，只是数据输出顺序有所改变。结论：首先对比四个图的聚类结果，并没有因为初始点选取的不同而发生大的改变，只是改变了迭代次数，其中选取最前面的三个数据和后面某一不连续的数据为初始点时迭代次数最少。实验表明：K-均值算法对初始值得敏感

55、体现在对聚类结果的迭代次数上，选取合理的初始点有助于我们高效率的完成聚类工作，用最少的时间完成我们所需要的结果为我们更好的应用在实际生活上。因此，从这此实验我们得到的结论是：（1）尽量选择数据最开始的连续的点作为初始点，这样可以用最少的迭代次数完成聚类；（2）改变K-均值算法的初始点可以影响数据集的迭代次数，对聚类结果影响不大；（3）每次初始值的改变也会造成数据输出顺序的改变，即使是在聚类结果不变的情况下。实验二：本次试验是验证不同的数据输入顺序，对聚类结果的影响，实验的数据集为了更具说服力，还是用实验一中的数据，不同之处是，此次实验只是将数据集中的后75个数放到前面，也就是与前75个数调换一

56、下顺序，本次试验只是验证数据集输入顺序的改变对聚类结果的影响，所以只选取两种初始值进行验证，与实验一进行对比，可得实验结果如下：令前三个数据p1p2p3作为初始聚类中心，如图4.5所示：图4.5 数据输入顺序改变聚类图1把第p4p5p6个数据作为初始聚类中心，得到的聚类结果如图4.6所示：图4.6 数据输入顺序改变聚类图2实验分析与结论：分析：本次实验主要是与之前的数据顺序不同时所得的聚类结果，由图4.5与图4.1，图4.6与图4.2的对比结果可得出，改变了数据的输入顺序，造成聚类结果有很大的改变，同时迭代次数也增加了，这说明K-均值算法对数据输入顺序的敏感性不仅体现在迭代次数上，而且更会改变数据的迭代次数。另外，再对比图4.5与图4.6的结果，虽然两次的聚类结果是一样的，但是