K-means 聚类算法学习笔记

K-means 聚类算法 是一种无监督学习算法，用来将 $n$ 个样本点分成 $k$ 类，使得整个数据集的误差平方和 $SSE$ 最小。在本例中，样本点是指平面直角坐标系上的点，聚类中心也是平面直角坐标系上的点，而每个点的损失函数则是它到聚类中心的距离。即：找出 2 个点，使得所有点到这 2 个点的距离的更小者之和最小。

K-means 聚类算法流程如下：

随机指定 $k$ 个样本点为聚类中心；
计算所有点对每个样本点的距离，选择最近的样本点；
计算同一类的所有点的重心，并将重心作为新的聚类中心；
重复2.3.，直到所有点选定的最近样本点均不再改变。

其中

$SSE=\sum_{i=1}^{k}\sum_{x\in C_i}\sum_{j=1}^m(x_j-S_{ij})^2$

理论上说， $SSE$ 会随着 $k$ 的变大而单调递减。

参考文献。

function [ClusterID,Means] = KMeansClustering(S, K, plot_flag)
% 输入参数：
% S: 用于聚类的数据，每一行对应一个样本的特征向量，每一列对应一个特征
% K：需要聚成的簇的数量
% plot_flag: 是否需要可视化每一次迭代的更新结果

% 输出参数：
% ClusterID：聚类结果，表示每个样本被聚类至第几个簇
% Means：由簇中心向量组成的矩阵，每一行对应一个簇的中心

%% 初始参数设置
maxiter = 10000;            % 这里的maxiter为迭代算法设置了最大迭代次数，防止算法陷入死循环
iter = 0;                   % 用于表示当前算法已迭代的次数
n = size(S, 1)             % 样本数量

%% 随机初始化聚类均值
ClusterID = zeros(n,1);
rk = randperm(n);
k=rk(1:K);
Means= S(k,:);

%% 开始迭代优化
while iter<maxiter
    OldClusterID = ClusterID;
    %% 将样本分配到距离自己最近的簇中
    
    %%% ###### 需要你完成: ###### %%%
    % 1. 计算每个样本到聚类中心的距离Dist
    Dist = zeros(n,K);
    for i=1:n
        for j=1:K
            for l=1:size(S,2)
                Dist(i,j)=Dist(i,j)+(S(i,l)-Means(j,l))^2;
            end
        end
    end
    % 2. 根据每个样本到各个簇的距离，把每个样本指定到与自己最近的簇中，并生成簇结果ClusterID
     dis=size(n,1);
     [dis,ClusterID]=min(Dist,[],2);

%     Dist
%      ClusterID
%     k
%     pause(1)
% end
    %%% ######################### %%%
    %% 根据新分配的样本，重新计算簇中心
    % 按簇更新
    for i = 1:K
    
        %%% ###### 需要你完成: ###### %%%
        % 1. 首先找到属于该簇的样本
        id = zeros(n,1);
        cnt=0;
        for j=1:n
            if ClusterID(j)==i
                cnt=cnt+1;
                id(cnt)=j;
            end
        end
        % 2. 根据上一步得到的属于该簇的样本，计算这些样本的均值作为该簇的中心Means(i,:)
        Means(i,:) = zeros(size(S,2),1);
        for j=1:size(S,2)
            for l=1:cnt
                Means(i,j)=Means(i,j)+S(id(l),j);
            end
            Means(i,j)=Means(i,j)/cnt;
        end
        %%% ######################### %%%
    end
    
    %% 对每一次迭代的结果进行可视化
    if plot_flag == 1
        if iter==0
            figure
        end
    i1 = find(ClusterID==1);
    i2 = find(ClusterID==2);
    plot_cluster(S,i1,i2,Means);
    title(cat(2,'第',int2str(iter+1),'轮聚类结果'));
    set(gca,'fontsize',15)
    pause(1)
    end
    
    %% 判断迭代退出的条件
    if ClusterID == OldClusterID
        break;
    end
    iter = iter+1;
end