2.3. 聚类

可以使用模块 sklearn.cluster 对无标签数据进行聚类。

每种聚类算法都有两种变体：一种是类，它实现了 fit 方法以在训练数据上学习聚类；另一种是函数，它给定训练数据后，返回一个对应于不同聚类的整数标签数组。对于类，训练数据上的标签可以在 labels_ 属性中找到。

输入数据

需要注意的一个重要事项是，此模块中实现的算法可以接受不同类型的矩阵作为输入。所有方法都接受形状为 (n_samples, n_features) 的标准数据矩阵。这些矩阵可以从 sklearn.feature_extraction 模块中的类获得。对于 AffinityPropagation、SpectralClustering 和 DBSCAN，也可以输入形状为 (n_samples, n_samples) 的相似度矩阵。这些矩阵可以从 sklearn.metrics.pairwise 模块中的函数获得。

2.3.1. 聚类方法概述

scikit-learn 中聚类算法的比较

方法名称	参数	可伸缩性	用例	几何（使用的度量）
K-均值	聚类数量	对于非常大的 n_samples，中等大小的 n_clusters，使用MiniBatch 代码	通用，聚类大小均匀，扁平几何，聚类数量不多，归纳式	点之间的距离
相似度传播	阻尼，样本偏好	不可伸缩，与 n_samples 相关	聚类数量多，聚类大小不均匀，非扁平几何，归纳式	图距离（例如最近邻图）
均值漂移	带宽	不可伸缩，与 n_samples 相关	聚类数量多，聚类大小不均匀，非扁平几何，归纳式	点之间的距离
谱聚类	聚类数量	中等 n_samples，小 n_clusters	聚类数量少，聚类大小均匀，非扁平几何，转导式	图距离（例如最近邻图）
Ward 层次聚类	聚类数量或距离阈值	大 n_samples 和 n_clusters	聚类数量多，可能存在连通性约束，转导式	点之间的距离
凝聚聚类	聚类数量或距离阈值，连接类型，距离	大 n_samples 和 n_clusters	聚类数量多，可能存在连通性约束，非欧氏距离，转导式	任意成对距离
DBSCAN	邻域大小	非常大的 n_samples，中等大小的 n_clusters	非扁平几何，聚类大小不均匀，异常点去除，转导式	最近点之间的距离
HDBSCAN	最小聚类成员数，最小邻近点数	大 n_samples，中等大小的 n_clusters	非扁平几何，聚类大小不均匀，异常点去除，转导式，层次结构，可变聚类密度	最近点之间的距离
OPTICS	最小聚类成员数	非常大的 n_samples，大 n_clusters	非扁平几何，聚类大小不均匀，可变聚类密度，异常点去除，转导式	点之间的距离
高斯混合	许多	不可伸缩	扁平几何，适用于密度估计，归纳式	到中心的马哈拉诺比斯距离
BIRCH	分支因子，阈值，可选全局聚类器。	大 n_clusters 和 n_samples	大数据集，异常点去除，数据降维，归纳式	点之间的欧氏距离
二分K-均值	聚类数量	非常大的 n_samples，中等大小的 n_clusters	通用，聚类大小均匀，扁平几何，无空聚类，归纳式，层次结构	点之间的距离

当聚类具有特定形状（即非扁平流形）且标准欧氏距离不是正确度量时，非扁平几何聚类非常有用。这种情况出现在上图的前两行中。

高斯混合模型，用于聚类，在文档的另一章节中进行了描述，专门讨论了混合模型。KMeans 可以看作是高斯混合模型的一个特例，每个分量具有相同的协方差。

转导式聚类方法（与归纳式聚类方法相对）不适用于新的、未见过的数据。

示例

• 归纳式聚类：处理新数据的归纳式聚类模型的示例。

2.3.2. K-均值

KMeans 算法通过尝试将样本分离成 n 个方差相等的组来聚类数据，从而最小化一个称为惯性（inertia）或簇内平方和（within-cluster sum-of-squares）的准则（见下文）。此算法需要指定聚类的数量。它对大量样本具有良好的伸缩性，并已应用于许多不同领域的大量应用。

k-means 算法将一组 \(N\) 个样本 \(X\) 分成 \(K\) 个不相交的簇 \(C\)，每个簇由簇中样本的均值 \(\mu_j\) 描述。这些均值通常被称为簇“质心”；请注意，它们通常不是来自 \(X\) 中的点，尽管它们位于相同的空间中。

K-均值算法旨在选择使惯性（inertia）或簇内平方和准则（within-cluster sum-of-squares criterion）最小化的质心

\[\sum_{i=0}^{n}\min_{\mu_j \in C}(||x_i - \mu_j||^2)\]

惯性可以被认为是衡量聚类内部一致性的指标。它存在各种缺点

• 惯性假设簇是凸且各向同性的，但这并非总是如此。它对细长形簇或形状不规则的流形表现不佳。

• 惯性不是一个归一化指标：我们只知道较低的值更好，零是最佳值。但在非常高维的空间中，欧氏距离往往会膨胀（这是所谓的“维度诅咒”的一个实例）。在 k-均值聚类之前运行诸如主成分分析（PCA）之类的降维算法可以缓解此问题并加快计算速度。

有关上述问题的更详细描述以及如何解决这些问题，请参阅示例 k-means 假设的演示 和 使用 KMeans 聚类上的轮廓分析选择聚类数量。

K-均值通常被称为 Lloyd 算法。基本来说，该算法有三个步骤。第一步选择初始质心，最基本的方法是从数据集 \(X\) 中选择 \(k\) 个样本。初始化后，K-均值包括循环执行另外两个步骤。第一步将每个样本分配给其最近的质心。第二步通过计算分配给每个先前质心的所有样本的均值来创建新的质心。计算旧质心和新质心之间的差异，算法重复最后这两个步骤，直到此值小于某个阈值。换句话说，它重复直到质心不再显著移动。

K-均值等同于具有一个小的、全相等、对角协方差矩阵的期望最大化算法。

该算法也可以通过Voronoi 图的概念来理解。首先使用当前质心计算点的 Voronoi 图。Voronoi 图中的每个段都成为一个单独的簇。其次，质心更新为每个段的均值。然后算法重复此过程，直到满足停止准则。通常，当迭代之间目标函数的相对减少量小于给定容差值时，算法停止。在此实现中并非如此：当质心移动小于容差时，迭代停止。

只要有足够的时间，K-均值总会收敛，但这可能收敛到局部最小值。这高度依赖于质心的初始化。因此，计算通常会进行多次，使用不同的质心初始化。解决此问题的一种方法是 k-means++ 初始化方案，该方案已在 scikit-learn 中实现（使用 init='k-means++' 参数）。这会将质心初始化为（通常）彼此远离，从而可能比随机初始化产生更好的结果，如参考文献所示。有关比较不同初始化方案的详细示例，请参阅 手写数字数据上的 K-Means 聚类演示 和 k-means 初始化影响的经验评估。

K-means++ 也可以独立调用，用于为其他聚类算法选择种子，详见 sklearn.cluster.kmeans_plusplus 及其用法示例。

该算法支持样本权重，可以通过参数 sample_weight 给出。这允许在计算簇中心和惯性值时对某些样本分配更大的权重。例如，为样本分配权重 2 等同于将该样本的副本添加到数据集 \(X\) 中。

示例

• 使用 k-均值对文本文档进行聚类：基于稀疏数据使用 KMeans 和 MiniBatchKMeans 进行文档聚类。

• K-Means++ 初始化示例：使用 K-means++ 为其他聚类算法选择种子。

2.3.2.1. 低级并行化

KMeans 得益于基于 OpenMP 的 Cython 并行化。数据的小块（256 个样本）并行处理，这还带来了低内存占用。有关如何控制线程数量的更多详细信息，请参阅我们的并行化说明。

示例

• k-均值假设的演示：演示 k-均值何时直观执行以及何时不直观执行。

• 手写数字数据上的 K-Means 聚类演示：聚类手写数字。

参考文献

• “k-means++: The advantages of careful seeding” Arthur, David, and Sergei Vassilvitskii, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics (2007)

2.3.2.2. 迷你批次 K-均值

MiniBatchKMeans 是 KMeans 算法的一个变体，它使用迷你批次（mini-batches）来减少计算时间，同时仍然尝试优化相同的目标函数。迷你批次是输入数据的子集，在每次训练迭代中随机采样。这些迷你批次显著减少了收敛到局部解所需的计算量。与其他减少 k-均值收敛时间的算法相比，迷你批次 k-均值产生的结果通常仅略差于标准算法。

该算法在两个主要步骤之间迭代，类似于普通的 k-均值。在第一步中，从数据集中随机抽取 \(b\) 个样本，形成一个迷你批次。然后将这些样本分配给最近的质心。在第二步中，更新质心。与 k-均值不同，这是按每个样本进行的。对于迷你批次中的每个样本，通过计算该样本与所有先前分配给该质心的样本的流式平均值来更新分配的质心。这会降低质心随时间的变化率。这些步骤一直执行到收敛或达到预定迭代次数。

MiniBatchKMeans 比 KMeans 收敛更快，但结果质量有所降低。在实践中，这种质量差异可能很小，如示例和引用的参考文献所示。

示例

• K-均值和迷你批次 K-均值聚类算法的比较：KMeans 和 MiniBatchKMeans 的比较。

• 使用 k-均值对文本文档进行聚类：基于稀疏数据使用 KMeans 和 MiniBatchKMeans 进行文档聚类。

• 人脸部位字典的在线学习

参考文献

• “Web Scale K-Means clustering” D. Sculley, Proceedings of the 19th international conference on World wide web (2010)

2.3.3. 相似度传播

AffinityPropagation 通过在样本对之间发送消息直到收敛来创建聚类。然后使用少量范例来描述数据集，这些范例被识别为最能代表其他样本的范例。在样本对之间发送的消息表示一个样本作为另一个样本范例的适用性，该适用性会根据来自其他样本对的值进行更新。这种更新会迭代进行直到收敛，此时会选择最终的范例，从而给出最终的聚类。

相似度传播之所以有趣，是因为它根据提供的数据自动选择聚类数量。为此，两个重要的参数是偏好（preference），它控制使用的范例数量，以及阻尼因子（damping factor），它阻尼责任（responsibility）和可用性（availability）消息，以避免在更新这些消息时出现数值振荡。

相似度传播的主要缺点是其复杂性。该算法的时间复杂度为 \(O(N^2 T)\)，其中 \(N\) 是样本数量，\(T\) 是收敛前的迭代次数。此外，如果使用密集相似度矩阵，内存复杂度为 \(O(N^2)\)，但如果使用稀疏相似度矩阵则可降低。这使得相似度传播最适用于中小型数据集。

算法描述

点之间发送的消息属于两类之一。第一类是责任 \(r(i, k)\)，它是样本 \(k\) 应该成为样本 \(i\) 的范例的累积证据。第二类是可用性 \(a(i, k)\)，它是样本 \(i\) 应该选择样本 \(k\) 作为其范例的累积证据，并且考虑了所有其他样本对 \(k\) 应该成为范例的值。通过这种方式，如果范例 (1) 与许多样本足够相似，并且 (2) 被许多样本选择为自身的代表，则样本会选择它们。

更正式地，样本 \(k\) 作为样本 \(i\) 的范例的责任由下式给出

\[r(i, k) \leftarrow s(i, k) - max [ a(i, k') + s(i, k') \forall k' \neq k ]\]

其中 \(s(i, k)\) 是样本 \(i\) 和 \(k\) 之间的相似度。样本 \(k\) 作为样本 \(i\) 的范例的可用性由下式给出

\[a(i, k) \leftarrow min [0, r(k, k) + \sum_{i'~s.t.~i' \notin \{i, k\}}{r(i', k)}]\]

首先，\(r\) 和 \(a\) 的所有值都设置为零，然后迭代计算每个值直到收敛。如上所述，为了避免在更新消息时出现数值振荡，在迭代过程中引入了阻尼因子 \(\lambda\)

\[r_{t+1}(i, k) = \lambda\cdot r_{t}(i, k) + (1-\lambda)\cdot r_{t+1}(i, k)\]

\[a_{t+1}(i, k) = \lambda\cdot a_{t}(i, k) + (1-\lambda)\cdot a_{t+1}(i, k)\]

其中 \(t\) 表示迭代次数。

示例

• 相似度传播聚类算法演示：对具有 3 个类别的合成 2D 数据集进行相似度传播。

• 可视化股市结构：在金融时间序列上进行相似度传播以查找公司组。

2.3.4. 均值漂移

MeanShift 聚类旨在发现样本平滑密度中的斑点（blobs）。它是一种基于质心的算法，通过更新质心候选者为给定区域内点的均值来工作。然后，这些候选者在后处理阶段进行过滤，以消除近似重复项，从而形成最终的质心集合。

数学细节

质心候选者的位置使用一种称为爬山（hill climbing）的技术进行迭代调整，该技术寻找估计概率密度的局部最大值。给定迭代 \(t\) 的质心候选者 \(x\)，候选者根据以下方程进行更新

\[x^{t+1} = x^t + m(x^t)\]

其中 \(m\) 是均值漂移（mean shift）向量，它为每个质心计算，指向点密度最大增长的区域。为了计算 \(m\)，我们将 \(N(x)\) 定义为 \(x\) 周围给定距离内的样本邻域。然后使用以下方程计算 \(m\)，有效地将质心更新为其邻域内样本的均值

\[m(x) = \frac{1}{|N(x)|} \sum_{x_j \in N(x)}x_j - x\]

通常，\(m\) 的方程取决于用于密度估计的核。通用公式是

\[m(x) = \frac{\sum_{x_j \in N(x)}K(x_j - x)x_j}{\sum_{x_j \in N(x)}K(x_j - x)} - x\]

在我们的实现中，如果 \(x\) 足够小，\(K(x)\) 等于 1，否则等于 0。实际上 \(K(y - x)\) 指示 \(y\) 是否在 \(x\) 的邻域中。

该算法会自动设置聚类数量，而不是依赖于参数 bandwidth，该参数决定搜索区域的大小。此参数可以手动设置，但如果未设置带宽，则可以使用提供的 estimate_bandwidth 函数进行估计。

该算法可伸缩性不高，因为它在算法执行期间需要多次最近邻搜索。算法保证收敛，但当质心变化很小时，算法将停止迭代。

新样本的标记通过查找给定样本的最近质心来执行。

示例

• 均值漂移聚类算法演示：对具有 3 个类别的合成 2D 数据集进行均值漂移聚类。

参考文献

• “Mean shift: A robust approach toward feature space analysis” D. Comaniciu and P. Meer, IEEE Transactions on Pattern Analysis and Machine Intelligence (2002)

2.3.5. 谱聚类

SpectralClustering 执行样本之间亲和矩阵的低维嵌入，然后对低维空间中的特征向量分量进行聚类，例如通过 KMeans。如果亲和矩阵稀疏且使用 amg 求解器来解决特征值问题，则计算效率特别高（注意，amg 求解器需要安装 pyamg 模块。）

当前版本的 SpectralClustering 需要预先指定聚类数量。它适用于少量聚类，但不建议用于大量聚类。

对于两个聚类，SpectralClustering 求解相似图上归一化割问题的凸松弛：将图切成两部分，使得被切割的边的权重与每个聚类内部的边的权重相比很小。当处理图像时，这个准则特别有趣，其中图顶点是像素，相似图的边的权重是使用图像梯度的函数计算的。

警告

将距离转换为良好行为的相似度

请注意，如果您的相似度矩阵的值分布不佳，例如存在负值或使用距离矩阵而非相似度，则谱问题将是奇异的，问题无法求解。在这种情况下，建议对矩阵的元素应用转换。例如，在有符号距离矩阵的情况下，通常应用热核（heat kernel）

similarity = np.exp(-beta * distance / distance.std())

请参阅示例以了解此类应用。

示例

• 用于图像分割的谱聚类：使用谱聚类从嘈杂背景中分割对象。

• 将希腊硬币图片分割成区域：使用谱聚类将硬币图片分割成区域。

2.3.5.1. 不同的标签分配策略

可以使用不同的标签分配策略，对应于 SpectralClustering 的 assign_labels 参数。"kmeans" 策略可以匹配更精细的细节，但可能不稳定。特别是，除非您控制 random_state，否则它可能无法在多次运行中重现，因为它依赖于随机初始化。替代的 "discretize" 策略是 100% 可重现的，但倾向于创建相当均匀且几何形状的分区。最近添加的 "cluster_qr" 选项是一种确定性替代方案，它倾向于在下面的示例应用中创建视觉上最佳的分区。

assign_labels="kmeans"	assign_labels="discretize"	assign_labels="cluster_qr"

参考文献

• “Multiclass spectral clustering” Stella X. Yu, Jianbo Shi, 2003

• “Simple, direct, and efficient multi-way spectral clustering” Anil Damle, Victor Minden, Lexing Ying, 2019

2.3.5.2. 谱聚类图

谱聚类也可以通过其谱嵌入来划分图。在这种情况下，亲和矩阵是图的邻接矩阵，并且 SpectralClustering 用 affinity='precomputed' 初始化

>>> from sklearn.cluster import SpectralClustering
>>> sc = SpectralClustering(3, affinity='precomputed', n_init=100,
...                         assign_labels='discretize')
>>> sc.fit_predict(adjacency_matrix)  

参考文献

• “A Tutorial on Spectral Clustering” Ulrike von Luxburg, 2007

• “Normalized cuts and image segmentation” Jianbo Shi, Jitendra Malik, 2000

• “A Random Walks View of Spectral Segmentation” Marina Meila, Jianbo Shi, 2001

• “On Spectral Clustering: Analysis and an algorithm” Andrew Y. Ng, Michael I. Jordan, Yair Weiss, 2001

• “Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge” David Zhuzhunashvili, Andrew Knyazev

2.3.6. 层次聚类

层次聚类是聚类算法的一个通用族，它们通过不断合并或分裂来构建嵌套的聚类。这种聚类层次结构表示为一棵树（或树状图）。树的根是包含所有样本的唯一聚类，叶子是仅包含一个样本的聚类。有关更多详细信息，请参阅维基百科页面。

AgglomerativeClustering 对象使用自下而上的方法执行层次聚类：每个观察值都从自己的聚类开始，然后聚类逐个合并在一起。连接准则决定了用于合并策略的度量

• Ward 最小化所有聚类内部平方差之和。它是一种方差最小化方法，从这个意义上讲，它与 k-均值目标函数相似，但采用凝聚层次方法解决。

• 最大（Maximum）或完全连接（complete linkage）最小化聚类对之间观察值的最大距离。

• 平均连接（Average linkage）最小化聚类对之间所有观察值距离的平均值。

• 单连接（Single linkage）最小化聚类对之间最近观察值的距离。

AgglomerativeClustering 在与连通性矩阵结合使用时也可以扩展到大量样本，但当样本之间未添加连通性约束时计算成本高昂：它在每一步都会考虑所有可能的合并。

特征凝聚

FeatureAgglomeration 使用凝聚聚类将非常相似的特征组合在一起，从而减少特征数量。它是一种降维工具，参见无监督降维。

2.3.6.1. 不同的连接类型：Ward、完全、平均和单连接

AgglomerativeClustering 支持 Ward、单、平均和完全连接策略。

凝聚聚类具有“强者恒强”的特点，导致聚类大小不均匀。在这方面，单连接是表现最差的策略，而 Ward 则能产生最规则的聚类大小。然而，Ward 无法改变亲和度（或聚类中使用的距离），因此对于非欧氏度量，平均连接是一个很好的替代方案。单连接虽然对噪声数据不鲁棒，但计算效率很高，因此对于提供较大数据集的层次聚类可能很有用。单连接在非球状数据上也能表现良好。

示例

• 数字 2D 嵌入上的各种凝聚聚类：探索真实数据集中不同的连接策略。

  • 比较玩具数据集上的不同层次连接方法：探索玩具数据集中不同的连接策略。

2.3.6.2. 聚类层次结构的可视化

可以将表示聚类层次合并的树可视化为树状图。视觉检查通常有助于理解数据结构，尽管在小样本量的情况下更有用。

示例

• 绘制层次聚类树状图

2.3.6.3. 添加连通性约束

AgglomerativeClustering 的一个有趣方面是，可以通过连接矩阵向该算法添加连接约束（只有相邻的聚类才能合并），该矩阵为每个样本定义了遵循给定数据结构的相邻样本。例如，在下面的 swiss-roll 示例中，连接约束禁止合并在 swiss-roll 上不相邻的点，从而避免形成跨越卷叠的重叠部分的聚类。

这些约束有助于施加特定的局部结构，但它们也使算法更快，尤其是在样本数量较多时。

连接约束通过连接矩阵施加：一个 scipy 稀疏矩阵，仅在行和列与应连接的数据集索引的交点处有元素。该矩阵可以从先验信息构建：例如，您可能希望通过仅合并相互链接的页面来聚类网页。它也可以从数据中学习，例如使用 sklearn.neighbors.kneighbors_graph 将合并限制为最近邻，如此示例所示，或者使用 sklearn.feature_extraction.image.grid_to_graph 仅允许在图像上合并相邻像素，如硬币示例所示。

警告

单连接、平均连接和完全连接的连通性约束

连通性约束与单连接、完全连接或平均连接可以增强凝聚聚类“强者愈强”的特点，尤其是当它们使用 sklearn.neighbors.kneighbors_graph 构建时。在聚类数量很少的极限情况下，它们倾向于产生少量宏观占据的聚类和几乎为空的聚类。（参见有结构与无结构的凝聚聚类中的讨论）。单连接是对此问题最脆弱的连接选项。

示例

• 对硬币图像进行结构化 Ward 层次聚类的演示：Ward 聚类将硬币图像分割成区域。

• 层次聚类：结构化与非结构化 Ward：在 swiss-roll 上使用 Ward 算法的示例，比较结构化方法与非结构化方法。

• 特征凝聚与单变量选择：基于 Ward 层次聚类的特征凝聚降维示例。

• 有结构与无结构的凝聚聚类

2.3.6.4. 改变度量

单连接、平均连接和完全连接可以与各种距离（或亲和度）一起使用，特别是欧氏距离（l2）、曼哈顿距离（或城市街区距离，或l1）、余弦距离或任何预先计算的亲和度矩阵。

• l1 距离通常适用于稀疏特征或稀疏噪声：即许多特征为零的情况，例如在文本挖掘中使用罕见词的出现。

• 余弦（cosine）距离很有趣，因为它对信号的全局缩放是不变的。

选择度量的指导原则是使用能够最大化不同类别样本之间的距离，并最小化每个类别内部距离的度量。

示例

• 使用不同度量的凝聚聚类

2.3.6.5. 二分 K-均值

BisectingKMeans 是 KMeans 的迭代变体，使用分裂式层次聚类。它不是一次性创建所有质心，而是基于先前的聚类逐步选择质心：一个聚类被反复分成两个新聚类，直到达到目标聚类数量。

当聚类数量较大时，BisectingKMeans 比 KMeans 更高效，因为它在每次二分时只处理数据的一个子集，而 KMeans 总是处理整个数据集。

尽管 BisectingKMeans 无法从 "k-means++" 初始化的优势中受益（根据其设计），但在惯性方面，它仍然会产生与 KMeans(init="k-means++") 可比的结果，且计算成本更低，并且很可能比随机初始化的 KMeans 产生更好的结果。

如果聚类数量相对于数据点数量较少，则此变体比凝聚聚类更高效。

此变体也不会产生空聚类。

存在两种选择要拆分的聚类策略

• bisecting_strategy="largest_cluster" 选择包含最多点的聚类

• bisecting_strategy="biggest_inertia" 选择惯性最大的聚类（内部平方和最大的聚类）

在大多数情况下，通过最大数据点数量进行选择可以产生与通过惯性进行选择同样准确的结果，并且速度更快（特别是对于大量数据点，计算误差可能成本很高）。

通过最大数据点数量进行选择也可能产生大小相似的聚类，而 KMeans 以产生不同大小的聚类而闻名。

二分 K-均值和常规 K-均值之间的差异可以在示例二分 K-均值和常规 K-均值性能比较中看到。常规 K-均值算法倾向于创建不相关的聚类，而二分 K-均值创建的聚类则井然有序，并形成相当明显的层次结构。

参考文献

• “A Comparison of Document Clustering Techniques” Michael Steinbach, George Karypis and Vipin Kumar, Department of Computer Science and Egineering, University of Minnesota (June 2000)

• “Performance Analysis of K-Means and Bisecting K-Means Algorithms in Weblog Data” K.Abirami and Dr.P.Mayilvahanan, International Journal of Emerging Technologies in Engineering Research (IJETER) Volume 4, Issue 8, (August 2016)

• “Bisecting K-means Algorithm Based on K-valued Self-determining and Clustering Center Optimization” Jian Di, Xinyue Gou School of Control and Computer Engineering,North China Electric Power University, Baoding, Hebei, China (August 2017)

2.3.7. DBSCAN

DBSCAN 算法将聚类视为被低密度区域分隔的高密度区域。由于这种通用视图，DBSCAN 找到的聚类可以是任何形状，这与假设聚类为凸形的 k-均值不同。DBSCAN 的核心组成部分是核心样本（core samples）的概念，这些样本位于高密度区域。因此，一个聚类是一组相互接近（通过某种距离度量）的核心样本，以及一组接近核心样本（但本身不是核心样本）的非核心样本。该算法有两个参数：min_samples 和 eps，它们正式定义了我们所说的密集（dense）的含义。min_samples 越大或 eps 越小，表示形成聚类所需的密度越高。

更正式地，我们将核心样本定义为数据集中的一个样本，使得在距离 eps 内存在 min_samples 个其他样本，这些样本被定义为核心样本的邻居。这告诉我们核心样本位于向量空间的密集区域中。一个聚类是一组核心样本，可以通过递归地选取一个核心样本，找到其所有是核心样本的邻居，然后找到它们所有是核心样本的邻居，以此类推来构建。一个聚类还包含一组非核心样本，这些样本是聚类中核心样本的邻居，但它们本身不是核心样本。直观地说，这些样本位于聚类的边缘。

根据定义，任何核心样本都是聚类的一部分。任何不是核心样本，并且距离任何核心样本至少 eps 的样本，都被算法视为异常值。

虽然参数 min_samples 主要控制算法对噪声的容忍度（在嘈杂和大型数据集上可能需要增加此参数），但参数 eps 对于数据集和距离函数来说选择恰当至关重要，通常不能保留默认值。它控制点的局部邻域。如果选择太小，大多数数据将根本不会被聚类（并标记为“噪声”的 -1）。如果选择太大，它会导致相邻的聚类合并成一个聚类，并最终导致整个数据集被返回为一个单一聚类。文献中讨论了一些选择此参数的启发式方法，例如基于最近邻距离图中的拐点（如下面参考文献所述）。

在下图中，颜色表示聚类成员资格，大圆圈表示算法找到的核心样本。小圆圈是非核心样本，但仍是聚类的一部分。此外，异常值用黑色点表示。

示例

• DBSCAN 聚类算法演示

实现

DBSCAN 算法是确定性的，在给定相同数据和相同顺序时，总是生成相同的聚类。然而，当数据以不同顺序提供时，结果可能会有所不同。首先，尽管核心样本总是被分配到相同的聚类，但这些聚类的标签将取决于数据中遇到这些样本的顺序。其次，更重要的是，非核心样本被分配到的聚类可能因数据顺序而异。当一个非核心样本距离不同聚类中的两个核心样本的距离小于 eps 时，就会发生这种情况。根据三角不等式，这两个核心样本之间的距离必须大于 eps，否则它们将在同一个聚类中。非核心样本被分配到在数据遍历中首先生成的聚类，因此结果将取决于数据顺序。

当前的实现使用球树（ball trees）和 kd 树（kd-trees）来确定点的邻域，这避免了计算完整的距离矩阵（如 scikit-learn 0.14 版本之前所做）。使用自定义度量的可能性得以保留；有关详细信息，请参阅 NearestNeighbors。

大样本量下的内存消耗

此实现默认情况下不是内存高效的，因为它在无法使用kd-trees或ball-trees（例如，使用稀疏矩阵）的情况下会构建一个完整的成对相似度矩阵。这个矩阵将消耗 \(n^2\) 个浮点数。解决此问题的一些机制是：

• 结合使用 OPTICS 聚类和 extract_dbscan 方法。OPTICS 聚类也会计算完整的成对矩阵，但每次只在内存中保留一行（内存复杂度为 n）。

• 可以以内存高效的方式预计算稀疏半径邻域图（其中缺失的条目被假定为超出eps），然后使用 metric='precomputed' 在此图上运行DBSCAN。参见 sklearn.neighbors.NearestNeighbors.radius_neighbors_graph。

• 数据集可以被压缩，无论是通过删除数据中存在的精确重复项，还是通过使用BIRCH。这样，您只需用相对较少数量的代表来表示大量的点。然后，在拟合DBSCAN时可以提供一个 sample_weight。

参考文献

• 一种用于发现大型空间数据库中带噪声的聚类的基于密度算法 Ester, M., H. P. Kriegel, J. Sander, and X. Xu, In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226-231. 1996

• DBSCAN 重访，再访：为什么以及如何（仍然）使用 DBSCAN。 Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). In ACM Transactions on Database Systems (TODS), 42(3), 19。

2.3.8. HDBSCAN

HDBSCAN 算法可以看作是 DBSCAN 和 OPTICS 的扩展。具体来说，DBSCAN 假设聚类准则（即密度要求）是 全局同质的。换句话说，DBSCAN 可能难以成功捕获具有不同密度的簇。HDBSCAN 缓解了这一假设，并通过构建聚类问题的替代表示来探索所有可能的密度尺度。

注意

此实现改编自HDBSCAN的原始实现 scikit-learn-contrib/hdbscan，基于 [LJ2017]。

示例

• HDBSCAN聚类算法演示

2.3.8.1. 互可达图

HDBSCAN 首先定义 \(d_c(x_p)\)，即样本 \(x_p\) 的 核心距离，其定义为到其第 min_samples 个最近邻的距离，其中也计算其自身。例如，如果 min_samples=5 且 \(x_*\) 是 \(x_p\) 的第 5 个最近邻，则核心距离为

\[d_c(x_p)=d(x_p, x_*).\]

接下来，它定义了两个点 \(x_p, x_q\) 的 相互可达距离 \(d_m(x_p, x_q)\)，其定义为

\[d_m(x_p, x_q) = \max\{d_c(x_p), d_c(x_q), d(x_p, x_q)\}\]

这两个概念允许我们构建 相互可达图 \(G_{ms}\)，该图针对固定的 min_samples 选择而定义，其中每个样本 \(x_p\) 与图中的一个顶点相关联，因此点 \(x_p, x_q\) 之间的边是它们之间的相互可达距离 \(d_m(x_p, x_q)\)。我们可以通过从原始图中移除任何值大于 \(\varepsilon\) 的边来构建此图的子集，表示为 \(G_{ms,\varepsilon}\)。在此阶段，任何核心距离小于 \(\varepsilon\) 的点都被标记为噪声。然后，通过查找此修剪图的连通分量来对剩余点进行聚类。

注意

获取修剪图 \(G_{ms,\varepsilon}\) 的连通分量等同于运行带有 min_samples 和 \(\varepsilon\) 的DBSCAN*。DBSCAN* 是 [CM2013] 中提到的DBSCAN的略微修改版本。

2.3.8.2. 层次聚类

HDBSCAN可以被视为一种算法，它在所有 \(\varepsilon\) 值上执行DBSCAN*聚类。如前所述，这等同于查找所有 \(\varepsilon\) 值的相互可达图的连通分量。为了高效地完成此操作，HDBSCAN首先从完全连接的相互可达图中提取最小生成树（MST），然后贪婪地剪切权重最高的边。HDBSCAN算法的概述如下：

1. 提取 \(G_{ms}\) 的MST。

2. 通过为每个顶点添加一条“自环边”来扩展MST，其权重等于底层样本的核心距离。

3. 为MST初始化一个单一的簇和标签。

4. 从MST中移除权重最大的边（同时移除所有权重相同的边）。

5. 将簇标签分配给包含现在已移除边的端点的连通分量。如果该分量至少没有一条边，则将其分配一个“空”标签，标记为噪声。

6. 重复步骤 4-5，直到不再有连通分量。

因此，HDBSCAN能够以层次化的方式，针对固定的 min_samples 选择，获得DBSCAN*可实现的所有可能分区。事实上，这使得HDBSCAN能够对多个密度进行聚类，因此不再需要将 \(\varepsilon\) 作为超参数给出。相反，它仅依赖于 min_samples 的选择，这通常是一个更鲁棒的超参数。

HDBSCAN 可以通过一个额外的超参数 min_cluster_size 进行平滑处理，该参数指定在层次聚类过程中，样本数量少于 minimum_cluster_size 的分量被视为噪声。实际上，可以将 minimum_cluster_size = min_samples 来耦合参数并简化超参数空间。

参考文献

[CM2013]

Campello, R.J.G.B., Moulavi, D., Sander, J. (2013). 基于层次密度估计的密度聚类。载于：Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (eds) 知识发现与数据挖掘进展。PAKDD 2013。计算机科学讲义(), vol 7819. 柏林，海德堡：施普林格出版社。基于层次密度估计的密度聚类

[LJ2017]

L. McInnes and J. Healy, (2017). 加速分层密度聚类。载于：IEEE International Conference on Data Mining Workshops (ICDMW), 2017, pp. 33-42。加速分层密度聚类

2.3.9. OPTICS

OPTICS 算法与 DBSCAN 算法有许多相似之处，可以视为DBSCAN的泛化，它将 eps 要求从单个值放宽到值范围。DBSCAN和OPTICS之间的关键区别在于OPTICS算法构建了一个 可达性 图，该图为每个样本分配了一个 reachability_ 距离，以及在聚类 ordering_ 属性中的一个位置；这两个属性在模型拟合时被分配，并用于确定聚类成员身份。如果OPTICS以 inf 的默认值运行 max_eps，那么可以使用 cluster_optics_dbscan 方法以线性时间对任何给定的 eps 值重复执行DBSCAN风格的聚类提取。将 max_eps 设置为较低的值将缩短运行时间，可以将其视为每个点找到其他潜在可达点的最大邻域半径。

OPTICS 生成的 可达性 距离允许对单个数据集中的聚类进行可变密度提取。如上图所示，将 可达性 距离和数据集 ordering_ 结合起来，生成了一个 可达性图，其中点密度表示在 Y 轴上，点被排序，使得附近的点相邻。在单个值处“切割”可达性图会产生类似DBSCAN的结果；“切割”上方的所有点都被归类为噪声，并且每次从左到右读取时出现中断都表示一个新的聚类。OPTICS 的默认聚类提取通过查看图中的陡峭斜率来查找聚类，用户可以使用参数 xi 定义什么是陡峭斜率。图本身还有其他分析可能性，例如通过可达性图谱系图生成数据的层次表示，并且可以通过 cluster_hierarchy_ 参数访问算法检测到的聚类层次结构。上图已进行颜色编码，以使平面空间中的聚类颜色与可达性图的线性分段聚类相匹配。请注意，蓝色和红色聚类在可达性图中是相邻的，并且可以在层次结构中表示为更大父聚类的子聚类。

示例

• OPTICS聚类算法演示

与DBSCAN的比较

OPTICS cluster_optics_dbscan 方法和DBSCAN的结果非常相似，但并非总是完全相同；特别是在外围点和噪声点的标记方面。这部分是因为OPTICS处理的每个密集区域的第一个样本具有较大的可达性值，同时又靠近其区域中的其他点，因此有时会被标记为噪声而不是外围。当相邻点被考虑标记为外围或噪声时，这会影响它们。

请注意，对于任何单个 eps 值，DBSCAN 的运行时间通常比 OPTICS 短；然而，对于在不同 eps 值下重复运行的情况，OPTICS 的单次运行可能需要比 DBSCAN 更少的累积运行时间。同样重要的是要注意，只有当 eps 和 max_eps 接近时，OPTICS 的输出才接近 DBSCAN 的输出。

计算复杂度

空间索引树用于避免计算完整的距离矩阵，并允许在大样本集上高效使用内存。可以通过 metric 关键字提供不同的距离度量。

对于大型数据集，可以通过 HDBSCAN 获得相似（但不完全相同）的结果。HDBSCAN 实现是多线程的，并且比 OPTICS 具有更好的算法运行时复杂度，但代价是内存扩展性较差。对于使用 HDBSCAN 会耗尽系统内存的超大型数据集，OPTICS 将保持 \(n\)（而不是 \(n^2\)）的内存扩展；然而，可能需要调整 max_eps 参数才能在合理的时间内给出解决方案。

参考文献

• “OPTICS: ordering points to identify the clustering structure.” Ankerst, Mihael, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. In ACM Sigmod Record, vol. 28, no. 2, pp. 49-60. ACM, 1999.

2.3.10. BIRCH

Birch 为给定数据构建一个称为聚类特征树（CFT）的树。数据本质上被有损压缩为一组聚类特征节点（CF节点）。CF节点有许多称为聚类特征子簇（CF子簇）的子簇，并且这些位于非终端CF节点中的CF子簇可以拥有CF节点作为子节点。

CF子簇包含聚类所需的必要信息，从而避免了在内存中保存整个输入数据的需要。这些信息包括：

• 子簇中的样本数量。

• 线性求和 - 一个n维向量，包含所有样本的和

• 平方和 - 所有样本的L2范数平方之和。

• 质心 - 避免重复计算线性求和 / n_samples。

• 质心的平方范数。

BIRCH 算法有两个参数，即阈值和分支因子。分支因子限制了节点中子簇的数量，而阈值限制了进入样本与现有子簇之间的距离。

此算法可以被视为一种实例或数据归约方法，因为它将输入数据归约为一组直接从CFT叶子中获取的子簇。这些归约后的数据可以进一步通过输入到全局聚类器中进行处理。这个全局聚类器可以通过 n_clusters 进行设置。如果 n_clusters 设置为None，则直接读取叶子中的子簇；否则，全局聚类步骤会将这些子簇标记为全局簇（标签），并将样本映射到最近子簇的全局标签。

算法描述

• 一个新的样本被插入到CF树的根节点，该根节点是一个CF节点。然后，它与根节点的子簇合并，该子簇在合并后具有最小半径，并受到阈值和分支因子条件的限制。如果子簇有任何子节点，则重复此操作直到到达叶节点。在叶节点中找到最近的子簇后，此子簇和父子簇的属性会递归更新。

• 如果将新样本与最近的子簇合并后得到的子簇半径大于阈值的平方，并且子簇数量大于分支因子，则暂时为该新样本分配空间。选择两个最远的子簇，并根据这些子簇之间的距离将子簇分成两组。

• 如果这个分裂节点有一个父子簇并且有空间容纳一个新的子簇，那么父节点就会被分成两个。如果没有空间，那么这个节点会再次被分成两个，并且这个过程会递归地继续，直到到达根节点。

BIRCH 还是 MiniBatchKMeans？

• BIRCH 在高维数据上的扩展性不是很好。经验法则是，如果 n_features 大于20，通常最好使用 MiniBatchKMeans。

• 如果需要减少数据实例的数量，或者希望获得大量子簇（无论是作为预处理步骤还是其他用途），BIRCH 比 MiniBatchKMeans 更有效。

如何使用 partial_fit？

为了避免全局聚类的计算，建议用户在每次调用 partial_fit 时：

1. 最初将 n_clusters=None。

2. 通过多次调用 partial_fit 训练所有数据。

3. 使用 brc.set_params(n_clusters=n_clusters) 将 n_clusters 设置为所需值。

4. 最后调用 partial_fit，不带任何参数，即 brc.partial_fit()，这将执行全局聚类。

参考文献

• Tian Zhang, Raghu Ramakrishnan, Maron Livny BIRCH: An efficient data clustering method for large databases. https://www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf

• Roberto Perdisci JBirch - BIRCH聚类算法的Java实现 https://code.google.com/archive/p/jbirch

2.3.11. 聚类性能评估

评估聚类算法的性能不像计算错误数量或监督分类算法的精确度和召回率那样简单。特别是，任何评估指标都不应考虑聚类标签的绝对值，而应考虑这种聚类是否定义了与某些真实类别集相似的数据分离，或者是否满足某些假设，例如根据某些相似度指标，属于同一类别的成员比属于不同类别的成员更相似。

2.3.11.1. 兰德指数

已知真实类别分配 labels_true 和我们聚类算法对相同样本的分配 labels_pred，（调整或未调整）兰德指数 是一个衡量两种分配 相似性 的函数，忽略排列。

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.rand_score(labels_true, labels_pred)
0.66

兰德指数不能保证随机标记获得接近0.0的值。调整后的兰德指数 校正了偶然性，并提供了这样的基线。

>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24

与所有聚类指标一样，可以在预测标签中置换0和1，将2重命名为3，并获得相同的分数。

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.rand_score(labels_true, labels_pred)
0.66
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24

此外，rand_score 和 adjusted_rand_score 都具有 对称性：交换参数不会改变分数。因此它们可以用作 共识度量。

>>> metrics.rand_score(labels_pred, labels_true)
0.66
>>> metrics.adjusted_rand_score(labels_pred, labels_true)
0.24

完美标记得分为 1.0

>>> labels_pred = labels_true[:]
>>> metrics.rand_score(labels_true, labels_pred)
1.0
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
1.0

较差的一致性标签（例如，独立标记）得分较低，对于调整后的兰德指数，得分将为负值或接近零。然而，对于未调整的兰德指数，得分虽然较低，但不一定接近零。

>>> labels_true = [0, 0, 0, 0, 0, 0, 1, 1]
>>> labels_pred = [0, 1, 2, 3, 4, 5, 5, 6]
>>> metrics.rand_score(labels_true, labels_pred)
0.39
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
-0.072

优点

• 可解释性：未调整的兰德指数与 labels_pred 和 labels_true 中标签相同或不同的样本对的数量成比例。

• 随机（均匀）标签分配的调整兰德指数得分接近0.0，适用于任何 n_clusters 和 n_samples 值（例如，这对于未调整的兰德指数或V-度量则不适用）。

• 有界范围：较低的值表示不同的标签，相似的聚类具有较高的（调整或未调整）兰德指数，1.0是完美的匹配分数。未调整的兰德指数得分范围是[0, 1]，调整后的兰德指数得分范围是[-0.5, 1]。

• 对聚类结构不做任何假设：(调整或未调整)兰德指数可用于比较各种聚类算法，并可用于比较诸如假设各向同性斑点形状的k-means算法与可以找到“折叠”形状聚类的谱聚类算法的结果。

缺点

• 与惯性不同，（调整或未调整）兰德指数需要知道真实类别，这在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习设置中）。

  然而，（调整或未调整）兰德指数也可以在纯粹无监督的设置中作为共识指数的构建块，用于聚类模型选择（待办）。

• 即使聚类本身显著不同，未调整的兰德指数也通常接近 1.0。这可以理解为将兰德指数解释为聚类产生的元素对标记的准确性：在实践中，通常大多数元素对在预测聚类和真实聚类下都被分配了 不同 的对标签，从而导致高比例的对标签一致，进而导致高分数。

示例

• 聚类性能评估中的偶然性调整：分析数据集大小对随机分配聚类度量值的影响。

数学公式

如果 C 是真实类别分配，K 是聚类，那么我们定义 \(a\) 和 \(b\) 为

• \(a\)，在C中属于同一集合且在K中也属于同一集合的元素对的数量

• \(b\)，在C中属于不同集合且在K中也属于不同集合的元素对的数量

未调整的兰德指数由下式给出

\[\text{RI} = \frac{a + b}{C_2^{n_{samples}}}\]

其中 \(C_2^{n_{samples}}\) 是数据集中可能配对的总数。无论计算是在有序对还是无序对上执行，只要计算一致执行，结果都是相同的。

然而，兰德指数不能保证随机标签分配会得到接近零的值（特别是当簇的数量与样本的数量处于同一数量级时）。

为了抵消这种效应，我们可以通过定义调整后的兰德指数如下来折算随机标记的预期RI \(E[\text{RI}]\)：

\[\text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]}\]

参考文献

• 比较分区 L. Hubert and P. Arabie, Journal of Classification 1985

• Hubert-Arabie调整兰德指数的属性 D. Steinley, Psychological Methods 2004

• 兰德指数维基百科条目

• 给定大小的两次聚类的最小调整兰德指数，2022，J. E. Chacón 和 A. I. Rastrojo

2.3.11.2. 基于互信息的分数

已知真实类别分配 labels_true 和我们聚类算法对相同样本的分配 labels_pred，互信息 是一个衡量两种分配 一致性 的函数，忽略排列。此度量有两种不同的归一化版本可用，即 归一化互信息 (NMI) 和 调整互信息 (AMI)。NMI 在文献中经常使用，而 AMI 是最近提出的，并且 针对偶然性进行了归一化。

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504

可以在预测标签中置换0和1，将2重命名为3，并获得相同的分数。

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504

所有 mutual_info_score、adjusted_mutual_info_score 和 normalized_mutual_info_score 都是对称的：交换参数不会改变分数。因此它们可以用作 共识度量。

>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)  
0.22504

完美标记得分为 1.0

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
1.0

>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)  
1.0

这对于 mutual_info_score 不成立，因此更难判断。

>>> metrics.mutual_info_score(labels_true, labels_pred)  
0.69

不良（例如，独立标记）的分数非正。

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
-0.10526

优点

• 随机（均匀）标签分配的AMI分数接近0.0，适用于任何 n_clusters 和 n_samples 值（例如，这对于原始互信息或V-measure则不适用）。

• 上限为1：接近零的值表示两个标签分配基本上是独立的，而接近1的值表示显著的一致性。此外，AMI恰好为1表示两个标签分配是相同的（有或没有排列）。

缺点

• 与惯性不同，基于MI的度量需要知道真实类别，这在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习设置中）。

  然而，基于MI的度量在纯粹无监督设置中也很有用，作为共识指数的构建块，可用于聚类模型选择。

• NMI和MI未针对偶然性进行调整。

示例

• 聚类性能评估中的偶然性调整：分析数据集大小对随机分配聚类度量值的影响。本示例还包括调整兰德指数。

数学公式

假设有两个标签分配（对相同 N 个对象），\(U\) 和 \(V\)。它们的熵是分区集的不确定性量，定义为

\[H(U) = - \sum_{i=1}^{|U|}P(i)\log(P(i))\]

其中 \(P(i) = |U_i| / N\) 是从 \(U\) 中随机抽取的一个对象落入类别 \(U_i\) 的概率。对于 \(V\) 也类似

\[H(V) = - \sum_{j=1}^{|V|}P'(j)\log(P'(j))\]

其中 \(P'(j) = |V_j| / N\)。 \(U\) 和 \(V\) 之间的互信息（MI）计算如下：

\[\text{MI}(U, V) = \sum_{i=1}^{|U|}\sum_{j=1}^{|V|}P(i, j)\log\left(\frac{P(i,j)}{P(i)P'(j)}\right)\]

其中 \(P(i, j) = |U_i \cap V_j| / N\) 是随机选取的一个对象同时落入类别 \(U_i\) 和 \(V_j\) 的概率。

它也可以用集合基数公式表示为

\[\text{MI}(U, V) = \sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \frac{|U_i \cap V_j|}{N}\log\left(\frac{N|U_i \cap V_j|}{|U_i||V_j|}\right)\]

归一化互信息定义为

\[\text{NMI}(U, V) = \frac{\text{MI}(U, V)}{\text{mean}(H(U), H(V))}\]

互信息的这个值以及归一化变体没有针对偶然性进行调整，并且会随着不同标签（簇）数量的增加而趋于增加，无论标签分配之间实际的“互信息”量如何。

互信息的期望值可以使用以下等式 [VEB2009] 计算。在此等式中，\(a_i = |U_i|\)（\(U_i\) 中的元素数量）和 \(b_j = |V_j|\)（\(V_j\) 中的元素数量）。

\[E[\text{MI}(U,V)]=\sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \sum_{n_{ij}=(a_i+b_j-N)^+ }^{\min(a_i, b_j)} \frac{n_{ij}}{N}\log \left( \frac{ N.n_{ij}}{a_i b_j}\right) \frac{a_i!b_j!(N-a_i)!(N-b_j)!}{N!n_{ij}!(a_i-n_{ij})!(b_j-n_{ij})! (N-a_i-b_j+n_{ij})!}\]

使用期望值，调整互信息可以使用与调整兰德指数相似的形式计算

\[\text{AMI} = \frac{\text{MI} - E[\text{MI}]}{\text{mean}(H(U), H(V)) - E[\text{MI}]}\]

对于归一化互信息和调整互信息，归一化值通常是每个聚类熵的某种 广义 均值。存在各种广义均值，并且没有明确的规则来优先选择哪一种。这个决定很大程度上是基于领域；例如，在社区检测中，算术均值是最常见的。每种归一化方法都提供“定性上相似的行为” [YAT2016]。在我们的实现中，这由 average_method 参数控制。

Vinh et al. (2010) 根据其平均方法命名了 NMI 和 AMI 的变体 [VEB2010]。他们的“sqrt”和“sum”平均值分别是几何平均和算术平均；我们使用这些更广泛的通用名称。

参考文献

• Strehl, Alexander, and Joydeep Ghosh (2002). “Cluster ensembles - a knowledge reuse framework for combining multiple partitions”. Journal of Machine Learning Research 3: 583-617. doi:10.1162/153244303321897735。

• 维基百科关于（归一化）互信息的条目

• 维基百科关于调整互信息的条目

[VEB2009]

Vinh, Epps, and Bailey, (2009). “信息论聚类比较度量”。《第26届年度国际机器学习会议论文集 - ICML ‘09》。doi:10.1145/1553374.1553511。ISBN 9781605585161。

[VEB2010]

Vinh, Epps, and Bailey, (2010). “信息论聚类比较度量：变体、属性、归一化和偶然性校正”。JMLR <https://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf>

[YAT2016]

Yang, Algesheimer, and Tessone, (2016). “人工网络上社区检测算法的比较分析”。Scientific Reports 6: 30750。doi:10.1038/srep30750。

2.3.11.3. 同质性、完备性和V-度量

已知样本的真实类别分配后，可以使用条件熵分析定义一些直观的度量。

特别是Rosenberg和Hirschberg（2007）为任何聚类分配定义了以下两个理想目标：

• 同质性：每个聚类只包含单个类别的成员。

• 完备性：给定类别的所有成员都被分配到同一个聚类。

我们可以将这些概念转化为分数：homogeneity_score 和 completeness_score。两者的下限为0.0，上限为1.0（越高越好）。

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.homogeneity_score(labels_true, labels_pred)
0.66

>>> metrics.completeness_score(labels_true, labels_pred)
0.42

它们的调和平均数称为 V-measure，由 v_measure_score 计算。

>>> metrics.v_measure_score(labels_true, labels_pred)
0.516

该函数的公式如下：

\[v = \frac{(1 + \beta) \times \text{homogeneity} \times \text{completeness}}{(\beta \times \text{homogeneity} + \text{completeness})}\]

beta 默认为 1.0，但如果使用小于 1 的 beta 值，

>>> metrics.v_measure_score(labels_true, labels_pred, beta=0.6)
0.547

同质性将获得更大的权重，而使用大于 1 的值则

>>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8)
0.48

完备性将获得更大的权重。

V-度量实际上等同于上面讨论的互信息（NMI），其中聚合函数是算术平均值 [B2011]。

同质性、完备性和V-度量可以使用 homogeneity_completeness_v_measure 一次性计算，如下所示：

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(0.67, 0.42, 0.52)

以下聚类分配略好，因为它具有同质性但缺乏完备性：

>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(1.0, 0.68, 0.81)

注意

v_measure_score 具有 对称性：它可以用来评估同一数据集上两个独立分配的 一致性。

然而，completeness_score 和 homogeneity_score 则不具备此特性：两者都受以下关系约束：

homogeneity_score(a, b) == completeness_score(b, a)

优点

• 有界分数：0.0是最差的，1.0是完美分数。

• 直观的解释：V-度量较差的聚类可以通过 同质性和完备性 进行定性分析，以更好地了解分配所犯的“类型”错误。

• 对聚类结构不做任何假设：可用于比较各种聚类算法，例如假设各向同性斑点形状的k-means算法与可以找到“折叠”形状聚类的谱聚类算法的结果。

缺点

• 前面介绍的指标 没有根据随机标记进行归一化：这意味着根据样本数量、簇和真实类别的数量，一个完全随机的标记不一定会产生相同的同质性、完备性以及V-度量值。特别是，随机标记不会产生零分数，尤其当簇的数量很大时。

  当样本数量超过一千且簇数量小于10时，可以安全地忽略此问题。对于较小的样本数量或较多的簇，使用调整后的指数（如调整兰德指数（ARI））更安全。

• 这些指标 需要知道真实类别，这在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习设置中）。

示例

• 聚类性能评估中的偶然性调整：分析数据集大小对随机分配聚类度量值的影响。

数学公式

同质性和完备性分数正式由下式给出

\[h = 1 - \frac{H(C|K)}{H(C)}\]

\[c = 1 - \frac{H(K|C)}{H(K)}\]

其中 \(H(C|K)\) 是 给定聚类分配的类别的条件熵，其表达式为

\[H(C|K) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{n_{c,k}}{n} \cdot \log\left(\frac{n_{c,k}}{n_k}\right)\]

而 \(H(C)\) 是 类别的熵，其表达式为

\[H(C) = - \sum_{c=1}^{|C|} \frac{n_c}{n} \cdot \log\left(\frac{n_c}{n}\right)\]

其中 \(n\) 是样本总数，\(n_c\) 和 \(n_k\) 分别是属于类别 \(c\) 和聚类 \(k\) 的样本数，最后 \(n_{c,k}\) 是从类别 \(c\) 分配到聚类 \(k\) 的样本数。

给定类别的聚类条件熵 \(H(K|C)\) 和 聚类熵 \(H(K)\) 以对称方式定义。

Rosenberg 和 Hirschberg 进一步将 V-度量 定义为 同质性与完备性的调和平均：

\[v = 2 \cdot \frac{h \cdot c}{h + c}\]

参考文献

• V-Measure: 基于条件熵的外部聚类评估度量 Andrew Rosenberg and Julia Hirschberg, 2007

[B2011]

社交媒体中事件的识别与特征化，Hila Becker，博士论文。

2.3.11.4. Fowlkes-Mallows 分数

最初的Fowlkes-Mallows指数（FMI）旨在衡量两个聚类结果之间的相似性，这本质上是一种无监督比较。Fowlkes-Mallows指数的监督适应（如 sklearn.metrics.fowlkes_mallows_score 中实现）可以在已知样本真实类别分配时使用。FMI定义为成对精确度和召回率的几何平均值。

\[\text{FMI} = \frac{\text{TP}}{\sqrt{(\text{TP} + \text{FP}) (\text{TP} + \text{FN})}}\]

在上述公式中：

• TP (真阳性)：在真实标签和预测标签中都聚在一起的点对数量。

• FP (假阳性)：在预测标签中聚在一起但在真实标签中不聚在一起的点对数量。

• FN (假阴性)：在真实标签中聚在一起但在预测标签中不聚在一起的点对数量。

得分范围从0到1。高值表示两个聚类之间有很好的相似性。

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140

可以在预测标签中置换0和1，将2重命名为3，并获得相同的分数。

>>> labels_pred = [1, 1, 0, 0, 3, 3]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140

完美标记得分为 1.0

>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
1.0

不良（例如，独立标记）的分数为零。

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.0

优点

• 随机（均匀）标签分配的FMI分数接近0.0，适用于任何 n_clusters 和 n_samples 值（例如，这对于原始互信息或V-度量则不适用）。

• 上限为1：接近零的值表示两个标签分配基本独立，而接近1的值表示显著的一致性。此外，恰好为0的值表示 完全 独立的标签分配，而恰好为1的FMI表示两个标签分配相同（有或没有排列）。

• 对聚类结构不做任何假设：可用于比较各种聚类算法，例如假设各向同性斑点形状的k-means算法与可以找到“折叠”形状聚类的谱聚类算法的结果。

缺点

• 与惯性不同，基于FMI的度量需要知道真实类别，这在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习设置中）。

参考文献

• E. B. Fowkles and C. L. Mallows, 1983. “比较两个层次聚类的方法”。美国统计协会杂志。https://www.tandfonline.com/doi/abs/10.1080/01621459.1983.10478008

• Fowlkes-Mallows指数的维基百科条目

2.3.11.5. 轮廓系数

如果不知道真实标签，则必须使用模型本身进行评估。轮廓系数（sklearn.metrics.silhouette_score）就是这种评估的一个例子，其中较高的轮廓系数得分表示模型具有更好定义的聚类。轮廓系数针对每个样本定义，由两个分数组成：

• a：样本与同一类别中所有其他点之间的平均距离。

• b：样本与 下一个最近聚类 中所有其他点之间的平均距离。

单个样本的轮廓系数 s 表达式为

\[s = \frac{b - a}{max(a, b)}\]

样本集的轮廓系数为每个样本轮廓系数的平均值。

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

在常规使用中，轮廓系数应用于聚类分析的结果。

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
0.55

优点

• 该分数的范围在-1（不正确聚类）到+1（高度密集聚类）之间。分数接近零表示聚类重叠。

• 当簇密集且分离良好时，分数较高，这与簇的标准概念相关。

缺点

• 对于凸形聚类，轮廓系数通常高于其他聚类概念，例如通过DBSCAN获得的基于密度的聚类。

示例

• 使用KMeans聚类的轮廓分析选择聚类数量：在此示例中，轮廓分析用于选择n_clusters的最佳值。

参考文献

• Peter J. Rousseeuw (1987). “轮廓：聚类分析解释和验证的图形辅助工具”。Computational and Applied Mathematics 20: 53-65。

2.3.11.6. Calinski-Harabasz 指数

如果真实标签未知，则可以使用 Calinski-Harabasz 指数（sklearn.metrics.calinski_harabasz_score）——也称为方差比准则——来评估模型，其中较高的 Calinski-Harabasz 分数表示模型具有更好定义的簇。

该指数是所有簇的簇间离散度之和与簇内离散度之和的比率（其中离散度定义为距离平方和）。

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

在常规使用中，Calinski-Harabasz 指数应用于聚类分析的结果。

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabasz_score(X, labels)
561.59

优点

• 当簇密集且分离良好时，分数较高，这与簇的标准概念相关。

• 该分数计算速度快。

缺点

• 对于凸形聚类，Calinski-Harabasz指数通常高于其他聚类概念，例如通过DBSCAN获得的基于密度的聚类。

数学公式

对于一个大小为 \(n_E\) 并被聚类为 \(k\) 个簇的数据集 \(E\)，Calinski-Harabasz 分数 \(s\) 定义为簇间离散度均值与簇内离散度之比：

\[s = \frac{\mathrm{tr}(B_k)}{\mathrm{tr}(W_k)} \times \frac{n_E - k}{k - 1}\]

其中 \(\mathrm{tr}(B_k)\) 是组间离散度矩阵的迹，\(\mathrm{tr}(W_k)\) 是簇内离散度矩阵的迹，定义为：

\[W_k = \sum_{q=1}^k \sum_{x \in C_q} (x - c_q) (x - c_q)^T\]

\[B_k = \sum_{q=1}^k n_q (c_q - c_E) (c_q - c_E)^T\]

其中 \(C_q\) 是聚类 \(q\) 中的点集，\(c_q\) 是聚类 \(q\) 的中心，\(c_E\) 是 \(E\) 的中心，\(n_q\) 是聚类 \(q\) 中的点数。

参考文献

• Caliński, T., & Harabasz, J. (1974). “一种用于聚类分析的枝晶方法”。《统计通讯—理论与方法》3: 1-27。doi:10.1080/03610927408827101。

2.3.11.7. Davies-Bouldin 指数

如果真实标签未知，则可以使用 Davies-Bouldin 指数（sklearn.metrics.davies_bouldin_score）来评估模型，其中较低的 Davies-Bouldin 指数表示模型具有更好的簇间分离。

该指数表示簇之间的平均“相似性”，其中相似性是一种衡量簇间距离与簇本身大小的度量。

零是最低可能分数。值越接近零表示分区越好。

在常规使用中，Davies-Bouldin 指数应用于聚类分析的结果，如下所示：

>>> from sklearn import datasets
>>> iris = datasets.load_iris()
>>> X = iris.data
>>> from sklearn.cluster import KMeans
>>> from sklearn.metrics import davies_bouldin_score
>>> kmeans = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans.labels_
>>> davies_bouldin_score(X, labels)
0.666

优点

• Davies-Bouldin的计算比轮廓系数的计算更简单。

• 该指数完全基于数据集固有的量和特征，因为其计算仅使用点间距离。

缺点

• 对于凸形聚类，Davies-Bouldin指数通常高于其他聚类概念，例如通过DBSCAN获得的基于密度的聚类。

• 质心距离的使用将距离度量限制在欧几里德空间。

数学公式

该指数被定义为每个簇 \(C_i\)（\(i=1, ..., k\)）与其最相似的簇 \(C_j\) 之间的平均相似度。在此指数的背景下，相似度定义为一个衡量 \(R_{ij}\) 的度量，它权衡：

• \(s_i\)，簇 \(i\) 中每个点与该簇质心之间的平均距离——也称为簇直径。

• \(d_{ij}\)，簇质心 \(i\) 和 \(j\) 之间的距离。

构造 \(R_{ij}\) 使其非负且对称的简单选择是

\[R_{ij} = \frac{s_i + s_j}{d_{ij}}\]

Davies-Bouldin指数定义为

\[DB = \frac{1}{k} \sum_{i=1}^k \max_{i \neq j} R_{ij}\]

参考文献

• Davies, David L.; Bouldin, Donald W. (1979). “一个聚类分离度量” IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224-227。

• Halkidi, Maria; Batistakis, Yannis; Vazirgiannis, Michalis (2001). “关于聚类验证技术” Journal of Intelligent Information Systems, 17(2-3), 107-145。

• Davies-Bouldin指数的维基百科条目.

2.3.11.8. 列联矩阵

列联矩阵（sklearn.metrics.cluster.contingency_matrix）报告每个真实/预测聚类对的交集基数。列联矩阵为所有聚类指标提供了足够的统计量，其中样本是独立同分布的，并且不需要考虑某些实例未被聚类的情况。

这是一个例子：

>>> from sklearn.metrics.cluster import contingency_matrix
>>> x = ["a", "a", "a", "b", "b", "b"]
>>> y = [0, 0, 1, 1, 2, 2]
>>> contingency_matrix(x, y)
array([[2, 1, 0],
       [0, 1, 2]])

输出数组的第一行表示有三个样本，它们的真实簇是“a”。其中，两个在预测簇0中，一个在预测簇1中，没有在预测簇2中。第二行表示有三个样本，它们的真实簇是“b”。其中，没有在预测簇0中，一个在预测簇1中，两个在预测簇2中。

用于分类的混淆矩阵是一个方阵列联矩阵，其中行和列的顺序对应于一个类别列表。

优点

• 允许检查每个真实簇在预测簇中的分布，反之亦然。

• 计算出的列联表通常用于计算两个聚类之间的相似度统计量（如本文档中列出的其他统计量）。

缺点

• 列联矩阵在聚类数量较少时易于解释，但在聚类数量较大时则变得非常难以解释。

• 它没有提供任何单一指标作为聚类优化的目标。

参考文献

• 列联矩阵的维基百科条目

2.3.11.9. 配对混淆矩阵

配对混淆矩阵 (sklearn.metrics.cluster.pair_confusion_matrix) 是一个 2x2 的相似度矩阵

\[\begin{split}C = \left[\begin{matrix} C_{00} & C_{01} \\ C_{10} & C_{11} \end{matrix}\right]\end{split}\]

它是在两种聚类结果之间计算的，通过考虑所有样本对，并统计在真实聚类和预测聚类中被分配到相同或不同簇的样本对的数量。

它包含以下条目

\(C_{00}\) : 两个聚类结果都将样本对未聚在一起的对数

\(C_{10}\) : 真实标签聚类将样本对聚在一起，但另一个聚类结果未将样本对聚在一起的对数

\(C_{01}\) : 真实标签聚类未将样本对聚在一起，但另一个聚类结果将样本对聚在一起的对数

\(C_{11}\) : 两个聚类结果都将样本对聚在一起的对数

如果将聚在一起的样本对视为正对，那么就像二分类一样，真反例计数为 \(C_{00}\)，假反例为 \(C_{10}\)，真正例为 \(C_{11}\)，假正例为 \(C_{01}\)。

完美匹配的标签分配，无论实际标签值如何，对角线上的所有条目都非零。

>>> from sklearn.metrics.cluster import pair_confusion_matrix
>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1])
array([[8, 0],
       [0, 4]])

>>> pair_confusion_matrix([0, 0, 1, 1], [1, 1, 0, 0])
array([[8, 0],
       [0, 4]])

将所有类别成员分配到相同簇的标签分配是完整的，但可能不总是纯净的，因此会受到惩罚，并具有一些非对角线上的非零条目。

>>> pair_confusion_matrix([0, 0, 1, 2], [0, 0, 1, 1])
array([[8, 2],
       [0, 2]])

该矩阵不是对称的

>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2])
array([[8, 0],
       [2, 2]])

如果类别成员完全分散在不同的簇中，则分配是完全不完整的，因此矩阵的所有对角线条目都为零。

>>> pair_confusion_matrix([0, 0, 0, 0], [0, 1, 2, 3])
array([[ 0,  0],
       [12,  0]])

参考文献

• “Comparing Partitions” L. Hubert 和 P. Arabie, Journal of Classification 1985