K-means算法算是个著名的聚类算法了，不仅容易实现，并且效果也不错，训练过程不需人工干预，实乃模式识别等领域的居家必备良品啊，今天就拿这个算法练练手。属于无监督学习中间接聚类方法中的动态聚类
流程：
1.随机选取样本中的K个点作为聚类中心 2.计算所有样本到各个聚类中心的距离，将每个样本规划在最近的聚类中 3.计算每个聚类中所有样本的中心，并将新的中心代替原来的中心 4.检查新老聚类中心的距离，如果距离超过规定的阈值，则重复2-4，直到小于阈值
聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。
在聚类问题中，给我们的训练样本是，每个，没有了y。
K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：
1、 随机选取k个聚类质心点（cluster centroids）为。
2、 重复下面过程直到收敛 {
对于每一个样例i，计算其应该属于的类
对于每一个类j，重新计算该类的质心
K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。
下图展示了对n个样本点进行K-means聚类的效果，这里k取2。
参考;http://blog.csdn.net/holybin/article/details/22969747
Kmeans有以下几个优点：
1、是解决聚类问题的一种经典算法，算法简单、快速。
2、对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度是线性的，大约是O（nkt），其中n是所有样本的数目，k是簇的数目,t是迭代的次数。通常k<<n。
3、该算法是收敛的（不会无限迭代下去）。
4、算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。
Kmeans也存在如下缺点：
1、只有在簇的平均值被定义的情况下才能使用，不适用于某些应用，如涉及有分类属性的数据不适用。它的前提假设是样本数据的协方差矩阵已经归一化。
2、虽然理论证明它是一定可以收敛的，但是不能保证是全局收敛，可能是局部收敛，这样的话找到的聚类中心不一定是最佳方案。
3、要求用户必须事先给出要生成的簇的数目K。对于同一个数据样本集合，选择不同的K值，得到的结果是不一样的，甚至是不合理的。
4、对中心初值敏感，对于不同的初始值，可能会导致不同的聚类结果。
5、对于"噪声"和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。
6、不适合于发现非凸面形状的簇，或者大小差别很大的簇。
CV_EXPORTS_W double kmeans( InputArray data, int K, InputOutputArray bestLabels, TermCriteria criteria, int attempts, int flags, OutputArray centers = noArray() ); 注意，在opencv中，kmeans（）函数是在core.h头文件中的，所以首先要包含这个头文件。下面分析其参数： 1 InputArray data：输入的待聚类向量，其中每一行是一个样本，有多少列，就有多少个样本。 2 int K： 要聚类的个数。 3 InputOutputArray bestLabels：行数与data是一样的，每行有一个数字，代表分类的编号。比如聚类的数目是8类，那么每行的数字在0-3。 4 TerCriteria criteria：这个变量用于控制结束条件。其中TerCriteria是一个模板类，在opencv中的定义如下： TermCriteria::TermCriteria(int _type, int _maxCount, double _epsilon) : type(_type), maxCount(_maxCount), epsilon(_epsilon) {} 其中，type的类型有三种： TermCriteria::COUNT： 代表以运行的步数为结束条件。 TermCriteria::EPS： 代表迭代到阈值时结束。 TermCriteria::COUNT + TermCriteria::EPS：当步数或阈值中有一个达到条件时终止。 _maxCount是运行的步数，_epsilon是阈值。 5 int attempts：这个变量控制kmean算法进行的次数，选择最优的结果做为最后结果。 6 int flags：这个变量可以取以下三个类型。 KMEANS_RANDOM_CENTERS：随机选择初始中心。 KMEANS_PP_CENTERS：以一种算法，确定初始中心。 KMEANS_USE_INITIAL_LABELS：用户自定义中心。 7 centers：这个变量代表具体的聚类中心。 下面来看一个例子#include "opencv2/highgui/highgui.hpp" #include "opencv2/core/core.hpp" #include <iostream> using namespace cv; using namespace std; int main( int /*argc*/, char** /*argv*/ ) { const int MAX_CLUSTERS = 5; Scalar colorTab[] = { Scalar(0, 0, 255), Scalar(0,255,0), Scalar(255,100,100), Scalar(255,0,255), Scalar(0,255,255) }; Mat img(500, 500, CV_8UC3); RNG rng(12345); for(;;) { int k, clusterCount = rng.uniform(2, MAX_CLUSTERS+1); int i, sampleCount = rng.uniform(1, 1001); Mat points(sampleCount, 1, CV_32FC2), labels; clusterCount = MIN(clusterCount, sampleCount); Mat centers(clusterCount, 1, points.type()); /* generate random sample from multigaussian distribution */ for( k = 0; k < clusterCount; k++ ) { Point center; center.x = rng.uniform(0, img.cols); center.y = rng.uniform(0, img.rows); Mat pointChunk = points.rowRange(k*sampleCount/clusterCount, k == clusterCount - 1 ? sampleCount : (k+1)*sampleCount/clusterCount); rng.fill(pointChunk, CV_RAND_NORMAL, Scalar(center.x, center.y), Scalar(img.cols*0.05, img.rows*0.05)); } randShuffle(points, 1, &rng); kmeans(points, clusterCount, labels, TermCriteria( CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 10, 1.0), 3, KMEANS_PP_CENTERS, centers); img = Scalar::all(0); for( i = 0; i < sampleCount; i++ ) { int clusterIdx = labels.at<int>(i); Point ipt = points.at<Point2f>(i); circle( img, ipt, 2, colorTab[clusterIdx], CV_FILLED, CV_AA ); } imshow("clusters", img); char key = (char)waitKey(); if( key == 27 || key == 'q' || key == 'Q' ) // 'ESC' break; } return 0; }
matlab
K-means聚类算法采用的是将N*P的矩阵X划分为K个类，使得类内对象之间的距离最大,而类之间的距离最小。
使用方法：
Idx=Kmeans(X,K)
[Idx,C]=Kmeans(X,K)
[Idx,C,sumD]=Kmeans(X,K)
[Idx,C,sumD,D]=Kmeans(X,K)
[…]=Kmeans(…,’Param1’,Val1,’Param2’,Val2,…)
各输入输出参数介绍：
X N*P的数据矩阵
K 表示将X划分为几类，为整数
Idx N*1的向量，存储的是每个点的聚类标号
C K*P的矩阵，存储的是K个聚类质心位置
sumD 1*K的和向量，存储的是类间所有点与该类质心点距离之和
D N*K的矩阵，存储的是每个点与所有质心的距离
[…]=Kmeans(…,'Param1',Val1,'Param2',Val2,…)
这其中的参数Param1、Param2等，主要可以设置为如下：
1. ‘Distance’(距离测度)
‘sqEuclidean’ 欧式距离（默认时，采用此距离方式）
‘cityblock’ 绝度误差和，又称：L1
‘cosine’ 针对向量
‘correlation’ 针对有时序关系的值
‘Hamming’ 只针对二进制数据
2. ‘Start’（初始质心位置选择方法）
‘sample’ 从X中随机选取K个质心点
‘uniform’ 根据X的分布范围均匀的随机生成K个质心
‘cluster’ 初始聚类阶段随机选择10%的X的子样本（此方法初始使用’sample’方法）
matrix 提供一K*P的矩阵，作为初始质心位置集合
3. ‘Replicates’（聚类重复次数） 整数
<span style="font-size:18px;">X = [randn(100,2)+ones(100,2);... randn(100,2)-ones(100,2)]; opts = statset('Display','final'); [idx,ctrs] = kmeans(X,2,... 'Distance','city',... 'Replicates',5,... 'Options',opts); plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12) hold on plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12) plot(ctrs(:,1),ctrs(:,2),'kx',... 'MarkerSize',12,'LineWidth',2) plot(ctrs(:,1),ctrs(:,2),'ko',... 'MarkerSize',12,'LineWidth',2) legend('Cluster 1','Cluster 2','Centroids',... 'Location','NW') </span>
图像识别算法交流 QQ群：145076161，欢迎图像识别与图像算法，共同学习与交流
