作者：George Seif
来源： AI公园，编译：ronghuaiyang
导读
聚类作为一种无监督技术，在很多的场合非常的有用，今天給大家介绍5个非常常用的聚类算法，以及各自的优缺点。
聚类是一种机器学习技术，涉及数据点的分组。给定一组数据点，我们可以使用聚类算法将每个数据点分类到特定的组中。理论上，同一组中的数据点应该具有相似的属性或特征，而不同组中的数据点应该具有高度不同的属性或特征。聚类是一种无监督学习方法，是统计数据分析中应用广泛的一种技术。
在数据科学中，通过观察我们应用聚类算法时，数据点落在什么组中，我们可以使用聚类分析从我们的数据中获得一些有价值的见解。今天，我们来看看数据科学家需要知道的5种流行的聚类算法及其优缺点！
K-Means聚类
K-Means可能是最知名的聚类算法，它在很多介绍性的数据科学和机器学习课程中都会讲到。它在代码中很容易理解和实现！查看下面的图表以获得说明。
① 首先，我们选择一些要使用的类/组，并随机初始化它们各自的中心点。为了计算要使用的类的数量，最好快速查看数据并尝试标识任何不同的分组。中心点是与每个数据点向量长度相同的向量，是上图中的“X”。
② 每个数据点的分类是通过计算该点与每个组中心之间的距离，然后将该点分类为离该点最近的组中的该点。
③ 根据这些分类点，我们通过取组中所有向量的平均值来重新计算组中心。
④ 对一定数量的迭代重复这些步骤，或者直到组中心在迭代之间变化不大。你还可以选择随机初始化组中心几次，然后选择看起来提供了最佳结果的那次。
K-Means的优点是非常快，因为我们所做的只是计算点到群中心的距离，很少的计算！因此，它具有线性复杂度O(n)。
另一方面，K-Means有几个缺点。首先，你必须选择有多少组/类。这个并不容易，理想情况下，对于聚类算法，我们希望它能帮我们解决这些问题，因为它的目的是从数据中获得一些见解。K-means也从随机选择聚类中心开始，因此在不同的算法运行情况下可能会产生不同的聚类结果。因此，结果可能是不可重复的，缺乏一致性。其他聚类方法更加一致。
K-Medians是与K-Means相关的另一种聚类算法，这个方法使用组的中值向量而不是使用均值重新计算组中心点。这种方法对异常值不太敏感(因为使用了中值)，但是对于较大的数据集，这种方法要慢得多，因为在计算中值向量时，每次迭代都需要排序。
Mean-Shift 聚类
Mean shift聚类是一种基于滑动窗口的算法，它试图找到数据点的密集区域。它是一种基于中心的算法，其目标是定位每个组/类的中心点，其工作原理是将中心点更新为滑动窗口内点的平均值。然后在后处理阶段对这些候选窗口进行筛选，以消除几乎重复的内容，形成最终的中心点集及其对应的组。查看下面的图表以获得说明。
① 为了解释均值漂移，我们考虑二维空间中的一组点，如上图所示。我们从一个以点C(随机选择)为中心、半径为r的圆形滑动窗口开始。均值漂移是一种爬坡算法，它涉及到在每一步上迭代地将核转移到一个更高的密度区域，直到收敛。
② 在每次迭代中，通过将中心点移动到窗口内点的平均值(因此得名)，滑动窗口会向密度更高的区域移动。滑动窗口内的密度与窗口内点的数量成正比。自然地，通过向窗口内点的均值移动，它将逐渐向点密度较高的区域移动。
③ 我们继续根据平均值移动滑动窗口，直到没有方向可以容纳内核中的更多点。看看上面的图表，我们继续移动这个圆直到不再增加密度(窗口中的点的个数)。
④ 步骤1到步骤3的过程是通过许多滑动窗口完成的，直到所有点都位于一个窗口中。当多个滑动窗口重叠时，保留包含最多点的窗口。然后根据数据点所在的滑动窗口对数据点进行聚类。
下面显示了从所有滑动窗口端到端的整个过程。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。
与K-means聚类相比，不需要选择簇的数量，因为均值漂移会自动发现这一点。这是一个巨大的优势。簇中心收敛于最大密度点的事实也是非常可取的，因为它非常直观，易于理解，并且很好地符合自然数据驱动。缺点是窗口大小/半径“r”的选择可能非常重要。
基于密度的噪声应用空间聚类(DBSCAN)
DBSCAN是一种基于密度的聚类算法，类似于均值漂移，但有几个显著的优点。看看下面另一个漂亮的图片，让我们开始吧！
① DBSCAN以未访问过的的任意数据点作为起点开始，这个点的邻域的提取使用距离ε(ε距离内的所有点作为邻域点)。
② 如果在这个邻域内有足够数量的点(根据minPoints)，则聚类过程开始，当前数据点成为新簇中的第一个点。否则，该点将被标记为noise(稍后该噪声点可能成为聚类的一部分)。在这两种情况下，该点都标记为“已访问”。
③ 对于这个新的簇中的第一个点，在其ε距离的领域内的点也成为同一聚类的一部分。这个过程中所有点的ε的邻域内的点属于同一簇，然后对所有的已经添加到簇中的新的点重复这个操作。
④ 重复步骤2和步骤3，直到确定簇中的所有点，也就是这个簇中所有点的e邻域内的点都被访问和标记过。
⑤ 完成当前聚类之后，将检索和处理新的未访问点，从而发现另一个聚类或噪声。这个过程重复进行，直到所有点都标记为已访问。在这个过程的最后，所有的点都被访问过了，所以每个点都被标记为属于一个簇或者是噪声。
与其他聚类算法相比，DBSCAN具有很大的优势。首先，它根本不需要设置簇的数量，它还可以将异常值识别为噪声，这与均值漂移不同，均值漂移只是将异常值扔进一个簇，即使数据点非常不同。此外，它能够很好地找到任意大小和任意形状的簇。
DBSCAN的主要缺点是，当簇的密度不同时，它的性能不如其他聚类方法。这是因为当簇的密度不同的时候，用来确定邻域点的距离设置阈值ε和minPoints也会不同。这个缺点也会出现在非常高纬度的数据中，因为距离阈值ε的估计变得具有挑战性。
基于混合高斯模型的EM算法
K-Means的一个主要缺点是它很原始的使用平均值作为簇的中心。我们可以从下图中看出为什么这不是最好的方法。在左手边，人眼很明显地看到两个半径不同的圆形星系团以相同的平均值为中心。K-Means无法处理这个问题，因为簇的平均值非常接近。在簇不是圆形的情况下，K-Means也会失败，这也是使用平均值作为簇中心的后果。
高斯混合模型(GMMs)给了我们比K-Means更大的灵活性。对于GMMs，我们假设数据点是高斯分布的，这个假设没有使用均值表示它们是圆环的那么严格。这样，我们就有两个参数来描述簇的形状：平均值和方差！举一个二维的例子，这意味着星系团可以是任何形状的椭圆(因为我们在x和y方向上都有标准差)。因此，每个高斯分布被分配到一个单独的聚类。
为了找到每个簇的高斯分布参数(均值和方差）我们将使用一种名为期望最大化(EM)的优化算法。请看下图，这是高斯分布在星系团上的一个例子。然后我们可以继续使用GMMs进行期望最大化聚类的过程。
① 我们首先选择簇的数量(像K-Means那样)，然后随机初始化每个集群的高斯分布参数。也可以通过快速查看数据来尝试对初始参数提供一个良好的估计。正如上图所示，这并不是100%必要的，因为高斯函数一开始很差，但很快就得到了优化。
② 给定每个簇的高斯分布，计算每个数据点属于特定簇的概率。一个点离高斯函数的中心越近，它就越有可能属于这个簇。这应该很直观，因为对于高斯分布，我们假设大多数数据位于更靠近簇中心的位置。
③ 在这些概率的基础上，我们计算了高斯分布的一组新的参数，使簇内数据点的概率最大化。我们使用数据点位置的加权和来计算这些新参数，其中的权重是属于特定簇的数据点的概率。为了直观地解释这一点，我们可以看一下上面的图形，特别是黄色簇作为一个例子。分布在第一次迭代时是随机开始的，但是我们可以看到大多数黄色的点都在分布的右边。当我们计算一个由概率加权的和时，即使中心附近有一些点，大多数都在右边。因此，分布的均值自然地向这些点集移动。我们还可以看到，大多数点是“从右上到左下”的。因此，标准差的变化会产生一个更适合这些点的椭圆，从而使概率加权的和最大化。
④ 步骤2和步骤3重复执行，直到收敛，在收敛过程中，分布在不同的迭代之间变化不大。
使用GMMs有两个关键优势。首先，由于有了标准差参数，GMMs在聚类协方差方面比K-Means灵活得多，簇可以呈现任何椭圆形状，而不限于圆形。K-Means实际上是GMM的一种特殊情况，其中每个簇在所有维度上的协方差都趋近于0。其次，由于GMMs使用概率，每个数据点可以有多个簇。因此，如果一个数据点位于两个重叠簇的中间，我们可以简单地定义它的类，即它的x%属于类1，y%属于类2。GMMs支持混合成员。
层次聚类
层次聚类算法实际上分为两类：自顶向下和自底向上。自底向上算法在开始时将每个数据点视为单个簇，然后依次合并两个簇，直到所有簇合并到包含所有数据点的单个簇中。因此，自底向上的层次聚类被称为分层聚类或HAC。簇的层次结构用树(或树状图)表示。树根是收集所有样本的唯一簇，叶子是只有一个样本的簇。在继续学习算法步骤之前，请查看下面的图表以获得说明。
我们首先将每个数据点视为单个簇，如果我们的数据集中有X个数据点，那么我们就有X个簇。然后我们选择一个距离来度量两个簇之间的距离。作为示例，我们将使用第一个簇中的数据点与第二个集群簇中的数据点之间的average linkage平均距离定义两个簇之间的距离。
在每次迭代中，我们将两个簇合并为一个簇。根据我们选择的距离度量，选择要组合的两个簇作为平均链路最小的簇，这两个簇之间的距离最小，因此它们是最相似的，应该组合在一起。
重复步骤2，直到到达树的根。我们只有一个包含所有数据点的簇。通过这种方式，我们可以选择最终需要多少个簇，只需选择何时停止组合簇。
层次聚类不需要我们指定簇的数量，我们甚至可以选择哪个簇看起来最好，因为我们正在构建一个树。此外，该算法对距离度量的选择不敏感。所有这些算法都能很好地工作，而对于其他聚类算法，距离度量的选择是关键。层次聚类方法的一个特别好的用例是，底层数据具有层次结构，你希望恢复层次结构，其他聚类算法不能做到这一点。这些层次聚类的优点来自于低效，它的时间复杂度是O(n³)，而k-means，GMM都是线性复杂度。
结论
这里有5个数据科学家应该知道的聚类算法！我们将这些算法和其他一些算法的出色性能的可视化来结束本文，感谢Scikit Learn！看到不同的算法如何与不同的数据进行比较和对比，真是太酷了!
本文转自：AI公园，作者：George Seif，编译：ronghuaiyang，转载此文目的在于传递更多信息，版权归原作者所有。
