用于聚类分析的无监督深度嵌入

摘要

群集对于许多数据驱动的应用领域至关重要，并且已经在距离函数和分组算法方面被广泛研究。相对较少的工作集中在学习表示的聚类上。在本文中，我们提出了深度嵌入式群集（DEC），这是一种使用深度神经网络同时学习特征表示和群集分配的方法。 DEC学习了从数据空间到低维特征空间的映射，在其中它迭代地优化了聚类目标。我们对图像和文本语料库的实验评估表明，与最新方法相比，该方法有显着改进。

1.介绍

聚类是一种重要的数据分析和可视化工具，已从不同角度在无监督的机器学习中进行了广泛的研究：聚类的定义是什么？什么是正确的距离指标？如何有效地将实例分组到群集中？如何验证集群？等等。文献中已经探索了许多不同的距离函数和嵌入方法。相对较少的工作集中在执行聚类的特征空间的无监督学习上。

距离或相异性的概念对于数据聚类算法至关重要。距离又取决于在特征空间中表示数据。例如，k均值聚类算法（MacQueen等，1967）使用给定特征空间中点之间的欧几里得距离，对于图像来说，该距离可能是原始像素或梯度-方向直方图。功能空间的选择通常留作最终用户确定的特定于应用程序的细节。但是很明显，特征空间的选择至关重要。对于除最简单的图像数据集以外的所有图像，在原始像素上使用欧几里得距离进行聚类是完全无效的。在本文中，我们将重新审视聚类分析并提出一个问题：我们是否可以使用数据驱动的方法来共同解决特征空间和聚类成员关系？

我们从计算机深度学习的最新工作中汲取了灵感（Krizhevsky等人，2012; Girshick等人，2014; Zeiler＆Fergus，2014; Long等人，2014），其中基准任务的明显收益来自学习更好的特征。但是，这些改进是通过有监督的学习获得的，而我们的目标是无监督的数据聚类。为此，我们定义了从数据空间X到低维特征空间Z的参数化非线性映射，在此我们优化了聚类目标。与先前在数据空间或在浅层线性嵌入式空间上工作不同，我们通过对聚类目标进行反向传播使用随机梯度下降（SGD）来学习映射，该映射由深度神经网络进行参数化。我们将此群集算法称为“深度嵌入式聚类”或DEC。

优化DEC具有挑战性。我们要同时解决集群分配和基础特征表示。但是，与监督学习不同，我们无法使用标记数据来训练我们的深度网络。相反，我们建议使用从当前软集群分配派生的辅助目标分布来迭代地优化集群。该过程逐渐改善了聚类以及特征表示。

我们的实验表明，在图像和文本数据集的准确性和运行时间方面，都比最新的聚类方法有了显着改进。我们对MNIST（LeCun等，1998），STL（Coates等，2011）和REUTERS（Lewis等，2004年）在DEC上做了评估，将其与标准和最新的聚类方法进行了比较（Nie等，2011；Yang等，2010）。此外，我们的实验表明，与最新方法相比，DEC对超参数的选择不那么敏感。这种鲁棒性是我们的聚类算法的重要属性，因为当将其应用于实际数据时，监督不适用于超参数交叉验证。我们的贡献是：（a）联合优化深度嵌入和聚类； （b）通过软分配进行新颖的迭代改进； （c）就聚类准确性和速度而言，最新的聚类结果。我们基于DEC的基于Caffe（Jia等人，2014）的实现可从https://github.com/piiswrong/dec获得。

2.相关工作

聚类已经在机器学习中对特征选择（Boutsidis等，2009; Liu＆Y u，2005; Alelyani等，2013），距离函数（Xing等，2002; Xiang等。 （2008年），分组方法（MacQueen等，1967年； V在Luxburg，2007年； Li等人，2004年）和聚类验证（Halkidi等人，2001年）等方面被广泛的研究。篇幅不允许进行全面的文献研究，我们将读者引向（Aggarwal＆Reddy，2013）进行调查。

kmeans（MacQueen et al，1967）和高斯混合模型（GMM）（Bishop，2006）是流行的聚类方法的一个分支。这些方法快速且适用于各种各样的问题。但是，它们的距离指标仅限于原始数据空间，并且在输入维数较高时它们往往无效（Steinbach等人，2004）。几种k均值的变体已经被提出来解决高维输入空间的问题。 De la Torre＆Kanade（2006）;叶等。 （2008年）执行联合降维和聚类，方法是先将数据与k均值聚类，然后将数据投影到较低的维中，从而使聚类间的方差最大化。在EM算法的迭代中重复此过程，直到收敛为止。但是，此框架仅限于线性嵌入。我们的方法采用深度神经网络来执行非线性嵌入，这对于更复杂的数据是必需的

谱聚类及其变体最近变得越来越流行（V on Luxburg，2007）。它们允许更灵活的距离度量，并且通常比kmeans表现更好。Yang等人已经探索了结合谱聚类和嵌入。（2010）；Nie等，（2011）田等，（2014年）提出了一种基于频谱聚类的算法，但用深度自动编码器代替了特征值分解，从而提高了性能，但进一步增加了内存消耗。

大多数谱聚类算法需要计算完整的图拉普拉斯矩阵，因此在数据点数量上具有二次或超级二次复杂度。这意味着他们需要具有大内存的专用机器来存储大于几万个点的任何数据集。为了将频谱聚类扩展到大型数据集，发明了近似算法来权衡性能与速度（Yan等，2009）。但是，我们的方法在数据点数量上是线性的，并且可以适当地扩展到大型数据集。

最小化数据分布和嵌入式分布之间的Kullback-Leibler（KL）差异已用于数据可视化和降维（van der Maaten＆Hinton，2008）。例如，T-SNE是该学校的非参数算法，而t-SNE的参数变体（van der Maaten，2009）使用深度神经网络对嵌入进行参数化。 t-SNE的复杂度为O（n²），其中n是数据点的数量，但可以用O（nlogn）近似（van Der Maaten，2014）。

我们从参数化t-SNE中获得启发。与其最小化KL散度以产生忠实于原始数据空间中距离的嵌入，不如定义基于质心的概率分布并将其KL散度最小化为辅助目标分布以同时改善聚类分配和特征表示。基于质心的方法还具有将复杂度降低到O（nk）的优点，其中k是质心的数量。

3.深度嵌入聚类

考虑以下问题：将一组n个点{xiisin;X} n i = 1聚类为k个聚类，每个聚类由质心micro;j， j = 1，hellip; ，k表示。我们建议首先使用非线性映射ftheta;：X→Z，变换数据：而不是直接在数据空间X中进行聚类，其中theta;是可学习的参数，Z是潜在特征空间。 Z的维数通常比X小得多，以避免“维度的诅咒”（Bellman，1961）。为了参数化ftheta;，深层神经网络（DNN）由于其理论函数近似特性（Hornik，1991）和已证明的特征学习能力（Bengio 等，2013）而成为自然的选择。

所提出的算法（DEC）通过同时学习特征空间Z中的k个聚类中心{mu;jisin;Z} kj = 1以及将数据点映射到Z的DNN参数theta;来对数据进行聚类。DEC有两个阶段：（1 ）使用深度自动编码器进行参数初始化（Vincent等，2010）和（2）参数优化（即聚类），在此过程中，我们在计算辅助目标分布和最小化Kullback-Leibler（KL）差异之间进行迭代。我们从描述阶段（2）参数优化（聚类）开始，给定theta;的初始估计值且{micro;j} k j = 1。

3.1用KL散度来聚类

给定非线性映射ftheta;的初始估计和初始聚类质心{mu;j} k j = 1，我们建议使用在两个步骤之间交替的无监督算法来改善聚类。第一步，我们计算嵌入点和聚类质心之间的软分配。第二步，我们更新深度映射ftheta;并通过使用辅助目标分布从当前的高置信度分配中学习来优化聚类质心。重复该过程，直到满足收敛标准为止。

3.1.1 软分配

继van der Maaten amp; Hinton (2008)之后，我们使用学生t分布作为核来测量嵌入点z_i和质心mu;_j之间的相似度：

其中zi =ftheta;（xi）isin;Z对应于嵌入后的xiisin;X，其中alpha;是学生t分布的自由度，而qij可解释为将样本i分配给聚类j的概率（即软分配）。由于我们无法在无监督的环境中对验证集上的alpha;进行交叉验证，并且得知它是多余的（van der Maaten，2009），因此对于所有实验，我们让alpha;= 1。

3.1.2 KL散度最小化

我们建议在辅助目标分布的帮助下，通过从群集的高可信度分配中学习来迭代地优化群集。具体来说，通过将软分配与目标分布匹配来训练我们的模型。为此，我们将目标定义为软分配q_i和辅助分布p_i之间的KL散度损失：

目标分布P的选择对于DEC的性能至关重要。天真的方法是将每个p_i设置为高于置信度阈值的数据点的增量分布（到最接近的质心），而忽略其余部分。但是，由于q_i是软分配，因此使用较软的概率目标更加自然和灵活。具体来说，我们希望目标分布具有以下属性：（1）加强预测（即提高簇纯度），（2）更加注重以高置信度分配的数据点，（3）归一化每个损失的贡献重心，以防止大型簇扭曲隐藏的特征空间。

在我们的实验中，我们首先通过将qi提升至第二次方来计算p_i，然后按每个簇的频率归一化：

其中fj = Sigma;_iq_ij 软集群频率。有关L和P的经验特性的讨论，请参阅第5.1节。我们的培训策略可以看作是一种自我培训的形式（Nigam＆Ghani，2000）。与自训练中一样，我们采用初始分类器和未标记的数据集，然后使用分类器标记数据集，以便对其自身的高置信度预测进行训练。确实，在实验中，我们观察到DEC通过学习高置信度预测来提高每次迭代中的初始估计，从而有助于改善低置信度预测。

3.1.3 优化

我们使用具有动量的随机梯度下降（SGD）联合优化聚类中心{micro;j}和DNN参数theta;。关于每个数据点z_i和每个聚类质心micro;_j的特征空间嵌入的L梯度计算如下：

然后，梯度part;L/part;zi向下传递到DNN，并在标准反向传播中用于计算DNN的参数梯度part;L/part;theta;。为了发现聚类分配，当少于两次的点间更改聚类分配的点数少于总点数时，我们停止执行该过程。

3.2 参数初始化

到目前为止，我们已经讨论了在给定DNN参数theta;和簇质心{micro;j}的初始估计的情况下DEC如何进行。现在我们讨论如何初始化参数和质心。

我们使用堆叠式自动编码器（SAE）初始化DEC，因为最近的研究表明它们在真实数据集上始终产生语义上有意义且分隔良好的表示形式（Vincent等人，2010; Hinton＆Salakhutdinov，2006; Le，2013）。因此，SAE学习的无监督表示自然促进了DEC聚类表示的学习。

我们逐层初始化SAE网络，每层都是一个去噪自动编码器，经过训练以在随机损坏后重建前一层的输出(Vincent等人，2010年)。去噪自动编码器是一个两层神经网络，定义为

其中Dropout(·)（Srivastava等，2014）是随机映射，随机将其一部分输入维设置为0，g1和g2分别是用于编码和解码层的激活函数，并且theta;= {W1，b1，W2，b2}是模型参数。通过最小化最小平方损失||x-y||²₂来进行训练。训练完一层后，我们将其输出h作为输入来训练下一层。我们在所有编码器/解码器对中都使用整流线性单位（ReLU）（Nair＆Hinton，2010），除了第一对中的g2（它需要重建可能具有正值和负值的输入数据，例如零均值图像）和最后一对的g1（因此最终的数据嵌入保留了完整的信息（Vincent等，2010））。

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

为了初始化聚类中心，我们通过初始化的DNN传递数据以获取嵌入的数据点，然后在特征空间Z中执行标准k均值聚类以获得k个初始的质心{u_j}^k_j=1。

4. 实验

4.1 数据集

我们在一个文本数据集和两个图像数据集上评估了所提出的方法（DEC），并将其与其他算法（包括k均值，LDGMI（Yang等人，2010）和SEC（Nie等人，2011）进行了比较。 LDGMI和SEC是基于频谱聚类的算法，使用拉普拉斯矩阵和各种变换来改善聚类性能。扬等人报道了经验证据。 （2010）； Nie等。 （2011年）表明，LDMGI和SEC在许多数据集上均优于传统的谱聚类方法。我们显示了定性和定量结果，这些结果证明了DEC与LDGMI和SEC相比的优势。

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

·MNIST：MNIST数据集由70000个手写数字组成，像素大小为28 x 28。这些数字居中并进行尺寸规格化（LeCun等，1998）。

bull;STL-10：96 x 96彩色图像的数据集。有10个类别，每个类别有1300个示例。它还包含100000张相同分辨率的未标记图像（Coates等，2011）。训练自动编码器时，我们还使用了未标记的集合。与Doersch等类似。 （2012年），我们将HOG功能和一个8times;8的颜色图串联起来，用作所有算法的输入。

路透社：路透社包含大约810000个以类别树标记的英语新闻报道（

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[239215]，资料为PDF文档或Word文档，PDF文档可免费转换为Word