【基础方法】聚类方法(K-means、FCM)

以前通常做的都是分类的问题,虽然说聚类也可以用于分类,但是这方面涉及的比较少,只大概了解了相关的概念。这次简单地介绍学习建模时候看到的三种聚类方法:K-means算法和FCM算法。

K-means聚类方法

K-means聚类方法通过均值进行聚类,每个原始的元素经过聚类后都属于并且只属于某一个类。这是一种严格划分的方法,也可称为硬划分(HCM)。
   对于给定的含有$n$个元素的数据集$X$,$x_k$是其中第$k$个元素,$1\leqslant k\leqslant n$。将该数据集聚类为$C$个类,聚类后新的聚类中心集合为$P$,$p_i$是其中第$i$个聚类中心,$1\leqslant k\leqslant C$,则目标函数如下:
$$J_0(X,P)=\sum_{i=1}^{C}\sum_{x_k\in X}(d_{ki})^2$$
其中$d_{ik}$为第$k$个元素和第$i$个聚类中心的失真度,通常用距离表示,如欧氏距离。
   算法的具体流程如下:

  1. 在数据集$X$中任取$C$个元素,作为初始类别。
  2. 通过最近邻方法求出每个元素属于哪一个类,并计算出目标函数$J_0$的值。
  3. 计算每一类的均值,作为新的聚类中心。
  4. 若$J_0$小于某一个值,或者迭代后新的$J_0$与上一次$J_0$相差小于某个值,则停止;否则转步骤二。

该算法需要预先给定聚类的类别数目,并且受到初始位置的影响。在该算法的基础上,提出了一种二分k-means算法,算法流程如下:

  1. 将原数据集先通过k-means分成两类。
  2. 将每个类依次再分成两类,并计算出每个类二分时对应的目标函数。
  3. 选取最小的目标函数值对应的类,进行二分。
  4. 若当前的类别数达到目标类别数,则停止聚类;否则,转到步骤二。

matlab代码

虽然matlab自带kmeans函数,但我还是写了一遍,主要的问题就是生成点了,具体代码如下:

function [U,P] = K_means( X, C )
% 本函数通过K-means方法,将原有数据集聚类,得到C个类。
% 输入:
% X:数据集(n*t)
%    n:数据个数
%    t:数据维数
% C:目标聚类类别数
% 输出:
% U:聚类结果矩阵(n*1)
% P: 聚类中心

% 初始参数设置
[n,~]=size(X);
maxiter=1000;
j0=0;
dvalue=1*10^(-9);
U=zeros(n,1);

% 随机取一些数作为初始聚类中心
ind=randperm(n, C);
P=X(ind,:);

for m=1:maxiter
    j1=0;
    for i=1:n
        d=pdist2(P, X(i,:), 'Euclidean');
        [dist,U(i)]=min(d);
        j1=dist*dist+j1;
    end
    
    if abs(j1-j0)<dvalue
        break
    end
    
    for i=1:C
        P(i,:)=sum(X(U==i,:))/sum(U==i);
    end
    j0=j1;
end

end

主函数:

% % 生成数据
% n=50;
% b=40;
% x(1:n,1:2)=bsxfun(@plus,rand(n,2)*b,[25,25]);
% x(n+1:2*n,1:2)=bsxfun(@plus,rand(n,2)*b,[25,75]);
% x(2*n+1:3*n,1:2)=bsxfun(@plus,rand(n,2)*b,[75,75]);
% x(3*n+1:4*n,1:2)=bsxfun(@plus,rand(n,2)*b,[75,25]);
% save x2.mat x;

% C=4;
% [U, P]=K_means(x,C);
% % 画点
figure;
for i=1:C
    hold on;
    x1=x((U==i),1);
    y1=x((U==i),2);
    scatter(x1,y1);
end

聚类结果如下,对于随机生成的0~100范围内100个点,写的算法分类结果如下:


   matlab自带的k-means聚类函数聚类结果如下:


   这样的数据点太离散,聚类结果看不出什么,我改变了原始的数据点,聚类结果如下:


   matlab自带的k-means聚类函数聚类结果如下:

FCM聚类算法

FCM(Fuzzy C-means)算法,也称模糊C均值算法,是一种通过隶属度(每一个元素属于某个类的程度)进行聚类的柔性划分算法。它通过描述每个元素属于某个类的不确定程度进行软聚类。
   对于给定的含有$n$个元素的数据集$X$,$x_k$是其中第$k$个元素,$1\leqslant k\leqslant n$。将该数据集聚类为$C$个类,聚类后新的聚类中心集合为$P$,$p_i$是其中第$i$个聚类中心,$1\leqslant k\leqslant C$。
   FCM算法通常用一个模糊矩阵描述划分结果。对于K-means聚类方法来说,它的分类矩阵由0和1构成,是一个布尔矩阵。对于FCM算法而言,模糊矩阵 $U=(u_{ki})_{n*c}$ ,其中$0\leqslant u_{ki}\leqslant 1$为隶属度,表示第$k$个元素属于第$i$个类的程度。目标函数如下:
$$J_1(X,P)=\sum_{i=1}^{C}\sum_{x_k\in X}{u_{ki}^m(d_{ki})^2}$$
   约束条件:
$$
\forall k, \sum_{i=1}^{C}{u_{ki}}=1
$$
$$
\forall i, \sum_{k=1}^{n}{u_{ki}}>0
$$
其中$m$是加权指数,一般大于1。
   使用拉格朗日乘子方法对目标函数求导,得到聚类中心和隶属度计算方法如下:
$$
p_i=\frac{\sum_{j=1}^{n}{u_{ji}^{m}x_j}}{\sum_{j=1}^{n}{u_{ji}^{m}}}
$$
$$
u_{ki}=\frac{1}{\sum_{j=1}^{C}{(\frac{d_ki}{d_kj})^{\frac{2}{m-1}}}}
$$
   算法流程如下:

  1. 随机初始划分,得到$U$。
  2. 得到聚类中心。
  3. 计算得到目标函数$J_0$的值。
  4. 若$J_0$小于某一个值,或者迭代后新的$J_0$与上一次$J_0$相差小于某个值,则停止;否则更新模糊矩阵,转步骤二。

参考博客:
https://www.cnblogs.com/xiaohuahua108/p/6187178.html
https://blog.csdn.net/taoyanqi8932/article/details/53727841
https://www.cnblogs.com/sddai/p/6259553.html