k-Means算法和实战演练

1.  k-均值聚类算法介绍

跟之前写的SVM和Adaboost算法不一样的是，k-均值聚类算法所进行分类的数据是没有类别的。

之前写的机器学习算法，都是分类算法，属于监督学习，简单来说就是我给训练机器一部分带有分类标签的训练数据，训练机器自己通过学习找到其中的分类准则，并用该准则来分类之后给的预测数据；

k-均值聚类算法是聚类算法，属于无监督学习，简单来说就是我给训练机器的数据就是没有分类标签的，训练机器需要通过算法将这些数据进行分类，每加入一个新的数据，分类结果都会有所不同。

2.  k-均值聚类算法原理

首先，随机确定k个初始点作为中心。然后将数据集中的每一个点分配到一个簇中，这里的分配原则是就近原则，即数据点离哪一个中心点的欧式距离小就分到那一簇里。：

(这里假设数据点有n个特征值)

第一次将所有的点都分配完后，就要将中心点的值进行更新，更新的原则是就是取该簇里数据点的中心点：

得到新的中心点后，再次将所有数据点重新进行分配，直到中心点不会再变化。

3.  k-Means算法流程图

4.  k-Means算法二维数据简单演练

数据集：一些离散的坐标

当k=3时：

（‘+’表示中心点）

当k=4时:

我们可以发现，k=4的时候效果会好一些，但这个结论是根据我们用肉眼看出来，我们可以想一想，如果要让计算机自动能确定k的值，该怎么做？

5.  提高聚类性能

由于k-均值算法收敛到的是局部最小值，而非全局最小值，我们为了判断选什么样的k好，生成的簇什么样的好，定义了一个指标——误差平方和（SSE）。

SSE值越小表示数据点就越接近于它们的中心，聚类效果也越好。我们可以想到，只要增加簇的个数，SSE的值肯定就会减小（极端情况就是每一个点都是一个簇，那么SSE就为0了），但这肯定不是我们聚类的目标，我们希望的是保持簇数目不变的情况下提高簇的质量。

5.1  两种处理方法

1.合并最近的中心

2.合并两个使得SSE增幅最小的中心

6.  二分k-均值算法

二分k-均值算法是为了克服k-均值算法收敛于局部最小值的问题。

该算法首先将所有数据点作为一个簇，然后将该簇一分为二。之后选择一个簇继续进行划分，选择的原则是对该簇划分能最大程度降低SSE的值。然后不断重复，知道达到指定的簇数目为止。

7.  二分k-均值算法流程图

8.  二分k-均值算法二维数据简单演练

数据集沿用之前使用的数据集

k=3：

k=4:

我们可以看出来k=3时，二分k-均值算法的效果比k-均值聚类算法的效果要好。

k=4时，两种算法的效果是一样的。

9.  对地图上的点进行聚类

10.  参考文献

《机器学习实战》