三维点云学习（4）1- Spectral的理论推导与解释

回顾谱聚类的步骤

Graph Cut

RatioCut -> Unnormalized
Ncut->Normalized

Min-Cut

进行聚类切割的过程可看作，将Wij(两点之间的关系权重)最小化
多个类时切割时可看作 cut A和A的反集

Min-Cut constrain

描述一个分区的大小
1.|A| 衡量每个节点中点的数量 -》对应与 RatioCut
2.vol(A)描述A的权重大小,一个分区里所有的边的权重之和 NormalizedCut

也就是说：
Unnormalized 偏向于每个类中点的数量均衡
normalized 偏向于每个类中权重均衡

Laplacian matrix 的直观理解

不管点与点之间的关系怎么样，总有一个特征值为0

当出现如下图所示两个特征值为0时，代表有两个连通域，也可以理解为可以直接分为两大类点
对应的特征向量也能很直观表现点之间的关系

当出现下图的情况时：
特征值为0的数量代表了独立分区的数量（1个）
根据第二个特征向量点的政府可以做切割

证明

下图1：只有一个连通域，拉普拉斯特征值为0只有一个，并且特征向量为常数向量
下图2：有两个连通域，拉普拉斯特征值为0有两个，并且特征向量表征点之间的关系

证明有多少个连通域就有多少个特征向量

存在当fi = fj时，存在特征向量为0

RatioCut for K=2

谱聚类的两种理解含义

1.图切割理解 a.尽可能把切割的权重Wij降低；b.切割的部分不能太细
2.将维运算理解，由原来的NN矩阵降为NK矩阵

复杂度，优劣