论文阅读“Semi-supervised clustering with deep metric learning and graph embedding”

Li X, Yin H, Zhou K, et al. Semi-supervised clustering with deep metric learning and graph embedding[J]. World Wide Web, 2020, 23(2): 781-798.

摘要翻译

聚类作为社交网络中的一种常见技术，因其高性能而引起了广泛的研究兴趣，并提出了许多聚类方法。现有聚类方法是基于无监督学习的。事实上，我们通常可以在实际应用中得到少数的标记样本。最近，人们提出了几种半监督聚类方法，尽管还有很多改进的空间。本文的目标是解决半监督聚类过程中的两个研究问题：(i)如何学习更有鉴别性的特征以提升聚类过程的；(ii)如何有效地利用已标记的数据和未标记的数据来提高聚类的性能。为了解决这两个问题，论文提出了一种新的基于深度度量学习(SCDML)的半监督聚类方法，它以一种新的方法有效地利用了深度度量学习和半监督学习。为了使提取的数据贡献特征更具有代表性，标签传播网络更适合实际应用，论文在深度度量学习网络中采用 triplet loss，并将bedding？与标签传播策略相结合，动态地将未标签数据更新为已标签数据，进一步改进了聚类，称为 semi-supervised clustering with deep metric learning and graph embedding (SCDMLGE)。SCDMLGE增强了度量学习网络的鲁棒性，提高了聚类的准确性。在多个基准数据集上的实验，说明了模型的有效性。

聚类归纳

The unsupervised clustering technique has drawn a tremendous amount
of research attention, and many clustering methods have been proposed in the past.

这些聚类方法通常可以分为三种类型：

基于特征学习的方法。该方法试图通过结合数据降维技术或子空间学习技术来寻找更具有区分性的特征。
基于度量学习的方法。此方法旨在学习训练数据的一个适当的距离度量。在学习的距离度量下，它可以将相似的样本组合在一起并同时将不相似的样本分离。
基于图的聚类。这种方法根据数据的成对相似性将数据划分为不同的类簇。

semi-supervised clustering with deep metric learning框架

SCDML--可以利用深度度量学习模型提取可判别的特征，同时，通过KNN标签更新策略优化聚类结果，动态增加标记数据集，然后进一步提升度量学习网络的性能。

图（a）展示了现有的半监督的固定输入聚类模型训练网络模型，而在论文的网络模型中，该模型通过增量地不断更新标记数据，如图（b）所示。

该框架贡献点总结

设计了一种新的半监督聚类模型，其中包括一个半监督深度度量学习子网和一个标签传播子网。

SCDML

在深度度量学习子网中，通过使用Siamese CNNs来抽取可判别的特征来最小化聚类误差。
在标签传播子网中，通过KNN标记更新策略将无标记数据转换为有标记数据。并以此增强深度度量学习子网的性能。

（1） semi-supervised deep metric learning network

step 1: 将已标记的样本对输入到Siamese CNNs，来抽取可识别的特征。该网络的损失函数为对比损失:

contrastive loss

step 2: 然后通过训练好的度量学习网络对所有数据，包括标记数据和未标记数据进行编码，以获得其对应特征。
step 3: 最后，根据编码特征对未标记数据进行分类，并将分类结果记录为未标记数据的标签。

（2） k-nearest neighbors label updating strategy

给定数据集，所有的数据属于 $C$ 个类簇，每个类簇包含有限的标记数据，大量的未标记数据。为了充分利用未标记数据的特性，我们每次将 $K*C$ 个新的未标记数据添加到标记数据集。KNN标签更新策略的主要流程如下。
step 1: 通过有标签的数据来计算每个类簇的中心：

step 2: 计算每个无标签数据到类簇中心的距离，并选择top k样本添加到有标签数据中：

在SCDML的(b)图中的实点表示标记数据，空心点表示未标记数据。在找到每个类簇的标记数据中心后，将距离该中心最近的未标记样本（top k）作为新的标记数据。

随着标记数据数量的增加，度量模型可以学习更鲁棒性和有鉴别性的特征，这将进一步提高聚类的准确性。

Improved semi-supervised clustering with deep metric learning

进一步作者考虑到：(i)度量函数的选择会影响数据特征提取的准确性，进而影响聚类结果的准确性; (ii)在实际应用中，由于每个簇的密度、被标记数据的数量以及它们在每个簇中的分布不同，KNN标签更新策略不是很适用。
由此进行了两个方面的改进：(i)将triplet CNNs作为度量学习模型，并以triplet loss作为模型的损失来训练网络。(ii)设计了一个更合理的标签传播网络，将未标记数据动态转换为标记数据。改进后的总体框架如下图所示：

SCDMLGE

（1） Semi-supervised deep metric learning and classification network

step 1: 用带有标记数据来训练网络。首先，通过 triplet CNNs提取可识别特征，然后利用特征训练分类器。为了同时学习特征提取和训练分类网络，改论文设计了半监督深度度量学习和分类网络的损失函数如下：

L Loss

其中，

||W||^2_F

是一个防止过度拟合的正则项。

L_M

和

L_C

分别是度量学习损失和分类损失。

triplet loss

上式为典型的triplet loss构造，最小化Anchor和正例之间的距离，而最大化Anchor和负例之间的距离。

\alpha

是人为设置的二者之间的最小间隔。
用于分类的损失函数如下:

classification loss

step 2: 分别对标记数据和未标记数据利用训练好的网络进行编码，得到对应的特征输出

S’_l

和

S’_u

。
step 3: 根据分类网络标记未标记的数据。样本

s_{ui}

对应的分类标签记为：

l_{ui}^1

。

（2）Semi-supervised clustering labeling propagation network

通过深度度量学习和分类网络，可以获得未标记数据的标签，称为弱标签。为了获得未标记数据的强标签，论文设计了一个半监督的标签传播网络。它包括半监督聚类和标记传播两部分。

在半监督聚类的过程中，提出了一种改进的图聚类算法。

首先构造一个相似度矩阵 $W$ 。

W

其中， $σ$ 表示样本点的邻域宽度，即 $σ$ 越大，样本点之间的相似性就越大。
然后构造度矩阵 $D$ 。

D

得到拉普拉斯矩阵 $L$ 。

L
接下来，对拉普拉斯矩阵进行矩阵分解（附：矩阵分解的意义）使用 $L$ 的top k特征向量（列向量） $u_1,u_2, ...,u_k$ 形成一个新的矩阵 $U \in R^{N*k}$ (k为特征向量的个数，N为特征向量的维数)。然后，利用k-means聚类算法得到了聚类结果。(注：这里作者没说怎么用，我认为形成的 $U$ 就是谱聚类中对应的降维后的矩阵，原来 $N*N$ 的矩阵被转换成 $N*k$ 的矩阵，然后利用k-means聚类)
最后利用聚类结果对无标签数据的CNN特征表示 $S'_u$ 进行标记， $l^2_{ui}$ 是 $s'_{ui}$ 的聚类标签。(注：这里作者也没说聚类标签和分类标签的对应，因为对于分类标签来说有明确的标签信息，而在聚类中只存在相似性。因此，我猜测可能是通过每个类簇中有标签数据的Tag来对类簇标记进行统一明确的？欢迎一起讨论)

当同时得到未标记数据 $S_u$ 的分类标签和聚类标签时，由此进行标记传播策略。

假设 $ΔS$ 表示新增的强标签数据，它可通过以下方式获得：

ΔS

此时对标记数据和未标记数据进行更新，

update data

完整的算法过程如下：