Skip to content

2.3. 聚类(Clustering)

可以使用模块sklearn.cluster对未标记的数据进行聚类。

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

输入数据

需要注意的一点是，该模块中实现的算法可以将不同类型的矩阵作为输入。所有方法都接受形状为 [n_samples, n_features]的标准数据矩阵。这些可以从sklearn.feature_extraction模块的类中获取。对于仿射投影(AffinityPropagation), 谱聚类(SpectralClustering) 和 DBSCAN，还可以输入形状为[n_samples, n_samples]的相似矩阵。这些可以从sklearn.metrics.pairwise模块中的函数获得。

2.3.1. 聚类方法综述

https://scikit-learn.org/stable/_images/sphx_glr_plot_cluster_comparison_0011.png

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

方法名 参数 可扩展性(Scalability) 使用场景 几何图形（度量使用(metric used)）
K均值(K-Means) 聚类的数量(number of clusters) 很大的n_samples，中等的n_clusters， MiniBatch代码 通用的，聚类大小均匀，几何形状平坦，聚类数量不太多 点之间的距离
亲和力传播(Affinity propagation) 阻尼(damping)，样本偏好(sample preference) 无法扩展n_samples 许多聚类，聚类大小不均，几何形状不平坦 图形距离（例如最近邻图）
均值转移(Mean-shift) 带宽(bandwidth) 无法扩展n_samples 许多聚类，聚类大小不均，几何形状不平坦 点之间的距离
谱聚类(Spectral clustering) 聚类的数量(number of clusters) 中等的n_samples，小的n_clusters 聚类数量很少，聚类大小均匀，几何形状不平坦 图形距离（例如最近邻图）
Ward分层聚类(Ward hierarchical clustering) 聚类的数量或距离阈值(number of clusters or distance threshold) 大的n_samples和n_clusters 许多聚类，可能是连接限制 点之间的距离
层次聚类(Agglomerative clustering) 聚类的数量或距离阈值，链接类型，距离(number of clusters or distance threshold, linkage type, distance) 大的n_samples和n_clusters 许多聚类，可能是连通性约束，非欧几里得距离 任何成对的距离
DBSCAN 邻域大小(neighborhood size) 很大的n_samples，中等的n_clusters 非平坦几何形状，聚类大小不均 最近点之间的距离
OPTICS 最小聚类成员(minimum cluster membership) 非常大的n_samples，大的n_clusters 非平坦几何形状，不均匀的聚类大小，可变的聚类密度 点之间的距离
高斯混合(Gaussian mixtures) 许多(many) 不可扩展 平面几何形状，适合密度估计 到中心点的马氏距离(Mahalanobis distances)
Birch 分支因子，阈值，可选的全局簇。(branching factor, threshold, optional global clusterer.) 大的n_clusters和n_samples 大数据集，去除离群点，数据缩减。 点之间的欧式距离

当簇具有特定形状（即非平坦流形）且标准欧氏距离不是正确的度量方法时，非平坦几何聚类(Non-flat geometry clustering)很有用。这种情况出现在上图的两个顶行中。

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

2.3.2. K-means

KMeans算法通过尝试在$n$组等方差的样本中分离样本来对数据进行聚类，最小化称为惯量(inertia)或簇内平方和(within-cluster sum-of-squares)的标准（见下文）。此算法要求指定簇的数量。它可以很好地扩展到大量的样本，并已在许多不同领域得到广泛应用。

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

K-means算法的目标是选择使惯量(inertia)或簇内平方和(within-cluster sum-of-squares)最小化的质心： $$ \sum_{i=0}^{n}\min_{\mu_j \in C}(||x_i - \mu_j||^2) $$ 惯量(inertia)可以被认为是衡量簇与簇之间相关性的指标。它有各种缺点：

  • 惯量(inertia)假设集群是凸(convex )的并且各向同性(isotropic)，但并非总是如此。它对细长的簇或形状不规则的流形反应很差。

  • 惯量(inertia)不是一个标准化的指标：我们只知道较低的值更好，零是最佳值。但是在非常高维的空间中，欧几里德距离趋于膨胀(inflated)（这是所谓的“维数灾难”的一个例子）。在进行k-means聚类之前运行如主成分分析（PCA）等降维算法可以缓解这一问题，并加快计算速度。

https://scikit-learn.org/stable/_images/sphx_glr_plot_kmeans_assumptions_0011.png

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

https://scikit-learn.org/stable/_images/sphx_glr_plot_kmeans_digits_0011.png

K-means等价于期望最大化算法(expectation-maximization algorithm)，其协方差矩阵较小且均相等。

该算法也可以通过 Voronoi 图的概念来理解。首先利用当前质心计算点的Voronoi 图。Voronoi图中的每一段(segment)都成为一个独立的簇。其次，将质心更新为每段(segment)的平均值。然后，算法重复此操作，直到满足停止条件。通常，当迭代之间目标函数的相对减少量小于给定的公差值(tolerance value)时，算法停止。在这个实现中不是这样的：当质心的移动小于公差(tolerance)时，迭代停止。

给定足够的时间，K-means将始终收敛(converge)，但这可能是一个局部极小值。这在很大程度上取决于质心的初始化。因此，计算通常要进行多次，每次对质心进行不同的初始化。解决这个问题的一种方法是k-means++初始化方案，它已经在scikit-learn中实现（使用 init='k-means++' 参数）。如参考文献中所示，这会使将质心初始化为（通常）彼此距离较远，从而产生比随机初始化更好的结果。

该算法支持样本加权，样本权重可以由 sample_weight参数给出。这允许在计算簇中心和惯性值时为一些样本分配更多的权重。例如，为一个样本指定2的权重相当于将该样本的副本添加到数据集X。

可以给出一个允许K-means并行运行的参数，称为n_jobs。给这个参数赋予一个正值，表示使用指定数量的处理器（默认值：1）。值-1表示使用所有可用的处理器，-2表示使用所有可用处理器减一个处理器，依此类推。并行化通常以消耗内存为代价加快计算速度（在这种情况下，需要存储多个质心副本，每个作业(job)一个副本）。

警告：当numpy使用Accelerate(加速)框架时，K-Means的并行版本在OS X上被破坏。这是预期的行为：可以在fork之后调用 Accelerate ，但您需要使用Python二进制文件执行子进程（在posix下，多进程不执行此操作）。

K-means可用于矢量量化(vector quantization)。这是使用KMeans训练模型的转换方法(transform method)实现的。

示例：

参考文献：

2.3.2.1.小批量 (Mini Batch) K-Means

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

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

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

https://scikit-learn.org/stable/_images/sphx_glr_plot_mini_batch_kmeans_0011.png

示例：

参考文献：

2.3.3. 亲和力传播(Affinity Propagation)

AffinityPropagation通过在样本对之间发送消息直到收敛来创建簇(clusters)。然后使用少量的示例来描述数据集，这些示例被标识为最具代表性的其他示例。在样本对之间发送的消息表示一个样本作为另一个样本的范例样本的合适程度，合适程度值根据其他样本对的值进行迭代更新，直到收敛，完成最终聚类中心的选取，从而给出最终的聚类。

https://scikit-learn.org/stable/_images/sphx_glr_plot_affinity_propagation_0011.png

亲和力传播(Affinity Propagation)可能很有趣，因为它根据提供的数据选择簇的数量。为此，这两个重要的参数是preference （控制使用的示例数量）和 damping factor（阻尼因子，该参数阻尼责任和可用性消息，以避免在更新这些消息时出现数值振荡(numerical oscillations)）。

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

示例：

算法描述：点之间发送的消息属于两个类别之一。第一个是责任(responsibility )$r(i, k)$，是样本$k$应该是样本$i$的模范样本(exemplar)的合适程度；第二个是可用性(availability )$a(i, k)$，是样本$i$应该选择样本$k$作为模范样本的合适程度，并考虑所有其他样本选取样本$k$作为模范样本的合适程度。这样，如果样本（1）与多个样本足够相似，并且（2）该样本被多个样本选择以代表它们自己，则此样本被选为模范样本。

更正式地说，样本$k$作为样本$i$的模范样本的responsibility由以下公式进行计算： $$ r(i, k) \leftarrow s(i, k) - max [ a(i, k') + s(i, k') \forall k' \neq k] $$ 其中$s(i, k)$是样本$i$和$k$之间的相似性(similarity)。样本$k$作为样本$i$的模范样本的可用性(availability)由下式给出： $$ a(i, k) \leftarrow min [0, r(k, k) + \sum_{i'~s.t.~i' \notin \{i,k\}}{r(i', k)}] $$ 首先，$r$和$a$的所有值都设置为零，并且每次迭代的计算都会一直进行直到收敛。如上所述，为了在更新消息时避免数值振荡(numerical oscillations)，将阻尼因子(damping factor)$λ$引入迭代过程： $$ 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. 平均位移(Mean Shift)

MeanShift聚类的目的是在光滑的样本密度中发现斑点(blobs)。这是一种基于质心的算法，其工作原理是将质心的候选值更新为给定区域内点的平均值。然后，在后处理阶段对这些候选对象进行过滤，以消除近重复项(near-duplicates)，形成最终的质心集。

给定第$t$次迭代的候选质心$x_i$，根据下列方程更新候选： $$ x_i^{t+1} = m(x_i^t) $$ 其中$N(x_i)$是$x_i$附近给定距离内的样本的邻域，$m$是针对每个质心计算的“平均移动(mean shift)”矢量，而每个质心都指向点密度最大增加的区域。这是使用以下公式计算的，有效地将质心更新为其邻域内样本的平均值： $$ m(x_i) = \frac{\sum_{x_j \in N(x_i)}K(x_j - x_i)x_j}{\sum_{x_j \in N(x_i)}K(x_j - x_i)} $$ 该算法自动设置簇的数量，而不是依赖于参数bandwidth，该参数决定了要搜索的区域的大小。此参数可以手动设置，但可以使用提供的estimate_bandwidth函数进行估计，如果未设置参数bandwidth，则调用此函数。

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

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

https://scikit-learn.org/stable/_images/sphx_glr_plot_mean_shift_0011.png

示例：

参考文献：

2.3.5. 谱聚类(Spectral clustering)

SpectralClustering （谱聚类）在样本之间执行亲和力矩阵(affinity matrix)的低维嵌入，然后在低维空间中对特征向量的分量进行聚类（例如，通过KMeans）。如果亲和力矩阵是稀疏的，并且amg求解器用于特征值问题（注意，amg解算器要求安装pyamg模块），那么计算将会非常高效。

当前版本的谱聚类要求预先指定簇的数量。它在簇比较少的情况下运行良好，但在簇比较多的情况下不建议使用。

对于两个簇，谱聚类解决了相似图上归一化切割的凸松弛问题：将图一分为二，使得切割的边缘的权重比簇内边缘的权重小。当处理图像时，这个标准特别有趣，其中图形顶点是像素，并且使用图像的梯度函数计算相似度图的边的权重。

noisy_img segmented_img

警告： 将距离转化为表现良好的相似性

请注意，如果相似度矩阵的值分布不均匀，例如使用负值或使用距离矩阵而不是相似度，则谱问题将(spectral problem)是奇异的(singular)，并且该问题无法解决。在这种情况下，建议对矩阵的条目(entries)进行转换。例如，在有符号距离矩阵的情况下，应用热核(heat kernel)是常见的：

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

请参阅此类应用程序的示例。

示例：

2.3.5.1. 不同的标签分配策略(Different label assignment strategies)

可以使用不同的标签分配策略，相对应SpectralClustering的assign_labels参数。"kmeans"的策略可以匹配更精细的细节，但可能不稳定。特别是，除非您控制random_state，否则它可能无法从一次运行复现到另一次运行，因为它取决于随机初始化值。另一种"discretize" 策略是100%可复现的，但往往会产生相当均匀和几何形状的块(parcels)。

coin_kmeans coin_discretize
assign_labels="kmeans" assign_labels="discretize"

2.3.5.2. 谱聚类图(Spectral Clustering Graphs)

谱聚类(Spectral Clustering)也可以通过谱嵌入来划分图。在这种情况下，亲和矩阵(affinity matrix)是图的邻接矩阵(adjacency matrix)，谱聚类(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. 层次聚类(Hierarchical clustering)

层次聚类(Hierarchical clustering)是一类常用的聚类算法，它通过连续合并或拆分嵌套聚类(nested clusters)来构建嵌套聚类。簇的层次结构表示为树（或树状图(dendrogram)）。树根是收集所有样本的唯一簇，叶子是只有一个样本的簇。请参阅维基百科页面了解更多详细信息。

AgglomerativeClustering(聚集聚类)对象使用自底向上的方法执行分层聚类：每个观察值是一个聚类，簇被连续地合并在一起。链接标准(linkage criteria)确定用于合并策略的度量：

  • Ward最小化所有簇内的平方差之和。这是一种方差最小化(variance-minimizing)方法，在这个意义上类似于k-means目标函数，但使用聚集层次法(agglomerative hierarchical approach)进行处理。

  • Maximum或complete linkage最小化成对簇中样本间的最大距离。

  • Average linkage最小化成对簇中所有样本之间的平均距离。

  • Single linkage最小化成对簇中最近样本之间的距离。

当它与连通矩阵(connectivity matrix)一起使用时，AgglomerativeClustering(聚集聚类)也可以扩展到大量的样本，但是当样本之间不添加连通约束时，计算代价很高：它在每一步都考虑所有可能的合并。

FeatureAgglomeration(特征聚集)

FeatureAgglomeration(特征聚集)使用聚集聚类(agglomerative clustering )将看起来非常相似的特征组合在一起，从而减少特征的数量。它是一个降维工具，参见无监督降维。

2.3.6.1. Different linkage type: Ward, complete, average, and single linkage

AgglomerativeClustering(聚集聚类)支持Ward, single, average, 和 complete linkage 策略。

https://scikit-learn.org/stable/_images/sphx_glr_plot_linkage_comparison_0011.png

聚集聚类具有“富变更富(rich get richer)”的行为，导致簇大小不均匀。在这方面，single linkage 是最差的策略，而 Ward 给出了最规则的尺寸。然而，亲和力(affinity)（或聚类中使用的距离）不能随Ward而变化，因此对于非欧氏度量， average linkage是一个很好的选择。Single linkage虽然对噪声数据不鲁棒，但可以非常有效地计算，因此可以用于提供更大数据集的层次聚类。Single linkage也可以在非球形(non-globular)数据上表现良好。

示例：

2.3.6.2. 集群层次结构的可视化(Visualization of cluster hierarchy)

可以将表示簇层次合并(hierarchical merging of clusters)的树可视化为树状图(dendrogram)。可视化通常有助于理解数据的结构，在小样本情况下更是如此。

https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_dendrogram_0011.png

2.3.6.3. 添加连接约束(Adding connectivity constraints)

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

unstructured structured

这些约束有助于施加一定的局部结构，同时也使算法更快，特别是在样本数较多的情况下。

连接性约束(connectivity constraints)是通过一个连接性矩阵(connectivity matrix)施加的：一个scipy稀疏矩阵，它只在一行和一列的交集处有元素，而这些行和列记录着应该被连接的数据集的索引。这个矩阵可以由先验信息(a-priori information)构造：例如，您可能希望只合并从一个指向另一个的链接的网页来对网页进行聚类。它也可以从数据中学习，例如使用sklearn.neighbors.kneighbors_graph将合并限制为最近的邻居（如本例），或使用 sklearn.feature_extraction.image.grid_to_graph仅启用图像上相邻像素的合并（如 硬币 示例）。

示例：

警告：single, average and complete linkage的连通性约束

连接性约束和单一、完全或平均的连接可以增强聚集聚类的 ‘rich getting richer’现象，特别是在它们用 sklearn.neighbors.kneighbors_graph构建时。在少数簇的限制下，它们倾向于给出一些宏观上占据的簇(occupied clusters)和几乎为空的簇(empty clusters)。（见有无结构的聚集聚类中的讨论）。在这个问题上，Single linkage是最脆弱的 linkage 选择。

https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_0011.png https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_0021.png https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_0031.png https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_0041.png

2.3.6.4. 改变度量(Varying the metric)

Single, average 和 complete linkage可以与各种距离（或仿射(affinities)）一起使用，特别是欧几里德距离（l2）、曼哈顿距离（或Cityblock或 l1）、余弦距离或任何预先计算的仿射矩阵(affinity matrix)。

  • l1 距离通常有利于稀疏特征或稀疏噪声：即许多特征为零，就如在文本挖掘中使用稀有词(rare words)一样。

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

选择度量的准则是使用一个最大化不同类中样本之间的距离，并最小化每个类中样本之间的距离。

https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_metrics_0051.png https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_metrics_0061.png https://scikit-learn.org/stable/_images/sphx_glr_plot_agglomerative_clustering_metrics_0071.png

示例：

2.3.7. DBSCAN

DBSCAN 算法将簇视为被低密度区域分隔的高密度区域。由于这个相当普遍的观点，DBSCAN发现的集群可以是任何形状，而k-means假设集群是凸形的(convex shaped)。DBSCAN的核心部分是核心样本 的概念，核心样本位于高密度区域。因此，一个簇是一组核心样本，每个样本彼此靠近（通过某种距离度量方法进行测量）和一组靠近核心样本（但本身不是核心样本）的非核心样本。该算法有两个参数，min_samples 和 eps，它们正式定义了稠密 的含义。较大的 min_samples 或较小的 eps表示形成簇所需的较高密度。

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

根据定义，任何核心样本都是簇的一部分。该算法将非核心样本，且与核心样本的距离至少为 eps的样本视为离群值(outlier)。

虽然参数min_samples主要控制算法对噪声的容忍程度（在有噪声和较大数据集上，可能需要增加此参数），但参数min_samples对于数据集和距离函数的适当选择至关重要，并且通常不能保留默认值。它控制点的局部邻域。当选择的值太小时，大多数数据根本不会被聚类（并标记为-1表示“噪声”）。当选择的值太大时，它会导致相近的聚类合并到一个簇中，并最终将整个数据集作为单个簇返回。文献中已经讨论了一些选择该参数的启发式(heuristics)方法，例如基于最近邻距离图中的knee（如下面的参考文献中所讨论）。

在下图中，颜色表示簇成员属性，大圆圈表示算法找到的核心样本。较小的圆是仍然是簇的一部分的非核心样本。此外，离群值(outliers)用下面的黑点表示。

dbscan_results

示例：

实现

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

This implementation is by default not memory efficient because it constructs a full pairwise similarity matrix in the case where kd-trees or ball-trees cannot be used (e.g., with sparse matrices). This matrix will consume n^2 floats. A couple of mechanisms for getting around this are:

当前的实现使用 ball-trees 和 kd-trees 来确定点的邻域，这避免了计算全距离矩阵(full distance matrix)（如0.14之前的scikit-learn版本中所实现的）。保留使用自定义度量(custom metrics)的可能性；有关详细信息，请参阅NearestNeighbors。

大样本的内存消耗

默认情况下，此实现是在无法使用 ball-trees 或 kd-trees （例如，使用稀疏矩阵）的情况下构造完整的成对相似矩阵(full pairwise similarity matrix)，因此，该实现内存利用率低。这个矩阵将消耗n^2个浮点数。解决这一问题的两种机制是：

  • 将 OPTICS 聚类与 extract_dbscan 方法结合使用。OPTICS聚类还计算完整的成对矩阵(pairwise matrix)，但一次只在内存中保留一行（内存复杂性n）。

  • 稀疏半径邻域图（其中丢失的条目被认为是eps之外的）可以以节省内存的方式进行预编译(precomputed)，可以使用metric='precomputed'运行dbscan。请参见sklearn.neighbors.NearestNeighbors.radius_neighbors_graph。

  • 数据集可以压缩，方法删除数据中出现的完全重复的数据，或者使用BIRCH。然后你只用相对少量的样本代表大量的点。您可以在拟合 DBSCAN 时提供 sample_weight参数。

参考文献：

  • “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
  • “DBSCAN revisited, revisited: why and how you should (still) use 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. OPTICS

OPTICS算法与 DBSCAN 算法有许多相似之处，可以认为是DBSCAN的一个推广，DBSCAN 将eps需求从单个值放宽到一个值范围。DBSCAN与OPTICS的关键区别在于，OPTICS算法建立了一个可达(reachability)图，该图为每个样本分配了一个reachability_距离和一个簇 ordering_ 属性内的点；这两个属性是在模型拟合时分配的，用于确定簇成员。如果OPTICS运行时的默认值为 inf 设置为max_eps，则可以使用cluster_optics_dbscan 方法在线性时间内对任何给定的 eps 值重复执行DBSCAN类型的簇提取。将 max_eps 设置为较低的值将导致较短的运行时间，并且可以认为是从每个点距离其他潜在可达点的最大邻域半径(maximum neighborhood radius)。

optics_results

OPTICS 产生的可达(reachability)距离允许在单个数据集中对簇进行可变密度提取。如上图所示，结合可达距离和数据集ordering_ 属性，生成可达性图，其中点密度表示在Y轴上，并按顺序排列点，以使附近的点相邻。在单个值上“切割”可达图会产生类似DBSCAN的结果；“切割”上方的所有点都被归类为噪声，每次从左到右读取时出现中断都表示新的簇。默认使用OPTICS的簇提取会查看图中的陡坡(steep slopes)来查找簇，用户可以使用参数xi定义什么是陡坡。对图本身的分析也有其他的可能性，例如通过可达图树状图生成数据的层次表示，并且该算法检测到的簇的层次可以通过 cluster_hierarchy_ 参数来访问。上面的图已经进行了颜色编码(color-coded)，使得平面空间中(planar space)的簇颜色与可达图的线性段簇(linear segment clusters)相匹配。请注意，蓝色和红色簇在可达图中相邻，并且可以分层表示为较大父簇的子簇。

示例：

与DBSCAN比较：

OPTICS的 cluster_optics_dbscan方法和DBSCAN 的结果非常相似，但并不总是完全相同，具体地说，是在标记离群点和噪声点(periphery and noise points)方面。这部分是因为OPTICS 处理的每个密集区域的第一个样本在接近其区域中的其他点时具有很大的可达值，因此有时会标记为噪声点而不是离群点(periphery)。当相邻点被视为可标记为离群点(periphery)或噪声点的候选点时，这会影响相邻点。

注意，对于eps的任何单个值，DBSCAN 的运行时间往往比 OPTICS 短；但是，在不同eps值下重复运行，单个OPTICS运行所需的累计运行时间可能比DBSCAN少。还需要注意的是，只有当 eps 和 max_eps 接近时，OPTICS的输出才接近DBSCAN。

计算复杂度：

空间索引树(Spatial indexing trees)用于避免计算全距离矩阵(full distance matrix)，并允许在大样本集上高效使用内存。可以通过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.9. Birch

Birch为给定的数据构建了一种名为聚类特征树（Clustering Feature Tree，简称CFT）的树。数据本质上是有损压缩到一组聚类特征节点（Clustering Feature nodes，即CF Nodes）。CF Nodes 有许聚类特征子簇（Clustering Feature subclusters，即CF subclusters），这些位于非终端CF Nodes中的CF subclusters可以将CF Nodes作为子结点。

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

  • 子簇中的样本数。

  • 线性和-包含所有样本总和的n维向量

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

  • 质心-避免重新计算线性和（或n_samples）。

  • 质心的平方范数。

Birch算法有两个参数：阈值(threshold )和分支因子(branching factor)。分支因子限制节点中的子簇数量，阈值限制输入样本与现有子簇之间的距离。

该算法可以看作是一种实例或数据简化方法，因为它将输入数据简化为一组直接从CFT的叶子中获得的子簇。这样减少的数据可以通过将其输入全局聚类簇(global clusterer)来进一步处理。这个全局聚类器可以通过n_clusters参数来设置。如果将n_clusters设置为None，则直接读取叶中的子簇，否则全局聚类步骤会将这些子簇标记为全局簇（标签），并将样本映射到最近子簇的全局标签。

算法描述:

  • 一个新的样本被插入到作为CF节点(CF Node)的CF树(CF Tree)的根中。然后将其与根的子簇合并，该子簇在合并后具有最小的半径，并受阈值和分支因子(hreshold and branching factor)条件的约束。如果子集群有任何子节点，则重复此操作，直到它到达叶。在叶中找到最近的子簇后，递归更新此子簇和父子簇的属性。

  • 如果通过合并新样本和最近的子簇而获得的子簇的半径大于阈值的平方，并且如果子簇的数量大于分支因子，则临时为该新样本分配空间。取两个最远的子簇，根据这些子簇之间的距离将子簇分为两组。

  • 如果此分割节点有父子簇(parent subcluster)，并且有空间容纳新的子簇，则父簇被分割为两个。如果没有空间，则该节点再次被分成两个，并递归地继续该过程，直到到达根节点。

Birch 还是 MiniBatchKMeans?

  • Birch不能很好地适应高维数据。根据经验，如果 n_features 大于20，通常最好使用MiniBatchKMeans。
  • 如果需要减少数据实例的数量，或者需要大量子簇作为预处理步骤或其他步骤，那么Birch比MiniBatchKMeans更有用。

如何使用 partial_fit?

为了避免全局聚类(global clustering)的计算，建议用户每次调用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()，它执行全局聚类。

https://scikit-learn.org/stable/_images/sphx_glr_plot_birch_vs_minibatchkmeans_0011.png

参考文献：

  • 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 - Java implementation of BIRCH clustering algorithm https://code.google.com/archive/p/jbirch

2.3.10. 聚类算法性能评估

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

2.3.10.1. Adjusted Rand index

真实类分配(ground truth class assignments)：labels_true 和我们的聚类算法对同样的样本集预测出的类分配：labels_pred，adjusted Rand index是一个用来度量上述两种分配的相似度(similarity)的函数，而忽略排列并有机会归一化：

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

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

可以在预测的标签中排列(permute)0和1，将2改为3，得到相同的分数：

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

此外，adjusted_rand_score是对称的：交换参数不会更改得分。因此，它可以作为共识度量(consensus measure)：

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

完美标签得分为1.0：

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

坏的标签（例如独立标签）具有负值或接近0.0的得分：

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

2.3.10.1.1. 优点

  • 随机(均匀)标签分配的 ARI 得分接近于0.0对于n_clusters和n_samples的任何值（这不是未经过调整的Rand index或者V-measure的情况）。
  • 得分被界定在[-1, 1]的区间内：负值是坏的（独立性标签），相似的聚类有一个正的 ARI，1.0是完美的匹配得分。
  • 没有对聚类的结构做任何假定：可以用于比较聚类算法，比如假定了各向同性的“blob”形状的k-means方法的结果和寻找具有“folded”形状的谱聚类方法的结果进行比较。

2.3.10.1.2. 缺点

  • 与惯性(inertia)方法不同，ARI 需要真实类(ground truth classes)的相关知识，而在实践中几乎不可得到，或者需要人工手动分配（如在监督学习环境中）。

然而，ARI还可以在纯粹无监督的设置中作为可用于聚类模型选择的共识索引的构建模块。

示例：

2.3.10.1.3. 数学公式

如果C是真实类分配，而K是聚类，让我们定义$a$和$b$如下：

  • $a$，在C中相同集合和在K中相同集合的元素对的数量
  • $b$，在C中不同集合和在K中不同集合的元素对的数量

原始（未调整的）Rand index如下： $$ \text{RI} = \frac{a + b}{C_2^{n_{samples}}} $$ 其中$C_2^{n_{samples}}$是在(未排序的)数据集中所有可能的元素对的总数量。

然而，RI评分不能保证随机标签分配将获得接近零的值（特别是如果聚类的数量与样本数量有相同的数量级）。

为了抵消这种影响，我们可以通过定义调整后的Rand index(adjusted Rand index，即ARI)来对随机标签分配的期望RI$E[\text{RI}]$进行削减(discount)，如下所示：

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

2.3.10.2. 基于互信息的得分

给定真实类的分配：labels_true和我们的聚类算法对同样的样本集预测出的类分配：labels_pred，互信息(Mutual Information)是一个函数，用于度量两个分配集合的一致性，忽略了排列组合。目前可以用这种度量方法的两个不同的归一化版本：规范化互信息(Normalized Mutual Information)（NMI）和调整后的互信息(Adjusted Mutual Information)（AMI）。NMI在文献中可以经常看到，并且针对偶然性进行了标准化：

>>> 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都是对称的：交换函数的参数不会改变得分。因此，它们可以用作共识度量(consensus measure)：

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

完美标签分配(Perfect labeling)的得分是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...

2.3.10.2.1. 优点

  • 随机(均匀)标签分配有一个接近于0的AMI得分。对于n_clusters和n_samples的任何值（这不是未经过调整的 互信息(Mutual Information)或者V-measure的情况）。
  • 上界为1：得分值接近于0表明两个标签分配集合很大程度上是独立的，而得分值接近于1表明两个标签分配集合具有很大的一致性。更进一步，正好是1的AMI表示两个标签分配相等。（带有或不带有排列）。

2.3.10.2.2. 缺点

  • 与惯性(inertia)方法不同, 基于互信息的度量(MI-based measures)需要真实类的相关知识 而在实践中几乎不可得到，或者需要人工手动分配（如在监督学习环境中）。

然而，基于互信息的度量还可以在纯粹无监督的设置中作为可用于聚类模型选择的共识索引的构建模块。

  • NMI和MI不会随便调整。

示例：

2.3.10.2.3. 数学公式

假定我们有两个标签分配集合(具有相同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(i, j) = |U_i \cap V_j| / N$。$U$和$V$之间的互信息的计算公式如下：

$$ \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$中的概率。

互信息还可以用集合基数(set cardinality)的形式来表示： $$ \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})!} $$ 使用了互信息期望值后，经过调整的互信息的计算将使用与ARI(adjusted Rand index)类似的形式进行 :

$$ \text{AMI} = \frac{\text{MI} - E[\text{MI}]}{\text{mean}(H(U), H(V)) - E[\text{MI}]} $$ 对于归一化互信息和调整后的互信息，归一化值通常是每个聚类的熵的某个广义均值。有各种广义均值存在，并没有明确的规则说某一个优先于其他的。这个决定很大程度上是取决于各个领域的基础；例如，在社区检测中，算术平均值是最常见的。每一种归一化方法提供“定性相似的行为(qualitatively similar behaviours)” [YAT2016]。在我们的实现中，由 average_method参数控制。

Vinh et al. (2010)对各种NMI和AMI的变体用它们使用的平均方法进行了命名[VEB2010]。他们在论文里说的‘sqrt’和‘sum’ 平均分别是几何和算数平均；我们使用这些更广泛的通用名称。

参考文献

2.3.10.3. 同质性(Homogeneity)，完备性(completeness)和 V-度量(V-measure)

给定样本的真实类分配的相关知识, 则使用条件熵分析来定义某个直观的指标(metric)是可能的。

特别地，Rosenberg和Hirschberg(2007)为任意聚类分配定义了以下两个理想的目标：

  • 同质性(Homogeneity)：每个聚类里面只包含单个类的样本。
  • 完备性(completeness)：一个给定类的所有样本都被分到了同一个聚类中。

我们可以将上述概念转化为homogeneity_score和completeness_score函数。这两个函数的返回值都是介于0到1之间（返回值越高越好）：

>>> 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)，通过函数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，但可以给beta传入小于1的值：

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

更多权重将归因于同质性，并且给beta传入大于1的值：

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

更多权重将归因于完备性。

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

同质性，完备性和V-度量可使用以下方法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...)

注意：v_measure_score是对称的：可用于评估同一数据集上两个独立分配(independent assignments)的一致性。completeness_score和homogeneity_score 的情况并非如此：两者都受以下关系约束：

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

2.3.10.3.1. 优点

  • 有界得分：0.0代表最坏的情况，1.0是最完美的得分。
  • 直观可解释性：具有坏的V-度量值的聚类可以从同质性和完备性角度进行定性分析(qualitatively analyzed in terms of homogeneity and completeness)来更好的感受到聚类算法预测标签分配的时候犯了哪种错误。
  • 对聚类结构没有做任何假定：可以用于比较聚类算法，比如假定了各向同性的blob 形状的k-means方法的结果和寻找具有“folded”形状的谱聚类方法的结果进行比较。

2.3.10.3.2. 缺点

  • 以前引入的度量指标并没有对随机标记进行标准化 ：这意味着，依赖于样本数量、聚类的数量和真实类的数量，一个完全的随机标记对于同质性、完备性和v-度量来说并不总是产生相同的值。特别是，随机标记不会产生零得分，尤其是当簇数很大时。

当样本数大于1000个，聚类的数量小于10个时，可以安全地忽略这个问题。对于较小的样本大小或较多的聚类数量，使用调整后的索引比如Adjusted Rand Index(ARI)更安全。

../_images/sphx_glr_plot_adjusted_for_chance_measures_0011.png

  • 这些度量指标需要真实类的相关知识，而这些相关知识在实践中几乎不可得到，或者需要人工手动分配（如在监督学习环境中）。

示例：

2.3.10.3.3. 数学公式

同质性和完备性由以下形式正式给出：

$$ 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} $$ 参考文献

2.3.10.4. Fowlkes-Mallows 得分

当已知样本的真实类分配时，可以使用Fowlkes-Mallows索引（sklearn.metrics.fowlkes_mallows_score）。Fowlkes-Mallows得分FMI，定义为成对精度(pairwise precision)和成对召回率(pairwise recall)的几何平均值：

$$ \text{FMI} = \frac{\text{TP}}{\sqrt{(\text{TP} + \text{FP}) (\text{TP} + \text{FN})}} $$ 其中TP是True Positive的数量（例如，在真实标签集中和预测标签集中属于相同聚类的点对的数量），FP 是False Positive的数量（例如，在真实标签集中但不在预测标签集中属于相同聚类的点对的数量），FN是False Negative的数量（例如，不在真实标签集中但在预测标签集中属于相同簇的点对的数量）。

FMI得分取值范围在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

坏的标记（例如，独立标签）的得分是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.10.4.1. 优点

  • 随机(均匀)标签分配有一个接近于0的FMI得分。对于n_clusters 和 n_samples 的任何值（这不是未处理的互信息(raw Mutual Information)或者V-度量的情况）。
  • 上界为1：得分值接近于0，表明两个标签分配集合很大程度上是独立的，而得分值接近于1，表明两个标签分配集合 具有很大的一致性。更进一步，正好是0的FMI表示两个标签分配纯粹独立，正好是1的FMI表示两个标签分配相等。（带有或不带有排列）。
  • 对聚类结构没有做任何限制：可以用于比较聚类算法，比如假定了各向同性的blob形状的k-means方法的结果和寻找具有“folded”形状的谱聚类方法的结果进行比较。

2.3.10.4.2. 缺点

  • 与惯性方法不同，基于FMI度量需要真实类的相关知识，而这些知识在实践中几乎不可得到，或者需要人工手动分配（如在监督学习环境中）。

参考文献

  • E. B. Fowkles and C. L. Mallows, 1983. “A method for comparing two hierarchical clusterings”. Journal of the American Statistical Association. http://wildfire.stat.ucla.edu/pdflibrary/fowlkes.pdf
  • Wikipedia entry for the Fowlkes-Mallows Index

2.3.10.5. 轮廓系数(Silhouette Coefficient)

如果不知道真实标签，则必须使用模型本身进行评估。轮廓系数（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...

参考文献

  • Peter J. Rousseeuw (1987). “Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis”. Computational and Applied Mathematics 20: 53–65. doi:10.1016/0377-0427(87)90125-7.

2.3.10.5.1. 优点

  • 对于高度稠密的聚类，得分被限制在-1和+1之间。得分在0附近表明是有重叠的聚类。
  • 当聚类(cluster)密集且分离良好时，得分较高，这与聚类(cluster)的标准概念有关。

2.3.10.5.2. 缺点

  • 凸形聚类(cluster)的轮廓系数通常比其他聚类(cluster)高，例如，通过DBSCAN获得的基于密度的聚类(cluster)。

示例：

2.3.10.6. Calinski-Harabasz 指数

如果不知道基本真值标签，则可以使用Calinski-Harabasz指数(sklearn.metrics.calinski_harabasz_score)来评估模型，其中较高的Calinski-Harabasz分数与具有更好定义的簇的模型相关。

此指数(index)是所有簇的簇间色散(between-clusters dispersion)和簇内色散(inter-cluster dispersion)之和的比率（其中色散(dispersion)定义为距离的平方和）：

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

2.3.10.6.1. 优点

  • 当集群密集且分离较好时，得分更高，这与簇的标准概念有关。
  • 得分计算速度快。

2.3.10.6.2. 缺点

  • 凸簇(convex clusters)的Calinski-Harabasz指数通常高于其它类型的簇，例如通过DBSCAN获得的基于密度的簇。

2.3.10.6.3. 数学公式

对于大小为$n_E$的数据集$E$聚类成$k$个簇，Calinski-Harabasz得分$s$被定义为簇间色散平均值(between-clusters dispersion mean)与簇内分散( within-cluster dispersion)的比率： $$ 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.10.7. Davies-Bouldin 指数

如果不知道真值标签，可以使用Davies-Bouldin 指数(sklearn.metrics.davies_bouldin_score) 来评估模型，其中较低的Davies-Bouldin index与聚类之间分离较好的模型相关。

此指数(index)表示集群之间的平均“相似性”，其中相似性是比较集群之间的距离和集群本身大小的度量。

零是可能的最低分。接近零的值表示更好的分区。

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

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

2.3.10.7.1. 优点

  • Davies Bouldin的计算比轮廓分数(Silhouette scores)的计算简单。

  • index 仅计算数据集内的数量和特征。

2.3.10.7.2. 缺点

  • 对于凸簇(convex clusters)，Davies-Boulding 指数通常高于其他类型的簇，例如从DBSCAN获得的基于密度的簇。

  • 质心距离只能使用欧几里德空间的距离度量。

2.3.10.7.3. 数学公式

index 定义为每个聚类$C_i$与其最相似的一个聚类$C_j$之间的平均相似性(average similarity)，其中$i=1, ..., k$。在这个index定义下，相似性(similarity)被定义为一种衡量$R_{ij}$，它权衡：

  • $s_i$，簇$i$的每个点与簇的质心之间的平均距离，也称为簇直径(cluster diameter)。

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

构造$R_ij$使其非负且对称的一个简单选择是： $$ R_{ij} = \frac{s_i + s_j}{d_{ij}} $$ 然后，Davies-Bouldin index定义为： $$ DB = \frac{1}{k} \sum_{i=1}^k \max_{i \neq j} R_{ij} $$

参考文献：

2.3.10.8. 列联矩阵(Contingency Matrix)

列联矩阵（sklearn.metrics.cluster.contingency_matrix）报告每个真实/预测的簇对的交集基数(intersection cardinality)。列联矩阵为所有的聚类度量(clustering metrics)提供了足够的统计信息，其中样本是独立的、相同分布的，并且不需要考虑一些没有被聚类的实例。

下面是一个例子：

>>> 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”。其中，两个在预测簇(predicted cluster) 0中，一个在1中，没有一个在2中。第二行表示有三个样本的真实簇为“b”。其中，没有一个在预测的集群0中，一个在1中，两个在2中。

分类的混淆矩阵(confusion matrix)是一个平方列联矩阵，其中行和列的顺序对应于类的列表。

2.3.10.8.1. 优点

  • 允许检查每个真实簇在预测簇之间的传播，反之亦然。
  • 计算出的列联表通常用于计算两个簇之间的相似性统计（如本文档中列出的其他统计方式）

2.3.10.8.2. 缺点

  • 列联矩阵对于小数量的簇易于解释，但对于大数量的簇则变得非常难以解释。
  • 它没有给出一个指标作为聚类优化的目标。

参考文献：

© 2007 - 2019, scikit-learn 开发人员 (BSD 许可证). 此页显示源码