基于最小二乘法的判别嵌入式聚类算法

支晓斌,芦玉良

(1.西安邮电大学 理学院,陕西 西安 710121;　2.西安邮电大学 通信与信息工程学院,陕西 西安 710121)

聚类分析是一种基本的多元统计分析方法，是无监督模式识别的一个重要分支[1]。聚类分析能够根据数据间的相似性对其进行自动分类，对于探索数据集的内部结构具有重要意义，已在模式识别、图像处理和数据挖掘等领域得到广泛应用。但在实际应用中，聚类分析经常会面临高维数据，“维数灾难”问题使传统聚类算法的聚类精度显著退化，难以得到理想的聚类效果。对高维数据的聚类已经成为聚类分析领域的一个挑战性问题[2]。

判别聚类(discriminative clustering,DC)算法首次将线性判别分析(linear discriminant analysis,LDA)和聚类算法结合，在完成对数据特征提取实现降维的同时对数据进行聚类[3]，但DC算法中所用的LDA存在散度矩阵奇异性问题和求解特征值计算复杂度高的问题。判别嵌入式聚类(discriminative embedded clustering,DEC)算法[4]采用最大间距准则(maximum margin criterion,MMC)[5-8]取代LDA来对数据降维，解决了散度矩阵奇异问题。但是，DEC算法与DC算法类似，需要求解特征值问题，仍然存在计算复杂度高的问题，严重影响着其实际应用[9]。改进的判别嵌入式聚类(efficient discriminative embedded clustering,EDEC)算法[9]在原DEC算法上对数据进行变换预处理，利用QR分解对类间散度矩阵做特征分解，对数据做初次降维处理，在此基础上用MMC对数据进行二次降维，两次降维提高了DEC算法的聚类效率。

LDA等价于最小二乘问题，此结论推广至正则化的情形后，可得出一种高效率的LDA方法，即基于最小二乘法的线性判别分析(least square based linear discriminant analysis,LSLDA)算法[10]。鉴于这一方法的有效性，为改善DEC算法对高维数据的聚类效率，本文将基于最小二乘法的降维过程引入到DEC算法当中，提出一种基于最小二乘法的判别嵌入式聚类(least square based discriminative embedded clustering,LSDEC)算法，先对数据做最小二乘变换预处理以降低数据的维数，再在该降维后的数据集上进行DEC聚类。

1　DEC算法和LSLDA算法

1.1　DEC算法

X=(x1,x2,…,xn)。

设这些数据点可分为c类，第j类中含有nj个数据点(j=1,2,…,c)。记第j类为Xj，另记以其中数据点为列向量构成的m×nj矩阵为Xj。

DEC算法可以描述为优化问题

maxJDEC(W,H)=
tr [WT(Sb+(1-λ)Sw)W],s.t.WTW=I。

(1)

其中，λ为平衡参数，W为将样本由高维空间映射到低维空间的待求变换矩阵。矩阵H={hij}n×c为待求隶属度矩阵。若数据点xi属于第j类，则hij=1，否则hij=0。Sb为类间散度矩阵，Sw为类内散度矩阵，分别定义为

(2)

而ej=(1,1,…,1)为nj维行向量。

根据DEC算法，给定隶属度矩阵，利用MMC对数据做降维处理，用K均值算法对降维后的数据进行聚类，然后用得到的新的隶属度矩阵再去指导MMC对数据降维，重复降维和聚类这两个过程直到得到最佳的聚类结果。DEC算法实现了子空间的选择和对数据的聚类，由于聚类过程是在最优子空间内完成的，因此该算法具有良好的聚类性能，另外，DEC算法利用MMC对数据降维，避免了DC算法存在的散布矩阵奇异性问题。但是，DEC算法与DC算法类似，需要求解特征值问题，对高维数据计算复杂度高，这一缺陷限制了DEC算法的应用。

1.2　LSLDA算法

LDA可描述为广义特征值问题[10]

XSXTw=αXXTw。

(3)

其中S为n×n阶对称半正定矩阵，定义为

式(3)可改写为标准特征值问题

(XXT)†XSXTw=αw,

其中矩阵(XXT)†代表矩阵XXT的广义逆。

广义特征值计算问题与基于最小二乘法的LDA等价，并且这一等价性结论在正则化情形下仍然成立[10]。

LSLDA算法的具体步骤如下。

步骤1输入数据矩阵X、带有类标签编码的矩阵U、正则化参数γ。

步骤2解决最小二乘问题

(4)

由于式(4)中的最小二乘问题可以用共轭梯度迭代算法高效率求解，所以LSLDA比直接求解广义特征值问题的LDA更加高效。

2　LSDEC算法

为改善DEC算法对高维数据的聚类效率，将LSLDA算法中的基于最小二乘法的降维过程引入到DEC算法中，通过对数据做最小二乘变换预处理，降低DEC算法的时间复杂度。

LSDEC算法具体步骤如下。

步骤1对数据进行中心化和规范化处理，初始化隶属度矩阵H0，给定平衡参数λ、正则化参数γ和阈值ε。

步骤2根据式(4)求解最小二乘问题，求得变换矩阵W1。

步骤3根据公式(2)构造矩阵Hb。

步骤6令G=W1W3，用变换矩阵G对数据进行降维处理,即Y=GTX，用K均值聚类算法对降维后的数据进行聚类，更新隶属度矩阵H。若‖H-H0‖<ε，则算法停止；否则将H赋给H0，返回步骤3。

步骤2至步骤4的加入使DEC算法的计算复杂度由原来的O(nm2)减少为O(nmc)，而高维数据的维数通常远大于类数，即m≫c，因此，LSDEC算法能够有效地降低DEC算法的时间复杂度。

3　实验及分析

为验证新提出的LSDEC算法的有效性，将LSDEC算法与K均值算法、DEC算法和EDEC算法在8个真实数据集上做对比实验。

3.1　实验设置

实验所用数据包括5个UCI数据集[11]Wine、Letter(abc)、Satimage、Spambse和Mfeat4，手写数字图像数据MINIST[12]，文本数据DOC[13],和基因表达数据集Leukemia(http://cilab.ujn.edu.cn/datasets.htm)，共8组数据，各数据特性如表1所示。

表1　数据特性

实验在Intel(R)Core i5 2.50GHZ CPU，8G内存win10系统环境下进行，从算法运行时间和聚类精度两个方面来衡量聚类算法的性能。其中聚类精度定义为

3.2　算法聚类精度测试

平衡参数λ取值范围为集合{10-6，10-4，10-2，100，102，104，106}，各算法在8组数据集上的聚类精度对比如图1所示。为方便表示，在图中用LSDEC-6和LSDEC-1分别表示正则化参数取10-6和10-1的LSDEC算法。

由于DEC算法在Lekumia数据上运行内存溢出，所以无法获得聚类精度和运行时间。由图1可见，在选取合适的平衡参数时，LSDEC算法只有在Satimage数据上的最优精度不及EDEC算法，在其他7组数据上的最优精度均高于K均值算法、DEC算法和EDEC算法，而且在部分数据上精度提升效果明显。在8组数据上，LSDEC算法的聚类精度在取任意γ时都优于DEC算法的聚类精度。

3.3　算法耗时测试

LSDEC算法与K均值算法、DEC算法和EDEC算法在不同平衡参数下对8组数据的运行时间如图2所示。

由图2可见，K均值算法聚类效率最高，但其最优聚类精度不及LSDEC算法。LSDEC算法在聚类效率上优于DEC算法，随着数据维数和样本数的增加，运行效率提升效果越明显。由以上实验结果可以看出，LSDEC算法在聚类效率方面对DEC算法做了有效的改进。

(a) Wine

(b) Satimage

(c) Mfeat4

(d) Letter (abc)

(e) Spambse

(f) MINIST

(g) Doc

(h) Lekumia

图1各数据聚类精度对比

(a) Wine

(b) Satimage

(c) Mfeat4

(d) Letter (abc)

(e) Spambse

(f) MINIST

(g) Doc

(h) Lekumia

图2各数据聚类时间对比

4　结语

LSDEC算法将最小二乘法引入到DEC算法中，先对数据做最小二乘变换降维预处理，然后利用MMC对数据进行二次降维，两次降维有效地降低了DEC算法的时间复杂度。实验结果表明，LSDEC算法不仅在效率上有显著提升，而且在聚类精度上也有所提高。LSDEC算法是一种线性的聚类算法，下一步的工作可以将"核"方法[14]引入到LSDEC算法当中，将其推广成一种非线性的聚类算法。