现在的位置: 首页 > 综合 > 正文

聚类算法 K-means

2019年01月06日 ⁄ 综合 ⁄ 共 4390字 ⁄ 字号小中大 ⁄ 评论关闭

聚类算法——K-means

原文地址 http://www.cnblogs.com/moondark/archive/2012/03/08/2385770.html

首先要来了解的一个概念就是聚类，简单地说就是把相似的东西分到一组，同 Classification (分类)不同，对于一个 classifier ，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做 supervised learning (监督学习)，而在聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需要知道如何计算相似
度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在 Machine Learning 中被称作 unsupervised learning (无监督学习)。

　　我们经常接触到的聚类分析，一般都是数值聚类，一种常见的做法是同时提取 N 种特征，将它们放在一起组成一个 N 维向量，从而得到一个从原始数据集合到 N 维向量空间的映射——你总是需要显式地或者隐式地完成这样一个过程，然后基于某种规则进行分类，在该规则下，同组分类具有最大的相似性。

　　假设我们提取到原始数据的集合为(x₁, x₂, …, x_n)，并且每个xi为d维的向量，K-means聚类的目的就是，在给定分类组数k（k ≤ n）值的条件下，将原始数据分成k类
S = {S₁, S₂, …, S_k}，在数值模型上，即对以下表达式求最小值：
$\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - \boldsymbol\mu_i \right\|^2$
这里μ_i 表示分类S_i的平均值。

　　那么在计算机编程中，其又是如何实现的呢？其算法步骤一般如下：

1、从D中随机取k个元素，作为k个簇的各自的中心。

2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。

3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。

4、将D中全部元素按照新的中心重新聚类。

5、重复第4步，直到聚类结果不再变化。

6、将结果输出。

　　用数学表达式来说，

设我们一共有 N 个数据点需要分为 K 个 cluster ，k-means 要做的就是最小化

$\displaystyle J = \sum_{n=1}^N\sum_{k=1}^K r_{nk} \|x_n-\mu_k\|^2$

这个函数，其中 $r_{nk}$ 在数据点
n 被归类到 cluster k 的时候为 1 ，否则为 0 。直接寻找 $r_{nk}$ 和 $\mu_k$ 来最小化并不容易，不过我们可以采取迭代的办法：先固定 $\mu_k$ ，选择最优的 $r_{nk}$ ，很容易看出，只要将数据点归类到离他最近的那个中心就能保证最小。下一步则固定 $r_{nk}$ ，再求最优的 $\mu_k$ 。将对 $\mu_k$ 求导并令导数等于零，很容易得到最小的时候 $\mu_k$ 应该满足：

$\displaystyle \mu_k=\frac{\sum_n r_{nk}x_n}{\sum_n r_{nk}}$

亦即 $\mu_k$ 的值应当是所有
cluster k 中的数据点的平均值。由于每一次迭代都是取到的最小值，因此只会不断地减小（或者不变），而不会增加，这保证了
k-means 最终会到达一个极小值。虽然 k-means 并不能保证总是能得到全局最优解，但是对于这样的问题，像 k-means 这种复杂度的算法，这样的结果已经是很不错的了。

首先 3 个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色，如下图所示：

iter_00

然后进入第一次迭代：按照初始的中心点位置为每个数据点着上颜色，重新计算 3 个中心点，结果如下图所示：

iter_01

可以看到，由于初始的中心点是随机选的，这样得出来的结果并不是很好，接下来是下一次迭代的结果：

iter_02

可以看到大致形状已经出来了。再经过两次迭代之后，基本上就收敛了，最终结果如下：

iter_04

不过正如前面所说的那样 k-means 也并不是万能的，虽然许多时候都能收敛到一个比较好的结果，但是也有运气不好的时候会收敛到一个让人不满意的局部最优解，例如选用下面这几个初始中心点：

iter_00_bad

最终会收敛到这样的结果：

iter_03_bad

　　整体来讲，K-means算法的聚类思想比较简单明了，并且聚类效果也还算可以，算是一种简单高效应用广泛的 clustering 方法，接下来，我将讨论其代码实现过程。

　K-means的源码实现

　　一般情况下，我们通过C++/Matlab/Python等语言进行实现K-means算法，结合近期我刚刚学的C++，先从C++实现谈起，C++里面我们一般采用的是OpenCV库中写好的K-means函数，即cvKmeans2，首先来看函数原型：
　　从OpenCV manual看到的是：
int cvKMeans2(const CvArr* samples, int nclusters,
　　　　　　　 CvArr* labels, CvTermCriteria termcrit,
　　　　　　　 int attempts=1, CvRNG* rng=0,int flags=0,
　　　　　　　 CvArr* centers=0,double* compactness=0);
由于除去已经确定的参数，我们自己需要输入的为：
void cvKMeans2(
  　　const CvArr* samples, //输入样本的浮点矩阵，每个样本一行。
  　　int cluster_count,  //所给定的聚类数目
   　　* labels,    //输出整数向量：每个样本对应的类别标识
   　　CvTermCriteria termcrit //指定聚类的最大迭代次数和／或精度（两次迭代引起的聚类中心的移动距离）
);

可以参考 opencv论坛上的介绍

http://wiki.opencv.org.cn/index.php/Cxcore%e5%85%b6%e5%ae%83%e6%b7%b7%e5%90%88%e5%87%bd%e6%95%b0

也可以参考opencv官方网站的资源

http://www.aishack.in/2010/08/k-means-clustering-in-opencv/

http://docs.opencv.org/modules/core/doc/clustering.html

附上一个对图像的颜色聚类的例子

#include <cv.h>
#include <cxcore.h>
#include <highgui.h>

// KMeans2
// 按照给定的类别数目对样本集合进行聚类
//
// void cvKMeans2( const CvArr* samples, int cluster_count,
// CvArr* labels, CvTermCriteria termcrit );
// samples
// 输入样本的浮点矩阵，每个样本一行。
// cluster_count
// 所给定的聚类数目
// labels
// 输出整数向量：每个样本对应的类别标识
// termcrit
// 指定聚类的最大迭代次数和／或精度（两次迭代引起的聚类中心的移动距离）
// 函数 cvKMeans2 执行 k-means 算法搜索 cluster_count 个类别的中心并对样本进行分类，输出 labels(i) 为样本 i 的类别标识。

void main()
{
IplImage* img=cvLoadImage("sample.bmp");//加载图像，图像放在Debug文件夹里，这里是相对路径

cvNamedWindow( "原始图像", 1 ); //创建窗口
cvShowImage( "原始图像", img ); //显示图像
// cvWaitKey(0); //等待按键


int i,j;
CvMat *samples=cvCreateMat((img->width)*(img->height),1,CV_32FC3);//创建样本矩阵，CV_32FC3代表32位浮点3通道（彩色图像）
CvMat *clusters=cvCreateMat((img->width)*(img->height),1,CV_32SC1);//创建类别标记矩阵，CV_32SF1代表32位整型1通道

int k=0;
for (i=0;i<img->width;i++)
{
for (j=0;j<img->height;j++)
{
CvScalar s;
//获取图像各个像素点的三通道值（RGB）
s.val[0]=(float)cvGet2D(img,j,i).val[0];
s.val[1]=(float)cvGet2D(img,j,i).val[1];
s.val[2]=(float)cvGet2D(img,j,i).val[2];
cvSet2D(samples,k++,0,s);//将像素点三通道的值按顺序排入样本矩阵
}
}

int nCuster=2;//聚类类别数，自己修改。
cvKMeans2(samples,nCuster,clusters,cvTermCriteria(CV_TERMCRIT_ITER,100,1.0));//开始聚类，迭代100次，终止误差1.0

IplImage *bin=cvCreateImage(cvSize(img->width,img->height),IPL_DEPTH_8U,1);//创建用于显示的图像，二值图像
k=0;
int val=0;
float step=255/(nCuster-1);

for (i=0;i<img->width;i++)
{
for (j=0;j<img->height;j++)
{
val=(int)clusters->data.i[k++];
CvScalar s;
s.val[0]=255-val*step;//这个是将不同类别取不同的像素值，
cvSet2D(bin,j,i,s); //将每个像素点赋值
}
}

cvNamedWindow( "聚类图像", 1 ); //创建窗口
cvShowImage( "聚类图像", bin ); //显示图像
cvWaitKey(0); //等待按键

cvDestroyWindow( "原始图像" );//销毁窗口
cvReleaseImage( &img ); //释放图像
cvDestroyWindow( "聚类图像" );//销毁窗口
cvReleaseImage( &bin ); //释放图像

}

【上篇】LoG 和 DoG的本质联系与区别
【下篇】C++精确获取时间（QueryPerformanceCounter）

作者: llano

该日志由 llano 于5年前发表在综合分类下，最后更新于 2019年01月06日.
转载请注明: 聚类算法 K-means | 学步园 +复制链接

抱歉!评论已关闭.

学步园