1 kmeans聚类思想
-
维基百科上的描述
对于X = {x1, x2, ..., xn}n 个观测样本，其中每个样本 x 都是 d 维向量，将这 n 个样本划分成 k 个集合S = { S1, S2, ..., Sk} (k<=n)，每个集合使用集合中的样本均值来表示（集合中心 centroid 等于样本均值）。kmeans算法目的是：以每个 centroid 与集合中所有样本欧式距离最小为标准，寻找一个最优的集合划分。这个公式概括了之前的描述：(ui 为第 i 个集合的样本均值）
kmeans_function.png
-
观测样本，d 维向量， 欧式距离
例子：从一张 256x256 像素的RGB图像来解释
lena256.jpg
x1=(179, 121,32)，x2=(137, 50, 75)，它们的欧式距离为：sum( (x1-x2)^2 ) = (179-137)^2 + (121-50)^2 + (32-75)^2
2 kmean标准算法 - Lloyd's algorithm
-
算法步骤
- step 1： 初始化 k 个质心，即设置 k 个 d 维向量，表示要将样本划分成 k 个集合：m1(1),…,mk(1) 此时，集合中还没有任何样本。m 的上标 (1) 表示中心的更新次数即 step2 中的 t
-
几种初始化方法：
1.完全随机赋值
2.随机选择 k 个样本作为初始值
3.分裂法（先计算所有样本均值得到一个质心，再添加一个微小扰动，使质心 1 分为 2 -> 聚类 -> 再分裂，得到 k 个质心）
-
step 2： 聚类，计算每个观测样本与质心的欧式距离，根据距离最小原则将样本放入 k 个集合中
-
step 3： 更新每个集合的质心，将每个集合的样本均值作为新的质心
- step 4： 判断是否满足停止条件，不满足，则继续进行 step2， step3
- 停止条件： 直接设置迭代次数，或者判断质心变化误差很小就视为收敛，退出循环
- 源码分享：my_kmeans
3 k-mean应用：RGB图像压缩
k-means压缩原理
-
压缩测试
k = 2，64，100 即压缩倍数为 12，4，3.42
- 源码分享：kmeansVQ
参考：
1.k-means clusetering wiki
2.http://blog.pluskid.org/?p=57
