数据科学中必须熟知的5种聚类算法

2019 年 2 月 12 日 AI研习社

本文为 AI 研习社编译的技术博客，原标题：

The 5 Clustering Algorithms Data Scientists Need to Know

作者 | George Seif

翻译 | 邓普斯•杰弗、arnold_hua、小Y的彩笔

校对 | 邓普斯•杰弗审核| Lam-W 整理 | 菠萝妹

原文链接：

https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68

注：本文的相关链接请点击文末【阅读原文】进行访问

数据科学中必须熟知的5种聚类算法

聚类算法是机器学习中涉及对数据进行分组的一种算法。在给定的数据集中，我们可以通过聚类算法将其分成一些不同的组。在理论上，相同的组的数据之间有相同的属性或者是特征，不同组数据之间的属性或者特征相差就会比较大。聚类算法是一种非监督学习算法，并且作为一种常用的数据分析算法在很多领域上得到应用。

在数据科学领域，我们利用聚类分析，通过将数据分组可以比较清晰的获取到数据信息。今天我们来看看，作为数据科学家需要知道并掌握的五种比较比较流行的聚类算法。

K-means 聚类算法

K-means 聚类算法可能是大家最为熟悉的聚类算法。它在许多的工业级数据科学和机器学习课程中都有被讲解。并且容易理解和实现相应功能的代码。比如以下的图片：

k-means聚类

首先，我们确定要聚类的数量，并随机初始化它们各自的中心点。为了确定要聚类的数量，最好快速查看数据并尝试识别任何不同的分组。中心点是与每个数据点向量长度相同的向量，是上图中的“x”。
通过计算当前点与每个组中心之间的距离，对每个数据点进行分类，然后归到与距离最近的中心的组中。
基于迭代后的结果，计算每一类内，所有点的平均值，作为新簇中心。
迭代重复这些步骤，或者直到组中心在迭代之间变化不大。您还可以选择随机初始化组中心几次，然后选择看起来提供最佳结果。

k-means的优点是速度非常快，因为我们真正要做的就是计算点和组中心之间的距离；计算量少！因此，它具有线性复杂性o（n）。

另一方面，k-means有两个缺点。首先，您必须先确定聚类的簇数量。理想情况下，对于一个聚类算法，我们希望它能帮我们解决这些问题，因为它的目的是从数据中获得一些洞察力。k-均值也从随机选择聚类中心开始，因此它可能在算法的不同运行中产生不同的聚类结果。因此，结果可能不可重复，缺乏一致性。

K中位数是与K均值相关的另一种聚类算法，除了不使用平均值重新计算组中心点之外，我们使用组的中位数向量。这种方法对异常偏离值不太敏感（因为使用了中值），但对于较大的数据集来说要慢得多，因为在计算中值向量时，每次迭代都需要排序。

Mean-Shift 聚类

Mean-shift 聚类是一个基于滑窗的算法，尝试找到数据点密集的区域。它是一个基于质心的算法，也就是说他的目标是通过更新中心点候选者定位每个组或类的中心点，将中心点候选者更新为滑窗内点的均值。这些候选滑窗之后会在后处理阶段被过滤，来减少临近的重复点，最后形成了中心点的集合和他们对应的组。查看下面的说明图。

单滑窗的 Mean-Shift 聚类

为了解释 mean-shift，我们将考虑一个二维空间中的点集，像上图所示那样。我们以一个圆心在C点（随机选择）的圆形滑窗开始，以半径 r 作为核。Mean shift 是一个爬山算法，它每一步都迭代地把核移动到更高密度的区域，直到收敛位置。
在每次迭代时，通过移动中心点到滑窗中点的均值处，将滑窗移动到密度更高的区域（这也是这种算法名字的由来）。滑窗内的密度与在其内部点的数量成正比。很自然地，通过将中心移动到窗内点的均值处，可以逐步的移向有个高的密度的区域。
我们继续根据均值来移动滑窗，直到有没有哪个方向可以使核中容纳更多的点。查看上面的图，我们一直移动圆圈直到密度不再增长。（即窗内点的数量不再增长）。
用很多滑窗重复1-3这个过程，直到所有的点都包含在了窗内。当多个滑动窗口重叠时，包含最多点的窗口将被保留。然后，根据数据点所在的滑动窗口对数据点进行聚类。

下图展示了所有滑动窗口从端到端的整个过程。每个黑色的点都代表滑窗的质心，每个灰色的点都是数据点。

Mean-Shift 聚类的全部过程

与 K-means 聚类不同的是，Mean-Shift 不需要选择聚类的数量，因为mean-shift 自动发现它。这是一个很大的优点。事实上聚类中心向着有最大密度的点收敛也是我们非常想要的，因为这很容易理解并且很适合于自然的数据驱动的场景。缺点是滑窗尺寸/半径“r“的选择需要仔细考虑。

基于密度的带噪声的空间聚类的应用（DBSCAN)

DBSCAN 是一个基于密度的聚类算法，与 mean-shift 相似，但是有几个值得注意的优点。查看下面这个花哨的图片，我们开始吧！

DBSCAN 笑脸聚类

DBSCAN 从一个任意的还没有被访问过的启动数据点开始。用一个距离 epsilon ε 将这个点的邻域提取出来（所有再距离 ε 内的点都视为邻居点）。
如果在邻域内有足够数量的点（根据 minPoints) ，那么聚类过程开始，并且当前数据点变成新集群中的第一个点。否则，该点将被标记为噪声（之后这个噪声点可能会变成集群中的一部分）。在这两种情况中的点都被标记为”已访问“。
对于这个新集群中的第一个点，在它 ε 距离邻域内的点已将变成相同集群中的一部分。这个让所有在 ε 邻域内的点都属于相同集群的过程在之后会一直被重复做，直到所有新点都被加进集群分组中。
第 2，3 步的过程会一直重复直到集群内所有点都被确定，即所有在 ε 邻域内的点都被访问且被打上标签。
一旦我们在当前集群做完这些，一个新的未被访问的点会被提取并处理，从而会接着发现下一个集群或噪声。这个过程反复进行直到所有的点都被编辑为已访问。既然在最后所有的点都被访问，那么每个点都被标记为属于一个集群或者是噪声。

相较于其他聚类算法，DBSCAN 提出了一些很棒的优点。首先，它根本不需要预置集群的数量。它还将离群值认定为噪声，不像 mean-shift 中仅仅是将它们扔到一个集群里，甚至即使该数据点的差异性很大也这么做。另外，这个算法还可以很好的找到任意尺寸核任意形状的集群。

SBSCAN 最大的缺点是当集群的密度变化时，它表现的不像其他算法那样好。这是因为当密度变化时，距离的阈值 ε 和用于确定邻居点的 minPoints 也将会随之改变。这个缺点也会发生在很高为的数据中，因为距离阈值 ε 变得很难被估计。

基于高斯混合模型(GMM)的期望最大化（EM）聚类

k-means的一个主要缺点是它简单地使用了集群中心的平均值。通过下面的图片，我们可以看到为什么这不是最好的方式。在左手边，人眼可以很明显地看到，有两个半径不同的圆形星团以相同的平均值为中心。k-means不能处理这个问题，因为不同簇的平均值非常接近。当簇不是圆形时，k均值也会失效，这也是将均值用作簇中心的后果。

K-means不适用的case

高斯混合模型（gmms）具有更好的灵活性比K-means。使用GMMs，我们需要假设数据点是高斯分布，相对于环形的数据而言，这个假设的严格程度与均值相比弱很多。这样的话，我们有两个参数来描述簇的形状：均值和标准差。以二维为例，意味簇可以是任何一种椭圆形（因为我们有两个标准差在x和y方向）。因此，每个高斯分布会被分配到单一的聚类簇。

为了在每个聚类簇中找到这两个高斯参数（e.g均值和标准差），我们将使用的优化算法称为expectation–maximization（EM）。请看下面的图片，以说明将高斯拟合聚类簇。然后，我们可以处理EM聚类过程使用gmms。

使用GMMs的EM聚类

我们首先设定聚类簇的数量（如k-means），然后随机初始化每个集群的高斯分布参数。我们也可以通过快速查看数据来为初始参数提供一个很好的猜测。正如上图所示，这不是100%必要的，因为高斯操作开始时候是非常差的，但很快优化。
给定每个簇的高斯分布，计算每个数据点属于特定簇的概率。一个点越靠近高斯中心，它就越可能属于该簇。这应该是直观的，因为对于高斯分布，我们假设大多数数据都靠近集群的中心。
基于这些概率，我们为高斯分布计算了一组新的参数，这样我们就可以最大化群集中数据点的概率。我们使用数据点位置的加权和计算这些新参数，其中权重是属于特定集群的数据点的概率。为了以可视化的方式解释这一点，我们可以查看上面的图形，特别是以黄色集群为例。在第一次迭代中，分布是随机开始的，但是我们可以看到大多数黄点都在分布的右边。当我们计算一个由概率加权的和时，即使在中心附近有一些点，但大多数都在右边。因此，分布的平均值很自然地移近这些点集。我们还可以看到，大多数点是“从右上到左下”。因此，标准偏差会发生变化，以创建一个更适合这些点的椭圆，以便最大化概率加权的和。
第2步和第3步重复进行，直到收敛，也就是在收敛过程中，迭代变化不大。

使用GMMS有两个关键优势。首先，GMMS在簇协方差方面比K均值灵活得多；由于标准偏差参数的存在，簇可以呈现任何椭圆形状，而不局限于圆形。k均值实际上是GMM的一个特例，其中每个簇的所有维协方差都接近于0。其次，由于GMM使用概率，因此每个数据点可以有多个集群。因此，如果一个数据点位于两个重叠集群的中间，我们可以简单地定义它的类，方法是说它属于类1的X%，属于类2的Y%。即GMMS支持混合成员。

凝聚层次聚类

凝聚层次聚类算法实际上分为 2 类：自上而下或自下而上。自下而上算法在一开始将每个数据点当作一个单个集群对待，然后逐步的合并（或凝聚）成对的集群，直到所有的集群被合并到一个集群中，这个集群包含所有的点。自下而上层次聚类因此被叫做层次凝聚的聚类或者 HAC。这个聚类的层次被表示为一棵树（或者树状图）。树根是唯一的集群，他聚集了所有的样本，叶子是只有一个样本的集群。在接着看算法步骤之前，请查看下面的图示说明。

凝聚层次聚类

我们通过将每个点视作一个单个集群作为开始，即如果我们的数据集中有 X 个数据点，那么我们就有 X 个集群。我们然后选择一个距离度量标准来测量两个集群之间的距离。作为一个例子，我们将用到平均连接，它将两个集群之间的距离定义为第一个集群中的数据点与第二个集群中数据点的平均距离。
在每次迭代时，我们将两个集群组合成一个。两个将被组合的集群是在那些有最小平均连接的集群中选出来的，即根据我们选择的距离度量标准，这些两两集群之间有最小的距离，且因此是最相似的也最应该被组合。
一直重复第二步，直到我们到达树的根部，即我们只有一个包含所有数据点的集群。通过这种方法，我们仅仅通过选择停止组合的集群的时机，即选择何时停止树的构建，就可以挑选出最终我们想要的集群数。

层次聚类不要求我们指定集群的数目，并且我们甚至可以选择看上去最好的集群的数目，因为我们正在构建一棵树。另外，算法对于距离度量的选择也是不敏感的；所有的这些都和其他聚类算法的效果一样好，而对于其他算法，距离度量的选择是很关键的。层次聚类方法的一个典型的使用案例是当底层数据具有层次结构并且要恢复层次结构时；其他聚类算法做不到这个。这些层次聚类的优点的代价是效率很低，因为它的时间复杂度是O(n³)，不像有线性复杂度的 K-Means 和 GMM 那样。