·1114· 智能系统学报 第15卷 个簇，使得“同一个簇内的样本相似度较高，不同 括I:图递归神经网络(graph recurrent neural net-- 簇间的样本相似度较低”。在实际的聚类分析 works,Graph RNNs)、图卷积网络(graph confolu- 任务中，由于数据类型和结构分布的复杂性与多 tional networks,.GCN)、图自动编码器(graph au- 样性，单一聚类方法的适用范围、可靠性和稳定 toencoders,.GAE)和图强化学习(graph reinforce-. 性都受到了制约，为此，研究人员结合集成学习 ment learning,Graph RL)。其中图卷积网络为半监 技术提出了聚类集成的方法。聚类集成的目 督方法，利用节点属性和节点标签训练模型参 的是将数据集的多重基聚类集成为统一的、综合 数，图自动编码器为无监督方法，利用自动编码 的最终聚类结果，其过程主要包括两个阶段，首 器的降维技术学习图的低维表征。 先使用不同的聚类算法或重复同一种聚类算法生 1.2图自动编码器 成多个基聚类；其次设计有效的一致性函数对基 图自动编码器(graph autoencoders,.GAE)在稀 聚类进行集成，获得最终聚类集成结果。 疏自编码器(sparse autoencoder,.SAE)I的启发下 一致性函数通常用来将基聚类的划分结果进 被提出，该模型将邻接矩阵或其变体作为节点的 行集成，得到一个统一的聚类结果。现有的一致 原始特征，将自动编码器(autoencoder,AE)作为 性函数大体包括以下几种。1)投票法：其基本思 降维方法来学习低维节点表征。简单来说，图自 想是首先根据得到的基聚类对样本划分结果进行 动编码器的基本思想是：首先输人图的邻接矩阵 投票，然后计算每个样本被划分到各个簇中的投 和节点的特征矩阵；然后通过编码器学习节点低 票比例，若样本归属于某个簇的投票比例超过一 维向量表示的均值和方差；最后利用解码器重构 定阈值（一般大于等于0.5），则将样本划分到该簇 图。因此图自动编码器能很好地处理没有监督信 中。2)证据积累：其基本思想是同一个自然簇 息的图，同时学习图的低维表征。 中的“样本对“在不同的基聚类中可能属于同一个 簇。具体划分过程为：把每个基聚类看作是一个 2图神经网络自监督聚类集成算法 独立的证据，计算“样本对”被分到同一个簇中的 本文提出了一种深度自监督聚类集成算法， 次数，从而得到共协矩阵，然后使用基于最小生 该算法首先根据基聚类划分计算样本之间的相似 成树(mininum spaning tree,MST)的层次聚类算法 度矩阵以表达样本之间的邻接关系，将基聚类在 得到最终的聚类结果9.3)概率积累：其基本 特征空间的表示转化为图数据表示：然后利用图 思想是使用簇密度来计算基聚类中所有“样本对” 自动编码器学习图的低维嵌入，由低维嵌入的似 间的距离，生成p-association矩阵，依据最高寿命 然分布监督聚类集成过程，同时通过聚类集成目 标准采用MST合并p-association矩阵得到最终的 标指导低维嵌入的学习过程，形成一个聚类集成 聚类结果。4)超图划分：其基本思想是先将聚 的自监督优化模型，从而优化聚类集成结果，该 类集成问题转化为超图的最小切割问题，在此基 算法如图1所示。 础上使用基于图论的聚类算法得到最终的聚类结 2.1基聚类的图数据表示 果91。其中用超图表示基聚类，超边表示簇，超 本文基于已有的基聚类划分计算样本之间的 边的顶点表示归属于该簇的样本，Strehl等)提 相似性，将相似度矩阵作为邻接矩阵把样本数 出HGPA、CSPA和MCLA三种基于超图的划分 据的拓扑空间表示转化为图数据表示。以下为利 方法。 用基聚类计算样本相似度矩阵的过程示例，图2 1相关工作 给出了5个样本(x,,…,)构成的数据集以及 在其上生成的基聚类集合Ⅱ={π1,2}，其中π1= 1.1图神经网络 {C,C3,Cg},π2={C,C}。 Scarselli等于2009年将神经网络和图嵌入 首先计算相交簇之间的相似度，称为样本之 模型结合提出了图神经网络(graph neural net-- 间的一阶全局相似度： wok,GNN),该模型对图的信息结构进行编码，将 xc.nxc (1) 每个节点用一个低维状态向量表示，从而学习图 XC.UXC 的表征，能以半监督的方式处理各种类型的图， 式中：C、C表示不同基聚类中的任意两个簇； 比如无环图、有向图、无向图等。近年来图神经 w,表示簇C,和簇C之间的相似度；xc,表示簇 网络已成为一种应用广泛的图分析方法，主要包 C,中的任意样本；xc,表示簇C中的任意样本。个簇，使得“同一个簇内的样本相似度较高，不同 簇间的样本相似度较低[1] ”。在实际的聚类分析 任务中，由于数据类型和结构分布的复杂性与多 样性，单一聚类方法的适用范围、可靠性和稳定 性都受到了制约，为此，研究人员结合集成学习 技术提出了聚类集成的方法[2-4]。聚类集成的目 的是将数据集的多重基聚类集成为统一的、综合 的最终聚类结果[5] ，其过程主要包括两个阶段，首 先使用不同的聚类算法或重复同一种聚类算法生 成多个基聚类；其次设计有效的一致性函数对基 聚类进行集成，获得最终聚类集成结果[6]。 一致性函数通常用来将基聚类的划分结果进 行集成，得到一个统一的聚类结果。现有的一致 性函数大体包括以下几种。1) 投票法：其基本思 想是首先根据得到的基聚类对样本划分结果进行 投票，然后计算每个样本被划分到各个簇中的投 票比例，若样本归属于某个簇的投票比例超过一 定阈值 (一般大于等于 0.5)，则将样本划分到该簇 中 [7-8]。2) 证据积累：其基本思想是同一个自然簇 中的“样本对”在不同的基聚类中可能属于同一个 簇。具体划分过程为：把每个基聚类看作是一个 独立的证据，计算“样本对”被分到同一个簇中的 次数，从而得到共协矩阵，然后使用基于最小生 成树 (mininum spaning tree, MST) 的层次聚类算法 得到最终的聚类结果[9-10]。3) 概率积累[11] ：其基本 思想是使用簇密度来计算基聚类中所有“样本对” 间的距离，生成 p-association 矩阵，依据最高寿命 标准采用 MST 合并 p-association 矩阵得到最终的 聚类结果[12]。4) 超图划分：其基本思想是先将聚 类集成问题转化为超图的最小切割问题，在此基 础上使用基于图论的聚类算法得到最终的聚类结 果 [9，13]。其中用超图表示基聚类，超边表示簇，超 边的顶点表示归属于该簇的样本，Strehl 等 [9] 提 出 HGPA、CSPA 和 MCLA 三种基于超图的划分 方法。 1 相关工作 1.1 图神经网络 Scarselli 等 [14] 于 2009 年将神经网络和图嵌入 模型结合提出了图神经网络 (graph neural net￾work，GNN)，该模型对图的信息结构进行编码，将 每个节点用一个低维状态向量表示，从而学习图 的表征，能以半监督的方式处理各种类型的图， 比如无环图、有向图、无向图等。近年来图神经 网络已成为一种应用广泛的图分析方法，主要包 括 [15] ：图递归神经网络 (graph recurrent neural net￾works, Graph RNNs)、图卷积网络 (graph confolu￾tional networks, GCN)、图自动编码器 (graph au￾toencoders, GAE) 和图强化学习 (graph reinforce￾ment learning, Graph RL)。其中图卷积网络为半监 督方法，利用节点属性和节点标签训练模型参 数，图自动编码器为无监督方法，利用自动编码 器的降维技术学习图的低维表征[16]。 1.2 图自动编码器 图自动编码器 (graph autoencoders，GAE) 在稀 疏自编码器 (sparse autoencoder，SAE)[17] 的启发下 被提出，该模型将邻接矩阵或其变体作为节点的 原始特征，将自动编码器 (autoencoder，AE) 作为 降维方法来学习低维节点表征。简单来说，图自 动编码器的基本思想是：首先输入图的邻接矩阵 和节点的特征矩阵；然后通过编码器学习节点低 维向量表示的均值和方差；最后利用解码器重构 图。因此图自动编码器能很好地处理没有监督信 息的图，同时学习图的低维表征。 2 图神经网络自监督聚类集成算法 本文提出了一种深度自监督聚类集成算法， 该算法首先根据基聚类划分计算样本之间的相似 度矩阵以表达样本之间的邻接关系，将基聚类在 特征空间的表示转化为图数据表示；然后利用图 自动编码器学习图的低维嵌入，由低维嵌入的似 然分布监督聚类集成过程，同时通过聚类集成目 标指导低维嵌入的学习过程，形成一个聚类集成 的自监督优化模型，从而优化聚类集成结果，该 算法如图 1 所示。 2.1 基聚类的图数据表示 (x1, x2,··· , x5) II= {π1, π2} π1 = { C 1 1，C 1 2，C 1 3 } π2 = { C 2 1，C 2 2 } 本文基于已有的基聚类划分计算样本之间的 相似性，将相似度矩阵作为邻接矩阵把样本数 据的拓扑空间表示转化为图数据表示。以下为利 用基聚类计算样本相似度矩阵的过程示例，图 2 给出了 5 个样本 构成的数据集以及 在其上生成的基聚类集合 ，其中 ， 。 首先计算相交簇之间的相似度，称为样本之 间的一阶全局相似度： wi j =   xCi ∩ xCj      xCi ∪ xCj    (1) xCi xCj 式中：Ci、Cj 表示不同基聚类中的任意两个簇； wi j 表示簇 Ci 和簇 Cj 之间的相似度； 表示簇 Ci 中的任意样本； 表示簇 Cj 中的任意样本。 ·1114· 智 能 系 统 学 报 第 15 卷