Python实现实现Kmeans聚类算法聚类算法
主要为大家详细介绍了Python实现Kmeans聚类算法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
本节内容：本节内容：本节内容是根据上学期所上的模式识别课程的作业整理而来，第一道题目是Kmeans聚类算法，数据集是Iris(鸢尾
花的数据集)，分类数k是3，数据维数是4。
关于聚类关于聚类
聚类算法是这样的一种算法：给定样本数据Sample，要求将样本Sample中相似的数据聚到一类。有了这个认识之后，就应
该了解了聚类算法要干什么了吧。说白了，就是归类。
首先，我们需要考虑的是，如何衡量数据之间的相似程度？比如说，有一群说不同语言的人，我们一般是根据他们的方言
来聚类的（当然，你也可以指定以身高来聚类）。这里，语言的相似性（或者身高）就成了我们衡量相似的量度了。在考虑存
在海量数据，如微博上各种用户的关系网，如何根据用户的关注和被关注来聚类，给用户推荐他们感兴趣的用户？这就是聚类
算法研究的内容之一了。
Kmeans就是这样的聚类算法中比较简单的算法，给定数据样本集Sample和应该划分的类数K，对样本数据Sample进行聚
类，最终形成K个cluster，其相似的度量是某条数据i与中心点的”距离”(这里所说的距离，不止于二维)。
基本思想基本思想
KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各
个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。
基本步骤基本步骤
K-Means聚类算法主要分为三个步骤：
1，初始化k个聚类中心。
2，计算出每个对象跟这k个中心的距离（相似度计算，这个下面会提到），假如x这个对象跟y这个中心的距离最小（相似度
最大），那么x属于y这个中心。这一步就可以得到初步的k个聚类 。
3，在第二步得到的每个聚类分别计算出新的聚类中心，和旧的中心比对，假如不相同，则继续第2步，直到新旧两个中心相
同，说明聚类不可变，已经成功 。
复杂度分析复杂度分析
时间复杂度：O(tKmn)，其中，t为迭代次数，K为簇的数目，m为记录数，n为维数
空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数
初始质心的选择初始质心的选择
选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始质心，但是这样簇的质量常常很差。处
理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE（误差的平方
和）的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。
第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初
始质心。该方法通常很有效，但仅对下列情况有效：
（1）样本相对较小，例如数百到数千（层次聚类开销较大）；
（2）K相对于样本大小较小
第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选
择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法
可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群
点很少（多了就不是离群点了），它们多半不会在随机样本中出现。计算量也大幅减少。
第四种方法是使用使用canopy算法进行初始划分算法进行初始划分。基于Canopy Method的聚类算法将聚类过程分为两个阶段：
Stage1：聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计
算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy ，通过一系列计算得到若干Canopy，Canopy之间可
以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理。
Stage2：在各个Canopy 内使用传统的聚类方法(如K-means)，不属于同一Canopy 的对象之间不进行相似性计算。从这个方
法起码可以看出两点好处：首先，Canopy 不要太大且Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对
象的个数；其次，类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy 个数完全可以作为这
个K值，一定程度上减少了选择K的盲目性。
算法实验算法实验
任务任务
在给定的Iris.txt样本文件中，用K-means聚类算法将150个4维样本数据分成3类
数据集数据集(Iris.txt)
5.1 3.5 1.4 0.2
4.9 3.0 1.4 0.2
