1. 引言
聚类是特征学习和计算机视觉中的一项重要但具有挑战性的任务。对于图像聚类任务,最重要的是找到原始数据的有效表示。为了挖掘出原始数据中内在的结构信息,许多研究人员已经做了大量的工作。最流行的特征提取方法包括主成分分析 [1] (PCA)、奇异值分解 [2] (SVD)、概念分解 [3] (CF)非负矩阵分解 [4] (NMF)等。1999年,Lee和Seung [4] 在《自然》杂志上首次提出了非负矩阵分解的概念。NMF的目标是得到两个非负矩阵,基矩阵和编码矩阵,其乘积尽可能接近原始矩阵。由于NMF的良好性能,在Lee和Seung的工作之后,许多标准NMF的变体被提出,用于从不同的观点改进NMF。
为了提高NMF的稀疏性,Li等人提出了一种加入局部约束的局部NMF [5] (LNMF)。在此之后,Chen等人在NMF中引入了局部坐标约束 [6]。Cai等人提出了一个图正则化 [7] NMF (GNMF),试图涉及数据空间的几何信息。GNMF通过构造一个k最近邻(kNN)图来对几何结构进行编码。因为一个简单图中的一条边只能连接两个顶点,GNMF只考虑了两个样本之间的成对关系,而忽略了样本间的高维结构。为了探索样本之间的高阶关系,Zeng等人通过构建一个编码更多样本之间关系的超图,开发了一个超图正则化 [8],因为超图可以连接两个以上的顶点,HNMF可以找出数据的高阶关系。
上述方法在某种程度上确实改进了标准的NMF。然而,由于原始数据中所包含的潜在噪声会影响聚类和分类的性能。当数据包含噪声或离群值时,特征和样本的误差都是平方的,因此有一些噪声特征或一些离群值的误差较大将支配目标函数。Kong等人提出了鲁棒非负矩阵分解算法 [9],克服了标准NMF算法对噪声和异常值敏感的缺点。
为了减轻噪声或异常值的影响,处理高维、包含噪声和异常值的数据。整合L2,1范数和超图正则化的优点,给出了一种基于L2,1范数的超图正则化非负矩阵分解。在COIL20和ORL数据集上的实验结果表明,L2,1HNMFL方法在聚类精度和归一化互信息上优于四种具有代表性的方法k-means、NMF、L2,1NMF和GNMF。在第二节中,简要回顾了标准NMF及其一些具有代表性的变体。在第三节中,详细描述了L2,1HNMFL方法并给出了有效的迭代更新规则。第四节展示了在数据集上的实验结果。最后,在第五节中简要地总结了这篇论文。
2. 预备知识
给定的非负数据矩阵
,
表示一个数据点。标准NMF定义为:
上述问题通常通过迭代更新算法来解决,其中U和V的迭代更新方法如下:
,
.
为了提高NMF的鲁棒性,Kong等人提出L2,1NMF算法,能够降低数据集中噪声和异常值的影响。目标函数定义为:
其中L2,1范数定义为
迭代更新规则为
,
.
为了保持数据的局部几何结构,Cai等人提出了GNMF,目标函数为
其中
是图拉普拉斯矩阵。W是图的权重矩阵,D是对角矩阵,
。
因为一个简单图中的一条边只能连接两个顶点。为了考虑样本之间的高维结构,Zeng等人提出了超图正则化。下面将简单地介绍超图的一些基本定义 [10]:
给定一个超图
,其中A表示超图中所有顶点的集合,E表示所有超边的集合,任意一个超边
是顶点集A的一个子集。S是超图的权重矩阵,它是一个对角矩阵,元素
表示超边e权重
的大小。把一个顶点和一条超边的关系记为关联矩阵H,则关联矩阵H表示为
。
对于任意顶点
,顶点a的度定义为
,对于超边
,它的度定义为
。超图的权重矩阵为S,其元素
表示为
。超图拉普拉斯矩阵
,
。
3. 基于L2,1范数的超图正则化非负矩阵分解
在这一部分中,给出了基于L2,1范数的超图正则化非负矩阵分解算法(L2,1HNMFL),不仅可以克服数据中噪声和异常值的影响,还可以保持数据集的内在几何结构,得到更加准确的聚类效果。下面先介绍目标中正则化项。
3.1. 目标函数
首先介绍坐标编码的概念 [11]。
定义:坐标编码是一对
,
是一组锚点,
是
到
的映射。得到物
理近似式:
。
根据上式,基矩阵U的列可以看作是一组锚点,而数据集中的每个数据点都可以用锚点的线性组合来表示。编码矩阵V的列包含了数据点相对于锚点的坐标。为了获得稀疏编码,每个数据点都应该表示为只有几个附近锚点的线性组合,即每个数据点应该只足够接近几个锚点。这可以通过引入局部坐标约束来实现,局部坐标约束可以表述为以下问题:
将上式整合到鲁棒的NMF中,并且增加超图正则项,目标函数定义为:
(1)
s.t.
,
.
3.2. 更新规则
下面给出更新规则和推导过程,经过简单运算,(1)式可以改写为:
其中
和
是大于0的常数。目标函数的第二项和第三项分别是局部坐标约束项和超图正则化项。
,根据迹的知识,目标函数可以写为:
其中,
,
,
。
设
和
分别是
和
的拉普拉斯乘子。
和
是对应的拉普拉斯矩阵,则拉普拉斯扩展式L为:
令
和
,得到:
定义列向量
。设
是一个
矩阵,其行为
。定义列向量
。设
为一个
矩阵,其列为p。根据上式,关于L2,1HNMFL算法的迭代公式为:
, (2)
. (3)
4. 实验
4.1. 数据集的描述
ORL数据集:ORL人脸数据库共由总共400张人脸图像组成,为40个个体在不同光照条件、有/没有眼镜和不同面部表情的情况下的10张灰度人脸图像。所有图像的分辨率都被调整为32 × 32。
COIL20数据集:数据集由20个物体的1440张图像组成,灰度大小为32 × 32。每个物体有72张不同的图像,所有的图像都是黑色的背景。
4.2. 比较的方法
为了验证算法的有效性,与四种具有代表性的方法k-means、NMF、L21NMF和GNMF进行比较。
4.3. 实验设计
在实验中,使用了两个通常使用的测量方法来评估算法的效果,分别是聚类精度(AC)和归一化互信息(NMI) [12]。
聚类精度(AC)定义为:
其中
是数据集给出的标签,
是聚类算法提供的标签,
是将
映射到等价标签的排列映射函数,
是delta函数,如果
,其值为1,否则为0。
互信息(NMI)可以衡量两个集群集之间的相似性,在聚类应用中得到了广泛的应用。设C和
为两组集,然后将MI定义为
其中,
和
分别表示属于集群C和集群
的样本的概率。
表示一个样本同时属于C和
的联合概率。然后将NMI定义为:
其中
和
分别表示C和
的信息熵。
在实验中,在一定范围内改变了参数,以寻找所给出的方法的最佳性能,正则化参数
和
在{0.001、0.01、0.1、0、1、10、100、1000}中进行选择。所有方法对上述数据集的聚类结果如表1~4所示。对于每个给定的聚类数k,从数据集中随机选择的不同类重复10次测试运行,并聚类性能的方差和平均值。
![](Images/Table_Tmp.jpg)
Table 1. Clustering accuracy on COIL20
表1. COIL20上的聚类准确度(AC)
![](Images/Table_Tmp.jpg)
Table 2. Normalized Mutual Information on COIL20
表2. COIL20上的归一化互信息(NMI)
![](Images/Table_Tmp.jpg)
Table 3. Clustering accuracy on ORL
表3. ORL上的聚类准确度(AC)
![](Images/Table_Tmp.jpg)
Table 4. Normalized Mutual Information on ORL
表4. ORL上的归一化互信息(NMI)
4.4. 实验结果与分析
通过以上两个数据集上的实验结果进行分析,可以得出:
1) k-means的聚类性能不如其他方法。这表明,通过其他方法获得的高维样本的低维表示在数据聚类中是有用的,并可以提高聚类性能。2) 在大多数情况下,GNMF的性能优于NMF,这验证了几何结构在矩阵分解算法中的重要作用。3) 由于L2,1HNMFL算法是利用局部约束来保持几何结构,并利用L2,1范数来保持稀疏性,故L2,1HNMFL算法优于所有其他算法。4) 与其他方法相比,给出的L2,1HNMFL算法在测试的AC和NMI值上都获得最好的聚类性能。这表明,通过将超图的构造和局部约束合并到一个统一的框架中,L2,1HNMFL算法比其他方法具有更强的判别能力。
5. 结语
新方法给出了一个基于超图正则化和局部约束的聚类模型,可以有效地处理高维、稀疏和有噪声的数据。在COIL20数据集和ORL数据集上,聚类精度分别提高了6.90%和4.83%,归一化互信息分别提高了3.08%和2.30%。