K均值聚类知识点大全：算法、应用、评估方法和缺点
点击上方关注，All in AI中国
作者：Imad Dabbura
聚类
聚类是一种最常用的探索性数据分析技术，用于直观地了解数据的结构。它可以定义为在数据中识别子组的任务，使得相同子组（集群）中的数据点非常相似，而不同集群中的数据点非常不同。换句话说，我们试图在数据中找到同质的子组，使得每个聚类中的数据点根据相似性度量（例如基于欧几里得的距离或基于相关性的距离）尽可能相似。决定使用哪种相似性度量是特定于应用程序的。
聚类分析是基于特性或样本来寻找样本子群的特性来完成的，其中我们试图基于样本来找到特性的子组。我们将在此处介绍基于特性的集群。聚类用于市场细分；我们试图“处罚”那些在行为或属性，图像分割/压缩等方面彼此相似的“客户”；我们尝试将相似区域组合在一起，根据主题记录来聚类等。
与监督学习不同，聚类被认为是一种无监督学习方法，因为我们不具备将聚类算法的输出与真实标签进行比较以评估其性能的基本真理。我们只想通过将数据点分组到不同的子组来尝试研究数据的结构。
在这篇文章中，我们将仅介绍Kmeans，由于其简单性，它被认为是最常用的聚类算法之一。
Kmeans算法
Kmeans算法是一种迭代算法，它试图将数据集划分为Kpre定义的不同的、非重叠的子组（集群），其中每个数据点只属于一个组。它尝试使集群间数据点尽可能地相似，同时使集群尽可能保持不同（远）。它将数据点分配给一个集群，使得数据点之间的平方距离与集群的质心（属于该集群的所有数据点的算术平均值）之和最小。我们在集群中的变化越小，数据点在同一集群中的同质性（相似）就越多。
kmeans算法的工作方式如下：
1. 指定集群K的数量。
2. 首先对数据集进行混洗，然后在不替换初始化质心的情况下随机选择质心的K数据。
3. 继续迭代，直到质心没有变化。即，向集群分配数据点不会改变为止。
l 计算数据点与所有质心之间的平方距离之和。
l 将每个数据点分配给最近的集群（质心）。
l 通过获取属于每个集群的所有数据点的平均值来计算集群的质心。
kmeans所采用的解决问题的方法被称为期望最大化。E步骤将数据点分配给最近的集群。M步骤是计算每个集群的质心。下面是我们如何以数学方式解决它的细分。
目标函数是：
其中数据点xi，如果它属于集群k，wik = 1;否则，wik = 0。 此外，μk是xi集群的质心。
这是由两个部分组成的最小化问题。我们首先在固定μk的情况下最小化J w.r.t. wik。然后我们固定wik的值最小化J w.r.t. μk。从技术上讲，我们首先区分J w.r.t.wik并更新集群分配（E-step）。 然后我们区分J w.r.t. μk并在上一步（M步骤）的集群分配后重新计算质心。因此，E步骤是：
换句话说，将数据点xi分配给最近的集群，该集群通过其与集群的质心的平方距离之和来判断。
M步骤是：
这意味着需要重新计算每个集群的质心以反映新的分配。
这里有几点需要注意：
l 由于包括kmeans的聚类算法使用基于距离的测量来确定数据点之间的相似性，因此建议将数据标准化为零且标准偏差为1，因为几乎任何数据集中的要素都具有不同的测量单位，例如年龄与收入。
l 由于kmeans迭代性质和算法开始时质心的随机初始化，不同的初始化可能导致不同的集群，因为kmeans算法可能陷入局部最优而不会收敛于全局最优。因此，建议使用不同的质心初始化运行算法，并选择产生较低平方距离总和的运行结果。
l 示例的赋值不会改变与集群内变异没有变化是一样的：
实现
我们将在这里使用简单的kmeans实现来说明一些概念。 然后我们将使用更高效的sklearn实现为我们处理许多事情。
应用
kmeans算法非常受欢迎，可用于各种应用，如市场细分、文档聚类、图像分割和图像压缩等。通常我们进行聚类分析的目标是：
1. 认为我们正在处理的数据结构非常有意义。
2. 如果我们认为不同子组的行为存在很大差异，则聚类然后预测将为不同子组建立不同模型的位置。这方面的一个例子是将患者聚集到不同的子组中，并为每个子组建立模型，以预测心脏病发作风险的概率。
在这篇文章中，我们将在两种情况下应用聚类：
l 间歇喷泉喷发（2D数据集）。
l 图像压缩。
关于间歇喷泉喷发的Kmeans
我们将首先在2D数据集上实现kmeans算法，看看它是如何工作的。该数据集有272个观测值和2个特性。这些数据涵盖了美国怀俄明州黄石国家公园的间歇泉喷发和喷发持续时间之间的等待时间。我们将尝试在数据点中找到K个子组并相应地对它们进行分组。以下是功能说明：
l 喷发（浮动）：以分钟为单位的喷发时间。
l 等待（int）：等待下一次喷发的时间。
让我们先绘制数据：
我们将使用这些数据，因为它是一个二维数据集，所以它很容易绘制并在视觉上发现聚类。很明显，我们有2个集群。让我们首先对数据进行标准化，然后在K = 2的标准化数据上运行kmeans算法。
上图显示了由它们所属的集群着色的数据的散点图。在这个例子中，我们选择K = 2。 符号'*'是每个集群的质心。我们可以将这两个集群视为不同情景下间歇泉有不同类型的行为。
接下来，我们将展示质心的不同初始化可能会产生不同的结果。 我将使用9个不同的random_state来更改质心的初始化并绘制结果。每个图的标题将是每次初始化的平方距离之和。
作为补充说明，该数据集被认为非常容易，并且在不到10次迭代中收敛。因此，为了看到随机初始化对收敛的影响，我将用3次迭代来说明这个概念。但是，在现实世界的应用程序中，数据集根本不是那么干净和漂亮！
如上图所示，我们最终只采用了两种不同的基于不同初始化的聚类方式。我们会选择平方距离最小的那个。
关于图像压缩的Kmeans
在这部分中，我们将实现kmeans来压缩图像。我们将要处理的图像是396 x 396 x 3。因此，对于每个像素位置，我们将有3个8位整数，用于指定红色，绿色和蓝色的强度值。我们的目标是将颜色数量减少到30，并仅使用这30种颜色来表示（压缩）照片。为了选择要使用的颜色，我们将在图像上使用kmeans算法，并将每个像素视为数据点。这意味着将图像从高度x宽度x通道重新整形为（高度*宽度）x通道，即，我们将在三维空间中具有396 x 396 = 156,816个数据点，这是RGB的强度。这样做将允许我们使用每个像素的30个质心来表示图像，并且将图像的尺寸显著减小6倍。原始图像尺寸为396×396×24 = 3,763,584位。但是，新的压缩图像将是30 x 24 + 396 x 396 x 4 = 627,984位。巨大的差异来自于我们将使用质心作为像素颜色的查找，并且将每个像素位置的大小减小到4位而不是8位。
从现在开始，我们将使用sklearn实现kmeans。这里有几点需要注意：
l n_init是运行具有不同质心初始化的kmeans的次数。将报告最佳结果。
l tol是用于声明收敛的集群内变异度量。
l init的默认值是k-means ++，它可以产生比质心随机初始化更好的结果。
我们可以看到原始图像和压缩图像之间的比较。压缩后的图像看起来接近原始图像，这意味着我们能够保留原始图像的大部分特性。对于较少数量的集群，我们将以较高的压缩率而牺牲图像质量。作为补充说明，这种图像压缩方法称为有损数据压缩，因为我们无法从压缩后的图像中重建原始图像。
评估方法
与监督学习相反，聚类分析没有可靠的评估指标，我们可以用它来评估不同聚类算法的结果。此外，由于kmeans需要k作为输入并且不从数据中学习它，因此在任何问题中我们应该具有的集群的数量没有正确的答案。有时领域知识和直觉可能会有所帮助，但通常情况并非如此。在聚类预测方法中，因为聚类用于下游建模，所以我们可以根据不同的K聚类评估模型的执行情况。
在这篇文章中，我们将介绍两个可能让我们对k有直观认识的指标：
1.肘法
2.轮廓分析
肘法
肘法使我们能够根据数据点与其指定集群的质心之间的平方距离（SSE）之和来了解一个k个集群的数量。我们在SSE开始变平并形成肘部的地方挑选k的位置。我们将使用间歇喷泉数据集并针对不同的k值评估SSE，并查看曲线可能形成弯曲和变平的位置。
上图显示k = 2不是一个好的选择。有时候仍然难以找出要使用的大量集群，因为曲线是单调递减的，并且可能没有显示任何弯曲点或者曲线开始变平的明显点。
轮廓分析
轮廓分析可用于确定集群之间的分离程度。对于每个样本：
l 计算同一集群（ai）中所有数据点的平均距离。
l 计算距离最近的集群（bi）中所有数据点的平均距离。
l 计算系数：系数可以取区间[-1,1]中的值。
l 如果它是0 - >样本非常接近相邻的集群。
l 如果它是1 - >样本远离相邻的集群。
l 如果它是-1 - >样本被分配给错误的集群。
因此，我们希望系数尽可能大并且接近1，以得到一个良好的集群。我们将再次使用geyser数据集，因为运行轮廓分析的成本更低，实际上很可能只有两组数据点。
如上图所示，n_clusters = 2的最佳平均轮廓得分约为0.75，所有聚类均高于平均值，这表明它实际上是一个不错的选择。此外，轮廓图的“厚薄”表示每个集群的大小。该图显示聚类1的样本几乎是聚类2的两倍。然而，随着我们将n_clusters增加到3和4，平均轮廓得分分别急剧下降到0.48和0.39左右。此外，轮廓图的厚度开始显示出大的波动。底线是：良好的n_clusters将具有远高于0.5的轮廓平均得分以及所有聚类高于平均得分。
缺点
如果集群具有球形形状，则Kmeans算法可以很好地捕获数据结构。它总是试图在质心周围构造一个漂亮的球形。这意味着，在集群具有复杂几何形状的那一刻，kmeans在聚类数据方面做得很差。我们将举例说明kmeans表现不佳的三种情况。
首先，kmeans算法不允许远离彼此的数据点共享同一个集群，即使它们显然属于同一个集群。下面是两条不同水平线上的数据点示例，说明了kmeans如何尝试将每条水平线的一半数据点组合在一起。
Kmeans认为点'B'更接近点'A'而不是点'C'，因为它们具有非球形形状。因此，点'A'和'B'将位于同一集群中，但点'C'将位于不同的集群中。请注意，单链接聚类方法是正确的，因为它不会分离类似的点。
其次，我们将生成具有不同均值和标准差的多元正态分布生成数据。因此，我们将有3组数据，其中每组由不同的多元正态分布（不同的平均值/标准偏差）生成。其中的一组将拥有比其他两组更多的数据点。接下来，我们将对K = 3的数据运行kmeans，看看它是否能够正确地聚类数据。为了使比较更容易，我将首先根据它来自的分布绘制彩色数据。然后我将绘制相同的数据，但现在根据已分配的集群进行着色。
看起来kmeans无法正确找出集群。由于它试图最小化集群的内部变化，因此它对较大集群的权重比较小集群更大。换句话说，较小聚类中的数据点可以远离质心，以便更多地聚焦在较大的聚类上。
最后，我们将生成具有复杂几何形状的数据，并在两个数据集上测试kmeans。
正如预期的那样，kmeans无法找出两个数据集的正确聚类。 但是，如果我们使用内核方法，我们可以帮助kmeans完美地聚类这些数据集。我们的想法是将数据转换为更高维度的表示，使其线性可分（与我们在SVM中使用的想法相同）。不同类型的算法在光谱聚类等场景中运行良好，见下文：
结论
Kmeans聚类是最流行的聚类算法之一，通常是从业者在解决聚类任务时应用的第一件“工具”，用以了解数据集的结构。kmeans的目标是将数据点分组到不同的非重叠子组中。当集群具有一种球形时，它的确做得很好。然而，当集群的几何形状偏离球形时，它就会受到影响。此外，它也没有从数据中学习集群的数量，并且需要预先定义它。要成为一名优秀的从业者，最好了解算法/方法背后的假设，以便你对每种方法的优缺点有一个很好的了解。这将帮助你决定何时使用某种方法以及在何种情况下使用。在这篇文章中，我们介绍了与kmeans相关的优势，劣势和一些评估方法。
以下是主要结论：
l 应用kmeans算法时缩放/标准化数据。
l 肘法在选择集群数时通常不起作用，因为误差函数对于所有kmeans是单调递减的。
l Kmeans为更大的集群提供了更多的权重。
l Kmeans假设球形的集群（半径等于质心和最远数据点之间的距离），并且当集群具有不同的形状（例如椭圆集群）时不能很好地工作。
l 如果集群之间存在重叠，则kmeans不具有针对属于重叠区域的不确定性的内在度量，以便分配每个数据点的集群。
l 即使无法聚集数据（例如来自均匀分布的数据），Kmeans仍可以对数据进行聚类。
