二分K均聚类算法在Iris上的测试.docx

二分K均值聚类算法在Iris上的测试目录一、问题背景3二、解决思路4（1）K均值算法思想4（2）二分K均值算法4三、实验结果5（1）数据集5（2）实验结果7四、观察分析9参考文献10附录11附录1 实验数据汇总结果展示11附录2 二分K均值算法功能实现主要代码13一、问题背景目前，对于聚类问题的研究普遍存在于社会生活中的各个领域，如模式识别，图像处理、机器学习和统计学等。关于对生活中各种各样的数据的聚类分类问题己经成为众多学者的研究热题之一[1]。聚类和分类的区别在于，聚类没有任何先验知识可循，要通过数据自身的特点，将数据自动的划分到不同的类别中。聚类的基本形式定义为“在已给的数据集合中寻找数据点集的同类集合。每一个集合叫做一个类，并确定一个区域，在区域中对象的密度高于其他区域中的密度”[2]。聚类方法有很多种，其中最简单的形式便是划分式聚类，划分式聚类试图将给定的数据集合分割成不相交的子集，使具体的聚类准则是最优的。实际中应用最广泛的准则是聚类误差平方和准则，即对于每一个点都计算它到相应的聚类中心点的平方距离，并对数据集合上的所有点的距离进行求和。一种最流行的基于最小聚类误差平法和的聚类方法是K-均值算法。K-均值算法是一种基于划分的聚类算法，它通过不断的迭代来进行聚类，当算法收敛到一个结束条件时就终止迭代过程，输出聚类结果。由于其算法思想简便，又容易实现对大规模数据的聚类，因此K-均值算法己成为一种最常用的聚类算法之一[3]。K-均值算法能找到关于聚类误差的局部的最优解，是一个能应用在许多聚类问题上的快速迭代算法。它是一种以点为基础的聚类算法，以随机选取的初始点为聚类中心，迭代地改变聚类中心来使聚类误差最小化。K-均值算法由于其聚类过程简单，易于实现，因此已经成为当前最常用的聚类算法之一。但是K-均值的算法的聚类结果容易受到初始聚类中心点的选取的影响，不稳定，且容易受到数据中的噪声点、离群点的影响[4]。并且在K-均值方法的迭代过程中由于初值的选取就有随机性就会导致聚类容易陷入局部最优，而找不到全局最优。K-均值缺点详细介绍如下：第一，K-均值算法中的K值必须由用户输入，在算法的流程图中我们可以看出，K-值是必须是一个用户最先确定的参数。K-均值方法必须在 K-值已知的前提下才能进行聚类。但是在一些实际问题的求解过程中，自然簇的个数K是没有事先给出的，通常是用户所不知道的。第二，K-均值聚类算法对于噪声和离群点数据非常敏感，聚类结果很容易受到数据中所含有的噪声和离群点的影响。该算法中在簇的质心求解过程中，是通过对每个簇求均值得到的，当数据集中含有噪声和离群点数据时，在计算质心时将导致聚类中心偏离数据真正密集的区域，而得到的聚类中心将向噪声和离群点数据所在的区域偏移， 然后在此基础上进行数据点的重新分配，这必然会引起聚类结果的不准确[5,6]。二、解决思路本课程主要针对K均值的有点以及对K值的初始选择这一限制，设计一种改进的K-均值聚类方法，即二分K均值算法。通过查阅资料总结，二分K均值算法可以加速K-均值算法的执行速度，因为它的相似度计算少了[7]。另外二分K均值算法不受初始化问题的影响，因为这里不存在随机点的选取，且每一步都保证了误差最小。（1）K均值算法思想K均值算法是一种经典的基于欧氏距离的硬划分算法，这种算法采用误差平方和函数作为优化的目标函数，误差平方和函数SSE的定义如所示[8]： （1） （2）式中：K——聚类的数目；Cj(j=1,2,...k)——聚类的第j个簇；X——簇Cj中的任意一组数据对象；Cj——含有mj个数据对象的Cj质心。可以看出SSE表示数据样本点和簇间中心间差异度平方之和，簇的中心会影响到SSE的值。很显然，如果SSE的值越小，那么就代表这种划分方法聚类的质量就越好。因此，K均值聚类的目标就是要设法找出能够使聚类准则函数SSE的值达到最小的聚类结果。 （2）二分K均值算法 二分k均值（bisecting k-means）算法的主要思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。以此进行下去，直到簇的数目等于用户给定的数目k为止。二分K均值算法思想具体如下：设X={x1，x2，...xi，...，xn}为n个Rd空间的数据，在开始聚类前，指定K为聚类个数。为了得到K个簇，将所有点的集合分裂成两个类，放到簇表S中。从簇表中选取一个簇Ci，用基本的K均值聚类算法对选定的簇Ci进行二分聚类。从二分实验中选择具有最小总SSE的两个簇，将这两个簇添加到簇表S中，更新簇表。如此下去，知道产生K个簇。在二分K均值算法中，使用结果簇的质心作为基本K均值的初始质心。使用误差平方和SSE作为度量聚类质量的目标函数，也称SSE为散度。对于