南京大学学报(自然科学), 2022, 58(3): 469-482 doi: 10.13232/j.cnki.jnju.2022.03.011

基于相关熵和流形正则化的图像聚类

时照群, 刘兆伟,, 刘惊雷,

烟台大学计算机与控制工程学院,烟台,264005

Image clustering based on correntropy and manifold regularization

Shi Zhaoqun, Liu Zhaowei,, Liu Jinglei,

School of Computer and Control Engineering,Yantai University,Yantai,264005,China

通讯作者: E⁃mail:lzw@ytu.edu.cnE⁃mail: jinglei_liu@sina.com

收稿日期: 2022-01-11  

基金资助: 国家自然科学基金.  62072391.  62172351
山东省自然科学基金.  ZR2020MF148

Received: 2022-01-11  

摘要

近年来,聚类作为机器学习、数据挖掘等领域的基本问题受到广泛的关注及研究,然而数据中普遍存在的噪声和异常值严重影响聚类结果.提出一个基于相关熵和流形正则化的聚类框架CRNMF (Correntropy and Manifold Regularization Non⁃Negative Matrix Factorization).首先,采用基于相关熵的非负矩阵分解(Non⁃Negative Matrix Factorization,NMF)作为损失函数来抑制非高斯噪声和异常值的影响;其次,充分考虑数据的结构信息,采用流形正则化学习数据的局部结构,并通过l2,1⁃范数对非负矩阵进行稀疏约束;最后,利用半二次优化技术(Half⁃Quadratic Optimization Technique,HQ)进行优化,并分析了收敛性和计算复杂度.在五个图像数据集上进行测试,实验结果表明,提出的框架在图像聚类任务中具有较好的有效性和鲁棒性.

关键词: 非负矩阵分解 ; 相关熵 ; 流形正则化 ; 半二次优化技术 ; 图像聚类

Abstract

As a basic problem in machine learning,data mining and other fields,clustering has received extensive attention and research in recent years. However,the widespread noise and outliers of data affect the clustering results seriously. Therefore,a clustering framework based on correntropy and manifold regularization (CRNMF) is proposed. First,the Non⁃Negative Matrix Factorization (NMF) based on correntropy is used as the loss function to suppress the effects of non⁃Gaussian noise and outliers. Second,the structure information of the data is fully considered,the manifold regularization is used to learn the local structure of the data,and the sparse constraint is applied to the non⁃negative matrix by l2,1⁃norm. Finally,the Half⁃Quadratic Optimization Technique (HQ) is used to optimize the algorithm,and the convergence and computational complexity are analyzed. Experimental results show that the proposed CRNMF is effective and robust on five image datasets.

Keywords: Non⁃Negative Matrix Factorization (NMF) ; correntropy ; manifold regularization ; Half⁃Quadratic Optimization Technique (HQ) ; image clustering

PDF (1300KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

时照群, 刘兆伟, 刘惊雷. 基于相关熵和流形正则化的图像聚类. 南京大学学报(自然科学)[J], 2022, 58(3): 469-482 doi:10.13232/j.cnki.jnju.2022.03.011

Shi Zhaoqun, Liu Zhaowei, Liu Jinglei. Image clustering based on correntropy and manifold regularization. Journal of nanjing University[J], 2022, 58(3): 469-482 doi:10.13232/j.cnki.jnju.2022.03.011

聚类的目的是将相似度高的数据点聚为一类,将相似度低的数据点聚为不同类.由于聚类在机器学习、数据挖掘、计算机视觉等领域受到广泛关注,如何降低噪声和异常值对聚类结果的影响已成为一个重要课题.几十年来,大量的聚类算法被提出,例如k⁃means1、谱聚类(Spectral Clustering,SC)2和非负矩阵分解(Non⁃Negative Matrix Factorization,NMF)3等.k⁃means既是基于划分的聚类算法,也是基于矩阵分解的聚类算法,虽然实现速度快,但无法处理非线性数据.谱聚类可以用来处理非线性数据,但其计算成本较高.大多数情况下,现实世界聚类任务中遇到的数据维数非常高,传统的聚类算法及其变种4-6因为噪声和冗余的影响,处理高维数据的性能不佳,因此,发现高维数据的低维表示尤为重要.由于NMF对数据表示良好的可解释性和明确的物理意义,已成为最流行的维度还原算法之一7-8.本文主要研究NMF在聚类中的应用.

传统矩阵分解有低秩表示(Latent Low⁃Rank Representation,LRR)9、主成分分析(Principal Components Analysis,PCA)10和奇异值分解(Singular Value Decomposition,SVD)11等.与它们不同,NMF的目标是学习两个低维非负矩阵,即分解后的两个非负矩阵的乘积能够逼近原始数据矩阵.由于施加在低维子空间中分解矩阵上的非负约束条件且只允许学习矩阵的加法组合,NMF只学习基于部分的数据表示12-13.更重要的是,NMF符合大脑中人类认知过程的直观概念,即结合部分形成整体,这已在心理学和生理学中得到研究14-15.因此,NMF可以被认为是一种优秀的降维算法,并已成功应用于包括文本分析和图像处理在内的各种实际应用中.一般地,大多数传统NMF及其扩展算法中的矩阵分解的目标函数或优化准则是基于欧式距离或KL (Kullback⁃Leibler)散度,因为它们具有简单、良好的数学性质和对高斯噪声不敏感等优点.然而在许多实际应用中,数据通常包含不同类型的非高斯噪声和异常值,这种情况下,传统NMF算法及其扩展的性能很差.在Lee and Seung12之后,受到上述原始NMF优越特性的激励,NMF受欢迎的程度日益提高.随后,为了解决不同的问题,提出了许多以NMF为代表的变体和扩展.但是,如果不考虑数据的流形结构,传统NMF算法的性能依旧很差.因此,保持数据流形结构的重要性在机器学习、数据挖掘和模式识别的研究领域引起了相当大的关注16-18.例如,图正则化非负矩阵分解(Graph Regularized Non⁃Negative Matrix Factorization,GNMF)充分利用数据的固有几何结构,通过拉普拉斯正则化将数据空间建模为嵌入在环境空间中的流形.GNMF同时考虑了原始空间中数据点的线性和非线性关系,与只考虑欧氏距离的普通NMF区别很大19-20,因此GNMF比普通NMF更适合聚类问题.在此基础上,Guan et al21充分考虑数据的几何结构和不同类别的判别信息,提出流形正则化判别非负矩阵分解算法(Manifold Regularized Discriminative Non⁃Negative Matrix Factorization,MD⁃NMF).Shang et al22提出一种考虑样本流形和特征流形的图对偶正则化算法(Graph Dual Regularization Non⁃Negative Matrix Factorization,DNMF),用于处理共聚类问题.Zeng et al23提出超图正则化算法(Hyper⁃Graph Regularized Non⁃Negative Matrix Factorization,HNMF)来更好地反映数据中固有的几何结构.Li et al24同时考虑标签信息和局部流形正则化,提出基于图的判别非负矩阵分解算法 (Graph⁃Based Discriminative Non⁃Negative Matrix Factorization,GDNMF),通过构造p⁃近邻图对数据的局部几何结构进行编码,并在NMF中考虑标签信息,增强了聚类表示的区分能力.

以上算法都使用欧式距离来最小化原始数据矩阵和重构矩阵之间的距离,由于欧式距离的可解释性和可处理性,已被广泛应用于基于NMF的算法中.然而,基于欧式距离的NMF对非高斯噪声和异常值敏感,进行聚类任务时性能显著降低,因此,相关熵被提出用于处理基于NMF的任务.Wang et al25将相关熵引入GNMF,提出一种用于图像聚类的非负矩阵分解算法(Correntropy Induced Metric Based Graph Regularized Non⁃Negative Matrix Factorization,CGNMF),在考虑数据流形结构的同时增强算法的鲁棒性.Du et al26提出一种基于相关熵诱导度量的鲁棒算法(Robust Non⁃Negative Matrix Factorization Method Based on the Correntropy Induced Metric,CIM⁃NMF),通过结合关于离群点的结构知识导出用于处理离群点的基于行的CIM⁃NMF.Li et al27通过最大化用于非可视化图像聚类的相关熵准则,发展图正则化的非负矩阵分解算法(Graph Regularized Non⁃Negative Matrix Factorization by Maximizing Correntropy,GRNMF).Zhou et al28提出一种无监督的特征选择算法,称为基于相关熵的全局和局部保持鲁棒稀疏子空间学习算法(Global and Local Structure Preserving Robust Sparse Subspace Learning,GLoRSS).谢林江和尹东29提出基于最大相关熵准则的鲁棒度量学习算法,将相关熵引入度量学习来更好地实现分类.Yu et al30提出用于癌症聚类的超图正则化非负矩阵分解算法(Correntropy⁃Based Hypergraph Regularized Non⁃Negative Matrix Factorization,CHNMF),用相关熵代替欧氏距离来提高鲁棒性并引入超图正则化项,在癌症数据集上效果较好.

同时,引入范数对矩阵进行稀疏约束来发展一些稳健的NMF算法.Peng et al31提出一种基于相关熵的鲁棒非负矩阵分解算法(l1⁃Norm Non⁃Negative Matrix Factorization Based on Maximum Correntropy Criterion,l1⁃CNMF),将传统的NMF算法与l1⁃范数和最大相关熵准则结合,对系数矩阵进行稀疏约束,在图像聚类任务中取得了较好的效果.Zhang et al32提出基于l2,1⁃范数的矩阵分解来获得抗噪声和离群点的鲁棒解.Chen et al33提出基于流形正则化和稀疏学习的鲁棒非负矩阵分解算法(Robust Non⁃Negative Matrix Factorization via Jointly Manifold Regularization and Sparse Learning,MS⁃RNMF),在NMF中引入l2,1⁃范数约束,同时对基矩阵和系数矩阵进行稀疏约束.

然而,传统的基于NMF的聚类算法仍然具有以下问题:(1)容易受非高斯噪声和异常值的影响而产生较大的误差;(2)无法充分利用数据的结构信息;(3)没有利用矩阵的稀疏性,导致计算复杂,优化时间长.

受上述工作启发,为了充分保持数据的结构信息并继承传统NMF算法的优点,本文提出基于相关熵和流形正则化的图像聚类算法 (CRNMF).在提出的框架中引入相关熵代替欧式距离来减轻非高斯噪声的影响.另外,充分考虑数据的结构信息并通过l2,1⁃范数进行稀疏约束,减轻异常值的影响.CRNMF算法的流程如图1所示.

本文的主要贡献如下:

(1)针对图像聚类问题,提出一个基于相关熵和流形正则化的联合优化框架CRNMF,将相关熵、稀疏约束和流形正则整合到一个统一的目标函数中.

(2)通过相关熵代替欧式距离,通过流形正则化保存数据的局部结构,并引入l2,1⁃范数对非负矩阵进行稀疏约束,增强了算法的抗非高斯噪声能力和局部平滑性.

(3)利用半二次优化技术(Half⁃Quadratic Optimization Technique,HQ)对CRNMF进行优化,将非凸目标函数转化为乘法形式的二次函数,导出算法的更新规则,同时在理论上证明了算法的收敛性,并分析了计算复杂度.

图1

图1   CRNMF框架

Fig.1   The framework of CRNMF


(4)在五个图像数据集上进行实验,实验结果表明,提出的算法在图像聚类任务中有较好的有效性和鲁棒性.

1 相关工作

首先,本文工作使用的符号如表1所示.

表1   相关符号

Table 1  Related notations

符 号描 述
XRM×N数据矩阵
U基矩阵
V潜在数据表示矩阵
L拉普拉斯矩阵
S相似度矩阵
D度矩阵
H,M1,M2对角矩阵
σ核带宽参数
p图最近邻数
β稀疏参数
η正则化参数
λ权衡参数
ϱ变量标量
M特征维度
N样本数量
K嵌入维度
E期望算子
κ,核函数
T转置运算符
Tr矩阵的迹
FFrobenius范数
2,1l2,1⁃范数

新窗口打开| 下载CSV


1.1 非负矩阵分解 (NMF)

NMF的主要思想是将非负数据矩阵近似分解为两个低维非负矩阵,其乘积尽可能逼近原数据矩阵以找到原始数据矩阵的恰当低维表示.

假设X=x1,x2,,xN0M×N为原始数据矩阵,X的每一列表示包含M个元素的样本向量,NMF3可以表示为:

XUVT

其中,K<minN,M为正整数,U=uik0M×KV=vjk0N×K分别表示基矩阵和系数矩阵.

多数情况下,传统的NMF通常使用欧式距离作为度量,表示为以下优化问题:

𝒪SED=j=1Ni=1MXij-UVTij2=X-UVTF2

其中,F为Frobenius范数,T为转置运算符.

虽然UV式(2)中是非凸的,但不是同时非凸.因此,传统NMF的乘法更新规则如下:

UUXVUVTV
VVXTUVUTU

实际上,通常KM并且KN.因此,NMF基本上为寻找原始数据矩阵的压缩近似.近似值按列查看如下所示:

xjk=1Kukvjk

其中, ukU的第k列向量.因此,数据向量 xjU的列的线性组合近似,由V的分量加权.

与其他矩阵分解算法最大的不同是,NMF对UV的非负约束只允许碱基之间的加性组合,因此NMF是基于部分的表示.由于基于部分表示的优点,NMF已经被应用于许多现实世界的任务,如聚类任务、人脸分析、基因表达分析等19.

1.2 流形正则化

在许多现实世界的应用中,数据点常位于一个低维的流形上,因此流形学习引起了巨大的关注.通常,邻近的数据点可能有相似的特征并被分类或划分到同一组中.假设邻近的数据点在新的数据空间中也是相近的,称为“流形假设”34.将“流形假设”引入非负矩阵分解中,即局部流形学习,以期望小邻域内的邻近数据点可以共享内在的几何结构.

为了捕捉数据的内在几何结构使用基于图的流形方法,使用热核函数构建最近邻图来度量数据点之间的相似度.若两个数据点在原始空间中相似则在目标空间中也相似.给定具有N个数据点的数据集X=x1,x2,,xN,根据其中任意两点间的相似度建立相似度矩阵SN×N,定义:

S=e-xi-xj22λ2,ij0,                 

其中,λ是一个权衡参数.

为了保留局部信息,结合流形正则化和局部相似度使数据点达到无差异33.vivj 是与数据点xixj 关联的特征向量.通过12mini,jvi-vj2测量数据点vivj 之间的微小差异.因此,局部相似度得分越高则数据点之间的差异越小,定义如下:

𝒪data=i,j=1Ndvi,vj×S=TrVTDV-TrVTSV=TrVTLV

其中,Tr表示矩阵的迹,度矩阵D=j=1NS,并且LN×N为拉普拉斯矩阵,L=D-S.

1.3 相关熵

由于对非高斯噪声和异常值的鲁棒性,相关熵已被广泛应用.作为一个非线性和局部相似性度量函数,相关熵直接与相似随机变量AB在联合空间邻域中的概率有关,定义如下2835-36

VA,B=EκA,B=κa,bdFABa,b

其中,E  κ,分别是期望算子和核函数,FABa,b表示A,B的联合分布函数.核函数κ,定义如下:

κσa,b=ga,b=e-a-b22σ2

其中,σ>0是控制高斯核的所有属性的核带宽参数.由于联合分布函数FABa,b的值几乎不可能精确估计,因此,通常使用有限数量的数据样本an,bnn=1N将相关熵表示为:

V̂N,σA,B=1Nn=1Ngan-bn

其中,V̂N,σ代表相关熵的估计量.

从两个不同的方面进行分析来说明相关熵的鲁棒性.首先,可以利用高斯核的泰勒级数展开重写式(8):

VA,B=n=0-1n2nσ2nn!a-b2ndFABa,b

从统计学角度看,相关熵可以捕捉高阶矩(即所有的偶数阶矩),这有助于抑制非高斯噪声和异常值的负面影响.其次,每个数据样本对相关熵的贡献在很大程度上取决于沿联合空间中a=b的高斯核函数.此外,如果样本点相距很近,则相关熵表现为l2⁃范数距离;如果样本点相距较远,则相关熵表现为l1⁃范数距离;如果样本点相距非常远,则相关熵表现为l0⁃范数.因此,基于上述分析,相关熵对非高斯噪声和异常值不敏感.

1.4 半二次优化技术(HQ)

通常,基于信息论学习(Information Theoretic Learning,ITL)方法的目标函数是非线性的且非凸的,难以直接进行优化.幸运的是,HQ常被用来解决基于ITL的优化问题30-3136.假设ϕe是向量eM的潜在成本函数,定义如下:

ϕe=i=1Mϕei

其中,ei 是向量 e 的第i个元素.基于最小化的HQ,通过引入辅助变量ϱi来固定ei,方法如下:

ϕei=minϱiQei,ϱi+φϱi

其中,ϱi仅取决于ϕ  Qei,ϱi为HQ函数,

φ  ϕ  的双势函数.本文考虑Qei,ϱi的乘法形式,定义如下:

Qei,ϱi=12ϱiei2

假设Qe,ϱ=i=1MQei,ϱi,其中ϱ=ϱ1,,ϱM.结合式(13)和式(14),可以得到式(13)的向量形式如下:

ϕe=minϱQe,ϱ+i=1Mφϱi

2 CRNMF算法

2.1 目标函数

如前所述,为了克服传统NMF算法的局限性,学习有区别的数据表示,充分利用数据的结构信息,增强矩阵的稀疏性,本文提出基于相关熵和流形正则化的CRNMF框架.CRNMF用相关熵代替欧式距离,通过流形正则化学习局部结构,并引入l2,1⁃范数对非负矩阵进行约束,有效减轻了非高斯噪声和异常值的影响,具有良好的有效性和鲁棒性.

CRNMF目标函数如下:

maxU,V𝒪=i=1Mgj=1NXij-UVTij2-βU2,1+V2,1-ηTrVTLV

其中,第一项为用相关熵代替欧式距离,第二项是对聚类中心U和聚类指示器V进行稀疏约束,第三项是流形正则,β为稀疏参数,η为正则化参数.

2.2 算法优化

显然,上述目标函数(16)的优化问题很难直接解决,因为目标函数(16)中的UV是非二次和非凸的.近年来,HQ已成功用于解决ITL中的优化问题37,因此,本文使用基于共轭函数理论的HQ对CRNMF进行优化.首先将非凸目标函数转化为乘法形式的二次函数,然后利用乘法更新规则对转化后的二次函数进行求解.基于凸共轭函数的性质,有以下命题:

命题1

存在gx的凸共轭函数φ,使:

gx=maxϱϱx2σ2-φϱ

其中,ϱ是一个标量变量,对于一个固定的xϱ的最大值为ϱ=-gx.

显然,CRNMF的优化问题(16)可以通过使用命题1进行优化:

maxU,V,ϱ𝒪̂=i=1Mϱiσ2j=1NXij-UVTij2-φϱi-βU2,1+V2,1-ηTrVTLV

其中,𝒪̂表示𝒪的扩充目标函数,并且ϱ=ϱ1,,ϱMT为辅助向量.当固定UV,并使𝒪̂最大时,辅助参数ϱi的计算式如下:

ϱi=-gj=1NXij-UVTij2=-e-j=1NXij-UVTij22σ2

由于应用的多样性,没有一个统一的策略来选择最佳的核带宽参数σ.因此,σ通常是根据经验确定.本文中核带宽参数σ的计算式如下:

σ=12Mi=1Mj=1NXij-UVTij2

类似地,固定ϱσ时可以将式(18)改写为:

maxU,V𝒪̂=i=1Mϱij=1NXij-UVTij2-βU2,1+V2,1-ηTrVTLV

式(21)相当于以下优化问题:

minU,V𝒪̂1=-i=1Mϱij=1NXij-UVTij2+βU2,1+V2,1+ηTrVTLV=TrXTHX-2VUTHX+VUTHUVT+βTrUM1UT+VM2VT+ηTrVTLV

其中,H,M1,M2为正对角矩阵.

Hii=-ϱi=e-j=1NXij-UVTij22σ2
M1ii=1Ui,i=1,2,,M
M2jj=1Vj,j=1,2,,N

假设Φ=Φik0M×KΨ=Ψjk0N×K分别是UV的拉格朗日乘子,对于约束U0V0,有以下等价目标函数:

=TrXTHX-2VUTHX+VUTHUVT+βTrUM1UT+VM2VT+ηTrVTLV+TrΦUT+TrΨVT

更新U:固定VH更新U.

因为:

U=-2HXV+2HUVTV+2βM1U+Φ

使用KKT条件Φikuik=0,可得以下更新规则:

uikuikHXVikHUVTV+βM1Uik

更新V:固定UH更新V.

因为:

V=-2XTHU+2VUTHU+2βM2V+2ηLV+Ψ

使用KKT条件Ψjkvjk=0,可得以下更新规则:

vjkvjkXTHU+ηSVjkVUTHU+βM2V+ηDVjk

完整的CRNMF算法总结在算法1中.

算法1

CRNMF算法

输入:数据矩阵X,图最近邻数p,参数βη,嵌入维度K,最大迭代次数T.

输出:基矩阵U和潜在数据表示矩阵V.

1.随机初始化UV

2.根据式(6)计算相似度矩阵S

3.重复;

4.根据式(24)和式(25)分别计算对角矩阵M1,M2

5.根据式(20)更新σ

6.根据式(23)更新H

7.根据式(28)更新U

8.根据式(30)更新V

9.直到收敛.

3 算法分析

3.1 收敛性分析

不失一般性,使用辅助函数法证明提出算法的收敛性,并有以下定理:

定理1

CRNMF中的目标函数𝒪̂1在更新规则(28)和(30)下不递增.

在证明定理1之前,首先给出辅助函数和引理1的定义如下:

定义1

Gv,v'Fv的辅助函数,满足下列条件:

Gv,v'Fv,Gv,v=Fv

引理1

如果GF的辅助函数,那么F在从t迭代到t+1的以下更新步骤下不递增:

vt+1=argminVGv,vt

证明

Fvt+1Gvt+1,vtGvt,vt=Fvt

显然,如果使用引理1和更新规则(28)和(30)证明最小化目标函数𝒪̂1的辅助函数G,则可以得出结论,在更新规则(28)和(30)下,𝒪̂1不递增.假设uikvjk是矩阵UV中的任意项,并且将FikFjk定义为分别只涉及uik项和vjk项的部分,则相对于UV的一阶和二阶偏导数为:

Fik'=𝒪̂1Uik=-2HXV+2HUVTVik+2βM1Uik
Fik''=2𝒪̂1U2ik=2HiiVTVkk+2βM1ii
Fjk'=𝒪̂1Vjk=-2XTHU+2VUTHUjk+2βM2Vjk+2ηLVjk
Fjk''=2𝒪̂1V2jk=2UTHUkk+2βM2jj+2ηLjj

本质上,更新规则是元素式的.因此,需要证明FikFjk在规则(28)和(30)下都是不递增的.

引理2

Gu,uiktGv,vjktFikFjk的辅助函数,定义如下:

Gu,uikt=Fikuikt+Fik'u-uikt+HUVTV+βM1Uikuiktu-uikt2
Gv,vjkt=Fjkvjkt+Fjk'v-vjkt+VUTHU+βM2V+ηDVjkvjktv-vjkt2

证明

显然,Gu,u=FikuGv,v=Fjkv,接下来需要证明Gu,uiktFikuGv,vjktFjkv.结合式(33)和式(34),将Fiku的泰勒级数展开,得到以下等式:

Fiku=Fikuikt+Fik'uiktu-uikt+12Fik''uiktu-uikt2=Fikuikt+Fik'uiktu-uikt+u-uikt2HiiVTVkk+βM1ii

为了保证Gu,uiktFiku,结合式(37)和式(39),得到以下不等式:

HUVTV+βM1UikuiktHiiVTVkk+βM1ii

因为:

HUVTVik=l=1KuiltHiiVTVlkuiktHiiVTVkk

式(40)得证.所以,Gu,uiktFiku.

结合式(35)和式(36),将Fjkv的泰勒级数展开,得到以下等式:

Fjkv=Fjkvjkt+Fjk'vjktv-vjkt+12Fjk''vjktv-vjkt2=Fjkvjkt+Fjk'vjktv-vjkt+v-vjkt2UTHUkk+βM2jj+ηLjj

为了保证Gv,vjktFjkv,结合式(38)和式(42),得到以下不等式:

VUTHU+βM2V+ηDVjkvjktUTHUkk+βM2jj+ηLjj

由于β>0η>0

VUTHUjk=l=1KvjltUTHUlkvjktUTHUkk

并且

ηDVjk=ηl=1NDjlvlktηDjjvjktηD-Sjjvjkt=ηLjjvjkt

式(43)得证.所以,Gv,vjktFjkv.

综上,引理2得证.

接下来,证明定理1.

证明

对于目标函数𝒪̂1,将Gu,uikt替换为式(37),将Gv,vjkt替换为式(38),导出以下更新规则:

uikt+1=uikt-uiktFik'uikt2HUVTV+βM1Uik=uiktHXVikHUVTV+βM1Uik
vjkt+1=vjkt-vjktFjk'vjkt2VUTHU+βM2V+ηDVjk=vjkXTHU+ηSVjkVUTHU+βM2V+ηDVjk

3.2 鲁棒性分析

本文通过HQ对CRNMF算法进行优化,将非凸优化问题转化为迭代加权的NMF问题.由命题1可知,当固定矩阵UV时,数据矩阵X中每个样本的每一项都被赋予一个权重.权重的计算如下:

ϱi=-gj=1NXij-(UVT)ij2=-e-j=1NXij-UVTij22σ2

根据式(48)可知,当数据受损严重时将被分配较小的权重,因而对目标函数的贡献较小.通过引入相关熵和l2,1⁃范数,CRNMF能够有效地减轻噪声对聚类结果的影响.因此,CRNMF算法对噪声和异常值不敏感.

3.3 计算复杂度分析

计算复杂度对于评估算法的效率非常重要.分析每次更新迭代的CRNMF计算成本,并使用最常用的符号O来表示所提出算法的复杂度.首先,根据式(6)可知,CRNMF需要OMN2构造p⁃近邻图来计算相似度矩阵,M为特征维度,N为样本数量.此外,根据式(20)、式(23)、式(28)和式(30)更新σHUV 的计算复杂度为OTMNKK为嵌入维度.假设提出的算法在T次迭代后停止,则CRNMF的整体计算复杂度为OMN2+TMNK.

4 实验

4.1 实验设置

4.1.1 实验环境

所有算法均用Matlab R2018a实现,在一台2.40 GHz Intel Core CPU 16.0 GB RAM和Windows 10操作系统的计算机上进行.

4.1.2 数据集

实验使用五个图像数据集,分别为CMU PIE,ORL,UMIST,YaleB和COIL20.用于聚类任务的数据集的详细特征如表2所示,图2图6给出了每个数据集的图像样本.对于每个图像数据集,将数据格式化为具有相同维数和样本数大小的数据矩阵,并将每个样本(即数据矩阵的每一列)归一化为欧几里得长度.

表 2   实验中使用的数据集描述

Table 2  Description of datasets used in experiments

数据集样本数量维度
CMU PIE2856102468
ORL400102440
UMIST575102420
YaleB2414102438
COIL201440102420

新窗口打开| 下载CSV


CMU PIE:包含68个人的2856幅图像,每个人有13种不同的姿态、4种不同表情和43种不同的光照条件.

ORL:剑桥大学提出的数据集,包含40个人的400幅图像.每个人有10张面部表情图像.

UMIST:包含20个人的575幅图像,每个主题由不同种族、性别或外貌的图像组成,并包含从侧面到正面的一系列姿势.

YaleB:包含38个人的2414幅正面人脸图像(大约每人64幅图像),所有图像都已损坏.

COIL20:哥伦比亚大学提出的数据集,包含20个对象的1440幅图像,每个对象都由72幅不同角度的图像组成.

图2

图2   CMU PIE数据集样本

Fig.2   Samples of CMU PIE dataset


图3

图3   ORL数据集样本

Fig.3   Samples of ORL dataset


图4

图4   UMIST数据集样本

Fig.4   Samples of UMIST dataset


图5

图5   YaleB数据集样本

Fig.5   Samples of YaleB dataset


图6

图6   COIL20数据集样本

Fig.6   Samples of COIL20 dataset


4.1.3 评价指标

为了衡量聚类性能,采用三个常用的评价指标,即聚类精度(ACC)、归一化互信息(NMI)和纯度(PUR).

聚类精度(ACC)定义如下:

 ACC=Nn=1δrn,mapcnN

其中,N是数据集的总数,rncn分别是数据集提供的标签和聚类标签.δh,z表示δ函数,当

h=zδ函数返回1,否则返回0.map是通过使用Kuhn⁃Munkres算法38将每个聚类标签映射到来自数据集的等价标签的映射函数.

归一化互信息(NMI)定义如下:

NMI=Ni=1Nj=1ni,jlgni,jninjNi=1nilgninNj=1n̂jlgnjn

其中,nin̂j分别表示第i个簇和第j个类的大小,ni,j表示它们的交集中的数据量,N是簇的数量.

纯度(PUR)定义如下:

PUR=1nNi=1maxnij

其中,nij是簇中属于第i类数据点的数量.

具体地,聚类精度(ACC)计算聚类中的数据点来自同一类的百分比;归一化互信息(NMI)衡量不同簇的相似性;纯度(PUR)衡量聚类中的数据点来自一个类的程度.所有评价指标范围是0到1,值越大,聚类性能越好.

4.1.4 比较算法

为了证明提出的CRNMF算法在聚类任务中的有效性和鲁棒性,将CRNMF与七种相关聚类算法进行比较,它们是k⁃means,NMF,GNMF19,CGNMF25,GDNMF24,GLoRSS[28l1⁃CNMF31.在这些比较算法中,k⁃means是基线.

(1)k⁃means算法是应用最广泛的聚类算法之一,常被用于聚类算法的基线.

(2)非负矩阵分解(NMF)将原始数据矩阵分解为两个非负矩阵,实现了高维数据的低维表示,以更好地应用于聚类任务.

(3)图正则化非负矩阵分解(GNMF)通过结合拉普拉斯正则化来考虑流形数据上的固有几何结构.

(4)基于相关熵诱导度量的图正则化非负矩阵分解算法(CGNMF)将相关熵引入GNMF,在保持数据几何结构的同时增强算法的抗噪声能力.

(5)基于图的带标签信息的判别非负矩阵分解(GDNMF)是在考虑了数据的局部几何结构的同时,在NMF中引入了标签信息.

(6)GLoRSS是一种基于最大相关熵准则的鲁棒子空间学习算法.

(7)l1⁃CNMF是基于最大相关熵准则的l1⁃范数非负矩阵分解算法,该算法用相关熵提高鲁棒性并且对系数矩阵进行l1⁃范数约束.

4.1.5 其他设置

实验需要预先设置四个主要参数,分别是图最近邻数p、稀疏参数β、正则化参数η和嵌入维度K.在不提及其他方面的情况下,将参数pβη分别设置为5,0.1,100,嵌入维度K设置为簇的数量.热核函数涉及的权衡参数λ设置为1,CRNMF中相关熵使用的核带宽参数σ式(20)计算.GNMF算法的正则化参数设置为100.CGNMF算法的正则化参数设置为10-6.GDNMF算法的正则化参数设置为1,标签约束参数在1,5,10,100中选取.GLoRSS算法的局部结构保持项参数设置为1,稀疏参数在0.001,

0.01,0.1,1,10,100中选取.l1⁃CNMF算法的稀疏参数设置为0.1.与直接应用于原始数据的

k⁃means不同,其他算法的聚类过程包括两个主要步骤:(1)获得原始数据矩阵的潜在低维表示矩阵;(2)对学习的表示矩阵运用k⁃means算法.根据经验,最大迭代次数设置为300次,并对所有算法进行20次具有不同初始值的相关蒙特卡罗方法.对于每个数据集,计算出平均结果作为所有算法的最终聚类结果,并突出显示最佳结果.

4.2 聚类结果

在五个图像数据集上的实验结果如表3所示,表中粗体字为结果最优.可以看出,提出的CRNMF算法基本在所有图像数据集上都获得了最佳的聚类性能,在大多数情况下,CRNMF在精度(ACC)、归一化互信息(NMI)和纯度(PUR)上优于其他算法.例如,在五个图像数据集上,CRNMF的聚类性能比GNMF有明显提高,可以证明相关熵的有效性.在CMU PIE数据集上,CRNMF的聚类精度(ACC)、归一化互信息(NMI)和纯度(PUR)比CGNMF分别提高1.94%,3.95%和0.54%,证明增加稀疏约束在一定程度上可以提高聚类结果.

表3   本文算法和七个对比算法在五个数据集上的聚类结果:精度、归一化互信息和纯度

Table 3  Clustering results of ACCNMI and PUR by our algorithm and other algorithms on five image datasets

DatasetACC
k⁃meansNMFGNMFCGNMFGDNMFGLoRSSl1⁃CNMFCRNMF
CMU PIE24.23%51.32%76.22%76.36%76.07%72.35%73.89%78.30%
ORL49.02%58.66%60.15%60.69%56.07%56.31%61.62%61.73%
UMIST40.05%49.34%53.70%54.67%54.47%51.31%54.35%63.13%
YaleB07.25%30.47%31.33%34.47%33.39%33.07%33.97%35.42%
COIL2059.72%65.77%71.84%75.46%79.83%73.12%76.33%81.67%
DatasetNMI
k⁃meansNMFGNMFCGNMFGDNMFGLoRSSl1⁃CNMFCRNMF
CMU PIE53.65%73.26%88.31%88.57%88.13%85.14%87.25%92.52%
ORL69.23%50.14%73.38%74.76%73.46%73.76%73.88%74.93%
UMIST58.04%46.92%70.84%74.61%71.07%70.91%74.13%76.75%
YaleB08.18%38.12%42.70%42.19%42.08%41.29%42.78%53.06%
COIL2070.05%71.98%79.53%85.99%88.33%82.30%87.06%90.03%
DatasetPUR
k⁃meansNMFGNMFCGNMFGDNMFGLoRSSl1⁃CNMFCRNMF
CMU PIE30.62%59.49%80.67%86.25%87.46%84.33%86.70%86.79%
ORL59.20%60.96%64.22%66.15%61.97%62.23%65.41%66.18%
UMIST45.73%54.73%66.83%67.84%73.04%64.19%67.68%67.65%
YaleB12.21%32.15%38.91%39.98%39.99%38.34%39.57%40.49%
COIL2068.59%74.57%73.97%84.77%85.83%83.31%85.43%86.39%

新窗口打开| 下载CSV


在所有数据集上,CRNMF的聚类结果均优于l1⁃CNMF,证明利用l2,1⁃范数对矩阵约束的有效性.与传统的聚类算法相比,CRNMF在大多数情况下优于这些比较算法的主要原因可以概括如下:该算法在目标函数中使用相关熵代替欧式距离,可以减少非高斯噪声污染对数据集的负面影响;CRNMF还充分考虑了数据的局部结构,并通过l2,1⁃范数对矩阵进行稀疏约束,在保持局部平滑的同时充分利用了矩阵的稀疏性,因此具有更好的聚类效果.此外,k⁃means的聚类结果比其他算法差得多,表明挖掘数据潜在的低维表示可以提高聚类任务的性能.

同时,为了验证CRNMF各部分的有效性,分别将βη设为0.当β=0时,CRNMF仅包含相关熵项和流形正则项,此时在CMU PIE数据集上ACC=75.56%,可以证明稀疏约束的重要性.当η=0时,CRNMF仅包含相关熵项和稀疏约束项,此时在CMU PIE数据集上ACC=19.64%,因此,流形正则项在提高聚类性能方面发挥极大的作用.

CRNMF在COIL20数据集上的T⁃SNE可视化结果如图7图8所示,由图可见,CRNMF可以将相似的数据聚集到同一类中.

4.3 鲁棒性

为了验证CRNMF算法的鲁棒性,在CMU PIE数据集上进行实验.具体地,将噪声密度为0.01的椒盐噪声加入CMU PIE数据集.CMU PIE数据集加入椒盐噪声后的图像如图9所示.CMU PIE数据集加入椒盐噪声后聚类精度的变化如图10所示,其中,n%表示所有图像的噪声百分比,n=0,10,20,30,40,50,n越大,噪声水平越高.由图可见,随着噪声水平的增加,提出的CRNMF算法在大多数情况下具有最佳的聚类精度,表明相关熵对非高斯噪声和异常值不敏感,所以处理非高斯噪声和异常值是有效的.与实验中的其他算法相比,CRNMF算法在具有明显异常值的CMU PIE数据集上鲁棒性更强.

图7

图7   COIL20数据集T⁃SNE可视化

Fig.7   T⁃SNE visualization of COIL20 dataset


图8

图8   CRNMF在COIL20数据集上的T⁃SNE可视化

Fig.8   T⁃SNE visualization of CRNMF on COIL20 dataset


图9

图9   加入椒盐噪声的CMU PIE数据集

Fig.9   CMU PIE dataset with salt and pepper noise


图10

图10   CMU PIE数据集上椒盐噪声影响下的聚类精度变化

Fig.10   Variation of ACC under the influence of salt and pepper noise on CMU PIE dataset


4.4 参数选择

在COIL20,CMU PIE和UMIST数据集上研究参数pβη的选择对聚类性能的影响.参数pβη分别选自3,5,7,9,

110.01,0.1,1,10,10010,50,100,500,

1000.图11图13显示了参数pβη对聚类精度的影响.由图可见,对于参数pp=5时聚类精度最高,p太大或太小都会对CRNMF产生较大的影响,因此p=5是最好的选择.在范围0.01,0.1,1,10,100β比较稳定,当β=0.1时在三个数据集上性能最佳,但β不能太大或太小,否则会出现过拟合的问题.同时,当η=100时,CRNMF在三个数据集上的表现最好.

4.5 收敛性

为了验证CRNMF的收敛性,在COIL20数据集上进行实验.实验结果如图14所示,x轴表示迭代次数,y轴表示CRNMF的目标函数值𝒪̂1.由图可见,对于COIL20数据集,在乘法更新规则(28)和(30)下,𝒪̂1的值单调递减,并且,CRNMF算法收敛速度快,通常在200次迭代以内收敛,证明了半二次优化技术的有效性.

图11

图11   在COIL20,CMU PIE和UMIST数据集上CRNMF随参数p的聚类精度变化

Fig.11   ACC of CRNMF with the change of parameter p on COIL20,CMU PIE and UMIST datasets


图12

图12   在COIL20,CMU PIE和UMIST数据集上CRNMF随参数β的聚类精度变化

Fig.12   ACC of CRNMF with the change of parameter β on COIL20,CMU PIE and UMIST datasets


图13

图13   在COIL20,CMU PIE和UMIST数据集上CRNMF随参数η的聚类精度变化

Fig.13   ACC of CRNMF with the change of parameter η on COIL20,CMU PIE and UMIST datasets


图14

图14   CRNMF在COIL20数据集上的收敛曲线

Fig.14   Convergence curves of CSNMF on COIL20 dataset


5 结论和展望

本文提出一种基于相关熵和流形正则化的图像聚类算法(CRNMF),将相关熵、稀疏约束和流形正则集成为一个统一框架.采用相关熵代替传统NMF中的欧氏距离,在充分学习数据的局部结构的同时对非负矩阵进行稀疏约束,有效抑制非高斯噪声和异常值的影响.最后,采用半二次优化技术(HQ)导出CRNMF的乘法更新规则,证明了算法的正确性和收敛性.在五个图像数据集上进行实验,并与经典的聚类算法进行比较,证明CRNMF的聚类精度(ACC)、归一化互信息(NMI)和纯度(PUR)都有所提高.

尽管CRNMF在聚类任务中取得了较好的效果,但仅限于处理非高斯噪声.为了处理更加复杂的噪声,未来的工作将进一步提高CRNMF的有效性和鲁棒性.首先,拓展所提出的算法,增加双图调节或超图约束;其次,充分利用数据中的监督信息,研究算法在半监督学习中的性能;最后,将所提出的算法应用到多视图聚类任务中.

参考文献

Hartigan J AWong M A.

Algorithm AS 136:A k⁃means clustering algorithm

Applied Statistics,197928(1):100-108.

[本文引用: 1]

Von Luxburg U.

A tutorial on spectral clustering

Statistics and Computing,200717(4):395-416.

[本文引用: 1]

Lee D DSeung H S.

Algorithms for non⁃negative matrix factorization

Proceedings of the 13th International Conference on Neural Information Processing Systems. Cambridge,MA,USAMIT Press2000(13):535-541.

[本文引用: 2]

Jain A K.

Data clustering:50 years beyond k⁃means

Pattern Recognition Letters,201031(8):651-666.

[本文引用: 1]

Kriegel H PKröger PZimek A.

Clustering high⁃dimensional data:A survey on subspace clustering,pattern⁃based clustering,and correlation clustering

ACM Transactions on Knowledge Discovery from Data,20093(1):1.

Chakraborty SPaul DDas Set al.

Entropy regularized power k⁃means clustering

2020arXiv,2001.03452.

[本文引用: 1]

Wang Y XZhang Y J.

Nonnegative matrix factorization:A comprehensive review

IEEE Transactions on Knowledge and Data Engineering,201325(6):1336-1353.

[本文引用: 1]

Tolić DAntulov⁃Fantulin NKopriva I.

A nonlinear orthogonal non⁃negative matrix factorization approach to subspace clustering

Pattern Recognition,2018(82):40-55.

[本文引用: 1]

Liu G CLin Z CYan S Cet al.

Robust recovery of subspace structures by low⁃rank representation

IEEE Transactions on Pattern Analysis and Machine Intelligence,201335(1):171-184.

[本文引用: 1]

Jolliffe I T.

Principal component analysis

Journal of Marketing Research,200287(4):513.

[本文引用: 1]

Höcker AKartvelishvili V.

SVD approach to data unfolding

Nuclear Instruments and Methods in Physics Research Section A:Accelerators,Spectrometers,Detectors and Associated Equipment,1996372(3):469-481.

[本文引用: 1]

Lee D DSeung H S.

Learning the parts of objects by non⁃negative matrix factorization

Nature,1999401(6755):788-791.

[本文引用: 2]

Li S ZHou X WZhang H Jet al.

Learning spatially localized,parts⁃based representation

Proceedings of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Kauai,HI,USAIEEE20015.

[本文引用: 1]

Ullman S.

High⁃level vision:Object⁃recognition and visual cognition

Optical Engineering,199736(11):231-256.

[本文引用: 1]

Logothetis N KSheinberg D L.

Visual object recognition

Annual Review of Neuroscience,199619):577-621.

[本文引用: 1]

Liu X WWang LZhang Jet al.

Global and local structure preservation for feature selection

IEEE Transactions on Neural Networks and Learning Systems,201725(6):1083-1095.

[本文引用: 1]

Chen JMa Z MLiu Y.

Local coordinates alignment with global preservation for dimensionality reduction

IEEE Transactions on Neural Networks and Learning Systems,201324(1):106-117.

Luong KNayak R.

Learning inter⁃ and intra⁃manifolds for matrix factorization⁃based multi⁃aspect data clustering

IEEE Transactions on Knowledge and Data Engineering,2020DOI:10.1109/TKDE. 2020.3022072 .

[本文引用: 1]

Cai DHe X FHan J Wet al.

Graph regularized nonnegative matrix factorization for data representation

IEEE Transactions on Pattern Analysis and Machine Intelligence,201133(8):1548-1560.

[本文引用: 3]

He PXu X HDing Jet al.

Low⁃rank nonnegative matrix factorization on stiefel manifold

Information Sciences,2020(514):131-148.

[本文引用: 1]

Guan N YTao D CLuo Z Get al.

Manifold regularized discriminative nonnegative matrix factorization with fast gradient descent

IEEE Transactions on Image Processing,201120(7):2030-2048.

[本文引用: 1]

Shang F HJiao L CWang F.

Graph dual regularization non⁃negative matrix factorization for co⁃clustering

Pattern Recognition,201245(6):2237-2250.

[本文引用: 1]

Zeng KYu JLi C Het al.

Image clustering by hyper⁃graph regularized non⁃negative matrix factorization

Neurocomputing,2014(138):209-217.

[本文引用: 1]

Li H RZhang J SShi Get al.

Graph⁃based discriminative nonnegative matrix factorization with label information

Neurocomputing,2017(266):91-100.

[本文引用: 2]

Wang Y YWu S YMao Bet al.

Correntropy induced metric based graph regularized non⁃negative matrix factorization

Neurocomputing,2016(204):172-182.

[本文引用: 2]

Du LXuan LShen Y D.

Robust nonnegative matrix factorization via half⁃quadratic minimization

2012 IEEE 12th International Conference on Data Mining. Brussels,BelgiumIEEE2013201-210.

[本文引用: 1]

Li LYang J JZhao K Let al.

Graph regularized

[本文引用: 1]

non⁃negative matrix factorization by maximizing correntropy. Journal of Computers,20149(11):2570-2579.

[本文引用: 1]

Zhou NXu Y YCheng Het al.

Maximum correntropy criterion⁃based sparse subspace learning for unsupervised feature selection

IEEE Transactions on Circuits and Systems for Video Technology,201929(2):404-417.

[本文引用: 2]

谢林江尹东.

基于最大相关熵准则的鲁棒度量学习算法

计算机系统应用,201827(10):146-153.

[本文引用: 1]

Xie L J, Yin D.

Robust metric learning based on maximum correntropy criterion

Computer Systems and Applications,201827(10):146-153.

[本文引用: 1]

Yu NWu M JLiu J Xet al.

Correntropy⁃based hypergraph regularized NMF for clustering and feature selection on multi⁃cancer integrated data

IEEE Transactions on Cybernetics,202051(8):3952-3963.

[本文引用: 2]

Peng S YSer WLin Z Pet al.

Robust sparse nonnegative matrix factorization based on maximum correntropy criterion

2018 IEEE International Symposium on Circuits and Systems. Florence,ItalyIEEE20181-5.

[本文引用: 3]

Zhang L FZhang QDu Bet al.

Robust manifold matrix factorization for joint clustering and feature extraction

31st AAAI Conference on Artificial Intelligence. San Francisco,CA,USAMachine Learning Applications20171662-1668.

[本文引用: 1]

Chen G FXu CWang J Yet al.

Robust non⁃negative matrix factorization for link prediction in complex networks using manifold regularization and sparse learning

Physica A:Statistical Mechanics and its Applications,2020539122882DOI:10.1016/j.physa.2019.122882 .

[本文引用: 2]

Belkin MNiyogi PSindhwani V.

Manifold regularization:A geometric framework for learning from Labeled and Unlabeled examples

The Journal of Machine Learning Research,20067(1):2399-2434.

[本文引用: 1]

Peng S YChen B DSun Let al.

Constrained maximum correntropy adaptive filtering

Signal Processing,2017140116-126.

[本文引用: 1]

Peng S YSer WChen B Det al.

Robust semi⁃supervised nonnegative matrix factorization for image clustering

Pattern Recognition,2021111):107683DOI:10.1016/j.patcog.2020.107683 .

[本文引用: 2]

He RHu B GYuan X Tet al. Robust recognition via information theoretic learning. New YorkSpringer2014.

[本文引用: 1]

Lovász LPlummer M D. Matching theory. Amsterdam,The NetherlandsNorth⁃Holland1986544.

[本文引用: 1]

/