机器学习-数据聚类与分群

0

聚类就是将样本划分为由具有类似的特征组成的多个类。在实际分析一堆数据时,往往会只给出这些数据的特征变量,但不知道这些数据应该如何分类,这就需要对已有数据根据性质分组。

聚类有两种常用的算法:KMeans 和 DBSCAN 。

KMeans算法

算法原理

KMeans 算法是最简单、最容易理解的聚类算法,其中 K 代表数据,Means 代表每个类别内样本的均值。顾名思义,它是用数据的均值对其分类。

例如,对于如下散点的分布,可以比较清晰地看出来它大致聚为四个集群:

之所以可以看出它们形成了四个集群,因为每个集群都围绕着一个中心点分布,如果点离这个中心的距离更近,那么就容易看出该点属于这个集群。

这就是 KMeans 算法的原理,KMeans 算法以距离作为样本间相似度的度量标准,将距离相近的样本分配至同一个类别。通常可以采用两点间的直线距离(欧几里得距离)来度量各样本间的距离。

KMeans 算法最重要的就是计算中心点。直接计算中心点的话计算量很大,而且处理较为复杂。因此,KMeans 使用一种称为期望最大化(expectation-maximization, E-M)的算法来处理这个问题。期望最大化算法应用于数据科学的很多场景中,KMeans 是该算法的一个非常简单并且易于理解的应用。

期望最大化算法包含以下步骤:

  1. 期望步骤(E-step):将样本点分配给最近的集群中心点代表的类别,更新每个点是属于哪一个集群的期望
  2. 最大化步骤(M-step):将集群中心点设置为该集群所有点坐标的平均值,得到集群关于中心点拟合函数最大化时对应的坐标

最开始的中心点可以通过在现有点中随机选取得到。每一次重复期望最大化步骤都将会得到更好的聚类效果,直到前后两次分类结果没有差别为止。

下图展示了 KMeans 聚类时的可视化迭代过程:

也可以借助可视化网站 https://www.naftaliharris.com/blog/visualizing-k-means-clustering/ 交互式查看 KMeans 算法聚类的过程。该网站还给出了许多其它算法的交互式演示,包括接下来介绍的 DBSCAN 聚类算法。

代码实现

以上介绍了 KMeans 的原理。在实际应用中,可以直接使用 Scikit-Learn 提供的工具完成 KMeans 聚类,它与 Scikit-Learn 其它工具的接口是一致的。KMeans 模型的主要参数 n_clusters 即 K 值,表示样本聚成的类数:

from sklearn.cluster import KMeans
kms = KMeans(n_clusters=7)
kms.fit(points)
KMeans(n_clusters=7)

当聚类完成后,可以使用 .labels_ 属性获取聚类结果,.cluster_centers_ 属性获取每一个类别的中心点。

以下将所有样本点和聚类的中心点以散点图的形式表现出来,并根据聚合成的不同类别以不同颜色区分结果:

plt.scatter(X[:, 0], X[:, 1], c=cluster.labels_, cmap='Wistia')
centers = cluster.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='b', s=200, alpha=0.5)

结果整体来说划分良好。

结果分析

由于 KMeans 算法是一种期望最大化算法,它会在每一步中改进结果以向着更优解的方向移动,但是这并不保证可以到达全局最优解。初始中心点的选择会在较大程度上影响聚类结果,某些随机值带来的初始中心点可能会导致仅收敛到局部最优解,但整体聚类结果并不理想:

不好的随机种子带来的不好收敛结果

基于此,Scikit-Learn 的 KMeans 模型提供了 n_init 参数,用于多次使用不同的随机种子运行模型,并选取最好的结果。该参数的默认值是 10 ,即从 10 次不同的测试中选择最好结果。

多次运行还需要分析哪个是最好结果,评价 KMeans 模型的一项常用的指标是各个点到聚类中心距离的平方和,称为惯性(inertia)或 WSS(Within-Cluster-Sum of Squared)。在聚合成相同数量的集群时,WSS 越小,则说明模型越好。在建立模型后,可以使用 .inertia_ 属性检查当前模型的 WSS 值。

下图对比了不同聚类结果下的 WSS 值:

在之前的模型建立中,通过绘制散点图来观察数据大致可以被聚合成的类别数量。但在没有提前指定数据类别数量的情况下,如果数据维度很高或者数据量过大,那么就无法以直观的形式检查它可能的类别数量。

有些时候即便以可视化的形式展现出来,也未必能很好地判断聚合类别数。例如,考虑以下数据点集合在不同聚类数下的结果:

检查结果可以发现,当聚合成 2 、3 、4 类时的结果似乎都有一定道理。

可以使用 WSS 来判断最好的结果,但是随着聚类个数的增加,聚类中心也变多了,各个点到聚类中心的距离肯定更近。如果将不同聚类数以及对应的最好的 WSS 值绘制在图表上,会得到以下折线:

在折线上通常会出现一个拐点,这个拐点称为“肘”(elbow)。在肘部对应的 K 值之前,每增加一个分类数可以使 WSS 快速下降;但在肘部之后,更多的分类数对 WSS 的影响并不明显。在不清楚合适分类数的情况下,肘部对应的 K 值是一个不错的选择。

如果将折线的两端连成一条直线,那么肘部在 \\( y \\) 方向上离这条直线的距离一般最远。因此,可以使用以下代码计算肘部对应的 K 值:

slope = (WSS[0] - WSS[-1]) / (Krange[0] - Krange[-1])
intercept = WSS[0] - slope * Krange[0]
y = Krange * slope + intercept
best_k = Krange[(y - WSS).argmax()]

这种方式比较简单,但结果比较粗糙。一种更精确但也更复杂的方法是使用轮廓系数(silhouette value)。样本点轮廓系数的计算公式为:

\\[ s(i) = \frac{b(i) - a(i)}{\max \{ a(i), b(i) \}} \\]

其中 \\( a(i) \\) 是样本 \\( i \\) 与同一集群中其它样本的平均距离,\\( b(i) \\) 是平均最近集群距离(即到不包括自身集群的最近集群实例的平均距离)。轮廓系数的取值范围是 \\( [-1, +1] \\) ,该值越接近 +1 ,表示对应的样本点越好地位于自身的集群中,并且远离其它集群;接近 0 的轮廓系数表示它接近一个集群的边界;接近 -1 的系数意味着样本点可能分配给了错误的集群。

可以使用以下代码计算轮廓分数(所有实例的平均轮廓系数):

from sklearn.metrics import silhouette_score
silhouette_score(X, cluster.labels_)
0.320434040824261

将不同聚类数的轮廓分数以折线图的形式绘制出来,结果为:

从结果中可以看到,虽然使用肘点判断结果为 \\( k=3 \\) 时效果最好,但轮廓系数判断该值使得一个集群可能会被不合理地拆分,使得许多样本点落在了它们的分界线上,说明 \\( k=2 \\) 可能是一个更好的集群数。

Scikit-Learn 还提供了 KMeans 算法的一个变种,它在每次迭代中采用随机抽样的方法选择小批量的数据子集,在减小计算时间的同时能够尽可能的拟合原始的数据。这在数据集过大时可以显著提升算法的速度,并且可以处理内存无法容纳的超大数据集。可以使用 MiniBatchKMeans 类调用该算法,使用方式和 KMeans 类是一致的:

from sklearn.cluster import MiniBatchKMeans
%%timeit
cluster = KMeans(n_clusters=12)
cluster.fit(X)
744 ms ± 81.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%%timeit
cluster = MiniBatchKMeans(n_clusters=12)
cluster.fit(X)
392 ms ± 74.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

KMeans 是一种经典的聚类算法,它适用于任意维度数据的聚类,但在聚类时需要提前知道或判断 K 值。KMeans 的聚类依据是更接近的集群中心点,这使得在实际聚类时每个集群边界总是线性的。使用 Voronoi 图可以很清晰地表现这一原理,图中落在由中心点确定的多边形内的样本会被归为该类:

由于只能确定线性聚类边界,当集群呈现非线性的复杂形状时,KMeans 往往会不起作用,例如以下数据:

KMeans 算法无法处理非线性边界

这时候就不能使用 KMeans 了。不过有一种算法可以很好地处理这种形式的聚类问题:DBSCAN。

DBSCAN算法

算法原理

DBSCAN 算法全称 Density-Based Spatial Clustering of Applications with Noise ,是一种以密度为基础的空间聚类算法,可以用密度的形式发现任意形状的集群。该算法将集群定义为具有足够密度的连续区域,因此可以处理任意形状的边界,如下图所示:

DBSCAN 算法的基本步骤为:先随机选取一个点,以该样本点为圆心,按照设定的半径作圆。如果圆内的样本数大于等于设定的阈值(密度),则将这些样本归为一类。接着选定圆内的其它样本点,继续作圆;如果某个圆内的样本数小于阈值,则放弃该圆的绘制。不断重复以上步骤直到没有可画的圆为止,并将这些圆内的样本点归为一个集群。

下图展示了该算法的原理:

注意,以上两图内都存在不属于高密度集群内的点(游离点),因此这也是 DBSCAN 算法的优势之一,即可以使用密度的概念剔除不属于任一类别的噪点。

代码实现

DBSCAN 算法的实现与 KMeans 算法遵循同样的接口。它可以调整的参数有 eps(作圆的半径)和 min_samples(圆内的最少样本数),以此来控制密度:

from sklearn.cluster import DBSCAN
cluster = DBSCAN(eps=0.2, min_samples=5)
cluster.fit(X)
DBSCAN(eps=0.2, min_samples=5)

聚类的结果也可以通过 .labels_ 属性检查。之前说过 DBSCAN 算法可以判断噪点的存在,噪点在 .labels_ 结果内对应的标签均为 -1 ,因此可以用类型以下的形式在散点图中标出噪点,效果与上文展示的图片类似:

plt.scatter(X[:, 0][cluster.labels_ == -1], X[:, 1][cluster.labels_ == -1],
            s=30, c='g', marker='x')

DBSCAN 的结果还包含了 .components_ 属性,可以得到半径内包含足够样本的核心实例本身,或者可以使用 .core_sample_indices_ 属性获取它们的索引。

虽然 DBSCAN 的接口遵循 Scikit-Learn 接口的标准,但它没有 .predict() 方法。这是由于聚类算法不一定适合用于分类:有时候预测一个新样本分类的难度可能和重新聚类差别不大,尤其是 DBSCAN 可能出现同时被划分到两个类别且难以判断哪个是更好的情况。因此聚类完成后可以将结果应用到其余的分类器中,例如 KMeans 算法的思路就和 \\( K=1 \\)K 近邻算法很像。

结果分析

和 KMeans 一样,DBSCAN 的参数 epsmin_samples 也并不好直接确定。若密度选取过小,两个邻近集群可能被合并;若密度选择过大,则一个集群可能会被拆分。

参数 min_samples 可以使用以下的原则确定:

\\[ \text{min points} \geq \text{dim} + 1 \\]

eps 的值可以使用绘制 K-距离曲线的方式得到。K-距离表示每个样本第 K 个最近邻样本距离。将数据集所有点对应的 K 近邻距离按照降序方式排序,便可以绘制出 K 距离图线。

可以通过以下方式得到所有样本点排序后的 K-距离:

from sklearn.neighbors import NearestNeighbors

neighbors = NearestNeighbors(n_neighbors=4)
distances, indices = neighbors.fit(X).kneighbors(X)

distances = np.sort(distances, axis=0)[:, 1][::-1]

曲线图明显拐点位置为对应较好的参数。在本示例中,eps 可以取 1.0 左右。

最后要注意的是,虽然这种方式比起随机选择的参数具有一定的合理性,但是得到的参数仍然未必是合理的。

下图对比了 KMeans 算法与 DBSCAN 算法对同一批数据的聚类结果。对比结果可以发现:DBSCAN 算法在聚类时可以发现任意形状的簇将其聚为一类,而 KMeans 算法只是机械地将距离近的数据归到同一组:

图片来源于网络

总的来说,DBSCAN 算法不需要事先知道集群数,并且可以发现任意形状的集群,初始中心点选择也不影响聚类结果。但它的特点决定了不适用于密度变化较大的数据,参数也难以确实最优值。因此如果难以通过可视化等方式检查数据并确定合适的参数的话,尽量还是谨慎选用该算法。

示例:图像颜色聚合

接下来通过一个具体的示例介绍聚类算法的使用。这里通过聚类算法分析一张图片的主要颜色组成,将其提取出来并用于压缩图像颜色。

一个图像由若干像素点组成,一般在网络上传输的图像每一个像素点都使用 RGB 色值表示,每一个色值占据一个字节。那么这样的一个图像可以使用形状为 (image_height, image_width, 3) 的数组描述。可以使用以下代码获取这样的数值:

from PIL import Image
image = np.array(Image.open(r'images\image-03.jpg'))

考虑到这里只关注像素的 RGB 通道,对像素的位置不感兴趣,因此可以将其转为自变量为 RGB 值的二维数据:

X = image.reshape(-1, 3)

然后利用以上数据建立聚类模型。由于自变量的密度不好确定且可能改变,并且为了便于使用中心值描述每一类的结果,在已知 K 值的情况下,使用 KMeans 是一个更好的选择:

model = KMeans(n_clusters=6)
model.fit(X)
colors = model.cluster_centers_
print(colors)
[[130.67128133 83.12713456 79.94169614] [ 3.56554958 26.66450421 36.41714522] [219.65209098 126.73938314 97.28939034] [191.28186172 90.94572996 72.60806672] [ 67.96981169 62.53358817 67.36300707] [241.93716223 157.78285689 119.45559918]]

以下展示了部分示例图片聚合得到的主要颜色值:

可以根据结果,将一批图像通过二次聚类的方式按颜色分类,还可以用于将图像包含的颜色压缩。颜色压缩也很简单,只需要将每一类颜色都填充其中心点的色值即可:

segmented_image = model.cluster_centers_[model.labels_]   \
                     .reshape(image.shape)              \
                     .astype(np.uint8)
plt.imshow(segmented_image)
<matplotlib.image.AxesImage at 0x25a800741f0>

以下对比了同一图像在不同颜色数下图像压缩的结果:

京ICP备2021034974号
contact me by hello@frozencandles.fun