基于拉普拉斯约束的半监督模糊C均值算法

Semi-Supervised Fuzzy C-Means Algorithm Based on Laplace Constraint

摘要: 模糊聚类算法作为经典的无监督算法之一，在未提供先验信息的基础上容易陷入局部最优。为了能够将监督学习与无监督学习相结合，同时利用已标签数据和未标签数据共同进行训练学习，本文通过对目标函数进行拉普拉斯约束，通过验证隶属度的范围始终大于等于零，能够证明该算法是有效的。在其基础上加入先验信息来挖掘大量有用的信息，使之在未提供先验信息的基础上，算法能够合理、有效地利用部分已标识样本的类别信息对未标识样本产生影响，从而提高半聚类算法的聚类性能；最后，将文章中提出的两类改进算法与原始模糊c均值(FCM)进行聚类指标对比，能够显示其具有良好的聚类效果。

Abstract: As one of the classical unsupervised algorithms, fuzzy clustering algorithm is easy to fall into local optimum without providing prior information. In order to combine supervised learning with unsupervised learning and use both labeled and unlabeled data for training learning, this paper proved the effectiveness of the algorithm through Laplace constraint on the objective function and verification that the range of membership is always greater than or equal to zero. On this basis, prior information is added to mine a lot of useful information, so that the algorithm can reasonably and effectively use the category information of part of the identified samples to affect the unidentified samples, so as to improve the clustering performance of the semi-clustering algorithm. Finally, the two improved algorithms proposed in this paper are compared with the original Fuzzy C-means (FCM) for clustering index, and the results show that the proposed algorithm has good clustering effect.

1. 引言

近年来，聚类分析在模式识别、图像处理和数据挖掘中得到了广泛的应用。它试图将数据集划分为不同的组，使得同一集群中的数据点(模式、样本和主题)具有较高的相似性，而不同集群中的数据点具有较低的相似性。到目前为止，已经开发了许多聚类算法，包括层次聚类 [1]、谱聚类 [2] 和模糊c均值聚类(FCM) [3] 等。

作为半监督聚类，可以采用不同的方法来控制聚类过程。传统的模糊聚类算法对未知样本的使用率较低，针对于该问题，相关领域学者经过不断研究提出了半监督模糊聚类。2000年，Wagstaff引入了一个具有成对约束集群的修改版本，即“必须连接”和“不能连接”，以提高聚类性能 [4]。由于模糊c均值(FCM)是最经典的算法之一，一些相关的工作已经被提出，来约束半监督模糊c均值，例如在隶属度中加入半监督项 [6]。半监督模糊聚类算法通过将少量的数据类别标签作为监督信息 [5] 来加入到模糊聚类算法中，使其在整个聚类迭代优化过程中发挥一定的监督作用。SFCM算法 [7] 是一种经典的半监督聚类算法，它以标签信息作为先验知识。该算法将已知的类别标签集成到隶属度矩阵中，指导隶属度矩阵的优化，约束项中所含的先验信息则会对隶属度矩阵的优化起监督作用，并创建最合理的模糊划分，以此提高聚类效果。Pedrycz和Waletzky [8] 接受了改进的FCM算法，并将聚类问题的标记数据和未标记数据作为改进目标函数的途径。Luis等人 [9] 提出了一种新的半监督模糊c均值算法，该算法利用基因本体注释作为先验知识来指导基因分组过程。同时，引入基于核的FCM方法(SSKFCM) [10] [11] 将半监督学习技术与核方法相结合，提高了模糊划分的质量。该方法将半监督聚类扩展到核空间，使聚类在输入空间中划分成具有非线性边界的群。

半监督聚类方法分为基于相似度的聚类方法和基于搜索的聚类方法，Zhang等人 [12] 提出了一个框架，对由边缘信息构造的加权拉普拉斯矩阵进行优化更新。在文献 [13] 的基础上，提出了一种鲁棒稀疏模糊k均值聚类算法，该算法是对标准模糊k均值算法的一种改进，它采用了一个鲁棒函数而不是平方数据拟合项来处理离群点。该文章中提出了一种新的方法(FSCM)来实现谱聚类结构和数据的模糊相似矩阵的联合学习。更为重要的是，结合稀疏性的概念，进一步引入惩罚项，使每个样本的对象簇成员具有适当的稀疏性。该算法不仅保证了软聚类算法在实际应用中的鲁棒性，而且考虑到隶属度数量较少，避免了性能下降 [14]。根据不同聚类评价算法的适用范围，提出了一种特征加权模糊半监督聚类算法(SFFD) [15] [16]。该算法基于完全自适应的距离函数、特征权重和两两约束构造一个统一的目标函数，用于在两两约束下搜索最优原型参数和最优特征权重。同时，给出了四种不同的模糊聚类有效性评价算法，采用不同的算法来评估SFFD算法的有效性，得到不同输入数据集的最优聚类数，从而确定聚类形成过程中的聚类数。文章 [17] 中提出的半监督模糊聚类算法充分利用了已知的信息样本，以最小信息熵对应的聚类数作为整个样本的最优聚类数，以此得到的聚类中心是模糊聚类的原始聚类中心。

本文在研究模糊c均值聚类(FCM)算法的基础上，通过加入正则项来约束FCM，提出了一种基于拉普拉斯约束的模糊c均值(FCML)算法，给出了FCML算法的迭代结果，并对其进行非负证明，即u_ij经过多次迭代后，其最终结果仍为非负数，以此来证明该算法的有效性。

文章第三节在研究基于拉普拉斯约束的模糊c均值(FCML)算法的基础上，提出了基于拉普拉斯约束的半监督模糊c均值(SFCML)算法，该算法通过引入一些监督信息来改进FCML算法，可以在不提供先验信息的情况下充分利用先验信息来对未标记样本进行部分标记，合理有效地利用部分已识别样本的类别信息，从而提高半聚类算法的聚类性能，其最终结果具有和FCM算法一样简洁的隶属度与聚类中心的迭代公式。

最后，将文章中提出的基于拉普拉斯约束的模糊c均值(FCML)算法及基于拉普拉斯约束的半监督模糊c均值(SFCML)算法与原始模糊c均值(FCM)的聚类性能进行了检验和评价。

2. 基于拉普拉斯约束的模糊c均值(FCML)

2.1. 目标函数设计

为了将数据点按一定的隶属度分组到每个聚类中，模糊c均值聚类的目标函数为：

$\min {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-v_j\Vert }_2^2{u}_{ij}^2}}$

$\text{st}\text{.}{\displaystyle \underset{i=1}{\overset{c}{\sum }}{u}_{ij}}=1$ (1)

其中X为原始样本数据集， $V=\left\{v_1,v_2,\cdots ,v_c\right\}$ 为C个聚类中心， $U={\left(u_{ij}\right)}_{c\times n}$ 为隶属度矩阵， $\Vert \cdot \Vert$ 为欧式距离。

通过稀疏化模糊c均值去除大量的冗余变量，只保留与相应变量最相关的解释变量，简化了模型的同时却保留了数据集中最重要的信息，能够有效地解决高维数据集建模中的诸多问题，因此，本文在模糊c均值聚类的基础上引入了拉普拉斯约束：

$\min {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-v_j\Vert }_2^2{u}_{ij}^2}}+2\lambda Tr\left(U^{\text{T}}{L}_{S}U\right)$ 2)

式中n表示元素个数，c表示聚类个数，d为维数，S为数据X的相似矩阵， $L_S=D-\frac{S^{\text{T}}+S}{2}$ 为S的Laplace矩阵， $D={\displaystyle \underset{j=1}{\overset{n}{\sum }}\frac{\left(s_{ij}+s_{ji}\right)}{2}}$ 为对角矩阵。

2.2. 理论分析

当U和S固定时，更新V可得到

$V_j=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_{ij}^2{x}_i}}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_{ij}^2}}$ (3)

当V和S固定时，更新U，由目标函数可知与U有关的函数为：

$\min {\displaystyle \underset{i=1}{\overset{c}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}^2{d}_{ij}^2}}+2\lambda Tr\left(U{L}_S{U}^{\text{T}}\right)$ (4)

在聚类算法中，有一个经典的等式：

$2Tr\left(U{L}_S{U}^{\text{T}}\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\Vert u_i-u_j\Vert }_F^2{s}_{ij}}}$ (5)

关于(5)式是否成立，给出了如下证明：

$U^{\text{T}}{L}_{S}U=U^{\text{T}}\left(D-S\right)U=U^{\text{T}}DU-U^{\text{T}}SU$

$\begin{array}{c}2Tr\left(U^{\text{T}}{L}_{S}U\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_i^2{d}_i}-{\displaystyle \underset{i,j=1}{\overset{n}{\sum }}{u}_i{u}_j{s}_{ij}}=\frac{1}{2}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_i^2{d}_i}-2{\displaystyle \underset{i,j=1}{\overset{n}{\sum }}{u}_i{u}_j{s}_{ij}}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_j^2{d}_j}\right)\\ ={\displaystyle \underset{i,j=1}{\overset{n}{\sum }}{\Vert u_i-u_j\Vert }_F^2{s}_{ij}}\end{array}$

因此，目标函数(4)可以改写成：

$J=\min {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-v_j\Vert }_2^2{u}_{ij}^2}}+\lambda {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert u_i-u_j\Vert }_F^2{s}_{ij}}}+\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-x_j\Vert }_2^2{s}_{ij}^2}}$ (6)

即(6)式为

$J_u=\min {\displaystyle \underset{i=1}{\overset{c}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}^2{d}_{ij}^2}}+\lambda {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\Vert u_i-u_j\Vert }_F^2{s}_{ij}}}$ (7)

其中含 $u_{ij}$ 的项为：

$\begin{array}{l}{u}_{ij}^2{d}_{ij}^2+2\lambda {\displaystyle \underset{l\ne j}{\sum }{\Vert u_l-u_j\Vert }_F^2{s}_{lj}}\\ =u_{ij}^2{d}_{ij}^2+2\lambda \left({\Vert u_1-u_j\Vert }_F^2{s}_{1j}+\cdots +{\Vert u_{j-1}-u_j\Vert }_F^2{s}_{j-1,j}+{\Vert u_{j+1}-u_j\Vert }_F^2{s}_{j+1,j}+\cdots +{\Vert u_n-u_j\Vert }_F^2{s}_{nj}\right)\end{array}$ (8)

同理， ${\Vert u_1-u_j\Vert }_F^2={\left(u_{{}_{11}}-u_{1j}\right)}^2+{\left(u_{{}_{21}}-u_{2j}\right)}^2+\cdots +{\left(u_{{}_{c1}}-u_{cj}\right)}^2$，其中只有 ${\left(u_{i1}-u_{ij}\right)}^2$ 中 $u_{ij}$，所以(8)式中含 $u_{ij}$ 的值为：

$u_{ij}^2{d}_{ij}^2+2\lambda {\displaystyle \underset{l\ne j}{\sum }{\left(u_{ij}-u_{il}\right)}^2{s}_{lj}}$ (9)

对其进行拉格朗日求导可得

$2u_{ij}{d}_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{ij}{s}_{lj}}-4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}-{\xi }_j=0$

其中 ${\xi }_i$ 为Lagrange乘子，所以

$u_{ij}=\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}+{\xi }_j}{2d_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}$ (10)

由约束条件 ${\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{kj}}=1$ 可知(10)式为

${\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{kj}}={\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}+{\xi }_j}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}=1$ (11)

即

${\xi }_j=\frac{1-{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}{{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{1}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}$ (12)

将(12)式代入(10)式中可得

$u_{ij}=\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}+\frac{1-{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}{{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{1}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}}{2d_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}$ (13)

本文中，我们对迭代后(13)式中 $u_{ij}\ge 0$ 是否成立进行了证明：

证明： $u_{ij}=\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}+\frac{1-{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}{{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{1}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}}{2d_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}\ge 0$

由于 $2d_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}\ge 0,2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}\ge 0,4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}\ge 0$，因此在这里只需证： $1-{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}\ge 0$ 即

${\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}\le 1$

因为

$\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}\le \frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}=\frac{{\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{{\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}$

可得

${\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}\le {\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{{\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{{\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}$

因为

$\begin{array}{c}{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{{\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{{\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}={\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{u_{k1}{s}_{1j}+u_{k2}{s}_{2j}+\cdots +u_{k,j-1}{s}_{j-1,j}+u_{k,j+1}{s}_{j+1,j}+\cdots +u_{kn}{s}_{nj}}{s_{1j}+s_{2j}+\cdots +s_{j-1,j}+s_{j+1,j}+\cdots +s_{nj}}}\\ =\frac{s_{1j}{\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{k1}}+s_{2j}{\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{k2}}+\cdots +s_{j-1,j}{\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{k,j-1}}+s_{j+1,j}{\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{k,j+1}}+\cdots +s_{nj}{\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{kn}}}{s_{1j}+s_{2j}+\cdots +s_{j-1,j}+s_{j+1,j}+\cdots +s_{nj}}\end{array}$ (14)

由约束条件可得 ${\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{k1}}=1,\cdots ,{\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{kn}}=1$，从而 ${\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{{\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{{\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}=1$，因此 $u_{ij}\ge 0$ 得证。

固定U和V，更新S，(4)式可以看作：

$\lambda Tr\left(U^{\text{T}}{L}_{S}U\right)+\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-x_j\Vert }_2^2{s}_{ij}^2}}=\lambda {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert u_i-u_j\Vert }_2^2{s}_{ij}}}+\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-x_j\Vert }_2^2{s}_{ij}^2}}$ (15)

由于i独立，因此对(5)式求解，可以得到

$s_i^{\text{T}}D{s}_i+\frac{\lambda }{\mu }{s}_i^{\text{T}}{V}_i$ (16)

2.3. 算法流程

基于拉普拉斯约束的模糊c均值(FCML)与其他聚类算法具有类似的框架，其流程可以总结为：

输入：原始样本数据集X，聚类簇数c以及相似矩阵S。

输出：聚类中心V，迭代后的隶属度矩阵U。

步骤1：按照约束条件初始化U并设置聚类簇数c，迭代次数设置为100次。

步骤2：计算实际数据集的样本点与聚类中心的距离d；

步骤3：利用公式(4)计算迭代后的隶属度矩阵U；

步骤4：利用公式(3)计算V；

步骤5：本次计算得出的聚类中心与上次相比，不发生变化或者满足迭代次数超出最大次数，则算法停止；否则，返回步骤2。

3. 基于拉普拉斯约束的半监督模糊c均值算法(SFCML)

3.1. 目标函数设计

半监督聚类是一种监督聚类和无监督聚类相结合的聚类方法，既可以使用有标记的数据，也可以使用无标记的数据。在上一节中，我们通过对FCM算法进行拉普拉斯约束，得到了FCML算法，该过程是简单的，它通常可以达到预期的性能。然而，FCML算法没有嵌入可在某些应用中收集和有用的先验知识，因此算法容易陷入局部最优。本节中，我们在数据集X上运行FCML算法，给定原始数据集X，第l个样本与它们的集群标签y构成一个标记子集Y，其余的 $n-l$ 个样本构成一个未标记子集，通过将先验知识引入到FCML中，此时SFCML算法的目标函数为：

$\begin{array}{l}J=\min {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-v_j\Vert }_2^2{u}_{ij}^2}}+\lambda {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert u_i-u_j\Vert }_F^2{s}_{ij}}}+\alpha {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\left(u_{ij}-f_{ij}{b}_i\right)}^2{d}_{ij}^2}}\\ \text{st}\text{.}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_{ij}}=1,u_{ij}\ge 0\end{array}$ (17)

式中， $\alpha \left(\alpha \ge 0\right)$ 是反映保真度项重要性的参数， $\alpha$ 的具体值和 $\frac{总样本数L}{标记样本数L_1}$ 成正比例关系； $f_{ij}$ 为标签样本的隶属度矩阵，其值具体表示为 $x_i$ 归于 $c_j$ 的程度大小； $b_i$ 为一个布尔型的二值向量，根据其实际值可以判断 $x_i$ 是否是已经标记的数据。 $b_i$ 需要满足的条件如下：

$\{\begin{array}{l}{b}_i=1,x_i被标记\\ b_i=0,其他\end{array}$ (18)

3.2. 理论分析

当U和S固定时，更新V可得到

$v_j=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_{ij}^2{x}_i}}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_{ij}^2}}$ (19)

当V和S固定时，更新U，由目标函数可知与U有关的函数为：

其中含 $u_{ij}$ 的项为：

$J=\min {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert x_i-v_j\Vert }_2^2{u}_{ij}^2}}+\lambda {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\Vert u_i-u_j\Vert }_F^2{s}_{ij}}}+\alpha {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\left(u_{ij}-f_{ij}{b}_i\right)}^2{d}_{ij}^2}}$ (20)

$\begin{array}{l}{u}_{ij}^2{d}_{ij}^2+2\lambda {\displaystyle \underset{l\ne j}{\sum }{\Vert u_l-u_j\Vert }_F^2{s}_{lj}+\alpha {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\left(u_{ij}-f_{ij}{b}_i\right)}^2}}}{d}_{ij}^2\\ =u_{ij}^2{d}_{ij}^2+2\lambda \left({\Vert u_1-u_j\Vert }_F^2{s}_{1j}+\cdots +{\Vert u_{j-1}-u_j\Vert }_F^2{s}_{j-1,j}+{\Vert u_{j+1}-u_j\Vert }_F^2{s}_{j+1,j}+\cdots +{\Vert u_n-u_j\Vert }_F^2{s}_{nj}\right)\\ +\alpha \left({\left(u_{11}-f_{11}{b}_1\right)}^2{d}_{11}^2+\cdots +{\left(u_{1j}-f_{1j}{b}_1\right)}^2{d}_{1j}^2+\cdots +{\left(u_{ij}-f_{ij}{b}_i\right)}^2{d}_{ij}^2+\cdots +{\left(u_{nc}-f_{nc}{b}_n\right)}^2{d}_{nc}^2\right)\end{array}$ (21)

由于只有 ${\left(u_{i1}-u_{ij}\right)}^2$ 及 $\alpha \left(u_{ij}-f_{ij}{b}_i\right)d_{ij}^2$ 中有 $u_{ij}$，所以(21)式中含 $u_{ij}$ 的值为：

$u_{ij}^2{d}_{ij}^2+2\lambda {\displaystyle \underset{l\ne j}{\sum }{\left(u_{ij}-u_{il}\right)}^2{s}_{lj}}+\alpha {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\left(u_{ij}-f_{ij}{b}_i\right)}^2{d}_{ij}^2}}$ (22)

将(22)式改写为

$L\left(u_{ij},\eta ,{\beta }_{ij}\right)=u_{ij}^2{d}_{ij}^2+2\lambda {\displaystyle \underset{l\ne j}{\sum }{\left(u_{ij}-u_{il}\right)}^2{s}_{lj}}+\alpha {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\left(u_{ij}-f_{ij}{b}_i\right)}^2{d}_{ij}^2}}-\eta \left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{u}_{ij}-1}\right)-{\beta }_{ij}{u}_{ij}$ (23)

对(23)式中 $u_{ij}$ 求偏导数可得：

$\frac{\partial J_u}{\partial u}=2u_{ij}{d}_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }\left(u_{ij}-u_{il}\right)s_{lj}}+2\alpha \left(u_{ij}-f_{ij}{b}_i\right)d_{ij}^2-\eta -{\beta }_{ij}$

对其进行拉格朗日求导可得

$2u_{ij}{d}_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{ij}{s}_{lj}}-4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}-2\alpha \left(u_{ij}-f_{ij}{b}_i\right)d_{ij}^2-\eta -{\beta }_{ij}=0$

其中 $\eta$ 和 ${\beta }_{ij}\ge 0$ 为Lagrange乘子，所以

$u_{ij}={\left(\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}-2\alpha f_{ij}{b}_i{d}_{ij}^2+\eta +{\beta }_{ij}}{2d_{ij}^2-2\alpha d_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}\right)}_{+}$ (24)

由约束条件 ${\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{kj}}=1$ 可知(24)式为

${\displaystyle \underset{k=1}{\overset{c}{\sum }}{u}_{kj}}={\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}-2\alpha f_{kj}{b}_k{d}_{kj}^2+{\xi }_j}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}=1$ (25)

因此

${\xi }_j=\frac{1-{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}+{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{2\alpha f_{kj}{b}_k{d}_{kj}^2}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}}{{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{1}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}$ (26)

将(25)式代入(24)式中可得

$u_{ij}=\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{il}{s}_{lj}}-2\alpha f_{ij}{b}_i{d}_{ij}^2+\frac{1-{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{4\lambda {\displaystyle \underset{l\ne j}{\sum }{u}_{kl}{s}_{lj}}}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}+{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{2\alpha f_{kj}{b}_k{d}_{kj}^2}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}{{\displaystyle \underset{k=1}{\overset{c}{\sum }}\frac{1}{2d_{kj}^2-2\alpha d_{kj}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}}}}{2d_{ij}^2-2\alpha d_{ij}^2+4\lambda {\displaystyle \underset{l\ne j}{\sum }{s}_{lj}}}$ (27)

3.3. 算法2

基于拉普拉斯约束的半监督模糊c均值(SFCML)与其他半监督聚类算法具有类似的框架，其流程为：

输入：需要聚类的数据对象集合X，聚类的类别数c以及带有标签信息的约束集Y。

输出：更新后的聚类中心V及隶属度矩阵U。

步骤1：通过计算每个集群中标记样本的平均值来初始化集群中心V₀，按照约束条件随机初始化U，设置聚类个数c，由标记信息计算标记信息的初始隶属度矩阵F₀；

步骤2：计算实际数据集X的样本点与聚类中心的距离d，标签样本集Y与聚类中心的距离d_y；

步骤3：利用公式(27)计算迭代后的隶属度矩阵U；

步骤4：利用公式(19)计算聚类中心V；

步骤5：本次计算得出的聚类中心与上次相比，不发生变化或者满足迭代次数超出最大次数，则算法停止；否则，返回步骤2。

4. 实验结果分析

4.1. 实验设计

为评估聚类结果，采用聚类准确率(ACC)、NMI指标及兰德指数(简称RI)这三种被广泛使用的聚类性能指标。ACC指标可以发现聚类结果和真实类标签之间的一对一关系，且测量每个聚类所包含的来自对应类别的数据点的多少，其计算式为

$ACC=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\delta \left(map\left(r_i\right),q_i\right)}}{n}$

NMI指标用于确定聚类的质量，给定一个聚类结果，则

$NMI=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{n}_{ij}\lg \frac{n_{ij}}{n_i{\hat{n}}_j}}}}{\sqrt{\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{n}_i\lg \frac{n_i}{n}}\right)\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{\hat{n}}_j\lg \frac{{\hat{n}}_j}{n}}\right)}}$

兰德指数(简称RI)算法的性能根据该算法获得的决策数量的正确率来评估。它需提供定实际类别信息C，假设K是聚类结果，a表示在C和k中都是同类别的元素对数，d表示在C与k中都是不同类别的元素对数，则RI参数为： $RI=\frac{a+d}{C_2^n\text{samples}}$，其中 $C_2^n\text{samples}$ 数据集中可以组成的总元素对数。

4.2. 真实数据集实验结果

我们在真实数据集中选取iris数据集进行实验。实验采用FCM、FCML和SFCML进行测试和比较。为了验证测试结果的可靠性，在FCM、FCML和SFCML实验中均使用欧氏距离。此外，算法的标签样本点个数为10个，标签样本点的初始隶属度相同。采用三种算法对真实数据集进行依次测试，每种算法测试10次。最终实验结果见表1。

Table 1. Accuracy of FCM, FCML and SFCML algorithms on Iris data set

表1. Iris数据集上FCM、FCML、SFCML算法准确率

由表1可以清楚看出，FCM算法、FCML算法和SFCML算法的准确率大小依次为：SFCML算法最大，FCML算法其次，最后是FCM算法，与理论分析结果一致。和FCM算法相比，FCML算法能够有效提取有用信息进行聚类，而SFCML算法在FCML算法的基础上加入监督信息，使得算法准确率进一步提升。

表2分别对FCM、FCML和SFCML算法进行聚类质量NMI及聚类效果RI对比。

Table 2. Clustering effect comparison of FCM, FCML and SFCML on Iris data set

表2. Iris数据集上FCM、FCML、SFCML聚类效果对比

从聚类准确度方面分析，SFCML算法达到最大值，为0.9800；而FCM算法因为没有监督信息集拉普拉斯约束项做指导，聚类的准确率是3种算法中最小的，为0.9600；FCML算法居中，为0.9703。综合来看，无论用3个方面的哪一个评价，SFCML算法的聚类性能都要优于其他2种聚类算法。

5. 总结与展望

本文在经典FCM算法的基础上引入了拉普拉斯算法进行约束，提高聚类的抗噪性能以及提取重要的属性特征，并将最终迭代结果进行非负验证。其次，利用少量标记信息进行数据预处理，构造半监督聚类算法SFCML来对FCML算法进行改进。此外，由于SFCML的目标函数是基于FCM的，它继承了聚类算法FCM的大部分优点。本文在真实数据集上进行算法对比实验，实验结果进一步验证了本文提出的SFCML算法的有效性。之后对半监督的研究将从对相似矩阵S进行半监督学习，并验证是否能达到改进已有算法的效果。与多个领域进行融合，在不同领域内运用半监督聚类算法的思想，加入不同领域的知识，可以得到更加优化的效果。

致谢

首先要感谢我的论文指导老师、西安工程大学理学院研究生院的马盈仓老师。马老师对我论文的研究方向做出了指导性的意见和建议，在写这篇论文的过程中，他对我遇到的困难和疑惑及时给予了认真的指导，提出了许多有益的改进建议，投入了大量的心血和精力。衷心感谢马老师对我的帮助和关心！同时，我也要感谢西安工程大学理学院研究生院计算数学专业的老师们和全体同学们，我们互相学习，互相帮助，度过了一段美好而难忘的时光。此外，我还要感谢我的朋友和同学们在论文的准备过程中给予我的大力支持和帮助，给我带来了很大的启发。也要感谢参考文献中的作者，他们的研究文章对我的研究课题有了一个很好的起点。最后，谢谢论文评阅老师们的辛苦工作。衷心感谢我的家人、朋友和同学对我的鼓励和支持，让我顺利完成了这篇论文。

基金项目

国家自然科学基金项目(61976130)；陕西省重点研发计划项目(2018KW-021)；陕西省自然科学基金项目(2020JQ-923)。