核化图正则子空间分割方法

郑毅伟 许金波 王艺恬 简彩仁

摘 要：传统的线性子空间分割方法很难刻画数据的非线性结构。借鉴核理论提出核化图正则子空间分割方法，在非线性空间中对数据进行重构，有利于刻画数据的非线性特点。利用Sylvester方程可求得全局最优解。2个图像数据集和2个基因表达数据集的实验结果表明，核化图正则子空间分割方法优于其他线性子空间分割方法。

关键词：子空间分割;核理论;图正则;聚类;Sylvester方程;非线性结构

中图分类号：TP311;TP371 文献标识码：A 文章编号：2095-1302（2019）05-00-03

0 引 言

聚类在机器学习等领域有着广泛的应用[1]。谱聚类是一种传统的聚类方法，谱聚类利用数据点之间的相似性构造出关联矩阵，再用关联矩阵构造出无向图，最后用谱方法进行分割。谱聚类方法的主要问题是求解相似矩阵。随着表示理论的兴起[2-4]，许多基于表示理论的重构方法为谱图矩阵的建立提供了新的途径。基于表示理论的子空间分割方法利用表示理论得到重构系数，再利用重构系数构造谱图矩阵，最后用谱聚类的方法实现聚类。

子空间分割的目的是将数据集分割成几个不同的类簇，每个类簇都对应一个子空间，从而对样本数据集进行分割聚类。近年来，基于表示理论的数据重构方法的发展带动了子空间分割方法的创新，许多基于表示理论的子空间分割方法被提出，使得该研究方向成为聚类问题研究的热点之一。例如，稀疏表示子空间分割方法（SSC）[5]利用L1范数的稀疏性得到具有稀疏性能的重构系数;低秩表示子空间分割方法（LRR）[6]基于低秩表示的思想旨在寻找低秩矩阵刻画重构系数;最小二乘回归子空间分割方法（LSR）[7]利用传统的岭回归模型通过正则L2范数得到具有聚集功能的重构系数。不仅如此，许多基于这些方法的拓展模型被提出[8-9]。但是这些子空间分割方法都是在高维样本空间中基于欧氏距离度量的识别方法，不适合刻画非线性数据的本质。针对这一不足，结合图正则子空间分割方法，利用核理论[10-11]，提出核化图正则子空间分割方法，在高维核空间中研究非线性数据的聚类问题。

1 相关工作

本节叙述了对核化图正则子空间分割方法提出的理论依据。

1.1 图正则化项

图正则化项借鉴流形学习的思想，保持原有数据集的流形结构，在模式识别的研究中应用广泛[8，12]。假设原样本空间的两个样本xi和xj映射为新样本空间的两个样本zi和zj，定义图正则化项：

式中：D是对角矩阵且;图拉普拉斯矩阵L=D-G，G是边权矩阵。

式中Nk（xi）是xi的k近邻所组成的集合。

1.2 子空间分割方法

基于表示理论的子空间分割方法的关键在于重构矩阵Z的求解。低秩表示子空间分割方法[6]主要保持重构矩阵的低秩性质，其数学模型为：

最小二乘回归子空间分割方法[7]主要保持重构系数的聚集性，其数学模型为：

利用图正则化项提出的图正则化子空间分割方法[8]如下：

2 核化图正则子空间分割方法

针对传统子空间分割方法在线性空间中对原样本数据集进行重构不能很好刻画数据集的非线性特点的不足，提出核化图正则子空间分割方法。定义非线性特征空间映射Φ：Rm→M，其中Rm表示原样本空间，M表示低维流形空间。由该非线性映射Φ得到X的低维流形表示Φ（X），利于刻画数据集的非线性特点。对低维流形表示Φ（X）进行子空间分割研究给出核化图正则子空间分割方法的目标函数：

3 实验分析

为验证核化图正则化子空间分割方法（KGRSS）的有效性，将使用KGRSS和不同的子空间分割方法，即图正则化子空间分割方法（GRSS）[8]，最小二乘回归子空间分割方法（LSR）[7]，低秩表示子空间分割法（LRR）[6]，以及两种传统聚类算法，即K均值聚类法（K-means）和层次聚类法（HC）进行聚类准确率的比较，聚类准确率的计算公式参考文献[12]。

3.1 实验数据

本研究实验选用4个应用于模式识别的数据集作为研究，分别为图像数据集ORL，pixraw10P和基因表达数据集TOX_171，nci9，它们的简要信息见表1所列。

3.2 实验结果分析

为避免聚类的随机性，实验过程中将每种方法运行50次，聚类准确率的均值见表2所列。

观察聚类准确率，对比实验结果可知，相比GRSS方法，KGRSS方法可以取得更加理想的聚类准确率，这一结果表明，基于核理论的核化图正則子空间分割方法在数据的聚类研究中更加实用。对比经典的线性子空间分割方法LSR和LRR，KGRSS方法也可以得到更优的聚类准确率。因此，KGRSS可以更好地反映出数据的非线性特点，取得更好的聚类准确率。KGRSS方法得到的聚类准确率相较于传统的聚类方法K-means和HC得到的聚类准确率有明显提升，原因是传统聚类方法以欧式距离为度量，不适合具有非线性特点的数据识别研究。由上述实验结果可知，KGRSS方法相较于其他各类方法大部分都能更好地适应数据的聚类，因此可以表明KGRSS是一种适合数据聚类的方法。

3.3 参数分析

图1显示了正则参数λ和近邻参数K的变化对聚类准确率的影响。当近邻参数K不变时，较大的正则参数λ能够得到较高的聚类准确率;当正则参数λ不变时，近邻参数K在不同的数据中出现了不同的变化情况，2～7范围中的近邻参数K可以取得较高的聚类准确率。通过对图1实验结果的观察，范围2～7的近邻参数K以及较大的正则参数λ是一组较为理想的参数选择，表明了KGRSS方法较强的实用性与相对较好的应用价值。

4 结 语

利用核方法改进图正则子空间分割方法，提出了核化图正则子空间分割方法（KGRSS），并成功实现了数据的聚类。KGRSS方法用高斯核函数对数据样本进行处理，引入光滑函数保持样本的几何结构，并且对Sylvester方程进行求解得到全局最优解。实验结果表明，KGRSS方法可以很好地适应数据的非线性特点，并且聚类效果比其他子空间分割方法和传统聚类方法更好。因此，运用KGRSS方法能够更好地实现数据聚类。