基于ε-邻域和拉普拉斯矩阵秩约束的谱聚类算法

2020-05-18朱恒东马盈仓

纺织高校基础科学学报 2020年1期

朱恒东,马盈仓,杨婷,张要

(西安工程大学理学院,陕西西安 710048)

0 引言

聚类[1]是将一群不相关的对象划分为相似对象的过程。其中建立在谱图理论基础上的谱聚类算法是目前研究较多、理论基础深厚、应用广泛的聚类方法[2],其本质是将聚类问题转化为图形最优切分问题,相较于传统的聚类算法,可以更好地处理非凸分布等复杂数据。在过去几十年中,谱聚类在机器学习[3]、图像处理[4]、计算机视觉[5]以及系统辨识[6]等领域都有着广泛的应用。谱聚类算法作为近年来热门聚类方法之一[7],很多学者们提出了不同的谱聚类[8],如传统的N-cut算法[9]和R-cut算法,也有最新的基于二部图的快速聚类算法[10]等。

谱聚类算法可以简单分为3 个步骤:①构建相似矩阵;②谱分析;③应用k-means等算法聚类。其中至少存在2个问题。首先,相似矩阵的构造方法很多,不同方法直接影响聚类结果,构造合适的相似矩阵成为了一个问题[11]。Ng等[12]提出了NJW算法,考虑采用高斯核函数来构造相似矩阵。采用全连接构造方法，数据点之间的相似度保留过多影响聚类效果，为了满足稀疏性,文献[13]引入了K-近邻思想。为了避免δ参数的不确定性对聚类结果的影响,Tulin等[14]提出了NC算法,以自适应的方式自行调整参数。文献[15]引入深度学习中的S型函数来构造相似矩阵。虽然取得了一定效果,但也容易被“错误”的数据影响[16]。其次,在谱聚类过程中,一般先是求解特征矩阵,然后对特征矩阵进行K-means得到聚类结果。对于大规模数据聚类问题,谱聚类在谱分析处理中由于涉及大图构建、特征分解等高计算度复杂操作[9,12,17],使得求解难度增加,并且即使求解出特征矩阵,也并不能直接得到聚类结果,而是要进行离散化处理得到结果,使得运行效率不高。导致难以直接使用谱聚类算法解决大规模数据聚类问题。文献[18]不通过求解特征矩阵来聚类,而是采用对拉普拉斯矩阵进行秩约束,保证图有K个连通分支数目,进而选择对最后学习到的相似矩阵直接聚类。近年来关于谱聚类的研究虽然取得了一定进展,但总体上仍处于初级探索阶段,该算法仍然有很大的深入研究空间。

基于以上情况,本文提出新的谱聚类方法。首先,在采用传统高斯核函数构建相似矩阵过程中,引入ε-邻域思想,对亲和矩阵进行稀疏化处理,可以有效利用数据点的局部信息[19],剔除大量不相关点的信息,还可以降低谱分析过程中的计算量;其次,在谱分析过程中,对相似矩阵的拉普拉斯矩阵加上秩约束[20],并且对相似矩阵加上l2,1范数作为正则项来修正模型,保证图的结构性；然后利用学习到的相似矩阵来直接聚类。建立基于ε-邻域和拉普拉斯矩阵秩约束的谱聚类算法(spectral clustering algorithmε-nearest neighbors based on and Laplace matrix rank constraint,简写为ε-RSC)。

1 预备知识

1.1 谱聚类

谱聚类的原理是首先利用样本数据X={x1,x2,…,xn},X∈Rn×k,得到邻接矩阵,然后根据邻接矩阵求得拉普拉斯矩阵,再对拉普拉斯矩阵进行特征分解得到特征向量,最后对特征矩阵进行聚类。常采用高斯核函数[21]构造邻接矩阵A,即

(1)

(2)

进而得到新的函数

(3)

1.2 l2,1范数

使用l2范数的平方作为损失函数对较小的异常值不敏感，但对较大的异常值敏感；使用l1范数作为损失函数对较大的异常值不敏感，对较小的异常值敏感。由文献[22]可知l2,1范数综合了l2范数和l1范数的优点,既无论异常值的大小，l2和l1范数的鲁棒性均可被利用。

性质1[23]对于矩阵X,其中有

‖X‖2,1=tr(XTDX)

(4)

式中：D是对角矩阵,对角元素为

2 模型的建立及求解

2.1 模型建立

谱聚类原始目标函数为

min tr(FTLSF)
st.FTF=1

(5)

(6)

为了不求解特征矩阵F,采用对相似矩阵S聚类。对拉普拉斯矩阵加上秩约束,即rank(LS)=n-K,通过保证图有K个连通分支,保证图的结构性,最终迭代得到聚类结果。式(6)转化为

(7)

式中:λ为常数;A为采用1.1节方法构造的相似矩阵;S为最终学习的相似矩阵。

2.2 模型求解

将式(7)变化为如下模型:

(8)

式中:A为亲和矩阵;S为要学习的相似矩阵。对于S,存在一个函数fi∈Rc×1[20],使得

(9)

此时采用交替迭代优化算法求解,具体步骤为

1) 当S固定时,式(8)变为

min tr(FTLSF)
st.FTF=1,F∈Rn×k

(10)

对拉普拉斯矩阵LS进行特征分解,求解K个最小特征值对应的特征向量,得到F。

2) 当F固定时,结合式(9),式(8)变为

(11)

(12)

根据1.2中l2,1范数的性质1,得

(13)

(14)

(15)

再根据拉格朗日乘子法,得

(16)

对si求偏导,并令其偏导数等于0,得

Dsi-pi-η1-αi=0

(17)

对其中每个数据,有

dijsij-pij-η-αij=0

(18)

令dijsij=0,根据KKT条件,得

(19)

其中(v)+=max(0,v),根据η定义函数

(20)

gi(η)=0

(21)

式中：gi(η)为分段单调递增函数,可用牛顿法迭代求解。值得说明的是,由于在算法过程中借用牛顿迭代法,因此是收敛的。

经过以上交替迭代优化算法计算后,得到最终学习到的相似矩阵。在迭代过程中,因为加入了拉普拉斯矩阵秩约束,通过保证特征矩阵的秩为K个,从而保证图有K个连通分支数目,进而可以直接对相似矩阵直接聚类,得到聚类结果。

2.3 算法流程

根据2.2模型求解,总结梳理ε-RSC算法流程如下:

输入亲和矩阵A∈Rn×n,聚类数K,常数λ

1) 计算亲和矩阵A;

3) for iter=1,2,…,最大迭代次数 do;

4) while不收敛do;

5) 固定F,由F求解vi,初始化S;

6) fori=1,2,…,n;

8) end for;

9) 固定S,由S求解拉普拉斯矩阵,求解F,完成更新F;

10) end while;

11) end for;

12) 解出S,利用图的K个连通分支聚类。

3 实验

为验证算法有效性,将本文ε-RSC算法与K均值(K-means)算法、LRR方法、SR方法以及文献[22]中CLR-L方法进行对比,数据集选取人造数据集和真实数据集。

3.1 评价指标

以聚类准确率和标准化互信息评价算法聚类性能。聚类准确率

(22)

式中:ri和si分别为聚类算法得到的类标签和数据集真实的类标签;n为样本个数;函数δ(x,y)在当x=y时为1,否则为0;map(ri)是一个排列匹配函数,将ri标签映射成与si匹配的等效标签。A值在[0,1]之间,值越大越好。

标准化互信息用于确定聚类的质量,其公式为

(23)

3.2 人造数据集

人造数据集选取Cdata04数据集和双月数据集。Cdata04数据集由4个环型簇组成,形状如四叶草,如图1所示。叶子交汇的地方,由于数据间联系紧密,给聚类分析带来一定难度。双月型数据集是一类典型的非线性数据集,形状如两轮弯月,如图2所示。由于双月型数据的特殊分布,很多聚类算法容易将中间嵌入的地方混聚一类。