5种算法玩转聚类分析

聚类是一种涉及数据点分组的机器学习技术。给定一组数据点，我们可以使用聚类算法将每个数据点分类到特定的组中。理论上，同一组中的数据点应具有相似的属性或特征，而不同组中的数据点应具有较大差异的属性或特征。聚类是无监督学习的一种方法，也是用于许多领域中统计数据分析的常用技术。

在数据科学中，通过使用聚类分析，查看数据点在应用聚类分析算法时所对应的分类，从而挖掘出数据隐藏的信息。今天，我们将讨论数据科学家需要了解的5种流行聚类算法以及它们的优缺点！

1.K-Means聚类

K-Means可能是我们最熟知的聚类算法之一。它在很多介绍性的数据科学和机器学习课程中出现过。因为很容易理解并且容易用代码实现，如下所示。

K-Means Clustering

1、我们首先选择若干簇，并随机初始化他们各自的中心点。为了计算出需要使用的簇的数量，最好是快速地浏览数据并尝试识别所有独特的分组。中心点是与数据点矢量有相同维数的向量，如上图中的“X”。

2、对于每个数据点，通过计算该点与每个簇中心点之间的距离，按照距离最小的原则进行分类，将该点归类到距离最近的簇中。

3、基于这些分类点，重新计算簇中的所有向量的平均值，确定新的中心点。

4、重复迭代这些步骤若干次，或者直到各组的中心点在两次迭代之间变化不大时停止迭代。也可以选择随机初始化簇中心若干次，然后选择效果最好的分类结果。

K-Means的优点是运算速度非常快，因为我们所做的只是计算点和簇中心之间的距离（这是非常少的计算！），因此它有线性复杂度O（n）。

另一方面，K-Means有两个缺点。首先，必须设置簇的数量，这对聚类算法来说并不简单。我们希望它自己找出这些答案，因为聚类算法目的就是从数据中获得隐藏信息。此外，K-Means算法从随机选择的聚类中心开始执行，它可能在算法的不同运行过程中产生不同的聚类结果。这可能会导致结果无法复现且缺乏一致性。而其他聚类方法则相对具有较高的一致性。

K-Medians是与K-Means相关的另一种聚类算法，不同之处在于我们使用各簇的中位数向量来重新计算簇中心点，而不是通过均值来重新计算。该方法对异常值不敏感（因为使用了中位数的原因），但对于较大的数据集运算速度要慢很多，因为在计算中位数向量时，需要在每次迭代时进行排序。

2.均值漂移聚类

Mean-Shift聚类是基于滑动窗口的算法，试图找到数据点的密集区域。这是一种基于质心的算法，意味着其目标是定位每个簇的中心点，通过将滑动窗口的均值点作为候选点来迭代更新中心点。在后处理阶段将消除近似重复的窗口，最终形成一组中心点及其相应的簇。如下所示。

Mean-Shift Clustering for a single sliding window

1、为了解释Mean-Shift，我们将考虑如上图所示的二维空间中的一组点。我们从圆形滑动窗口为核心开始，其以C点（随机选择）为中心并以r半径。Mean-Shift是一种爬山算法（局部择优的方法），它在每个步骤中将核迭代地转移到更高密度的区域，直到收敛。

2、在每次迭代中，通过将中心点移动到窗口内所有点的平均值位置（因此得名），将滑动窗口中心移向密度较高的区域。滑动窗口内的密度与其内部的点数成正比。通过转换到窗口内点的平均值位置，窗口将逐渐移动到有着更高点密度的区域。

3、我们继续根据平均值移动滑动窗口，直到无法通过移动使内核中容纳更多的点。如上图所示; 我们不断移动这一圆形，直到密度（即窗口中的点数）不再增加。

4、步骤1至3的这个过程用许多滑动窗口完成，直到所有点均落到某一个窗口内。当多个滑动窗口重叠时，保留包含最多点的窗口。然后根据数据点所在的滑动窗口将其聚为一类。

下图显示了包含所有滑动窗口的整个过程。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。

The entire process of Mean-Shift Clustering

与K-means聚类相比，Mean-Shift的最大优势就是可以自动发现簇的数量而不需要人工选择。簇的中心向最大密度点聚合的事实也是非常令人满意的，因为它可被非常直观地理解并很自然地契合数据驱动。当然不足就是窗口大小/半径“r”的选择可能是非平凡的。

3.具噪声基于密度的空间聚类算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，类似于Mean-Shift，但具有一些显著的优点。如下图所示。

DBSCAN Smiley Face Clustering

1、DBSCAN以任何尚“未访问”过的任意起始数据点开始。 这个点的邻域用距离epsilon ε 表示（ε距离内的所有点都是邻域点）。

2、如果在该邻域内有足够数量的点（根据minPoints阈值判断），则开始聚类过程，并将当前数据点设为新簇中的第一个点。否则，该点将被标记为噪声（稍后这个噪声点可能会成为簇的一部分）。 在这两种情况下，该点都被标记为“已访问”。

3、对于新簇中的第一个点，ε邻域内的点也成为同一个簇的一部分。之后对已经添加到簇中的所有新点重复执行这一过程，即将ε邻域中的所有点归到同一个簇内。

4、重复步骤2和3的这个过程直到簇中的所有点都被确定，即簇内所有点的ε邻域内点都已“被访问”和标记过。

5、当我们完成了对当前簇的操作，则会检索和处理一个新的未访问点，这样可发现更多的集群或噪声。重复此过程，直到所有点都被标记为“已访问”。由于所有点已经被访问完毕，每个点都被标记为归属于一个簇或是噪声。

与其他聚类算法相比，DBSCAN有很多优点。 首先，它根本不需要预先设定簇的数量。它还能将异常值识别为噪声，而不是像Mean-Shift那样将数据点简单地扔进一个簇中，不管数据之间是否有很大的差异。另外，它能够很好地找到任意大小和任意形状的簇。

DBSCAN的主要缺点是当簇的密度不同时，DBSCAN的性能不如其他的聚类算法。因为当密度变化时，用于识别邻近点的距离阈值ε和minPoints也将随着簇的变化而变化。同样对较高维数据的处理时也会存在距离阈值ε难以估计的缺陷。

4.高斯混合模型的期望最大化聚类

K-Means的主要缺点之一是其简单地使用了平均值作为簇的中心。通过下图，我们可以看出为什么这不是最佳方式。在左侧，人的眼睛可以明显地看到有两个半径不同的圆形簇以相同的平均值为中心。 由于这些簇的均值非常接近，导致K-Means无法处理这个问题。 K-Means在簇不是圆形的情况下也会失效，这也是因为它使用均值作为簇的中心。

Two failure cases for K-Means

高斯混合模型（GMMs）相比于K-Means来说有更多的灵活性。 对于GMMs，我们假设数据点是服从高斯分布的（对于用均值进行聚类，这一假设是个相对较弱的限制）。 这样，我们有两个参数来描述簇的形状：均值和标准差！ 以二维为例，这意味着簇可以采用任何类型的椭圆形（因为我们在x和y方向都有标准偏差）。 因此，每个簇都有一个高斯分布。

为了找到每个簇的高斯参数（例如平均值和标准偏差），使用期望最大化（EM）的优化算法。下图为高斯拟合的簇。然后我们可以继续进行使用GMMs的期望最大化聚类过程。

EM Clustering using GMMs

1、我们首先选择簇的数量（如K-Means）并随机初始化每个簇的高斯分布参数。人们也可以尝试通过快速浏览数据来猜测一个较好的初始参数。但从上图可以看出这不是必要的，因为虽然高斯拟合虽然开始时效果很差，但很快就得到了优化。

2、给定每个簇的高斯分布，计算每个数据点属于特定簇的概率。一个点越接近高斯分布的中心，越可能属于该簇。这应该是直观的，因为对于高斯分布，我们假设大部分数据更靠近集群的中心。

3、基于这些概率，我们为高斯分布计算一组新的参数，以便使集群内数据点的概率最大化。我们使用数据点位置的加权和来计算这些新参数，其中权重是数据点属于特定簇的概率。为了以可视化的方式解释这一点，可以参照上面的动态效果。以黄色的簇为例，第一次迭代时分布随机设置，但我们可以看到大部分黄点都在该分布的右侧。当我们计算一个按概率加权的和时，虽然中心附近有一些点，但它们中的大部分都在右边。因此，分布的均值自然会更接近这些点的集合。我们也可以看到，大部分点都是“从右上到左下”分布的。因此，标准偏差将被改变，从而创建更适合这些点的椭圆，以便最大化概率加权的总和。

4、迭代地重复步骤2和3直到收敛，当分布在两次迭代中变化不大时停止。

使用GMMs有两个关键优势。首先GMMs在簇的协方差方面比K-Means更灵活，由于含有标准差参数，簇可以采取任何椭圆形状，而不仅限于圆形。K-Means实际上是GMMs的一个特例，其中每个簇的协方差在所有维度上都接近0。其次，由于GMMs使用了概率，每个数据点可以有多个簇。因此，如果一个数据点位于两个重叠的簇的中间，我们可以简单地定义它的簇，X%属于簇1且Y%属于簇2。即GMMs支持混合的成员资格。

5.凝聚层次聚类

分层聚类算法实际上分为两类：自上而下或自下而上。自下而上算法首先将每个数据点视为单个簇，然后不断合并（或聚合）成对的簇，直到所有簇合并成一个包含所有数据点的簇。因此自下而上的层次聚类被称为分层凝聚聚类或HAC。该簇的层次结构被表示为树（或树状图）。树的根是包含所有样本的唯一的簇，叶是仅有一个样本的簇。在进入算法步骤之前，请查看下面的图解。

Agglomerative Hierarchical Clustering

1、我们首先将每个数据点视为一个单一的簇，即如果我们的数据集中有X个数据点，则有X个簇。然后选择一个度量来确定两个簇之间的距离。使用平均连接（average linkage）作为例子来定义两个簇之间的距离，即第一个簇内的点与第二个簇内的点的平均距离。

2、在每次迭代中，我们将两个簇合并成一个簇。选出的两个簇为平均连接最小的簇。即根据我们选择的距离度量，这两个簇之间的距离最小，因此是最相似的，应该被合并起来。

3、重复步骤2直到我们到达树的根部，即我们只有一个包含所有数据点的簇。通过这种方式，我们可以在最后选择想要的簇数量，当只需选择何时停止簇的合并，即何时停止树的构建！

分层聚类不要求我们指定聚类的数量，因为我们在构建一棵树，我们甚至可以选择哪个数量的簇看起来最好。另外，该算法对距离度量的选择不敏感，它们的效果都趋于相同，而对其他聚类算法而言，距离度量的选择则是至关重要的。

分层聚类方法的一个特别好的应用是源数据具有层次结构并且用户想要恢复其层次结构，其他聚类算法则无法做到这一点。这种层次聚类是以较低的效率为代价实现的，与K-Means和GMM的线性复杂性不同，它具有O（n3）的时间复杂度。

总结

这是数据科学家应该知道的top5的聚类算法！我们将用一个展现这些算法性能的图来结束本文。向Scikit学习！

翻译：非线性

审校：wanting

编辑：Yiri

原文地址：

https://www.kdnuggets.com/2018/06/5-clustering-algorithms-data-scientists-need-know.html

关注集智AI学园公众号

获取更多更有趣的AI教程吧！

搜索微信公众号：swarmAI

学园网站：campus.swarma.org

商务合作和投稿转载｜swarma@swarma.org