数据科学家必须了解的六大聚类算法：带你发现数据之美

2018 年 2 月 12 日 机器之心

选自TowardsDataScience

作者：George Seif

机器之心编译

参与：程耀彤、蒋思源、李泽南

在机器学习中，无监督学习一直是我们追求的方向，而其中的聚类算法更是发现隐藏数据结构与知识的有效手段。目前如谷歌新闻等很多应用都将聚类算法作为主要的实现手段，它们能利用大量的未标注数据构建强大的主题聚类。本文从最基础的 K 均值聚类到基于密度的强大方法介绍了 6 类主流方法，它们各有擅长领域与情景，且基本思想并不一定限于聚类方法。

本文将从简单高效的 K 均值聚类开始，依次介绍均值漂移聚类、基于密度的聚类、利用高斯混合和最大期望方法聚类、层次聚类和适用于结构化数据的图团体检测。我们不仅会分析基本的实现概念，同时还会给出每种算法的优缺点以明确实际的应用场景。

聚类是一种包括数据点分组的机器学习技术。给定一组数据点，我们可以用聚类算法将每个数据点分到特定的组中。理论上，属于同一组的数据点应该有相似的属性和/或特征，而属于不同组的数据点应该有非常不同的属性和/或特征。聚类是一种无监督学习的方法，是一种在许多领域常用的统计数据分析技术。

K-Means（K 均值）聚类

K-Means 可能是最知名的聚类算法。它是很多入门级数据科学和机器学习课程的内容。在代码中很容易理解和实现！请看下面的图。

K-Means 聚类

首先，我们选择一些类/组，并随机初始化它们各自的中心点。为了算出要使用的类的数量，最好快速查看一下数据，并尝试识别不同的组。中心点是与每个数据点向量长度相同的位置，在上图中是「X」。
通过计算数据点与每个组中心之间的距离来对每个点进行分类，然后将该点归类于组中心与其最接近的组中。
根据这些分类点，我们利用组中所有向量的均值来重新计算组中心。
重复这些步骤来进行一定数量的迭代，或者直到组中心在每次迭代后的变化不大。你也可以选择随机初始化组中心几次，然后选择看起来提供了最佳结果的运行。

K-Means 的优势在于速度快，因为我们真正在做的是计算点和组中心之间的距离：非常少的计算！因此它具有线性复杂度 O(n)。

另一方面，K-Means 有一些缺点。首先，你必须选择有多少组/类。这并不总是仔细的，并且理想情况下，我们希望聚类算法能够帮我们解决分多少类的问题，因为它的目的是从数据中获得一些见解。K-means 也从随机选择的聚类中心开始，所以它可能在不同的算法中产生不同的聚类结果。因此，结果可能不可重复并缺乏一致性。其他聚类方法更加一致。

K-Medians 是与 K-Means 有关的另一个聚类算法，除了不是用均值而是用组的中值向量来重新计算组中心。这种方法对异常值不敏感（因为使用中值），但对于较大的数据集要慢得多，因为在计算中值向量时，每次迭代都需要进行排序。

均值漂移聚类

均值漂移聚类是基于滑动窗口的算法，它试图找到数据点的密集区域。这是一个基于质心的算法，这意味着它的目标是定位每个组/类的中心点，通过将中心点的候选点更新为滑动窗口内点的均值来完成。然后，在后处理阶段对这些候选窗口进行过滤以消除近似重复，形成最终的中心点集及其相应的组。请看下面的图例。

均值漂移聚类用于单个滑动窗口

为了解释均值漂移，我们将考虑二维空间中的一组点，如上图所示。我们从一个以 C 点（随机选择）为中心，以半径 r 为核心的圆形滑动窗口开始。均值漂移是一种爬山算法，它包括在每一步中迭代地向更高密度区域移动，直到收敛。
在每次迭代中，滑动窗口通过将中心点移向窗口内点的均值（因此而得名）来移向更高密度区域。滑动窗口内的密度与其内部点的数量成正比。自然地，通过向窗口内点的均值移动，它会逐渐移向点密度更高的区域。
我们继续按照均值移动滑动窗口直到没有方向在核内可以容纳更多的点。请看上面的图；我们一直移动这个圆直到密度不再增加（即窗口中的点数）。
步骤 1 到 3 的过程是通过许多滑动窗口完成的，直到所有的点位于一个窗口内。当多个滑动窗口重叠时，保留包含最多点的窗口。然后根据数据点所在的滑动窗口进行聚类。

下面显示了所有滑动窗口从头到尾的整个过程。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。

均值漂移聚类的整个过程

与 K-means 聚类相比，这种方法不需要选择簇数量，因为均值漂移自动发现这一点。这是一个巨大的优势。聚类中心朝最大点密度聚集的事实也是非常令人满意的，因为理解和适应自然数据驱动的意义是非常直观的。它的缺点是窗口大小/半径「r」的选择可能是不重要的。

基于密度的聚类方法（DBSCAN）

DBSCAN 是一种基于密度的聚类算法，它类似于均值漂移，但具有一些显著的优点。请看下面的另一个有趣的图形，让我们开始吧！

DBSCAN 聚类

DBSCAN 从一个没有被访问过的任意起始数据点开始。这个点的邻域是用距离 ε（ε 距离内的所有点都是邻域点）提取的。
如果在这个邻域内有足够数量的点（根据 minPoints），则聚类过程开始，并且当前数据点成为新簇的第一个点。否则，该点将会被标记为噪声（稍后这个噪声点可能仍会成为聚类的一部分）。在这两种情况下，该点都被标记为「已访问」。
对于新簇中的第一个点，其 ε 距离邻域内的点也成为该簇的一部分。这个使所有 ε 邻域内的点都属于同一个簇的过程将对所有刚刚添加到簇中的新点进行重复。
重复步骤 2 和 3，直到簇中所有的点都被确定，即簇的 ε 邻域内的所有点都被访问和标记过。
一旦我们完成了当前的簇，一个新的未访问点将被检索和处理，导致发现另一个簇或噪声。重复这个过程直到所有的点被标记为已访问。由于所有点都已经被访问，所以每个点都属于某个簇或噪声。

DBSCAN 与其他聚类算法相比有很多优点。首先，它根本不需要固定数量的簇。它也会将异常值识别为噪声，而不像均值漂移，即使数据点非常不同，也会简单地将它们分入簇中。另外，它能够很好地找到任意大小和任意形状的簇。

DBSCAN 的主要缺点是当簇的密度不同时，它的表现不如其他聚类算法。这是因为当密度变化时，用于识别邻域点的距离阈值 ε 和 minPoints 的设置将会随着簇而变化。这个缺点也会在非常高维度的数据中出现，因为距离阈值 ε 再次变得难以估计。

用高斯混合模型（GMM）的最大期望（EM）聚类

K-Means 的一个主要缺点是它对于聚类中心均值的简单使用。通过下面的图，我们可以明白为什么这不是最佳方法。在左侧，可以非常清楚的看到有两个具有不同半径的圆形簇，以相同的均值作为中心。K-Means 不能处理这种情况，因为这些簇的均值是非常接近的。K-Means 在簇不是圆形的情况下也失败了，同样是由于使用均值作为聚类中心。

K-Means 的两个失败案例

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

为了找到每个簇的高斯参数（例如均值和标准差），我们将用一个叫做最大期望（EM）的优化算法。请看下面的图表，这是一个高斯适合于簇的例子。然后我们可以使用 GMMs 继续进行最大期望聚类的过程。

使用 GMMs 的 EM 聚类

我们首先选择簇的数量（如 K-Means 所做的），并随机初始化每个簇的高斯分布参数。也可以通过快速查看数据来尝试为初始参数提供一个好的猜测。但是请注意，正如上图所看到的，这不是 100% 必要的，因为高斯开始时我们很穷，但是很快就得到了优化。
给定每个簇的高斯分布，计算每个数据点属于一个特定簇的概率。一个点越靠近高斯的中心，它就越可能属于该簇。这应该是很直观的，因为对于高斯分布我们假设大部分数据更靠近簇的中心。
基于这些概率，我们计算一组新的高斯分布参数使得簇内的数据点的概率最大化。我们使用数据点位置的加权和来计算这些新参数，其中权重是数据点属于该特定簇的概率。为了用可视化的方式解释它，我们可以看一下上面的图，特别是黄色的簇，我们以它来作为例子。分布在第一次迭代时随即开始，但是我们可以看到大部分的黄点都在分布的右侧。当我们计算一个概率加权和时，即使中心附近有一些点，但它们大部分都在右侧。因此，分布的均值自然会接近这些点。我们也可以看到大部分的点分布在「从右上到左下」。因此改变标准差来创建更适合这些点的椭圆，以便最大化概率加权和。
重复步骤 2 和 3 直到收敛，其中分布在迭代中的变化不大。

使用 GMMs 有两个关键的优势。首先，GMMs 比 K-Means 在簇协方差方面更灵活；因为标准差参数，簇可以呈现任何椭圆形状，而不是被限制为圆形。K-Means 实际上是 GMM 的一个特殊情况，这种情况下每个簇的协方差在所有维度都接近 0。第二，因为 GMMs 使用概率，所以每个数据点可以有很多簇。因此如果一个数据点在两个重叠的簇的中间，我们可以简单地通过说它百分之 X 属于类 1，百分之 Y 属于类 2 来定义它的类。即 GMMs 支持混合资格。

凝聚层次聚类

层次聚类算法实际上分为两类：自上而下或自下而上。自下而上的算法首先将每个数据点视为一个单一的簇，然后连续地合并（或聚合）两个簇，直到所有的簇都合并成一个包含所有数据点的簇。因此，自下而上层次聚类被称为凝聚式层次聚类或 HAC。这个簇的层次用树（或树状图）表示。树的根是收集所有样本的唯一簇，叶是仅仅具有一个样本的簇。在进入算法步骤前，请看下面的图例。

凝聚式层次聚类

我们首先将每个数据点视为一个单一的簇，即如果我们的数据集中有 X 个数据点，那么我们就有 X 个簇。然后，我们选择一个测量两个簇之间距离的距离度量标准。作为例子，我们将用 average linkage，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。
在每次迭代中，我们将两个簇合并成一个。这两个要合并的簇应具有最小的 average linkage。即根据我们选择的距离度量标准，这两个簇之间的距离最小，因此是最相似的，应该合并在一起。
重复步骤 2 直到我们到达树根，即我们只有一个包含所有数据点的簇。这样我们只需要选择何时停止合并簇，即何时停止构建树，来选择最终需要多少个簇！

层次聚类不需要我们指定簇的数量，我们甚至可以选择哪个数量的簇看起来最好，因为我们正在构建一棵树。另外，该算法对于距离度量标准的选择并不敏感；他们都同样表现很好，而对于其他聚类算法，距离度量标准的选择是至关重要的。层次聚类方法的一个特别好的例子是当基础数据具有层次结构，并且你想要恢复层次时；其他聚类算法不能做到这一点。与 K-Means 和 GMM 的线性复杂度不同，层次聚类的这些优点是以较低的效率为代价的，因为它具有 O(n³) 的时间复杂度。

图团体检测（Graph Community Detection）

当我们的数据可以被表示为一个网络或图（graph）时，我们可以使用图团体检测方法完成聚类。在这个算法中，图团体（graph community）通常被定义为一种顶点（vertice）的子集，其中的顶点相对于网络的其它部分要连接得更加紧密。

也许最直观的案例就是社交网络。其中的顶点表示人，连接顶点的边表示他们是朋友或互粉的用户。但是，若要将一个系统建模成一个网络，我们就必须要找到一种有效连接各个不同组件的方式。将图论用于聚类的一些创新应用包括：对图像数据的特征提取、分析基因调控网络（gene regulatory networks）等。

下面是一个简单的图，展示了最近浏览过的 8 个网站，根据他们的维基百科页面中的链接进行了连接。

这些顶点的颜色表示了它们的团体关系，大小是根据它们的中心度（centrality）确定的。这些聚类在现实生活中也很有意义，其中黄色顶点通常是参考/搜索网站，蓝色顶点全部是在线发布网站（文章、微博或代码）。

假设我们已经将该网络聚类成了一些团体。我们就可以使用该模块性分数来评估聚类的质量。分数更高表示我们将该网络分割成了「准确的（accurate）」团体，而低分则表示我们的聚类更接近随机。如下图所示：

模块性可以使用以下公式进行计算：

其中 L 代表网络中边的数量，k_i 和 k_j 是指每个顶点的 degree，它可以通过将每一行和每一列的项加起来而得到。两者相乘再除以 2L 表示当该网络是随机分配的时候顶点 i 和 j 之间的预期边数。

整体而言，括号中的项表示了该网络的真实结构和随机组合时的预期结构之间的差。研究它的值可以发现，当 A_ij = 1 且 ( k_i k_j ) / 2L 很小时，其返回的值最高。这意味着，当在定点 i 和 j 之间存在一个「非预期」的边时，得到的值更高。

最后的 δc_i, c_j 就是大名鼎鼎的克罗内克 δ 函数（Kronecker-delta function）。下面是其 Python 解释：

通过以上公式可以计算图的模块性，且模块性越高，该网络聚类成不同团体的程度就越好。因此通过最优化方法寻找最大模块性就能发现聚类该网络的最佳方法。

组合学（combinatorics）告诉我们对于一个仅有 8 个顶点的网络，就存在 4140 种不同的聚类方式。16 个顶点的网络的聚类方式将超过 100 亿种。32 个顶点的网络的可能聚类方式更是将超过 128 septillion（10^21）种；如果你的网络有 80 个顶点，那么其可聚类的方式的数量就已经超过了可观测宇宙中的原子数量。

因此，我们必须求助于一种启发式的方法，该方法在评估可以产生最高模块性分数的聚类上效果良好，而且并不需要尝试每一种可能性。这是一种被称为 Fast-Greedy Modularity-Maximization（快速贪婪模块性最大化）的算法，这种算法在一定程度上类似于上面描述的 agglomerative hierarchical clustering algorithm（集聚层次聚类算法）。只是 Mod-Max 并不根据距离（distance）来融合团体，而是根据模块性的改变来对团体进行融合。

下面是其工作方式：