稀疏子空间聚类综述

稀疏子空间聚类(Sparse subspace clustering, SSC)是一种基于谱聚类的数据聚类框架. 高维数据通常分布于若干个低维子空间的并上, 因此高维数据在适当字典下的表示具有稀疏性. 稀疏子空间聚类利用高维数据的稀疏表示系数构造相似度矩阵, 然后利用谱聚类方法得到数据的子空间聚类结果. 其核心是设计能够揭示高维数据真实子空间结构的表示模型, 使得到的表示系数及由此构造的相似度矩阵有助于精确的子空间聚类. 稀疏子空间聚类在机器学习、计算机视觉、图像处理和模式识别等领域已经得到了广泛的研究和应用, 但仍有很大的发展空间. 本文对已有稀疏子空间聚类方法的模型、算法和应用等方面进行详细阐述, 并分析存在的不足, 指出进一步研究的方向.     

基于稀疏子空间聚类的多层网络社团检测

现有的子空间聚类方法大多只适用于单层网络,或者仅对多层网络中每层的聚类结果简单地进行平均,未考虑每层网络中包含信息量不同的特点,致使聚类性能受限。针对该问题,提出一种面向多层网络的稀疏子空间聚类方法。将距离正则项和非负约束条件集成到稀疏子空间聚类框架中,从而在聚类时能够同时利用数据的全局信息和局部信息进行图学习。此外,通过引入稀疏约束使学习到的图具有更清晰的聚类结构,并设计迭代算法进行优化求解。在多个真实数据集上的实验结果表明,该方法能够挖掘网络不同层的互补信息,得到准确的一致性联合稀疏表示,有效提高社团聚类性能。     

基于光谱空间结合的非负稀疏保持嵌入的谱聚类

为了解决高光谱遥感影像的特征融合问题,针对高光谱数据的维数高、信息量繁杂冗余、非线性而且数据量庞大特点,利用图谱理论非负稀疏保持嵌入的降维方法,提出基于光谱空间结合的非负稀疏保持嵌入的谱聚类进行样本的标记算法,有效地利用空间信息和原有光谱信息,提高分类的精度.该算法在引入非负稀疏表示的同时,利用样本的光谱与空间相关信息构建Laplacian图,嵌入投影到低维的子空间,然后再用经典的K均值聚类算法进行分类.算法能够有效保持样本的几何稀疏结构,而且光谱空间信息的结合使得图像的边界像素点得到了更好的分类.     

利用坐标下降实现并行稀疏子空间聚类

随着数据规模的不断扩大,稀疏子空间聚类问题面临计算上的巨大挑战。现有稀疏子空间聚类算法如交替方向乘子法(ADMM)往往基于串行实现,难以利用多核处理器提高处理大规模聚类问题的效率。针对这个问题,提出一种基于坐标下降的并行稀疏子空间聚类方法。该方法利用稀疏子空间聚类可以建模为求解一系列的样本自稀疏表达子问题的特点,使用坐标下降方法来求解每个子问题,具有参数少、收敛快的优点;同时结合自稀疏表达子问题独立的特点,在处理器的各个核心上同时求解不同样本对应的子问题,因此可以充分利用计算机资源,减少运行时间开销。在模拟数据和运动分割数据集Hopkins-155上与常用的ADMM算法进行对比实验,结果表明该算法在多核处理器上可以显著提升运行速度且聚类精度与ADMM相当。     

基于三支决策的多视图低秩稀疏子空间聚类算法

多视图子空间聚类是一种从子空间中学习所有视图共享的统一表示, 挖掘数据潜在聚类结构的方法. 作为一种处理高维数据的聚类方法, 子空间聚类是多视图聚类领域的研究热点之一. 多视图低秩稀疏子空间聚类是一种结合了低秩表示和稀疏约束的子空间聚类方法. 该算法在构造亲和矩阵过程中, 利用低秩稀疏约束同时捕捉了数据的全局结构和局部结构, 优化了子空间聚类的性能. 三支决策是一种基于粗糙集模型的决策思想, 常被应用于聚类算法来反映聚类过程中对象与类簇之间的不确定性关系. 本文基于三支决策的思想, 设计了一种投票制度作为决策依据, 将其与多视图稀疏子空间聚类组成一个统一框架, 从而形成一种新的算法. 在多个人工数据集和真实数据集上的实验表明, 该算法可提高多视图聚类的准确性.     

非负子空间聚类指导下的非负矩阵分解

非负矩阵分解作为一种有效的数据表示方法被广泛应用于模式识别和机器学习领域。为了得到原始数据紧致有效的低维数据表示,无监督非负矩阵分解方法在特征降维的过程中通常需要同时发掘数据内部隐含的几何结构信息。通过合理建模数据样本间的相似性关系而构建的相似度图,通常被用来捕获数据样本的空间分布结构信息。子空间聚类可以有效发掘数据内部的子空间结构信息,其获得的自表达系数矩阵可用于构建相似度图。该文提出了一种非负子空间聚类算法来发掘数据的子空间结构信息,同时利用该信息指导非负矩阵分解,从而得到原始数据有效的非负低维表示。同时,该文还提出了一种有效的迭代求解方法来求解非负子空间聚类问题。在两个图像数据集上的聚类实验结果表明,利用数据的子空间结构信息可以有效改善非负矩阵分解的性能。     

基于信息粒度的文本聚类算法

根据文本对象数据的高维性,稀疏性的特点,提出一种基于信息粒度原理的文本聚类方法.首先在给出文本的稀疏特征,文本的稀疏特征向量,文本的稀疏相似度,等价关系隶属度,广义的等价关系等定义的基础上,利用信息粒度原理生成初始聚类,然后提出并理论推导类间相似度的计算方法,进行类的归并.该算法聚类过程不依赖于输入样本的排列顺序,文本数据的有效压缩提高了算法的执行效率.     

基于聚类的林业病虫害实体抽取研究

在基于半监督和主动学习的信息抽取研究中,对初始样本集的选择,鲜有考虑样本在数据集中的分布情况。以林业领域的病虫害抽取为例,提出基于聚类的方法来获取样本在数据集中的分布信息,以此指导初始样本集和迭代过程中标注样本的选择。实验结果表明,基于聚类的方法相比于随机初始训练集,在不同标注样本集个数的情况下,模型f值均有提高。相比于单一的主动学习方法,在性能相近的情况下,节约了30%左右的人工标注量。     

融入无监督度量学习的稀疏子空间聚类模型

子空间聚类任务中的无标记数据具有维度高、数据分布分散等特点,传统方法对数据预处理未进行详细地针对化设计且大多使用欧氏距离度量数据间的相似性,使聚类性能提升受限.因此,本文提出融入无监督度量学习的稀疏子空间聚类模型,该算法将距离度量与子空间聚类联合到同一框架,设计由两步组成的聚类过程.该方法对原始数据进行度量学习并重构了稀疏子空间聚类模型,使数据预处理不再是一个单独的步骤,最大限度地将输入的无标记数据之间相似度提高,有效提升了子空间聚类性能、加强了模型泛化能力.我们在真实公开数据集上进行实验测试,实验结果表明该方法优于现有的子空间聚类算法,具有良好的聚类性能.     

基于样本空间分布密度的初始聚类中心优化K-均值算法*

针对传统K-均值聚类算法对初始聚类中心敏感、现有初始聚类中心优化算法缺乏客观性,提出一种基于样本空间分布密度的初始聚类中心优化K-均值算法。该算法利用数据集样本的空间分布信息定义数据对象的密度,并根据整个数据集的空间信息定义了数据对象的邻域;在此基础上选择位于数据集样本密集区且相距较远的数据对象作为初始聚类中心,实现K-均值聚类。UCI机器学习数据库数据集以及随机生成的带有噪声点的人工模拟数据集的实验测试证明,本算法不仅具有很好的聚类效果,而且运行时间短,对噪声数据有很强的抗干扰性能。基于样本空间分布密度的初始聚类中心优化K-均值算法优于传统K-均值聚类算法和已有的相关K-均值初始中心优化算法。     

基于分式函数约束的稀疏子空间聚类方法

针对现有稀疏子空间聚类算法获取的系数矩阵不能准确反应高维空间中数据分布的稀疏性的不足,提出一种分式函数约束的稀疏子空间聚类模型,并利用交替方向迭代方法给出该模型的解。在无噪声情形下,证明了该方法获取的系数矩阵具有块对角结构,这为其准确获取数据结构提供了理论保证;在含噪声情形下,对异常点噪声同样采用分式函数约束作为正则项,提高了模型的鲁棒性。在人工数据集、Extended Yale B库和Hopkins155数据集上的实验结果表明,基于分式函数约束的稀疏子空间聚类方法不仅提高了聚类结果的准确率,而且对异常点噪声具有更好的鲁棒性。     

k近邻约束的稀疏子空间聚类

稀疏子空间聚类是近年提出的高维数据聚类框架，针对实际数据并不完全满足线性子空间模型的假设，提出[k]近邻约束的稀疏子空间聚类算法。该算法结合数据的子空间结构，[k]近邻及距离信息，在稀疏子空间模型上，添加[k]近邻约束项。添加的约束项符合距离越小，相似系数越大的直观认识且不改变系数矩阵的稀疏性。在人脸数据集Extended YaleB、ORL、AR，物体图像数据集COIL20及手写数据集USPS上的聚类实验表明提出的算法具有良好的性能。     

基于多样性的多视图低秩稀疏子空间聚类算法

本文主要研究如何通过挖掘多视图特征的多样性信息来促进多视图聚类,提出了基于多样性的多视图低秩稀疏子空间聚类算法。该方法直接将视图多样性概念应用于多视图低秩稀疏子空间聚类算法框架中,确保不同视图的子空间表示矩阵的多样性;为了实现多个视图聚类一致性同时达到提高聚类性能的目标,在该框架中引入谱聚类算法共同优化求解。通过对3个图像数据集的实验验证了该算法的有效性,同时其聚类的性能优于已有的单视图及多视图算法。     

Optimality and stability of the K-hyperline clustering algorithm

K-hyperline clustering is an iterative algorithm based on singular value decomposition and it has been successfully used in sparse component analysis. In this paper, we prove that the algorithm converges to a locally optimal solution for a given set of training data, based on Lloyd’s optimality conditions. Furthermore, the local optimality is shown by developing an Expectation-Maximization procedure for learning dictionaries to be used in sparse representations and by deriving the clustering algorithm as its special case. The cluster centroids obtained from the algorithm are proved to tessellate the space into convex Voronoi regions. The stability of clustering is shown by posing the problem as an empirical risk minimization procedure over a function class. It is proved that, under certain conditions, the cluster centroids learned from two sets of i.i.d. training samples drawn from the same probability space become arbitrarily close to each other, as the number of training samples increase asymptotically.     

Discriminant sparse neighborhood preserving embedding for face recognition

Sparse subspace learning has drawn more and more attentions recently. However, most of the sparse subspace learning methods are unsupervised and unsuitable for classification tasks. In this paper, a new sparse subspace learning algorithm called discriminant sparse neighborhood preserving embedding (DSNPE) is proposed by adding the discriminant information into sparse neighborhood preserving embedding (SNPE). DSNPE not only preserves the sparse reconstructive relationship of SNPE, but also sufficiently utilizes the global discriminant structures from the following two aspects: (1) maximum margin criterion (MMC) is added into the objective function of DSNPE; (2) only the training samples with the same label as the current sample are used to compute the sparse reconstructive relationship. Extensive experiments on three face image datasets (Yale, Extended Yale B and AR) demonstrate the effectiveness of the proposed DSNPE method.     

基于深度自编码的多视图子空间聚类网络

传统子空间浅层聚类模型对于多视图和非线性数据的聚类性能不佳。为此,提出一种基于深度自编码器的多视图子空间聚类网络模型,通过在深度自编码器中引入子空间聚类中的“自我表示”特性以及加权稀疏表示,提升了多视图子空间聚类算法的学习能力。推导的深度自编码多视图子空间聚类算法能够聚类具有复杂结构的数据点。通过多视图数据集验证了提出算法的有效性。结果表明,该方法能够有效地挖掘数据固有的多样性聚类结构,并利用多个视图之间互补信息,在性能上与现有方法相比有较大的提升。