【Scikit-Learn 中文文档】聚类 - 无监督学习 - 用户指南 | ApacheCN

2018-01-15 15:09:38 浏览数 (1)

2.3. 聚类

未标记的数据的 Clustering（聚类） 可以使用模块 sklearn.cluster 来实现。

每个 clustering algorithm （聚类算法）有两个变体: 一个是 class, 它实现了 fit 方法来学习 train data（训练数据）的 clusters（聚类），还有一个 function（函数），是给定 train data（训练数据），返回与不同 clusters（聚类）对应的整数标签 array（数组）。对于 class（类），training data（训练数据）上的标签可以在 labels_ 属性中找到。

输入数据

需要注意的一点是，该模块中实现的算法可以采用不同种类的 matrix （矩阵）作为输入。所有这些都接受 shape [n_samples, n_features] 的标准数据矩阵。 这些可以从以下的 sklearn.feature_extraction 模块的 classes （类）中获得。对于 AffinityPropagation, SpectralClustering 和 DBSCAN 也可以输入 shape [n_samples, n_samples]的相似矩阵。这些可以从 sklearn.metrics.pairwise 模块中的函数获得。

2.3.1. 聚类方法概述

在 scikit-learn 中的 clustering algorithms （聚类算法）的比较在 scikit-learn 中的 clustering algorithms （聚类算法）的比较

当 clusters （簇）具有 specific shape （特殊的形状），即 non-flat manifold（非平面 manifold），并且标准欧几里得距离不是正确的 metric （度量标准）时，Non-flat geometry clustering （非平面几何聚类）是非常有用的。这种情况出现在上图的两个顶行中。

用于 clustering （聚类）的 Gaussian mixture models （高斯混合模型），专用于 mixture models （混合模型）描述在 文档的另一章节 。可以将 KMeans 视为具有 equal covariance per component （每个分量相等协方差）的 Gaussian mixture model （高斯混合模型）的特殊情况。

2.3.2. K-means

KMeans 算法通过试图分离 n groups of equal variance（n 个相等方差组）的样本来聚集数据，minimizing （最小化）称为 inertia 或者 within-cluster sum-of-squares （簇内和平方）的 criterion （标准）。 该算法需要指定 number of clusters （簇的数量）。它可以很好地 scales （扩展）到 large number of samples（大量样本），并已经被广泛应用于许多不同领域的应用领域。

Inertia（惯性）, 或 the within-cluster sum of squares（簇内和平方差） criterion（标准）,可以被认为是 internally coherent clusters （内部想干聚类）的 measure （度量）。 它有各种缺点:

  • Inertia（惯性）假设 clusters （簇）是 convex（凸）的和 isotropic （各项同性），这并不是总是这样。它对 elongated clusters （细长的簇）或具有不规则形状的 manifolds 反应不佳。
  • Inertia（惯性）不是一个 normalized metric（归一化度量）: 我们只知道 lower values （较低的值）是更好的，并且 零 是最优的。但是在 very high-dimensional spaces （非常高维的空间）中，欧几里得距离往往会变得 inflated （膨胀）（这就是所谓的 “curse of dimensionality （维度诅咒/维度惩罚）”）。在 k-means 聚类之前运行诸如 PCA 之类的 dimensionality reduction algorithm （降维算法）可以减轻这个问题并加快计算速度。

示例:

  • Demonstration of k-means assumptions: 演示 k-means 是否 performs intuitively （直观执行），何时不执行
  • A demo of K-Means clustering on the handwritten digits data: 聚类手写数字

参考:

  • “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. 小批量 K-Means

MiniBatchKMeans 是 KMeans 算法的一个变体，它使用 mini-batches （小批量）来减少计算时间，同时仍然尝试优化相同的 objective function （目标函数）。 Mini-batches（小批量）是输入数据的子集，在每次 training iteration （训练迭代）中 randomly sampled （随机抽样）。这些小批量大大减少了融合到本地解决方案所需的计算量。 与其他降低 k-means 收敛时间的算法相反，mini-batch k-means 产生的结果通常只比标准算法略差。

MiniBatchKMeans 收敛速度比 KMeans ，但是结果的质量会降低。在实践中，质量差异可能相当小，如示例和引用的参考。

示例:

  • Comparison of the K-Means and MiniBatchKMeans clustering algorithms: KMeans 与 MiniBatchKMeans 的比较
  • Clustering text documents using k-means: 使用 sparse MiniBatchKMeans （稀疏 MiniBatchKMeans）的文档聚类
  • Online learning of a dictionary of parts of faces

参考:

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

2.3.3. Affinity Propagation

AffinityPropagation AP聚类是通过在样本对之间发送消息直到收敛来创建聚类。然后使用少量示例样本作为聚类中心来描述数据集， 聚类中心是数据集中最能代表一类数据的样本。在样本对之间发送的消息表示一个样本作为另一个样本的示例样本的 适合程度，适合程度值在根据通信的反馈不断更新。更新迭代直到收敛，完成聚类中心的选取，因此也给出了最终聚类。

Affinity Propagation 算法比较有趣的是可以根据提供的数据决定聚类的数目。 因此有两个比较重要的参数 preference, 决定使用多少个示例样本 *damping factor*（阻尼因子） 减少吸引信息和归属信息以防止 更新减少吸引度和归属度信息时数据振荡。

2.3.4. Mean Shift

示例:

  • A demo of the mean-shift clustering algorithm: Mean Shift clustering on a synthetic 2D datasets with 3 classes.

参考:

  • “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 是在样本之间进行亲和力矩阵的低维度嵌入，其实是低维空间中的 KMeans。 如果亲和度矩阵稀疏，则这是非常有效的并且 pyamg module 以及安装好。 SpectralClustering 需要指定聚类数。这个算法适用于聚类数少时，在聚类数多是不建议使用。

对于两个聚类，它解决了相似图上的 normalised cuts 问题: 将图形切割成两个，使得切割的边缘的重量比每个簇内的边缘的权重小。在图像处理时，这个标准是特别有趣的: 图像的顶点是像素，相似图的边缘是图像的渐变函数。

Warning

Transforming distance to well-behaved similarities

请注意，如果你的相似矩阵的值分布不均匀，例如:存在负值或者距离矩阵并不表示相似性 spectral problem 将会变得奇异，并且不能解决。 在这种情况下，建议对矩阵的 entries 进行转换。比如在符号距离有符号的情况下通常使用 heat kernel:

代码语言：javascript复制
similarity = np.exp(-beta * distance / distance.std())

请看这样一个应用程序的例子。

示例:

  • Spectral clustering for image segmentation: Segmenting objects from a noisy background using spectral clustering.
  • Segmenting the picture of a raccoon face in regions: Spectral clustering to split the image of the raccoon face in regions.

2.3.5.1. 不同的标记分配策略

可以使用不同的分配策略, 对应于 assign_labels 参数 SpectralClustering。 "kmeans" 可以匹配更精细的数据细节，但是可能更加不稳定。 特别是，除非你设置 random_state 否则可能无法复现运行的结果 ，因为它取决于随机初始化。另一方， 使用 "discretize" 策略是 100% 可以复现的，但是它往往会产生相当均匀的几何形状的边缘。

assign_labels="kmeans"

assign_labels="discretize"

参考:

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

2.3.6. 层次聚类

Hierarchical clustering 是一个常用的聚类算法，它通过不断的合并或者分割来构建聚类。 聚类的层次被表示成树（或者 dendrogram（树形图））。树根是拥有所有样本的唯一聚类，叶子是仅有一个样本的聚类。 请参照 Wikipedia page 查看更多细节。

The AgglomerativeClustering 使用自下而上的方法进行层次聚类:开始是每一个对象是一个聚类， 并且聚类别相继合并在一起。 linkage criteria 确定用于合并的策略的度量:

  • Ward 最小化所有聚类内的平方差总和。这是一种 variance-minimizing （方差最小化）的优化方向， 这是与k-means 的目标函数相似的优化方法，但是用 agglomerative hierarchical（聚类分层）的方法处理。
  • Maximum 或 complete linkage 最小化聚类对两个样本之间的最大距离。
  • Average linkage 最小化聚类两个聚类中样本距离的平均值。

AgglomerativeClustering 在于连接矩阵联合使用时，也可以扩大到大量的样本，但是 在样本之间没有添加连接约束时，计算代价很大:每一个步骤都要考虑所有可能的合并。

FeatureAgglomeration

The FeatureAgglomeration 使用 agglomerative clustering 将看上去相似的 特征组合在一起，从而减少特征的数量。这是一个降维工具, 请参照 无监督降维。

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

AgglomerativeClustering 支持 Ward, average, and complete linkage 策略.

Agglomerative cluster 存在 “rich get richer” 现象导致聚类大小不均匀。这方面 complete linkage 是最坏的策略，Ward 给出了最规则的大小。然而，在 Ward 中 affinity (or distance used in clustering) 不能被改变，对于 non Euclidean metrics 来说 average linkage 是一个好的选择。

示例:

  • Various Agglomerative Clustering on a 2D embedding of digits: exploration of the different linkage strategies in a real dataset.

2.3.6.2. 添加连接约束

AgglomerativeClustering 中一个有趣的特点是可以使用 connectivity matrix（连接矩阵） 将连接约束添加到算法中（只有相邻的聚类可以合并到一起），连接矩阵为每一个样本给定了相邻的样本。 例如，在 swiss-roll 的例子中，连接约束禁止在不相邻的 swiss roll 上合并，从而防止形成在 roll 上 重复折叠的聚类。

这些约束对于强加一定的局部结构是很有用的，但是这也使得算法更快，特别是当样本数量巨大时。

连通性的限制是通过连接矩阵来实现的:一个 scipy sparse matrix（稀疏矩阵），仅在一行和 一列的交集处具有应该连接在一起的数据集的索引。这个矩阵可以通过 a-priori information （先验信息） 构建:例如，你可能通过仅仅将从一个连接指向另一个的链接合并页面来聚类页面。也可以从数据中学习到,

例如使用 sklearn.neighbors.kneighbors_graph 限制与最临近的合并 :ref:`this example

<sphx_glr_auto_examples_cluster_plot_agglomerative_clustering.py>`, 或者使用 sklearn.feature_extraction.image.grid_to_graph 仅合并图像上相邻的像素点， 例如 raccoon face 。

示例:

  • A demo of structured Ward hierarchical clustering on a raccoon face image: Ward clustering to split the image of a raccoon face in regions.
  • Hierarchical clustering: structured vs unstructured ward: Example of Ward algorithm on a swiss-roll, comparison of structured approaches versus unstructured approaches.
  • Feature agglomeration vs. univariate selection: Example of dimensionality reduction with feature agglomeration based on Ward hierarchical clustering.
  • Agglomerative clustering with and without structure

Warning

Connectivity constraints with average and complete linkage

Connectivity constraints 和 complete or average linkage 可以增强 agglomerative clustering 中的 ‘rich getting richer’ 现象。特别是，如果建立的是 sklearn.neighbors.kneighbors_graph。 在少量聚类的限制中, 更倾向于给出一些 macroscopically occupied clusters 并且几乎是空的 (讨论内容请查看 Agglomerative clustering with and without structure)。

2.3.6.3. Varying the metric

Average and complete linkage 可以使用各种距离 (or affinities), 特别是 Euclidean distance (l2), Manhattan distance（曼哈顿距离）(or Cityblock（城市区块距离）, or l1), cosine distance(余弦距离),

或者任何预先计算的 affinity matrix（亲和度矩阵）.

  • l1 distance 有利于稀疏特征或者稀疏噪声: 例如很多特征都是0，就想在文本挖掘中使用 rare words 一样。
  • cosine distance 非常有趣因为它对全局放缩是一样的。

选择度量标准的方针是使得不同类样本之间距离最大化，并且最小化同类样本之间的距离。

示例:

  • Agglomerative clustering with different metrics

2.3.7. DBSCAN

The DBSCAN 算法将聚类视为被低密度区域分隔的高密度区域。由于这个相当普遍的观点， DBSCAN发现的聚类可以是任何形状的，与假设聚类是 convex shaped 的 K-means 相反。 DBSCAN 的核心概念是 core samples, 是指位于高密度区域的样本。 因此一个聚类是一组核心样本，每个核心样本彼此靠近（通过一定距离度量测量） 和一组接近核心样本的非核心样本（但本身不是核心样本）。算法中的两个参数, min_samples 和 eps,正式的定义了我们所说的 *dense*（稠密）。较高的 min_samples 或者

较低的 ``eps``表示形成聚类所需的较高密度。

更正式的,我们定义核心样本是指数据集中的一个样本，存在 min_samples 个其他样本在 eps 距离范围内，这些样本被定为为核心样本的邻居 neighbors 。这告诉我们核心样本在向量空间稠密的区域。 一个聚类是一个核心样本的集合，可以通过递归来构建，选取一个核心样本，查找它所有的 neighbors （邻居样本） 中的核心样本，然后查找 their （新获取的核心样本）的 neighbors （邻居样本）中的核心样本，递归这个过程。 聚类中还具有一组非核心样本，它们是集群中核心样本的邻居的样本，但本身并不是核心样本。 显然，这些样本位于聚类的边缘。

根据定义，任何核心样本都是聚类的一部分，任何不是核心样本并且和任意一个核心样本距离都大于 eps 的样本将被视为异常值。

在下图中，颜色表示聚类成员属性，大圆圈表示算法发现的核心样本。 较小的圈子是仍然是群集的 一部分的非核心样本。 此外，异常值由下面的黑点表示。

示例:

  • Demo of DBSCAN clustering algorithm

实现

DBSCAN 算法是具有确定性的，当以相同的顺序给出相同的数据时总是形成相同的聚类。 然而，当以不同的顺序提供数据时聚类的结果可能不相同。首先，即使核心样本总是被 分配给相同的聚类，这些集群的标签将取决于数据中遇到这些样本的顺序。第二个更重 要的是，非核心样本的聚类可能因数据顺序而有所不同。 当一个非核心样本距离两个核心样本的距离都小于 eps 时，就会发生这种情况。 通过三角不等式可知，这两个核心样本距离一定大于 eps 或者处于同一个聚类中。 非核心样本将被非配到首先查找到改样本的类别，因此结果将取决于数据的顺序。

当前版本使用 ball trees 和 kd-trees 来确定领域，这样避免了计算全部的距离矩阵 （0.14 之前的 scikit-learn 版本计算全部的距离矩阵）。保留使用 custom metrics （自定义指标）的可能性。细节请参照 NearestNeighbors。

大量样本的内存消耗

默认的实现方式并没有充分利用内存，因为在不使用 kd-trees 或者 ball-trees 的情况下构建一个 完整的相似度矩阵（e.g. 使用稀疏矩阵）。这个矩阵将消耗 n^2 个浮点数。 解决这个问题的几种机制:

  • A sparse radius neighborhood graph （稀疏半径邻域图）(其中缺少条目被假定为距离超出eps) 可以以高效的方式预先编译，并且可以使用 metric='precomputed' 来运行 dbscan。
  • 数据可以压缩，当数据中存在准确的重复时，可以删除这些重复的数据，或者使用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

2.3.8. Birch

The Birch 为提供的数据构建一颗 Characteristic Feature Tree (CFT，聚类特征树)。 数据实质上是被有损压缩成一组 Characteristic Feature nodes (CF Nodes，聚类特征节点)。 CF Nodes 中有一部分子聚类被称为 Characteristic Feature subclusters (CF Subclusters)， 并且这些位于非终端位置的CF Subclusters 可以拥有 CF Nodes 作为孩子节点。

CF Subclusters 保存用于聚类的必要信息，防止将整个输入数据保存在内存中。 这些信息包括:

  • Number of samples in a subcluster（子聚类中样本数）.
  • Linear Sum - A n-dimensional vector holding the sum of all samples（保存所有样本和的n维向量）
  • Squared Sum - Sum of the squared L2 norm of all samples（所有样本的L2 norm的平方和）.
  • Centroids - To avoid recalculation linear sum / n_samples（为了防止重复计算 linear sum / n_samples）.
  • Squared norm of the centroids（质心的 Squared norm ）.

Birch 算法有两个参数，即 threshold （阈值）和 branching factor 分支因子。Branching factor （分支因子） 限制了一个节点中的子集群的数量 ，threshold （簇半径阈值）限制了新加入的样本和存在与现有子集群中样本的最大距离。

该算法可以视为将一个实例或者数据简化的方法，因为它将输入的数据简化到可以直接从CFT的叶子结点中获取的一组子聚类。 这种简化的数据可以通过将其馈送到global clusterer（全局聚类）来进一步处理。Global clusterer（全局聚类）可以 通过 ``n_clusters``来设置。

如果 n_clusters 被设置为 None，将直接读取叶子结点中的子聚类，否则，global clustering（全局聚类） 将逐步标记他的 subclusters 到 global clusters (labels) 中，样本将被映射到 距离最近的子聚类的global label中。

算法描述:

  • 一个新的样本作为一个CF Node 被插入到 CF Tree 的根节点。然后将其合并到根节点的子聚类中去，使得合并后子聚类 拥有最小的半径，子聚类的选取受 threshold 和 branching factor 的约束。如果子聚类也拥有孩子节点，则重复执 行这个步骤直到到达叶子结点。在叶子结点中找到最近的子聚类以后，递归的更新这个子聚类及其父聚类的属性。
  • 如果合并了新样本和最近的子聚类获得的子聚类半径大约square of the threshold（阈值的平方）， 并且子聚类的数量大于branching factor（分支因子），则将为这个样本分配一个临时空间。 最远的两个子聚类被选取，剩下的子聚类按照之间的距离分为两组作为被选取的两个子聚类的孩子节点。
  • If this split node has a parent subcluster and there is room for a new subcluster, then the parent is split into two. If there is no room, then this node is again split into two and the process is continued recursively, till it reaches the root. 如果拆分的节点有一个 parent subcluster ，并且有一个容纳一个新的子聚类的空间，那么父聚类拆分成两个。 如果没有空间容纳一个新的聚类，那么这个节点将被再次拆分，依次向上检查父节点是否需要分裂， 如果需要按叶子节点方式相同分裂。

Birch or MiniBatchKMeans?

  • Birch 在高维数据上表现不好。一条经验法则，如果 n_features 大于20，通常使用 MiniBatchKMeans 更好。
  • 如果需要减少数据实例的数量，或者如果需要大量的子聚类作为预处理步骤或者其他， Birch 比 MiniBatchKMeans 更有用。

How to use partial_fit?

为了避免对 global clustering 的计算，每次调用建议使用 partial_fit 。

  1. 初始化 n_clusters=None 。
  2. 通过多次调用 partial_fit 训练所以的数据。
  3. 设置 n_clusters 为所需值，通过使用 brc.set_params(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.http://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.9. 聚类性能度量

度量聚类算法的性能不是简单的统计错误的数量或计算监督分类算法中的 precision （准确率）和 recall （召回率）。 特别地，任何 evaluation metric （度量指标）不应该考虑到 cluster labels （簇标签）的绝对值，而是如果这个簇定义类似于某些 ground truth set of classes 或者满足某些假设，使得属于同一个类的成员更类似于根据某些 similarity metric （相似性度量）的不同类的成员。

2.3.9.1. 调整后的 Rand 指数

考虑到 the ground truth class 赋值 labels_true 和相同样本 labels_pred 的聚类算法分配的知识，adjusted Rand index 是一个函数，用于测量两个 assignments （任务）的 similarity（相似度） ，忽略 permutations （排列）和 with chance normalization（使用机会规范化）:

>>>

代码语言：javascript复制
>>> 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， 得到相同的分数:

>>>

代码语言：javascript复制
>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)  
0.24...

另外， adjusted_rand_score 是 symmetric（对称的） : 交换参数不会改变 score （得分）。它可以作为 consensus measure（共识度量）:

>>>

代码语言：javascript复制
>>> metrics.adjusted_rand_score(labels_pred, labels_true)  
0.24...

完美的标签得分为 1.0

>>>

代码语言：javascript复制
>>> labels_pred = labels_true[:]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
1.0

坏 (e.g. independent labelings（独立标签）) 有负数 或 接近于 0.0 分:

>>>

代码语言：javascript复制
>>> 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.9.1.1. 优点
  • Random (uniform) label assignments have a ARI score close to 0.0（随机（统一）标签分配的 ARI 评分接近于 0.0） 对于 n_clusters 和 n_samples 的任何值（这不是原始的 Rand index 或者 V-measure 的情况）。
  • Bounded range（范围是有界的） [-1, 1]: negative values （负值）是坏的 (独立性标签), 类似的聚类有一个 positive ARI （正的 ARI）， 1.0 是完美的匹配得分。
  • No assumption is made on the cluster structure（对簇的结构不需作出任何假设）: 可以用于比较聚类算法，例如 k-means，其假定 isotropic blob shapes 与可以找到具有 “folded” shapes 的聚类的 spectral clustering algorithms（谱聚类算法）的结果。
2.3.9.1.2. 缺点
  • 与 inertia 相反，ARI requires knowledge of the ground truth classes（ARI 需要 ground truth classes 的相关知识） ，而在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习环境中）。 然而，ARI 还可以在 purely unsupervised setting （纯粹无监督的设置中）作为可用于 聚类模型选择（TODO）的共识索引的构建块。

示例:

  • Adjustment for chance in clustering performance evaluation: 分析数据集大小对随机分配聚类度量值的影响。
2.3.9.1.3. 数学表达

参考

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

2.3.9.2. 基于 Mutual Information （互信息）的分数

考虑到 ground truth class assignments （标定过的真实数据类分配） labels_true 的知识和相同样本 labels_pred 的聚类算法分配， Mutual Information 是测量两者 agreement 分配的函数，忽略 permutations（排列）。 这种测量方案的两个不同的标准化版本可用，Normalized Mutual Information(NMI) 和 Adjusted Mutual Information(AMI)。NMI 经常在文献中使用，而 AMI 最近被提出，并且 normalized against chance:

>>>

代码语言：javascript复制
>>> 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...

可以在 predicted labels （预测的标签）中 permute （排列） 0 和 1, 重命名为 2 到 3 并得到相同的得分:

>>>

代码语言：javascript复制
>>> 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 是 symmetric（对称的）: 交换参数不会更改分数。因此，它们可以用作 consensus measure:

>>>

代码语言：javascript复制
>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)  
0.22504...

完美标签得分是 1.0:

>>>

代码语言：javascript复制
>>> 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 是不正确的，因此更难判断:

>>>

代码语言：javascript复制
>>> metrics.mutual_info_score(labels_true, labels_pred)  
0.69...

坏的 (例如 independent labelings（独立标签）) 具有非正分数:

>>>

代码语言：javascript复制
>>> 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.9.2.1. 优点
  • Random (uniform) label assignments have a AMI score close to 0.0（随机（统一）标签分配的AMI评分接近0.0） 对于 n_clusters 和 n_samples 的任何值（这不是原始 Mutual Information 或者 V-measure 的情况）。
  • Bounded range（有界范围） [0, 1]: 接近 0 的值表示两个主要独立的标签分配，而接近 1 的值表示重要的一致性。此外，正好 0 的值表示 purely（纯粹） 独立标签分配，正好为 1 的 AMI 表示两个标签分配相等（有或者没有 permutation）。
  • No assumption is made on the cluster structure（对簇的结构没有作出任何假设）: 可以用于比较聚类算法，例如 k-means，其假定 isotropic blob shapes 与可以找到具有 “folded” shapes 的聚类的 spectral clustering algorithms （频谱聚类算法）的结果。
2.3.9.2.2. 缺点
  • 与 inertia 相反，MI-based measures require the knowledge of the ground truth classes（MI-based measures 需要了解 ground truth classes） ，而在实践中几乎不可用，或者需要人工标注或手动分配（如在监督学习环境中）。 然而，基于 MI-based measures （基于 MI 的测量方式）也可用于纯无人监控的设置，作为可用于聚类模型选择的 Consensus Index （共识索引）的构建块。
  • NMI 和 MI 没有调整机会。

示例:

  • Adjustment for chance in clustering performance evaluation: 分析数据集大小对随机分配聚类度量值的影响。 此示例还包括 Adjusted Rand Index。
2.3.9.2.3. 数学公式

mutual information 的价值以及 normalized variant （标准化变量）的值不会因 chance （机会）而被调整，随着不同标签（clusters（簇））的数量的增加，不管标签分配之间的 “mutual information” 的实际数量如何，都会趋向于增加。

参考

  • 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.
  • 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.
  • 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
  • Wikipedia entry for the (normalized) Mutual Information
  • Wikipedia entry for the Adjusted Mutual Information

2.3.9.3. 同质性，完整性和 V-measure

鉴于样本的 ground truth class assignments （标定过的真实数据类分配）的知识，可以使用 conditional entropy （条件熵）分析来定义一些 intuitive metric（直观的度量）。

特别是 Rosenberg 和 Hirschberg (2007) 为任何 cluster （簇）分配定义了以下两个理想的目标:

  • homogeneity(同质性): 每个簇只包含一个类的成员
  • completeness(完整性): 给定类的所有成员都分配给同一个簇。

我们可以把这些概念作为分数 homogeneity_score 和 completeness_score 。两者均在 0.0 以下 和 1.0 以上（越高越好）:

>>>

代码语言：javascript复制
>>> 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 的 harmonic mean 由以下函数计算 v_measure_score:

>>>

代码语言：javascript复制
>>> metrics.v_measure_score(labels_true, labels_pred)    
0.51...

V-measure 实际上等于上面讨论的 mutual information (NMI) 由 label entropies [B2011] （标准熵 [B2011]） 的总和 normalized （归一化）。

Homogeneity（同质性）, completeness（完整性） and V-measure 可以立即计算 homogeneity_completeness_v_measure 如下:

>>>

代码语言：javascript复制
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
...                                                      
(0.66..., 0.42..., 0.51...)

以下聚类分配稍微好一些，因为它是同构但不完整的:

>>>

代码语言：javascript复制
>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
...                                                      
(1.0, 0.68..., 0.81...)

Note

v_measure_score 是 symmetric（对称的）: 它可以用于评估同一数据集上两个 independent assignments （独立赋值）的 agreement（协议）。

这不是这样的 completeness_score 和 homogeneity_score: 两者的关系是被这样约束着:

代码语言：javascript复制
homogeneity_score(a, b) == completeness_score(b, a)
2.3.9.3.1. 优点
  • Bounded scores（分数是有界的）: 0.0 是最坏的, 1.0 是一个完美的分数.
  • Intuitive interpretation（直观解释）: 具有不良 V-measure 的聚类可以在 qualitatively analyzed in terms of homogeneity and completeness（在同质性和完整性方面进行定性分析） 以更好地感知到作业完成的错误类型。
  • No assumption is made on the cluster structure（对簇的结构没有作出任何假设）: 可以用于比较聚类算法，例如 k-means ，其假定 isotropic blob shapes 与可以找到具有 “folded” shapes 的聚类的 spectral clustering algorithms （频谱聚类算法）的结果。
2.3.9.3.2. 缺点
  • 以前引入的 metrics （度量标准）**not normalized with regards to random labeling（并不是随机标记的标准化的）**: 这意味着，根据 number of samples （样本数量），clusters （簇）和 ground truth classes （标定过的真实数据类），完全随机的标签并不总是产生 homogeneity （同质性），completeness（完整性）和 hence v-measure 的相同值。特别是 random labeling won’t yield zero scores especially when the number of clusters is large（随机标记不会产生零分，特别是当集群数量大时）。 当样本数量超过 1000，簇的数量小于 10 时，可以安全地忽略此问题。For smaller sample sizes or larger number of clusters it is safer to use an adjusted index such as the Adjusted Rand Index (ARI)（对于较小的样本数量或者较大数量的簇，使用 adjusted index 例如 Adjusted Rand Index (ARI)）。
  • 这些 metrics （指标） require the knowledge of the ground truth classes（需要标定过的真实数据类的知识），而在实践中几乎不可用，或需要人工标注来人工分配（如在受监督的学习环境中）。

示例:

  • Adjustment for chance in clustering performance evaluation: 分析数据集大小对随机分配聚类度量值的影响。
2.3.9.3.3. 数学表达

Homogeneity（同质性） 和 completeness（完整性） 的得分由下面公式给出:

参考

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

[B2011]

(1, 2) Identication and Characterization of Events in Social Media, Hila Becker, PhD Thesis.

2.3.9.4. Fowlkes-Mallows 分数

当样本的已标定的真实数据的类别分配已知时，可以使用 Fowlkes-Mallows index （Fowlkes-Mallows 指数）(sklearn.metrics.fowlkes_mallows_score) 。Fowlkes-Mallows 分数 FMI 被定义为 geometric mean of the pairwise precision （成对的准确率）和 recall （召回率）的几何平均值:

其中的 TP 是 True Positive（真正例） 的数量（即，真实标签和预测标签中属于相同簇的点对数），FP 是 False Positive（假正例） （即，在真实标签中属于同一簇的点对数，而不在预测标签中），FN 是 False Negative（假负例） 的数量（即，预测标签中属于同一簇的点对数，而不在真实标签中）。

score （分数）范围为 0 到 1。较高的值表示两个簇之间的良好相似性。

>>>

代码语言：javascript复制
>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>>

代码语言：javascript复制
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.47140...

可以在 predicted labels （预测的标签）中 permute （排列） 0 和 1 ，重命名为 2 到 3 并得到相同的得分:

>>>

代码语言：javascript复制
>>> labels_pred = [1, 1, 0, 0, 3, 3]

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

完美的标签得分是 1.0:

>>>

代码语言：javascript复制
>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
1.0

坏的（例如 independent labelings （独立标签））的标签得分为 0:

>>>

代码语言：javascript复制
>>> 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.9.4.1. 优点
  • Random (uniform) label assignments have a FMI score close to 0.0（随机（统一）标签分配 FMI 得分接近于 0.0） 对于 n_clusters 和 n_samples 的任何值（对于原始 Mutual Information 或例如 V-measure 而言）。
  • Bounded range（有界范围） [0, 1]: 接近于 0 的值表示两个标签分配在很大程度上是独立的，而接近于 1 的值表示 significant agreement 。此外，正好为 0 的值表示 purely 独立标签分配，正好为 1 的 AMI 表示两个标签分配相等（有或者没有 permutation （排列））。
  • No assumption is made on the cluster structure（对簇的结构没有作出任何假设）: 可以用于比较诸如 k-means 的聚类算法，其将假设 isotropic blob shapes 与能够找到具有 “folded” shapes 的簇的 spectral clustering algorithms （频谱聚类算法）的结果相结合。
2.3.9.4.2. 缺点
  • 与 inertia（习惯）相反，FMI-based measures require the knowledge of the ground truth classes（基于 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.9.5. Silhouette 系数

如果标注过的真实数据的标签不知道，则必须使用模型本身进行度量。Silhouette Coefficient (sklearn.metrics.silhouette_score) 是一个这样的评估的例子，其中较高的 Silhouette Coefficient 得分与具有更好定义的聚类的模型相关。Silhouette Coefficient 是为每个样本定义的，由两个得分组成:

  • a: 样本与同一类别中所有其他点之间的平均距离。
  • b: 样本与 下一个距离最近的簇 中的所有其他点之间的平均距离。

然后将单个样本的 Silhouette 系数 s 给出为:

给定一组样本的 Silhouette 系数作为每个样本的 Silhouette 系数的平均值。

>>>

代码语言：javascript复制
>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> dataset = datasets.load_iris()
>>> X = dataset.data
>>> y = dataset.target

在正常使用情况下，将 Silhouette 系数应用于聚类分析的结果。

>>>

代码语言：javascript复制
>>> 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.9.5.1. 优点
  • 对于不正确的 clustering （聚类），分数为 -1 ， highly dense clustering （高密度聚类）为 1 。零点附近的分数表示 overlapping clusters （重叠的聚类）。
  • 当 clusters （簇）密集且分离较好时，分数更高，这与 cluster （簇）的标准概念有关。
2.3.9.5.2. 缺点
  • convex clusters（凸的簇）的 Silhouette Coefficient 通常比其他类型的 cluster （簇）更高，例如通过 DBSCAN 获得的基于密度的 cluster（簇）。

示例:

  • Selecting the number of clusters with silhouette analysis on KMeans clustering : 在这个例子中，silhouette 分析用于为 n_clusters 选择最佳值.

2.3.9.6. Calinski-Harabaz 指数

如果不知道真实数据的类别标签，则可以使用 Calinski-Harabaz 指数 (sklearn.metrics.calinski_harabaz_score) 来评估模型，其中较高的 Calinski-Harabaz 的得分与具有更好定义的聚类的模型相关。

代码语言：javascript复制
>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> dataset = datasets.load_iris()
>>> X = dataset.data
>>> y = dataset.target

在正常使用情况下，将 Calinski-Harabaz index （Calinski-Harabaz 指数）应用于 cluster analysis （聚类分析）的结果。

>>>

代码语言：javascript复制
>>> 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_harabaz_score(X, labels)  
560.39...
2.3.9.6.1. 优点
  • 当 cluster （簇）密集且分离较好时，分数更高，这与一个标准的 cluster（簇）有关。
  • 得分计算很快
2.3.9.6.2. 缺点
  • 凸的簇的 Calinski-Harabaz index（Calinski-Harabaz 指数）通常高于其他类型的 cluster（簇），例如通过 DBSCAN 获得的基于密度的 cluster（簇）。

参考

  • Caliński, T., & Harabasz, J. (1974). “A dendrite method for cluster analysis”. Communications in Statistics-theory and Methods 3: 1-27. doi:10.1080/03610926.2011.560741.

中文文档: http://sklearn.apachecn.org/cn/stable/modules/clustering.html

英文文档: http://sklearn.apachecn.org/en/stable/modules/clustering.html

官方文档: http://scikit-learn.org/stable/

GitHub: https://github.com/apachecn/scikit-learn-doc-zh（觉得不错麻烦给个 Star，我们一直在努力）

贡献者: https://github.com/apachecn/scikit-learn-doc-zh#贡献者

有兴趣的们也可以和我们一起来维护，持续更新中 。。。

机器学习交流群: 629470233

机器学习 scikit-learn

0 人点赞