判别性增强的稀疏子空间聚类_胡慧旗.pdf

第 49卷 第 2期2023年 2月Computer Engineering 计算机工程判别性增强的稀疏子空间聚类胡慧旗，张维强，徐晨（深圳大学 数学与统计学院，广东 深圳 518060）摘要：稀疏关系表示(SRR)是一种性能良好的子空间聚类算法，其利用一个数据样本和所有样本间的邻域关系作为新特征来学习自表示系数，由自表示系数矩阵构建相似度矩阵并通过谱聚类得到聚类结果。同时考虑相似度矩阵的稀疏性和聚集性，在 SRR算法基础上提出一个判别性增强的稀疏子空间聚类模型。对邻域关系矩阵的自表示矩阵采用平方 F 范数代替 SSR 中的核范数，降低模型求解难度，并在邻域关系矩阵的自表示矩阵中引入新的正则项，保证自表示矩阵的类间判别性和邻域关系矩阵的类内聚集性，进一步优化聚类性能。实验结果表明：与SSC、LRR、LSR、BDR-B、SRR 等模型相比，该模型具有较好的聚类性能；在 MNIST、USPS、ORL 数据集上，聚类错误率较 SRR 模型分别下降 9.6、14.1、3.8 个百分点；在 Extended Yale B 数据集上，针对 2、3、5、8、10 类聚类问题的聚类错误率较 SRR模型分别下降 0.39、0.72、1.32、2.73、3.28个百分点。关键词：子空间聚类；相似度矩阵；邻域关系；判别性；谱聚类开放科学（资源服务）标志码（OSID）：中文引用格式：胡慧旗，张维强，徐晨.判别性增强的稀疏子空间聚类 J.计算机工程，2023，49（2）：98-104.英文引用格式：HU H Q，ZHANG W Q，XU C.Discriminant enhanced sparse subspace clustering J.Computer Engineering，2023，49（2）：98-104.Discriminant Enhanced Sparse Subspace ClusteringHU Huiqi，ZHANG Weiqiang，XU Chen（College of Mathematics and Statistics，Shenzhen University，Shenzhen 518060，Guangdong，China）【Abstract】The Sparse Relation Representation（SRR）algorithm shows good clustering performance.It uses the neighborhood relation between a data sample and other samples as new features to learn the self-representation coefficient，which is then used to construct the affinity matrix；spectral clustering is finally applied to realize segmentation.Considering both the sparsity and aggregation of a similarity matrix，this study proposes a discriminant-enhanced sparse subspace clustering model based on the SSR algorithm.The study s novelty is two-fold：first，to overcome the complexity induced by the nuclear norm in SSR，it uses the squared F norm to regularize the self-representation matrix；second，it introduces a new regularization term that can guarantee the inter-class discrimination of the self-expression coefficient matrix and grouping effect of the neighborhood relation matrix.The experimental results show that compared with SSC，LRR，LSR，BDR-B，SRR，and other models，this model has better clustering performance.On MNIST，USPS，and ORL datasets，the clustering error rate of this model is 9.6，14.1，and 3.8 percentage points lower than that of the SRR model，respectively；on the Extended Yale B dataset，the clustering error rates of the model in the 2，3，5，8，and 10 cluster problems are 0.39，0.72，1.32，2.73，and 3.28 percentage points lower than in the SRR model，respectively.【Key words】subspace clustering；affinity matrix；neighborhood relation；discrimination；spectral clusteringDOI：10.19678/j.issn.1000-3428.00636210概述 子空间聚类是一种非常有效的高维数据聚类方法，假设高维数据分布在几个低维子空间的并中，其目的是将高维数据分成不同的类，一类对应一个子空间。目前，子空间聚类已被广泛应用于计算机视觉1、图像处理2-3、系统识别4等领域。基于谱聚类的子空间聚类算法因其计算简单、聚类性能优异而成为研究热点。稀疏子空间聚类（SSC）5-6、低秩表示子空间聚类（LRR）7-8和最小二乘回归子空间聚类基金项目：国家自然科学基金“多视角聚类关键科学问题及其在图像分割中的应用研究”（61972264）；国家自然科学基金“基于高阶张量分解的复杂视频显著性目标探测模型”（61872429）；广东省自然科学基金“多视角聚类及其在健康信息学中的应用”（2019A1515010894）；深圳市高校稳定支持计划“基于深度神经网络的多视角聚类研究”（20200807165235002）。作者简介：胡慧旗（1998），女，硕士研究生，主研方向为子空间聚类；张维强，副教授、博士；徐 晨（通信作者），教授、博士。收稿日期：2021-12-27 修回日期：2022-03-30 Email：人工智能与模式识别文章编号：1000-3428（2023）02-0098-07 文献标志码：A 中图分类号：TP391.4第 49卷 第 2期胡慧旗，张维强，徐晨：判别性增强的稀疏子空间聚类（LSR）9是基于谱聚类的子空间聚类中 3 个经典的算法，它们的共同点是利用高维数据的自表示构建相似度矩阵，然后通过谱聚类得到聚类结果。3种算法的不同点在于自表示系数的约束不同：SSC对自表示系数矩阵采用l0或l1范数约束，希望每个数据的自表示是稀疏的，仅被其所属子空间（即同类）的数据表示，但是稀疏约束会导致自表示过于稀疏，即仅从同类数据中挑选最相似的数据对其表示，忽略了其他相关的数据，不利于聚类；LRR对自表示系数矩阵采用低秩约束，这是一种全局结构，但低秩表示可能导致过于稠密的自表示，即不同子空间的数据参与了表示，另外，当数据采样不足时，低秩表示可能会失效；LSR对自表示系数采用l2范数正则，这有利于将高度相关的数据聚集在一起，但也会导致类内类间的自表示都是均匀的，不利于分离不同类别的数据。在子空间独立的条件下，以上 3 种算法都被证明自表示系数矩阵是一个分块对角矩阵，即来自不同子空间数据间的表示系数为零。自表示系数矩阵的块对角结构揭示了数据与低维空间的真实隶属关系，从而相应相似度矩阵表现出类内相似度高、类间相似度低的特性，这有利于谱聚类产生正确的聚类标签。因此，子空间聚类问题关键在于自表示系数矩阵的构造，理想的自表示系数矩阵应同时具有稀疏性和聚集性，即类间稀疏、类内聚集。鉴于这一考虑，很多算法10-12对数据的自表示矩阵同时进行稀疏约束和低秩约束，或者同时进行稀疏约束和l2范数约束，强制自表示系数矩阵具有稀疏性和聚集性。FENG 等13指出自表示系数矩阵应具有块对角结构，并通过添加显式的硬约束，强迫 SSC 和 LRR 得到的自表示系数矩阵具有精确的块对角结构。进一步地，LU 等14提出 K 块对角正则项，迫使自表示系数矩阵具有块对角结构。考虑模型的整体性能，LI等15提出结构稀疏子空间聚类（SSSC）模型，通过引入联合正则项实现系数矩阵和聚类标签的联合学习，使得模型直接输出聚类标签。受 SSSC 模型启发，ZHANG 等16在 LRR 模型中加入联合正则项，提出低秩结构稀疏子空间聚类（LRS3C）模型，构建了一个联合优化框架。在 LRS3C 基础上，YOU 等17通过添加促使低相关数据尽量远离的l1范数正则项，防止系数矩阵过于密集，加强了类间数据的稀疏性，进一步提升了聚类性能。然而，原始数据中往往存在噪声和其他干扰，直接对原始数据进行自表示得到的相似度矩阵也会受到噪声或干扰的影响，导致不能准确反映数据的真实子空间隶属关系，造成数据误分类。针对此问题，SRR18对原始数据进行了二阶自表示：首先对原始数据进行自表示，由于得到的自表示矩阵反映了每个数据与其他数据的某种相关性，因此称其为邻域关系矩阵；然后将每个数据的自表示向量作为数据的新特征，对新特征再进行二阶自表示，也称为重构系数矩阵；最后基于此矩阵构造相似度矩阵，并通过谱聚类得到最终聚类结果。实验结果表明，该方法具有较高的聚类精度。本文基于 SRR中数据的邻域关系可准确反映数据类别属性这一特点，提出一种兼顾相似度矩阵稀疏性和聚集性的子空间聚类方法。利用 F 范数代替核范数，降低 SRR模型的求解难度，并构建一个新的正则项来增强不同类别数据之间表示系数的判别性。在此基础上，使用人脸和手写体数字数据集进行实验，验证本文方法的聚类效果。1符号定义与相关工作 首先定义本文所用数学符号：设数据矩阵X=x1,x2,xn Rd n包含来自k个子空间的n个d维数据，一个数据对应一个列xi，每个数据点只能属于其中一个子空间；C=(Cij)Rn n为数据X的自表示矩 阵，称 为 邻 域 关 系 矩 阵，其 中 每 一 列 为Ci,i=1,2,n；Ci-Cj2表示向量(Ci-Cj)的欧几里得范数；C的 自 表 示 矩 阵 记 作Z，即 重 构 系 数 矩 阵Z Rn n，Z1=ij|Zij和ZF=ijZ2ij分 别 为Z 的l1范数和 F范数，Z*=ii(Z)为矩阵Z的函数，其中i(Z)为Z的奇异值，ii(Z)表示Z的所有奇异值之和；diag(C)是一个对角矩阵，其对角元素是矩阵C相应对角线上的元素；I表示单位矩阵。考虑到原始数据中存在大量噪声和干扰，WEI等18认为数据间的邻域关系特征比原数据更能揭示其类别属性，并提出如下 SRR模型：minC,Z,E1,E2(C1+Z*+1E11+2E22F)s.t.X=XC+E1,diag(C)=0,C=CZ+E2（1）其中：X表示原始数据矩阵，其中一列对应一个数据样本；C为邻域关系矩阵；Z为重构系数矩阵；E11用于刻画数据中的离群点；E22F用于处理邻域关系矩阵中的高斯噪声；1和2为权重参数。在 SSR 模型中：首先邻域关系矩阵C的每一列表达了原始数据矩阵X中的对应列与其他数据之间的某种相关性，并利用l1范数对其进行约束；然后