论文解读（IDEC）《Improved Deep Embedded Clustering with Local Structure Preservation》

论文信息

论文标题：Improved Deep Embedded Clustering with Local Structure Preservation
论文作者：Xifeng Guo, Long Gao, Xinwang Liu, Jianping Yin
论文来源：2017, IJCAI
论文地址：download 
论文代码：download 

1 Introduction

 　　本文解决的思路：

• • 使用聚类损失函数指导代表特征空间的 points 分布；
  • 采用 under-complete autoencoder 维护数据的局部结构；
  • 联合 聚类损失 和 AE 损失 来训练。

　　IDEC 既可以很好的实现聚类任务，还可以学到能保持局部结构的表示（Representation）。

2 Related Work

2.1 Deep Clustering

　　目前阶段的聚类算法：

1. 1. Two-stage work that applies clustering after having learned a representation；[ 该方法基于良好的表示 ]
   2. Approaches that jointly optimize the feature learning and clustering；[ 特征学习的时候同时进行聚类 ]

　　对于 1 举例：

1. • Tian et al., 2014 ：先使用 AE 学到低维有用表示，然后使用 k-means 进行聚类；
   • Chen, 2015 ：层级训练深度信念网络(DBN)，然后将 non-parametric maximum-margin 聚类应用于学习到的中间表示；
   • Peng et al., 2016 ： 使用稀疏自编码器，同时自适应学习局部和全局结构信息的表示，再采用传统的聚类算法进行聚类；

　　对于 2 举例：

• • Yang et al., 2016 ：proposes a recurrent framework in deep representations and image clusters, which integrates two processes into a single model with a unified weighted triplet loss and optimizes it end-to-end. 
  • Xie et al.，2016 ：DEC 通过深度神经网络学习从观测空间到低维潜在空间的映射，可以同时获得特征表示和聚类分配；

2.2 Autoencoder

　　AE 有两个部分：

• • Encoder：编码器函数为  z=fW(x)z=fW(x)  ，输出表示 zz 。

　　　　　　z=fW(x)z=fW(x)

• • Decoder：解码器函数为  x′=gW′(z)，根据表示 z 重构原始输入 x 。

　　　　　　x′=gW′(z)

　　两种常见的自编码器：

• • 欠完备自编码器（ Under-complete autoencoder）：z 的维度要小于原始输入的维度。
  • 去噪自编码器（ Denoising autoencoder）：L=‖x−gW′(fW(˜x))‖22(1)

　　Reference：

1. 1. 欠完备自编码器：从自编码器获得有用特征的一种方法是限制  h  的维度比 x 小，这种编码维度小于输入维度的自编码器称为欠完备（undercomplete）自编码器。学习欠完备的表示将强制自编码器捕捉训练数据中最显著的特征。
   2. 去噪自编码器（denoising autoencoder，DAE）是一类接受损坏数据作为输入，并训练来预测原始未被损坏数据作为输入的自编码器。

2.3 Deep Embedded Clustering

　　DEC 首先对 AE 进行预训练，然后丢弃解码器，通过优化以下目标进行微调：

　　　　L=KL(P‖Q)=∑i∑jpijlogpijqij(2)

　　其中：

• • qij 是表示  zi  和聚类中心  μj  之间的相似度。定义为：

　　　　　　qij=(1+‖zi−μj‖2)−1∑j(1+‖zi−μj‖2)−1(3)

• • Eq.2 中的 pij  是目标分布，定义为：

　　　　　　pij=q2ij/∑iqij∑j(q2ij/∑iqij)(4)

　　DEC算法：

• • 首先，对原始数据集  X ，跑一遍 AE ，获得 Encoder 生成的表示  zi=fW(xi) ；
  • 其次，基于  zi ，使用传统的  k−means ，获得若干聚类中心 μj；
  • 然后，根据 Eq.3 和 Eq.4 计算得的  qij  和  pij  去计算  Eq.2 中的 L；
  • 最后，根据  qij  进行  label  分配。

3 Improved Deep Embedded Clustering

　　本文 model 有两个必不可少的部分：

• • Autoencoder；
  • clustering loss；

　　模型架构如 Fig.1. 所示：

　　

　　目标函数定义为：

　　　　L=Lr+γLc(6)

　　其中：

• • Lr  是重构损失；
  • Lc  是聚类损失；
  • γ>0  是控制 the degree of distorting embedded space 的系数，当  γ=1  或  Lr≡0  即是DEC的目标函数；

3.1 Clustering loss and Initialization

　　回顾 DEC 聚类损失函数（参考前面提到的 Eq.2. 、Eq.3.、Eq.4.）：

　　　　Lc=KL(P‖Q)=∑i∑jpijlogpijqij(7)

　　通过 DEC model  给的启发：

• • 预训练：使用堆叠降噪自编码器（stacked denoising autoencoder）。
  • 然后基于预训练生成的有效表示  {zi=fW(xi)}ni=1  使用  k−means 获得聚类中心  {μj}Kj=1 。     

3.2 Local structure preservation

　　由于 DEC 直接丢弃 Decoder 并通过聚类损失 Lc  直接微调编码器，可能造成嵌入空间的扭曲。[ 说白了就是研究  Decoder 的影响 ]

　　所以本文提出保持解码器不变，直接将聚类损失加到嵌入空间中去。

 　　本文将堆叠降噪自编码器替换为欠完备自编码器，重构损失  [  Mean Squared Error ]  ：

　　　　Lr=n∑i=1‖xi−gW′(zi)‖22(8)

3.3 Optimization

　　Eq.6 采用小批量随机梯度下降法优化，有三个参数需要优化，分别是：

1. 1. 自编码器的权重参数
   2. 聚类中心  uj 
   3. 目标分布  P

　　首先阐述：更新自编码器权重参数和聚类中心
　　固定目标分布 P ，优化

　　　　∂Lc∂zi=2K∑j=1(1+‖zi−μj‖2)−1(pij−qij)(zi−μj)(9)

　　　　∂Lc∂μj=2n∑i=1(1+‖zi−μj‖2)−1(qij−pij)(zi−μj)(10)

　　然后根据上式可以计算出：

• • 聚类中心更新公式：

　　　　　　μj=μj−λmm∑i=1∂Lc∂μj(11)

• • 解码器权重参数更新公式：

　　　　　　W′=W′−λmm∑i=1∂Lr∂W′(12)

• 编码器权重更新公式为：

　　　　　　W=W−λmm∑i=1(∂Lr∂W+γ∂Lc∂W)(13) $

　　然后阐述：更新目标分布

　　由于目标分布  P  是基于 soft label [ pij 依托于 qij ]  ，频繁更新容易造成不稳定，所以  P  的更新并没有在每个  iter  中更新，而是在每个  batch  中更新。但是实际上，本文是在 每  T iterations  进行更新。label 分配方法如下：

　　　　si=argmaxjqij(14)

　　这里当连续两次分配的百分比小于 δ  将停止训练。

　　整个算法被总结在算法1中。

　　

　　IDEC 的算法复杂度为  O(nD2+ndK)  ，其中 D、d、K  分别为隐层中神经元的最大数量、嵌入层的维数和 cluster 的数量。通常  K≤d≤D  ，所以时间复杂度可以简化为  O(nD2) 。

4 Experiments

数据集

• MNIST [图像数据集]：70000张手写数字图
• USPS [图像数据集]：9298张灰度手写数字图
• REUTERS-10K [文本数据集]：810000篇有标签新闻报道，这边采样10000篇报道。

　　

聚类结果

　　实验1：实验结果如  Table 2  所示：

　　

　　结论：

• • 深度聚类方法： AE+k-means, DEC和 IDEC 表现明显优于传统方法，但这三种方法之间仍存在很大的差距。
  •  AE+k-means 和 DEC 相比证明了聚类损失的指导意义，DEC 和 IDEC 相比证明了自编码器可以提高聚类性能。

　　实验2：DEC 和 IDEC 对比实验：

　　

　　结论：

• • IDEC 聚类精度高于 DEC ;
  • IDEC 收敛慢于 DEC ;
  • IDEC 聚类损失高于 DEC ;
  • 最后几次迭代重构损失和初始迭代损失相差不大；

　　实验3：DEC 和 IDEC 可视化对比实验：

　　

　　上下行分别是 IDEC 和  DEC  的  t-SNE 可视化结果。

　　实验4：DEC 和 IDEC 参数  λ 和  γ  的对比实验：

　　

　　结论：

• • IDEC在最佳学习率  λ=0.1  的情况下优于 DEC 在最佳学习率  λ=0.01 当  γ∈[0.05,1.0] ；
  • 对于较大的  λ  需要搭配较小的 λ ；

5 Conclusion

　　本文提出了改进的深度嵌入式聚类(IDEC)算法，该算法联合进行了聚类，并学习了适合于聚类的嵌入式特征，并保留了数据生成分布的局部结构。IDEC通过优化基于KL散度的聚类损失来操纵特征空间来散射数据。它通过合并一个自动编码器来维护局部结构。实验实验表明，结构保存对深度聚类算法至关重要，有利于聚类性能。未来的工作包括：在IDEC框架中添加更多的先验知识（如稀疏性），并为图像数据集合并卷积层。

 

修改历史

2022-02-13 创建文章
2022-06-09 修订文章

 

论文解读目录 

• 论文信息
• 1 Introduction
• 2 Related Work
•     2.1 Deep Clustering
•     2.2 Autoencoder
•     2.3 Deep Embedded Clustering
• 3 Improved Deep Embedded Clustering
•     3.1 Clustering loss and Initialization
•     3.2 Local structure preservation
•     3.3 Optimization
• 4 Experiments
• 5 Conclusion
• 修改历史

__EOF__