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. 聚类方法综述

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

当簇具有特定形状（即非平坦流形）且标准欧氏距离不是正确的度量方法时，非平坦几何聚类(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）等降维算法可以缓解这一问题，并加快计算速度。

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

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)实现的。

示例：

• k-均值假设的演示: 演示k-均值何时直观地执行，何时不执行
• 在手写数字数据集上进行K-Means聚类的演示: 对手写数字进行聚类

参考文献：

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

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

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

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

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

示例：

• 比较K-Means和MiniBatchKMeans聚类算法: 比较KMeans和MiniBatchKMeans
• 使用k-means对文本文档进行聚类: 使用稀疏MiniBatchKMeans对文档进行聚类
• 在线学习面部表情字典

参考文献：

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

2.3.3. 亲和力传播(Affinity Propagation)

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

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

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

示例：

• 亲和力传播聚类算法演示: 3类合成二维数据集上的亲和力传播。
• 在金融时间序列上可视化股市结构 和力传播，以发现公司群(groups of companies)。

算法描述：点之间发送的消息属于两个类别之一。第一个是责任(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，则调用此函数。

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

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

示例：

• mean-shift聚类算法演示：3类合成2D数据集上的 Mean Shift 聚类。

参考文献：

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

2.3.5. 谱聚类(Spectral clustering)

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

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

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

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

请注意，如果相似度矩阵的值分布不均匀，例如使用负值或使用距离矩阵而不是相似度，则谱问题将(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)。

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)  

参考文献：

• “A Tutorial on Spectral Clustering” Ulrike von Luxburg, 2007
• “Normalized cuts and image segmentation” Jianbo Shi, Jitendra Malik, 2000
• “A Random Walks View of Spectral Segmentation” Marina Meila, Jianbo Shi, 2001
• “On Spectral Clustering: Analysis and an algorithm” Andrew Y. Ng, Michael I. Jordan, Yair Weiss, 2001
• “Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge” David Zhuzhunashvili, Andrew Knyazev

2.3.6. 层次聚类(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 策略。

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

示例：

• 二维数字嵌入上的各种聚集聚类：在真实数据集中探索不同的 linkage 策略。

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

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

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

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

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

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

示例：

• 在硬币图像上的结构化Ward分层聚类演示：Ward聚类用于在区域中分割硬币图像。

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

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

• 有无结构的聚集聚类

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

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

2.3.6.4. 改变度量(Varying the metric)

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

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

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

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

示例：

• 使用不同指标的聚集聚类

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聚类算法演示

实现

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

示例：

• OPTICS 聚类算法演示

与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()，它执行全局聚类。

参考文献：

• 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)来对随机标签分配的期望RIE[\text{RI}]进行削减(discount)，如下所示：

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

• Comparing Partitions L. Hubert and P. Arabie, Journal of Classification 1985
• Wikipedia entry for the adjusted Rand index

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不会随便调整。

示例：

• 聚类算法性能评估中的机会调整：分析数据集大小对随机分配的聚类度量值的影响。此示例还包括Adjusted Rand Index。

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’ 平均分别是几何和算数平均；我们使用这些更广泛的通用名称。

参考文献

• Strehl, Alexander, and Joydeep Ghosh (2002). “Cluster ensembles – a knowledge reuse framework for combining multiple partitions”. Journal of Machine Learning Research 3: 583–617. doi:10.1162/153244303321897735.
• Wikipedia entry for the (normalized) Mutual Information
• Wikipedia entry for the Adjusted Mutual Information

• [VEB2009] Vinh, Epps, and 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, and Bailey, (2010). “Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance”. JMLR http://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf

• [YAT2016] Yang, Algesheimer, and Tessone, (2016). “A comparative analysis of community detection algorithms on artificial networks”. Scientific Reports 6: 30750. doi:10.1038/srep30750.

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)更安全。

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

示例：

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

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

• V-Measure: A conditional entropy-based external cluster evaluation measure Andrew Rosenberg and Julia Hirschberg, 2007

• [B2011] Identication and Characterization of Events in Social Media, Hila Becker, PhD Thesis.

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

示例：

• 在KMeans聚类上使用轮廓分析选择聚类数目：在本示例中，轮廓分析用于为n_clusters选择最佳值。

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中点的数量。

参考文献：

• Caliński, T., & Harabasz, J. (1974). “A Dendrite Method for Cluster Analysis”. Communications in Statistics-theory and Methods 3: 1-27. doi:10.1080/03610927408827101.

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}

参考文献：

• Davies, David L.; Bouldin, Donald W. (1979). “A Cluster Separation Measure” IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224-227. doi:10.1109/TPAMI.1979.4766909.
• Halkidi, Maria; Batistakis, Yannis; Vazirgiannis, Michalis (2001). “On Clustering Validation Techniques” Journal of Intelligent Information Systems, 17(2-3), 107-145. doi:10.1023/A:1012801612483.
• Wikipedia entry for Davies-Bouldin index.

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

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

参考文献：

• Wikipedia entry for contingency matrix

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

未经允许不得转载：PythonOK » 2.3. 聚类(Clustering)