聚类分析是一项无监督学习任务,在很多领域中有广泛应用。聚类分析可以发现数据的全局分布模式,以及属性之间有价值的相互关系。随着信息技术的进步,各种类型的数据维度可达成百上千,甚至更高,因此针对高维数据的聚类分析具有非常重要的意义。由于冗余维度和复杂噪声的存在,基于距离的相似度度量往往对高维数据失效,通常采用子空间的方法对高维数据加以分析。一般认为高维数据嵌入低维的流形中,子空间聚类的目的是将源自不同子空间的高维数据,划分到其所属的低维子空间。如何去除噪声对数据的影响,也是子空间聚类中的重要任务。近年来,稀疏子空间聚类得到了广泛的关注。稀疏子空间聚类是一种基于广义稀疏表示和谱聚类算法的数据聚类框架,其核心是设计能揭示高维数据真实子空间结构的表示模型,获得低维子空间下的系数表示矩阵,来构造有助于精确聚类的相似度矩阵。稀疏子空间聚类在计算机视觉、图像处理和模式识别等领域内已有广泛的研究和应用,但是仍然存在很多问题亦有很大的发展空间。本文在稀疏子空间聚类的模型和快速算法上展开了具有针对性的研究,具体而言,本文的主要工作和具体创新如下:1.提出一种基于稀疏表示的低秩子空间恢复和划分的统一框架(Low Rank subspace Sparse Representation,LRSR)。高维数据中往往含有冗余维度和奇异噪声,因此需要利用子空间恢复和划分的方式找到其所属的子空间。低秩表示的方法在含有稀疏噪声的数据上表现良好,但是直接利用含有噪声的现实数据作为字典并不合理,本文在LRSR模型中引入字典变量,与系数表示矩阵共同求解,具有更强的容错能力。在不相交子空间的假设下,LRSR模型对系数表示矩阵同时施加低秩和稀疏的约束,使其满足强对角块结构,为后续的子空间聚类奠定了基础。同时,LRSR能够恢复数据集中受噪声严重污染的数据。LRSR模型在ADMM算法的框架下求解,本文给出了算法的收敛性保证。人脸图像Extended YaleB和运动轨迹Hopkins155数据集上实验结果表明LRSR算法在去除噪声干扰、恢复原始数据、聚类准确率的表现上明显优于现有方法。2.提出一种基于谱间距全局信息和样本间局部距离的相似度矩阵求解方法(Global-Local Affinity matrix Model,GLAM)。在图学习方法中,图的构造(相似度矩阵的构造)揭示数据间的关系,如何构造反映数据类内相似属性和类间差异的相似度矩阵是非常关键的。利用谱间距作为全局约束,在一定程度上能够抵抗噪声的干扰,维持与类别相关的相似度矩阵特征空间的稳定性。因此,本文提出从最大化谱间距的角度去逼近理想对角块结构的相似度矩阵,同时将数据间的局部距离作为正则项来防止谱间距过大而造成相似度矩阵失效。子空间划分的方法与GLAM构造的相似度矩阵相结合,令子空间聚类的准确率有明显的提升。同时,本文还将GLAM方法构造的相似度矩阵成功地应用到基于图的半监督分类任务中,现实公共数据集上实验结果验证了 GLAM算法的有效性。3.提出一种求解核范数优化问题的快速算法(Non-convex Low Rank Represen-tation via Block Coordinate Descent Method,NLRR++)。基于核范数优化的子空间划分方法中,每次迭代都包含时间复杂度很高的奇异值分解,使其很难扩展到大规模数据集。本文在矩阵分解的框架下,通过单位秩矩阵和的方式重新构造非凸低秩模型,并利用块坐标下降法更新变量,使得算法的时间复杂度由O(n3)降低到O(mnd),空间复杂度由O(n2)降低到O(mn)(通常情况下d《m《n)。在此基础上,本文还设计了按一定概率分布值更新内部变量的随机算法,进一步缩短算法的执行时间。算法的每次迭代中只包含“矩阵-向量”乘法,计算简单便于并行化处理。通过精心设计变量中坐标的更新顺序,新算法能更快收敛。同时,给出了NLRR++算法的收敛性分析。考虑到谱聚类算法在大数据集上的不可扩展性,利用非凸模型的特殊形式,提出了更加快速简单的聚类方法。和当前先进的方法相比,NLRR++算法更加准确高效,求解速度比最先进的非凸低秩方法快12倍。