稀疏约束的嵌入式模糊均值聚类算法

王继奎，杨正国，易纪海，刘学文，王会勇，聂飞平

(1.兰州财经大学 信息工程学院，甘肃 兰州 730020；2.桂林电子科技大学 数学和计算科学学院，广西 桂林 541004；3.西北工业大学 光学影像分析与学习中心，陕西 西安 710119)

聚类分析是机器学习领域研究的热点之一，被广泛应用在图像识别[1]、文本分析[2-3]和客户关系管理[4]等领域中.K-Means[5]是其中最经典的聚类算法.K-Means算法聚类速度快，性能好.然而，K-Means计算出的类簇中心并不是实际存在的数据.作为K-Means的替代算法，Kmedoids[6]选择离计算出的类簇中心最近的样本作为类簇中心.尽管K-Means算法计算速度快，被广泛使用，但是也具有若干缺点，比如对异常点敏感，鲁棒性不强及仅适用于球形分布的数据等.为了解决这些问题，研究者们进行系列研究[7-12].文献[13-16]对K-Means算法进行扩展完成分类属性数据、混合类型数据聚类.

K-Means算法属于硬划分，在优化的过程中容易出现划分不准确等问题.为解决这一问题，研究人员提出了模糊均值聚类算法(Fuzzy C-Means,FCM)[17].FCM被广泛应用于各个领域，大大提升了聚类能力.然而FCM算法仍然具有对异常点敏感，鲁棒性不强，仅适用于球形分布的数据等问题.研究人员在FCM算法的基础上，又提出了Kernel based FCM[18]、Multivariate FCM、Modified probabilistic FCM[19]、Conditional spatial FCM[20]、Generalized entropy-based physicalistic FCM[21]等算法.

随着科技的发展，高维数据不断涌现.机器学习算法在面对高维数据时，产生了维度灾难问题，比如计算复杂度高.在许多场合，尽管数据的维度很高，但是有意义的数据分布往往嵌入在某个低维子空间中.降维技术不仅能使高维数据更好地被理解或者可视化，而且可以很好地解决机器学习算法在面临数据维度高时产生的诸多问题.降维技术主要包括无监督降维、半监督降维和有监督降维等类别.主成分分析(Principal Component Analysis,PCA)与局部保留投影(Local Preserving Projection,LPP)[22]是两个常用的无监督线性降维方法.针对线性降维技术不适用于流形数据的问题，研究人员又提出了许多非线性的降维技术，比如locally linear embedding[23-24]、Isomap[25]及Laplacian Eigenmap[26]等.这些非线性的降维方法计算复杂度高，不适用于数据规模大的数据集，而且处理新增数据不方便.这些问题限制了非线性降维方法的实际应用.

面对高维数据聚类，传统的策略是先利用降维技术将高维数据转变为低维数据，然后用一个具体的聚类算法完成聚类.两阶段的策略将降维过程与随后的聚类过程分开.目前也有一些研究从多视图的角度进行高维数据的聚类，取得了不错的效果[27-28].如何将降维过程与降维后的聚类过程融为一体，建立统一的优化模型成为新的研究思路.在此想法的基础上，我们将经典的线性降维技术与FCM算法统一在一个模型中，提出了一种稀疏约束的嵌入式模糊均值聚类算法(Embedded Fuzzy c-means with Sparsity Constraint,EFSC).本文主要完成了以下工作:(1) 提出了将线性降维与模糊聚类算法统一的聚类算法EFSC；(2) 将稀疏约束施加在模糊矩阵上，提高了EFSC算法的聚类性能；(3) 提出了一种有效的迭代优化算法完成模型优化；(4) 对EFSC聚类模型的时间复杂度进行分析，分析表明EFSC具有输入数据规模的线性时间复杂度；(5) 在基准数据集上进行实验，结果表明与经典的聚类算法相比，EFSC算法具有更高的准确度，验证了EFSC算法的有效性.

1 相关工作

在聚类分析和数据降维方面，研究者们进行了大量卓有成效的研究.其中线性降维是最常用的降维技术，模糊聚类是很有效的聚类算法.下面对这两种经典算法进行介绍.

1.1 线性降维

给定数据集X=[x1,x2,…,xn]，X∈d×n表示数据集，xi∈d×1表示一个数据，d表示数据的维度，n表示数据的个数.线性降维的目的是寻找一个投影矩阵W∈Rd×d′将数据X投影到d′维度子空间，其中，d′≪d.在众多的线性降维算法中，PCA和LPP是两个常用的算法.PCA使降维后的数据方差最大化，而LPP则使得降维前后的数据近邻关系得到保持.然而，目前的线性降维算法仅利用了数据本身的信息，没有利用数据的分布信息.比如，不同类别间的数据靠得很近，而相同类别内的数据较为分散的时候，PCA效果不佳，容易将不同类别的数据投影在相近的空间中，不利于降维后的聚类.

1.2 模糊聚类

模糊聚类是在k均值聚类的基础上发展出来的一种算法.其目标函数如下:

(1)

式(1)中：M∈d×c表示类簇中心；mk∈d×1表示第k个中心；α∈n×c表示模糊矩阵；αi∈1×c表示模糊矩阵α的第i行，1c=[1,1,…,1]T表示维度为c，元素全为1的向量；αi1c=1表示模糊矩阵α的每一行和为1；αik表示样本xi对类簇中心mk的模糊系数；γ>1表示模糊指数，当γ=1，FCM等价于K-Means.通过迭代算法可以求出最优的模糊矩阵α，类簇中心矩阵M.通过调整γ的取值，FCM可以取得比K-Means更好的聚类效果.然而，FCM与K-Means同样仅适用于球形数据且对异常点敏感、算法鲁棒性差.

2 EFSC-稀疏约束的嵌入式模糊均值聚类算法

传统的高维数据聚类往往采用两阶段的策略.先利用某个降维技术将数据降到指定的维度，然后执行一个具体的聚类算法完成聚类.一个新的研究思路是将降维过程与聚类过程合二为一，使降维过程与聚类过程互相监督.

2.1 模型提出

我们的目的是创建一个模型将投影矩阵嵌入在聚类模型中，将投影矩阵、类簇中心和模糊矩阵一起优化，使降维过程与聚类过程合二为一.为此，我们提出了以下模型:

(2)

模型(2)与(1)的区别在于模型(2)加入了一个投影矩阵W∈Rd×d′.当α∈n×c确定后，我们可以学习W∈Rd×d′和M∈d′×c，当学习到最优的W和M后，我们可以反过来学习最优的模糊矩阵α.因为模型(2)采用计算降维后的样本点和类簇中心的距离，如果存在若干异常点，则整个模型受异常点的影响较大，类簇中心会向异常点移动，从而偏离了真正的类簇中心.为了解决这一问题，我们进一步提出以下模型:

(3)

(4)

其中K表示αi中的非零元素的个数.模型(4)就是我们提出的EFSC算法模型.我们的新模型将线性降维、模糊聚类统一在一起，并且加入了更加鲁棒的距离函数以及模糊矩阵的稀疏约束来提升聚类效果.

2.2 模型求解

我们采用迭代优化的方法求解模型(4)，其正确性已经由文献[29]证明.具体来说，在每次迭代过程中固定一组变量，优化另一组变量.EFSC算法的每次迭代分以下两步进行:

(1) 固定W、M，优化α:当W、M固定，模型(4)简化为:

(5)

其中：

(6)

由于αi的约束发生在每行，因此问题(5)可以分解为n个独立的子问题分别求解，其第i个子问题如下所示:

(7)

根据拉格朗日乘数法和KKT(Karush-Kuhn-Tucker)条件得到αik的最优解为:

(8)

(2) 固定α，优化W、M:当α固定，模型(4)简化为:

(9)

模型(9)难以直接求解.文献[30]提出了一种新颖的迭代变权方法可解决此类问题.一种通用的优化问题描述为:

(10)

其中：hi(x)为任意凹函数；x∈C表示x上的任意约束.令h′i(gi(x))表示凹函数hi在点gi(x)上的任意超梯度.可采用如下迭代变权优化算法解决:

显然，模型(9)是模型(10)的特例.因而可以用表1所示的迭代变权法解决.令:

表1 算法1Tab.1 Algorithm 1

(11)

算法1中步骤2求解的模型转化为:

(12)

式(11)、(12)对应于算法1中的1、2步，分别完成了超梯度与参数的更新.文献[30]提出的迭代变权算法保证了模型(12)的最优解满足模型(9)的KKT条件，所以模型(12)的最优解就是模型(9)的局部最优解.模型(12)可进一步转化为:

(13)

其中:

(14)

模型(13)的目标函数关于mk求导并令导数为0，得:

(15)

由式(15)可求得mk的最优解为:

(16)

(17)

为了得到W的最优解，我们提出以下引理:

证 令Z=WTX∈d′×n，zi表示Z的第i列，F=WTY∈d′×c，fk表示F的第k列，则

(18)

显然，式(18)中的第1项和第2项用迹的形式表示为:

(19)

令ei表示第i个规范向量，可将式(18)中最后一个等号右边的第3项转化为:

(20)

结合公式(18)、(19)和(20)得:

则引理1得证.

所以问题(17)中W的最优解可由Q最小的d′个特征值对应的特征向量给出，通过式(16)求出mk的最优解.

通过以上分析，ESFC算法流程由表2列出.

表2 EFSC算法Tab.2 EFSC algorithm

2.3 算法复杂度分析

令n表示输入数据的规模，c表示类簇数，d表示数据的维度.EFSC算法在每一次迭代中，计算fik的时间复杂度为O(ndc)；计算sik的时间复杂度为O(nc)；求解W的时间复杂度为O(nd2)，计算mk的时间复杂度为O(ndc)；计算αik的时间复杂度为O(ndc).设迭代次数为t，d≤n，c≤n，则整个算法的时间复杂度为O(max(nd2,ndc)t).由此可见，EFSC算法具有输入数据规模n的线性时间复杂度.

3 实 验

为了验证EFSC算法的有效性，选择YALE、UPS、COIL和ORL 4个数据集(http:∥www.cad.zju.edu.cn/home/dengcai/Data/data.html)进行实验，在实验时先使用PCA将数据降到100维.实验采用常用的准确度作为度量标准，选择K-Means、KMedoids、FCM、AKFM[31]、RSFKM[32]和两阶段的PCA+FCM进行对比.实验环境为Win7操作系统、2.7GHz AMD A12-9800B R7 CPU、Matlab2012a.

3.1 参数设置

3.2 实验结果与分析

在实验过程中所有算法的类簇数c由真值给出.K-Means、KMedoids、FCM、AKFM和RSKM算法各运行20次，计算聚类准确度的均值和方差.PCA+FCM两阶段方法和EFSC各运行20次，记录每一维度的最优结果，并计算所有维度最优聚类准确度的均值和方差.实验结果如表3所示.

表3 各算法在YALE、UPS、COIL和ORL数据集上的准确度比较Tab.3 Comparison results on YALE,UPS,COIL and ORL datasets in term of accuracy

从表3可以看出EFSC在全部4个基准数据集上都取得了最好的聚类效果.K-Means、Kmedoids在全部4个基准数据集上准确度接近，表明这两个算法本质上非常接近.AKFM和RSKM算法在YALE、UPS、COIL和ORL的准确度明显高于K-Means、Kmedoids算法，表明引入模糊性和鲁棒的距离函数可提升聚类的性能.PCA+FCM两阶段策略的聚类准确度仅次于EFSC算法，这表明高维数据的本质结构通常嵌入在低维空间中.EFSC算法同时进行降维和聚类，聚类效果明显好于传统的先降维后聚类的两阶段方法PCA+FCM.在YALE、UPS、COIL和ORL 4个数据集上，EFSC算法比PCA+FCM两阶段方法的聚类准确度分别提升了1.71%、0.40%、2.60%和14.52%.

3.3 参数敏感性分析

(1) 维度对聚类准确度的影响

高维数据集的本质类簇结构往往存在于某个较低维的子空间中.我们在γ=1.1，K=c的条件下进行实验，检验不同的维度对聚类准确度的影响.实验结果如图1所示.从图1可以看出，聚类准确度在不同的维度取得不同的值，在维度较低时，聚类准确度较低；当维度d→100时，取得最高的聚类准确度.实验结果表明一方面高维数据的最优类簇结构存在于较低维的空间中，另一方面也表明对于图像数据经过PCA降到100维后，难以使用很低的维度描述其本质类簇结构.

(2) 模糊指数对聚类准确度的影响

模糊指数的不同取值会改变聚类中心的分布，从而改变聚类效果，模糊指数选择对于基于FCM的系列算法性能有决定性影响.不同的数据集往往对应着不同的最佳模糊指数.我们在K=c，d=98，γ∈[1,3]，步长为0.1的条件下对EFSC算法进行实验，检验不同的模糊指数取值对聚类准确度的影响实验结果，如图2所示.图2表明，在γ→1时候，EFSC取得了最高的聚类准确度，γ值的变化对不同数据集的聚类结果影响巨大.总体来说，随着γ的增加，聚类准确度存在降低的趋势.

(3) 稀疏约束对聚类准确度的影响

实验经验表明，权重矩阵的稀疏约束往往可以获得更好的聚类效果.我们在γ=1.1，d=98，K∈[1,c]步长为1的条件下进行实验，检验不同的稀疏约束对聚类准确的影响.实验结果如图3所示.从图3可以看出K的取值对聚类准确度的影响不大，并且没有明显的相关性.但是，当K取得合适的值时，EFSC算法取得最高的聚类准确度.比如对YALE数据集，当K=3时，取得最优的聚类准确度50.30%；对于UPS数据集当K=4时，EFSC取得最高的聚类准确度70.98%；对于COIL数据集，当K=2取得最高的聚类准确度68.61%；对于ORL数据集，当K=28时，取得最高的聚类准确度79.25%.对于不同数据集，稀疏约束K的取值各不同，需在实践中调整K的取值，以使EFSC具有最佳的聚类效果.

3.4 收敛曲线

我们将EFSC算法在不同的数据集上运行100次，并记录下每次迭代计算所得的最优值.对所记录的最优值归一化后绘制在一张图形上.图4展示了EFSC算法在YALE、UPS、COIL和ORL数据集上的收敛曲线.

从图4可以看出EFSC算法在YALE、UPS和COIL数据集上迭代不到20次就收敛了，在ORL数据集上，大约迭代40次就收敛了.所以，EFSC算法收敛的速度很快.图4中的收敛曲线也验证了EFSC算法的正确性.

4 结 语

与传统的高维数据聚类采用两阶段算法不同，本文提出了将线性降维和FCM模糊聚类统一的EFSC模型，并给出了一种有效的迭代优化算法，交替学习投影矩阵W、类簇中心M和模糊矩阵α.在EFSC模型中加入了新的距离计算函数，消除了异常点的影响，使得模型更具鲁棒性.同时，我们在模型中加入了对模糊矩阵α的稀疏约束，提升了模型的聚类性能.在基准测试数据集上的实验结果表明：与K-Means、Kmedoids、FCM、AKFM、RSKM和PCA+FCM两阶段算法相比，EFSC算法具有更高的聚类准确度，验证了EFSC算法的有效性.