[文献阅读] Unsupervised Deep Embedding for Clustering Analysis (无监督的深度嵌入式聚类)

Abstract:

This week I read Unsupervised Deep Embedding for Clustering Analysis .It discusses the concept of Unsupervised Deep Embedding for Clustering Analysis (DEC), a method that employs KL divergence for clustering loss to adjust a pre-trained neural network encoder. DEC is an approach that leverages deep neural networks to simultaneously learn feature representations and cluster assignments.

摘要

无监督的深度嵌入式聚类 Unsupervised Deep Embedding for Clustering Analysis http://arxiv.org/abs/1511.06335

k-means和高斯混合模型(GMM)是流行的聚类方法。但是它们的距离指标仅限于原始数据空间，并且在输入维度较高时它们往往会失效。

该论文首先提出将KL散度用于聚类损失，并使用这一损失调整一个预训练的神经网络编码器。称为深度嵌入聚类（DEC），这是一种使用深度神经网络同时学习特征表示和聚类分配的方法。为了使KL散度更好应用于聚类任务，文章创设性的设置了KL散度中两个分布，目标分布P和真实分布Q。DEC学习从数据空间到低维特征空间的映射，并在其中迭代优化聚类目标，解决了原始数据点高维而失效的问题。对图像和文本语料库的实验评估表明，与最先进的和传统的聚类方法，有了显著的改进。

聚类

聚类是机器学习中的一种无监督的分类方法，给定一组数据点，我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上，同一组中的数据点应该具有相似的属性和/或特征，而不同组中的数据点应该具有高度不同的属性和/或特征，依据此分类。常见的聚类算法比如K-means，高斯混合模型(GMM)。

深度聚类

引入了深度学习的聚类叫深度聚类。通过神经网络的特征学习或者非线性映射，替代传统的手工特征提取器，学习到更高质量的特征。深度聚类算法大都由聚类损失与网络损失两部分构成，高质量的特征有助于提升聚类效果，聚类结果可以引导神经网络学习更好的特征。

KL散度

kmeans和高斯混合模型(GMM)是流行的聚类方法的一个分支。这些方法快速且适用于各种各样的问题。但是，它们的距离指标仅限于原始数据空间，并且在输入维度较高时它们往往会失效。

KL散度（Kullback-Leibler divergence），可以以称作相对熵（relative entropy）或信息散度（information divergence）。KL散度的理论意义在于度量两个概率分布之间的差异程度，当KL散度越大的时候，说明两者的差异程度越大；而当KL散度小的时候，则说明两者的差异程度小。如果两者相同的话，则该KL散度应该为0。

离散的情况下用q(x)去近似p(x)的KL散度的公式（对于聚类问题，我们往往只会关心离散的情况）:
$$KL(P||Q)=\sum p(x)\frac{p(x)}{q(x)}$$
对上面的式子进行展开：

最后得到的第一项称作P和Q的交叉熵（cross entropy），后面一项就是P的自身交叉熵。

H§代表着基于P分布自身的编码长度，也就是最优的编码长度（最小字节数）。而H(P,Q)则代表着用Q的分布去近似P 分布的信息，自然需要更多的编码长度。并且两个分布差异越大，需要的编码长度越大。所以两个值相减是大于等于0的一个值，代表冗余的编码长度，也就是两个分布差异的程度。

公式上可以看出，KL散度具有非对称性，也就是说，分布P到分布Q的KL散度，并不一定等于分布Q到分布P的KL散度。

深度嵌入式聚类(DEC)

聚类问题的数学描述：
考虑将n个点$x_i\in X,n_i=1$的集合聚类为k个类的问题，每个聚类由质心${\mu }_j$表示，$j=1,...,k$。

首先使用非线性映射$f_{\theta }$：X→Z变换数据，而不是直接在数据空间X中进行聚类，其中θ是可学习的参数，Z是潜在特征空间。 Z的维度通常比X小得多，以避免“维度的诅咒”。为了对fθ进行参数化，深层神经网络(DNN)由于其理论函数逼近特性和已证明的特征学习能力而成为最好的选择。

DEC算法通过同时学习特征空间Z中的k个聚类中心 { μ j ∈ Z } k j = 1 k \{{μ_j\in Z}\}^k_{k_j = 1} {μj​∈Z}kj​=1k​和将数据点映射到Z的神经网络参数θ来对数据进行聚类。DEC有两个阶段：

1. 非线性映射f_θ：X→Z，使用深度自动编码器进行参数初始化。
2. KL聚类，其中我们在计算辅助目标分布与最小化KL散度之间进行迭代。

KL散度聚类

给定非线性映射$f_{\theta }$的初始估计值和初始聚类质心 { μ j ∈ Z } k j = 1 k \{{μ_j\in Z}\}^k_{k_j = 1} {μj​∈Z}kj​=1k​，使用在两步之间交替的无监督算法来改善聚类。在第一步中，我们计算嵌入点和聚类质心之间的软分配概率， 第二步，我们通过使用辅助目标分布，从当前的高置信度分配中，学习来更新映射f(θ)的参数，并更新聚类质心。重复该过程，直到满足收敛标准（数据点与其对应的质心不再改变）为止。

软分配（soft assignment）

软分配不同于硬分配，硬分配只给每个数据点分配到一个质心，软分配为每个数据点给出它分配到每个质心的概率。

通过**软分配（soft assignment）**策略，将每个数据点分配到每个聚类的概率分布上，而不是硬分配到一个聚类。这种策略可以更好地处理数据点的边界情况和噪声，提高聚类的鲁棒性和准确性。

使用t分布（student学生分布）作为概率分布，来衡量嵌入点$z_i$和质心${\mu }_j$之间的相似性：

其中$z_i=f_{\theta }(x_i)\in Z$对应于嵌入后的xi∈X，其中α是t分布的自由度，而$q_{ij}$可解释为将样本$z_i$分配给聚类j的概率(即软分配)。由于我们无法在无监督的环境中对验证集上的α进行交叉验证，因此对于所有实验，我们使α= 1。

为什么使用t-分布？

使用t-分布这一灵感来自t-SNE可视化算法。t-分布是一种长尾分布，与正态分布相比之下，t分布的尾部较高，对异常点不敏感，保证了其鲁棒性，因此其拟合结果更为合理，较好的捕获了数据的整体特征。

KL散度损失

我们希望通过最小化将软分配与目标分布之间的损失来训练我们的模型。为此，我们将目标损失定义为软分配$q_{ij}$和辅助分布$p_{ij}$之间的KL散度损失，如下所示：

从KL散度公式看，分布Q就是软分配使用的t分布，而目标分布P则需要自行拟定，来表示通过迭代质心的移动，使得真实分布Q朝着什么样的方向前进。

目标分布P的选择对于DEC的性能至关重要。

我们希望目标分布P具有以下属性：

• (1)预测效果好(即提高簇纯度)
• (2)更加重视具有高置信度的数据点
• (3)归一化每个损失的贡献重心以防止大型簇扭曲隐藏的特征空间。

文章的实验中，通过先将$q_{ij}$升至第二次幂，然后通过每个聚类（簇）的频率进行归一化来计算$p_{ij}$：

其中$f_j={\sum }_i{q}_{ij}$ 。意义是软分配情况下的簇频率。

训练

使用具有动量的随机梯度下降（SGD）来优化参数。

编码器的初始化

文中的解码-编码器实际就是一个预训练好的泛用的嵌入模型，它能很好的将自然语言通过语义映射到高维空间。

经过逐层训练之后，我们以反向逐层训练的顺序将所有编码器层与所有解码器层连接起来，形成一个深层的自动编码器，然后对其微调以最小化重建损失。最终结果是多层深层自动编码器，中间有一个瓶颈编码层。然后我们丢弃解码器层，并将编码器层用作数据空间和特征空间之间的初始映射。

聚类中心的初始化

为了初始化聚类中心，我们通过初始化的DNN（就是上面的编码器）传递数据以获取嵌入的数据点，然后在特征空间Z中执行标准k-means聚类以获得k个初始质心 { μ j ∈ Z } k j = 1 k \{{μ_j\in Z}\}^k_{k_j = 1} {μj​∈Z}kj​=1k​。

实验评估

我们在一个文本数据集和两个图像数据集上评估了所提出的方法(DEC)，并将其与其他算法(包括k-means，LDGMI和SEC)进行了比较。 LDGMI和SEC是基于谱聚类的算法，使用拉普拉斯矩阵和各种变换来提高聚类性能。我们展示了定性和定量结果，这些结果证明了DEC与LDGMI和SEC相比的优势。

为了研究不同算法的性能和通用性，我们对两个图像数据集和一个文本数据集进行了实验：

•MNIST：MNIST数据集由280000像素大小的70000个手写数字组成。这些数字居中并进行尺寸归一化。

•STL-10：96 x 96彩色图像的数据集。有10个类别，每个类别有1300个样本。它还包含100000张相同分辨率的无标签图像(Coates等，2011)。

•REUTERS：REUTERS包含大约810000个以类别树标签的英语新闻报道。我们使用了四个根类别：公司/工业，政府/社会，市场和经济学作为标签，并进一步修剪了由多个根类别标签的所有文档以得到685071个文章。

总结

无监督的深度嵌入式聚类 Unsupervised Deep Embedding for Clustering Analysis

文章在无监督聚类问题上，首先将KL散度引入，并提出深度嵌入式聚类(DEC)。

KL散度是一种描述分布之间差异的函数，这对于离散数据点聚类问题具有很好的描述性。并通过KL散度作为损失，通过再训练的方式，使得预训练的深层神经网络编码器调整成同时学习特征表示和聚类分配的网络。在网络的迭代映射和聚类收敛后，每个数据点将被分配到唯一的质心，完成聚类。

DEC的创设性不仅在于引入了KL散度，同样在于KL散度中两个分布的设置，目标分布P和真实分布Q。软分配中真实分布Q设置为t-分布，目标分布P则通过归一化的真实分布的二次幂计算。

正是这些性质使得DEC在聚类的鲁棒性和准确性都有更好的效果。