简介

  k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，由James MacQueen 在1967年提出，是聚类方法中最著名，最具代表性的算法之一
  在提到Kmeans之前稍微介绍下聚类和分类的区别

原理

  从字面上看，就是将N个样本划分成K个类别，通过均值（Mean）的方法，其原理是根据已知初始中心点，计算所有样本距中心点距离并将该点划分为距离最小的类中，并根据得到的类计算新的中心点，若该过程收敛，中心点会随着迭代逐渐趋近于最终点。

步骤

1. 确定初始中心点：主要是确定初始点个数，初始点的位置对会影响迭代快慢。

2. 计算样本距中心点位置，并划分至最小距离对应类别。

3. 通过计算类内均值得到新的中心点。

4. 重复第2、3步，直至满足终止条件

   1. 没有样本被重新分配
   2. 没有中心点发生变化
   3. 误差平方和局部最小

时间复杂度：$O(tknm)$，其中，t 为迭代次数，k 为簇的数目，n 为样本点数，m 为样本点维度。

空间复杂度：$O(m(n+k))$，其中，k 为簇的数目，m 为样本点维度，n 为样本点数。

优缺点

优点：

• 容易理解，聚类效果不错，虽然是局部最优， 但往往局部最优就够了；
• 处理大数据集的时候，该算法可以保证较好的伸缩性；
• 当簇近似高斯分布的时候，效果非常不错；
• 算法复杂度低。
  缺点：
• K 值需要人为设定，不同 K 值得到的结果不一样；
• 对初始的簇中心敏感，不同选取方式会得到不同结果；
• 对异常值敏感；样本只能归为一类，不适合多分类任务；
• 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类（对噪声、异常点敏感）。

一点思考

&emps;&emps;作为最经典的算法，其改进的方向还是很多的
1、K值在选取过程中是人为的，可以改为自适应的
2、K值在选取之后是固定的，明显这不是合理的操作
3、在距离、均值、误差等计算上根据实际问题也可改进

改进算法

1. 核Kmeans算法
2. Kmeans++算法
3. ISODATA算法

待补充