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

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

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

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

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

均值漂移聚类有哪些算法的整个过程

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

基于密度的聚类有哪些算法方法（DBSCAN）

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

• DBSCAN 从一个没有被访问过的任意起始数据点开始。这个点的邻域是用距离 ε（ε 距离内的所有点都是邻域点）提取的。

• 如果在这个邻域內有足够数量的点（根据 minPoints）则聚类有哪些算法过程开始，并且当前数据点成为新簇的第一个点否则，该点将会被标记为噪声（稍后这個噪声点可能仍会成为聚类有哪些算法的一部分）在这两种情况下，该点都被标记为「已访问」

• 对于新簇中的第一个点，其 ε 距离邻域内的点也成为该簇的一部分这个使所有 ε 邻域内的点都属于同一个簇的过程将对所有刚刚添加到簇中的新点进行重复。

• 重复步骤 2 和 3矗到簇中所有的点都被确定，即簇的 ε 邻域内的所有点都被访问和标记过

• 一旦我们完成了当前的簇，一个新的未访问点将被检索和处理导致发现另一个簇或噪声。重复这个过程直到所有的点被标记为已访问由于所有点都已经被访问，所以每个点都属于某个簇或噪声

  
  

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

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

用高斯混合模型（GMM）的较大期望（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它将两个簇之间的距离定义为第一个簇中的数据点與第二个簇中的数据点之间的平均距离。

• 在每次迭代中我们将两个簇合并成一个。这两个要合并的簇应具有最小的 average linkage即根据我们选择的距离度量标准，这两个簇之间的距离最小因此是最相似的，应该合并在一起

• 重复步骤 2 直到我们到达树根，即我们只有一个包含所有数據点的簇这样我们只需要选择何时停止合并簇，即何时停止构建树来选择最终需要多少个簇！

  
  

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

当我们的数据可以被表示为一个网络或图（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 之间存在一个「非预期」的边时，得到的值更高

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

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

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

• 首先初始分配每个顶点到其自己的团体然后計算整个网络的模块性 M。

• 第 1 步要求每个团体对（community pair）至少被一条单边链接如果有两个团体融合到了一起，该算法就计算由此造成的模块性妀变 ΔM

• 第 2 步是取 ΔM 出现了较大增长的团体对，然后融合然后为这个聚类有哪些算法计算新的模块性 M，并记录下来

• 重复第 1 步和 第 2 步——每一次都融合团体对，这样最后得到 ΔM 的较大增益然后记录新的聚类有哪些算法模式及其相应的模块性分数 M。

• 当所有的顶点都被分组荿了一个巨型聚类有哪些算法时就可以停止了。然后该算法会检查这个过程中的记录然后找到其中返回了较高 M 值的聚类有哪些算法模式。这就是返回的团体结构

  
  

团体检测（community detection）是现在图论中一个热门的研究领域，它的局限性主要体现在会忽略一些小的集群且只适用于結构化的图模型。但这一类算法在典型的结构化数据中和现实网状数据都有非常好的性能

以上就是数据科学家应该知道的 6 大聚类有哪些算法算法！我们将以展示各类算法的可视化效果结束本文！