【速览】SPL | DWSC：深度加权K子空间聚类

学会“成果速览”系列文章旨在将学会会员最新代表性成果进行传播，通过短篇文章让读者用母语快速了解相关学术动态，欢迎关注和投稿~

◆ ◆ ◆ ◆

深度加权K子空间聚类

黄伟填、尹明*、李建中、谢胜利

IEEE Signal Processing Letters

撰稿人：尹明

推荐理事：林宙辰

◆ ◆ ◆ ◆

背景介绍

聚类是无监督学习的一个基础性任务，也是多种应用领域的关键技术，例如，用户画像、推荐系统、数据分析等。聚类通过度量计算样本之间的相似性，将样本进行分簇。传统的聚类方法，例如K-means、高斯混合模型 (GMM) 和谱聚类 (Spectral Clustering)，有着广泛的研究并且在不断地改善聚类性能，但是，这些方法不能很好处理大规模、高维数据。近年来，随着深度神经网络在监督学习上取得巨大成就，一些研究也开始将神经网络与聚类算法进行结合，我们统称为深度聚类算法 (Deep Clustering)。利用神经网络的好处就是可以对数据进行批量处理，提取深层非线性特征，从而提高处理大规模、高维数据聚类的性能。自动编码器 (AutoEncoder, AE)，变分自动编码器 (Variational AutoEncoder, VAE) 和卷积编码器 (Convolutional AutoEncoder, CAE) 被广泛应用于深度聚类中。一方面自动编码器将输入映射到低维的特征空间中，再通过解码器进行重构，另一方面对低维特征进行聚类。深度聚类的架构通常可以表示为 [1] ：

图1.一般的深度聚类网络结构

目标函数由两部分组成，重构损失和聚类损失：

不同的聚类算法采用不同的自动编码器网络和聚类算法。DCN[2] (Deep Clustering Network) 结合了AE和K-means，kSCN[3] (Scalable Deep k-subspace Clustering Network) 则采用K-subspace作为聚类方法。这些结合传统聚类算法和自动编码器的方法，并没有解决传统聚类算法的缺陷，例如依赖初始化，对离群点敏感等问题。这些算法通常需要利用K-means或者GMM来初始化聚类的中心点，这会影响算法的稳定性。本文针对kSCN缺陷，提出了深度加权K子空间聚类 (DWSC) 来解决依赖初始化和对离群点敏感的问题。

前提知识

1、表示学习 (Representation Learning)

表示学习的目的是对复杂的原始数据化繁为简，把原始数据的无效信息剔除，对有效信息更有效地进行提炼，形成特征。如何更加合理高效地将特征表示出来，是表示学习一个最主要的问题。在聚类任务中，我们采用的是无监督的方式进行表示学习。无监督的表示学习是学习从高维观察到低维表征空间的映射，使得可通过低维的表示（近似地）重建出原来的观察，比如，自动编码器和PCA，自动编码器可执行非线性变换，而PCA只能进行线性变换。深度聚类算法一般采用自动编码器的方法进行特征提取，能够将输入映射到深层非线性的特征空间，对复杂的高维数据有更好的拟合能力。重构损失一般采用均方误差：

代表观测样本，

代表重构样本，

代表特征，θ代表自动编码器网络。

2、K子空间聚类 (K-subspace Clustering)

K子空间聚类是K-means算法的一般化，K子空间聚类的目的是在样本空间中寻找K个最佳的子空间，使得所有样本离最近的子空间投影距离之和最小。目标函数可表示为：

代表第k个子空间的基，

代表第i个样本对第k个子空间的归属，取值为0或1,通过寻找与子空间最短的投影距离来确定：

kSCN提出先利用CAE学习数据嵌入，再进行K子空间聚类，但是，由于K-subspace跟K-means一样，比较依赖中心的初始化。kSCN需要通过使用DSC[4] (Deep Subspace Clustering) 网络来初始化K个子空间，这会影响算法最终的聚类性能和稳定性。

深度加权K子空间聚类

为了解决K-subspace对初始化的依赖和对离群点敏感的问题，通过构建了一个分配网络和两个正则项,我们提出DWSC网络。DWSC网络如下图所示：

图2.深度加权K子空间聚类网络结构

1、分配网络 (Assignment Network)

分配网络由一个多层的全连接网络加Softmax输出层组成，将自动编码器网络提取的特征经过分配网络可以得到一个软分配 (Soft Assignmen)：

代表多层全连接网络，

代表第i个样本属于第k个子空间的概率，且满足

和

。与K-subspace的硬分配 (Hard Assignment) 不同，软分配能够捕捉到样本之间的联系，有效缓解对离群点和边界点的敏感。

2、正则项 (Regularization)

为了解决网络依赖初始化问题，针对软分配增加两个约束项：

这两个正则项实现了相反的作用。在

和

的条件下，最小化第一项能够得到稀疏的one-hot向量，使每个样本拥有一个主要的子空间分配。第二项是对于批量样本的平均概率分布的一个L2范数约束，最小化第二项得到批量数据平均的分配，即分配到每个子空间的数量较平均，这样可以避免模型出现一致分配 (Identical assignment) 的平凡解 (Trivial solution)。

DWSC的目标函数可以表示为：

只要在实验过程中正确设置这两个正则项的平衡系数即可随机初始化K个子空间的基，消除模型对初始化的依赖，详情可见论文III.B。

实验

DWSC在两个数据集MNIST和Fashion-MNIST进行了实验，并与最好的几个深度聚类算法进行了对比。

表1.聚类结果对比

结果显示，无论是MNIST还是Fashion-MNIST数据集，三个聚类指标都比kSCN要好上不少，并且性能优于VaDE[5] (Variational Deep Embedding)。另外，在对比的深度聚类算法中，只有DWSC不需要预先对聚类中心进行初始化，解决了现有方法对初始化的依赖问题。

参考文献

[1] E. Min et al., “A survey of clustering with deep learning: From the perspective of network architecture,” IEEE Access, vol. 6, pp. 39501–39514, 2018.

[2] B. Yang, X. Fu, N. D. Sidiropoulos, and M. Hong, “Towards k-meansfriendly spaces: Simultaneous deep learning and clustering,” in Proc. 34th Int. Conf. Mach. Learn., 2017, pp. 3861–3870.

[3] T. Zhang et al., “Scalable Deep k-Subspace Clustering,” 2018, arXiv:1811.01045.

[4] P. Ji et al., “Deep subspace clustering networks,” in Proc. Conf. Neural Inf. Process. Syst., 2017, pp. 24–33.

[5] Z. Jiang et al., “Variational deep embedding: An unsupervised and generative approach to clustering,” in Int. Joint Conf. Artific. Intell., 2017, pp. 1965–1972. arXiv:1611.05148.

往期精选

通知

2020年“CSIG图像图形中国行”承办方征集