数据科学家必须掌握的五种聚类算法
原创2023-02-17爱分享AI技术大本营
编译| AI技术大本营
参与|常陆
编辑|明明
【AI技术大本营介绍】聚类是一种将数据点按照一定的规则进行分组的机器学习技术。给定一组数据点，我们可以使用聚类算法将每个数据点分类到特定的簇中。理论上，属于同一类的数据点应该具有相似的属性或特征，而不同类的数据点应该具有非常不同的属性或特征。聚类是一种无监督学习的方法，也是许多领域统计数据分析的常用技术。
在数据科学中，我们可以使用聚类分析来获得一些有价值的信息。该方法是在应用聚类算法时检查数据点将属于哪个类。现在，我们来看看数据科学家需要掌握的五种常见聚类算法及其优缺点！
k君
价值聚类
K-Means可能是最知名的聚类算法，没有之一。这种算法在许多数据科学和机器学习入门课程中都有讲授。而且这个算法的代码很容易理解和实现！看下图就能明白了。
k均值聚类
1.首先，我们选择一些类/组来使用，并随机初始化它们各自的中心点(质心)。要计算使用的分类(类)数量，最好的方法是快速查看数据，并尝试确定有多少不同的组。中心是一个向量，它到每个数据点的向量长度是相同的，在上图中用“X”表示。
2.通过计算点和每个聚类中心之间的距离，对每个数据点进行分类。根据最小距离，将该点分类到与中心点对应的簇中。
3.根据这些分类的点，我们重新计算所有向量的平均值，以确定新的中心点。
4.重复上述步骤一定次数的迭代，或者直到聚类的中心点在迭代之间变化很小。也可以选择随机初始化聚类中心几次，然后选择看起来效果最好的数据，再重复上述步骤。
K-Means算法的优点是速度非常快，因为我们所做的只是计算点与聚类中心的距离；这已经是很小的计算了！因此，它的线性复杂度为O(n)。
然而，K-Means算法也有一些缺点。首先，您必须手动选择有多少个集群。这是一个很大的缺点。理想情况下，我们希望使用一个聚类算法来帮助我们找出有多少个聚类，因为聚类算法的目的是从数据中获得一些有用的信息。K-means算法的另一个缺点是从随机选取的聚类中心开始，导致算法每次运行的聚类结果都不一样。所以这种算法的结果可能是不可重复的，缺乏一致性。其他聚类算法的结果会更一致。
K-Medians是另一种类似于K-Means的聚类算法。它通过计算类中所有向量的中值而不是平均值来确定聚类的中心。这种方法的优点是对数据中的离群点不敏感，但在大数据集聚类时要慢得多。造成这种现象的原因是每次迭代这个方法都需要对数据进行排序。
Mean-Shift聚类算法是一种基于滑动窗口的聚类算法。也可以说是基于质心的算法，也就是说它通过计算滑动窗口内的平均值来更新中心点的候选框，从而找到每个聚类的中心点。然后，在剩余的处理阶段，过滤这些候选窗口，以消除相似或重复的窗口，并找到最终的中心点及其对应的聚类。看下图。
单滑动窗口均值漂移聚类算法
1.为了说明均值漂移算法，我们可以考虑二维空间中的一组点，如上图所示。我们从以点C为中心(随机选择)和以半径r为中心的平滑移动窗口开始。Mean-shift可以被视为轮廓算法。在每次迭代中，它可以将核函数(平滑移动窗口)移动到更高密度的区域，直到它收敛。
2.在每次迭代中，通过将中心点移动到窗口中点的平均值，滑动窗口被移动到更高密度的区域(因此得名)。滑动窗口中的数据密度与其内部点数成比例。当然，通过移动窗口内点的平均值，它(滑动窗口)会逐渐向点密度较高的区域移动。
3.我们继续按照平均值移动滑动窗口，直到找不到移动方向，这样滑动窗口就可以容纳更多的点。看看上图的动画效果；直到滑动窗口中的密度(即窗口中的点数)不再增加，我们才停止移动圆圈。
4.从步骤1到步骤3的过程是由许多滑动窗口完成的，直到所有的点都可以定位到相应的窗口中时才停止。当多个滑动窗口重叠时，该算法保留点数最多的窗口。所有最终数据点都根据它们的滑动窗口进行分类。
下图显示了所有滑动窗口从开始到结束的整个移动过程。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。
均值漂移聚类的整个过程
与K-means聚类算法相比，Mean-shift算法不需要选择聚类数，因为它自动找到几个类型。这是其他算法无法比拟的巨大优势。而且这种算法的聚类效果也非常理想。在自然数据驱动的情况下，可以直观地展示出来，符合其意义。该算法的缺点是窗口大小/半径“r”是固定的。
基于密度的噪声应用空间聚类
DBSCAN是一种基于密度的聚类算法，类似于Mean-shift算法，但它有一些显著的优点。让我们通过看下面这张奇怪的图来开始理解算法。
DBSCAN笑脸聚类
1.DBSCAN算法从一个没有被访问过的任意数据点开始。这个点的邻域由距离定义(即这个点的距离内的所有点都是邻域点)。
2.如果邻域中有足够多的点(根据minPoints的值)，则聚类过程开始，并且当前数据点成为新聚类中的第一个点。否则，该点将被标记为噪声(稍后，该噪声点可能会成为聚类的一部分)。在这两种情况下，该点将被标记为“已访问”。
3.对于新群集中的第一个点，其距离邻域中的点也将成为同一群的一部分。这个过程使邻域内的所有点都属于同一个聚类，然后对刚刚加入到该聚类的所有新点重复上述过程。
4.重复第2步和第3步，直到确定簇中的所有点，即访问并标记簇的邻域中的所有点。
5.一旦我们完成了当前的聚类，我们可以搜索和处理新的未访问点，然后我们可以进一步发现新的聚类或噪声。重复上述过程，直到所有点都被标记为已访问。因为已经访问了所有点，所以每个点都被标记为属于聚类或噪声。
与其他聚类算法相比，DBSCAN有很多优点。首先，它根本不需要确定聚类数。与均值漂移算法不同，当数据点差异很大时，它们将被简单地引入到聚类中，DBSCAN可以将异常值识别为噪声。此外，它还可以发现任何大小和形状的星团。
DBSCAN算法的主要缺点是当数据簇密度不均匀时，其效果不如其他算法。这是因为当密度变化时，用于识别相邻点的距离阈值和minPoints的设置会随着聚类而变化。这个缺点在处理高维数据时也会出现，因为距离阈值很难估计。
使用高斯混合模型的期望最大化聚类
K-Means算法的主要缺点之一是使用聚类中心的平均值过于单一。通过查看下面的图例，我们可以了解为什么它不是使用平均值的最佳方法。在左边，人眼可以明显看出，具有相同平均值的数据中心点是半径长度不同的两个圆形簇。而K-Means算法无法解决这类数据问题，因为这些聚类的均值非常接近。K-Means算法在聚类不圆的情况下也是无效的，也是因为把均值作为聚类中心。
K-Means算法的两个失败案例
与K-means算法相比，高斯混合模型可以处理更多的情况。对于GMM，我们假设数据点是高斯分布；这是一个限制性较小的假设，而不是用均值来表示它们是圆的。这样，我们就有两个参数来描述聚类的形状：均值和标准差！以二维为例，这意味着这些群集可以是任何类型的椭圆(因为GMM在X和Y方向上都有标准偏差)。因此，每个高斯分布由单个聚类指定。
为了找到每个聚类的高斯参数(例如，均值和标准差)，我们将使用期望最大化(EM)的优化算法。请看下面的图表，可以作为匹配簇高斯图的解释。然后，我们将使用GMM完成期望最大化聚类过程。
使用GMM的EM聚类
1.我们首先选择聚类的个数(比如K-Means)，然后随机初始化每个聚类的高斯分布参数。通过快速查看数据，您可以尝试为初始参数提供一个更好的猜测。但是，请注意，这并不是100%必要的，因为算法可以快速优化它，即使是从一个差的高斯分布。
2.给定每个分类的高斯分布，计算每个数据点属于特定分类的概率。一个点离高斯中心越近，就越有可能属于该簇。在使用高斯分布时，这应该是非常直观的，因为我们假设大部分数据更接近于聚类的中心。
3.基于这些概率，我们为高斯分布计算一组新的参数，以便我们可以最大化数据点在聚类中的概率。我们使用数据点位置的加权和来计算这些新参数，其中权重是数据点属于该特定聚类的概率。为了更直观地解释这一点，我们可以看看上图，尤其是黄色的星团。在第一次迭代中，分布是随机开始的，但我们可以看到大多数黄色点都在分布的右侧。当我们计算按概率加权的和时，即使靠近中心的点大部分都在右边，通过分布的均值自然会逼近这些点。我们还可以看到，大部分据点都是“从右上到左下”。因此，通过改变标准差的值，我们可以找到一个更适合这些点的椭圆，以最大化概率权重之和。
4.重复步骤2和3，直到收敛，即迭代中分布基本没有变化。
使用GMM方法有两个重要的优点。首先，在聚类协方差方面，GMM比K-Means灵活得多。因为使用了标准偏差参数，所以聚类可以呈现任何椭圆形状，而不是局限于圆形。K-mean算法实际上是GMM的特例，即每个聚类的协方差在所有维度上都接近于0。其次，因为GMM使用概率，每个数据点可以有多个聚类。因此，如果一个数据点位于两个重叠聚类的中间，我们可以简单地定义它的类，即属于类1的概率为x %，属于类2的概率为y %。也就是说，GMM支持混合班。
内聚层次聚类
聚类算法实际上分为两类：自顶向下或自底向上。自底向上算法首先将每个数据点视为一个单独的聚类，然后不断合并(或聚集)成对的聚类，直到所有的聚类合并成一个包含所有数据点的聚类。因此，自底向上的层次聚类被称为合成聚类或HAC。这个集群的层次结构可以用树(或树形图)来表示。树根是收集所有样本的唯一聚类，树叶是只有一个样本的聚类。在进入算法步骤之前，请检查下图。
合成聚类
1.我们首先把每个数据点当作一个单独的聚类，也就是说，如果我们的数据集中有X个数据点，那么我们就有X个聚类。然后，我们选择一个距离度量来度量两个聚类之间的距离。例如，我们将使用平均相关性度量，它将两个聚类之间的距离定义为第一个聚类中的数据点与第二个聚类中的数据点之间的平均距离。
2.在每次迭代中，我们将两个集群合并成一个集群。选择具有最小平均相关值的两个聚类进行合并。根据我们选取的距离测度，这两个聚类之间的距离最小，所以最相似，应该全部合并。
3.重复步骤2，直到我们到达树根，也就是说，我们只有一个包含所有数据点的聚类。这样，我们就可以选择最终需要多少个集群。方法是选择什么时候停止合并簇，也就是什么时候停止建树！
分层聚类不需要我们指定聚类的数量。我们甚至可以在构建树时选择看起来最好的簇的数量。此外，该算法对距离测量的选择不敏感。与其他距离度量选择很重要的聚类算法相比，该算法下的所有距离度量方法都表现良好。当基础数据有层次结构，想还原层次结构时，层次聚类算法可以达到这个目的；其他聚类算法做不到这一点。与K-Means和GMM的线性复杂度不同，层次聚类的这些优点是以低效率为代价的，即它具有O(n3)时间的复杂度。
结论
数据科学家应该掌握的5大聚类算法！感谢Scikit Learn Toolbox，我们可以用非常漂亮的可视化图形展示聚类算法的更多优秀结果。
作者|乔治赛义夫
原始链接
https://towards data science . com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d 136 ef 68
微信扫一扫
关注这个微信官方账号
