.. _clustering: ========== 聚类 ========== `聚类 `__ 是对未标记数据进行分组的一种方法，可以通过 :mod:`sklearn.cluster` 模块实现。 每种聚类算法都有两种变体：一种是类，实现了 ``fit`` 方法，用于在训练数据上学习聚类；另一种是函数，给定训练数据，返回一个整数标签数组，对应不同的聚类。对于类，训练数据上的标签可以在 ``labels_`` 属性中找到。 .. currentmodule:: sklearn.cluster .. topic:: 输入数据 需要注意的是，该模块中实现的算法可以接受不同类型的矩阵作为输入。所有方法都接受标准数据矩阵，形状为 ``(n_samples, n_features)`` 。这些可以从 :mod:`sklearn.feature_extraction` 模块中的类获得。对于 :class:`AffinityPropagation` 、:class:`SpectralClustering` 和 :class:`DBSCAN` ，还可以输入形状为 ``(n_samples, n_samples)`` 的相似度矩阵。这些可以从 :mod:`sklearn.metrics.pairwise` 模块中的函数获得。 聚类方法概览 =============================== .. figure:: ../auto_examples/cluster/images/sphx_glr_plot_cluster_comparison_001.png :target: ../auto_examples/cluster/plot_cluster_comparison.html :align: center :scale: 50 scikit-learn 中聚类算法的比较 .. list-table:: :header-rows: 1 :widths: 14 15 19 25 20 * - 方法名称 - 参数 - 可扩展性 - 使用场景 - 几何形状（使用的度量） * - :ref:`K-Means ` - 聚类数量 - 非常大的 ``n_samples`` ，中等 ``n_clusters`` 使用 :ref:`MiniBatch 代码 ` - 通用目的，均匀聚类大小，平面几何形状， 聚类数量不多，归纳型 - 点之间的距离 * - :ref:`Affinity propagation ` * - :ref:`均值漂移 ` - 带宽 - 不随 ``n_samples`` 扩展 - 多聚类，不均匀聚类大小，非平面几何，归纳式 - 点之间的距离 * - :ref:`谱聚类 ` - 聚类数量 - 中等 ``n_samples`` ，小 ``n_clusters`` - 少量聚类，均匀聚类大小，非平面几何，直推式 - 图距离（例如最近邻图） * - :ref:`Ward 层次聚类 ` - 聚类数量或距离阈值 - 大 ``n_samples`` 和大 ``n_clusters`` - 多聚类，可能存在连接约束，直推式 - 点之间的距离 * - :ref:`凝聚聚类 ` - 聚类数量或距离阈值，连接类型，距离 - 大 ``n_samples`` 和大 ``n_clusters`` - 多聚类，可能存在连接约束，非欧几里得距离，直推式 - 任意成对距离 * - :ref:`DBSCAN ` - 邻域大小 - 非常大 ``n_samples`` ，中等 ``n_clusters`` - 非平面几何，不均匀聚类大小，离群点移除，直推式 - 最近点之间的距离 * - :ref:`HDBSCAN ` - 最小聚类成员数，最小点邻居数 - 大 ``n_samples`` ，中等 ``n_clusters`` - 非平面几何，不均匀聚类大小，离群点移除，直推式，层次化，可变聚类密度 - 最近点之间的距离 * - :ref:`OPTICS ` - 最小聚类成员数 - 非常大 ``n_samples`` ，大 ``n_clusters`` - 非平面几何，不均匀聚类大小，可变聚类密度 异常值移除, 直推式 - 点之间的距离 * - :ref:`高斯混合模型 ` - 多个 - 不可扩展 - 平面几何, 适用于密度估计, 归纳式 - 到中心的马氏距离 * - :ref:`BIRCH ` - 分支因子, 阈值, 可选的全局聚类器 - 大型 ``n_clusters`` 和 ``n_samples`` - 大型数据集, 异常值移除, 数据降维, 归纳式 - 点之间的欧几里得距离 * - :ref:`二分K均值 ` - 聚类数量 - 非常大的 ``n_samples`` , 中等 ``n_clusters`` - 通用目的, 均匀聚类大小, 平面几何, 无空聚类, 归纳式, 层次化 - 点之间的距离 非平面几何聚类在聚类具有特定形状（即非平面流形）且标准欧几里得距离不是正确度量时非常有用。这种情况出现在上图中的前两行。 高斯混合模型，适用于聚类，在专门介绍混合模型的文档章节中进行了描述：:ref:`另一章节 ` 。K均值可以看作是每个分量具有相等协方差的高斯混合模型的特例。 :term:`直推式 ` 聚类方法（与 :term:`归纳式` 聚类方法相对）不是为应用于新数据而设计的。 .. _k_means: K均值 ===== :class:`K均值` 算法通过尝试将样本分离成 n 个具有相等方差的组来对数据进行聚类，最小化一个称为 *惯性* 或 组内平方和（见下文）的标准。该算法需要指定聚类数量。它在大样本数量上具有良好的扩展性，并在许多不同领域的广泛应用中得到了应用。 k均值算法将一组 :math:`N` 个样本 :math:`X` 分成 :math:`K` 个不相交的聚类 :math:`C` ，每个聚类由均值 :math:`\mu_j` 描述。 集群中样本的。这些均值通常被称为集群的“质心”；需要注意的是，它们通常不是来自 :math:`X` 的点，尽管它们存在于同一空间中。 K-means 算法旨在选择使 **惯性** 或 **簇内平方和准则** 最小的质心： .. math:: \sum_{i=0}^{n}\min_{\mu_j \in C}(||x_i - \mu_j||^2) 惯性可以被认为是衡量集群内部一致性的一种度量。它存在一些缺点： - 惯性假设集群是凸的和各向同性的，但这并不总是成立。它对细长集群或具有不规则形状的流形反应不佳。 - 惯性不是一个归一化度量：我们只知道较低的值更好，零是最优的。但在非常高维的空间中，欧几里得距离往往会变得膨胀（这是所谓的“维度灾难”的一个实例）。在运行 k-means 聚类之前，先使用如 :ref:`PCA` 这样的降维算法可以缓解这个问题并加快计算速度。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_kmeans_assumptions_002.png :target: ../auto_examples/cluster/plot_kmeans_assumptions.html :align: center :scale: 50 有关上述问题的更详细描述以及如何解决它们，请参阅示例 :ref:`sphx_glr_auto_examples_cluster_plot_kmeans_assumptions.py` 和 :ref:`sphx_glr_auto_examples_cluster_plot_kmeans_silhouette_analysis.py` 。 K-means 通常被称为 Lloyd's 算法。简单来说，该算法有三个步骤。第一步选择初始质心，最基本的方法是从数据集 :math:`X` 中选择 :math:`k` 个样本。初始化后，K-means 包括在这两个其他步骤之间循环。第一步将每个样本分配到其最近的质心。第二步通过取所有样本的均值来创建新的质心。 分配给每个先前质心的样本。计算旧质心和新质心之间的差异，并且算法重复这些最后两个步骤，直到该值小于某个阈值。换句话说，它重复直到质心不再显著移动。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_kmeans_digits_001.png :target: ../auto_examples/cluster/plot_kmeans_digits.html :align: right :scale: 35 K-means 等价于具有一个小型、全相等、对角协方差矩阵的期望最大化算法。 该算法也可以通过 `Voronoi 图 `_ 的概念来理解。首先使用当前质心计算点的 Voronoi 图。Voronoi 图中的每个段成为一个单独的簇。其次，质心更新为每个段的均值。然后算法重复这一点，直到满足停止准则。通常，算法在迭代之间的目标函数相对减少小于给定的容差值时停止。但在这种实现中，迭代在质心移动小于容差时停止。 给定足够的时间，K-means 总是会收敛，但这可能是局部最小值。这高度依赖于质心的初始化。因此，计算通常会多次进行，使用不同的质心初始化。帮助解决这个问题的一种方法是 k-means++ 初始化方案，这在 scikit-learn 中已经实现（使用 ``init='k-means++'`` 参数）。这将质心初始化为（通常）彼此远离，导致可能比随机初始化更好的结果，如参考文献所示。有关比较不同初始化方案的详细示例，请参阅 :ref:`sphx_glr_auto_examples_cluster_plot_kmeans_digits.py` 。 K-means++ 也可以独立调用来为其他聚类算法选择种子，详情和示例用法请参见 :func:`sklearn.cluster.kmeans_plusplus` 。 该算法支持样本权重，可以通过参数 ``sample_weight`` 给出。这允许在计算聚类中心和惯性值时为某些样本赋予更多权重。例如，为样本分配权重 2 相当于在数据集 :math:`X` 中添加该样本的一个副本。 K-means 可用于向量量化。这是通过 :class:`KMeans` 训练模型的 ``transform`` 方法实现的。有关在图像上执行向量量化的示例，请参阅 :ref:`sphx_glr_auto_examples_cluster_plot_color_quantization.py` 。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_cluster_iris.py` : 使用鸢尾花数据集的 :class:`KMeans` 示例用法 * :ref:`sphx_glr_auto_examples_text_plot_document_clustering.py` : 基于稀疏数据的文档聚类，使用 :class:`KMeans` 和 :class:`MiniBatchKMeans` 低级并行化 --------------------- :class:`KMeans` 通过 Cython 受益于基于 OpenMP 的并行化。小数据块（256 个样本）并行处理，此外还产生低内存占用。有关如何控制线程数量的更多详细信息，请参阅我们的 :ref:`parallelism` 笔记。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_kmeans_assumptions.py` : 展示 k-means 何时直观表现良好，何时表现不佳 * :ref:`sphx_glr_auto_examples_cluster_plot_kmeans_digits.py` : 聚类手写数字 .. dropdown:: 参考文献 * `"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) .. _mini_batch_kmeans: Mini Batch K-Means ------------------ :class:`MiniBatchKMeans` 是 :class:`KMeans` 算法的一个变体，它使用小批量来减少计算时间，同时仍然尝试优化相同的 objective function。小批量是每次训练迭代中随机采样的输入数据的子集。这些小批量大大减少了收敛到局部解所需的计算量。与其他减少 k-means 收敛时间的算法相比，小批量 k-means 产生的结果通常仅略差于标准算法。 该算法在两个主要步骤之间迭代，类似于普通的 k-means。在第一步中，从数据集中随机抽取 :math:`b` 个样本，形成一个小批量。然后将它们分配给最近的质心。在第二步中，更新质心。与 k-means 不同，这是在每个样本基础上完成的。对于小批量中的每个样本，分配的质心通过取该样本和所有先前分配给该质心的样本的流平均值来更新。这具有随时间减少质心变化率的效果。这些步骤一直执行直到收敛或达到预定的迭代次数。 :class:`MiniBatchKMeans` 比 :class:`KMeans` 收敛得更快，但结果的质量有所降低。在实践中，这种质量差异可能非常小，如示例和引用的参考文献所示。 .. figure:: ../auto_examples/cluster/images/sphx_glr_plot_mini_batch_kmeans_001.png :target: ../auto_examples/cluster/plot_mini_batch_kmeans.html :align: center :scale: 100 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_mini_batch_kmeans.py` : :class:`KMeans` 和 :class:`MiniBatchKMeans` 的比较 * :ref:`sphx_glr_auto_examples_text_plot_document_clustering.py` : 文档聚类 使用基于稀疏数据的 :class:`KMeans` 和 :class:`MiniBatchKMeans` * :ref:`sphx_glr_auto_examples_cluster_plot_dict_face_patches.py` .. dropdown:: 参考文献 * `"Web Scale K-Means clustering" `_ D. Sculley, *Proceedings of the 19th international conference on World wide web* (2010) .. _affinity_propagation: 亲和传播 ======== :class:`AffinityPropagation` 通过在样本对之间发送消息直到收敛来创建聚类。然后使用少量代表性样本（称为典范）来描述数据集。样本对之间发送的消息表示一个样本作为另一个样本典范的适宜性，这些消息会根据其他对的消息值进行更新。这个更新过程迭代进行，直到收敛，此时选择最终的典范，从而得到最终的聚类结果。 .. figure:: ../auto_examples/cluster/images/sphx_glr_plot_affinity_propagation_001.png :target: ../auto_examples/cluster/plot_affinity_propagation.html :align: center :scale: 50 亲和传播的一个有趣之处在于它根据提供的数据选择聚类的数量。为此，两个重要的参数是 *preference*（偏好），它控制使用的典范数量，以及 *damping factor*（阻尼因子），它抑制责任和可用性消息，以避免在更新这些消息时出现数值振荡。 亲和传播的主要缺点是其复杂性。该算法的时间复杂度为 :math:`O(N^2 T)` 阶，其中 :math:`N` 是样本数量，:math:`T` 是收敛前的迭代次数。此外，如果使用密集相似度矩阵，内存复杂度为 :math:`O(N^2)` 阶，但如果使用稀疏相似度矩阵，则可以降低。这使得亲和传播在处理大规模数据时最为适用。 适用于中小型数据集。 .. dropdown:: 算法描述 点之间发送的消息属于两种类别之一。第一种是责任 :math:`r(i, k)` ，即累积的证据表明样本 :math:`k` 应该是样本 :math:`i` 的示例。第二种是可用性 :math:`a(i, k)` ，即累积的证据表明样本 :math:`i` 应该选择样本 :math:`k` 作为其示例，并考虑所有其他样本的值，表明 :math:`k` 应该是示例。通过这种方式，如果样本 (1) 与许多样本足够相似，并且 (2) 被许多样本选择为代表自身，则选择示例。 更正式地，样本 :math:`k` 作为样本 :math:`i` 的示例的责任由以下公式给出： .. math:: r(i, k) \leftarrow s(i, k) - max [ a(i, k') + s(i, k') \forall k' \neq k ] 其中 :math:`s(i, k)` 是样本 :math:`i` 和样本 :math:`k` 之间的相似度。样本 :math:`k` 作为样本 :math:`i` 的示例的可用性由以下公式给出： .. math:: a(i, k) \leftarrow min [0, r(k, k) + \sum_{i'~s.t.~i' \notin \{i, k\}}{r(i', k)}] 首先，所有 :math:`r` 和 :math:`a` 的值都设置为零，并且每个值的计算迭代直到收敛。如上所述，为了避免更新消息时的数值振荡，引入了阻尼因子 :math:`\lambda` 到迭代过程中： .. math:: r_{t+1}(i, k) = \lambda\cdot r_{t}(i, k) + (1-\lambda)\cdot r_{t+1}(i, k) .. math:: a_{t+1}(i, k) = \lambda\cdot a_{t}(i, k) + (1-\lambda)\cdot a_{t+1}(i, k) 其中 :math:`t` 表示迭代次数。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_affinity_propagation.py` ：在具有 3 个类别的合成 2D 数据集上的亲和传播 * :ref:`sphx_glr_auto_examples_applications_plot_stock_market.py` 亲和传播 在金融时间序列中寻找公司群体 .. _mean_shift: Mean Shift ========== :class:`MeanShift` 聚类旨在发现样本平滑密度中的 *斑点*。它是一种基于质心的算法，通过更新候选质心为给定区域内点的均值来工作。这些候选质心随后在后期处理阶段进行过滤，以消除近似重复项，形成最终的质心集合。 .. dropdown:: 数学细节 质心候选位置使用一种称为爬山的技术进行迭代调整，该技术找到估计概率密度的局部最大值。给定迭代 :math:`t` 的候选质心 :math:`x` ，候选质心根据以下方程更新： .. math:: x^{t+1} = x^t + m(x^t) 其中 :math:`m` 是 *均值漂移* 向量，该向量针对每个质心计算，指向点密度增加最大的区域。为了计算 :math:`m` ，我们定义 :math:`N(x)` 为在给定距离内围绕 :math:`x` 的样本邻域。然后使用以下方程计算 :math:`m` ，有效地将质心更新为其邻域内样本的均值： .. math:: m(x) = \frac{1}{|N(x)|} \sum_{x_j \in N(x)}x_j - x 通常，:math:`m` 的方程取决于用于密度估计的内核。通用公式为： .. math:: 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 在我们的实现中，如果 :math:`x` 足够小，则 :math:`K(x)` 等于 1，否则等于 0。实际上，:math:`K(y - x)` 指示 :math:`y` 是否在 :math:`x` 的邻域内。 算法自动设置聚类数量，而不是依赖于参数 ``bandwidth`` ，该参数规定了搜索区域的大小。此参数可以手动设置，但可以使用提供的估计方法进行估计。 ``estimate_bandwidth`` 函数，如果未设置带宽，则会调用该函数。 该算法不具备高度可扩展性，因为它在执行过程中需要进行多次最近邻搜索。然而，该算法保证会收敛，但当质心的变化很小时，算法会停止迭代。 对新样本进行标记是通过为给定样本找到最近的质心来完成的。 .. figure:: ../auto_examples/cluster/images/sphx_glr_plot_mean_shift_001.png :target: ../auto_examples/cluster/plot_mean_shift.html :align: center :scale: 50 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_mean_shift.py` : 在具有3个类别的合成2D数据集上进行Mean Shift聚类。 .. dropdown:: 参考文献 * :doi:`"Mean shift: A robust approach toward feature space analysis" <10.1109/34.1000236>` D. Comaniciu and P. Meer, *IEEE Transactions on Pattern Analysis and Machine Intelligence* (2002) .. _spectral_clustering: 谱聚类 ======= :class:`SpectralClustering` 对样本间的亲和矩阵进行低维嵌入，然后对低维空间中特征向量的分量进行聚类，例如通过KMeans。如果亲和矩阵是稀疏的，并且使用 `amg` 求解器来解决特征值问题，那么它在计算上是特别高效的（注意， `amg` 求解器需要安装 `pyamg `_ 模块。） 当前版本的谱聚类需要预先指定聚类的数量。它在小数量的聚类上表现良好，但不建议用于大量聚类。 对于两个聚类，谱聚类解决了相似图上 `归一化割 `_ 问题的凸松弛：将图切割成两部分，使得被切割的边的权重相对于每个部分内部边的权重较小。 集群。在处理图像时，这一标准尤其有趣，其中图的顶点是像素，相似图的边的权重是使用图像梯度的函数计算的。 .. |noisy_img| image:: ../auto_examples/cluster/images/sphx_glr_plot_segmentation_toy_001.png :target: ../auto_examples/cluster/plot_segmentation_toy.html :scale: 50 .. |segmented_img| image:: ../auto_examples/cluster/images/sphx_glr_plot_segmentation_toy_002.png :target: ../auto_examples/cluster/plot_segmentation_toy.html :scale: 50 .. centered:: |noisy_img| |segmented_img| .. warning:: 将距离转换为良好分布的相似性 请注意，如果相似性矩阵的值分布不佳，例如包含负值或使用距离矩阵而非相似性矩阵，则谱问题将是奇异的，问题将无法解决。在这种情况下，建议对矩阵的条目应用变换。例如，在有符号距离矩阵的情况下，通常会应用热核变换:: similarity = np.exp(-beta * distance / distance.std()) 请参阅示例以了解此类应用。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_segmentation_toy.py` : 使用谱聚类从噪声背景中分割对象。 * :ref:`sphx_glr_auto_examples_cluster_plot_coin_segmentation.py` : 使用谱聚类将硬币图像分割成不同区域。 .. |coin_kmeans| image:: ../auto_examples/cluster/images/sphx_glr_plot_coin_segmentation_001.png :target: ../auto_examples/cluster/plot_coin_segmentation.html :scale: 35 .. |coin_discretize| image:: ../auto_examples/cluster/images/sphx_glr_plot_coin_segmentation_002.png :target: ../auto_examples/cluster/plot_coin_segmentation.html :scale: 35 .. |coin_cluster_qr| image:: ../auto_examples/cluster/images/sphx_glr_plot_coin_segmentation_003.png :target: ../auto_examples/cluster/plot_coin_segmentation.html :scale: 35 不同的标签分配策略 -------------------- 可以使用不同的标签分配策略，对应于 :class:`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| ================================ ================================ ================================ .. dropdown:: 参考文献 * `"Multiclass spectral clustering" `_ Stella X. Yu, Jianbo Shi, 2003 * :doi:`"Simple, direct, and efficient multi-way spectral clustering"<10.1093/imaiai/iay008>` Anil Damle, Victor Minden, Lexing Ying, 2019 .. _spectral_clustering_graph: 谱聚类图 ---------- 谱聚类也可以通过其谱嵌入来划分图。在这种情况下，亲和矩阵是图的邻接矩阵，并且 SpectralClustering 以 `affinity='precomputed'` 初始化:: >>> from sklearn.cluster import SpectralClustering >>> sc = SpectralClustering(3, affinity='precomputed', n_init=100, ... assign_labels='discretize') >>> sc.fit_predict(adjacency_matrix) # doctest: +SKIP .. dropdown:: 参考文献 * :doi:`"谱聚类教程" <10.1007/s11222-007-9033-z>` Ulrike von Luxburg, 2007 * :doi:`"归一化切割与图像分割" <10.1109/34.868688>` Jianbo Shi, Jitendra Malik, 2000 * `"谱分割的随机游走视角" `_ Marina Meila, Jianbo Shi, 2001 * `"关于谱聚类：分析与算法" `_ Andrew Y. Ng, Michael I. Jordan, Yair Weiss, 2001 * :arxiv:`"随机块分区流图挑战的预处理谱聚类" <1708.07481>` David Zhuzhunashvili, Andrew Knyazev .. _hierarchical_clustering: 层次聚类 ======== 层次聚类是一类通用的聚类算法，通过逐步合并或分割聚类来构建嵌套的聚类结构。这种聚类层次结构表示为一棵树（或树状图）。树的根是包含所有样本的唯一聚类，叶子是只有一个样本的聚类。更多详情请参见 `维基百科页面 `_ 。 :class:`AgglomerativeClustering` 对象使用自底向上的方法执行层次聚类：每个观测值从其自己的聚类开始，聚类逐步合并在一起。链接标准决定了合并策略使用的度量： - **Ward** 最小化所有聚类内的平方差之和。它是一种方差最小化方法，从这个意义上说，它类似于 k-means 目标函数，但采用了一种凝聚层次方法来处理。 - **最大** 或 **完全连接** 最小化成对集群观测之间的最大距离。 - **平均连接** 最小化所有成对集群观测之间的平均距离。 - **单连接** 最小化成对集群最近观测之间的距离。 :class:`AgglomerativeClustering` 也可以在联合使用连接矩阵时扩展到大量样本，但在样本之间没有添加连接约束时计算成本很高：它在每一步考虑所有可能的合并。 .. topic:: :class:`FeatureAgglomeration` :class:`FeatureAgglomeration` 使用凝聚聚类来将非常相似的特征分组在一起，从而减少特征的数量。它是一种降维工具，参见 :ref:`data_reduction` 。 不同的连接类型：Ward、完全、平均和单连接 ------------------------------------------------------------------- :class:`AgglomerativeClustering` 支持 Ward、单、平均和完全连接策略。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_linkage_comparison_001.png :target: ../auto_examples/cluster/plot_linkage_comparison.html :scale: 43 凝聚聚类具有“富者愈富”的行为，导致集群大小不均匀。在这方面，单连接是最差的策略，而 Ward 给出了最规则的大小。然而，Ward 的亲和性（或聚类中使用的距离）不能变化，因此对于非欧几里得度量，平均连接是一个好的替代方案。单连接虽然对噪声数据不鲁棒，但可以非常高效地计算，因此对于提供较大数据集的层次聚类非常有用。单连接在非球状数据上也可以表现良好。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_digits_linkage.py` ：在一个真实数据集中探索不同的连接策略。 * :ref:`sphx_glr_auto_examples_cluster_plot_linkage_comparison.py` : 探索玩具数据集中不同的链接策略。 聚类层次的可视化 ------------------ 可以可视化表示聚类层次合并的树状图。视觉检查通常有助于理解数据的结构，尽管在小样本量的情况下更为有用。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_dendrogram_001.png :target: ../auto_examples/cluster/plot_agglomerative_dendrogram.html :scale: 42 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_agglomerative_dendrogram.py` 添加连接性约束 ---------------- :class:`AgglomerativeClustering` 的一个有趣方面是，可以通过定义每个样本的邻近样本的连接矩阵，向该算法添加连接性约束（只有相邻的聚类可以合并在一起）。例如，在下面的瑞士卷示例中，连接性约束禁止合并不在瑞士卷上相邻的点，从而避免形成跨越卷的折叠重叠的聚类。 .. |unstructured| image:: ../auto_examples/cluster/images/sphx_glr_plot_ward_structured_vs_unstructured_001.png :target: ../auto_examples/cluster/plot_ward_structured_vs_unstructured.html :scale: 49 .. |structured| image:: ../auto_examples/cluster/images/sphx_glr_plot_ward_structured_vs_unstructured_002.png :target: ../auto_examples/cluster/plot_ward_structured_vs_unstructured.html :scale: 49 .. centered:: |unstructured| |structured| 这些约束有助于施加一定的局部结构，但它们也使算法在样本数量较多时更快。 通过连接性矩阵施加连接性约束：一个scipy稀疏矩阵，其元素仅位于行和列的交点处，这些行和列的索引对应于应该连接的数据集。这个矩阵可以从先验信息构建：例如，您可能希望通过仅合并从一个页面指向另一个页面的链接来对网页进行聚类。它也可以从数据中学习，例如使用:func:`sklearn.neighbors.kneighbors_graph` 来限制合并到最近邻，如:ref:`这个示例` 所示，或者使用:func:`sklearn.feature_extraction.image.grid_to_graph` 来仅允许图像上相邻像素的合并，如:ref:`硬币` 示例所示。 .. warning:: **单链接、平均链接和完全链接的连接性约束** 连接性约束和单链接、完全链接或平均链接可以增强聚合聚类的“富者愈富”方面，特别是如果它们是使用:func:`sklearn.neighbors.kneighbors_graph` 构建的。在小数量簇的极限情况下，它们往往会产生一些宏观上占据的簇和几乎空的簇。（参见:ref:`sphx_glr_auto_examples_cluster_plot_agglomerative_clustering.py` 中的讨论）。单链接是对此问题最脆弱的链接选项。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_001.png :target: ../auto_examples/cluster/plot_agglomerative_clustering.html :scale: 38 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_002.png :target: ../auto_examples/cluster/plot_agglomerative_clustering.html :scale: 38 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_003.png :target: ../auto_examples/cluster/plot_agglomerative_clustering.html :scale: 38 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_004.png :target: ../auto_examples/cluster/plot_agglomerative_clustering.html :scale: 38 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_coin_ward_segmentation.py` : 使用Ward聚类将硬币图像分割成不同区域。 * :ref:`sphx_glr_auto_examples_cluster_plot_ward_structured_vs_unstructured.py` : 在瑞士卷数据集上使用Ward算法的示例，比较结构化方法与非结构化方法。 * :ref:`sphx_glr_auto_examples_cluster_plot_feature_agglomeration_vs_univariate_selection.py` : 基于Ward层次聚类的特征聚合进行降维的示例。 * :ref:`sphx_glr_auto_examples_cluster_plot_agglomerative_clustering.py` 不同度量方式 ------------------- 单链接、平均链接和完全链接可以使用多种距离（或相似度），特别是欧氏距离（*l2*）、曼哈顿距离（或城市街区距离，或*l1*）、余弦距离，或任何预计算的相似度矩阵。 * *l1* 距离通常适用于稀疏特征或稀疏噪声：即许多特征为零，如使用罕见单词出现次数的文本挖掘。 * *余弦* 距离很有趣，因为它对信号的全局缩放不变。 选择度量方式的指导原则是使用能够最大化不同类别样本间距离，并最小化每个类别内样本间距离的度量。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_metrics_005.png :target: ../auto_examples/cluster/plot_agglomerative_clustering_metrics.html :scale: 32 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_metrics_006.png :target: ../auto_examples/cluster/plot_agglomerative_clustering_metrics.html :scale: 32 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_metrics_007.png :target: ../auto_examples/cluster/plot_agglomerative_clustering_metrics.html :scale: 32 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_agglomerative_clustering_metrics.py` 二分K均值 --------- .. _bisect_k_means: :class:`BisectingKMeans` 是 :class:`KMeans` 的迭代变体，使用分裂层次聚类。它不是一次性创建所有质心，而是基于先前的聚类逐步选择质心：一个聚类被重复地分成两个新聚类，直到达到目标聚类数。 当聚类数较大时，:class:`BisectingKMeans` 比 :class:`KMeans` 更高效，因为它每次二分时只处理数据集的一个子集，而 :class:`KMeans` 总是处理整个数据集。 尽管 :class:`BisectingKMeans` 无法从 `"k-means++"` 初始化的优势中受益，但它仍将以较低的计算成本产生与 `KMeans(init="k-means++")` 相当的惯性结果，并且很可能比随机初始化的 `KMeans` 产生更好的结果。 如果聚类数相对于数据点数较小，这种变体比凝聚聚类更高效。 这种变体也不会产生空聚类。 有两种策略选择要分裂的聚类： - ``bisecting_strategy="largest_cluster"`` 选择点数最多的聚类 - ``bisecting_strategy="biggest_inertia"`` 选择惯性最大的聚类（内部平方误差和最大的聚类） 在大多数情况下，按数据点最多的方式选择聚类会产生与按惯性选择一样准确的结果，并且速度更快（特别是在数据点较多时，计算误差可能成本较高）。 按数据点最多的方式选择聚类还可能产生大小相似的聚类，而 `KMeans` 已知会产生大小不同的聚类。 Bisecting K-Means 和常规 K-Means 之间的区别可以在示例中看到 :ref:`sphx_glr_auto_examples_cluster_plot_bisect_kmeans.py` 。 虽然常规 K-Means 算法倾向于创建不相关的聚类， 但 Bisecting K-Means 的聚类是有序的，并且形成了非常明显的层次结构。 .. dropdown:: 参考文献 * `"文档聚类技术的比较" `_ Michael Steinbach, George Karypis 和 Vipin Kumar, 明尼苏达大学计算机科学与工程系 (2000年6月) * `"K-Means 和 Bisecting K-Means 算法在网络日志数据中的性能分析" `_ K.Abirami 和 Dr.P.Mayilvahanan, 国际新兴技术工程研究期刊 (IJETER) 第4卷, 第8期 (2016年8月) * `"基于 K 值自确定和聚类中心优化的 Bisecting K-means 算法" `_ Jian Di, Xinyue Gou 华北电力大学控制与计算机工程学院, 河北保定 (2017年8月) .. _dbscan: DBSCAN ====== :class:`DBSCAN` 算法将聚类视为由低密度区域分隔的高密度区域。由于这种相当通用的观点， DBSCAN 发现的聚类可以是任何形状，而 k-means 则假设聚类是凸形的。DBSCAN 的核心概念是 *核心样本*，这些样本位于高密度区域中。因此，一个聚类是一组核心样本，每个样本彼此接近 （通过某种距离度量），以及一组接近核心样本的非核心样本（但它们本身不是核心样本）。 该算法有两个参数， ``min_samples`` 和 ``eps`` ，它们正式定义了我们所称的 *密集*。 较高的 ``min_samples`` 或较低的 ``eps`` 表示形成一个簇所需的密度更高。 更正式地，我们将核心样本定义为数据集中的一个样本， 使得在其距离 ``eps`` 内存在 ``min_samples`` 个其他样本，这些样本被定义为核心样本的*邻居*。这告诉我们核心样本位于向量空间的密集区域。一个簇是一组核心样本，可以通过递归地取一个核心样本，找到其所有为核心样本的邻居，找到这些邻居的所有为核心样本的邻居，依此类推来构建。一个簇还包含一组非核心样本，这些样本是簇中核心样本的邻居，但本身不是核心样本。直观上，这些样本位于簇的边缘。 根据定义，任何核心样本都属于一个簇。任何不是核心样本且与任何核心样本的距离至少为 ``eps`` 的样本，算法会将其视为异常值。 虽然参数 ``min_samples`` 主要控制算法对噪声的容忍度（在噪声大且数据量大的数据集上，可能需要增加此参数），但参数 ``eps`` 对于数据集和距离函数的选择*至关重要*，通常不能保留默认值。它控制点的局部邻域。当选择得太小时，大多数数据根本不会被聚类（并标记为 ``-1`` 表示“噪声”）。当选择得太大时，会导致接近的簇合并为一个簇，最终整个数据集被返回为一个单一的簇。文献中已经讨论了一些选择此参数的启发式方法，例如基于最近邻距离图中的拐点（如以下参考文献中所讨论的）。 在下图中，颜色表示簇成员身份，大圆圈表示算法找到的核心样本。较小的圆圈是非核心样本。 仍然属于某个簇的样本。此外，离群点以下用黑色点表示。 .. |dbscan_results| image:: ../auto_examples/cluster/images/sphx_glr_plot_dbscan_002.png :target: ../auto_examples/cluster/plot_dbscan.html :scale: 50 .. centered:: |dbscan_results| .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_dbscan.py` .. dropdown:: 实现 DBSCAN算法是确定性的，当给定相同数据并以相同顺序输入时，总是生成相同的簇。然而，当数据以不同顺序提供时，结果可能会有所不同。首先，尽管核心样本总是会被分配到相同的簇中，但这些簇的标签将取决于在数据中遇到这些样本的顺序。其次，更重要的是，非核心样本被分配到的簇可能会根据数据顺序的不同而有所不同。这种情况会发生在非核心样本与两个不同簇中的核心样本之间的距离都小于 ``eps`` 时。根据三角不等式，这两个核心样本之间的距离必须大于 ``eps`` ，否则它们会在同一个簇中。非核心样本会被分配到在数据遍历过程中首先生成的那个簇，因此结果将取决于数据顺序。 当前的实现使用球树和kd树来确定点的邻域，这避免了计算完整的距离矩阵（如在0.14版本之前的scikit-learn中所做的那样）。保留了使用自定义度量的可能性；详情请参见 :class:`NearestNeighbors` 。 .. dropdown:: 大样本尺寸的内存消耗 此实现默认情况下不是内存高效的，因为它在无法使用kd树或球树的情况下（例如，使用稀疏矩阵时）构建了一个完整的成对相似性矩阵。该矩阵将消耗 :math:`n^2` 的内存。 浮点数。解决这个问题的一些机制包括： - 使用 :ref:`OPTICS ` 聚类结合 `extract_dbscan` 方法。OPTICS 聚类也会计算完整的成对矩阵，但一次只保留一行在内存中（内存复杂度为 n）。 - 可以预先以内存高效的方式计算稀疏半径邻域图（其中缺失的条目被假定为超出 eps），并且可以在其上运行 dbscan，使用 ``metric='precomputed'`` 。参见 :meth:`sklearn.neighbors.NearestNeighbors.radius_neighbors_graph` 。 - 可以压缩数据集，如果数据中存在完全重复项，则删除这些重复项，或者使用 BIRCH。然后你只需要为大量点提供相对较少的代表。然后可以在拟合 DBSCAN 时提供 ``sample_weight`` 。 .. dropdown:: 参考文献 * `A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise `_ 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 * :doi:`DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. <10.1145/3068335>` Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). In ACM Transactions on Database Systems (TODS), 42(3), 19. .. _hdbscan: HDBSCAN ======= :class:`HDBSCAN` 算法可以看作是 :class:`DBSCAN` 和 :class:`OPTICS` 的扩展。具体来说，:class:`DBSCAN` 假设聚类标准（即密度要求）是 *全局均匀的*。换句话说，:class:`DBSCAN` 可能难以成功捕捉具有不同密度的聚类。:class:`HDBSCAN` 缓解了这一假设，并通过构建聚类问题的替代表示来探索所有可能的密度尺度。 .. note:: 此实现改编自HDBSCAN的原始实现， 基于[LJ2017]_的 `scikit-learn-contrib/hdbscan `_ 。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_hdbscan.py` 互达性图 -------- HDBSCAN首先定义样本 :math:`x_p` 的 *核心距离* :math:`d_c(x_p)` ，即到其第 `min_samples` 个最近邻的距离，包括自身。例如， 如果 `min_samples=5` 且 :math:`x_*` 是 :math:`x_p` 的第5个最近邻，则核心距离为： .. math:: d_c(x_p)=d(x_p, x_*). 接下来定义两点 :math:`x_p, x_q` 的 *互达性距离* :math:`d_m(x_p, x_q)` ，即： .. math:: d_m(x_p, x_q) = \max\{d_c(x_p), d_c(x_q), d(x_p, x_q)\} 这两个概念使我们能够构建 *互达性图* :math:`G_{ms}` ，该图针对固定的 `min_samples` 选择，将每个样本 :math:`x_p` 与图的一个顶点关联，从而点 :math:`x_p, x_q` 之间的边是它们之间的互达性距离 :math:`d_m(x_p, x_q)` 。我们可以通过移除任何值大于 :math:`\varepsilon` 的边来构建该图的子集，记为 :math:`G_{ms,\varepsilon}` ：从原始图中。任何核心距离小于 :math:`\varepsilon` 的点在此阶段被标记为噪声。剩余的点通过找到这个修剪图的连通分量来进行聚类。 .. note:: 取修剪图 :math:`G_{ms,\varepsilon}` 的连通分量等价于以 `min_samples` 和 :math:`\varepsilon` 运行DBSCAN*。DBSCAN* 是[CM2013]_中提到的DBSCAN的轻微修改版本。 层次聚类 -------- HDBSCAN可以看作是在所有 :math:`\varepsilon` 值上执行DBSCAN*聚类的算法。如前所述，这等价于找到连通 互可达性图的所有值的组成部分 :math:`\varepsilon` 。为了高效地完成这一任务，HDBSCAN首先从完全连接的互可达性图中提取一个最小生成树（MST），然后贪婪地剪除权重最高的边。HDBSCAN算法的概述如下： 1. 提取 :math:`G_{ms}` 的MST。 2. 通过为每个顶点添加一条“自边”来扩展MST，其权重等于基础样本的核心距离。 3. 为MST初始化一个单一的簇和标签。 4. 从MST中移除权重最大的边（平局情况下同时移除）。 5. 为包含现已移除边的端点的连通分量分配簇标签。如果分量没有至少一条边，则分配一个“空”标签，将其标记为噪声。 6. 重复步骤4-5，直到没有更多的连通分量。 因此，HDBSCAN能够以层次化的方式获得DBSCAN* 对于固定 `min_samples` 选择的所有可能的分区。实际上，这使得HDBSCAN能够在多个密度上进行聚类，因此不再需要 :math:`\varepsilon` 作为超参数。相反，它仅依赖于 `min_samples` 的选择，这通常是一个更稳健的超参数。 .. |hdbscan_ground_truth| image:: ../auto_examples/cluster/images/sphx_glr_plot_hdbscan_005.png :target: ../auto_examples/cluster/plot_hdbscan.html :scale: 75 .. |hdbscan_results| image:: ../auto_examples/cluster/images/sphx_glr_plot_hdbscan_007.png :target: ../auto_examples/cluster/plot_hdbscan.html :scale: 75 .. centered:: |hdbscan_ground_truth| .. centered:: |hdbscan_results| HDBSCAN可以通过额外的超参数 `min_cluster_size` 进行平滑处理，该参数指定在层次聚类过程中，样本数少于 `minimum_cluster_size` 的组件被视为噪声。在实践中， 可以将 `minimum_cluster_size = min_samples` 设置为耦合参数，从而简化超参数空间。 .. rubric:: 参考文献 .. [CM2013] Campello, R.J.G.B., Moulavi, D., Sander, J. (2013). 基于层次密度估计的密度聚类。在：Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (编) 知识发现与数据挖掘进展。PAKDD 2013. 计算机科学讲义(), 卷 7819。Springer, 柏林, 海德堡。 :doi:`基于层次密度估计的密度聚类 <10.1007/978-3-642-37456-2_14>` .. [LJ2017] L. McInnes 和 J. Healy, (2017). 加速层次密度聚类。在：IEEE 国际数据挖掘会议论文集 (ICDMW), 2017, 页码 33-42。 :doi:`加速层次密度聚类 <10.1109/ICDMW.2017.12>` .. _optics: OPTICS ====== :class:`OPTICS` 算法与 :class:`DBSCAN` 算法有许多相似之处，可以被视为对 DBSCAN 的泛化，它将 ``eps`` 要求从单一值放宽到值范围。DBSCAN 和 OPTICS 之间的关键区别在于，OPTICS 算法构建了一个 *可达性* 图，该图为每个样本分配了一个 ``reachability_`` 距离和一个在聚类 ``ordering_`` 属性中的位置；这两个属性在模型拟合时被分配，并用于确定聚类成员资格。如果 OPTICS 以 ``max_eps`` 的默认值 *inf* 运行，那么可以使用 ``cluster_optics_dbscan`` 方法在线性时间内对任何给定的 ``eps`` 值重复执行 DBSCAN 风格的聚类提取。将 ``max_eps`` 设置为较低的值将导致较短的运行时间，并且可以被视为从每个点寻找其他潜在可达点的最大邻域半径。 .. |optics_results| image:: ../auto_examples/cluster/images/sphx_glr_plot_optics_001.png :target: ../auto_examples/cluster/plot_optics.html :scale: 50 .. centered:: |optics_results| OPTICS 生成的 *可达性* 距离允许在一个数据集中提取可变密度的簇。如上图所示，结合 *可达性* 距离和数据集 ``ordering_`` 可以生成一个 *可达性图*，其中 Y 轴表示点的密度，并且点的顺序使得相邻点彼此靠近。在可达性图中“切割”单个值会产生类似于 DBSCAN 的结果；所有高于“切割”的点都被分类为噪声，并且每次从左到右阅读时出现断裂表示一个新的簇。OPTICS 默认的簇提取方法是通过图中的陡峭斜坡来寻找簇，用户可以使用参数 ``xi`` 定义什么算作陡峭斜坡。还可以对图本身进行其他分析，例如通过可达性图树状图生成数据的分层表示，并且算法检测到的簇层次结构可以通过参数 ``cluster_hierarchy_`` 访问。上图已经进行了颜色编码，使得平面空间中的簇颜色与可达性图的线性段簇相匹配。请注意，蓝色和红色簇在可达性图中是相邻的，并且可以分层表示为较大父簇的子簇。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_optics.py` .. dropdown:: 与 DBSCAN 的比较 OPTICS 的 ``cluster_optics_dbscan`` 方法和 DBSCAN 的结果非常相似，但并不总是完全相同；特别是边缘点和噪声点的标记。部分原因是 OPTICS 处理的每个密集区域的首个样本具有较大的可达性值，同时在其区域内靠近其他点，因此有时会被标记为噪声而不是边缘点。这会影响相邻点在它们被考虑为候选点时的分类。 被标记为边缘或噪声。 注意，对于任何单一的 ``eps`` 值，DBSCAN 的运行时间通常会比 OPTICS 短；然而，对于在不同 ``eps`` 值下的重复运行，OPTICS 的单次运行可能需要的累计运行时间比 DBSCAN 少。同样重要的是要注意，只有当 ``eps`` 和 ``max_eps`` 接近时，OPTICS 的输出才接近 DBSCAN 的输出。 .. dropdown:: 计算复杂度 使用空间索引树来避免计算完整的距离矩阵，并允许在大量样本上进行有效的内存使用。可以通过 ``metric`` 关键字提供不同的距离度量。 对于大型数据集，可以通过 :class:`HDBSCAN` 获得类似（但非相同）的结果。HDBSCAN 实现是多线程的，并且具有比 OPTICS 更好的算法运行时复杂度，但代价是内存扩展性较差。对于耗尽系统内存的极大数据集，OPTICS 将保持 :math:`n` （而不是 :math:`n^2` ）的内存扩展性；然而，可能需要调整 ``max_eps`` 参数以在合理的时间内给出解决方案。 .. dropdown:: 参考文献 * "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. .. _birch: BIRCH ===== :class:`Birch` 构建了一个名为聚类特征树（CFT）的树来处理给定数据。数据本质上被有损压缩为一组聚类特征节点（CF 节点）。CF 节点包含多个子聚类，称为聚类特征子聚类（CF 子聚类），这些位于非终端 CF 节点中的 CF 子聚类可以有 CF 节点作为子节点。 CF 子聚类保存了进行聚类所需的必要信息，从而避免了在内存中保存整个输入数据的需要。这些信息包括： - 子簇中的样本数量。 - 线性和 - 一个保存所有样本总和的 n 维向量 - 平方和 - 所有样本的平方 L2 范数之和。 - 质心 - 为了避免重新计算线性和 / 样本数量。 - 质心的平方范数。 BIRCH 算法有两个参数，阈值和分支因子。 分支因子限制了节点中子簇的数量，而 阈值限制了进入样本与现有子簇之间的距离。 该算法可以看作是一种实例或数据约简方法， 因为它将输入数据减少为一组直接从 CFT 的叶子节点获得的子簇。这种约简数据可以通过将其输入到全局聚类器中进一步处理。这个全局聚类器可以通过 ``n_clusters`` 设置。如果 ``n_clusters`` 设置为 None，则直接从叶子节点读取子簇，否则全局聚类步骤将这些子簇标记为全局簇（标签），并将样本映射到最近子簇的全局标签。 .. dropdown:: 算法描述 - 新样本插入到 CF 树的根节点，这是一个 CF 节点。然后它与根节点中合并后半径最小的子簇合并，受阈值和分支因子条件的限制。如果子簇有任何子节点，则重复此过程直到到达叶子节点。在叶子节点中找到最近的子簇后，该子簇及其父子簇的属性会递归更新。 - 如果通过合并新样本和最近的子簇得到的子簇的半径大于阈值的平方，并且如果子簇的数量大于分支因子，则为这个新样本临时分配空间。取两个最远的子簇，并根据它们之间的距离将子簇分成两组。 这些子簇之间的距离。 - 如果这个分裂节点有一个父子簇并且有空间容纳一个新的子簇，那么父子簇被分裂成两个。如果没有空间，那么这个节点再次被分裂成两个，并且这个过程递归地继续，直到达到根节点。 .. dropdown:: BIRCH还是MiniBatchKMeans？ - BIRCH在高维数据上的扩展性不是很好。根据经验，如果 ``n_features`` 大于二十，通常使用MiniBatchKMeans会更好。 - 如果需要减少数据实例的数量，或者希望得到大量的子簇作为预处理步骤或其他用途，BIRCH比MiniBatchKMeans更有用。 .. image:: ../auto_examples/cluster/images/sphx_glr_plot_birch_vs_minibatchkmeans_001.png :target: ../auto_examples/cluster/plot_birch_vs_minibatchkmeans.html .. dropdown:: 如何使用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()`` ，这将执行全局聚类。 .. dropdown:: 参考文献 * Tian Zhang, Raghu Ramakrishnan, Maron Livny BIRCH: 一种针对大型数据库的高效数据聚类方法。 https://www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf * Roberto Perdisci JBirch - BIRCH聚类算法的Java实现 https://code.google.com/archive/p/jbirch 分类算法。特别是任何评估指标不应考虑聚类标签的绝对值，而应考虑此聚类是否定义了与某些真实类别集相似的数据分离，或者是否满足某些假设，即属于同一类别的成员比属于不同类别的成员更相似，根据某种相似性度量。 .. currentmodule:: sklearn.metrics .. _rand_score: .. _adjusted_rand_score: 兰德指数 -------- 给定真实类别分配的知识 ``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... 此外， :func:`rand_score` 和 :func:`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 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.07... .. topic:: 优点： - **可解释性**：未调整的兰德指数与在 `labels_pred` 和 `labels_true` 中标签相同的样本对数量成正比，或者在两者中都不同的样本对数量成正比。 - **随机（均匀）标签分配的调整后兰德指数得分接近 0.0**，对于任何 ``n_clusters`` 和 ``n_samples`` 的值都是如此（而对于未调整的兰德指数或 V-measure 则不是这样）。 - **有界范围**：较低的值表示不同的标签分配，相似的聚类具有较高的（调整或未调整）兰德指数，1.0 是完美匹配得分。未调整的兰德指数得分范围是 [0, 1]，调整后的兰德指数得分范围是 [-1, 1]。 - **不假设聚类结构**：（调整或未调整）兰德指数可以用于比较所有类型的聚类算法，并且可以用于比较假设各向同性斑点形状的 k-means 等算法与能找到“折叠”形状聚类的谱聚类算法的结果。 .. topic:: 缺点： - 与惯性相反，**（调整或未调整）兰德指数需要已知真实类别**，这在实践中几乎从未可用，或者需要人工标注者进行手动分配（如在监督学习设置中）。 然而，（调整或未调整）兰德指数在纯无监督学习设置中也可以是有用的，例如在比较不同聚类算法的结果时。 无监督设置作为共识指数的一个构建模块，可用于聚类模型选择（待办事项）。 - **未调整的兰德指数通常接近1.0**，即使聚类本身存在显著差异。这可以通过将兰德指数解释为聚类产生的元素对标签准确性来理解：在实践中，通常存在大多数元素对在预测聚类和真实聚类下都被分配为“不同”对标签，从而导致高比例的一致对标签，进而导致高分。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_adjusted_for_chance_measures.py` : 分析数据集大小对随机分配的聚类度量值的影响。 .. dropdown:: 数学公式 如果C是真实类别分配，K是聚类结果，我们定义 :math:`a` 和 :math:`b` 为： - :math:`a` ，在C和K中都属于同一集合的元素对数 - :math:`b` ，在C和K中都属于不同集合的元素对数 未调整的兰德指数则由以下公式给出： .. math:: \text{RI} = \frac{a + b}{C_2^{n_{samples}}} 其中 :math:`C_2^{n_{samples}}` 是数据集中所有可能的元素对数。无论计算是在有序对还是无序对上进行，只要计算一致即可。 然而，兰德指数并不能保证随机标签分配会得到接近零的值（特别是当聚类数与样本数在同一数量级时）。 为了抵消这种效应，我们可以通过定义调整后的兰德指数来折扣随机标签分配的预期RI :math:`E[\text{RI}]` ： .. math:: \text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]} .. dropdown:: 参考文献 * `比较分区 `_ L. Hubert 和 P. Arabie，Journal of Classification 1985 * `Hubert-Arabie 调整兰德指数的性质 `_ D. Steinley，Psychological Methods 2004 * `维基百科关于兰德指数的条目 `_ .. _mutual_info_score: 基于互信息的评分 ------------------ 给定真实类别分配 ``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) # doctest: +SKIP 0.22504... 可以在预测标签中对 0 和 1 进行排列，将 2 重命名为 3，并获得相同的分数:: >>> labels_pred = [1, 1, 0, 0, 3, 3] >>> metrics.adjusted_mutual_info_score(labels_true, labels_pred) # doctest: +SKIP 0.22504... 所有 :func:`mutual_info_score` , :func:`adjusted_mutual_info_score` 和 :func:`normalized_mutual_info_score` 都是对称的：交换参数不会改变分数。因此它们可以作为 **共识度量**:: >>> metrics.adjusted_mutual_info_score(labels_pred, labels_true) # doctest: +SKIP 0.22504... 完美标记的得分为 1.0:: >>> labels_pred = labels_true[:] >>> metrics.adjusted_mutual_info_score(labels_true, labels_pred) # doctest: +SKIP 1.0 >>> metrics.normalized_mutual_info_score(labels_true, labels_pred) # doctest: +SKIP 1.0 对于 ``mutual_info_score`` 来说，这并不成立，因此更难以判断:: >>> metrics.mutual_info_score(labels_true, labels_pred) # doctest: +SKIP 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) # doctest: +SKIP -0.10526... .. topic:: 优点: - **随机（均匀）标签分配的 AMI 分数接近 0.0**，对于任何 ``n_clusters`` 和 ``n_samples`` 的值（这与原始互信息或 V-measure 不同）。 - **上限为 1**：接近零的值表示两个标签分配在很大程度上是独立的，而接近一的值表示显著的一致性。进一步地，AMI 正好为 1 表示两个标签分配是相等的（无论是否经过排列）。 .. topic:: 缺点: - 与惯性相反，**基于 MI 的度量需要已知真实类别**，而在实践中几乎从未可用，或者需要人工注释者手动分配（如在监督学习设置中）。 然而，基于 MI 的度量在纯粹的无监督设置中也可以作为构建共识指数的组成部分，用于聚类模型选择。 - NMI 和 MI 没有针对偶然性进行调整。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_adjusted_for_chance_measures.py` : 分析数据集大小对随机分配的聚类度量值的影响。此示例还包括调整兰德指数。 .. dropdown:: 数学表达 假设有两个相同的N个对象的标签分配，:math:`U` 和 :math:`V` 。它们的熵是一个分区集的不确定性量，定义为： .. math:: H(U) = - \sum_{i=1}^{|U|}P(i)\log(P(i)) 其中 :math:`P(i) = |U_i| / N` 是从 :math:`U` 中随机选取的对象落入类别 :math:`U_i` 的概率。同样地，对于 :math:`V` ： .. math:: H(V) = - \sum_{j=1}^{|V|}P'(j)\log(P'(j)) 其中 :math:`P'(j) = |V_j| / N` 。:math:`U` 和 :math:`V` 之间的互信息（MI）计算如下： .. math:: \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) 其中 :math:`P(i, j) = |U_i \cap V_j| / N` 是随机选取的对象同时落入类别 :math:`U_i` 和 :math:`V_j` 的概率。 它也可以用集合基数公式表示： .. math:: \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) 归一化互信息定义为 .. math:: \text{NMI}(U, V) = \frac{\text{MI}(U, V)}{\text{mean}(H(U), H(V))} 这个互信息值及其归一化变体没有针对偶然性进行调整，并且随着不同标签（簇）数量的增加，无论标签分配之间的实际“互信息”量如何，都会倾向于增加。 互信息的期望值可以通过以下方程计算 [VEB2009]_。在这个方程中，:math:`a_i = |U_i|` （:math:`U_i` 中的元素数量）和 :math:`b_j = |V_j|` （:math:`V_j` 中的元素数量）。 .. math:: 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})!} 使用期望值，调整互信息可以通过类似于调整兰德指数的形式来计算： .. math:: \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'平均值分别是几何平均和算术平均；我们使用这些更广泛通用的名称。 .. rubric:: 参考文献 * Strehl, Alexander, 和 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 `_ . * `Wikipedia关于（归一化）互信息的条目 `_ * `Wikipedia关于调整互信息的条目 `_ .. [VEB2009] Vinh, Epps, 和 Bailey, (2009). "Information theoretic measures for clusterings comparison". Proceedings of the 26th Annual International Conference on Machine Learning - ICML '09. `doi:10.1145/1553374.1553511 `_ . ISBN 9781605585161. .. [VEB2010] Vinh, Epps, 和 Bailey, (2010). "Information Theoretic Measures for Clusterings Comparison". Journal of Machine Learning Research 11: 2837-2844. for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance". JMLR .. [YAT2016] Yang, Algesheimer, and Tessone, (2016). "A comparative analysis of community detection algorithms on artificial networks". Scientific Reports 6: 30750. `doi:10.1038/srep30750 `_ . .. _homogeneity_completeness: 同质性、完整性和V-measure ------------------------- 给定样本的真实类别标签，可以使用条件熵分析定义一些直观的度量标准。 特别是Rosenberg和Hirschberg（2007）定义了以下两个任何聚类分配的理想目标： - **同质性**：每个簇仅包含单个类别的成员。 - **完整性**：给定类别的所有成员都被分配到同一个簇。 我们可以将这些概念转化为分数 :func:`homogeneity_score` 和 :func:`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**，由 :func:`v_measure_score` 计算:: >>> metrics.v_measure_score(labels_true, labels_pred) 0.51... 该函数的公式如下： .. math:: 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.2) 0.48... >>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8) 0.48... 更多的权重将被归因于完整性。 V-measure实际上等同于上述讨论的互信息（NMI），其聚合函数为算术平均值[B2011]_。 同质性、完整性和V-measure可以一次性使用 :func:`homogeneity_completeness_v_measure` 计算，如下所示:: >>> 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...) .. note:: :func:`v_measure_score` 是**对称的**：它可以用于评估同一数据集上两个独立分配的**一致性**。 对于 :func:`completeness_score` 和:func:`homogeneity_score` 则不是这样：两者都受以下关系约束:: homogeneity_score(a, b) == completeness_score(b, a) .. topic:: 优点: - **有界分数**：0.0是最差的，1.0是完美的分数。 - 直观的解释：具有不良V-measure的聚类可以根据同质性和完整性进行**定性分析**，以更好地感受分配所犯的“类型”错误。 - **不对聚类结构做任何假设**：可以用于比较聚类算法，例如假设各向同性斑点形状的k-means与可以找到具有“折叠”形状的聚类的谱聚类算法的结果。 .. topic:: 缺点: - 先前引入的指标**没有针对随机标记进行归一化**：这意味着根据样本数量、聚类和基本事实类别，完全随机的标记不会总是产生同质性、完整性和V-measure的相同值。 v-measure。特别是，**随机标签不会产生零分，尤其是在聚类数量很大时**。 当样本数量超过一千且聚类数量少于10时，这个问题可以安全地忽略。**对于较小的样本数量或较大的聚类数量，使用调整后的指数（如调整兰德指数ARI）更为安全**。 .. figure:: ../auto_examples/cluster/images/sphx_glr_plot_adjusted_for_chance_measures_001.png :target: ../auto_examples/cluster/plot_adjusted_for_chance_measures.html :align: center :scale: 100 - 这些指标**需要真实类别知识**，而在实践中几乎从未可用，或者需要人工注释者进行手动分配（如在监督学习设置中）。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_adjusted_for_chance_measures.py` : 分析数据集大小对随机分配的聚类度量值的影响。 .. dropdown:: 数学公式 同质性和完整性得分正式给出如下： .. math:: h = 1 - \frac{H(C|K)}{H(C)} .. math:: c = 1 - \frac{H(K|C)}{H(K)} 其中 :math:`H(C|K)` 是**给定聚类分配的类别的条件熵**，定义为： .. math:: 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) 而 :math:`H(C)` 是**类别的熵**，定义为： .. math:: H(C) = - \sum_{c=1}^{|C|} \frac{n_c}{n} \cdot \log\left(\frac{n_c}{n}\right) 其中 :math:`n` 是样本总数，:math:`n_c` 和 :math:`n_k` 分别是属于类别 :math:`c` 和聚类 :math:`k` 的样本数量，最后 :math:`n_{c,k}` 是属于类别 :math:`c` 被分配到聚类 :math:`k` 的样本数量。 **给定类别的聚类的条件熵** :math:`H(K|C)` 和 **簇的熵** :math:`H(K)` 以对称方式定义。 Rosenberg 和 Hirschberg 进一步定义 **V-measure** 为 **同质性和完整性的调和平均数**： .. math:: v = 2 \cdot \frac{h \cdot c}{h + c} .. rubric:: 参考文献 * `V-Measure: 一种基于条件熵的外部聚类评估指标 `_ Andrew Rosenberg 和 Julia Hirschberg, 2007 .. [B2011] `社交媒体中事件的识别与特征化 `_ , Hila Becker, 博士论文。 .. _fowlkes_mallows_scores: Fowlkes-Mallows 分数 ---------------------- 当样本的真实类别分配已知时，可以使用 Fowlkes-Mallows 指数 (:func:`sklearn.metrics.fowlkes_mallows_score` )。Fowlkes-Mallows 分数 FMI 定义为成对精确度和召回率的几何平均数： .. math:: \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] rst >>> 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 .. topic:: 优点: - **随机（均匀）标注分配的FMI分数接近0.0**，适用于任何 ``n_clusters`` 和 ``n_samples`` 的值（这与原始互信息或V-measure不同）。 - **上限为1**： 接近零的值表示两个标注分配基本独立，而接近一的值表示显著一致。进一步地，精确为0的值表示**完全**独立的标注分配，FMI精确为1表示两个标注分配相等（无论是否经过排列）。 - **不对聚类结构做假设**：可用于比较聚类算法，例如假设各向同性块状形状的k-means与能找到“折叠”形状聚类的谱聚类算法的结果。 .. topic:: 缺点: - 与惯性相反，**基于FMI的度量需要已知真实类别**，而在实践中几乎从未可用或需要人工标注者手动分配（如在监督学习设置中）。 .. dropdown:: 参考文献 * E. B. Fowkles 和 C. L. Mallows, 1983. "A method for comparing two hierarchical clusterings". Journal of the American Statistical Association. https://www.tandfonline.com/doi/abs/10.1080/01621459.1983.10478008 * `Wikipedia关于Fowlkes-Mallows指数的条目 `_ .. _silhouette_coefficient: 轮廓系数 ---------- 如果真实标签未知，评估必须使用模型本身进行。轮廓系数（:func:`sklearn.metrics.silhouette_score` ）就是这样一个评估指标，轮廓系数得分越高，表示模型具有更好的定义聚类。轮廓系数为每个样本定义，并由两个分数组成： - **a**：样本与同一类别中所有其他点之间的平均距离。 - **b**：样本与*下一个最近聚类*中所有其他点之间的平均距离。 单个样本的轮廓系数 *s* 定义如下： .. math:: 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... .. topic:: 优点： - 该分数在错误的聚类为 -1 和高度密集的聚类为 +1 之间有界。接近零的分数表示重叠的聚类。 - 当聚类密集且分离良好时，分数更高，这与聚类的标准概念相关。 .. topic:: 缺点： - 轮廓系数通常对于凸聚类比其他聚类概念（如基于密度的聚类，如通过 DBSCAN 获得的聚类）更高。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_cluster_plot_kmeans_silhouette_analysis.py` : 在这个示例中，使用轮廓分析来选择 n_clusters 的最佳值。 .. dropdown:: 参考文献 * Peter J. Rousseeuw (1987). :doi:`"Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis"<10.1016/0377-0427(87)90125-7>` . Computational and Applied Mathematics 20: 53-65. .. _calinski_harabasz_index: Calinski-Harabasz 指数 --------------------- 如果未知的真实标签，Calinski-Harabasz指数（:func:`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... .. topic:: 优点： - 当聚类密集且分离良好时，得分较高，这与聚类的标准概念相关。 - 计算速度快。 .. topic:: 缺点： - Calinski-Harabasz指数通常对于凸聚类（如通过K均值得到的聚类）比其他类型的聚类（如基于密度的聚类，如通过DBSCAN得到的聚类）更高。 .. dropdown:: 数学公式 对于大小为 :math:`n_E` 的数据集 :math:`E` ，已被聚类为 :math:`k` 个聚类，Calinski-Harabasz 分数 :math:`s` 定义为簇间离散度均值与簇内离散度的比率： .. math:: s = \frac{\mathrm{tr}(B_k)}{\mathrm{tr}(W_k)} \times \frac{n_E - k}{k - 1} 其中 :math:`\mathrm{tr}(B_k)` 是组间离散矩阵的迹， :math:`\mathrm{tr}(W_k)` 是簇内离散矩阵的迹，定义如下： .. math:: W_k = \sum_{q=1}^k \sum_{x \in C_q} (x - c_q) (x - c_q)^T .. math:: B_k = \sum_{q=1}^k n_q (c_q - c_E) (c_q - c_E)^T 其中 :math:`C_q` 是簇 :math:`q` 中的点的集合，:math:`c_q` 是簇 :math:`q` 的中心， :math:`c_E` 是 :math:`E` 的中心，:math:`n_q` 是簇 :math:`q` 中的点的数量。 .. dropdown:: 参考文献 * Caliński, T., & Harabasz, J. (1974). `"A Dendrite Method for Cluster Analysis" `_ . :doi:`Communications in Statistics-theory and Methods 3: 1-27 <10.1080/03610927408827101>` . .. _davies-bouldin_index: Davies-Bouldin 指数 -------------------- 如果未知的真实标签，可以使用 Davies-Bouldin 指数 (:func:`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... .. topic:: 优点： - Davies-Bouldin 的计算比 Silhouette 分数更简单。 - 该指数仅基于数据集固有的数量和特征，因为其计算仅使用点对点距离。 .. topic:: 缺点： - Davies-Boulding 指数通常对于凸簇比其他类型的簇（如基于密度的簇，如从 DBSCAN 获得的簇）更高。 - 使用质心距离限制了距离度量仅限于欧几里得空间。 .. dropdown:: 数学公式 该指数定义为每个簇 :math:`C_i` 对于 :math:`i=1, ..., k` 与其最相似的簇 :math:`C_j` 之间的平均相似度。在此指数的上下文中，相似度定义为一种度量 :math:`R_{ij}` ，它权衡了： - :math:`s_i` ，簇 :math:`i` 中每个点与该簇质心之间的平均距离——也称为簇直径。 - :math:`d_{ij}` ，簇质心 :math:`i` 和 :math:`j` 之间的距离。 构造 :math:`R_{ij}` 使其为非负且对称的一个简单选择是： .. math:: R_{ij} = \frac{s_i + s_j}{d_{ij}} 然后 Davies-Bouldin 指数定义为： .. math:: DB = \frac{1}{k} \sum_{i=1}^k \max_{i \neq j} R_{ij} .. dropdown:: 参考文献 * Davies, David L.; Bouldin, Donald W. (1979). :doi:`"A Cluster Separation Measure" <10.1109/TPAMI.1979.4766909>` IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224-227. * Halkidi, Maria; Batistakis, Yannis; Vazirgiannis, Michalis (2001). :doi:`"On Clustering Validation Techniques" <10.1023/A:1012801612483>` Journal of Intelligent Information Systems, 17(2-3), 107-145. * `Wikipedia 条目关于 Davies-Bouldin 指数 `_ . .. _contingency_matrix: 列联矩阵 ------------------ 列联矩阵 (:func:`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。 分类的 :ref:`混淆矩阵 ` 是一个方形的关联矩阵，其中行和列的顺序对应于一个类别列表。 .. topic:: 优点: - 允许检查每个真实簇在预测簇中的分布情况，反之亦然。 - 计算出的关联表通常用于计算两个聚类之间的相似性统计量（如本文档中列出的其他统计量）。 .. topic:: 缺点: - 关联矩阵对于少量簇易于解释，但对于大量簇则变得非常难以解释。 - 它没有提供一个单一的指标作为聚类优化的目标。 .. dropdown:: 参考文献 * `维基百科关于关联矩阵的条目 `_ .. _pair_confusion_matrix: 成对混淆矩阵 -------------- 成对混淆矩阵 (:func:`sklearn.metrics.cluster.pair_confusion_matrix` ) 是一个 2x2 的相似性矩阵 .. math:: C = \left[\begin{matrix} C_{00} & C_{01} \\ C_{10} & C_{11} \end{matrix}\right] 在通过考虑所有样本对并计算在真实和预测聚类中被分配到相同或不同簇的对数来计算的两个聚类之间。 它具有以下条目： :math:`C_{00}` : 两个聚类都没有将样本聚在一起的对数 :math:`C_{10}` : 真实标签聚类将样本聚在一起但另一个聚类没有将样本聚在一起的对数 :math:`C_{01}` : 真实标签聚类没有将样本聚在一起但另一个聚类将样本聚在一起的对数 :math:`C_{11}` : 两个聚类都将样本聚在一起的对数 考虑一个被聚在一起的样本对为正对，那么在二分类中，真阴性的计数是 :math:`C_{00}` ，假阴性是 :math:`C_{10}` ，真阳性是 :math:`C_{11}` ，假阳性是 :math:`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]]) .. dropdown:: 参考文献 * :doi:`"Comparing Partitions" <10.1007/BF01908075>` L. Hubert 和 P. Arabie, Journal of Classification 1985