聚类算法及其模型评估

聚类(Clustering)就是按照某个特定标准把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。

主要的聚类方法可以划分成如下几类：划分方法、层次方法、基于密度的方法、基于网络的方法、基于模型的方法。

聚类和分类有什么区别

聚类（Clustering）

聚类，简单地说就是把相似的东西分到一组，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此聚类通常并不需要使用训练数据进行学习，在机器学习中属于无监督学习。

分类（Classifification）

分类，对于一个分类器，通常需要你告诉它“这个东西被分为某某类”。一般情况下，一个分类器会从它 得到的训练集中进行学习，从而具备对未知数据进行分类的能力，在机器学习中属于监督学习。

k-means算法

k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。 k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。

k-means.png

k-means的算法流程

输入：包含n个对象的数据和簇的数目k

(1) 随机地选择k个对象，它们初始地代表着k个簇的中心或者说平均值

(2) 对每个对象，根据其与各簇中心的距离，将它划分给最近的簇

(3) 重新计算每个簇的平均值

(4) 重复步骤(2)、(3)知道簇中心不再变化

输出：n个对象到k个簇，使平方误差准则最小

平方误差准则定义如下：

这里E是数据中所有对象的平方误差的总和，p是对象，是簇的平均值，是每个簇的对象集。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧氏距离，当然也可以用其他距离度量。当平方误差最小，簇中心不再变化，循环结束。

k-means算法的优缺点

优点：

​ 简单、速度快、适合发现球形聚类

缺点：

1. k值不好选取，解决方案：可用GridSearch
2. 对初始聚类中心敏感，解决方案：多初始化几遍，选取损失函数小的
3. 对噪音和异常值免疫能力差
4. 不能解决非凸数据

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种典型的基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

要理解DNSCAN算法的流程，首先要熟悉几个概念：

1. 算法需要给定两个参数：邻域半径eps和密度阈值minPts。

   这两个算法参数实际可以刻画什么叫密集——当邻域半径eps内的点的个数大于密度阈值minPts时，就是密集。

2. 3种点的类别：核心点，边界点和噪声点。

   邻域半径eps内样本点的数量大于等于minPts的点叫做核心点。不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点。

DBSCAN3种点的类别.jpg

3. 4种点的关系：密度直达，密度可达，密度相连，非密度相连。

   如果P为核心点，Q在P的eps邻域内，那么称P到Q密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果P到Q密度直达，那么Q到P不一定密度直达。

   如果存在核心点P2，P3，……，Pn，且P1到P2密度直达，P2到P3密度直达，……，P(n-1)到Pn密度直达，Pn到Q密度直达，则P1到Q密度可达。密度可达也不具有对称性。

   如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。

   如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

DBSCAN4种点的关系.jpg

DBSCAN的算法流程

输入：邻域半径eps，密度阈值minPts

(1) 扫描数据集中每点，如果某点p的eps邻域半径范围内包含的点多于minPts个，则将其纳入核心点列表，并将其密度直达的点形成对应的临时聚类簇。

(2) 对于每一个临时聚类簇，检查其中的点是否为核心点，如果是，将该点对应的临时聚类簇和当前临时聚类簇合并，得到新的临时聚类簇。重复此操作，直到当前临时聚类簇中的每一个点要么不在核心点列表，要么其密度直达的点都已经在该临时聚类簇，该临时聚类簇升级成为聚类簇。最终所有临时簇全部被处理为止。

输出：簇的划分结果

DBSCAN算法的优缺点

优点：

1. 不需要指定簇的个数
2. 可以发现任意形状的簇
3. 擅长找到离群点

缺点：

1. 对于高维度数据不好处理
2. 参数难以选择

分层聚类

分层聚类(Hierarchical Clustering)是通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并(凝聚)和自上而下分裂两种方法。

分层聚类的算法流程：

注：这里以自下而上凝聚的方法为例。

1. 初始化，把每个样本(假设一共N个样本)各自归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度
2. 寻找各个类之间最相近的两个类，把他们归为同一类
3. 重新计算新生成的这个类与各个旧类之间的距离
4. 重复(2)、(3)步骤，知道所有样本都归为一类，算法结束（当然，我们可以事先给定n_clusters参数，表示分成几个聚类簇，当算法达到这个阈值时，迭代也会结束。）

分层聚类.gif

通过这张gif图，就能更加清楚地看出分层聚类的工作流程了。

关于如何判断两个类之间的距离，也就是相似度，有不少办法，这里介绍三种：

1. Single Linkage

   Single Linkage方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

2. Complete Linkage

   complete Linkage的计算方法与Single Linkage相反，将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反，两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

3. Average Linkage

   Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大，但结果比前两种方法更合理。

分层算法的优缺点

优点：

1. 可以发现类的层次关系
2. 能帮助解决k-means不能解决的非凸数据

缺点：

1. 时间复杂度高
2. 贪心算法，一步错步步错

聚类模型评估

评价聚类方法分簇的最佳数量和分簇效果。

1.轮廓系数（silhouette coefficient）

轮廓系数综合考虑了内聚度和分离度两种因素。

样本i轮廓系数：

表示样本i与其所在簇内其他样本的平均距离，表示样本i与其他簇样本的平均距离

聚类总的轮廓系数SC为：

轮廓系数取值范围为[-1,1]，取值越接近1则说明聚类性能越好，相反，取值越接近-1则说明聚类性能越差。轮廓系数最高的簇的数量表示簇的数量的最佳选择。

轮廓系数使用案例

1. 准备数据

# 导包
import numpy as np
from sklearn import datasets
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.metrics import silhouette_score

# 生成数据
X, y = datasets.make_blobs(random_state=100)    # make_blobs 默认100样本，2个特征
print(X.shape)    # (100, 2)
plt.scatter(X[:, 0], X[:, 1], c=y)

生成的数据如下所示，从图中可以看出分为3簇最好：

准备数据.png

2. 计算轮廓系数

score = []
for i in range(2, 7):
    kmeans = KMeans(n_clusters = i)
    kmeans.fit(X)
    y_ = kmeans.predict(X)    # 预测类别 == 标签

    print('当聚类类别数量是%d的时候，评价指标的轮廓系数是：'%i, silhouette_score(X, y_))
    score.append(silhouette_score(X, y_))

plt.rcParams['font.sans-serif'] = ['KaiTi']   # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False  # 用来正常显示负号
plt.rcParams['font.size'] = 18  # 设置字体大小
plt.plot(range(2,7), score)
plt.xlabel('K值')
plt.ylabel('轮廓系数')

得到如下结果：

当聚类类别数量是2的时候，评价指标的轮廓系数是： 0.6380785232724551
当聚类类别数量是3的时候，评价指标的轮廓系数是： 0.8353147343303
当聚类类别数量是4的时候，评价指标的轮廓系数是： 0.692708669793985
当聚类类别数量是5的时候，评价指标的轮廓系数是： 0.5318434130364085
当聚类类别数量是6的时候，评价指标的轮廓系数是： 0.3814586763403103

轮廓系数.png

当k值为3时，轮廓系数最高，聚类效果最好。

2.兰德系数（adjusted rand index）

如果 C 是一个真实簇的标签分配， K 是簇的个数，我们定义a和b为：

• a，在 C 中的相同集合的与 K 中的相同集合中的元素对数
• b，在 C 中的不同集合与 K 中的不同集合中的元素对数

兰德系数为：

其中是数据集中可能的数据对的总数。取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。

兰德系数使用案例

1. 准备数据

数据仍用上文轮廓系数的数据。

2. 计算兰德系数

from sklearn.metrics import adjusted_rand_score    # 兰德系数

score2 = []
for i in range(2, 7):
    kmeans = KMeans(n_clusters = i)
    kmeans.fit(X)
    y_ = kmeans.predict(X)    # 预测类别 == 标签

    print('当聚类类别数量是%d的时候，评价指标的兰德系数是：'%i, adjusted_rand_score(y, y_))
    score2.append(adjusted_rand_score(y, y_))

plt.plot(range(2,7), score2)
plt.xlabel('K值')
plt.ylabel('兰德系数')

得到如下结果：

当聚类类别数量是2的时候，评价指标的兰德系数是： 0.5628321618378193
当聚类类别数量是3的时候，评价指标的兰德系数是： 1.0
当聚类类别数量是4的时候，评价指标的兰德系数是： 0.8704389719572353
当聚类类别数量是5的时候，评价指标的兰德系数是： 0.7187670100598754
当聚类类别数量是6的时候，评价指标的兰德系数是： 0.5789975932695749

兰德系数.png

当k为3是，兰德系数最大，聚类效果最好。

然而，得分不能保证随机标签分配(random label assignments)会获得接近零的值（特别是如果簇的数量与样本数量有着相同的规模排序）。

为了抵消这种影响，我们可以通过定义 adjusted Rand index 来低估(discount)随机标签的预期——，如下所示：