深度嵌入子空间聚类方法

10高效的深度嵌入子空间聚类0蔡金宇1,3，范继聪2,3*，郭文忠1，王世平1，张云鹤1，张昭401福州大学计算机与数据科学学院，中国 2香港中文大学（深圳）数据科学学院，中国3深圳大数据研究院，中国 4合肥工业大学，中国0{jinyucai1995，cszzhang}@gmail.com，fanjicong@cuhk.edu.cn0guowenzhong@fzu.edu.cn，{shipingwangphd，zhangyhannie}@163.com0摘要0最近，深度学习方法在数据聚类任务中取得了显著进展。深度聚类方法(包括基于距离和子空间的方法)将聚类和特征学习集成到一个统一的框架中，聚类和表示之间存在相互促进的关系。然而，深度子空间聚类方法通常在自表达模型的框架下，因此具有二次时间和空间复杂度，这限制了它们在大规模聚类和实时聚类中的应用。在本文中，我们提出了一种新的深度聚类机制。我们旨在以迭代的方式从深度表示中学习子空间基，而经过改进的子空间基则有助于学习深度神经网络的表示。所提出的方法不属于自表达框架，其样本规模与线性相关，并适用于任意大规模数据集和在线聚类场景。更重要的是，所提出方法的聚类准确性远高于其竞争对手。在基准数据集上与最先进的聚类方法进行了广泛的比较研究，证明了所提出方法的优越性。01. 引言0聚类是机器学习中的一个基本问题，旨在在没有标签信息的情况下将样本分为类别，要求类内相似度高、类间相似度低。许多经典的聚类算法，如k-means[29]和谱聚类(SC)[30]在实际应用中取得了巨大的成功。然而，它们在处理具有复杂结构或/和高维度的数据时效果不佳，可以通过使用精细特征来改进。0*范继聪为通讯作者。0确实，一些先前的研究[14, 37, 38,47]利用了特征学习技术，如非负矩阵分解[2]、自编码器(AE)[1]及其变种[24, 31,36]来学习用于聚类的低维嵌入，从而提高了聚类准确性。然而，由于这些方法是两阶段聚类，并且特征学习不专门用于聚类，所以不能保证学习到的表示适用于聚类。最近，一些研究人员[3, 9, 26, 43,46]提出了端到端聚类方法，如深度嵌入聚类(DEC)[40]、联合无监督学习(JULE)[41]、深度自适应聚类(DAC)[6]和深度综合相关挖掘(DCCM)[39]。在这些方法中，聚类目标与网络优化过程相结合，提供了一种学习面向聚类的嵌入表示的方法。然而，大多数深度聚类方法在识别聚类时使用基于欧氏距离的度量，而欧氏距离并不总是对不同类型的数据结构有效或合理。子空间聚类假设数据位于不同的子空间[11]。一类经典的子空间聚类方法，如稀疏子空间聚类(SSC)[11]和低秩表示(LRR)[27]主要基于谱聚类[30]，在许多任务中，如人脸图像聚类，它们的性能优于k-means和经典谱聚类。最近，一些研究人员[8, 21, 25,44]表明，联合子空间聚类和深度学习在基准数据集上具有良好的性能。然而，这些方法很难扩展到大规模数据集，因为它们需要学习一个自表达矩阵，导致二次时间和空间复杂度。因此，一些最新的工作[12, 48,49]致力于提高子空间聚类的效率。本文旨在提供一种高效准确的深度子空间聚类方法。我们提出从提取的潜在特征中学习一组子空间基。𝑠1D(1) D(2)⋯D(𝑘)𝑎𝑗 = 𝐳𝑖TD(𝑗)𝑠2𝑠𝑘𝑠𝑖ǁ𝑠1ǁ𝑠2ǁ𝑠3ǁ𝑠𝑘𝐿𝑆𝑢𝑏𝐿𝑅𝑒𝑐𝑜𝑛𝐳𝑖𝐳1 𝐳2⋯𝐳𝑛1𝑎1 𝑎2⋯𝑎𝑘20编码器0解码器0子空间相似度向量0归一化的0子空间相似度0改进的0子空间相似度0�0�0�0�（包含子空间基）0输入数据重构0嵌入的0表示 �0图1.所提出方法的示意图。自动编码器网络用于学习输入数据的嵌入表示 Z，然后 Z 与子空间 D结合构建子空间相似度向量，进而产生归一化的子空间相似度S。随后，从 S 计算得到改进的子空间相似度 �S，提供自监督信息。注意，d 是子空间的维数，L Recon 和 L Sub分别表示重构损失和 � S 与 S之间的差异，网络通过联合优化它们进行训练。0通过深度自动编码器进行嵌入，其中基和网络参数被迭代地改进。所提出方法的网络结构如图1所示。我们的贡献如下。0•我们提出了一种新颖的深度子空间聚类方法，不属于传统的自表达框架。0• 我们的方法具有线性的时间和空间复杂度，因此适用于大规模子空间聚类。0•我们将该方法推广到在线聚类，以便能够有效处理任意大规模数据集和流数据集。0•我们分析了使用深度神经网络将基于距离的聚类和子空间聚类转换的可行性。0许多基准数据集（例如Fashion-MNIST、STL-10和REUTERS-10K）上的数值结果表明，我们的方法比竞争对手更有效。02. 相关工作和简要讨论02.1. 深度聚类0早期的深度聚类方法旨在应用深度特征学习方法（例如自动编码器[36]和变分自动编码器（VAE）[24]）从复杂的高维数据中提取特征进行聚类。然而，这些解决方案很难学习适合聚类任务的表示。当前的深度聚类方法侧重于构建端到端模型。Xie等人提出了DEC[40]，该方法设计了一个受到启发的聚类目标0通过t-SNE[35]进行可视化。它提供了一个聚类模型，可以同时优化聚类中心和嵌入特征。Chang等人提出了深度自进化聚类（DSEC），这是一种基于自进化的算法，通过选择的模式对网络进行交替训练。在[39]中，Wu等人提出了一种称为DCCM的方法，该方法使用伪标签进行自监督，并使用互信息来捕捉更具区分性的表示以进行聚类。Huang等人提出的分区置信度最大化（PICA）[20]最小化了一个分区不确定性指标，并学习最有信心的聚类分配。需要注意的是，这些深度聚类方法使用欧氏距离分配聚类，当聚类不集中在均值上时可能不太有用。02.2. 子空间聚类0经典的子空间聚类方法，如SSC[11]、LR-R[27]、Kernel-SSC[32]旨在学习用于谱聚类的自表达相似度矩阵。Ji等人提出了深度子空间聚类网络（DSC-Net），该网络将自表达模块与自动编码器网络结合起来。与SSC和LRR相比，DSC-Net在几个图像数据集上显示出显著的改进。Zhou等人提供了一种称为深度对抗子空间聚类（DASC）的方法，该方法利用生成对抗网络[16]进行对抗学习，提高了深度子空间聚类的性能。Zhou等人提出了分布保持子空间聚类（DPSC），以保留子空间中的潜在分布，提高子空间聚类模型的特征学习能力。另一方面，一些研究人员试图降低子空间聚类的复杂性[7, 12, 13, 33,49]。例如，Zhang等人提出了k-子空间聚类网络（k-SCN），将子空间的更新整合到嵌入空间的学习中，以解决学习相似度矩阵的缺点。Fan提出了一种称为k-分解子空间聚类（k-FSC）的方法，它具有线性的时间和空间复杂度，能够处理缺失数据和流数据。02.3. 简要讨论0我们在表1中分析了几种（由于空间限制）经典子空间聚类、大规模子空间聚类和深度子空间聚类方法的时间和空间复杂度。我们可以看到，这些经典子空间聚类方法和深度子空间聚类方法在样本数量方面具有二次时间和空间复杂度。相比之下，我们的方法具有线性时间和空间复杂度，与[ 12]的大规模子空间聚类方法相当。SSC [11]O(mn2)O(mn + ρn2)LRR [27]O(mn2 + m3)O(mn + n2)KSSC [32]O(n3)O(mn + n2)SSSC [33]O(ms3+k2ns)O(mn + ρn2s)S3COMP-C [7]O(dρn3(1 − δ))O(mn + ρn2)k-FSC [12]O(kmrn + ϑmn)O(mn + kmr + krn)DSC-Net [21]O(ln2 + ˜m˜ln)O( ˜mn + n2 + θ)DASC [52]O(ln2 + ˜m˜ln)O( ˜mn + n2 + θ)DPSC [51]O(ln2 + ˜m˜ln)O( ˜mn + n2 + θ)NCSC [50]O(ln2 + ˜m˜ln)O( ˜mn + n2 + θ)PSSC [28]O(mn2 + ln2 + ˜m˜ln)O( ˜mn + n2 + θ)EDESC(ours)O(kdpn + ˜m˜pn)O( ˜mn + kn + kpd + θ)x = fj(v) + ε,(1)̸xi ≈ hW( ˆB(j)ˆvi), xi ∈ Cj,(2)(3)̸̸̸,̸̸30方法 时间复杂度（每次迭代） 空间复杂度0表1. 我们的方法与一些深度聚类和子空间聚类方法在聚类 n个维度为 m的样本时的时间和空间复杂度的比较。为了节省空间，我们将参数的解释放在补充材料中。03. 方法论03.1. 提出的模型0在本文中，我们旨在基于深度学习的子空间聚类，并尝试解决以下问题。0问题 1 给定一个数据矩阵  X  ∈  R m × n ，其中  m表示特征数量，  n 表示样本数量。假设  X = ¯ XP ，其中¯ X = [  ¯ X (1) , ¯ X (2) , . . . , ¯ X ( k ) ] ，而  P  ∈  R n ×n 是一个未知的排列矩阵。对于  j  = 1 , . . . , k ，假设 ¯ X (j ) ∈  R m × n j  的列由以下方式生成0其中  f j  :  R r k −→  R m 是一个未知的非线性函数，r j  0是一个超参数。因此，神经网络只需要学习一个近似的φ函数，这并不困难。如果我们交换u和v的角色，网络需要学习一个函数h，使得∥h(v1)−h(v2)∥是∥v�1v2∥的单调（粗略）变换，这是相当困难的。上述结果和分析验证了提供一个高效准确的深度子空间聚类方法来处理问题2或更一般的问题1是必要的。04.实验04.1.数据集和评估指标0为了评估我们方法的聚类性能，我们考虑了六个广泛使用的基准数据集，包括两个灰度图像数据集（MNIST2和Fashion-MNIST3），三个具有挑战性的真实世界图像数据集0子空间合成数据 欧几里得合成数据0图3.基于欧几里得和子空间原理的合成数据的聚类性能比较。0数据集名称 # 总样本数 # 类别数 # 大小0表2.六个基准数据集的详细信息。0（CIFAR-10 4，CIFAR-100和STL-105），以及一个文本数据集REUTERS-10K6。详细信息如表2所示。我们使用两个常用的聚类指标，聚类准确度（ACC）和标准化互信息（NMI），来衡量聚类性能。这两个指标的取值范围为[0，1]，得分越高表示聚类性能越好。04.2.实验设置0我们的模型由一个m-500-500-1,000-p全连接网络的编码器和对称的解码器构成。我们首先用相同结构的自动编码器进行50个epoch的预训练，然后使用预训练的权重初始化我们的模型。我们的方法使用Adam[23]优化器。学习率设置为0.001，训练epoch设置为200，批量大小固定为512，聚类k由相应数据集的类别给出。特别地，对于三个真实世界的图像数据集（STL-10，CIFAR-10和CIFAR-100），我们应用ResNet50[19]提取它们的2,048维特征。至于超参数的设置，η被固定为与d相同的值，并且我们在第4.6节进一步讨论了不同的d和β值对聚类的影响。04.3.与最先进方法的比较0在本节中，我们从三个方面与SOTA方法进行全面实验比较，包括经典方法（k-means [29]，SC [45]，AC[17]和NMF [2]），深度聚类方法（AE [1]，DAE[36]，VAE [24]，DEC [40]，IDEC [18]，04 http://www.cs.toronto.edu/kriz/cifar.html5 https://cs.stanford.edu/acoates/stl10/ 6https://keras.io/api/datasets/reuters/60方法/数据集 Fashion-MNIST CIFAR-10 CIFAR-100 STL-10 REUTERS-10K0k-means [29] 0.474 0.512 0.229 0.087 0.130 0.084 0.192 0.125 0.524 0.312 SC [45] 0.508 0.575 0.247 0.1030.136 0.090 0.159 0.098 0.402 0.375 AC [17] 0.500 0.564 0.228 0.105 0.138 0.098 0.332 0.239 – – NMF [2]0.434 0.425 0.190 0.081 0.118 0.079 0.180 0.096 – – AE [1] 0.567 0.553 0.314 0.239 0.165 0.100 0.303 0.2500.597 0.323 DAE [36] 0.493 0.548 0.297 0.251 0.151 0.111 0.302 0.224 0.582 0.354 VAE [24] 0.607 0.5750.291 0.245 0.152 0.108 0.282 0.200 0.625 0.329 DEC [40] 0.590 0.601 0.301 0.257 0.185 0.136 0.359 0.2760.618 0.314 IDEC [18] 0.592 0.604 0.316 0.273 0.191 0.140 0.378 0.324 0.684 0.351 VaDE [22] 0.578 0.6300.156 0.036 – – – – 0.723 0.416 JULE [41] 0.563 0.608 0.272 0.192 0.137 0.103 0.277 0.182 0.626 0.405 DAC[6] 0.615 0.632 0.522 0.396 0.238 0.185 0.470 0.366 – – DCC [4] – – 0.524 0.424 – – 0.489 0.371 – – DCCM[39] – – 0.623 0.496 0.327 0.285 0.482 0.376 – – VaGAN-GMM [42] 0.638 0.633 0.287 0.158 – – – – 0.8010.536 DSEC [5] – – 0.477 0.437 0.255 0.212 0.481 0.403 0.783 0.708 PICA [20] – – 0.696 0.591 0.337 0.3100.713 0.611 – –0EDESC（我们的方法）0.631 0.670 0.627 0.464 0.385 0.370 0.745 0.687 0.825 0.6110表3. 与基线和最先进方法在五个实验数据集上的聚类性能比较。注意最佳三个结果用粗体标记。0VaDE [22]，JULE [41]，DAC [6]，DCC [4]，DCCM[39]，VaGAN-GMM [42]，DSEC [5]和PICA[20]，以及子空间聚类方法（SSC [11]，LRR [27]，KSSC[32]，DSC-Net [21]，k-SCN [49]，DASC [52]，DPSC[51]，PSS-C[28]）。注意，我们直接从相关论文中报告了它们的实验结果。0与经典聚类和深度聚类方法的聚类性能比较如表3所示，观察到我们的方法在三种不同类型的数据集上都实现了优越的聚类性能。特别是在STL-10数据集上，提出的方法在准确率和NMI方面分别比PICA高出3.2%和7.6%。而在其他四个数据集上，提出的方法也始终保持着前三的聚类性能。此外，由于大多数深度聚类方法都是基于欧氏距离度量，这些观察结果还暗示了欧氏距离度量并不总是适用于所有数据结构，考虑到不同度量，如数据之间的角度关系，可能有助于揭示更好的聚类结构。表4展示了与几种子空间聚类方法的性能比较。带有SAE的方法表示对从堆叠自编码器中学习到的特征进行处理。在Fashion-MNIST数据集上，提出的方法在准确率和NMI方面优于其他比较方法，而在MNIST数据集上显著优于其他比较方法。值得注意的是，由于子空间聚类方法大多基于谱聚类，需要计算一个n×n的相似度矩阵，导致时间复杂度较高。时间和s-的比较也展示了我们方法的效率。0方法/数据集 MNIST Fashion-MNIST0准确率 NMI 准确率 NMI0SSC-SAE [11] 0.754 0.662 0.523 0.512 LRR-SAE[27] 0.740 0.669 0.580 0.591 KSSC-SAE [32] 0.8150.845 0.571 0.604 DSC-Net [21] 0.532 0.479 0.5580.548 k-SCN [49] 0.833 0.773 0.600 0.623 DASC[52] – – 0.617 0.647 DPSC [51] – – 0.624 0.645PSSC [28] 0.843 0.843 – –0EDESC（我们的方法）0.913 0.862 0.631 0.6700表4.与几种子空间聚类方法在MNIST和Fashion-MNIST上的聚类性能比较。注意最佳结果用粗体标记。0与表1中引用的几种聚类方法相比，计算复杂度的比较也展示了提出方法在计算成本方面的优势。此外，在表5中还展示了与几种聚类方法的运行时间比较，进一步证明了我们方法的效率。值得一提的是，提出的方法可以使用小批量实现，即具有扩展到在线聚类问题的潜力，这将在第4.8节中讨论。04.4. 定性研究0嵌入表示的可视化。图40图4展示了在具有挑战性的STL-10数据集上学习到的嵌入表示的t-SNE [35]可视化结果。 70(a) 原始数据0(e) 第1个Epoch (h) 第120个Epoch0(c) DEC (d) IDEC0(b) AE0图4. 在STL-10数据集上使用t-SNE可视化嵌入表示。注意，第一行显示了用作比较的几种方法的可视化，第二行显示了训练过程中提出方法的可视化。0数据集 MNIST Fashion-MNIST REUTERS-10K0SSC OT OT 13038.84 DSC-Net 5364.85 4225.53 N/A0DEC 383.49 346.57 65.920EDESC (MB) 414.68 372.20 61.09 EDESC (无MB) 68.3759.43 10.530表5.运行时间（秒）比较。MB、OT和N/A分别表示mini-batch、内存不足和结果不可用。0第一行显示了竞争方法未能找到良好的聚类结构。特别是在没有重构损失的指导下，从DEC学到的表示无法很好地反映数据结构，导致可视化结果略逊一筹。第二行显示了所提出方法在不同训练轮次中学到的表示的可视化结果，了解表示在训练过程中的演变是重要的。我们可以看到，随着训练轮次的增加，嵌入表示变得越来越具有区分性，与其他方法相比，所提出的方法最终揭示了更显著的聚类结构。0混淆矩阵。图5显示了所提出方法在STL-10和REUTERS-10K上的混淆矩阵，注意，预测的聚类标签已经经过处理，以与真实标签最佳映射。可以看到，两个混淆矩阵都呈现出对角结构，即大多数样本被正确分配到相应的类别。此外，以STL-10的混淆矩阵为例，还有一些有趣的观察结果。混淆矩阵中更高的显著性总是与逻辑上更相关的类别相关，例如'cat'。0(a) STL-10 (b) REUTERS-10K0图5.我们方法和真实标签在STL-10和REUTERS-10K上预测的聚类的混淆矩阵。0'dogs'和'monkey'属于'animal'，而'airplane'、'ship'、'truck'和'car'属于'transportation'。这与人类的思维一致，因为在现实场景中，这些物体有时会混淆。04.5. 消融研究0在本节中，我们进行了一项消融研究，以探索所提出方法中每个损失项对聚类性能的影响。具体而言，我们通过去除相应的损失项构建了三个退化模型，并在STL-10和REUTERS-10K数据集上进行实验。表6总结了消融研究的实验结果，我们可以得出一些结论。首先，L Recon对于在训练过程中保持固有数据结构信息非常重要，对聚类性能有很大影响。其次，聚类目标在训练中至关重要，因为在两个数据集的训练中去除 L Sub后，观察到显著的性能下降。第三，对子空间代理 D的约束可以帮助模型捕捉更具有区分性的嵌入表示。(a) STL-10(b) REUTERS-10K0.050.10.150.20.250.30.350.40.450.501020304050EpochDECIDECEDESC0.120.180.240.30.360.420.480.540.601020304050EpochDECIDECEDESC(a) STL-10(b) HAR80方法 STL-10 REUTERS-10K0ACC NMI ACC NMI0无 L Recon 0.512 0.565 0.727 0.466 无 L Sub 0.6260.658 0.662 0.338 无 D Cons 0.550 0.618 0.7990.590 竞争方法 EDESC 0.745 0.687 0.825 0.6110表6. 所提出方法及其退化模型的消融研究结果。0(a) ACC (b) NMI0图6.在REUTERS-10K数据集上，所提出方法的参数敏感性，d和β。0从而提高聚类性能。04.6. 参数敏感性0在本节中，我们分析了两个主要超参数d和β对聚类性能的影响。具体而言，我们将d的取值范围设置为[1, 2, ..., 6,7]，将β的取值范围设置为[0.01, 0.05, ..., 5,10]，然后在REUTERS-10K上进行实验。不同参数值下的聚类性能显示在图6中，我们得出以下观察结果。首先，当β的值过低时，聚类性能受到严重影响，特别是在NMI上，这说明所提出的聚类目标对聚类有益。其次，过高的β也对聚类性能产生负面影响。一个可能的解释是过高的值影响了原始数据固有结构的学习，导致嵌入空间的扰动。第三，与ACC相比，NMI对d的变化更为敏感。然而，它们在大多数参数值下仍然保持相对良好的聚类性能。总体而言，推荐的β值范围为[0.1,1]，d取决于数据集中的类别数量，但经验上不超过10个。04.7. 收敛分析0为验证所提方法的收敛性，我们在STL-10和REUTERS-10K数据集上运行了200个epochs，然后在图7中呈现了收敛曲线。可以观察到两条曲线在25个epochs后几乎趋于平稳，在100个epochs后基本达到收敛，这证明了所提方法的收敛性和快速收敛速度。0图7. STL-10和REUTERS-10K的收敛曲线。0聚类准确率0聚类准确率0图8. STL-10和HAR的在线聚类性能。04.8. 在线聚类0在线聚类旨在对流数据进行聚类，因此需要高效的算法，这对于现有的子空间聚类方法来说是一个挑战，但我们的方法可以处理。在这里，我们将我们的方法应用于STL-10和Human Activities Recognition (HAR)7数据集，并与DEC和IDEC进行比较。聚类性能如图8所示，验证了我们的方法在在线聚类中的可行性和有效性。05. 结论0在本文中，我们提出了一种基于深度学习的新型子空间聚类方法8。该方法具有线性时间和空间复杂度，因此适用于大型数据集。对许多基准数据集的实验结果验证了所提方法具有比竞争对手更高的聚类准确性。我们工作的主要限制源于全连接网络，可以通过更复杂的网络结构进行增强。0致谢0本工作部分得到了中国国家自然科学基金（编号U21A20472），福建省自然科学基金（编号2020J01130193）和深圳大数据研究院（编号T00120210002）的支持。07 https://archive.ics.uci.edu/ml/datasets/Human+Activity+Recognition+Using+Smartphones 8代码可在https://github.com/JinyuCai95/EDESC-pytorch找到90参考文献0[1] Yoshua Bengio, Pascal Lamblin, Dan Popovici, 和 HugoLarochelle. 深度网络的贪婪逐层训练.在神经信息处理系统进展中, 页码153–160, 2007.  1 ,  5 ,  60[2] Deng Cai, Xiaofei He, Xuanhui Wang, Hujun Bao, 和 Ji-awei Han. 保持局部非负矩阵分解.在国际人工智能联合会议论文集中, 页码1010–1015.国际人工智能联合会议, 2009.  1 ,  5 ,  60[3] Jinyu Cai, Shiping Wang, Chaoyang Xu, 和 Wenzhong