脚本宝典收集整理的这篇文章主要介绍了论文解读SDCN《Structural Deep Clustering Network》,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
在现实中,将结构信息集成到深度聚类中通常需要解决以下两个问题。
1、在深度聚类中应该考虑哪些结构性信息?
2、结构信息与深度聚类之间的关系是什么?
为获取结构信息,首先构造一个 KNN 图,它能够揭示数据的底层结构。为从 KNN 图中获取低阶和高阶的结构信息,提出了一个由多个图卷积层组成的 GCN 模块来学习 GCN 特定的表示。为了将结构信息引入到深度聚类中,引入了一个 AutoEncoder 模块来从原始数据中学习 AutoEncoder 特定的表示,并提出了一个 delivery operator 来将其与 GCN 特定的表示相结合。我们从理论上证明了 delivery operator 能够更好地辅助自动编码器与 GCN 之间的集成。特别地,我们证明了 GCN 为由 Autoencoder 学习的表示提供了一个近似的二阶图正则化,并且由自编码器学习的表示可以缓解GCN中的过平滑问题。
最后,由于自动编码器和GCN模块都将输出表示,我们提出了一个双自监督模块来统一引导这两个模块。通过双自监督模块,可以对整个模型进行端到端聚类任务训练。
综上所述,本文主要贡献如下:
The blue solid line represents that target distribution P is calculated by the distribution Q and the two red dotted lines represent the dual self-supervised mechanism. The target distribution P to guide the update of the DNN module and the GCN module at the same time.
在本节中,将介绍 SDCN,其整体框架如 Figure 1 所示。首先基于原始数据构建一个KNN图。然后,将原始数据和 KNN 图分别输入到自动编码器和GCN中。并将每一层的自动编码器与相应的 GCN 层连接起来,这样就可以通过 delivery operator 将自动编码器特定的表示集成到 GCN 的表示中。同时,我们提出了一种双重自监督机制来监督自动编码器和 GCN 的训练进程。本文将在下面详细描述我们提出的模型。
假设我们有原始数据 $mathrm{X} in mathbb{R}^{N times d} $,其中每一行 $mathbf{x}_{i}$ 代表 $i-th$ 样本,$N$ 是样本数,$d$ 是维度。 对于每个样本,我们首先找到它的 $top-K$ 相似邻居并设置边以将其与其邻居连接。 有很多方法可以计算样本的相似度矩阵 $S in mathbb{R}^{N} times N$。
这里列出在构建 KNN 图时使用的两种相似度计算的流行方法:
$ mathrm{S}_{i j}=e^{-frac{left|mathrm{x}_{i}-mathrm{x}_{j}right|^{2}}{t}}quad quad(1)$
其中, $t$ 为热传导方程中的时间参数。对于连续的数据,如:图像。
$mathrm{S}_{i j}=mathbf{x}_{j}^{T} mathbf{x}_{i} quad quad (2)$
对于离散数据,如: bag-of-words,使用点积相似性,使相似性只与相同 word 的数量相关。
在计算相似度矩阵 $S$ 后,选择每个样本的前 $k$ 个相似度点作为其邻居,构造一个无向的 $k$ 近邻图,从非图数据中得到邻接矩阵 $A$。
tips:代码中 $k =10$,但是仔细看生成的邻接矩阵可以发现部分点甚至出现了11个最近临。
在本文中,使用基本的自动编码器来学习原始数据的表示,以适应不同类型的数据特征。假设在自动编码器中存在 $L$ 个层,并且 $ℓ$ 表示层数。
在 Encoder 部分 $H(ℓ)$ 中,第 $ℓ$ 层学习到的表示如下:
$mathbf{H}^{(ell)}=phileft(mathbf{W}_{e}^{(ell)} mathbf{H}^{(ell-1)}+mathbf{b}_{e}^{(ell)}right)$
其中 $phi$ 是激活函数,本文取 $Relu$。 $mathbf{W}_{e}^{(ell)}$ 和 $mathbf {b}_{e}^{(ell)}$ 分别是 Encoder 中 $ell$ 层的权重矩阵和偏差。 此外,我们将 $mathbf{H}^{(0)}$ 表示为 raw data : $mathbf{X}$ 。
Encoder 部分后面是 Decoder 部分:
$mathbf{H}^{(ell)}=phileft(mathbf{W}_{d}^{(ell)} mathbf{H}^{(ell-1)}+mathbf{b}_{d}^{(ell)}right) quad quad (4)$
其中 $mathbf{W}_{d}^{(ell)}$ 和 $mathbf{b}_{d}^{(ell)}$ 是分别位于解码器第 $ell$ 层的权重矩阵和偏差 。
解码器部分的输出是对原始数据 $hat{mathbf{X}}=mathbf{H}^{(L)}$ 的重构,从而得到以下目标函数:
$mathcal{L}_{r e s}=frac{1}{2 N} sum limits _{i=1}^{N}left|mathbf{x}_{i}-hat{mathbf{x}}_{i}right|_{2}^{2}=frac{1}{2 N}|mathbf{X}-hat{mathbf{X}}|_{F}^{2}quad quad (5)$
自编码器能够从数据本身中学习有用的表示,例如 $mathrm{H}^{(1)}$ , $mathrm{H}^{(2)}$ , $cdots$ , $mathrm{H}^{(L)}$ ,但忽略了样本之间的关系。 在本节中,将介绍如何使用 GCN 模块来传播 DNN 模块生成的这些表示。 一旦将 DNN 模块学习到的所有表示都集成到 GCN 中,那么 GCN 可学习表示将能够适应两种不同类型的信息,即数据本身和数据之间的关系。
$mathrm{GCN}$ 的 $ell$ 层,权重矩阵 $mathbf{W}$ ,学习到的表示$mathrm{Z}^{(ell)}$ 可以通过以下卷积运算得到:
$mathrm{Z}^{(ell)}=phileft(widetilde{mathrm{D}}^{-frac{1}{2}} widetilde{mathrm{A}} widetilde{mathrm{D}}^{-frac{1}{2}} mathbf{Z}^{(ell-1)} mathbf{W}^{(ell-1)}right) quad quad (6)$
其中 $widetilde{mathbf{A}}=mathbf{A}+mathbf{I}$ 和 $widetilde{mathbf{D}}_{ii}=sum_{j} widetilde{mathbf {A}}_{mathbf{ij}}$ , $mathbf{I}$ 是每个节点中自循环的相邻矩阵 $A$ 的单位对角矩阵。 从方程 (6) 可以看出,表示 $Z^{(ell-1)}$ 将通过归一化邻接矩阵 $widetilde{mathbf{D}}^{-frac{1}{2}} widetilde{mathbf {A}} widetilde{mathbf{D}}^{-frac{1}{2}}$ 以获得新的表示 $Z^{(ell)}$ 。
考虑到自编码器 $mathbf{H}^{(ell-1)}$ 学习到的表示能够重构数据本身并包含不同的有价值信息,我们将这两种表示结合起来 $mathbf{Z}^{( ell-1)}$ 和 $mathbf{H}^{(ell-1)}$ 一起得到更完整和强大的表示如下:
$widetilde{mathbf{Z}}^{(ell-1)}=(1-epsilon) mathbf{Z}^{(ell-1)}+epsilon mathbf{H}^{(ell-1)} quad quad (7)$
其中 $ϵ$ 是一个平衡系数,在这里我们统一地将其设为 $0.5$ 。这样,我们一层地将自动编码器和 GCN 连接起来。
然后使用 $widetilde{mathbf{Z}}^{(ell-1)}$ 作为 $mathrm{GCN}$ 中 $l $ 层的输入来生成表示 $Z^{ (ell)} $:
$mathbf{Z}^{(ell)}=phileft(widetilde{mathbf{D}}^{-frac{1}{2}} widetilde{mathbf{A}} widetilde{mathbf{D}}^{-frac{1}{2}} widetilde{mathbf{Z}}^{(ell-1)} mathbf{W}^{(ell-1)}right) quad quad (8)$
由于每个 DNN 层学习的表示不同,为了尽可能多地保留信息,我们将从每个 DNN 层学习到的表示转移到相应的 GCN 层进行信息传播,如图 1 所示。delivery operator 在整个模型中工作 $L$ 次。 我们将在 3.5 节中从理论上分析这种 delivery operator 的优势。
注意,第一层GCN的输入是原始数据 $X$:
$mathrm{Z}^{(1)}=phileft(widetilde{mathbf{D}}^{-frac{1}{2}} widetilde{mathrm{A}} widetilde{mathbf{D}}^{-frac{1}{2}} mathbf{X} mathbf{W}^{(1)}right) quad quad (9)$
GCN模块的最后一层是具有 softmax 功能的多分类层:
$Z=operatorname{softmax}left(widetilde{mathbf{D}}^{-frac{1}{2}} widetilde{mathbf{A}} widetilde{mathbf{D}}^{-frac{1}{2}} mathbf{Z}^{(L)} mathbf{W}^{(L)}right) quad quad (10)$
结果 $z_{i j} in Z$ 表示概率样本 $i$ 属于聚类中心 $j$ ,我们可以将 $Z$ 视为概率分布。
现已在神经网络架构中将自动编码器与 GCN 连接起来。然而,它们并不是为 deep clustering 而设计的。自动编码器主要用于数据表示学习,这是一种无监督的学习场景,而传统的 GCN 是在半监督的学习场景中。它们两者都不能直接应用于聚类问题。
在此,我们提出了一个双自监督模块,它将自编码器和 GCN 模块统一在一个统一的框架内,有效地对这两个模块进行端到端训练以进行聚类。
对于第 $i$ 个样本和第 $j$ 个簇,我们使用 Student’s t-distribution 来度量数据表示 $h_i$ 和簇中心向量 $µ_j$ 之间的相似性:
${large q_{i j}=frac{left(1+left|mathbf{h}_{i}-boldsymbol{mu}_{j}right|^{2} / vright)^{-frac{v+1}{2}}}{sum_{j^{prime}}left(1+left|mathbf{h}_{i}-boldsymbol{mu}_{j^{prime}}right|^{2} / vright)^{-frac{v+1}{2}}}} quad quad (11)$
其中 $mathbf{h}_{i}$ 是 $mathbf{H}^{(L)}$ 的第 $i$ 行, $boldsymbol{mu}_{j}$ 初始化为 $K -means$ 在预训练自动编码器学习的表征上,$v$ 是 Student’s t-distribution 的自由度。 $q_{i j}$ 可以认为是将样本 $i$ 分配给集群 $j$ 的概率,即软分配。 我们将 $Q=left[q_{i j}right]$ 视为所有样本的分配分布,并让 $v=1$ 用于所有实验。
在获得聚类结果分布 $Q$ 后,我们的目标是通过从高置信度分配中学习来优化数据表示。具体来说,我们希望使数据表示更接近集群中心,从而提高集群的凝聚力。因此,我们计算一个目标分布 $P$ 如下:
${large p_{i j}=frac{q_{i j}^{2} / f_{j}}{sum_{j^{prime}} q_{i j^{prime}}^{2} / f_{j^{prime}}}} quad quad (12)$
其中 $f_{j}=sum_{i} q_{i j}$ 是软聚类频率。在目标分布 $P$ 中,对 $Q$ 中的每个分配进行平方和归一化,以便分配具有更高的置信度,采用 KL 散度来比较两类概率:
$mathcal{L}_{c l u}=K L(P | Q)=sum limits _{i} sumlimits _{j} p_{i j} log frac{p_{i j}}{q_{i j}} quad quad (13)$
通过最小化 $Q$ 和 $P$ 分布之间的 $KL$ 散度损失。
目标分布 $P$ 可以帮助DNN模块学习更好的聚类任务表示,即使数据表示更接近聚类中心。这被认为是一个自监督机制,因为目标分布 $P$ 是由分布 $Q$ 计算出来的,而 $P$ 分布依次监督分布 $Q$ 的更新。
另一个自监督模块在:对于 GCN 模块的训练,GCN 模块也会出现提供一个聚类分配分布 $Z$ 。因此,可以使用分配 $P$ 来监督分配 $Z$ 如下:
$mathcal{L}_{g c n}=K L(P | Z)=sum limits_{i} sum limits _{j} p_{i j} log frac{p_{i j}}{z_{i j}}quad quad (14)$
该目标函数有两个优点:
通过这种机制,SDCN可以直接将聚类目标和分类目标这两个不同的目标集中在一个损失函数中。因此,我们提出的SDCN的总体损失函数是:
$mathcal{L}=mathcal{L}_{text {res }}+alpha mathcal{L}_{text {clu }}+beta mathcal{L}_{g c n}quad quad (15)$
其中,$α>0$(实验取0.1) 是平衡原始数据的聚类优化和局部结构保存的超参数,$β>0$ (实验取0.01) 是控制GCN模块对嵌入空间的干扰的系数。
训练直到最大时期,SDCN 将得到一个稳定的结果。然后就可为样本设置标签。我们选择分布 $Z$ 中的软分配作为最终的聚类结果。因为 GCN 学习到的表示包含了两种不同类型的信息。分配给样本 $i$ 的标签是:
$r_{i}=underset{j}{arg max} z_{i j}quad quad (16)$
其中 $z_{ij}$ 是用方程 (10) 计算出来的。
算法流程:
在本节中,我们将分析 SDCN 如何将结构信息引入自动编码器。在此之前,我们给出了 Graph regularization 和 Second-order graph regularization 的定义。
Definition 1. Graph regularization [2]. Given a weighted graph $G$, the objective of graph regularization is to minimize the following equation:
$sum limits _{i j} frac{1}{2}left|mathbf{h}_{i}-mathbf{h}_{j}right|_{2}^{2} w_{i j}$
Definition 2. Second-order similarity. We assume that $mathrm{A}$ is the adjacency matrix of graph $mathcal{G}$ and $mathrm{a}_{i}$ is the $i -th$ column of $A$. The second-order similarity between node $i$ and node $j$ is
$s_{i j}=frac{mathbf{a}_{i}^{T} mathbf{a}_{j}}{left|mathbf{a}_{i}right|left|mathbf{a}_{j}right|}=frac{mathbf{a}_{i}^{T} mathbf{a}_{j}}{sqrt{d_{i}} sqrt{d_{j}}}=frac{C}{sqrt{d_{i}} sqrt{d_{j}}}$
其中 $C$ 为节点 $i$ 和节点 $j$ 之间的共同邻居的个数,$d_i$ 为节点 $i$ 的度。
其中 $s_{ij}$ 是二阶相似度。
与 Definition 1 相比,Definition 3 施加了一个高阶约束,即如果两个节点有许多共同的邻居,它们的表示也应该更相似。
Methods
Metrics
Parameter Setting.
if you want to know more ,please see the Code.
Table 2 shows the clustering results on six datasets.
我们将我们的模型与两种变体进行了比较,以验证GCN在学习结构信息方面的能力和 delivery operator 的生态能力。特别地,我们研究以下变体:
From Figure 2, we have the following observations:
我们选择具有原始图的数据集来验证聚类上传播层数的数量,因为它们具有自然结构信息。
分析如下:
$ϵ=0.0$ 表示GCN模块中的表示不包含来自自动编码器的表示,而 $ϵ=1.0$ 表示GCN只使用DNN学习到的表示 $H^{(L)}$。
在本文中,我们首次尝试将结构信息集成到深度聚类中。我们提出了一种新的结构性深度聚类网络,由DNN模块、GCN模块和双自监督模块组成。我们的模型能够有效地将自 autoencoder-spectic representation 与 GCN-spectic representation 结合起来。通过理论分析,证明了交付操作员的强度。我们表明,我们提出的模型在各种开放数据集中始终优于最先进的深度聚类方法。
以上是脚本宝典为你收集整理的论文解读SDCN《Structural Deep Clustering Network》全部内容,希望文章能够帮你解决论文解读SDCN《Structural Deep Clustering Network》所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。