简介

K均值聚类，也叫做K-Means Clustering，是一种著名的用于分类问题的无监督机器学习聚类算法。聚类是针对给定的样本， 依靠它们特征的相似度或者距离，将其归到若干个‘类’或者’簇‘的数据分析问题。一个类就是给定样本集合的一个子集。所谓”人以类聚，物以群分“，常理来看，越相似的人更容易聚集在一起，在这里也是一样，相似的样本聚集在相同的类里面，不相似的样本分布在不同的类里。聚类属于无监督学习，因为只是根据样本特征之间的相似度或者距离来进行分类，而类或者簇事先并不知道，即这些类或者簇的个数以及对应的概念语义需要使用者来把握和命名。下图是对K-Means聚类算法执行过程的一个动图展示，图片来自维基百科。

K-Means算法流程

聚类的基本概念

1. 相似度或距离度量方法

聚类的对象是观测数据或者样本集合。上面我们讲到相似的样本更大可能会聚集在相同的类或者簇里，但是如何来定义相似性呢？如果是判断两个人是否相似的话，我们一般会观察这2个人的身高，长相，性格，习惯等特征，以此来判断是否相似。同理，如果我们有个样本，每个样本具有个属性，假设我们能够计算出任意两个样本的每个属性之间的相似度(similariity)或者距离(distance)，那么我们就可以根据这个值来判断这两个样本是否相似。因此，聚类的核心概念是相似度和距离，有很多相似度和距离的计算方式。因为相似度和距离直接影响到聚类的结果，所以选择适当的相似度和距离度量方法，是聚类的根本问题。
如果我们将样本集合看成是空间中的点的集合，以该空间的距离表示样本之间的相似度，那么常用的距离有闵可夫斯基距离，闵可夫斯基距离越大表示相似度越小，距离越小则相似度越大。

我们常用的欧氏距离，其实就是闵可夫斯基距离的一种。

给定样本集合, 是维实数向量空间中点的集合，其中

当时，称为欧氏距离，即：

当时，称为曼哈顿距离，即：

当时，称为切比雪夫距离，即取各个坐标数值差的绝对值的最大值：

最常用也是大家最熟悉的，莫过于欧氏距离。除了上述距离度量方式以外，还有马哈拉诺比斯距离、相关系数、夹角余弦等等。感兴趣的读者可以自行查阅资料。

2. 类或者簇的定义

通过上节讲的相似度或者距离的度量方式，我们现在可以计算两个样本之间的距离了，然后通过聚类可以得到类或者簇，本质都是样本的子集。如果一个聚类方法假定一个样本只能属于一个类，或者类的交集为空集，那么该方法称为硬聚类方法。否则，如果一个样本属于多个类，或者类的交集不为空集，那么该方法称为软聚类方法。用表示类或者簇，用表示类中的样本，用表示中样本的个数，用表示样本之间的距离。
设为给定的正数，若集合中任意两个样本, 若满足：

那么称为一个类或者簇。
得到了一个类或者簇，也就是得到了一个子集，那么如何来描述这个类呢，主要有以下几种方式:

• 使用类中所有样本的均值，即类的中心
  
• 使用类中任意两个样本之间的最大距离，即
  
• 使用类的样本散布矩阵和样本协方差矩阵
  
  其中为样本的维度（样本属性的个数）。

3. 类间距离的度量

如果我们现在已经有两个类，分别包含个样本，分别用来代表它们的均值，即类中心。那么我们如何衡量这两个类之间的距离呢？这里面也包含好几种定义，如下。

• 最短距离或单连接
  定义类的样本与类的样本之间的最短距离为两类之间的距离
  
• 最大距离或完全连接
  定义类的样本与类的样本之间的最长距离为两类之间的距离
  
• 中心距离
  定义类的类中心与类的类中心之间的距离
  

中心距离是我们比较常用的。

K-Means算法流程

在了解了聚类算法的相关基本概念之后，现在我们就可以正式介绍K-Means算法了。K-Means Clustering算法译为K均值聚类算法，它是基于样本集合划分的聚类算法。k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本划分到k个类中，每个样本到其所属的类中心距离最短。并且每个样本只能属于一个类，故k均值聚类是硬聚类算法。K-均值算法归结为对样本集合X的划分，或者说从样本到类的函数的选择问题。K-均值聚类的策略是通过损失函数的最小化选取最优的划分或者函数。

1. 策略

我们首先统一一下相似度或距离的度量方式，在下文中统一采用欧氏距离作为样本之间的距离度量。

接着，定义样本与其所属的类中心之间的距离的总和为损失函数，即：

其中是第个类的均值或者聚类中心，是指示函数，判断第个样本是否属于第个类或簇。因此K均值算法就变成了一个最优化问题：

相似的样本总是被聚到同类中，此时的损失函数值最小，这个目标函数的最优化能达到聚类的目的。但是这是个组合问题，所有可能的分法是指数级别的，实际操作时，我们一般采用迭代的方法逐渐逼近问题的解。

算法流程

k-均值聚类算法是一个迭代的过程，每次迭代包括两个步骤。

1. 首先选择k个类的中心，将样本逐渐指派到与其最相近的中心的类中，得到一个聚类结果。
2. 接着计算每个类中的样本均值，将其作为新的聚类中心。

不断重复以上两个步骤，直到聚类中心不再发生改变。
下面给出算法具体步骤：
输入为个样本集合， 输出为样本的聚类。
（1）初始化时，令，从样本集合中随机选择k个样本作为初始聚类中心。
（2）对样本进行聚类。对固定的类中心，其中是的中心，计算每个样本到所有类中心的距离，将每个样本指派到与其最近的类中心去，构成聚类结果。
（3）计算新的类中心。对每一轮的聚类结果，计算当前各个类中的样本的均值，作为新的类中心。
（4）如果步骤（3）中计算出来的聚类中心结果与步骤（2）一样，即聚类中心不再发生改变，那么算法停止，输出结果。否则，返回步骤（2）继续执行。

k-均值聚类算法的复杂度为O(mnk)，其中m是样本的维度，n是样本的个数，k是类或者簇的个数。

实例演示

假如我们有以下5个样本点(为了可视化，这里选择的是二维平面上的坐标点)的集合，我们需要通过K-均值聚类算法将其聚集到2个类中。原始数据点如下。

import matplotlib.pyplot as plt

x_point = [0,0,1,5,5]
y_point = [2,0,0,0,2]
label_y = ['k','k','k','k','k']

plt.scatter(x_point, y_point, c=label_y)
# 设置坐标轴范围
plt.xlim(-2,6)
plt.ylim(-2,6)

plt.grid()
plt.show()

原始数据点

初始2个聚类中心

一次迭代之后

sklearn库算法包

sklearn库中已经有包装好的K-Means聚类算法，下面来展示一下其用法。我们使用sklearn的聚类数据集生成器，生成一些聚类数据，然后对其使用K-Means算法。如下：

import matplotlib.pyplot as plt
import seaborn as sns; sns.set()  # for plot styling
import numpy as np

from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=100, centers=4,
                       cluster_std=0.60, random_state=0)
plt.scatter(X[:, 0], X[:, 1], s=50);

聚类数据

肉眼观察可以看到这实际上可以聚为4类，接下来我们使用K-Means算法来自动进行分类。

from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)
y_kmeans

可视化一下：

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
# 取出K-Means算法得到的聚类中心
centers = kmeans.cluster_centers_
print(centers)
plt.scatter(centers[:, 0], centers[:, 1], c='r', marker='*', s=200);

K-Means算法结果

可以看到K-Means算法得到的结果跟我们直观看上去的很接近，很完美的完成了聚类任务。

手写K-Means算法

鉴于K-Means算法比较经典，同时也比较简单，因此在很多大厂面试的时候，都要求能够手写K-Means算法，本文这里也给出一个简单实现，如下：

import numpy as np

def euclidean(X, Y):
    return sum([(a - b)**2 for (a,b) in zip(X,Y)])**0.5

def dispatch_samples(x, centers):
    # 将样本x指派到距离最近的聚类中心
    res = []
    for i in range(x.shape[0]):
        idx, dis = 0, float('inf')
        for j in range(centers.shape[0]):
            d = euclidean(x[i], centers[j])
            if d < dis:
                idx, dis = j, d
        res.append(idx) # 将当前样本指派的类别放入数组中
    return np.array(res)

def Simple_KMeans(X, n_clusters, rseed=2):
    # 1. 首先随机选择n_clusters个样本作为原始聚类中心
    # 生成一个伪随机数生成器，每次都通过它来生成随机数，可以保证每次运行生成的随机数是一样
    rng = np.random.RandomState(rseed)
    # 取一个排列，然后取前n_clusters个作为聚类中心
    i = rng.permutation(X.shape[0])[:n_clusters]
    centers = X[i]
    while True:
        # 1. 对每个样本都计算其到所有聚类中心的距离，将样本指派到距离其最近的聚类中心
        labels = dispatch_samples(X, centers)
        # 2. 重新计算当前聚类的聚类中心
        new_centers = np.array([X[labels == i].mean(0) for i in range(n_clusters)])
        
        # 如果新的聚类中心与之前一致，则退出算法
        if np.all(centers == new_centers): break
        # 使用新的聚类中心
        centers = new_centers
    # 返回聚类中心和标签
    return centers, labels

centers, labels = Simple_KMeans(X, 4)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis');
plt.scatter(centers[:, 0], centers[:, 1], c='r', marker='*', s=200);

手写K-Means算法执行结果

K-Means优缺点

K-Means算法是一个经典的，实用的聚类算法，值得我们去掌握它，它具有以下优点 ：

• 算法原理简单，实现容易，收敛较快
• 聚类效果较优
• 算法可解释性较强
• 参数较少，仅仅需要类别数K

当然K-Means算法也有很多缺点，下面逐一说明。

• K-Means算法得到的结果是局部最优，并不总能得到全局最优解。还是以上面的例子，如果我们使用另外一个随机种子，那么得到的结果可能是这样的。

centers, labels = find_clusters(X, 4, rseed=80)
plt.scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='viridis');

错误的聚类结果

可以看到，修改了随机种子之后，说明初始聚类中心也改变了，那么得到的聚类结果就可能发生很大的改变，甚至不是我们想要的结果。

• 类的个数K必须手动提前设置
  我们必须提前告诉算法要聚成多少类，这个数据算法无法自己从数据中学到。但是有时候我们也无法确定应该设置成多少。算法只会乖乖地将数据聚合成我们设置给它的K类。在上面的例子中，如果我们将k设置成6，那么可能会得到以下的结果。

centers, labels = find_clusters(X, 6)
plt.scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='viridis');

聚成6类

算法确实收敛了，将样本聚成了6类，但是这个结果对我们来说有意义嘛？这个不太好回答。因为实际应用中的最优K值往往是不知道的。解决这个问题的一个思路是，尝试多个不同的K值，然后检查不同K值下的聚类结果的质量。衡量聚类结果的质量的方式可以是计算算是函数值，也可以是使用类的平均直径，即所有类的直径取平均。一般来说，类别数k变小时，平均直径会变大；类别说变大是，平均直径会逐渐减小，直到某个阈值之后就不再减小。而这个值一般是最优的k值。

• K-Means聚类受限于线性聚类边界
  K-Means模型假设一个样本点应该是比其他点更加靠近自己的聚类中心，但是对于一些有复杂边界的样本集合，这个假设就不成立了，比如如下这种情况。

from sklearn.datasets import make_moons
X, y = make_moons(200, noise=.05, random_state=0)

labels = KMeans(2, random_state=0).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='viridis');

复杂边界样本的聚类

实际上K-Means类之间的边界应该总是线性的，当面对这种具有复杂边界的情况是，K-Means算法并不能取得好的结果。

• 计算量巨大
  同KNN算法一样，K-Means算法在每次迭代的时候，每一个点都需要跟所有的聚类中心进行距离计算，当样本的维度较高时，这个计算量是非常大的。

K-Means++算法

K-Means算法自1967年由MacQueen提出后，历经很多次改进，比较有名的有K-Means++算法。K-Means++算法主要是解决前面提及的K-Means算法的初始化聚类中心随机选择导致的问题。K-Means++不再采用K-Means算法随机确定初始聚类中心的做法，而是令最初选择的聚类中心尽可能的远。这也符合我们的直觉，因为每个类之间就应该尽可能的远。K-Means++算法的流程如下：
（1）随机选取一个样本作为第一个聚类中心 ；
（2）计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离），用 表示；这个值越大，表示被选取作为聚类中心的概率较大；最后，用轮盘法选出下一个聚类中心；
（3）：重复（2），直到选出 k 个聚类中心。

选出初始点后，其余步骤就与标准K-means 算法一致了。

参考

• 《统计学习方法》 -- 李航
• 《机器学习》-- 周志华
• https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.scatter.html
• https://jakevdp.github.io/PythonDataScienceHandbook/05.11-k-means.html
• https://zhuanlan.zhihu.com/p/32375430