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

      假设要把样本集分为c个类别,算法描述如下:

   (1)适当选择c个类的初始中心;

   (2)在第k次迭代中,对任意一个样本,求其到c个中心的距离,将该样本归到距离最短的中心所在的类;

   (3)利用均值等方法更新该类的中心值;

   (4)对于所有的c个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变,则迭代结束,否则继续迭代。

该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

     算法缺点:

   (1) k值必须给定
 
 进行k-means算法时,必须指定聚类数量。但是有时候我们并不知道应该聚成多少个类,而是希望算法可以给出一个合理的聚类数量,往往一开始k值很难预先估计并给定。

   (2) 随机的k个中心点影响结果
 
 在k-means算法中,一开始的k个中心点是随机选定的,在后面的迭代中再进行重算,直到收敛。但是根据算法的步骤不难看出,这样一来最后所生成的结果往往很大程度上取决于一开始K个中心点的位置。这样一来,也就意味着结果具备很大的随机性,每次计算结果都会因为初始随机选择的中心质点不一样而导致结果不一样。

   (3)计算性能
该算法需要不断的对对象进行分类调整,不断的计算调整后新的聚类中心点,因此当数据量非常大时,算法的时间开销是非常大的。


OpenCV代码:
#include <iostream> #include <opencv2/opencv.hpp> #include <iostream> using
namespace std; using namespace cv; int main() { const int MAX_CLUSTERS = 5;
Vec3b colorTab[] = { Vec3b(0, 0, 255), Vec3b(0, 255, 0), Vec3b(255, 100, 100),
Vec3b(255, 0, 255), Vec3b(0, 255, 255) }; Mat data, labels; Mat pic =
imread("../img/66.png"); for (int i = 0; i < pic.rows; i++) //像素点线性排列 for (int
j = 0; j < pic.cols; j++) { Vec3b point = pic.at<Vec3b>(i, j); Mat tmp =
(Mat_<float>(1, 3) << point[0], point[1], point[2]); data.push_back(tmp); }
//根据浏览图片,确定k=3 kmeans(data, 3, labels, TermCriteria(TermCriteria::EPS +
TermCriteria::COUNT, 10, 1.0),3, KMEANS_RANDOM_CENTERS); int n = 0;
//显示聚类结果,不同的类别用不同的颜色显示 for (int i = 0; i < pic.rows; i++) for (int j = 0; j <
pic.cols; j++) { int clusterIdx = labels.at<int>(n); pic.at<Vec3b>(i, j) =
colorTab[clusterIdx]; n++; } imshow("K-means聚类算法", pic); waitKey(0); return 0; }
   原图:



处理后: