一种融合结构信息的图自编码器聚类方法

1.本发明涉及无监督学习及深度学习研究领域，具体涉及一种融合结构信息的图自编码器聚类方法，为充分利用数据中潜在特征信息进行聚类分析提供新思路。


背景技术：

2.聚类作为一项重要的无监督学习任务，其目的是将相似的数据样本划分至同一个簇，以区分无标签数据。传统的聚类方法，如k-means、dbscan和层次聚类等通过特定的距离度量标准对样本分簇。然而，随着输入数据维度的增加，此类算法的计算复杂度急剧增加，聚类性能也会大幅下降，因而有较难处理高维特征数据。近年来，借助深度神经网络强大的表示学习能力，从高维特征数据中提取更具有表征意义的特征，进而完成聚类分析，在无监督学习领域引起广泛关注。其中，xie等基于深度神经网络提取数据特征并构造初始聚类分布和高置信度辅助目标分布，通过最小化两个分布之间的kl散度优化聚类分配，同时改善数据特征表示，算法运行速度快，能够扩展到高维特征数据集实现聚类分析。yang等联合深度神经网络和k-means算法，提取更有利于k-means聚类分析的潜在特征，利用k-means代价优化特征提取，表现出较强的可扩展性。可以看出，上述算法仅限于数据本身特征，未能充分利用数据之间潜在的结构特征实现聚类分析。
3.谱聚类或图卷积网络(graph convolutional network,gcn)能够从图结构数据中习得数据结构特征实现聚类分析。谱聚类以子图内部相似度最大，子图之间相似度最小为目标，将聚类问题转化为图划分问题。但谱聚类需求解特征值和特征向量，计算复杂度高，应用于高维特征数据困难。而基于gcn的聚类算法在高维特征数据集上取得了令人瞩目的进展。如pan等结合gcn与生成对抗网络，开发对抗正则化图自编码器和对抗正则化变分图自编码器学习图嵌入表示实现聚类分析。由于数据特征和结构特征均可用于聚类分析，一些研究也尝试将二者结合实现更优的聚类性能。如bo等提出结构化深度聚类(structural deep clustering network,sdcn)模型，通过传递算子将每层自编码器提取的数据特征输送到对应的gcn层，首次将数据特征和结构特征相结合以实现聚类分析。付兴武等引入最大化互信息与最小化先验分布约束多层卷积自编码器的特征提取，同时将深度卷积自编码器习得数据特征和gcn习得结构特征相加实现图像聚类。这些研究为有效利用数据特征和结构特征提供了新思路，但对二者的融合仅停留在简单的拼接、堆栈或加法实现，未能达成两种特征深度的优势互补。同时，现有基于gcn的聚类算法在学习数据结构特征时往往缺乏约束和指导。


技术实现要素：

4.本发明目标是通过融合数据特征和结构特征提高深度聚类算法的性能，建立一种融合结构信息的图自编码器聚类方法，简称gaecsf。本发明通过构建自编码器提取数据特征，利用k近邻将数据表示为图结构，构建图自编码器提取结构特征，设计特征融合网络实现两种特征的互补融合与传递，同时建立自监督机制统一引导自编码器、图自编码器和特
征融合网络的协同训练，迭代优化，实现聚类分析。gaecsf的具体实施步骤是：
5.步骤(1)：构建自编码器提取数据特征信息，自编码器主要由编码器网络和解码器网络组成，假设数据集x＝{xi|i＝1,2,
…
,n}，其中xi为x的第i行，对应第i个样本，n为样本数目，h0＝x则为自编码器的输入。自编码器中编码器网络设计有l层，编码器网络第l层的输入即为第l-1层的输出，记作h
l-1
，则编码器网络第l层的输出如式(1)表示：
6.h
l
＝σ(w
lhl-1
+b
l
)
ꢀꢀꢀ
(1)
7.其中，σ表示relu激活函数，w
l
和b
l
分别表示编码器网络第l层的权重和偏置，解码器网络第l层的输如式(2)表示：
8.h＝σ(w
lhl-1
+b
l
)
ꢀꢀꢀ
(2)
9.其中，w
l
、b
l
分别表示解码器网络第l层的权重和偏置，h
l-1
为第l-1层的输出.编码器网络的输出h
l
即为解码器网络的输入h0，自编码器的输出为重构数据x，自编码器的目标即为最小化x和x之间的误差，因此自编码器优化的损失函数即为均方误差损失，如式(3)表示：
[0010][0011]
步骤(2)：基于k近邻将非图结构数据转换为图结构数据，对于连续数据，使用皮尔逊相关系数计算相似度的如式(4)所示：
[0012][0013]
而对于离散数据，使用内积计算相似度如式(5)所示：
[0014]sij
＝x
jt
xiꢀꢀꢀ
(5)
[0015]
设样本之间的相似度矩阵为s＝{s
ij
}，图数据中节点集合为v＝{v1,v2,
…
,vn}，邻接矩阵a＝{a
ij
}，其中，n为节点的数目，当节点vi与vj之间存在边相连时，a
ij
＝1，否则a
ij
＝0。将x中的每个样本作为目标节点，利用s筛选目标节点对应的前k个高相似性样本作为其邻居节点，将目标节点与邻居节点进行连接，构造一个无向的k近邻图，
[0016]
步骤(3)：构造基于gcn的图自编码器提取数据结构特征信息，基于gcn的图自编码器在习得数据结构特征的同时重构图结构关系。图自编码器呈对称结构，前l层为图编码网络，后l层为图解码网络，x和a作为图自编码器的输入，图编码网络第l层的输入即为第l-1层的输出，记作z
l-1
，则图编码网络第l层的输出如式(6)表示：
[0017][0018]
其中a＝a+i，d
ii
＝∑
jaij
，i表示节点的自连接，为单位矩阵，w
l-1
表示图编码网络第l-1层到第l层的权重，图编码网络中第1层因无前一层网络的输出，表示方式有所不同，第1层如式(7)所示：
[0019][0020]
相应的，假设图解码网络有l层，第l-1层的输出即为第l层的输入，记作z
l-1
，图解码网络第l层的输出表示如式(8)所示：
[0021]
[0022]
其中，w
l-1
表示图解码网络第l-1层到第l层的权重，图自编码器的输出如式(9)所示：
[0023][0024]
重构邻接矩阵由z
l
计算如式(10)表示：
[0025][0026]
基于a与a构造图重构损失如式(11)所示：
[0027][0028]
基于x与z
l
构造图特征重构损失如式(12)所示：
[0029][0030]
步骤(4)：构建特征融合网络互补融合传递数据特征和结构特征，特征融合网络由l层全连接网络构成，将自编码器和图自编码器逐层互补融合传递，第l层特征融合网络的输出如式(13)表示：
[0031]fl
＝σ(w
lf
(h
l
+z
l
+f
l-1
)+b
lf
)
ꢀꢀꢀꢀ
(13)
[0032]
其中w
lf
和b
lf
分别是特征融合网络第l层的权重和偏置，f
l-1
则表示第l-1层的输出，当l＝1时，因无前层特征融合网络，其输出如式(14)表示：
[0033]
f1＝σ(w
1f
(h1+z1)+b
1f
)
ꢀꢀꢀ
(14)
[0034]
步骤(5)：构建自监督机制统一引导自编码器、图自编码器和特征融合网络实现端到端协同训练，迭代优化，实现聚类标签的分配，通过k-means对预训练得到的编码器网络的输出h
l
进行聚类，得到j个聚类中心使用student’s t分布计算hi与聚类中心μj之间的相似性如式(15)所示：
[0035][0036]
其中hi∈h
l
，表示第i个样本的特征，对应h
l
的第i行，q
ij
可以被视作样本hi被分配给聚类中心μj的概率，v表示自由度，令q＝{q
ij
}，q的高置信度分布计算如式(16)所示：
[0037][0038]
令p＝{p
ij
}，计算概率分布p和q之间的kl散度式(17)所示：
[0039][0040]
通过最小化l
pq
约束q的生成，使p和q两个概率分布尽可能逼近，形成有效的自监督机制帮助自编码器习得对聚类更具有表征意义的数据特征，对于特征融合网络的输出f
l
，通过softmax机制获得其概率分布f如式(18)所示：
[0041]
f＝softmax(f
l
)
ꢀꢀꢀ
(18)
[0042]
概率分布p和f之间的kl散度计算如式(19)所示：
[0043][0044]
通过最小化l
pf
由p约束f的生成，最终完成自编码器、图自编码器和特征融合网络的协同训练，输出聚类标签分配如式(20)所示：
[0045]
c＝argmax(f)
ꢀꢀꢀ
(20)
[0046]
gaecsf整体的损失函数定义如式(21)所示：
[0047][0048]
通过最小化gaecsf算法整体损失函数进行迭代优化，最终，输出聚类标签分配c。
附图说明
[0049]
图1是融合结构信息的图自编码器聚类方法的模型图。
具体实施方式
[0050]
为了进一步解释本次发明的具体内容和优点，以下是具体实施方式和附图的详细说明。
[0051]
为了说明本算法的有效性，在6组数据集上进行实验对比，包含图像、自然语言、人类活动、作者关系网络、论文引文网络等数据集，数据集的统计信息如表1所示：
[0052]
表1：数据集统计信息
[0053][0054]
为有效评估算法的聚类效果，本文使用四个标准的无监督评价指标：准确度(accurary,acc)、归一化互信息(normalized mutual information,nmi)、平均兰德指数(average rand index,ari)和f1分数(f1-score,f1)。对于非图结构数据集usps、hhar和reuters，统一采用5-nn方法构造图结构以满足算法需求考虑过拟合问题，每种对比算法均运行10次实验，分别计算上述指标的平均值和标准差。对于不同的数据集，gaecsf参数设置有所不同，对于usps，学习率设置为10-3
，迭代次数设置为200；对于hhar，学习率设置为10-3
，迭代次数设置为300；对于reuters，学习率设置为10-4
，迭代次数设置为200；对于acm、dblp和citeseer，学习率设置为10-4
，迭代次数设置为80。实验硬件环境为intel(r)xeon(r)w-2175处理器和nvidia geforce rtx 2080ti显卡，软件环境为pytorch 1.3.1。本发明提出的算法(gaecsf)和xie等人提出的算法(dec)，guo等人提出的算法(idec)，kipf等人提出的算法(vgae)，wang等人提出的算法(daegc)，bo等人提出的算法(sdcn)的性能比较如表2所示：
[0055]
表2：实验对比结果(平均值
±
标准差)
[0056][0057]
表2中加粗字体和下划线字体分别表示不同指标下所有算法中的最优结果和次优结果。
[0058]
最后说明：上述实施方式是为了更好的说明本发明的思路，绝不是对本发明的限制，凡是根据本发明本质内容所做的等效的替换、修改或补充，均应包含在本发明的保护范围之内。

技术特征：
1.通过构建自编码器提取数据特征，利用k近邻将数据表示为图结构，构建图自编码器提取结构特征，具体包括以下步骤：步骤(1)：构建自编码器提取数据特征信息，自编码器主要由编码器网络和解码器网络组成，假设数据集x＝{x
i
|i＝1,2,
…
,n}，其中x
i
为x的第i行，对应第i个样本，n为样本数目，h0＝x则为自编码器的输入，自编码器中编码器网络设计有l层，编码器网络第l层的输入即为第l-1层的输出，记作h
l-1
，则编码器网络第l层的输出如式(1)表示：h
l
＝σ(w
l
h
l-1
+b
l
)
ꢀꢀꢀꢀꢀꢀꢀꢀ
(1)其中，σ表示relu激活函数，w
l
和b
l
分别表示编码器网络第l层的权重和偏置，解码器网络第l层的输如式(2)表示：h＝σ(w
l
h
l-1
+b
l
)
ꢀꢀꢀꢀꢀꢀꢀ
(2)其中，w
l
、b
l
分别表示解码器网络第l层的权重和偏置，h
l-1
为第l-1层的输出.编码器网络的输出h
l
即为解码器网络的输入h0，自编码器的输出为重构数据x，自编码器的目标即为最小化x和x之间的误差，因此自编码器优化的损失函数即为均方误差损失，如式(3)表示：步骤(2)：基于k近邻将非图结构数据转换为图结构数据，对于连续数据，使用皮尔逊相关系数计算相似度的如式(4)所示：而对于离散数据，使用内积计算相似度如式(5)所示：s
ij
＝x
jt
x
i
ꢀꢀꢀꢀꢀꢀꢀꢀ
(5)设样本之间的相似度矩阵为s＝{s
ij
}，图数据中节点集合为v＝{v1,v2,
…
,v
n
}，邻接矩阵a＝{a
ij
}，其中，n为节点的数目，当节点v
i
与v
j
之间存在边相连时，a
ij
＝1，否则a
ij
＝0，将x中的每个样本作为目标节点，利用s筛选目标节点对应的前k个高相似性样本作为其邻居节点，将目标节点与邻居节点进行连接，构造一个无向的k近邻图，步骤(3)：构造基于gcn的图自编码器提取数据结构特征信息，基于gcn的图自编码器在习得数据结构特征的同时重构图结构关系，图自编码器呈对称结构，前l层为图编码网络，后l层为图解码网络，x和a作为图自编码器的输入，图编码网络第l层的输入即为第l-1层的输出，记作z
l-1
，则图编码网络第l层的输出如式(6)表示：其中a＝a+i，d
ii
＝∑
j
a
ij
，i表示节点的自连接，为单位矩阵，w
l-1
表示图编码网络第l-1层到第l层的权重，图编码网络中第1层因无前一层网络的输出，表示方式有所不同，第1层如式(7)所示：相应的，假设图解码网络有l层，第l-1层的输出即为第l层的输入，记作z
l-1
，图解码网络第l层的输出表示如式(8)所示：
其中，w
l-1
表示图解码网络第l-1层到第l层的权重，图自编码器的输出如式(9)所示：重构邻接矩阵由z
l
计算如式(10)表示：基于a与a构造图重构损失如式(11)所示：基于x与z
l
构造图特征重构损失如式(12)所示：2.基于权利要求1中构建的自编码器和图自编码器，建立特征融合网络，将自编码器习得的数据特征和图自编码器习得的结构特征进行互补融合，特征融合网络由l层全连接网络构成，将自编码器和图自编码器逐层互补融合传递，第l层特征编码器网络输出如式(13)表示：其中w
lf
和分别是特征融合网络第l层的权重和偏置，f
l-1
则表示第l-1层的输出，当l＝1时，因无前层特征融合网络，其输出如式(14)表示：3.基于权利要求1中构建的的自编码器和图自编码器与权利要求2中构建的特征融合网络，建立自监督机制统一引导自编码器、图自编码器和特征融合网络实现端到端协同训练，迭代优化，实现聚类标签的分配，通过k-means对预训练得到的编码器网络的输出h
l
进行聚类，得到j个聚类中心使用student’st分布计算h
i
与聚类中心μ
j
之间的相似性如式(15)所示：其中h
i
∈h
l
，表示第i个样本的特征，对应h
l
的第i行，q
ij
可以被视作样本h
i
被分配给聚类中心μ
j
的概率，v表示自由度，令q＝{q
ij
}，q的高置信度分布计算如式(16)所示：令p＝{p
ij
}，计算概率分布p和q之间的kl散度式(17)所示：通过最小化l
pq
约束q的生成，使p和q两个概率分布尽可能逼近，形成有效的自监督机制帮助自编码器习得对聚类更具有表征意义的数据特征，对于特征融合网络的输出f
l
，通过softmax机制获得其概率分布f如式(18)所示：f＝softmax(f
l
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(18)
概率分布p和f之间的kl散度计算如式(19)所示：通过最小化l
pf
由p约束f的生成，最终完成自编码器、图自编码器和特征融合网络的协同训练，输出聚类标签分配如式(20)所示：c＝argmax(f)
ꢀꢀꢀꢀꢀꢀꢀꢀ
(20)gaecsf整体的损失函数定义如式(21)所示：通过最小化gaecsf算法整体损失函数进行迭代优化，最终，输出聚类标签分配c。

技术总结
本发明名为融合结构信息的图自编码器聚类方法，属无监督学习及深度学习研究领域。本发明目标是构建自编码器提取数据特征，利用K近邻将数据表示为图结构，构建图自编码器提取结构特征，设计特征融合网络实现两种特征的互补融合与传递，保留更多的潜在特征信息。同时，建立自监督机制统一引导自编码器、图自编码器和特征融合网络的协同训练，迭代优化，实现聚类分析。通过六组公共数据集上的实验对比结果验证本发明在高维特征数据集上的聚类分析有效性，本发明有望为充分利用数据潜在特征信息进行聚类分析提供新思路。进行聚类分析提供新思路。


技术研发人员：张林 陈祥志 刘辉 陈淑涛 向海平 潘永
受保护的技术使用者：中国矿业大学
技术研发日：2022.01.13
技术公布日：2023/7/26