（4） 循环过程（2）到（3）直至各个聚类不再发生变化为止。 算法步骤：
1.为各个聚类确定一个初始的聚类中心，这样就可以产生K 个初始聚类中心。 2.按最小距离的原则把样本集中的样本分配到最邻近聚类。 3.把各聚类中的样本均值规定为新的聚类中心。 4.重复执行步骤2、3直至聚类中心不再发生变化。 5.结束过程，得到K个聚类。
3.2 K-均值聚类算法的主要缺陷及分析
主要优点：
（1）作为解决聚类问题而出现的一种传统经典算法，具有简单、快速的特点。 对于较大数据集的聚类分析来说，该算法相比较而言是可伸缩和高效率的。因为它的时间复杂度是0 (n k x ) 。其中, n 是所有对象的个数, k 是所需要的簇的个数, x 是迭代发生了多少次。通常情况下有k < （2）当结果簇是密集的，而且簇与簇之间的区别较为明显时, 它的效果比较较好。 主要缺点： （1）K-均值算法只是在簇的平均值已经提前被定义了的情况时才能被使用，而这个前提对于处理符号属性的数据并不适用。在 K-means 算法中，首先要根据初始的聚类中心来确定一个适合的初始划分，接着要对初始划分开始进行进一步的优化操作。聚类结果对这个初始点的选择是相当敏感的。倘若初始值选择的不合适很可能造成不能得到准确的聚类结果的后果。这也是K-means算法目前存在的一个主要问题。对于该问题的解决，许多算法采用遗传算法——GA，例如可以采用遗传算法GA来进行初始化操作，而且内部聚类准则被当做评价指标。 （2）必须事先给出k值（想要生成的簇的个数）。并且对初值很敏感：不同的初始K值，也许将导致不同结果。在 K-means 算法中K值是要求提前必须给定的，但是这个值的选择是相当难以估计的。实际情况下大部分时候提前是并不能确定给定的数据集应划分成多少个类别才最适合这个数据集。这也是该算法的一个缺点。有的算法是通过采用类的自动识别它的初始数据集的分类和合并来得到较为合适聚类的簇数。例如 ISODATA 算法。对 K-means 算法中的聚类数目K 值的确定有很多方法，有的是根据方差分析理论结合应用混合 F 统计量来得到最合适分类数，并且采用模糊划分熵的方法来 18 验证其合理性。有的使用一种结合了全协方差矩阵的RPCL算法，而且逐步删去那些仅仅包含很少数据量的训练数据的类。还有的使用一种名为次胜者受罚的学习竞争规从而自动决定类的合理数目。它的思想为：对于每个输入来说，不但获胜单元的权值被加以修正以便适应输入值。而且对于次胜单元则采用惩罚的方法以使其远离输入值。 （3）该算法对“噪声数据”以及孤立的点数据是相当敏感的，即使少量的该类数据也可以对平均值产生相当大的影响。 （4）从 K-means 算法流程中可以清楚的看到，该算法的实现原理要求必须不断地对样本进行分类，并且必须不断地计算更新调整后的新的聚类中心。所以当数据量很大时，算法的时间复杂度是非常大的。因此需要对算法的时间复杂度时刻进行关注、审查以满足时间等的要求。例如可以利用一定的相似性准则来排除一些近似的聚类中心的侯选集。 3.3 本章小结 本章主要是针对K-均值算法作了系统的分析，介绍了它的基本定义、基本思想、主要流程，最后详细分析了该算法在实际应用中的优点和不足。K-均值算法是数据挖掘聚类划分算法中最基本的算法，虽然它本身在实际应用的过程中存在不足，但是我们不能忽视它本身对数据集聚类的优点，在有的实践应用中也取得了理想的效果，很多的算法也是以此为依据进行改进的，主要是对距离计算的改进，如P-CLUSTER算法，就是基于K-均值算法的一种改进，是启发知识来判断该数据集聚类对象M的最近的簇中心是否改变。 19 4 K-均值聚类算法的实验 4.1 实验结果分析 实验一： 本文测试采用的是从数据堂下载的c-fat500-10.txt数据集，对K-均值算法进行了验证，经过实验分别对150个数据的数据集选取不同初始点分别进行聚类，验证不同的初始条件对最终聚类结果的影响情况，得到的聚类结果分别如下图： 令前三个数据p[1]p[2]p[3]作为初始聚类中心，如图4.1所示： 图4.1 初始点为第1 2 3序号的聚类图 把第p[4]p[5]p[6]个数据作为初始聚类中心，得到的聚类结果如图4.2所示： 20 图4.2 初始点为第4 5 6序号的聚类图 把第p[100]p[101]p[102]个数据作为初始聚类中心，得到的聚类结果如图4.3所示： 图4.3 初始点为第100 101 102序号的聚类图 把第p[1]p[10]p[100]个数据作为初始聚类中心，结果如图4.4所示： 21 图4.4 初始点为第1 10 100序号的聚类 实验分析与结论： 分析：由以上聚类结果发现，不同的初始值的选取对聚类结果并不是造成很大影响，比较图4.1和图4.2可得，初始值选取的不同，只是造成聚类结果中极少数的数据发生变化，如数据20、27，聚类的迭代次数发生了改变由5次变为7次，还有不同点就是，聚类结果的输出顺序也发生了变化；对比图4.3和图4.2的聚类结果图可得，选择第100、101、102个数据与选择第4、5、6个数据作为初始点的聚类结果是一样的，不同之处就是数据聚类的输出顺序有所改变，可是图4.3的迭代次数又比图4.2的迭代次数增多，变为9次；前三次的实验是选取连续的数据作为初始点，在第四次的实验中，选取第1、10、100个数据不连续的这三个数据作为初始值，从结果图可以看出，本次实验与第一次的聚类结果和迭代次数都相同，只是数据输出顺序有所改变。 结论：首先对比四个图的聚类结果，并没有因为初始点选取的不同而发生大的改变，只是改变了迭代次数，其中选取最前面的三个数据和后面某一不连续的数据为初始点时迭代次数最少。实验表明：K-均值算法对初始值得敏感体现在对聚类结果的迭代次数上，选取合理的初始点有助于我们高效率的完成聚类工作，用最少的时间完成我们所需要的结果为我们更好的应用在实际生活上。因此，从这此实验我们得到的结论是： 22