k-means算法的matlab代码实现_从零实现机器学习算法（十一）KMeans

dc2df6d37e1c7aff8bf9c1f641002e94.png

1. KMeans简介

KMeans是一种简单的聚类方法，它使用每个样本到聚类中心的距离作为度量来决定簇。其中

值是用户指定的簇的数目。初始时，随机选取
个点作为聚类中心(质心)，然后通过不断修改聚类中心达到最优的效果。由于其计算每个簇的均值作为质心，因此也成为K均值。

2. KMeans模型

KMeans

KMeans算法较为简单，记K个簇中心为

，每个簇的样本数目为
。KMeans使用误差平方和作为目标函数，即

对损失函数求偏导，可得

令导数等于0，解得

即令每个簇的均值作为质心。

KMeans代码如下：

def

其中的adjustCluster()函数，为确定了初始的质心后的调整过程，功能是最小化损失函数

,其代码为：
def

2分KMeans

由于KMeans可能收敛于局部最小值，为了解决这一问题引入2分KMeans。2分KMeans原理是先将所有样本视为一个大簇，然后将其一分为二；然后选择其中一个继续划分，直到簇的个数达到了指定的

为止。那么如何选择要划分的簇呢？这里采用误差平方和（Sum of Squared Error, SSE）来作为评价标准。假设现在有
个簇，记为

选择被划分的簇流程为：将

中的一个簇
划分成两部分
（这两部分采用普通的KMeans方法）,此时的SSE为

适合划分的簇为

然后，如此反复，直到质心个数等于指定的

代码如下：

def

KMeans++

KMeans 方法由于初始的质心选择对于聚类算法具有很大的影响，因此引入KMeans++的算法。其原理为：假设现在有

个簇

则在选取第

个聚类中心时：距离当前
个聚类中心越远的点会有更高的概率被选为第
个聚类中心。这也符合我们的直觉：聚类中心当然是互相离得越远越好。首先计算每个样本点与当前已有的聚类中心的最短距离

然后计算每个样本被选为下一个聚类中心的概率

然后采用轮盘法选出下一个聚类中心。

个质心选完之后，运行adjustCluster()调整质心。KMeans++代码如下：
def

3. 总结与分析

聚类算法收敛后可以使用一些方法来调整质心。对于

值的选择也有一些方法来确定，如采用轮廓系数（Silhouette Coefficient）来确定。最后看下三种聚类方法的效果。

51be2122ba12511ffb742999a2c0a8b2.png

410555d82f102d3be7203b7287979ab9.png

ea6e5357d57ba462fca6b9694f398270.png

faf94f2cd58c70731be16c8801c2e7cc.png

可以发现KMeans++的算法运行效果最好，这三种方法运行时间差不多。

本文相关代码和数据集：

Ryuk17/MachineLearning​github.com
e35c15d0fc85d2e3e6811ee0a6a32c48.png

参考文献

[1] Peter Harrington, Machine Learning IN ACTION

[2] Andrew Ng, CS229 Lecture notes