未标记的数据的 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
模块中的函数获得。
当 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 (高斯混合模型)的特殊情况。
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 (度量)。 它有各种缺点:
示例:
参考:
MiniBatchKMeans
是 KMeans
算法的一个变体,它使用 mini-batches (小批量)来减少计算时间,同时仍然尝试优化相同的 objective function (目标函数)。 Mini-batches(小批量)是输入数据的子集,在每次 training iteration (训练迭代)中 randomly sampled (随机抽样)。这些小批量大大减少了融合到本地解决方案所需的计算量。 与其他降低 k-means 收敛时间的算法相反,mini-batch k-means 产生的结果通常只比标准算法略差。
MiniBatchKMeans
收敛速度比 KMeans
,但是结果的质量会降低。在实践中,质量差异可能相当小,如示例和引用的参考。
示例:
参考:
AffinityPropagation
AP聚类是通过在样本对之间发送消息直到收敛来创建聚类。然后使用少量示例样本作为聚类中心来描述数据集, 聚类中心是数据集中最能代表一类数据的样本。在样本对之间发送的消息表示一个样本作为另一个样本的示例样本的 适合程度,适合程度值在根据通信的反馈不断更新。更新迭代直到收敛,完成聚类中心的选取,因此也给出了最终聚类。
Affinity Propagation 算法比较有趣的是可以根据提供的数据决定聚类的数目。 因此有两个比较重要的参数 preference, 决定使用多少个示例样本 *damping factor*(阻尼因子) 减少吸引信息和归属信息以防止 更新减少吸引度和归属度信息时数据振荡。
示例:
参考:
SpectralClustering
是在样本之间进行亲和力矩阵的低维度嵌入,其实是低维空间中的 KMeans。 如果亲和度矩阵稀疏,则这是非常有效的并且 pyamg module 以及安装好。 SpectralClustering 需要指定聚类数。这个算法适用于聚类数少时,在聚类数多是不建议使用。
对于两个聚类,它解决了相似图上的 normalised cuts 问题: 将图形切割成两个,使得切割的边缘的重量比每个簇内的边缘的权重小。在图像处理时,这个标准是特别有趣的: 图像的顶点是像素,相似图的边缘是图像的渐变函数。
Warning
Transforming distance to well-behaved similarities
请注意,如果你的相似矩阵的值分布不均匀,例如:存在负值或者距离矩阵并不表示相似性 spectral problem 将会变得奇异,并且不能解决。 在这种情况下,建议对矩阵的 entries 进行转换。比如在符号距离有符号的情况下通常使用 heat kernel:
similarity = np.exp(-beta * distance / distance.std())
请看这样一个应用程序的例子。
示例:
可以使用不同的分配策略, 对应于 assign_labels
参数 SpectralClustering
。 "kmeans"
可以匹配更精细的数据细节,但是可能更加不稳定。 特别是,除非你设置 random_state
否则可能无法复现运行的结果 ,因为它取决于随机初始化。另一方, 使用 "discretize"
策略是 100% 可以复现的,但是它往往会产生相当均匀的几何形状的边缘。
assign_labels="kmeans" | assign_labels="discretize" |
---|---|
参考:
Hierarchical clustering 是一个常用的聚类算法,它通过不断的合并或者分割来构建聚类。 聚类的层次被表示成树(或者 dendrogram(树形图))。树根是拥有所有样本的唯一聚类,叶子是仅有一个样本的聚类。 请参照 Wikipedia page 查看更多细节。
The AgglomerativeClustering
使用自下而上的方法进行层次聚类:开始是每一个对象是一个聚类, 并且聚类别相继合并在一起。 linkage criteria 确定用于合并的策略的度量:
AgglomerativeClustering
在于连接矩阵联合使用时,也可以扩大到大量的样本,但是 在样本之间没有添加连接约束时,计算代价很大:每一个步骤都要考虑所有可能的合并。
The FeatureAgglomeration
使用 agglomerative clustering 将看上去相似的 特征组合在一起,从而减少特征的数量。这是一个降维工具, 请参照 无监督降维。
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 是一个好的选择。
示例:
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 。
示例:
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)。
Average and complete linkage 可以使用各种距离 (or affinities), 特别是 Euclidean distance (l2), Manhattan distance(曼哈顿距离)(or Cityblock(城市区块距离), or l1), cosine distance(余弦距离),
或者任何预先计算的 affinity matrix(亲和度矩阵).
选择度量标准的方针是使得不同类样本之间距离最大化,并且最小化同类样本之间的距离。
示例:
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
的样本将被视为异常值。
在下图中,颜色表示聚类成员属性,大圆圈表示算法发现的核心样本。 较小的圈子是仍然是群集的 一部分的非核心样本。 此外,异常值由下面的黑点表示。
示例:
实现
DBSCAN 算法是具有确定性的,当以相同的顺序给出相同的数据时总是形成相同的聚类。 然而,当以不同的顺序提供数据时聚类的结果可能不相同。首先,即使核心样本总是被 分配给相同的聚类,这些集群的标签将取决于数据中遇到这些样本的顺序。第二个更重 要的是,非核心样本的聚类可能因数据顺序而有所不同。 当一个非核心样本距离两个核心样本的距离都小于 eps
时,就会发生这种情况。 通过三角不等式可知,这两个核心样本距离一定大于 eps
或者处于同一个聚类中。 非核心样本将被非配到首先查找到改样本的类别,因此结果将取决于数据的顺序。
当前版本使用 ball trees 和 kd-trees 来确定领域,这样避免了计算全部的距离矩阵 (0.14 之前的 scikit-learn 版本计算全部的距离矩阵)。保留使用 custom metrics (自定义指标)的可能性。细节请参照 NearestNeighbors
。
大量样本的内存消耗
默认的实现方式并没有充分利用内存,因为在不使用 kd-trees 或者 ball-trees 的情况下构建一个 完整的相似度矩阵(e.g. 使用稀疏矩阵)。这个矩阵将消耗 n^2 个浮点数。 解决这个问题的几种机制:
metric='precomputed'
来运行 dbscan。
sample_weight
参数。
引用:
The Birch
为提供的数据构建一颗 Characteristic Feature Tree (CFT,聚类特征树)。 数据实质上是被有损压缩成一组 Characteristic Feature nodes (CF Nodes,聚类特征节点)。 CF Nodes 中有一部分子聚类被称为 Characteristic Feature subclusters (CF Subclusters), 并且这些位于非终端位置的CF Subclusters 可以拥有 CF Nodes 作为孩子节点。
CF Subclusters 保存用于聚类的必要信息,防止将整个输入数据保存在内存中。 这些信息包括:
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中。
算法描述:
Birch or MiniBatchKMeans?
n_features
大于20,通常使用 MiniBatchKMeans 更好。How to use partial_fit?
为了避免对 global clustering 的计算,每次调用建议使用 partial_fit
。
n_clusters=None
。n_clusters
为所需值,通过使用 brc.set_params(n_clusters=n_clusters)
。partial_fit
, 例如 brc.partial_fit()
执行全局聚类。参考:
度量聚类算法的性能不是简单的统计错误的数量或计算监督分类算法中的 precision (准确率)和 recall (召回率)。 特别地,任何 evaluation metric (度量指标)不应该考虑到 cluster labels (簇标签)的绝对值,而是如果这个簇定义类似于某些 ground truth set of classes 或者满足某些假设,使得属于同一个类的成员更类似于根据某些 similarity metric (相似性度量)的不同类的成员。
考虑到 the ground truth class 赋值 labels_true
和相同样本 labels_pred
的聚类算法分配的知识,adjusted Rand index 是一个函数,用于测量两个 assignments (任务)的 similarity(相似度) ,忽略 permutations (排列)和 with chance normalization(使用机会规范化):
>>>
>>> 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
是 symmetric(对称的) : 交换参数不会改变 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
坏 (e.g. independent labelings(独立标签)) 有负数 或 接近于 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...
n_clusters
和 n_samples
的任何值(这不是原始的 Rand index 或者 V-measure 的情况)。示例:
参考
考虑到 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:
>>>
>>> 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 并得到相同的得分:
>>>
>>> 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:
>>>
>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)
0.22504...
完美标签得分是 1.0:
>>>
>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
1.0
>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)
1.0
这对于 mutual_info_score
是不正确的,因此更难判断:
>>>
>>> metrics.mutual_info_score(labels_true, labels_pred)
0.69...
坏的 (例如 independent labelings(独立标签)) 具有非正分数:
>>>
>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
-0.10526...
n_clusters
和 n_samples
的任何值(这不是原始 Mutual Information 或者 V-measure 的情况)。示例:
mutual information 的价值以及 normalized variant (标准化变量)的值不会因 chance (机会)而被调整,随着不同标签(clusters(簇))的数量的增加,不管标签分配之间的 “mutual information” 的实际数量如何,都会趋向于增加。
参考
鉴于样本的 ground truth class assignments (标定过的真实数据类分配)的知识,可以使用 conditional entropy (条件熵)分析来定义一些 intuitive metric(直观的度量)。
特别是 Rosenberg 和 Hirschberg (2007) 为任何 cluster (簇)分配定义了以下两个理想的目标:
我们可以把这些概念作为分数 homogeneity_score
和 completeness_score
。两者均在 0.0 以下 和 1.0 以上(越高越好):
>>>
>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.homogeneity_score(labels_true, labels_pred)
0.66...
>>> metrics.completeness_score(labels_true, labels_pred)
0.42...
称为 V-measure 的 harmonic mean 由以下函数计算 v_measure_score
:
>>>
>>> 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
如下:
>>>
>>> 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
v_measure_score
是 symmetric(对称的): 它可以用于评估同一数据集上两个 independent assignments (独立赋值)的 agreement(协议)。
这不是这样的 completeness_score
和 homogeneity_score
: 两者的关系是被这样约束着:
homogeneity_score(a, b) == completeness_score(b, a)
示例:
Homogeneity(同质性) 和 completeness(完整性) 的得分由下面公式给出:
参考
[B2011] | (1, 2) Identication and Characterization of Events in Social Media, Hila Becker, PhD Thesis. |
---|
当样本的已标定的真实数据的类别分配已知时,可以使用 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。较高的值表示两个簇之间的良好相似性。
>>>
>>> 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...
可以在 predicted labels (预测的标签)中 permute (排列) 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
坏的(例如 independent labelings (独立标签))的标签得分为 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
n_clusters
和 n_samples
的任何值(对于原始 Mutual Information 或例如 V-measure 而言)。参考
如果标注过的真实数据的标签不知道,则必须使用模型本身进行度量。Silhouette Coefficient (sklearn.metrics.silhouette_score
) 是一个这样的评估的例子,其中较高的 Silhouette Coefficient 得分与具有更好定义的聚类的模型相关。Silhouette Coefficient 是为每个样本定义的,由两个得分组成:
然后将单个样本的 Silhouette 系数 s 给出为:
给定一组样本的 Silhouette 系数作为每个样本的 Silhouette 系数的平均值。
>>>
>>> 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 系数应用于聚类分析的结果。
>>>
>>> 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...
参考
示例:
如果不知道真实数据的类别标签,则可以使用 Calinski-Harabaz 指数 (sklearn.metrics.calinski_harabaz_score
) 来评估模型,其中较高的 Calinski-Harabaz 的得分与具有更好定义的聚类的模型相关。
>>> 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 (聚类分析)的结果。
>>>
>>> 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...
参考
中文文档: 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