title：《 deep embedded clustering with local structure preservation》
authors：xifeng guo, long gao, xinwang liu, jianping yin
sources：2017, ijcai
other：69 citations, 71 references
paper：download
code：download
本文解决的问题：先前根据不同情况设计聚类损失函数的工作可能破坏了特征空间，产生无意义的特征表示从而降低了聚类性能。
本文解决的思路：
使用聚类损失函数指导代表特征空间的 points 分布；
采用 under-complete autoencoder 维护数据的局部结构；
联合 聚类损失 和 ae 损失 来训练。
idec 既可以很好的实现聚类任务，还可以学到能保持局部结构的表示（representation）。
聚类任务的划时代杰作：
1967 macqueen 的 k-means ；
2006 bishop 的 gaussian mixture model ；
2007 von luxburg 的 spectral clustering ；
由于输入数据的维度很大，通常会有很多不可靠的特征数据，这严重影响力聚类效果。所以一个被普遍接受的想法是：将高维空间的输入数据映射到低维空间，然后再进行聚类。
q1：为什么传统降维方法如 pca 、lda等学习表示的能力有限？
a1：知道的可以再评论区抒发见解。
由于深度学习的发展，dnn model 能很好的实现 feature transformation ，学到有用的表示。
然后介绍 dec ，可以参考《论文解读（dec）unsupervised deep embedding for clustering analysis》。
本文贡献：
提出了一种深度聚类算法，可以联合进行聚类和学习具有局部结构保存的代表性特征。
通过实证证明了局部结构保存在深度聚类中的重要性。
idec 在很大的优势上优于最新的对手。
2.1 deep clustering
目前阶段的聚类算法：
- two-stage work that applies clustering after having learned a representation；[ 该方法基于良好的表示 ]
approaches that jointly optimize the feature learning and clustering；[ 特征学习的时候同时进行聚类 ]
对于 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=f_{w}(x)$ ，输出表示 $z$ 。
$z=f_{w}(x)$
decoder：解码器函数为 $x^{\prime}=g_{w^{\prime}}(z) $，根据表示 $z$ 重构原始输入 $x$ 。
$x^{\prime}=g_{w^{\prime}}(z)$
两种常见的自编码器：
欠完备自编码器（ under-complete autoencoder）：$z$ 的维度要小于原始输入的维度。
去噪自编码器（ denoising autoencoder）：$l=\left\|x-g_{w^{\prime}}\left(f_{w}(\tilde{x})\right)\right\|_{2}^{2} \quad \quad \quad (1)$
reference：
- 欠完备自编码器：从自编码器获得有用特征的一种方法是限制 $h$ 的维度比 $x$ 小，这种编码维度小于输入维度的自编码器称为欠完备（undercomplete）自编码器。学习欠完备的表示将强制自编码器捕捉训练数据中最显著的特征。
去噪自编码器（denoising autoencoder，dae）是一类接受损坏数据作为输入，并训练来预测原始未被损坏数据作为输入的自编码器。
2.3 deep embedded clustering
深度嵌入式聚类(dec) [xieetal.，2016] 首先对自动编码器进行预训练，然后删除解码器。其余的编码器通过优化以下目标进行微调：
$l=k l(p \| q)=\sum\limits_{i} \sum\limits_{j} p_{i j} \log \frac{p_{i j}}{q_{i j}}\quad \quad \quad (2)$
其中：
$q_{i j}$ 是表示 $z_{i}$ 和聚类中心 $\mu_{j}$ 之间的相似度。定义为：
${\large q_{i j}=\frac{\left(1 \left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}}{\sum_{j}\left(1 \left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}}}\quad \quad \quad (3) $
eq.2 中的 $p_{ij}$ 是目标分布，定义为：
${\large p_{i j}=\frac{q_{i j}^{2} / \sum_{i} q_{i j}}{\sum_{j}\left(q_{i j}^{2} / \sum_{i} q_{i j}\right)}}\quad \quad\quad(4) $
dec算法：
首先，对原始数据集 $x$ ，跑一遍 ae ，获得 encoder 生成的表示 $z_{i}=f_{w}\left(x_{i}\right)$ ；
其次，基于 ${z_i}$ ，使用传统的 $k-means$ ，获得若干聚类中心 ${\mu _j}$；
然后，根据 eq.3 和 eq.4 计算得的 $q_{ij}$ 和 $p_{ij}$ 去计算 eq.2 中的 $l$；
最后，根据 $q_{ij}$ 进行 $label$ 分配。
consider a dataset $x$ with $n$ samples and each sample $x_{i} \in \mathbb{r}^{d}$ where $d$ is the dimension.
the number of clusters $k$ is a priori knowledge and the $j$ th cluster center is represented by $\mu_{j} \in \mathbb{r}^{d}$ . let the value of $s_{i} \in\{1,2, \ldots, k\}$ represent the cluster index assigned to sample $x_{i}$ .
define nonlinear mapping $f_{w}: x_{i} \rightarrow z_{i}$ and $g_{w^{\prime}}: z_{i} \rightarrow x_{i}^{\prime}$ where $z_{i}$ is the embedded point of $x_{i}$ in the low dimensional feature space and $x_{i}^{\prime}$ is the reconstructed sample for $x_{i}$ .
目标：寻找最佳的 $f_{w}$ 来获得更好的 $\left\{z_{i}\right\}_{i=1}^{n}$ ，以便更好的做聚类任务。
本文 model 有两个必不可少的部分：
autoencoder；
clustering loss；
模型架构如 fig.1. 所示：
目标函数定义为：
$l=l_{r} \gamma l_{c}\quad\quad \quad (6)$
其中：
$l_{r} $ 是重构损失；
$l_{c}$ 是聚类损失；
$ \gamma>0$ 是控制 the degree of distorting embedded space 的系数，当 $\gamma=1$ 或 $l_{r} \equiv 0$ 即是dec的目标函数；
q2：$ \gamma$ 这个系数为什么这么加，看过很多文章这么写，但是不知道为什么一定加这？
a2：知道的可以再评论区抒发见解。
3.1 clustering loss and initialization
回顾 dec 聚类损失函数（参考前面提到的 eq.2. 、eq.3.、eq.4.）：
$l_{c}=k l(p \| q)=\sum\limits_{i} \sum\limits _{j} p_{i j} \log \frac{p_{i j}}{q_{i j}}\quad\quad \quad (7)$
通过 dec model 给的启发：
预训练：使用堆叠降噪自编码器（stacked denoising autoencoder）。
然后基于预训练生成的有效表示 $\left\{z_{i}=f_{w}\left(x_{i}\right)\right\}_{i=1}^{n}$ 使用 $k-means $ 获得聚类中心 $\left\{\mu_{j}\right\}_{j=1}^{k}$ 。
3.2 local structure preservation
由于 dec 直接丢弃 decoder 并通过聚类损失 $l_{c}$ 直接微调编码器，可能造成嵌入空间的扭曲。[ 说白了就是研究 decoder 的影响 ]
所以本文提出保持解码器不变，直接将聚类损失加到嵌入空间中去。
本文将堆叠降噪自编码器替换为欠完备自编码器 [ 理由是聚类需要干净的数据，个人感觉就是那个实验效果好选那个 ]，重构损失 [ mean squared error ] ：
$l_{r}=\sum\limits _{i=1}^{n}\left\|x_{i}-g_{w^{\prime}}\left(z_{i}\right)\right\|_{2}^{2}\quad \quad \quad (8)$
这里建议 $ \gamma$ 最好小于 $1$ ，这将在在 4.3 节通过实验证明。
3.3 optimization
eq.6 采用小批量随机梯度下降法优化，有三个参数需要优化，分别是：
- 自编码器的权重参数
聚类中心 $u_j$
目标分布 $p$
首先阐述：更新自编码器权重参数和聚类中心
固定目标分布 $p$ ，优化
$\frac{\partial l_{c}}{\partial z_{i}}=2 \sum\limits _{j=1}^{k}\left(1 \left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}\left(p_{i j}-q_{i j}\right)\left(z_{i}-\mu_{j}\right)\quad\quad\quad (9)$
$\frac{\partial l_{c}}{\partial \mu_{j}}=2 \sum\limits _{i=1}^{n}\left(1 \left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}\left(q_{i j}-p_{i j}\right)\left(z_{i}-\mu_{j}\right)\quad\quad\quad (10)$
然后根据上式可以计算出：
聚类中心更新公式：
$\mu_{j}=\mu_{j}-\frac{\lambda}{m} \sum\limits _{i=1}^{m} \frac{\partial l_{c}}{\partial \mu_{j}}\quad \quad \quad (11)$
解码器权重参数更新公式：
${\large w^{\prime}=w^{\prime}-\frac{\lambda}{m} \sum\limits _{i=1}^{m} \frac{\partial l_{r}}{\partial w^{\prime}}} \quad\quad\quad(12)$
编码器权重更新公式为：
${\large w=w-\frac{\lambda}{m} \sum\limits _{i=1}^{m}\left(\frac{\partial l_{r}}{\partial w} \gamma \frac{\partial l_{c}}{\partial w}\right)}\quad \quad \quad (13)$ $
然后阐述：更新目标分布
由于目标分布 $p$ 是基于 soft label [ $p_{ij}$ 依托于 $q_{ij}$ ] ，频繁更新容易造成不稳定，所以 $p$ 的更新并没有在每个 iter 中更新，而是在每个 batch 中更新。但是实际上，本文是在 每 t iterations 进行更新。label 分配方法如下：
$s_{i}=\arg \; \underset{j}{max}\; \; q_{i j}\quad \quad \quad (14)$
这里当连续两次分配的百分比小于 $\delta$ 将停止训练。
整个算法被总结在算法1中。
idec 的算法复杂度为 $o\left(n d^{2} n d k\right)$ ，其中 $d$、$d$、$k$ 分别为隐层中神经元的最大数量、嵌入层的维数和 cluster 的数量。通常 $ k \leq d \leq d$ ，所以时间复杂度可以简化为 $o\left(n d^{2}\right)$ 。
4.1 datasets
mnist [图像数据集]：70000张手写数字图
usps [图像数据集]：9298张灰度手写数字图
reuters-10k [文本数据集]：810000篇有标签新闻报道，这边采样10000篇报道。
4.2 results
实验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 参数 $\lambda$ 和 $ \gamma$ 的对比实验：
结论：
idec在最佳学习率 $\lambda=0.1$ 的情况下优于 dec 在最佳学习率 $\lambda=0.01$ 当 $ \gamma \in [0.05,1.0]$ ；
对于较大的 $\lambda$ 需要搭配较小的 $\lambda$ ；
本文提出了改进的深度嵌入式聚类(idec)算法，该算法联合进行了聚类，并学习了适合于聚类的嵌入式特征，并保留了数据生成分布的局部结构。idec通过优化基于kl散度的聚类损失来操纵特征空间来散射数据。它通过合并一个自动编码器来维护局部结构。实验实验表明，结构保存对深度聚类算法至关重要，有利于聚类性能。未来的工作包括：在idec框架中添加更多的先验知识（如稀疏性），并为图像数据集合并卷积层。
last modify ：2022-02-13 17:54:31
『总结不易，加个关注呗！』
