直观理解 K平均算法 (K-means clustering)

Ilingis · 发表于 2022-5-11 08:09

聚类又称无监督学习：也就是没有因变量(标签) $y_i$ 情况下，将数据进行合理的分组
聚类评估指标原则

簇内(Intra cluster)：簇内的点，互相距离应该很小
簇间(Inter cluster)：簇间的距离应该很大

Dunn指数：

是评估聚类算法的指标；对于一个好的聚类结果，Dunn指数应该是很大的

$D=\frac{\min_{i,j}\ \ d(i,j)} {\max_{k}\ \ d^\prime(k)}$ 也就等于 $\frac{最小簇间距离}{最大簇内距离}$

$d(i,j)$ ：指的是簇间(Inter cluster)距离
$d^\prime(k)$ ：指的是簇内(Intra cluster)距离

直观几何理解Dunn指数：

将两簇数据的每一个点，互相两两计算距离，为 $d_1,d_2,d_3,d_4....$ ; 然后取最小距离： $min(d_1,d_2,d_3,d_4....)$ 为 最小簇间距离
分别在两簇数据中求出最大两点距离 $d_1,d_2$ ,然后 $max(d_1,d_2)$ 为 最大簇内距离

一

扩展：后续再总结其它无监督学习评估指标
K平均算法 (K-means clustering)

几何解释

二

K-means中：K 就是簇数量或组类数量；为超参数

初始化：随机任取 K 个类，如K=2
在数据中随机选取2个点，为质心点(Centroids)
将所有的点与此两个质心点计算距离，选择最近的质心点，进行分类
最后，根据分类完成后的 2 簇数据，分别计算簇内距离的平均值，确定为新的质心
再重复3，4步骤，直到收敛（也就是所有质心点，进行第4步后没有太大变化）

数学解释与目标函数

三

目标函数： $\arg \min_{C_1,C_2,C_3... }\sum_{i=1}^{k} \sum_{x\in S_j}^{|S_j|} {||x-C_i ||^2}$
约束条件： $x\in S_j$ ， $S_j \cap S_i=\phi$
小结：

$C_i$ ：为质心点
$S_j$ ：为簇群点
$|S_j|$ ：为簇群的点数
目标函数：就是优化，簇内各点到质心点距离最小

扩展：上述公式具有指数时间复杂度：优化困难；后续将探讨近似算法求解优化问题
如何初始化:K-Means++

K-Means具有初始化敏感性(initialization sensitivity)：在初始化 K 个质心点时，随机化的点不同，因此最终分类的结果也可能会发生变化；
初始化敏感性几何解释

四

original points：为原始图
下面两图，为随机初始化质心点后，两种不同的模型收敛结果

1、第一种初始化质心点后，收敛的结果【想要的结果】

五

1、第二种初始化质心点后，收敛的结果【错误的结果】

六

K-Means++

1、在初始化时，首先只随机选择一个质心点
2、然后计算每个点到  质心点  的距离

七

3、第二个质心点 $C_2$ 随机选择的概率，与步骤 2 中的距离大小成正比；距离越大被选中的概率也就越大
4、选择好了两个质心点  ，那么再次计算所有点到质心点的距离，然后根据较大距离；大概率地选择第三个质心点

八

5、重复以上步骤，达到最终收敛效果
小结：在上述步骤中，没有利用距离最大的(绝对的方式)，来进行质心点的选择，而是利用概率(相对的方式)进行质点选择，是因为相对概率，可以降低异常值的影响
K-means的局限性

1、簇的不同大小(different sizes)

九

2、簇的不同密度(different densities)

十

3、非凸形状(non-convex)

十一

扩展：可使用较大的 K 来获得多个簇群，然后将不同的簇群进行合并，但实现比较繁琐，并非较好的方案
K中心点算法(K-medoids)

K-means的质心点可能是不可解释的：
比如在BOW(词袋模型)中，所有点的都是二进制向量 $[1,0,1,1,0,0,1]$ ；而K-means的质心点根据平均值计算出来后的向量可能为 $[1.2,0.4,3.2,1.1,0,0.3,1]$ ，那么这样的向量是被新创建出来的，没法解释是哪个点
K中心点算法(K-medoids)：不是给出使用平均值计算的质心，而是一个实际的数据点，具有可解释性；K中心点算法步骤如下：

随机选取K个中心点
计算各个点到中心点的距离，然后将点根据最短距离，进行分类，得到K 个簇群
将K中心点，在各自簇群里，与其它点进行交互；然后计算各点到中心点距离，如果损失减少(也就是求和距离减少)，保持中心点的交换否则撤销交换
重复2，3，直到收敛

K 值选择

K 值为超参数，可以利用网格搜索，选择最小目标函数值的 K值，为最优选择
参考：

https://en.wikipedia.org/wiki/K-means_clustering
https://cs.wmich.edu/alfuqaha/summer14/cs6530/lectures/ClusteringAnalysis.pdf

		自动登录	找回密码
密码			立即注册

直观理解 K平均算法 (K-means clustering)

本帖子中包含更多资源