• 1 Intro
• 2 Related
  • 2.1 基于特定聚类损失的神经网络
  • 2.2 无监督预训练网络
  • 2.3 有监督预训练网络
  • 2.4 无预训练网络
• 3 JULE 算法原理
  • 3.1 循环结构
  • 3.2 层次聚类
  • 3.3 卷积特征提取网络
  • 3.4 训练过程
• 4 JULE 的实现
  • 4.1 其他用来对比的算法
  • 4.2 实验结果分析
• 5 引用与拓展阅读

1 Intro

这篇论文依旧是深度聚类，特征提取，用特征聚类。

2 Related

聚类算法可以按照聚类目标函数不同，分为基于划分、基于层次、基于密度等算法。然而在深度聚类的范畴内，用同样的方式将算法分类并不合适，因为并非所有深度聚类算法都采用联合的聚类损失。在本文中，我按照深度聚类算法的网络结构将其分为四类。

第一类深度聚类算法用自动编码器（Autoencoder，以下简称 AE）进行特征提取。自编码器通过编码器和解码器来拟合一个非线性映射。其中，编码器是要训练的特征转换映射，解码器要根据编码器生成的结果重构数据，并使之最接近原始数据。

第二类深度聚类算法通过特定的聚类损失训练前馈网络，将这种深度神经网络（Deep Neural Network，以下简称 DNN）称为聚类 DNN（Clustering Deep Neural Network，以下简称 CDNN），此类网络层数可能非常多。另外，在大规模数据集进行预训练，聚类表现将有大幅提升。

第三和第四类深度聚类算法分别基于变分自编码器（Variational Autoencoder，以下简称 VAE）和生成对抗网络（Generative Adversarial Network，以下简称 GAN），它们是最近流行的生成模型，不仅可以聚类，还可以从获得的聚类结果中生成新的样本。

上一篇文章 属于第一类，本篇文章的 JULE 属于第二类方法。

2.1 基于特定聚类损失的神经网络

基于 CDNN 的深度聚类只需要聚类损失来训练神经网络，其中神经网络的结构可以是全连接神经网络（Fully connected nerual networks，以下简称 FCN）、卷积神经网络（Convolutional neural networks，以下简称 CNN）、深度置信网络（Deep Belief Networks，以下简称 DBN）

基于 CDNN 的深度聚类算法的通用结构如下图所示。网络的正向传播用来提取特征，并进行聚类，反向传播用来微调特征表示。

由于损失函数不包含重建误差，因此很有可能得到平凡解：每个样本简单地被映射为“自成一簇”，这导致特征的提取毫无意义。因此，在设计聚类误差的时候，应考虑避免平凡解。对于神经网络来说，参数的初始化也非常重要，因此，基于 CDNN 的深度聚类可以按照参数的初始化方式分为三类：无监督预训练、有监督预训练、随机初始化（无预训练）。

2.2 无监督预训练网络

受限玻尔兹曼机（Restricted Boltzmann Machine，以下简称 RBM）和 AE 被广泛应用于基于 CDNN 的深度聚类的参数初始化。这些算法首先训练 RBM 或 AE，然后利用聚类损失微调网络。

DNC

DNC（Deep Nonparametric Clustering[2]）运用 DBN 进行特征提取。DNC 首先训练 DBN 将数据进行嵌入（embedding），然后运行非参数最大剩余聚类。得到聚类结果后，便利用聚类损失微调 DBN 的最后一层。

2.3 有监督预训练网络

尽管无监督预训练能一定程度上更好地初始化网络参数，然而这个初始化的参数和要提取的特征还是没太大关系。[3] 做了一系列实验，发现用传统的聚类方法把 CNN 在 ImageNet 数据集上提取的特征直接聚类，其表现可以超过当时的所有聚类方法。因此，自然会想到利用 CNN 进行特征的提取。

CCNN

CCNN（Clustering Convolutional Neural Network[4]）是基于 CNN 的深度聚类网络迭代地进行聚类和特征表示。CCNN 在 ImageNet 数据集上有一个预训练的特征提取网络。首先随机挑选 $k$ 各样本，用与训练好的 CNN 进行特征提取，并作为初始的簇的中心。接下来每个迭代周期内，首先运行小批量（mini-batch）k-means 算法，以更新簇的中心；然后用随机提取下降（Stochastic gradient descent，SGD）的方法，用最接近簇中心的样本标签，给 CNN 有监督优化。以此循环，直到规定的次数为止。

CCNN 有如下优点：

1. 小批量 k-means 算法使得 CCNN 可应用于大规模的数据集，这也是唯一一个可以用来聚类百万量级数据的算法。

2. CCNN 设计了一种新的更新网络参数的方式，即只用最接近簇中心的样本作为有监督学习的标签，这使得只有高置信度的标签才会对网络参数产生影响。

3. 我们知道，每次聚类得到的标签结果并非一一对应，因此为了用聚类标签监督特征提取网络，则需要利用匈牙利算法进行全排列，以得到最佳匹配。CCNN 更新簇中心的方式采用了 k-means 的方式，巧妙地避免了时间复杂度极高的全排列过程。

2.4 无预训练网络

尽管预训练对聚类性能有很大帮助，但是仍然有一些算法仅通过优化聚类损失进行训练。这些算法利用随机的方式初始化参数。

DAC

DAC（Deep Adaptive Image Clustering[5]）是基于 CNN 的深度聚类网络。DAC 认为，每个样本两两之间只可能是两种关系，即属于同一簇和不属于同一簇，DAC 中的深度网络就是用来识别两样本间的这种关系。在 DAC 中，样本间的相似度用 CNN 生成的特征间的余弦相似度计算。通过 l2 范数约束，学习到的特征向量更接近指示向量的 one-hot 形式，可以直接用来聚类。

3 JULE 算法原理

JULE（Joint Unsupervised Learning of Deep Representations and Image Clusters，[1]）是一个基于特定聚类损失的神经网络。算法的目标是在一个结构中，解决未标记图像的图像聚类和表示学习。利用图像的聚类结果作为监督信号来学习表示，而这些表示又将有利于图像聚类。

从整体来看，给出 $n_s$ 个未标注的图像数据 $I = \{I_1,I_2,···,I_{n_s}\}$ ，那么总体上，学习图像特征表示和聚类的目标函数可以被写为：

$$ \mathop{\arg\min}\limits_{y,\theta} L(y,\theta|I) $$

其中 $L(·)$ 为损失函数，$y$ 代表聚类结果，$\theta$ 代表特征表示的参数。如果我们将两个参数 $y,\theta$ 之一固定，那么优化过程将分解成两步交替：

$$
\mathop{\arg\min}\limits_{y,\theta} L(y|I,\theta)\tag{3.1}
$$

$$
\mathop{\arg\min}\limits_{y,\theta} L(\theta|I,y)\tag{3.2}
$$

公式 3.1 表示在特征空间中聚类的过程，公式 3.2 表示有监督特征表示的过程。JULE 算法即为在两部分中交替迭代的结构，给定当前的表示参数来更新聚类结果，给定当前的聚类结果来更新特征表示参数。具体来说，JULE 使用自底向上的层次聚类进行聚类，并通过卷积神经网络（CNN）来提取图像特征。

3.1 循环结构

本算法整体上分为 p 个阶段，每个阶段有正向传播和反向传播两个部分：利用正向传播进行层次聚类，利用反向传播进行特征提取。

两个部分用同一个优化问题表示，使两部分的目标函数一致，避免了分部带来的误差积累。

3.2 层次聚类

自底向上的层次聚类如图所示，每轮选择两簇进行合并。六边形的样本表示，要合并的两簇应尽量接近；鲜艳颜色的样本表示，合并后的两簇应与其邻居尽量远。

因此，为了实现上述的两个要求，JULE 利用出入度计算两簇 $C_a,C_b$ 之间的相似度：

$$
\mathcal{A}_{C_a,C_b} = \frac{1}{|C_a^2|}1^T_{|C_a|}W_{C_a,C_b}W_{C_b,C_a}1_{|C_a|} + \frac{1}{|C_b^2|}1^T_{|C_b|}W_{C_b,C_a}W_{C_a,C_b}1_{|C_b|}
$$

其中 $C_A,C_b$ 代表两簇；$1$ 为对应长度的列向量，其所有元素均为 1；$W \in R^{n_s \times n_s}$ 为相似度矩阵，$W$ 的元素 $w_{ij}$ 满足：

$$
w_{ij}=
\begin{cases}
exp(-\dfrac{||x_i-x_j||_2^2}{\sigma^2})& x_j \in \mathcal{N}_i^{K_s} \\
0& otherwise
\end{cases}
$$

其中 ${N}_i^{K_s}$ 表示样本 $x_i$ 最近的 $K_s$ 个邻居；$\sigma^2 = \frac{a}{n_sK_s}\sum_{x_i\in X}\sum_{x_j \in \mathcal{N}_i^{K_s}} \|x_i – x_j\|^2_2$。$a,K_s$ 均为提前给定的系数。

有了簇间的相似度，就可以表示层次聚类第 $t$ 轮的目标函数：

$$
L^t(y^t,\theta^t|y^{t-1},I) = – \mathcal{A}(C_i^t,\mathcal{N}_{C_i^t}^{K_c}[1]) – \frac{\lambda}{K_c – 1} \sum_{k=2}^{K_c}(\mathcal{A}(C_i^t,\mathcal{N}_{C_i^t}^{K_c}[1]) – \mathcal{A}(C_i^t,\mathcal{N}_{C_i^t}^{K_c}[k]))
$$

其中右上角角标 $^t$ 表示第 $t$ 次迭代的数据。尽管 $y^t,\theta^t,y^{t-1}$ 并没有显式地出现在式子中，但是它们通过决定聚类结果，以及类间相似度矩阵，决定了目标函数的值。

目标函数分为两项：前一项计算了簇 $C_i$ 和它最近邻居的相似度，保证合并的两簇最近；后一项计算了 $C_i$ 和它最近邻居的相似度与 $C_i$ 和它其他邻居的相似度之间的差，保证合并后的新簇与其邻居最远。最终保证聚类结果簇内紧密，簇间稀疏。

3.3 卷积特征提取网络

卷积特征提取网络的结构如图所示，其中输入的图像以 MNIST 为例。卷积层可以大幅减小参数量，同时有效地提取局部特征。

卷积特征提取的目标函数与层次聚类目标函数一致：
$$
L^t(y^t,\theta^t|y^{t-1},I) = – \mathcal{A}(C_i^t,\mathcal{N}_{C_i^t}^{K_c}[1]) – \frac{\lambda}{K_c – 1} \sum_{k=2}^{K_c}(\mathcal{A}(C_i^t,\mathcal{N}_{C_i^t}^{K_c}[1]) – \mathcal{A}(C_i^t,\mathcal{N}_{C_i^t}^{K_c}[k]))
$$
目标函数使得样本在特征空间中，与同簇样本距离最近，与不同簇样本距离最远。

3.4 训练过程

给出一个包含 $n_s$ 个样本的数据局，我们假设期望最终聚成 $n_c^*$ 个簇。那么算法整体就分为 $n_s – n_c^*$ 时隙。在算法开始时，我们用简单的聚类将样本分成初始的簇，这里采用了[6]中的聚类方法。得到初始的簇后，卷积特征提取网络根据这些标签学习初始参数。接下来便开始迭代的过程：

在正向传播中，每个时隙合并两个簇。在反向传播中，我们运行约 20 个 epoch 来更新 $\theta$，并且相似度矩阵 $W$ 也会根据新表示进行更新。 第 $p$ 个周期的持续时间为 $n_p = ceil(\eta \times n^s_c)$ 个时隙，其中 $n^s_c$ 是当前周期开始时的簇数，而 $\eta$ 是一个参数，用于控制时隙的数量。$\eta$ 越小，更新 $\theta$ 的频率越高。

4 JULE 的实现

实验中参数如下表所示：

超参数	$K_s$	$a$	$K_c$	$\lambda$	$\eta$
取值	20	1.0	5	1.0	0.9

卷积层中，卷积滤波器大小为 $5\times 5$，通道数为 50，步长为 1。在池化层中，采用最大池化，其中 kernel size 为 2，步长为 2。卷积特征提取网络中，得到特征向量之后，还会加一层全连接层，将特征空间的维度将至 160。然后通过 l2 正则层，最终用于计算损失函数。

在特征提取的学习过程中，初试学习率为 0.01，学习率随训练衰减（ inverse learning rate decay policy），其中 gamma = 0.0001，Power = 0.75。优化器使用 SGD。

4.1 其他用来对比的算法

对于其它算法，若有代码，我将他们的代码跑三次，取最优值；对于没有代码的算法，我直接摘抄论文中的性能数值。

4.2 实验结果分析

各算法最终聚类性能对比如下表所示。可以明显看出，DEC 与 JULE 两种算法性能最好。

算法	k-means	SC-NJW	SC-ST	SC-LS	Ncut	AC-Link	AC-Zell
NMI	0.528	0.755	0.756	0.756	0.753	0.662	0.768

算法	AC-GDL	AC-PIC	NMF-LP	NMF-D	TSC-D	DEC	JULE
NMI	0.844	0.853	0.467	0.243	0.651	0.853	0.951

训练过程中的聚类性能表现如下图所示。聚类性能总体上随着学习不断提升。

训练过程中的损失函数变化如下图所示。损失函数均能快速收敛。

由于 JULE 采用的是自底向上的层次聚类，故中间聚类结果可视化如图所示。为了方便在二维分清类别，故只选取数字为 0，1，2，7 的四类手写数字画出在二维平面的分布。

5 引用与拓展阅读

[1] Yang J, Parikh D, Batra D. Joint Unsupervised Learning of Deep Representations and Image Clusters. 2016.

[2] ChenG. Deep Learning with Nonparametric Clustering. 2015.

[3] GuérinJ, GibaruO, ThierySetal. CNN features are also great at unsupervised classification. 2017.

[4] Hsu C, Lin C. CNN-Based Joint Clustering and Representation Learning with Feature Drift Compen- sation for Large-Scale Image Data [J]. IEEE Transactions on Multimedia, 2018, 20 (2): 421–429.

[5] Chang J, Wang L, Meng G et al. Deep Adaptive Image Clustering [J], 2017: 5880–5888.

[6] ZhangW, ZhaoD, WangX. Agglomerative clustering via maximum incremental pathintegral[J]. Pat- tern Recognition, 2013, 46 (11): 3056–3065.

[mathjax]