目录

一、前言

二、VQ概述

三、Kmeans算法

K-means 的算法步骤为：

 四、Matlab代码实现过程

五、 一点点可选改动（个人看法）

参考链接： 

---

一、前言

本人对机器学习、人工智能算法方面没什么研究，只是学习过程中恰好碰到了。

一开始看Kmeans算法只是为了图像（矩阵）的VQ（vector quantization），找了网上不少资料，跟VQ相关的比较多是LBG算法，单独找kmeans跟VQ联系不起来，后面研究了一下，得到这篇博客主要想表达的内容。

二、VQ概述

        VectorQuantization (VQ)是一种基于块编码规则的有损数据压缩方法。事实上，在 JPEG 和 MPEG-4 等多媒体压缩格式里都有 VQ 这一步。它的基本思想是：将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，从而压缩了数据而不损失多少信息。

       在以前，VQ运用的一个难点在于它要要解决一个多维积分（multi-dimensional integration）的问题。后来，在1980年，Linde, Buzo和Gray（LBG，这个缩写也是LBG算法的命名）提出一种基于训练序列的VQ设计算法，对训练序列的运用绕开了多维积分的求解，使得世上又诞生了一种经典的被世人称为LBG-VQ的算法！它一直延绵至今，经典永不褪色。

三、Kmeans算法

K-means 有一个著名的解释：牧师—村民模型：

有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，于是每个村民到离自己家最近的布道点去听课。
听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。
牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点……
就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来。

K-means 的算法步骤为：

1. 选择初始化的 k 个样本作为初始聚类中心 a=a1,a2,…ak ；
2. 针对数据集中每个样本 xi 计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
3. 针对每个类别 aj ，重新计算它的聚类中心 aj=1|ci|∑x∈cix （即属于该类的所有样本的质心）；
4. 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

 四、Matlab代码实现过程

（代码由参考文献中代码修改而来）

function [W, E_in, V] = KMeans(data, K)
%W是k个中心点；E_in是聚合效果，显示所有点的平均距离;V用中心点表示的新的数据
[N, d] = size(data);             %d个n维的点
% init W
sampleIds = randsample(d, K);    %从d个点中随机选择k个点作为中心点
W = data(:,sampleIds);                   %以这k个点为中心形成簇类
labels_u = zeros(1,d);                   %初始换建立一个1行d列的零数组
stop = true;  
while stop                                %把true复制给stop，需要一直循环
    stop = false;
    for i = 1:d                           %从第1个点一直到第d个点,得到每个点与对应最近中心
        x = data(:,i);                   %读取第1个数据放到X里面
        % check label        
        label = 0;                        %初始化label为0，代表是第几个簇类
        dist = 0;                         %初始化dist距离为0
        for j = 1:K                       %计算到达三个中心点的距离，依次推断属于哪个簇类
            tmp_dist = norm(x-W(:,j));        %计算欧式距离
            if label == 0 || tmp_dist < dist       %如果是第一次计算lable=0或者此时的距离小于上一次计算出的距离
                label = j;                         %当前的点暂时属于第j个聚类
                dist = tmp_dist;                   %欧式距离更新为当前的更小值
            end                                    
        end                                        %循环结束
        if labels_u(i) == label                    %如果第个i点不等于label
            stop = stop | false;                          %继续循环
        else
            stop = stop | true;
            labels_u(i) = label;                       %第个i点属于第label个簇类
        end
    end
    if stop == false                                %退出循环
        break;
    end
    %update W                                      %更新中心点
    new_W = zeros(N, K);                           %初始化中心点，并全部清零
    labels_count = zeros(1,K);                    %统计不同簇类的个数
    for i = 1:d                                    %遍历所有点
        label = labels_u(i);                       %提取出簇类标志
        new_W(:,label) = new_W(:,label) + data(:,i);    %相同簇类data数据之和
        labels_count(label) = labels_count(label) + 1;     %属于相同簇类的点的个数
    end
    for i = 1:K   %
        new_W(:,i) = new_W(:,i)/labels_count(i);        %初始化的中心点除以每个聚类里面总的个数，求出新质心
    end
    W = new_W;                         %用新的W来代替
end
E_in = 0;
V = zeros(N,d);
for i = 1:d                            %d个点需要重新遍历
    label = labels_u(i);               %将label标签提取出来
    V(:,i) = W(:,label);                 %用中心表示新数据
    E_in = E_in + norm(data(i)-W(:,label));     %每一个点跟对应中心的距离，所有的距离应该是欧式距离的和
end
E_in = E_in/d;                         %欧式距离的和除以d,每个点距离的均值，表示聚合的效果
end

输入参数：data 为原始数据，对应一列为“一点”，列数即为“点数”；k 表示需要的聚类中心个数

输出参数：W 为得到的聚类中心；E_in 所有点到对应中心距离的平均值，表示聚合效果；V 用对应聚类中心代替原有数据得到的新数据。

由VQ的相关概念可知，V可用 V = WH 进行表示，即用V近似表示原有数据data，或用W表示data达到数据降维的效果。系数H可在上面代码中倒数第五行加入 H(label,i) = 1 ，或得到输出结果后用 H = W\V 得到，表示原来第i个数据的聚类中心为第label个。

五、 一点点可选改动（个人看法）

上面代码中，聚类中心为 聚类中的所有点 求均值所得，但是所得 中心点 一般不在原数据中，可以进行计算，在最后分好对应聚类后（最后一次循环结束前），再计算一次距离，令离中心最近的原有的点 成为中心，这样更有利于VQ。

参考链接： 

(2条消息) Matlab实现Kmeans算法（每行代码标注详细注解）_高垚淼的博客-CSDN博客_matlab kmeans

【机器学习】K-means（非常详细） - 知乎 (zhihu.com)

(3条消息) 【机器学习】【数字信号处理】矢量量化（Vector Quantization）_Zhang_P_Y的博客-CSDN博客