数据嗨客 | 第9期：k-means

0. 引子

想象你是一名客户关系主管，你想根据客户的特征对客户进行分类，然后针对每一个类的客户聘用一个经理对改客户群体进行管理。每个类中的客户应该尽可能的相似（在需求，业务等方面）。

那么，如何才能知道哪个客户属于哪个类别呢？

这样的问题叫做聚类（Clustering）问题，与之前介绍的分类问题不同，客户所属的类别信息是未知的。

需要通过分析客户的特征，通过某些算法来将客户划分成不同的类别。这些算法叫做聚类算法。

聚类作为一种数据挖掘工具，在生物学，商务智能以及Web搜索等方面有着广泛的应用。

1. 聚类算法K-Means

作为一种流行的聚类算法，K-Means最初起源于信号处理。

K-Means的目标是将n个样本的数据划分到k个簇（也就是类别）中，其中k为人为指定的簇的个数，每个样本属于距离自己最近的簇。

下图为K-Means 用于图像处理的一个应用：

图 1 K-Means用于图像分割

图中给出了原始图像以及使用不同k值得到的K-Means聚类结果。

上图聚类的过程使用图片中每个像素点作为数据样本，聚类过程会将距离上比较接近的像素（图中的颜色）划分到同一簇。

划分完成后，使用簇的质心值（某种颜色）替代簇中每一个点的值（与质心颜色相似的颜色）。这样原图中原来假设有1000种颜色，聚类之后的图之用了2，3，10种不同的颜色（对应于k=2,3,10）。

由于只使用了少量的颜色，此这种方法也达到了图像压缩的目的。

2. 核心思想

现在我们就要介绍一些干货了，原理其实特别简单。

给定n个需要被聚类的样本的集合(x_1,x_2,…,x_n)，xi是d维实数向量。同样引入一组d维向量ci，其中i=1,2,…,k，且ci表示第i个簇Ci，我们可以认为ci是簇Ci的中心。

如下图所示：

图 2 样本点，簇以及簇心

簇的中心可以定义为所有划分到该簇的样本点的中心点。

我们的目标是为把每一个样本点划到离它最近的一个簇中，其中要用到样本点到簇中心点的距离的度量。

我们约定每一个属于某个簇的样本点

其中，E是所有样本的误差的平方和，p是样本点，ci是簇的簇心。

换言之，对于每个簇中的每个样本，求样本到其簇中心距离的平方，然后对所有的样本的求和。这个目标函数试图使生成的结果簇尽可能紧凑和独立。

3. 算法过程

在掌握了聚类的核心思想后，我们来具体看一下其具体算法，同样非常简单。

**K-Means算法过程**

1）选择k个点作为初始质心；

2）repeat:

2.1）将每个样本点通过距离计算指派到最近的质心，形成k个簇

2.2）更新簇的中心点值，即重新计算每个簇的质心

2.3）until 质心不发生变化 ***

重复上述优化过程，直至聚类的分配不再改变（或迭代次数超过某个值）。

由于每次优化过程，都降低目标函数E的值，因此目标函数E是一定收敛的。

然后，算法可能收敛到一个局部最优解而不是全局最优解。K-Means算法聚类过程如下图所示：

图 3 K-Means算法聚类过程

4. 质心的选择

前面，我们已经掌握了K-Means算法的主要内容，接下来我们了解一些其他的细节。

选择质心常见的做法是随机初始化质心，但是这种方法容易陷入局部最优化，不能得到最优的聚类结果，有时结果可能很糟糕。

常用处理方法：

1. 多次运行，每次使用一组不同的随机初始质心，然后选取具有最小E值的簇集。该策略虽然简单，但是效果可能不好，取决于数据集和寻找的簇的个数。随机选择初始质心存在的问题即使重复运行多次也不能克服。
2. 使用层次聚类技术对样本进行聚类，从层次聚类中提取k个簇，并用这些簇的中心作出初始质心。该方法通常很有效，使用条件为：1）样本数目不大；2）k相对样本大小较小。
3. 随机地选择第一个样本点，或取所有点的质心作为第一个质心点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。

5. 常用距离

一般情况下我们使用欧氏距离作为K-Means算法的距离度量，然而，对于其他一些数据类型，欧氏距离并不一定适用，比如文本数据。

此时，可以选择其他的距离度量，如曼哈顿距离、余弦相似度和Jaccard距离等。

6. K-Means方法优缺点

优点：

（1）算法实现简单，直观

（2）不仅可以使用欧式距离，还支持多种距离计算

缺点：

（1）需要指定k值和初始化k个簇

（2）聚类结果依赖于初始k个簇的选择

（3）容易陷入局部最优

（4）不易处理非簇状数据，且容易受离群点的影响

7. 二分K-Means算法

在了解了经典的K-Means方法之后，另外一种二分K-Means算法也很容易理解。

它相当于是原始K-Means方法的一个逆过程，采用分裂的方式从一个簇分裂成k个簇。

二分K-Means算法每次从所有簇中选择具有最大E值的簇划分为两个簇，重复该过程，直至簇集合中含有k个簇。直观上看，该算法可以克服质心选择上的问题。

二分K-Means算法过程：

1）把所有数据作为一个簇加入到簇集合；

2）Repeat：

2.1）从簇集合中，挑选出一个E值最大的簇

2.2）使用随机初始化质心的方式，将该簇划分为两个簇（一个簇对）

2.3）重复上一步骤p次，产生p个簇对，从p个簇对中选择EE值最小的簇对加入到簇集合中

2.4）直至簇集合中含有k个簇

在步骤2.1中，对于簇的挑选标准很多，不仅可以选择E值最大的簇，也可以选择样本数目最多的簇，或者使用其他标准。二分K-Means算法，在每一次划分过程都对质心做多次选取，选择最优划分，但也不能保证最终得到的事全局最优解。

8. K-Means方法的其他变种：

• K-medians clusetering：使用每个维度的中位数而不是均值来作为聚的中心；
• K-medoids：使用簇中心位置的数据作为簇的中心，而不是每个簇的平均值；
• K-Means++：K-Means++是一个为k-Means算法选取初始质心的算法，它主要在初始化过程，选择k个距离较远的质心；
• 基于粗糙集的K-Means聚类：原始的K-Means方法每次迭代中，每个数据样本只能划分给一个簇，基于粗糙集的K-Means聚类，一个数据样本可能被划分给多个簇。

本文由 普林科技（微信公众号：普林科技） 投稿 数据分析网 发表，并经数据分析网编辑。版权归作者所有，转载此文请与作者联系。