目前，很多应用如GoogleNews都以聚类算法作为主要实现手段，它们可以利用大量未标记的数据构建强大的主题聚类。本文介绍了6种主流方法，从最基本的K-means聚类到强大的基于密度的方法。他们各有各的专长领域和场景，基本思想不一定局限于聚类方法。本文将从简单高效的K-means聚类开始，然后介绍均值漂移聚类、基于密度的聚类、使用高斯混合和期望最大值方法的聚类、层次聚类以及针对结构化数据的图社区检测。我们不仅会分析基本的实现概念，还会给出每种算法的优缺点，以阐明实际的应用场景。聚类是一种涉及对数据点进行分组的机器学习技术。给定一组数据点，我们可以使用聚类算法将每个数据点分类到特定的组中。理论上，属于同一组的数据点应具有相似的属性和/或特征，而属于不同组的数据点应具有截然不同的属性和/或特征。聚类是一种无监督学习方法，是许多领域常用的统计数据分析技术。K-Means(K-Means)聚类K-Means可能是最著名的聚类算法。这是许多介绍性数据科学和机器学习课程的内容。它很容易理解和用代码实现！请看下图。K-Means聚类首先，我们选择一些类/组并随机初始化它们各自的中心点。要弄清楚要使用多少个类，快速查看数据并尝试识别不同的组是个好主意。中心点是与每个数据点的向量等长的位置，也就是上图中的“X”。通过计算数据点到每个组中心的距离对每个点进行分类，然后将点分类到离组中心最近的组中。从这些分类点，我们取组中所有向量的均值来重新计算组中心。这些步骤重复一定次数的迭代，或者直到每次迭代后组中心变化不??大。您还可以选择随机初始化组中心几次，然后选择似乎能提供最佳结果的运行。K-Means的优点是速度快，因为我们真正要做的是计算点和组中心之间的距离：计算量非常小！所以它的线性复杂度为O(n)。另一方面，K-Means有一些缺点。首先，您必须选择有多少组/班级。这并不总是很小心，理想情况下，我们希望聚类算法帮助我们计算出要分类多少类，因为它的目的是从数据中获得一些见解。K-means也是从随机选择的聚类中心开始的，所以它可能在不同的算法中产生不同的聚类结果。因此，结果可能无法重现且缺乏一致性。其他聚类方法更一致。K-Medians是另一种与K-Means相关的聚类算法，除了不使用均值，而是使用组的中值向量重新计算组质心。这种方法对异常值不太敏感（因为使用了中值），但对于较大的数据集来说速度要慢得多，因为在计算中值向量时每次迭代都需要进行排序。均值漂移聚类均值漂移聚类是一种基于滑动窗口的算法，它试图找到数据点的密集区域。这是一种基于质心的算法，这意味着它的目标是定位每个组/类的中心点，这是通过将候选中心点更新为滑动窗口内点的平均值来完成的。然后在后处理阶段过滤这些候选窗口以消除近重复，形成最终的中心点集及其对应的组。请参阅下面的图例。单个滑动窗口的均值漂移聚类为了解释均值漂移，我们将考虑二维空间中的一组点，如上图所示。我们从以C点（随机选择）为中心并以半径r为中心的圆形滑动窗口开始。Meanshift是一种爬山算法，包括在每一步迭代地向更高密度区域移动直到收敛。在每次迭代中，滑动窗口通过将中心点移向窗口内点的平均值（因此得名）来移向密度更高的区域。滑动窗口内的密度与其内的点数成正比。自然地，通过向窗口内点的平均值移动，它逐渐向点密度较高的区域移动。我们继续按均值移动滑动窗口，直到没有方向可以容纳内核中更多的点。看看上面的图表；我们继续移动圆圈，直到密度不再增加（即窗口中的点数）。步骤1到3的过程是通过许多滑动窗口完成的，直到所有点都在一个窗口内。当多个滑动窗口重叠时，保留包含最多点的窗口。然后根据数据点所在的滑动窗口进行聚类。所有滑动窗口从开始到结束的整个过程如下所示。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。MeanShift聚类的全过程与K均值聚类相比，该方法不需要选择聚类数，因为MeanShift会自动找到这个。这是一个巨大的优势。集群中心向最大点密度集群的事实也非常令人满意，因为理解和适应自然数据驱动的意义是非常直观的。它的缺点是窗口大小/半径“r”的选择可能无关紧要。基于密度的聚类方法(DBSCAN)DBSCAN是一种基于密度的聚类算法，类似于均值漂移但具有一些显着的优点。查看下面的另一个有趣的图形，让我们开始吧！DBSCANClusteringDBSCAN从任意一个没有被访问过的起始数据点开始。该点的邻域以距离ε提取（所有在ε距离内的点都是邻域点）。如果该邻域内有足够数量的点（根据minPoints），则聚类过程开始，当前数据点成为新聚类的第一个点。否则，该点将被标记为噪声（稍后可能仍是簇的一部分）。在这两种情况下，该点都标记为“已访问”。对于新集群中的第一个点，其ε距离邻域内的点也成为集群的一部分。这个使ε邻域中的所有点都属于同一个簇的过程将对所有刚添加到簇中的新点重复进行。重复步骤2和3，直到簇中的所有点都确定，即簇的ε邻域内的所有点都被访问并标记。一旦我们完成了当前集群，就会检索并处理一个新的未访问点，从而导致发现另一个集群或噪声。重复此过程，直到所有点都标记为已访问。由于已访问所有点，因此每个点都属于某个簇或噪声。与其他聚类算法相比，DBSCAN具有许多优势。首先，它根本不需要固定数量的集群。它还将异常值识别为噪声，这与均值偏移不同，均值偏移只是将数据点分组到集群中，即使它们非常不同。另外，它在寻找任意大小和形状的集群方面做得很好。DBSCAN的主要缺点是当簇具有不同密度时，它的性能不如其他聚类算法。这是因为用于识别邻域点的距离阈值ε和minPoints的设置会随着密度的变化而因簇而异。这个缺点也出现在非常高维的数据中，因为距离阈值ε再次变得难以估计。具有高斯混合模型(GMM)最大期望(EM)聚类的K-Means的一个主要缺点是其对聚类中心均值的简单使用。从下图中，我们可以看出为什么这不是最好的方法。在左边，可以很清楚地看到有两个不同半径的圆形星团，以同一个均值为中心。K-Means无法处理这种情况，因为这些集群的均值非常接近。当集群不是圆形时，K-Means也会失败，这也是由于使用均值作为集群中心。K-Means高斯混合模型(GMM)的两个失败案例为我们提供了比K-Means更大的灵活性。对于GMM，我们假设数据点是高斯分布的；与使用均值假设它们是循环的相比，这是一个限制性更小的假设。这样，我们就有了两个参数来描述集群的形状：均值和标准差！以2D为例，这意味着簇可以采用任何类型的椭圆（因为我们在x和y方向上都有标准偏差）。因此，每个高斯分布都分配给一个集群。为了找到每个集群的高斯参数（例如均值和标准差），我们将使用称为最大期望(EM)的优化算法。看一下下图，它是一个集群的高斯拟合示例。然后我们可以继续使用GMM进行期望最大聚类的过程。使用GMM的EM聚类我们首先选择聚类的数量（就像K-Means所做的那样）并随机初始化每个聚类的高斯分布参数。还可以通过快速查看数据来尝试对初始参数进行一个很好的猜测。但请注意，正如您在上图中所见，这不是100%必要的，因为高斯开始时我们很差，但很快得到优化。给定每个集群的高斯分布，计算每个数据点属于特定集群的概率。一个点越靠近高斯分布的中心，它就越有可能属于那个簇。这应该是直观的，因为对于高斯分布，我们假设大部分数据更靠近集群的中心。基于这些概率，我们计算了一组新的高斯分布参数，使集群内数据点的概率最大化。我们使用数据点位置的加权和来计算这些新参数，其中权重是数据点属于该特定集群的概率。为了直观地解释它，我们可以看一下上面的图，尤其是我们用作示例的黄色集群。分布在第一次迭代时立即开始，但我们可以看到大部分黄色点位于分布的右侧。当我们计算概率加权和时，即使有一些点靠近中心，但大多数都在右侧。因此，分布的均值自然会靠近这些点。我们还可以看到大部分点都是“从右上到左下”分布的。因此，标准偏差会发生变化，以创建一个更适合这些点的椭圆，从而使概率加权和最大化。重复步骤2和3直到收敛，此时分布在迭代中变化不大。使用GMM有两个主要优势。首先，GMM在聚类协方差方面比K-Means更灵活；由于标准偏差参数，集群可以呈现任何椭圆形，而不是被限制为圆形。K-Means实际上是GMM的一个特例，每个簇的协方差在所有维度上都接近于0。其次，因为GMM使用概率，所以每个数据点可以有很多集群。因此，如果一个数据点位于两个重叠集群的中间，我们可以简单地定义它的类，即它的X%属于第1类，Y%属于第2类。也就是说，GMM支持混合资格。凝聚层次聚类层次聚类算法实际上分为两类：自上而下或自下而上。自底向上算法首先将每个数据点视为一个单独的集群，然后不断合并（或聚合）两个集群，直到所有集群合并为一个包含所有数据点的集群。因此，自下而上的层次聚类称为凝聚层次聚类或HAC。这种聚类层次结构由树（或树状图）表示。树的根是唯一收集所有样本的簇，叶子是只有一个样本的簇。在执行算法步骤之前，请参阅下图。凝聚层次聚类我们首先将每个数据点视为一个集群，即如果我们的数据集中有X个数据点，那么我们有X个集群。然后我们选择一个距离度量来测量两个集群之间的距离。例如，我们将使用平均链接，它将两个集群之间的距离定义为第一个集群中的数据点与第二个集群中的数据点之间的平均距离。在每次迭代中，我们将两个集群合并为一个。要合并的两个集群应具有最小的平均链接。也就是说，根据我们选择的距离度量，两个集群之间的距离最小，因此最相似，应该合并在一起。重复步骤2，直到我们到达树的根，即我们只有一个包含所有数据点的集群。这样我们只需要选择什么时候停止合并集群，也就是什么时候停止建树，来选择最终需要多少个集群！层次聚类不需要我们指定簇的数量，我们甚至可以选择哪个簇的数量看起来最好，因为我们正在构建一棵树。此外，该算法对距离度量的选择不敏感；它们都表现得同样好，而对于其他聚类算法，距离度量的选择是至关重要的。层次聚类方法的一个特别好的例子是当底层数据具有层次结构并且您想要恢复层次结构时；其他聚类算法无法做到这一点。与K-Means和GMM的线性复杂度不同，层次聚类的这些优势是以较低的效率为代价的，因为它的时间复杂度为O(n3)。图社区检测当我们的数据可以表示为网络或图（graph）时，我们可以使用图社区检测的方法来完成聚类。在该算法中，图社区通常被定义为比网络其余部分连接更紧密的顶点子集。也许最直观的例子是社交网络。顶点代表人，连接顶点的边代表彼此是朋友或粉丝的用户。然而，要将系统建模为网络，我们必须找到一种有效连接各个组件的方法。图论在聚类方面的一些创新应用包括：图像数据的特征提取、基因调控网络的分析等。下面是一个简单的图表，显示了8个最近查看的网站，这些网站根据其维基百科页面中的链接进行连接。这些顶点的颜色表示它们的社区关系，大小根据它们的中心性来确定。这些集群在现实生活中也很有意义，其中黄色顶点通常是参考/搜索站点，蓝色顶点都是在线发布站点（文章、推文或代码）。假设我们已经将网络聚类成组。然后我们可以使用这个模块化分数来评估聚类的质量。较高的分数表示我们将网络划分为“准确”的组，而较低的分数表示我们的集群更接近随机。如下图所示：Modularity可以用下面的公式来计算：其中L表示网络中的边数，k_i和k_j是指每个顶点的度数，可以通过将每个顶点的条目相加得到行和列。将两者相乘除以2L表示随机分配网络时顶点i和j之间的预期边数。总的来说，括号中的项表示随机组合时网络的真实结构与预期结构之间的差异。研究其值可知，当A_ij=1且(k_ik_j)/2L较小时，返回最高值。这意味着当顶点i和j之间存在“意外”边时，结果值会更高。最后的δc_i，c_j就是著名的克罗内克-德尔塔函数（Kronecker-deltafunction）。下面是它的Python解释：图的模块度可以通过上面的公式计算出来，模块度越高，网络聚类到不同组的效果越好。因此，可以通过寻找最大模块性的优化方法找到对该网络进行聚类的最佳方法。组合学告诉我们，对于一个只有8个顶点的网络，有4140种不同的聚类方式。一个由16个顶点组成的网络可以以超过100亿种方式聚类。对于32个顶点的网络，有超过128septillion(10^21)种可能的聚类方式；如果你的网络有80个顶点，那么可能的聚类方式的数量超过了可观察宇宙中可能的聚类方式的数量。原子数。因此，我们必须求助于一种启发式方法，该方法可以很好地评估产生最高模块化分数的集群，而无需尝试所有可能性。这是一种称为Fast-GreedyModularity-Maximization的算法，它有点类似于上面介绍的凝聚层次聚类算法。只不过Mod-Max并不是根据距离来融合分组，而是根据模块化的变化来分组。它是这样工作的：首先最初将每个顶点分配给它自己的社区，然后计算整个网络的模块化M。步骤1要求每个社区对至少由一条边连接，如果合并两个社区，算法将计算由此产生的模块性变化ΔM。第二步，取ΔM增幅最大的组对，然后进行融合。然后为该集群计算并记录新的模块化M。重复步骤1和2——每次融合组对，使你最终获得最大增益ΔM——然后记录新的聚类模式及其相应的模块化分数M。当所有顶点被分组到一个巨大的集群时停止。该算法然后检查流程中的记录并找到返回最高M值的聚类模式。这是返回的组结构。社区发现（communitydetection）是图论中的一个热门研究领域。其局限性主要体现在忽略了一些小簇，仅适用于结构化图模型。但是这类算法在典型的结构化数据和真实的网络数据中都有很好的表现。结语以上就是数据科学家应该知道的6大聚类算法！我们将以显示各种算法的可视化结束本文！
