2.3. 聚类#

聚类 未标记数据的操作可以通过模块 sklearn.cluster 进行。

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

2.3.1. 聚类方法概述#

../_images/sphx_glr_plot_cluster_comparison_001.png

scikit-learn 中聚类算法的比较#

方法名称

参数

可扩展性

用例

几何形状（使用的度量）

K-Means

聚类数量

非常大的 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-Means

聚类数量

非常大的 n_samples，中等 n_clusters

通用，均匀的聚类大小，平面几何形状，没有空聚类，归纳式，层次式

点之间的距离

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

高斯混合模型（用于聚类）在专门针对混合模型的 文档的另一章 中进行了描述。KMeans 可以被视为具有相等协方差的每个分量的高斯混合模型的特例。

转导式 聚类方法（与 归纳式 聚类方法相反）并非旨在应用于新的、看不见的数据。

2.3.2. K-Means#

KMeans 算法通过尝试将样本分成 n 个方差相等的组来对数据进行聚类，从而最小化称为惯性或簇内平方和（见下文）的标准。该算法要求指定聚类数量。它可以很好地扩展到大量样本，并且已在许多不同领域的广泛应用领域中使用。

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

K-Means 算法旨在选择最小化惯性或簇内平方和标准的质心

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

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

  • 惯性假设聚类是凸的和各向同性的，但情况并非总是如此。它对细长的聚类或形状不规则的流形响应不佳。

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

../_images/sphx_glr_plot_kmeans_assumptions_002.png

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

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

../_images/sphx_glr_plot_kmeans_digits_001.png

K-Means 等效于具有较小、全等、对角协方差矩阵的期望最大化算法。

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

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

K-Means++ 也可以独立调用以选择其他聚类算法的种子，有关详细信息和示例用法，请参阅 sklearn.cluster.kmeans_plusplus。

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

K-Means 可用于矢量量化。这是使用经过训练的 KMeans 模型的 transform 方法实现的。有关对图像执行矢量量化的示例，请参阅 使用 K-Means 进行颜色量化。

示例

2.3.2.1. 低级并行#

KMeans 通过 Cython 利用基于 OpenMP 的并行性。小块数据（256 个样本）并行处理，这也有助于降低内存占用。有关如何控制线程数量的更多详细信息，请参阅我们的 并行性 说明。

示例

参考文献#

2.3.2.2. Mini Batch K-Means#

MiniBatchKMeans 是 KMeans 算法的一种变体，它使用小批量来减少计算时间，同时仍然尝试优化相同的目标函数。小批量是输入数据的子集，在每次训练迭代中随机采样。这些小批量大大减少了收敛到局部解所需的计算量。与其他减少 k-means 收敛时间的算法相比，小批量 k-means 生成的结果通常只比标准算法略差。

该算法在两个主要步骤之间迭代，类似于普通 k-means。在第一步中，从数据集中随机抽取 \(b\) 个样本，形成一个小批量。然后将它们分配给最近的质心。在第二步中，更新质心。与 k-means 不同的是，这是在每个样本的基础上完成的。对于小批量中的每个样本，分配的质心通过对样本和之前分配给该质心的所有样本进行流平均来更新。这具有随着时间的推移降低质心变化率的效果。这些步骤一直执行到收敛或达到预定的迭代次数。

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

../_images/sphx_glr_plot_mini_batch_kmeans_001.png

示例

参考文献#

2.3.3. 亲和传播#

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

../_images/sphx_glr_plot_affinity_propagation_001.png

亲和传播很有趣，因为它根据提供的数据选择聚类的数量。为此，两个重要的参数是偏好，它控制使用多少个示例，以及阻尼因子，它阻尼责任和可用性消息以避免在更新这些消息时出现数值振荡。

亲和传播的主要缺点是它的复杂性。该算法的时间复杂度为 \(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\) 表示迭代次数。

示例

2.3.4. 均值漂移#

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

数学细节#

质心候选者的位置使用称为爬山法的技术进行迭代调整，该技术找到估计概率密度的局部最大值。给定迭代 \(t\) 的质心候选者 \(x\)，候选者根据以下等式更新

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

其中 \(m\) 是为每个质心计算的均值漂移向量，该向量指向点密度最大增长的区域。为了计算 \(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 函数进行估计，如果未设置带宽，则会调用该函数。

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

对新样本进行标记是通过为给定样本找到最近的质心来完成的。

../_images/sphx_glr_plot_mean_shift_001.png

示例

参考文献#

2.3.5. 谱聚类#

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

当前版本的 SpectralClustering 需要预先指定聚类数量。它在少量聚类的情况下效果很好，但不建议用于大量聚类。

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

noisy_img segmented_img

警告

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

请注意，如果您的相似性矩阵的值分布不佳，例如具有负值或距离矩阵而不是相似性，则谱问题将是奇异的，问题无法解决。在这种情况下，建议对矩阵的条目应用转换。例如，在有符号距离矩阵的情况下，通常应用热核

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"

coin_kmeans

coin_discretize

coin_cluster_qr
参考文献#

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)
参考文献#

2.3.6. 层次聚类#

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

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

  • Ward 最小化所有聚类内平方差之和。它是一种方差最小化方法，从这个意义上说，它类似于 k 均值目标函数，但使用的是凝聚层次方法。

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

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

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

AgglomerativeClustering 当与连接矩阵一起使用时，也可以扩展到大量样本，但在没有添加样本之间的连接约束时，计算量很大：它在每一步都考虑所有可能的合并。

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

AgglomerativeClustering 支持 Ward、single、average 和 complete 连接策略。

../_images/sphx_glr_plot_linkage_comparison_001.png

凝聚层次聚类具有“富者愈富”的行为，导致聚类大小不均匀。在这方面，single 连接是最糟糕的策略，而 Ward 给出了最规则的大小。但是，亲和度（或聚类中使用的距离）不能随 Ward 变化，因此对于非欧几里得度量，average 连接是一个很好的替代方案。single 连接虽然对噪声数据不鲁棒，但可以非常有效地计算，因此对于提供更大数据集的层次聚类很有用。single 连接在非球形数据上也能表现良好。

示例

2.3.6.2. 聚类层次的可视化#

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

../_images/sphx_glr_plot_agglomerative_dendrogram_001.png

示例

2.3.6.3. 添加连接约束#

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

unstructured structured

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

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

警告

single、average 和 complete 连接的连接约束

连接约束和 single、complete 或 average 连接可以增强凝聚层次聚类的“富者愈富”方面，尤其是在使用 sklearn.neighbors.kneighbors_graph 构建时。在聚类数量较少的情况下，它们往往会给出几个宏观占据的聚类和几乎空的聚类。（参见 有结构和无结构的凝聚层次聚类 中的讨论）。single 连接是关于此问题的最脆弱的连接选项。

../_images/sphx_glr_plot_agglomerative_clustering_001.png ../_images/sphx_glr_plot_agglomerative_clustering_002.png ../_images/sphx_glr_plot_agglomerative_clustering_003.png ../_images/sphx_glr_plot_agglomerative_clustering_004.png

示例

2.3.6.4. 改变度量#

single、average 和 complete 连接可以与各种距离（或亲和度）一起使用，特别是欧几里得距离（l2）、曼哈顿距离（或 Cityblock，或 l1）、余弦距离或任何预先计算的亲和度矩阵。

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

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

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

../_images/sphx_glr_plot_agglomerative_clustering_metrics_005.png ../_images/sphx_glr_plot_agglomerative_clustering_metrics_006.png ../_images/sphx_glr_plot_agglomerative_clustering_metrics_007.png

示例

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 均值的聚类是有序的，并创建了一个相当明显的层次结构。

参考文献#

2.3.7. DBSCAN#

DBSCAN 算法将聚类视为由低密度区域分隔的高密度区域。由于这种相当通用的观点，DBSCAN 找到的聚类可以是任何形状，而 k 均值算法则假设聚类是凸形的。DBSCAN 的核心概念是 *核心样本*，即位于高密度区域的样本。因此，一个聚类是一组核心样本，每个样本彼此靠近（通过某种距离度量），以及一组非核心样本，这些样本靠近核心样本（但本身不是核心样本）。算法有两个参数，min_samples 和 eps，它们正式定义了我们所说的 *密集* 的含义。较高的 min_samples 或较低的 eps 表明形成聚类所需的密度更高。

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

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

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

在下图中，颜色表示聚类成员资格，大圆圈表示算法找到的核心样本。小圆圈是非核心样本，它们仍然是聚类的一部分。此外，离群值由下面的黑点表示。

dbscan_results

示例

实现#

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

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

大样本量时的内存消耗#

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

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

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

  • 可以压缩数据集，方法是删除数据中存在的精确重复项，或者使用 BIRCH。然后，您只需要为大量点提供相对较少的代表。然后，您可以在拟合 DBSCAN 时提供 sample_weight。

参考文献#

2.3.8. HDBSCAN#

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

注意

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

示例

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_*).\]

接下来，它定义了 \(d_m(x_p, x_q)\)，即两点 \(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)\)。我们可以构建此图的子集，表示为 \(G_{ms,\varepsilon}\)，方法是删除任何值大于 \(\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 能够以层次方式获得 DBSCAN* 为固定选择的 min_samples 可实现的所有可能分区。实际上，这允许 HDBSCAN 在多个密度上执行聚类，因此它不再需要将 \(\varepsilon\) 作为超参数给出。相反，它仅依赖于 min_samples 的选择，这往往是一个更健壮的超参数。

hdbscan_ground_truth

hdbscan_results

HDBSCAN 可以使用额外的超参数 min_cluster_size 进行平滑，该超参数指定在层次聚类期间，样本数少于 minimum_cluster_size 的分量被视为噪声。在实践中，可以设置 minimum_cluster_size = min_samples 来耦合参数并简化超参数空间。

参考文献

[CM2013]

Campello, R.J.G.B., Moulavi, D., Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. In: Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2013. Lecture Notes in Computer Science(), vol 7819. Springer, Berlin, Heidelberg. 基于层次密度估计的密度聚类

[LJ2017]

L. McInnes 和 J. Healy，(2017)。加速层次密度聚类。在：IEEE 数据挖掘研讨会国际会议 (ICDMW)，2017 年，第 33-42 页。 加速层次密度聚类

2.3.9. OPTICS#

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

optics_results

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

示例

与 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：排序点以识别聚类结构。” Ankerst，Mihael，Markus M. Breunig，Hans-Peter Kriegel 和 Jörg Sander。在 ACM Sigmod Record，第 28 卷，第 2 期，第 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 更有用。

../_images/sphx_glr_plot_birch_vs_minibatchkmeans_001.png
如何使用 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()，它执行全局聚类。

参考文献#

2.3.11. 聚类性能评估#

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

2.3.11.1. Rand 指数#

假设已知地面真实类分配 labels_true 和我们的聚类算法对相同样本的分配 labels_pred，（调整或未调整的）Rand 指数是一个函数，它测量两个分配的相似性，忽略排列。

>>> 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...

Rand 指数不能保证对随机标记获得接近 0.0 的值。调整后的 Rand 指数校正了偶然性，并将给出这样的基线。

>>> 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

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

>>> 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.07...

示例

数学公式#

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

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

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

未调整的 Rand 指数由以下公式给出：

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

其中 \(C_2^{n_{samples}}\) 是数据集中所有可能的对的数量。只要计算过程一致，计算是有序对还是无序对并不重要。

然而，Rand 指数不能保证随机标签分配会得到接近零的值（尤其是当聚类数量与样本数量处于同一数量级时）。

为了抵消这种影响，我们可以通过定义调整后的 Rand 指数来折扣随机标签分配的预期 RI \(E[\text{RI}]\)，如下所示：

\[\text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]}\]
参考文献#

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...

示例

数学公式#

假设两个标签分配（相同 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})!}\]

使用期望值，调整后的互信息可以使用与调整后的 Rand 指数类似的形式计算

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

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

Vinh 等人 (2010) 根据它们的平均方法命名了 NMI 和 AMI 的变体 [VEB2010]。它们的“sqrt”和“sum”平均值分别是几何平均值和算术平均值；我们更广泛地使用这些更常见的名称。

参考文献

[VEB2009]

Vinh, Epps 和 Bailey, (2009)。“用于聚类比较的信息论度量”。第 26 届年度国际机器学习大会论文集 - ICML '09。 doi:10.1145/1553374.1553511。ISBN 9781605585161。

[VEB2010]

Vinh, Epps 和 Bailey, (2010)。“用于聚类比较的信息论度量：变体、性质、归一化和机会校正”。JMRL <https://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf>

[YAT2016]

Yang, Algesheimer 和 Tessone, (2016)。“社区检测算法在人工网络上的比较分析”。科学报告 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 度量，由 v_measure_score 计算

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

此函数的公式如下

\[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.54...

将更多权重分配给同质性，而使用大于 1 的值

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

将更多权重分配给完整性。

V 度量实际上等同于上面讨论的互信息 (NMI)，聚合函数是算术平均值 [B2011].

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

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(0.66..., 0.42..., 0.51...)

以下聚类分配略好，因为它同质但并不完整

>>> 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)

示例

数学公式#

同质性和完整性分数由以下公式给出

\[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}\) 是分配到聚类 \(k\) 的类别 \(c\) 的样本数量。

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

Rosenberg 和 Hirschberg 进一步将V 度量定义为同质性和完整性的调和平均值

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

参考文献

[B2011]

社交媒体事件的识别和特征分析，Hila Becker，博士论文。

2.3.11.4. Fowlkes-Mallows 分数#

Fowlkes-Mallows 指数（sklearn.metrics.fowlkes_mallows_score）可以在已知样本的真实类别分配的情况下使用。Fowlkes-Mallows 分数 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
参考文献#

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...

示例

参考文献#

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...
数学公式#

对于大小为 \(n_E\) 的数据集合 \(E\)，它已被聚类为 \(k\) 个集群，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\) 中的点数。

参考文献#

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...
数学公式#

该指标定义为每个聚类 \(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}\]
参考文献#

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]])
参考文献#
本页内容
显示源代码