鲁棒自适应图正则化聚类算法

董 昊，李玲慧

鲁棒自适应图正则化聚类算法

董 昊，李玲慧

基于L2,1范数及图正则化项思想，提出了鲁棒自适应图正则化聚类算法.此算法不仅使数据矩阵行稀疏，而且增强了鲁棒性，从而提高聚类算法的性能，得到更优质的聚类结果.合成数据集验证了文中提出的聚类算法的有效性.

鲁棒；图正则；聚类

近年来，聚类分析技术在机器学习领域得到深入研究及广泛应用.传统的聚类方法如：kmeans聚类算法［1］、谱聚类算法［2］等已经被应用到各个领域.然而，传统的基于图的聚类方法通常是基于一个给定的数据图与其邻接矩阵，聚类时需要对数据图进行处理才可以提取聚类指标.此外，聚类的过程对于数据图的初始结构的质量要求是非常严格的.为了解决上述问题，Nie等提出了CLR聚类算法［3］.其算法是在给定的数据图的基础上，构建一个新的数据相似性矩阵，使聚类结果可以立即得到.

本文根据CLR聚类算法，基于L2,1范数及图正则化项思想，提出了鲁棒自适应图正则化聚类算法（RAGR）.此算法利用L2,1范数，既使数据行稀疏，又确保数据在几何结构上具有鲁棒性，同时保持矩阵的旋转不变性，从而提高聚类算法的性能，得到更优质的聚类结果.

1 鲁棒自适应图正则化聚类算法

1.1 模型的建立

给定一个具有邻接矩阵的结构图，矩阵M为其邻接矩阵，M∈Rn×n.构建矩阵M的一个相似矩阵U∈Rn×n，其对应的拉普拉斯矩阵为从而得到rank(LU)=n-k，因此U具有可置换的块对角矩阵.根据Nie、Wang和Huang的理论［4］可将基于U的数据点直接划分为k个类别.为了避免U的某些行的元素全是零的情况，给出约束∑juij=1，其中uij≥1.进而建立目标函数如式（1）所示.

1.2 模型的优化

假定αi(LU)表示LU的第i个最小特征值.因为LU半正定，因此αi(LU)≥0.当τ足够大时，式

根据Ky-Fan的极大极小值定理［5］，得出，由 此 给 出RAGR聚类算法的目标函数为

与原目标函数（1）相比，目标函数（2）增加了拉普拉斯正则化项，提高了聚类性能，而且更容易求解.

1.3 目标函数的求解

本文将用交替更新算法对目标函数（2）进行求解.

1）F的迭代更新.固定U，目标函数（2）将被转化为的最优解由LU的最小二乘值的最小特征向量决定［6］.

2）U的迭代更新.固定F，目标函数（2）被转化为

目标函数（3）中对于每一个i是独立的，因此可以单独地解决以下问题

目标函数（5）可以通过迭代法对以下问题进行求解.

其中，R为对角矩阵，第j个对角元素为，uij为当前的解，此方法在每一次迭代中收敛到目标函数（5）的最优解中.

下面用增广拉格朗日函数对目标函数（7）进行求解.

其中，ξ,β≥0是拉格朗日乘子.

其中，(ω)+=max(0,ω).

定义关于ξ的目标函数

1.4 RAGR算法的实现

Algorithm：鲁棒自适应图正则化聚类算法.

输入：矩阵M∈Rn×n，聚类数目k，正则化参数τ．

输出：矩阵M的相似性矩阵U∈Rn×n，其中U有k个连通分量初始化的F∈Rn×n.

While not converge do

2.根据目标函数（7）和（9）更新U.

End while

2 初始图的建立

本文旨在得到一个分块化的相似矩阵U∈Rn×n，因此，必须先得到初始图的邻接矩阵M∈Rn×n.由于矩阵U需要是非负和归一化的，所以矩阵U的每行元素的和应该等于1.因此需要对矩阵M引入相同的约束，即与mij≥0.

给定一组数据集X=[ ]x1,x2,x3,…,xn，定义为数据点xi与xj的距离，每一个最小距离对应一个邻接权mij.另外规定mii=0.下面给出目标函数.

为了确保数据图的稀疏性，限制mi的非零元的个数为q，即‖ ‖mi0=q，需要解决问题，其中为目标函数（11）的最优解.

3 实验结果与分析

首先选取一个100×100的块对角矩阵，其中有五块数据，每一块为20×20维.其中的数据表示一族数据集两个对应点的邻接值，其余所有部分为噪声.每一块内的邻接数据是在0到1之间随机产生的；噪声是在0到m间随机产生的，其中m分别取0.65、0.75、0.85进行试验，此外随机挑选20个噪声数据点，将他们的值设置成1.

参数的设置为：聚类数目k=5.对于正则化参数τ首先令τ=0.1.在每一次迭代中，如果LU的特征值数目大于k，则取τ的如果LU的特征值数目小于k，则取τ的2倍；当LU的特征值数目等于k时，停止迭代.随机产生的矩阵以及文中所述方法在不同设置下的聚类结果，如图1所示.

图1 随机产生的矩阵以及不同设置下的聚类结果

本文所提到的聚类算法（RAGR）与比例分割（Ratio Cut）、归一化分割（Normalized Cut）在合成数据中不同噪声环境下标准聚类精度（ACC）和归一化互信息（NMI）的比对结果，如表1所示.

表1 RAGR、Ratio Cut、Normalized Cut在合成数据中不同噪声环境下的ACC和NMI的比对结果

4 结论

在相同的初始化条件下，用不同的聚类方法，重复超过60次试验.实验结果表明当噪声逐渐增大时，本文所述聚类算法的精确度明显高于其他传统聚类算法的精确度，从而体现了本文所述聚类算法的鲁棒性.合成数据集实验结果证明了本文所述聚类算法的可行性及有效性.

O29

A

1008-7974（2018）01-0035-04

10.13877/j.cnki.cn22-1284.2018.02.010

2017-05-22

辽宁省自然科学基金项目（60875029）.

董昊，女，辽宁凤城人，辽宁师范大学数学学院硕士研究生（辽宁 大连 116029）.

［1］周爱武，于亚飞.K-Means聚类算法的研究［J］.计算机技术与发展，2011，21（2）：62-65.

［2］U Luxburg.A tutorial on spectral clustering［J］.Statistics and Computing，2007，17（4）：395-416.

［3］Nie F，Wang X，Jordan M，et al.The Constrained Laplacian Rank Algorithm forGraph-Based Clustering［J］.Artificial Intelligence，Phoenix，2016，34（5）：1012-1016.

［4］Nie F，Wang X，Huang H.Clustering and projected clustering with adaptive neighbors［J］.Knowledge Discovery and Data Mining，2014，42（6）：977-986.

［5］Fan K.On a theorem of Weyl concerning eigenvalues of linear transformations［J］.Natl Acad Sci，1949，35（11）：652-655.

［6］Nie F，Huang H，Cai X C.Efficient and robust feature selection via joint 2，1-norms minimization［J］.Neural Information Processing Systems，2010，37（12）：