正则化低秩子空间谱聚类算法

何家玉+许峰

摘 要：为解决缺损数据谱聚类中的不适定问题，提出一种正则化低秩子空间谱聚类算法。首先根据数据集建立核范数正则化低秩矩阵分解模型，然后用迭代法求解模型得出系数矩阵，由此构造相似矩阵，最后利用谱聚类算法得出聚类结果。实验表明，该算法在一定程度上可以解决缺损数据的谱聚类问题，抑制噪声，获得质量较高的聚类结果。

关键词：聚类分析；谱聚类；低秩子空间；不适定；正则化

DOIDOI：10.11907/rjdk.162025

中图分类号：TP311

文献标识码：A文章编号：1672-7800（2016）012-0022-03

0 引言

聚类分析是数据挖掘的一个重要研究领域，在统计学、生物学、模式识别、机器学习和社会科学中有着极为广泛的应用。所谓聚类就是将数据对象分组成为多个类或簇，使得在同一簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。k-均值聚类是聚类分析中最经典的算法，算法简单，可用于多种类型数据的聚类。但当数据集为非凸时，k-均值聚类往往陷于局部最优，聚类效果欠佳。另外，对于大小或密度不均匀的簇，k-均值聚类通常无法处理[1]。

谱聚类是一种新型的聚类分析方法，可以克服k-均值聚类等经典方法的一些缺陷[2]。谱聚类方法以图论中的谱图理论为基础，将聚类问题转化为图的最优划分问题。在众多图的最优划分准则中，归一化割集准则的划分效果相对较好，是谱聚类中常用的划分准则[3]。对于给定的划分准则和聚类数目k，谱聚类通常采用多路谱聚类算法将数据集划分为k个簇[4]。

最早的谱聚类算法是Ng，Bach和Jordan[4-5]提出的多路谱聚类方法。代表性的谱聚类算法还有Meila[6]提出的多路归一化割谱聚类方法；Vidal[7]提出的子空间谱聚类方法；Wang等[8]提出的多流形谱聚类方法；Cheng等[9]提出的低秩谱聚类方法；Elhamifar等[10]提出的稀疏子空间谱聚类方法。

在众多谱聚类算法中，低秩稀疏子空间谱聚类越来越受到学者的重视。在有些实际问题中，数据并不符合混合子空间的假设，分析这种数据具有很大的挑战性。研究表明，基于谱聚类的方法是处理该类问题的有效方法。虽然这类数据本身无法使用相互表示的方式，但是数据的特征可相互线性表示，且表示系数具有稀疏性或低秩性的特点。目前，这种低秩表示方法已被扩展用于图像处理。

本文在低秩子空间谱聚类算法的基础上，引入正则化过程以解决不适定问题，并根据数值实验对该算法进行性能测试。

1 谱聚类矩阵

谱聚类的基本思想是将聚类问题转化为图的最优划分问题，利用图的最优划分准则，使划分出的子图之间的边权之和较小，而子图内的边权之和较大。下面简要介绍本文算法设计过程中涉及到的谱聚类矩阵。

上述谱聚类矩阵性质类似但又有差异，不同的谱聚类算法可以选用不同的谱聚类矩阵。

2 正则化低秩子空间谱聚类算法

2.1 不适定问题与正则化

问题的适定性最早由法国数学家Hadamard[11]指出问题的解存在且唯一。不适定性通常包含两重含义：问题解的多重性和问题对扰动的敏感性。在很长一段时间内，人们认为研究不适定问题没有意义。直到1956年，人们逐渐发现适定问题并不能正确描述许多自然现象，许多现象均具有不适定性。至此，不适定问题的研究才引起相关学者的重视。

目前，对于不适定问题，已有PST、GPST、Monte Carlo、最佳摄动量、正则化等方法。其中，正则化是求解不适定问题的主要方法。不适定问题的正则化最早由前苏联数学家吉洪诺夫提出，其基本思想是：将所研究问题的解和相应空间加以适当限制，以保证当原始数据有缺损或扰动时，问题的近似解与真解具有较高的近似度。由于这种方法是通过对原问题附加“规则”，从而保证解的存在性和数值稳定性，因而称之为“正则化”方法。

2.2 低秩矩阵分解

大部分图像中都含有一些公共模式，这些基本模式称为基底或字典。通过这些基底的线性组合，可以表示出几乎所有的图像。在许多情况下，基底的数量是较少的，即许多图像的数据矩阵是低秩或近似低秩的。因为低秩矩阵可以被映射到低维空间进行分析，这就给图像处理带来了极大便利。

但在有些情况下，由于数据缺损及噪声影响，破坏了矩阵的低秩性。因为噪声往往是分布稀疏的，为了恢复矩阵的低秩性，可将略低数据矩阵D分解为两个矩阵A与E之和，其中第一个矩阵A低秩，第二个矩阵E稀疏。具体分解模型如下[13]：

3 数值实验

为了检验正则化低秩子空间谱聚类算法的性能，本文选取了两组典型的谱聚类仿真数据和两个人在不同光照下的共20幅人脸图像进行实验。

图1是视觉重建中的问题。特征提取是视觉重建的一个关键环节，图1中的十字的位置信息已经提取出来，为了确定十字的中心位置，要求将十字中的点按照 “横”和“竖”分为两类。

图2为一个平面和两条直线，这是一个不满足独立子空间的关系的例子，数据聚类有一定难度。从图2中还可以看出，原始数据有缺损，这在一定程度上要求聚类算法要有较强的缺损数据处理能力。

两个人在不同光照下的人脸图像共20幅，数据中每一列为一幅人脸图像，要求将这20幅图像分成两类。这是典型的图像低秩分解问题。谱聚类结果如下：

图3显示，十字线的聚类效果很好；图4显示，一平面二直线的聚类效果也较好，基本上将平面与两直线区分开来；图5显示，人脸图像被明显的分为两类，但第一行第三个图像和第五行第五个图像的识别结果出现了错误，这表明正则化低秩子空间谱聚类算法可能还存在某种不足，需要进一步改进。

4 结语

低秩子空间谱聚类算法适宜于缺损数据的聚类问题，但此算法可能出现不适定性。为此，本文提出用正则化方法解决不适定性。数值实验表明，这种算法在一定程度上可以解决缺损数据的谱聚类问题，抑制噪声，获得质量较高的聚类结果。

需指出的是，目前谱聚类的理论尚不成熟，许多算法性能的评价只能依赖于数据仿真。本文提出的算法虽可以解决低秩子空间谱聚类算法的不适定问题，但与经典的谱聚类算法相比，具有较高的复杂度，且对于复杂的图像分类问题效果有时欠佳，需要进一步深入研究。

参考文献：

[1] JAIN A，MURTY M，FLYNN P.Data clustering：a review[J].ACM Computing Surveys，1999，31（3）：264-323.

[2] LUXBRUG U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）：395-416.

[3] VERMA D，MEILA M.A comparison of spectral clustering algorithm[R].Washington：University of Washington，2003.

[4] NG A，JORDAN M，WEISS Y.On spectral clustering：analysis and an algorithm[C].Advances in Neural Information Processing Systems，Cambridge：MIT Press，2001：849-856.

[5] BACH F，JORDAN M.Learning spectral clustering[C].Advances in Neural Information Processing Systems，Cambridge：MIT Press，2004：1-13.

[6] MEILA M，XU L.Multiway cuts and spectral clustering[R].Washington：University of Washington，2003.

[7] VIDAL R.Subspace clustering[J].IEEE Signal Processing Magazine，2011，28（2）：52-68.

[8] WANF Y，JIANG Y，WU Y，et al.Spectral clustering on multiple manifolds[J].IEEE Transactions on Neural Networks，2011，22（7）：1149-1161.

[9] CHENG B，LIU G，WANG J，et al.Multi-task low rank affinity pursuit for image segmentation[J].ICCV，2011（10）：57-61.

[10] ELHAMIFAR E，VIDAL R.Sparse subspace clustering：algorithm，theory and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2765-2781.

[11] 刘继军.不适定问题的正则化方法及应用[M].北京：科学出版社，2005.

[12] 李宏伟.求解不适定问题的正则化方法[D].哈尔滨：哈尔滨理工大学，2011.

[13] 赵科科.低秩矩阵分解的正则化方法与应用[D].杭州：浙江大学，2012.

[14] 何家玉，许峰.基于特征向量自动选取的谱聚类算法[J].软件导刊，2016，15（8）：23-25.

（责任编辑：陈福时）