正则化低秩子空间谱聚类算法
作者：何家玉 许峰
来源：《软件导刊》2016年第12期
        摘 要：为解决缺损数据谱聚类中的不适定问题，提出一种正则化低秩子空间谱聚类算法。首先根据数据集建立核范数正则化低秩矩阵分解模型，然后用迭代法求解模型得出系数矩阵，由此构造相似矩阵，最后利用谱聚类算法得出聚类结果。实验表明，该算法在一定程度上可以解决缺损数据的谱聚类问题，抑制噪声，获得质量较高的聚类结果。
        关键词：聚类分析；谱聚类；低秩子空间；不适定；正则化
        DOIDOI：10.11907/rjdk.162025
正则化一个5 5随机矩阵
        中图分类号：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 结语
        低秩子空间谱聚类算法适宜于缺损数据的聚类问题，但此算法可能出现不适定性。为此，本文提出用正则化方法解决不适定性。数值实验表明，这种算法在一定程度上可以解决缺损数据的谱聚类问题，抑制噪声，获得质量较高的聚类结果。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。