Must Know！数据科学家们必须知道的 5 种聚类算法

2018 年 3 月 12 日 AI研习社 雷锋字幕组

本文为雷锋字幕组编译的技术博客，原标题 The 5 Clustering Algorithms Data Scientists Need to Know，作者为 George Seif。

翻译 | 姜波整理 | 凡江吴璇

聚类是一种关于数据点分组的机器学习技术。给出一组数据点，我们可以使用聚类算法将每个数据点分类到特定的组中。理论上，同一组中的数据点应具有相似的属性或特征，而不同组中的数据点应具有相当不同的属性或特征（即类内差异小，类间差异大）。聚类是一种无监督学习方法，也是一种统计数据分析的常用技术，被广泛应用于众多领域。

在数据科学中，我们可以通过聚类算法，查看数据点属于哪些组，并且从这些数据中获得一些有价值的信息。今天，我们一起来看看数据科学家需要了解的 5 种流行聚类算法以及它们的优缺点。

一、K 均值聚类

K-Means 可能是最知名的聚类算法了。在数据科学或机器学习课程中都有过它的介绍。K-Means 的代码也非常容易理解和实现。请查看下面的图片：

开始，我们先选取一些类型或者组类，分别随机初始化它们的中心点。要计算出使用的类的数量，最好快速查看数据并尝试识别不同的分组。中心点是与每个数据点向量长度相同的向量，并且是上图中的‘X’s’。
每一个数据点，是通过计算该点与每一组中的点之间的距离，来进行分类的，然后将该点归类到距离中心最近的组。
基于这些分类的点，我们通过求取每一组中所有向量的均值，重复计算每一组的中心点。
重复上述步骤，直到每一组的中心点不再发生变化或者变化不大为止。你也可以选择对组中心点进行多次随机初始化，选择运行效果最好的即可。
由于我们所做的只是计算点和组中心之间的距离，计算量较小，因此 K-Means 的一大优点就是运行速度非常快。所以它具有线性复杂度 O(n）。

当然，K-Means 也有两个缺点。首先，你必须选择有分类组的数目（如聚为 3 类，则 K=3）。这并不能忽略，理想情况下，我们希望它使用聚类算法来帮助我们理解这些数据，因为它的重点在于从数据中获得一些有价值的发现。由于 K-means 算法选择的聚类中心是随机的（即初始化是随机的），因此它可能会因为类数不同而运行算法中产生不同的聚类结果。因此，结果可能不可重复且缺乏一致性。相反，其他集群方法更一致。

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

二、Mean-Shift 聚类

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

Mean-Shift 聚类用于单个滑动窗口

为了解释平均偏移，我们将考虑像上图那样的二维空间中的一组点。我们从以 C 点（随机选择）为中心并以半径 r 为核心的圆滑动窗口开始。平均偏移是一种爬山算法，它涉及将这个核迭代地转移到每个步骤中更高密度的区域，直到收敛。
在每次迭代中，通过将中心点移动到窗口内的点的平均值（因此得名），将滑动窗口移向较高密度的区域。滑动窗口内的密度与其内部的点数成正比。当然，通过转换到窗口中的点的平均值，它将逐渐走向更高点密度的区域。
我们继续根据平均值移动滑动窗口，直到没有方向移位可以在内核中容纳更多点。看看上面的图片; 我们继续移动该圆，直到我们不再增加密度（即窗口中的点数）。
步骤 1 至 3 的这个过程用许多滑动窗口完成，直到所有点位于一个窗口内。当多个滑动窗口重叠时，保留包含最多点的窗口。数据点然后根据它们所在的滑动窗口聚类。

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

Mean-Shift 聚类的整个过程

与 K 均值聚类相比，不需要选择聚类数量，因为均值偏移可以自动发现。这是一个巨大的优势。聚类中心向最大密度点聚合的结果也是非常令人满意的，因为它的理解比较符合数据驱动的规律，且十分直观。缺点是窗口大小 / 半径 r 的选择是非常重要的，换句话说半径的选择决定了运行结果。

三、基于密度的噪声应用空间聚类（DBSCAN）

DBSCAN 是一种基于密度的聚类算法，类似于 mean-shift，但其拥有一些显着的优点。看看下面的另一个花哨的图形，让我们开始吧！（图片过大，请点击链接观看）

http://suo.im/3r9b56

http://suo.im/1JQmbi

http://suo.im/12XwkZ

DBSCAN 以任何尚未访问过的任意起始数据点开始。这个点的邻域用距离 epsilon 提取（ε距离内的所有点都是邻域点）。
如果在该邻域内有足够数量的点（根据 minPoints），则聚类过程将开始并且当前数据点将成为新聚类中的第一个点。否则，该点将被标记为噪声（稍后，这个噪声点可能会成为群集的一部分）。在这两种情况下，该点都被标记为 “已访问”。
对于新簇中的第一个点，ε距离邻域内的点也成为同一个簇的一部分。然后对已经添加到群集组中的所有新点重复使ε邻域中的所有点属于同一个群集的过程。
重复步骤 2 和 3 的这个过程直到聚类中的所有点都被确定，即聚类的ε邻域内的所有点都被访问和标记。
一旦我们完成了当前的集群，一个新的未访问点被检索和处理，导致发现更多的集群或噪声。重复此过程，直到所有点都被标记为已访问。由于所有点已经被访问完毕，每个点都被标记为属于一个簇或是噪声。
与其他聚类算法相比，DBSCAN 具有一些很大的优势。首先，它根本不需要 pe-set 数量的簇。它还将异常值识别为噪声，而不像 mean-shift，即使数据点非常不同，它们也会将它们引入群集中。另外，它能够很好地找到任意大小和任意形状的簇。

DBSCAN 的主要缺点是，当簇的密度不同时，DBSCAN 的性能不如其他组织。这是因为当密度变化时，用于识别邻近点的距离阈值ε和 minPoints 的设置将随着群集而变化。对于非常高维的数据也会出现这种缺点，因为距离阈值ε再次难以估计。

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

K-Means 的主要缺点之一是其使用了集群中心的平均值。通过查看下面的图片，我们可以明白为什么这不是选取聚类中心的最佳方式。在左侧，人眼看起来非常明显的是，有两个半径不同的圆形星团以相同的平均值为中心。K-Means 无法处理这个问题，因为这些集群的平均值非常接近。K-Means 在集群不是圆形的情况下也会出错，这也是因为使用均值作为集群中心的原因。

K-Means 的两个失败案例

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

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

使用 GMM 的 EM 聚类

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

使用 GMM 有两个关键优势。首先 GMM 比 K-Means 在群协方面更灵活。由于标准偏差参数，集群可以采取任何椭圆形状，而不是限于圆形。K 均值实际上是 GMM 的一个特例，其中每个群的协方差在所有维上都接近 0。其次，由于 GMM 使用概率，每个数据点可以有多个群。因此，如果一个数据点位于两个重叠的簇的中间，我们可以简单地定义它的类，将其归类为类 1 的概率为百分之 x，类 2 的概率为百分之 y。

五、凝聚层次聚类

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

凝聚层次聚类

我们首先将每个数据点视为一个单一的聚类，即如果我们的数据集中有 X 个数据点，则我们有 X 个聚类。然后我们选择一个度量两个集群之间距离的距离度量。作为一个例子，我们将使用平均关联，它将两个集群之间的距离定义为第一个集群中的数据点与第二个集群中的数据点之间的平均距离。
在每次迭代中，我们将两个群集合并成一个群集。将要组合的两个群被选为平均联系最小的群。即根据我们选择的距离度量，这两个群集之间的距离最小，因此是最相似的，应该结合起来。
重复步骤 2 直到我们到达树的根部，即我们只有一个包含所有数据点的聚类。通过这种方式，我们可以最终选择我们想要的簇数量，只需选择何时停止组合簇，即停止构建树。

分层聚类不需要我们指定聚类的数量，我们甚至可以选择哪个数量的聚类看起来最好，因为我们正在构建一棵树。另外，该算法对距离度量的选择不敏感; 他们都倾向于工作同样好，而与其他聚类算法，距离度量的选择是至关重要的。分层聚类方法的一个特别好的用例是基础数据具有层次结构并且您想要恢复层次结构; 其他聚类算法无法做到这一点。与 K-Means 和 GMM 的线性复杂性不同，这种层次聚类的优点是以较低的效率为代价，因为它具有 O（n3）的时间复杂度。

结论

数据科学家应该知道的这 5 个聚类算法！我们将期待一些其他的算法的执行情况以及可视化，敬请期待 Scikit Learn！