基于改进SMMC模型的多流形结构数据分析

邱益维+钟海伟

摘 要：提出一种改进的多流形谱聚类（SMMC）模型，提高复杂流形结构中的聚类精度。改进模型的核心在于首先对原始数据进行空间映射，得到能体现原始数据流形结构的数据；其次，根据流形距离的定义，利用局部点邻域构造各点的切平面，将切平面参数作为新流形的数据样本；最后用SMMC模型求解，得到聚类结果。实验结果表明，改进的SMMC模型对独立子空间、非线性良分离以及非线性交叉流形这三类数据的子空间聚类效果良好，且具有强鲁棒性和通用性。

关键词：SMMC模型；流形学习；子空间聚类；多流形建模

DOIDOI：10.11907/rjdk.171193

中图分类号：TP303

文献标识码：A 文章编号：1672-7800（2017）007-0029-04

0 引言

随着大数据时代的到来，数据量呈爆发式增长。如何对数据进行有效分析和处理已成为成功解决诸多问题的关键，由此涌现出大量的数据分析方法。在实际问题分析中可发现，大部分数据集实质上是由许多集合结构组合而成的。几何结构分析现已被广泛应用于对象识别、图像分类等模式识别和分类问题，同时也是对高维数据进行相关性分析、聚类分析等的有效方法。其中流形学习是几何结构分析方法中的重要组成部分[1-2]。流形学习的目的在于把高维数据在低维流形中表示出来，从而便于数据分析与存储，近年来流形学习的研究特别是多流形的研究逐渐增多[3]。

子空间聚类、混合线性模型、流形聚类等是目前主流的多流形模型方法。尽管目前对流形学习的研究较多，但仍面临巨大的挑战[4-5]。基于谱聚类的多流形聚类方法是众多流形聚类方法中的一类，它克服了传统稀疏子空间聚类（Sparse Subspace Clustering，SSC）算法不能很好地解决非线性子空间聚类的缺陷，能将线性或非线性、良分离或交叠的流形等多流形问题进行聚类，具有强大功能[1]。

本文在深入分析多流形谱聚类（Spectral Multi-manifold Clustering，SMMC）模型的基础上提出一种改进方法，对独立线性子空间、良分离曲线以及交叠曲线流形聚类中的3种典型数据进行聚类，并与其它流形聚类方法进行比较，实验结果表明，改进模型具有更好的聚类效果。

1 理论基础

1.1 多流形谱聚类模型

SMMC模型的基本思想是從相似性矩阵的角度出发，充分利用流形采样点所包含的自然的局部几何结构信息，辅助构造更适合的相似性矩阵，进而发现正确的流形聚类[5-6]。

根据数据点内包含的局部几何结构信息辅助构造相似性矩阵W[5]。当两个数据点满足条件相互靠近同时具有相似的局部切空间时，才能断定它们是来自同一个流形聚类。因此结合数据点之间的欧氏距离关系qij=q（xi-xj）和局部切空间之间的相似性pij来决定最后的相似性权值：

其中，f表示融合函数。结合理论与实际可知，两点划分为同类的概率与结构相似性成正比，与两者之间的欧式距离成反比。为使相似矩阵具有预期性质，融合函数f关于pij单调递增，关于qij单调递减。

假设数据点xi和xj（i，j=1，…N）处的局部切空间为Θi和Θj，则两数据点的局部切空间之间结构相似性可定义为：

1.2 流形距离

对于流形分类问题，其距离测度需要满足条件：在相同流形上的点的距离大于在不同流形上点的距离，而欧式距离不能体现该性质。为了满足聚类全局一致性的目的，使同一流形结构中的数据点的相似度高，而不同流形结构中的数据点的相似度低，使用一种能够体现全局一致性的测度—流形距离核测度。

所有样本点看作是图G=（V，E）的顶点，其中p∈Vl表示图上一个长度为l=p-1的连接点p1与pp的路径，边（pk，pk+1）E，1≤k

此流形距离测度可以度量流形上的最短路径，反映样本集内的流行结构。具体表现为用较短边连接同一流形上的两个样本点，较长边连接位于不同流形上的两个样本点，最终达到缩短同一流形上样本点间距离，放大不同流形上样本点间距离的目的。

2 SMMC模型改进

在利用坐标表示图像信息时，不同样本为流形上一点的空间坐标位置，此时样本不能很好地体现流形结构。对于SSC模型或SMMC模型，都先将图像信息从一种表示方式映射到另一种表示方式：SSC模型利用稀疏性要求，得到图像的稀疏表示；SMMC模型针对流形曲面，对局部进行线性重构，利用重构的空间基向量表示原始图像。

一定程度上讲，映射方式的选择决定了聚类的效果，对于SSC模型，因为采用的是自身向量再表示，该算法在向量自身相关性较大的场合有效，特别是在高维，小样本的情况下进行聚类。而SMMC算法是流形结果，对曲面采样稠密，稠密的条件保证了局部切空间的准确性，在抽样不够稠密和流形边界位置时，局部切空间的法线方向稳定性较差。本文针对SMMC在流形的局部表示上进行改进。

不同于SMMC模型中对局部点构成的矩阵进行奇异值分解，改进模型采用了奇异值向量来重构局部切平面，这样构成的切空间性质连续性不够明显，对于连续的曲面，设{h1，h2，……hk}∈δ（x，ε，k）为数据点x的流形邻域类中最近的k个数据点，令H=[h1，h2……hk]T，求解如下最小化问题：

参数β即为求解得到的数据点x重新表示。对于连续变化的流形结构，其切线构成新的流形。特别地，如果原始图像中的直线在局部法线的表示下为一个稠密点，若没有误差项，则新的表示下，直线变成点；对于曲线来说，在新的表示下为一连续的曲线。分离稠密点即可得到原始空间的直线。在高维空间中，切平面参数化以后，原始图像则表示成新的流形，平面表示为稠密点，曲面构成新的流形，然后利用重新参数化的数据根据SMMC模型算法求解。

根据以上论述，改进后的SMMC模型算法步骤可归纳为：

（1）计算各点之间的欧式距离。

（2）利用Floyd算法求解任意点的流形距离。

（3）重构局部切平面并估计参数β，组成的新数据样本，利用MPPCA训练M个d维的局部线性模型来近似潜在的流形数据。

（4）由式（10）确定每一个数据样本点的局部切空间。

（5）由式（2）计算两个局部切空间之间的结构相似性。

（6）由式（6）计算相似性矩阵W∈RN×N和对角矩阵D，其中dii=∑jwij。

（7）计算特征矩阵D-Wu=λDu最小的k个特征值对应的特征向量u1，u2，…uk。

（8）利用K-means算法将U=[u1，u2…uk]∈RN×k的行向量分组成k个聚类。

3 改进SMMC模型的子空间聚类验证

为了验证本文所提出的改进SMMC模型的有效性，将其应用于独立线性子空间的流形、良分离曲线的流形以及交叠曲线的流形这三類问题的子空间的聚类中，并与根据SSC模型、SMMC模型得到的聚类结果进行对比，仿真结果如下文所示。

由图1可知，对于独立线性子空间的流形，SSC模型不能很好地将两条直线分成两类，尤其是直线的交叉处无法得到好的聚类效果。SMMC模型对其聚类，直线的交叉处数据的聚类已经比SSC模型的结果好很多，但是没能完整地将两条直线聚成两类，说明模型还需改进。改进的SMMC模型可以很好地将同一直线上的点聚到同一类中，效果显著。

由图2可知，对于良分离曲线的流形，SSC模型的聚类效果很差，用SMMC模型和改进的SMMC模型均能很完美地将两条不相交的二次曲线聚成两类。因为这种类型的流形聚类正属于多流形聚类问题，用SSC模型难以解决多流形聚类问题，而SMMC模型正是针对这类问题的。

由图3可知，对于相交的两条螺旋线，用SSC模型分两类的结果没有规律性，每条螺旋线上的点都被聚到不同的两类当中去，效果不理想。采用SMMC模型聚类时，虽然没有将两条螺旋线完全分开，但是其中一条螺旋线的一半已经完全与另一条螺旋线区分开，说明相比SSC模型，用SMMC模型有更好地聚类效果。通过本文提出的改进SMMC模型聚类，发现可以将两条螺旋线可以进行区分且效果很好。

综上所述，SSC模型对独立线性子空间的两条平面直线具有较好的聚类效果，但不能很好解决非线性子空间聚类问题。对于非线性子空间，需建立二维坐标的多流形模型进行聚类。实验结果表明，SMMC模型应用到良分离曲线的流形聚类中，分类效果显著，但针对交叠曲线的流形聚类还存在一定的缺陷。本文提出的改进SMMC模型改善了SSC和SMMC模型在低维空间中的聚类效果，很好完成了实验中的三类图形数据的聚类，分类效果良好，且更具通用性。

4 结语

本文针对多流形聚类问题进行建模，在分析数据几何结构的理论基础上，提出了改进的SMMC模型。首先对原始数据进行一次空间映射，使映射后的数据能体现原始数据的流形结构。其次，根据流形距离的定义，利用局部点邻域构造各点的切平面，对于光滑的流形，各点的切平面法线方向缓慢变化，从而组成新的流形。最后利用重新构造流形得到的参数用SMMC模型算法求解。实验结果表明，相较于原始SMMC模型，结合切平面与法线方向的改进SMMC模型提高了低维子空间的聚类效果，且更具有一般性和通用性。

参考文献：

[1]易思，左小雷，黄小明，等.基于SMMC模型的数据多流形结构分析研究[J].数学的实践与认识，2016，46（14）：163-172.

[2]胡一帆，胡友彬，李绍辉，等.多流形结构数据建模与应用研究[J].现代计算机：普及版，2015，（12）：8-13.

[3]CHEN G，LERMAN G.Spectral curvature clustering（SCC）[J].International Journal of Computer Vision，2009，81（3）：317-330.

[4]刘向阳.多流形数据建模及其应用[D].上海：上海交通大学，2011.

[5]王勇.基于流形学习的分类与聚类方法及其应用研究[D].长沙：国防科技大学，2011.

[6]王梦莹，郑雄风，葛余超.混合流形结构的子空间聚类研究[J].数学的实践与认识，2016，46（14）：189-199.

[7]宋少宇.基于流形距离核的谱聚类算法研究及其应用[D].哈尔滨：哈尔滨工程大学，2012.