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

《正则化低秩子空间谱聚类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、正则化低秩子空间谱聚类算法　　摘要：为解决缺损数据谱聚类中的不适定问题，提出一种正则化低秩子空间谱聚类算法。首先根据数据集建立核范数正则化低秩矩阵分解模型，然后用迭代法求解模型得出系数矩阵，由此构造相似矩阵，最后利用谱聚类算法得出聚类结果。实验表明，该算法在一定程度上可以解决缺损数据的谱聚类问题，抑制噪声，获得质量较高的聚类结果。　　关键词：聚类分析；谱聚类；低秩子空间；不适定；正则化　　DOIDOI：10.11907/rjdk.162025　　中图分类号：TP311　　文献标识码：A文章编号：1672-7800（2016）012-

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

3、方法以图论中的谱图理论为基础，将聚类问题转化为图的最优划分问题。在众多图的最优划分准则中，归一化割集准则的划分效果相对较好，是谱聚类中常用的划分准则[3]。对于给定的划分准则和聚类数目k，谱聚类通常采用多路谱聚类算法将数据集划分为k个簇[4]。　　最早的谱聚类算法是Ng，Bach和Jordan[4-5]提出的多路谱聚类方法。代表性的谱聚类算法还有Meila[6]提出的多路归一化割谱聚类方法；Vidal[7]提出的子空间谱聚类方法；Wang等[8]提出的多流形谱聚类方法；Cheng等[9]提出的低秩谱聚类方法；Elhamifar等[1

4、0]提出的稀疏子空间谱聚类方法。　　在众多谱聚类算法中，低秩稀疏子空间谱聚类越来越受到学者的重视。在有些实际问题中，数据并不符合混合子空间的假设，分析这种数据具有很大的挑战性。研究表明，基于谱聚类的方法是处理该类问题的有效方法。虽然这类数据本身无法使用相互表示的方式，但是数据的特征可相互线性表示，且表示系数具有稀疏性或低秩性的特点。目前，这种低秩表示方法已被扩展用于图像处理。　　本文在低秩子空间谱聚类算法的基础上，引入正则化过程以解决不适定问题，并根据数值实验对该算法进行性能测试。　　1谱聚类矩阵　　谱聚类的基本思想是将聚类问题转化

5、为图的最优划分问题，利用图的最优划分准则，使划分出的子图之间的边权之和较小，而子图内的边权之和较大。下面简要介绍本文算法设计过程中涉及到的谱聚类矩阵。6　　上述谱聚类矩阵性质类似但又有差异，不同的谱聚类算法可以选用不同的谱聚类矩阵。　　2正则化低秩子空间谱聚类算法　　2.1不适定问题与正则化　　问题的适定性最早由法国数学家Hadamard[11]指出问题的解存在且唯一。不适定性通常包含两重含义：问题解的多重性和问题对扰动的敏感性。在很长一段时间内，人们认为研究不适定问题没有意义。直到1956年，人们逐渐发现适定问题并不能正确描述许多

6、自然现象，许多现象均具有不适定性。至此，不适定问题的研究才引起相关学者的重视。　　目前，对于不适定问题，已有PST、GPST、MonteCarlo、最佳摄动量、正则化等方法。其中，正则化是求解不适定问题的主要方法。不适定问题的正则化最早由前苏联数学家吉洪诺夫提出，其基本思想是：将所研究问题的解和相应空间加以适当限制，以保证当原始数据有缺损或扰动时，问题的近似解与真解具有较高的近似度。由于这种方法是通过对原问题附加“规则”，从而保证解的存在性和数值稳定性，因而称之为“正则化”方法。　　2.2低秩矩阵分解　　大部分图像中都含有一些公共模

7、式，这些基本模式称为基底或字典。通过这些基底的线性组合，可以表示出几乎所有的图像。在许多情况下，基底的数量是较少的，即许多图像的数据矩阵是低秩或近似低秩的。因为低秩矩阵可以被映射到低维空间进行分析，这就给图像处理带来了极大便利。6　　但在有些情况下，由于数据缺损及噪声影响，破坏了矩阵的低秩性。因为噪声往往是分布稀疏的，为了恢复矩阵的低秩性，可将略低数据矩阵D分解为两个矩阵A与E之和，其中第一个矩阵A低秩，第二个矩阵E稀疏。具体分解模型如下[13]：　　3数值实验　　为了检验正则化低秩子空间谱聚类算法的性能，本文选取了两组典型的谱聚类

8、仿真数据和两个人在不同光照下的共20幅人脸图像进行实验。　　图1是视觉重建中的问题。特征提取是视觉重建的一个关键环节，图1中的十字的位置信息已经提取出来，为了确定十字的中心位置，要求将十字中的点按照“横”和“竖”分为两类。　　图2为一