sklearn-聚类

摘要: sklearn 聚类基础

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

无监督学习只需要特征矩阵 $\boldsymbol{X}$，不需要真实标签 $\boldsymbol{y}$。PCA 是无监督学习中的一种，聚类算法也是无监督学习算法之一。

聚类的目的是将数据划分成有意义的或有用的组，这种划分需要基于业务需求或建模需求，聚类也可以单纯用于探索数据的自然结构和分布。

聚类结果是不确定的，不一定总能反映数据的真实分类，同样的聚类，根据不同的业务需求，可能是一个好结果也可能是一个坏结果。

---

聚类算法在 sklearn 中有两种，类和函数。如果是类，那么聚类流程与分类流程一样，需要实例化、训练、用接口和属性调结果这三步。如果是函数，只需要输入特征矩阵和超参数，即可返回聚类结果和各种指标。

sklearn.cluster 中的类

类	含义	输入
AffinityPropagation	亲和传播数据聚类	[damping, …]
AgglomerativeClustering	层次聚类	[…]
Birch	Birch聚类	[threshold, branching_factor, …]
DBSCAN	从矢量数组或距离矩阵执行 DBSCAN 聚类	[eps, min_samples, metric, …]
FeatureAgglomeration	层次特征	[n_clusters, …]
KMeans	K均值聚类	[n_clusters, init, n_init, …]
MiniBatchKMeans	小批量 K 均值聚类	[n_clusters, init, …]
MeanShift	用平坦核函数的平均移位聚类	[bandwidth, seeds, …]
SpectralClustering	光谱聚类	[n_clusters, …]

sklearn.cluster 中的函数

函数	含义	输入
affinity_propagation	亲和传播数据聚类	S[, …]
dbscan	从矢量数组或距离矩阵执行 DBSCAN 聚类	X[, eps, min_samples, metric, …]
estimate_bandwidth	估计要使用均值平移算法的带宽	X[, quantile, …]
k_means	k均值聚类	X, c_clusters[, …]
mean_shift	使用平坦核函数的平均移位聚类	X[, bandwidth, seeds, …]
spectral_clustering	光谱聚类	affinity[, …]
ward_tree	层次聚类算法	X[, connectivity, …]

另外 scipy.cluster 中也有聚类算法，很多 sklearn 中有的都可以在 scipy 中找到。

注意输入数据，sklearn.cluster 中的算法可以接收不同类型的矩阵作为输入

• 所有方法都接受 [n_samples, n_features] 的标准特征矩阵，这些可以从 sklearn.feature_extraction 模块中的类获得
• 对于亲和力传播，光谱聚类和 DBSCAN，还可以输入 [n_samples, n_samples] 的相似性矩阵，可以用 sklearn.metrics.pairwise 获取

---

KMeans

KMeans 工作原理

簇与质心

KMeans 将 N 个样本的特征矩阵 X 划分为 K 个无交集的簇。

簇中所有数据的均值 $\mu_{j}$ 称为质心(centroids)

簇的个数是超参数，需要人为输入确定。KMeans 的任务就是在给定 K 后找到 K 个最优的质心，并将理这些质心最近的数据分别分配到这些质心代表的簇中。算法如下:

确定 K
while True:
    将每个样本点分配到离它们最近的质心，生成 K 个簇
    对每个簇，计算所有被分到该簇的样本点的平均值作为新的质心
    当质心位置不再发生变化，迭代停止

质心位置不再发生变化的情况: 所有样本点都不会再从一个簇转移到另一个簇，质心就不会变化了。

簇内误差平方和

被分在同一个簇中的数据是有相似性的,而不同簇中的数据是不同的,当聚类完毕之后,我们就要分别去研究每个簇中的样本都有什么样的性质,从而根据业务需求制定不同的策略。

与LR评分卡模型中的”分箱”类似: 分箱的目的是希望一个箱内的人有着相似的信用风险,而不同箱的人的信用风险差异巨大,以此来区别不同信用度的人

聚类也是追求”簇内差异小，簇间差异大”，这个差异由样本点到其所在的簇的质心的距离来衡量。

$x$ 为样本点, $\mu$ 为质心，特征数为 n，i 为特征下标

• 欧氏距离

$$d(x, \mu) = \sqrt{\sum\limits_{i=1}\limits^{n}(x_{i} - \mu_{i})^{2}}$$

• 曼哈顿距离

$$d(x, \mu) = \sum\limits_{i=1}\limits^{n}(|x_{i} - \mu_{i}|)$$

• 余弦距离

$$\cos{\theta} = \frac{\sum_{1}^{n}(x_{i} \cdot \mu_{i})}{\sqrt{\sum_{1}^{n}(x_{i})^{2}}\sqrt{\sum_{1}^{n}(\mu_{i})^{2}}}$$

如果采用欧氏距离，则簇内所有样本点到质心的距离的平方和 CSS(Cluster Sum of Square) 如下，m 是簇中样本个数，j 是样本编号。

$$CSS = \sum\limits_{j=0}\limits^{m}\sum\limits_{i=1}\limits^{n}(x_{i} - \mu_{i})^{2}$$

整体平方和为 $\sum\limits_{l=1}^{K}CSS_{l}$，KMeans 追求的就是使得整体平方和最小的质心。

质心在不断变化迭代中，整体平方和是越来越小的。当整体平方和最小的时候，质心就不在发生变化了。

距离度量	质心	Inertia
欧氏距离	均值	最小化每个样本点到质心的欧氏距离之和
曼哈顿距离	中位数	最小化每个样本点到质心的曼哈顿距离之和
余弦距离	均值	最小化每个样本点到质心的余弦距离之和

sklearn 中只能使用欧氏距离。

KMeans 时间复杂度

平均: $O(KNT)$, K 为超参数，N 为样本数，T 为迭代次数
最坏: $O(N^{(K+2)/p})$, K为超参数, N 为样本数, p 为特征数

sklearn.cluster.KMeans

参数

n_clusters: 告诉模型要聚几类
init: 初始质心, 可以选 kmeans++, random 或一个形状为 (n_cluster, n_features) 的数组给出初始质心。
max_iter: 单次 KMeans 最大次数
tol: 两次迭代间 inertia 下降量

接口

predict:

属性

label_:
cluster_centers_:
inertia_:

聚类算法的评估指标

聚类模型的结果不是某种标签输出,并且聚类的结果是不确定的,其优劣由业务需求或者算法需求来决定,并且没有永远的正确答案。

KMeans的目标是簇内差异小,簇外差异大,我们就可以通过衡量簇内差异来衡量聚类的效果。而Inertia是用距离来衡量簇内差异的指标，因此自然想到 Inertia 作为评估指标。

Inertia 作为评估指标的缺点:

1. 只知道越小越好，是 0 最好，但不知道一个较小的 Inertia 究竟有没有达到模型极限，即能否继续提高
2. 计算受特征数影响，计算量大，不适合一次次地评估模型
3. 受 K 影响，K 变大的时候，Inertia 注定变小
4. 对数据分布有假设，它假设数据满足凸分布，且假设数据是各向同性的(isotropic)，即数据的属性在不同方向代表这相同的含义。但现实数据中会出现的细长簇，流形簇，环形簇等表现不好。

真实标签已知

(1) 互信息分

• 普通互信息分: metrics.adjusted_mutual_info_score(y_pred, y_true)
• 调整的互信息分: metrics.mutual_info_score(y_pred, y_true)
• 标准化互信息分: metrics.normalized_mutual_info_score(y_pred, y_true)

取值范围 (0, 1)
越接近 1，聚类效果越好
在随机均匀聚类下产生 0 分

(2) V-measure

• 同质性(是否每个簇仅包含单个类的样本): metrics.homogeneity_score(y_true, y_pred)
• 完整性(是否给定类的所有样本都被分配到同一个簇中): metrics.completeness_score(y_true, y_pred)
• 同质性和完整性的调和平均，称为 V-measure: metrics.v_meatrue_score(labels_true, labels_pred)
• 三者可以一次被计算出来 metrics.homogeneity_completeness_v_measure(labels_true,labels_pred)

取值范围 (0, 1)
越接近 1，聚类效果越好
由于分为同质性和完整性两种度量，可以更仔细地研究模型到底哪个任务做的不够好
对样本分布没有假设，在任何分布上都有不错的表现
在随机均匀聚类下不会产生 0 分

(3) 调整兰德系数

• metrics.adjusted_rand_score(y_true, y_pred)

取值在(-1,1)之间,负值象征着簇内的点差异巨大,甚至相互独立,正类的兰德系数比较优秀,越接近1越好
对样本分布没有假设,在任何分布上都可以有不错的表现,尤其是在具有”折叠”形状的数据上表现优秀
在随机均匀聚类下产生0分

真实标签未知

完全依赖于评价簇内的稠密程度(簇内差异小)和簇间的离散程度(簇外差异大)来评估聚类的效果。

轮廓系数

1) 样本与其自身所在的簇中的其他样本的相似度 a: 等于样本与同一簇中所有其他点之间的平均距离
2) 样本与其他簇中的样本的相似度 b: 等于样本与下一个最近的簇中的所有点之间的平均距离

根据聚类的要求”簇内差异小,簇外差异大”,我们希望b永远大于a,并且大得越多越好。

单个样本的轮廓系数为

$$s = \frac{b - a}{max(a, b)}$$

轮廓系数范围是(-1,1),其中值越接近1表示样本与自己所在的簇中的样本很相似,并且与其他簇中的样本不相似,当样本点与簇外的样本更相似的时候,轮廓系数就为负。当轮廓系数为0时,则代表两个簇中的样本相似度一致,两个簇本应该是一个簇。

总结: 轮廓系数越接近于1越好,负数则表示聚类效果非常差。

metrics.silhouette_score 返回一个数据集中所有样本的轮廓系数的均值。
metrics.silhouette_sample 返回数据集中每个样本自己的轮廓系数

轮廓系数对数据分布无假设。因此很多数据集上表现都很好。

缺点: 在凸形的类上表现虚高。比如基于密度进行的聚类,或通过DBSCAN获得的聚类结果,如果使用轮廓系数来衡量,则会表现出比真实聚类效果更高的分数。

卡林斯基-哈拉巴斯指数

sklearn.metrics.calinski_harabaz_score (X, y_pred)

Calinski-Harabaz 指数越高越好。对于有 k 个簇的聚类而言, Calinski-Harabaz 指数 $s(k)$ 写作如下公式:

$$s(K) = \frac{Tr(B_{K})}{Tr(W_{K})}\cdot\frac{N-K}{K-1}$$

其中N为数据集中的样本量,K为簇的个数(即类别的个数),$B_{k}$是组间离散矩阵,即不同簇之间的协方差矩阵,$W_{k}$是簇内离散矩阵,即一个簇内数据的协方差矩阵

数据之间的离散程度越高，协方差矩阵的迹越大。

在凸形数据上也会虚高，但比轮廓系数好的是它计算很快。

戴维斯-布尔丁指数

sklearn.metrics.davies_bouldin_score (X, y_pred)

权变矩阵

sklearn.metrics.cluster.contingency_matrix (X, y_pred)

画图选 n_cluster

• 聚出的类的轮廓系数
• 各类的轮廓系数对比
• 聚类后的数据分布图

画图后主观判断选几类

应用

• 非结构数据(图像，声音)的矢量量化(VQ)
• 特征选择(选择对模型贡献大的特征)
• PCA: 聚合信息
• 矢量量化: 在同等样本量下压缩信息大小

---

Jupyter 脚本链接

---