首次接触k-means算法是在大二参加华中地区数学建模时，题目是对各搜索引擎进行评价，在进行搜索结果文本分析的时候，稀里糊涂就用了k-means，现在趁着机器学习的作业，重新学习了一下。

K-means通常作为一种聚类分析方法流行于数据挖掘领域，其目的是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准[1]。K-means聚类是无监督机器学习中常用的算法，所谓无监督（无教师）学习，指拿到一堆数据，不知道其类别信息，直接丢给学习算法，算法根据数据特征，自动将数据分类。例如，有一堆水果混杂在一起，并不知道它们的名字，我们按照它们的特征（长的，圆的，有刺的）分成几堆，后来有人告诉我们这分别是香蕉、苹果和榴莲。我们并不知道这些水果的类别信息，但我们却能大体将其归类，这个性质特别实用，因为在实际中我们往往缺乏先验知识，拿到的是密密麻麻的一堆数据，如果直接喂给模型来学习可能会比较低效。于是k-means作为无监督的聚类算法，通常用于数据的预处理，实现大体上的分类，随后再进行更精细的处理。K-means有个很著名的解释，牧师—村民模型[2]：

有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的居民，于是每个居民到离自己家最近的布道点去听课。

听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的居民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。

牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个居民又去了离自己最近的布道点……

就这样，牧师每个礼拜更新自己的位置，居民根据自己的情况选择布道点，最终稳定了下来。

这便是K-means算法的过程：无监督的，自组织的，下面给出算法的具体描述。

Step1：聚类中心向量初始化。确定J个初始化聚类中心 C_0 = [C_10, C_20,...,C_J0]，作为初始向量中心；

Step2：数据输入及对应的聚类选择。输入数据x_i，选择最近的聚类 j*：C_j* = argmin ||x_i - C_j||，对全部数据进行操作，一般选择欧氏距离，对于不同的问题，要找到合适的距离的量化方法；

Step3：聚类中心向量的更新：C_j = 1/N sum_(x in xluster(j))x，其中 N_j是属于j聚类的数据数目；

Step4：判定，如果全部聚类中心向量没有变化，停止，否则返回step2.

 

K-means算法及其MATLAB代码都较为简单，且MATLAB中已有写好的的kmeans函数，可以直接调用，为具体分析该算法，下面给出自己写的代码：

function [CentCluster, idx] = mykmeans(x, k, MaxNum)

 %% 函数实现kmeans聚类

 % 输入： 样本集x, 聚类中心个数k 和最大迭代次数MaxNum

 % 输出： CentCluster为聚类中心，idx为样本的类别标记

 %%

[m, n] = size(x);  % m为样本个数，n 为样本维数

CentCluster = zeros(k, n);  % 聚类中心初始化

for j = 1:k

    CentCluster(j, :) = min(x) + rand(1, n) .* (max(x) - min(x));

end

idx = zeros(m, 1);  % 样本标记初始化

for iter = 1:MaxNum %  最大迭代次数

 % 为每个输入数据x_i, 选择最近的聚类c_j: c_j = argmin || x_i - c_j ||, idx用以记录   

    for i = 1:m

        temp = inf;

        for j = 1:k

            if norm(x(i, :) - CentCluster(j, :)) <= temp

                temp = norm(x(i, :) - CentCluster(j)); 

                idx(i) = j;

            end

        end

    end

 % 更新聚类中心向量：c_j = 1 / N_j * sum_(x in cluster(j)) x , 其中，N_j 是属于 j 聚类的数据数目

 % 即求出某一类数据（以离上一次聚类中心最近为划分）的距离均值

    for j = 1:k

        CentCluster(j, :) = 1 / sum(idx == j) * sum(x(find(idx == j), :), 1);

    end

end

%%

%以下为聚类结果的图示

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(x(idx == 3, 1), x(idx == 3, 2), 'g.', 'MarkerSize', 12)

plot(x(idx == 4, 1), x(idx == 4, 2), 'c.', 'MarkerSize', 12)

plot(CentCluster(:, 1), CentCluster(:, 2), 'kx', 'MarkerSize', 12, 'LineWidth', 2)

plot(CentCluster(:, 1), CentCluster(:, 2), 'ko', 'MarkerSize', 12, 'LineWidth', 2)

end

为了测试算法的性能，首先找了一个数据集，一共80个二维样本，设置聚类个数为4，测试结果如下：

http://s16/mw690/0047A2O8zy7c6w4KBd50f&690
为了进一步评测算法，利用[3]中对图像处理的部分MATLAB代码，调用mykmeans函数对图像进行分割，代码如下：

function kmeans_segmentation()

    clear;close all;clc;

    %% 读取测试图像

    im = imread('city.png');

    imshow(im), title('Original Image');  %%转换图像的颜色空间得到样本

    cform = makecform('srgb2lab');   

k = 4;  % 聚类个数

    lab = applycform(im,cform);

    ab = double(lab(:,:,2:3));

    nrows = size(lab,1); ncols = size(lab,2);

    X = reshape(ab,nrows*ncols,2)';

    figure, scatter(X(1,:)',X(2,:)',3,'filled'),title('Cluster Membership'); 

box on; %显示颜色空间转换后的二维样本空间分布

    %% 对样本空间进行Kmeans聚类

    max_iter = 100; %最大迭代次数

    [centroids, labels] = mykmeans(X', k, ma x_iter);

    %% 显示聚类分割结果

    pixel_labels = reshape(labels,nrows,ncols);

    rgb_labels = label2rgb(pixel_labels);

    figure, imshow(rgb_labels), title('Segmented Image');

    %print -dpdf Seg.pdf

  end

该函数首先读入一副图像，并将RGB空间的图片转换为LAB空间的分布图，调用mykmeans函数对空间各点进行聚类，最后根据聚类结果将LAB图转化为RGB图像。

http://s1/mw690/0047A2O8zy7c6w75LoY90&690        http://s11/mw690/0047A2O8zy7c6w78BT49a&690

上图分别是原始图像，利用k-means算法分割后的图像以及LAB空间的聚类结果，直观上来看，图像的分割还是比较合理的。下图是埃菲尔铁塔（你能信这么美的照片是我用手机拍出来的）的分割结果：

       http://s9/bmiddle/0047A2O8zy7c6wkdFr288&690

         http://s15/bmiddle/0047A2O8zy7c6wkhpM23e&690
  

 2017年6月23日晚于实验室

                                                                                               

[1]https://zh.wikipedia.org/wiki/K-平均算法

[2] https://zhuanlan.zhihu.com/p/20432322

[3] http://blog.csdn.net/autocyz/article/details/46773143