知识卡片
谱聚类把聚类变成切图
谱聚类的出发点是图论:把每个样本看成一个顶点,顶点之间用带权的边相连,边权表示相似度——距离越近权重越高,距离越远权重越低。这样”聚类”就变成了”把图切成几块”:理想的切法应让子图内部边的权重和尽量大、跨子图的边权和尽量小,也就是切在相似度最低的地方。
要让这件事可计算,需要三个构件:
- 邻接矩阵 W:W_ij 即边权。常用三种构造——ε-邻近法(距离小于阈值取 ε,否则取 0,太粗糙,少用)、K 近邻法(只保留每个点的 K 个最近邻)、全连接法(用高斯核等给所有点对赋正权重,最常用)。
- 度矩阵 D:对角矩阵,D_ii 为第 i 个点所有边权之和。
- 拉普拉斯矩阵 L = D − W:它继承了两者的对称性,因此特征值全为实数;且对任意向量 f 有二次型性质,可推出 L 半正定、最小特征值为 0。这保证了”求最小特征值”这件事有良好定义。
直接最小化割边权重会遇到一个退化陷阱:把每个点单独切出去,割边权重为 0,却是最没用的解。于是引入归一化:
- RatioCut:用子图点数 |A_i| 做分母,惩罚过小的子图;
- Ncut:用子图内边权和 vol(A_i) 做分母,比 RatioCut 更贴合”按权重平衡”的目标,通常更优。
求解时把”每个点属于哪块”松弛成连续向量,问题化为最小化 tr(HᵀLH),其解正是 L 最小的若干特征值对应的特征向量——用降维近似了这个 NP 难问题,这也是”谱”(特征值谱)一词的由来。松弛会损失少量信息,所以特征向量还要再做一次常规聚类(见 [[谱聚类先降维再聚类]])。
代价方面:谱聚类对数据结构几乎没有假设(不像 K-Means 要求凸集、GMM 假设高斯),能处理稀疏数据与高维数据,但结果高度依赖相似矩阵的构造方式,且降维幅度不够时会明显变慢。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第12章 聚类
原书出处 · 1 处
- 第12章 聚类 12.5.1 谱聚类的过程和原理 · 查看原书依据
谱聚类的主要思想:把所有的样本数据看作空间中的点,点之间用边连接起来形成图。图里面边的权重与点之间的距离有关,距离较远的两点之间的边权重值较低,而距离较近的两点之间的边权重值较高。
参考来源
- 位置:《机器学习基础:从入门到求职》第12章《第12章 聚类》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00015.html)
- 结论依据:原文以"点—边—边权"的图模型说明谱聚类思想,给出邻接矩阵三种构造、度矩阵与拉普拉斯矩阵 L=D−W 的性质,并说明 min cut 的退化问题及 RatioCut/Ncut 的归一化处理。
- 原始内容:谱聚类的主要思想:把所有的样本数据看作空间中的点,点之间用边连接起来形成图。图里面边的权重与点之间的距离有关,距离较远的两点之间的边权重值较低,而距离较近的两点之间的边权重值较高。……RatioCut切图考虑了目标子图的大小,避免了单个样本点作为一个簇的情况发生,平衡了各个子图的大小。