Kmeans算法的应用实例（Matlab版本）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

K-means是一种经典的聚类算法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

假设要把样本集分为c个类别，算法描述如下：
（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

K-means算法的应用之一就是图像的压缩。假设有一张1600*2400大小的RGB图，那么需要1600*2400*3字节的空间来存放每个像素的三个通道值。如果这是一张颜色单调的图片，我们就可以把颜色相近的像素点归类，用同一组RGB值来表示他们，把这组RGB值放入调色板的x位置，原图片中属于这一聚类的像素点只需要保存x值，然后根据x值到调色板查找RGB值。如果把一张图片的所有颜色聚成256个类，那么只需要1600*2400*1个字节来保存每个像素的调色板索引值，和256*3个字节保存调色板。尽管这一过程会使照片的色彩略有失真，但是它可以大大节省存储空间。

下面是k-means算法的Matlab代码。图片的像素按照RGB值被归为10个聚类，分别是原图像和聚类后的图像。如果增加聚类的个数，图像的效果会有所改善。

K-Means主要有两个最重大的缺陷——都和初始值有关：

K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ ISODATA 算法通过类的自动合并和分裂，得到较为合理的类型数目 K）
K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）
我在这里重点说一下 K-Means++算法步骤：

先从我们的数据库随机挑个随机点当“种子点”。
对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
重复第（2）和第（3）步直到所有的K个种子点都被选出来。
进行K-Means算法。
相关的代码你可以在这里找到“implement the K-means++ algorithm”(墙) 另，Apache 的通用数据学库也实现了这一算法