K-Means方法 & fuzzy C-Means方法

算法描述

核心思想：

• k-means方法

  • 无监督聚类算法，输入数据为样本矩阵$D=[x_1,x_2,...x_n]$，目标是获得簇划分C={C1,C2,...,Ck}C=\{C_1,C_2,...,C_k\}C={C1​,C2​,...,Ck​}，每个簇对应簇心u={u1,u2,...,uk}u=\{u_1,u_2,...,u_k\}u={u1​,u2​,...,uk​}

  • 同时做出假设，样本$x_i$所属类别为距离其最近的簇心对应类别

  • 聚类的优劣可以通过划分的k个簇的集中程度来表示

  • K-Means算法的核心目的为最小化各样本到其对应簇簇心距离之和，即最小化：
    $$J=\sum _{i=1}^k\sum _{x\in C_i}^k||x_{-}{u}_i|{|}_2^2$$

• fuzzy C-Means方法：

  • 对于k-means方法，每个样本对应唯一的类别

  • 当样本无法划分出明显分离的簇时，指派一个样本到一个特定的簇可能出错，因此对每个样本和每个簇赋予一个权值表明该样本属于该簇的程度

  • 与k-means方法相比，优化目标中增加了参数$f_{ij}$用来表示样本$x_i$属于j类的程度
    $$J=\sum _{i=1}^k\sum _{x\in C_i}^k{f}_{ij}^m||x-u_i|{|}_2^2$$

相关定义：

• 指示矩阵F：矩阵大小为N*C（样本数*类别数）；该矩阵每个行向量$F_i$与样本$x_i$对应，当$x_i$为第c类样本，$F_{ic}=1$且$F_i$其他元素为0

  相关计算：
  $$\begin{gathered} \underset{C\ast C}{F^{T}F}=\left[\begin{array}{cccc}{n}_1& 0& ...& 0\\ 0& n_2& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& n_c\end{array}\right] \\ (n_i为第i类样本的数量) \end{gathered}$$

  $$\begin{gathered} XF=[\sum _j{x}_j^1,\sum _j{x}_j^2,...,\sum _j{x}_j^C] \\ (x_j^c代表第c类的第j个样本；XF的列向量X_{\_j}代表第j类样本向量之和) \end{gathered}$$

• 均值矩阵M：用于表示各簇样本向量均值（簇中心）
  $$\begin{gathered} M=[u_1,u_2,...u_c]=XF(F^{T}F{)}^{-1} \\ (u_i为第i类样本均值) \end{gathered}$$

  $$\begin{gathered} M{F}^T=[u_{c1},u_{c2},...,u_{cn}] \\ (u_{ci}代表第i个样本对应类别的均值) \end{gathered}$$

目标优化推导：

• K-Means方法

  • 目标函数：
    $$J=\sum _{i=1}^k\sum _{x\in C_i}^k||x-c_i|{|}_2^2=\sum _{i=0}^k\sum _{j=0}^N||x_i-u_j||f_{ij}$$
    $f_{ij}$为指示矩阵i行j列内容，表示样本$x_i$是否为第j类，若是，则为1，否则为0

  • 优化内容：
    arg minF,M∑i=0k∑j=0N∣∣xi−uj∣∣fijs.t.  ∑j=1Cfij=1  (fij∈{0,1}) \underset{F,M}{arg\ min}\sum_{i=0}^k\sum_{j=0}^N||x_i-u_j||f_{ij}\\ s.t.\ \ \sum_{j=1}^Cf_{ij}=1\ \ (f_{ij}\in\{0,1\}) F,Marg min​i=0∑k​j=0∑N​∣∣xi​−uj​∣∣fij​s.t.  j=1∑C​fij​=1  (fij​∈{0,1})

  • 矩阵形式推导：

    代数形式的目标函数可以被转化为如下矩阵形式目标：
    $$\begin{array}{rl}J& =||X-M{F}^T|{|}_F^2\\ & =tr[(X-M{F}^T)(X-M{F}^T{)}^T]\\ & =tr(X{X}^T-XF{M}^T-M{F}^T{X}^T+M{F}^{T}FM)\end{array}$$
    因此该优化问题为针对两矩阵变量（F，M）的最小化问题，采用交替优化方法进行优化，即先确定一个参数，再确定另一个

    • 求解M：

      • 矩阵M是簇中心矩阵，其中数取值为实数域，可以通过求偏导，令为零的方法求解：
        $$\frac{\partial J}{\partial M}=-XF-XF+2M{F}^{T}F=2M{F}^{T}F-2XF$$

        $$\begin{array}{rl}& \frac{\partial J}{\partial M}=0\\ & =>2M{F}^{T}F-2XF=0\\ & =>M{F}^{T}F=XF\\ & =>M=XF(F^{T}F{)}^{-1}\end{array}$$

        即，在已知指示矩阵F（分类情况）下，使损失最小化的簇心即为各类样本向量均值$[u_1,u_2,...,u_k]$

    • 求解F：

      • 对于k-Means方法，指示矩阵F存在约束，元素fij∈{0,1}f_{ij}\in\{0,1\}fij​∈{0,1}

      • 因为F元素不连续，不能直接求导，因此将目标重新表示：
        $$X-M{F}^T=[x_1,x_2,...,x_n]-[u_1,u_2,...,u_k]\left[\begin{array}{cccc}{f}_{11}& f_{21}& ...& f_{n1}\\ f_{12}& f_{22}& ...& f_{n2}\\ ...& ...& ...& ...\\ f_{1k}& f_{2k}& ...& f_{nk}\end{array}\right]$$
        矩阵$F^T$第j列的列向量$f_j$代表样本$x_j$的分类情况，对每个样本都有k种情况（一个样本可能是k类中的一类）

        因此可以对每一个样本向量$x_j$枚举其类别，然后计算在该样本处产生的误差，选择误差最小的作为其预测类别

        因此对n个样本，需要进行n*k次枚举

        该方法等价于"将每个样本分到离其最近簇心对应的类"

    • 采用的交替优化方法即为先选取当前簇心矩阵下的最优指示矩阵，再选取当前指示矩阵下最优簇心矩阵，不断迭代

    • 由于迭代过程的每一步都能对目标函数进行优化，即目标函数值$J$每次都在下降，又$J$作为F范数平方大于0，有下界，因此必收敛

• fuzzy C-Means方法：

  • 将K-means方法中的标签矩阵F替换为权值F’，其元素$f_{ij}^{\prime }$代表第i个样本属于第j类的程度

  • 优化目标：
    $$J=\sum _{i=1}^k\sum _{x\in C_i}^k{f^{\prime }}_{ij}^m||x-u_i|{|}_2^2(m\ge 2)$$

    • 权值$f_{ij}^{\prime }$与标签$f_{ij}$相比的区别：
      • $f_{ij}^{\prime }\in [0,1]$而fij∈{0,1}f_{ij}\in{\{0,1\}}fij​∈{0,1}
      • 在优化目标中，权值需要进行m次方运算，若$m=1$，则最终问题与k-means等价，F’会收敛于F（最小损失一定出现在分类唯一时）

  • 同样使用交替优化方法分别求解$F^{\prime }与M$，得：
    $$f_{ij}^{\prime }=\frac{1}{{\sum }_{i=1}^k[\frac{||x_i-u_i||}{||x_i-u_k||}{]}^{\frac{2}{m-1}}}$$

    $$u_j=\frac{{\sum }_{i=1}^N{f^{\prime }}_{ij}^m{x}_i}{{\sum }_{i=1}^N{f}_{ij}^{\prime }}$$

算法流程

• K-Means 与 fuzzy C-Means聚类流程

  • 1）指定类别数k
  • 2）初始化簇心矩阵与指示/权值矩阵
  • 3）迭代：
    • 根据目前簇心矩阵更新指示/权值矩阵
    • 根据目前指示/权值矩更新阵簇心矩阵
    • 当相邻两次簇心更新量小于阈值时迭代停止
  • 4）得到指示/权值矩阵

• 超参数K选择：

  • 肘部法：

    以误差平方和SSE为指标，计算给定k值下所有样本的聚类误差和，用于代表聚类效果好坏

    当k小于真实类别时，随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，误差平方和会变小，且下降幅度会很大；

    当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓

• 轮廓系数法：

  • 对样本点$x_i$

    • 定义凝聚度a，是样本点与同类其他样本平均距离
    • 定义分离度b，是样本点与最近簇中所有样本的平均距离

  • 最近簇：
    $$C_j=\underset{C_k}{\mathrm{argmin}}\frac{1}{n}\sum _{x\in C_k}||x-u_k||$$

  • 定义轮廓系数
    $$S=\frac{b-a}{max(a,b)}$$

  • 求出所有样本的轮廓系数后再求平均值，得到对数据集X的平均轮廓系数

  • 簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好

  • 即令平均轮廓系数最大的k值即为最优k值

参考资料

【1】《机器学习》周志华

【2】《统计学习方法》李航

【3】[K-means中K值的选取][https://blog.csdn.net/sxllllwd/article/details/82151996]