k-means算法

聚类算法是无监督学习最常见的一种，K-Means 算法是一种聚类算法。

假设给定数据：x(1),x(2),⋯,x(m),x(i)∈Rnx(1),x(2),⋯,x(m),x(i)∈Rn，注意数据是没有标签的。

K-Means 算法的一般流程

1. 选择初始的 K 个聚类中心 μ1,μ2,…,μk∈Rnμ1,μ2,…,μk∈Rn
2. 重复以下两步直到收敛（聚类中心不再变化或者变化低于阙值）：
   （1）计算每个样本到各个聚类中心的距离，并将其类别标号设为距其最近的聚类中心的标号，即：
   c(i):=argminj∥x(i)−μj∥2j=1,2,…kc(i):=argminj‖x(i)−μj‖2j=1,2,…k
   （2）更新聚类中心的值为相同类别的样本的平均值
   μj=∑mi=1Ic(i) =jx(i)∑mi=1Ic(i)=jμj=∑i=1mIc(i)=jx(i)∑i=1mIc(i)=j

对 K-Means 算法进一步解释

K-Means算法要优化的目标函数如下：
J(c,μ)=m∑i=1∥x(i)−μc(i)∥2J(c,μ)=∑i=1m‖x(i)−μc(i)‖2
优化目标可以看成让所有点到其对应的聚类中心点的距离和最小。K-Means 算法可以看成对目标函数 JJ 的坐标下降过程，对应的解释如下：

1. 执行上述 2(1) 这一步的时候，相当于固定 μμ，改变 cc（每个样本所对应的类别），改变的规则是样本到哪个聚类中心的距离最小就将对应的样本对应的 cc 改为哪类。所以 J(c,μ)J(c,μ) 一定会减小。
2. 执行上述 2(2) 这一步的时候，相当于固定所有样本的 cc，重新计算各个类别的中心，进一步使 J(c, \mu) 减小。

K-Means 算法注意问题

1. 目标函数 JJ 不是一个凸函数，因此 k-means 算法不能保证收敛到全局最优解，一个简单的方法就是随机初始化多次，以最优的聚类结果作为最终的结果。
2. 聚类结束后，如果一个中心没有任何相关的样本，那么这个中心就应该去掉，或者重新聚类。

K-Means 算法的改进

1. k-means++ 算法，可以直观地将这改进理解成这 K 个初始聚类中心相互之间应该分得越开越好。在选取第一个聚类中心 (n=1) 时同样通过随机的方法。但在选取第 n+1 个聚类中心时：距离当前 n 个聚类中心越远的点会有更高的概率被选为第 n+1 个聚类中心。
2. 二分 k-means 算法，为了克服 k-means 聚类算法容易陷入局部最小值的问题和提高聚类的性能，提出了二分 k-means 聚类算法。该算法基本思想是首先将所有的样本点划分到一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，直到得到用户指定的簇数目为止。选择哪个簇进行划分取决于对其划分是否可以最大程度的降低 SSE（误差平方和）。

1. 斯坦福机器学习公开课 —— 吴恩达
2. 斯坦福ML公开课笔记 —— 张雨石
3. 《机器学习实战》

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以在文章下方的评论区进行评论，也可以邮件至 [email protected]