三维点云学习（3）2- K-Means

K-Means的具体构建流程

将输入的N个数据点，分为N个类
1.随机选取K个中心点
2.E-Step(expectation)：N个点、K个中心，求N个点到K个中心的nearest-neighbor
3.M-Step(maximization)：更新中心点的位置，把属于同一个类的数据点求一个均值，作为这个类的中心值
4.不断重复2、3步

K-Means数学上的定义

K-Means的本质是一直优化损失函数 J

最小化损失函数

最小化损失函数有两种方法：E-step(expectation)、M-step(maximization)
$\mu\,k：类的中心点$μk：类的中心点
$\Upsilon\,nk：bool值变量，判断是点是否属于该类$Υnk：bool值变量，判断是点是否属于该类

expectation

使得最近的Uk所对应的Rnk的值为1，其他值为0，可以尽可能的降低损失函数

maximization

一个类的中心点Uk等于属于这类的点的均值

K-Means过程的图示

(b) ©两步交替进行

判断算法收敛：
条件1：算法中心点Uk不再移动或者移动得较少
条件2：Rnk不在变化
现实中第三种情况，分到最后会出现一个点不断跳动振荡，需要考虑处理这种罕见的情况

K-Means Tricks

1.初始化选择Uk时，可以选取数据点里的点作为初始的中心点
2.执行多次K-Means迭代，选择损失函数最小的一次为最终的结果
3.在E-step(expectation)，可以使用octree或者kd-tree的方法寻找最临近点，确定Rnk
4.Mini-bath K-Means：每次迭代里，都选不一样的assemble

K-Medoids

K-Medoids（K中心点算法）加强版的k-means，在处理M-step时
K-Means：选取的是所有点的平均值
K-Medoids：选取的Uk是所有点的差值和函数最小，所以Uk必然数据集里的一个点

E-step相同，M-step求解V函数
本质就是求解在一个类中，那个点相对于其他所有点的距离的和函数（损失函数）最小，这个点就认为是中心点（UK），如下图历遍次数为7*7=49次，解决了噪声的问题。

K-Means的应用

Compression压缩

Limitations

K-means的缺点：
1.k是未知的，需要实验或者猜出K
2.k-means对噪声很敏感，所以发明K中心点解决噪声干扰问题
3.hard-asignment Rk为bool值，对于边界点难解决，所以需要引入GMM（高斯混合模型）解决