第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0:10.11992tis.202006050 一种深度自监督聚类集成算法 杜航原',张晶2,王文剑2 (1.山西大学计算机与信息技术学院,山西太原030006:2.山西大学计算智能与中文信息处理教育部重点实 验室,山西太原030006) 摘要:针对聚类集成中一致性函数设计问题,本文提出一种深度自监督聚类集成算法。该算法首先根据基聚 类划分结果采用加权连通三元组算法计算样本之间的相似度矩阵,基于相似度矩阵表达邻接关系,将基聚类由 特征空间中的数据表示变换至图数据表示:在此基础上,基聚类的一致性集成问题被转化为对基聚类图数据表 示的图聚类问题。为此,本文利用图神经网络构造自监督聚类集成模型,一方面采用图自动编码器学习图的低 维嵌入,依据低维嵌入似然分布估计聚类集成的目标分布:另一方面利用聚类集成目标对低维嵌入过程进行指 导,确保模型获得的图低维嵌入与聚类集成结果是一致最优的。在大量数据集上进行了仿真实验,结果表明本 文算法相比HGPA、CSPA和MCLA等算法可以进一步提高聚类集成结果的准确性。 关键词:特征空间:聚类算法:一致性函数:图表示:相似性度量:自监督学习:图数据:神经网络模型 中图分类号:TP391 文献标志码:A文章编号:1673-4785(2020)06-1113-08 中文引用格式:杜航原,张晶,王文剑.一种深度自监督聚类集成算法.智能系统学报,2020,15(6):1113-1120. 英文引用格式:DU Hangyuan,.ZHANG Jing,WANG Wenjian.A deep self-supervised clustering ensemble algorithmJ.CAAI transactions on intelligent systems,2020,15(6):1113-1120. A deep self-supervised clustering ensemble algorithm DU Hangyuan',ZHANG Jing',WANG Wenjian'2 (1.College of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Computa- tional Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China) Abstract:In this study,we propose a deep self-supervised clustering ensemble algorithm to obtain the design of a con- sensus function in a clustering ensemble.In this algorithm,a weighted connected-triple algorithm is applied to the cluster components for estimating the similarity matrix of the samples,based on which the adjacency relation can be de- termined.Thus,the cluster components can be transformed from data representation in the feature space to graph data representation.On this basis,the consistency integration problem of cluster components is transformed into a graph clus- tering problem for the graph data representation of cluster components.Further,a graph neural network is used to con- struct the self-supervised clustering ensemble model.This model uses a graph autoencoder to obtain the low-dimension- al embedding of the graph,and the target distribution of the cluster ensemble can be estimated based on the likelihood distribution generated via low-dimensional embedding.The clustering ensemble guides the learning of low-dimensional embedding.The above methods ensure that the low-dimensional embedding and clustering ensemble results obtained by the model are consistent and optimal.Simulation experiments were conducted on a large number of data sets.Results show that the proposed algorithm improves the accuracy of the clustering ensemble result compared with the accuracies obtained using algorithms such as HGPA,CSPA,and MCLA. Keywords:feature space;clustering algorithm;consistency function;graph representation;similarity measure;self-su- pervised learning;graphical data;neural network model 收稿日期:2020-06-29. 基金项目:国家自然科学基金项目(61902227,61673249 聚类分析在图像处理、机器学习、Web搜索 61773247,U1805263):山西省国际合作重点研发计 划项目(201903D421050):山西省基础研究计划项目 等众多领域得到了广泛应用,是机器学习领域一 (201901D211192):山西省应用基础研究计划项目 (201701D121053):山西省1331工程项目. 个比较活跃且极具挑战的研究方向。其主要思想 通信作者:王文剑.E-mail:wjwang(@sxu.edu.cn. 是通过计算样本间的相似度把数据集划分成若干
DOI: 10.11992/tis.202006050 一种深度自监督聚类集成算法 杜航原1 ,张晶2 ,王文剑1,2 (1. 山西大学 计算机与信息技术学院,山西 太原 030006; 2. 山西大学 计算智能与中文信息处理教育部重点实 验室,山西 太原 030006) 摘 要:针对聚类集成中一致性函数设计问题,本文提出一种深度自监督聚类集成算法。该算法首先根据基聚 类划分结果采用加权连通三元组算法计算样本之间的相似度矩阵,基于相似度矩阵表达邻接关系,将基聚类由 特征空间中的数据表示变换至图数据表示;在此基础上,基聚类的一致性集成问题被转化为对基聚类图数据表 示的图聚类问题。为此,本文利用图神经网络构造自监督聚类集成模型,一方面采用图自动编码器学习图的低 维嵌入,依据低维嵌入似然分布估计聚类集成的目标分布;另一方面利用聚类集成目标对低维嵌入过程进行指 导,确保模型获得的图低维嵌入与聚类集成结果是一致最优的。在大量数据集上进行了仿真实验,结果表明本 文算法相比 HGPA、CSPA 和 MCLA 等算法可以进一步提高聚类集成结果的准确性。 关键词:特征空间;聚类算法;一致性函数;图表示;相似性度量;自监督学习;图数据;神经网络模型 中图分类号:TP391 文献标志码:A 文章编号:1673−4785(2020)06−1113−08 中文引用格式:杜航原, 张晶, 王文剑. 一种深度自监督聚类集成算法 [J]. 智能系统学报, 2020, 15(6): 1113–1120. 英文引用格式:DU Hangyuan, ZHANG Jing, WANG Wenjian. A deep self-supervised clustering ensemble algorithm[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1113–1120. A deep self-supervised clustering ensemble algorithm DU Hangyuan1 ,ZHANG Jing2 ,WANG Wenjian1,2 (1. College of Computer and Information Technology, Shanxi University, Taiyuan 030006, China; 2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006, China) Abstract: In this study, we propose a deep self-supervised clustering ensemble algorithm to obtain the design of a consensus function in a clustering ensemble. In this algorithm, a weighted connected-triple algorithm is applied to the cluster components for estimating the similarity matrix of the samples, based on which the adjacency relation can be determined. Thus, the cluster components can be transformed from data representation in the feature space to graph data representation. On this basis, the consistency integration problem of cluster components is transformed into a graph clustering problem for the graph data representation of cluster components. Further, a graph neural network is used to construct the self-supervised clustering ensemble model. This model uses a graph autoencoder to obtain the low-dimensional embedding of the graph, and the target distribution of the cluster ensemble can be estimated based on the likelihood distribution generated via low-dimensional embedding. The clustering ensemble guides the learning of low-dimensional embedding. The above methods ensure that the low-dimensional embedding and clustering ensemble results obtained by the model are consistent and optimal. Simulation experiments were conducted on a large number of data sets. Results show that the proposed algorithm improves the accuracy of the clustering ensemble result compared with the accuracies obtained using algorithms such as HGPA, CSPA, and MCLA. Keywords: feature space; clustering algorithm; consistency function; graph representation; similarity measure; self-supervised learning; graphical data; neural network model 聚类分析在图像处理、机器学习、Web 搜索 等众多领域得到了广泛应用,是机器学习领域一 个比较活跃且极具挑战的研究方向。其主要思想 是通过计算样本间的相似度把数据集划分成若干 收稿日期:2020−06−29. 基金项目:国家自然科学基金项 目 (61902227, 61673249, 61773247,U1805263);山西省国际合作重点研发计 划项目 (201903D421050);山西省基础研究计划项目 (201901D211192);山西省应用基础研究计划项目 (201701D121053);山西省 1331 工程项目. 通信作者:王文剑. E-mail:wjwang@sxu.edu.cn. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020
·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 network,GNN),该模型对图的信息结构进行编码,将 每个节点用一个低维状态向量表示,从而学习图 的表征,能以半监督的方式处理各种类型的图, 比如无环图、有向图、无向图等。近年来图神经 网络已成为一种应用广泛的图分析方法,主要包 括 [15] :图递归神经网络 (graph recurrent neural networks, Graph RNNs)、图卷积网络 (graph confolutional networks, GCN)、图自动编码器 (graph autoencoders, GAE) 和图强化学习 (graph reinforcement 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 卷
第6期 杜航原,等:一种深度自监督聚类集成算法 ·1115· De 图 GCN Z-q (Z) 8 ↑自监督聚 编码器 类集成 解码器 L=KL (PIO) 图1自监督聚类集成模型 Fig.1 Self-supervised clustering ensemble model 式()只能计算存在交集的簇间的相似度,忽 ●x1 C ●X ●1 略了不相交的簇间的相似性关系。为此,加权连 通三元组(weighted connected-triple,WCT)算法l ●X3 X 通过利用三元连通关系来计算不相交簇之间的相 ●4 似度,即样本间的二阶全局相似度。WCT对簇 c ●X5 c C、CC.组成的三元组中C、C的之间的相似度 估算值为 图2样本的基聚类结果 WCT=min(wa,w) (2) Fig.2 Clustering results 式中:w,为簇C:和簇Ck之间的相似性;wA为簇 图3为利用基聚类集合Π生成的样本一阶全 C,和簇C,之间的相似性。WCT算法根据簇C、 局相似性关系图,该图中存在两个不相交的簇能 C之间存在的所有三元组(1,2,…,q)对C、C,之 同时与第3个簇相连,从而构成三元组。图4表 间相似度的估算值为 示簇C、C和C?之间的三元组。 0.33 C wcr-wcr (3) 029 0.33 簇C、C的相似度,即样本的二阶全局相似 度计算为 GO 0.26 WCTxDC simwcr(C.C)=wcTm (4) 0.33 式(4)中WCTmax是任意两个簇Cp、C,之间 WCTg的最大值,DCe(O,)表示置信度。图5是 do 由图3生成的样本间的二阶全局相似性关系图。 图3样本的一阶全局相似性关系 0.33 Fig.3 First-order global similarity relation of samples ○C 0.33 0.39 0.9 0.78 c( 0.25 、0.25 0.26 C ●C C 0.39 0.33 0.33 发掘关系 已知关系 图4三元组关系 图5样本的二阶全局相似性关系 Fig.4 Connected triple Fig.5 Second-order global similarity relation of samples
A 编码器 Z 解码器 • Aˆ Q P GCN L=KL (P||Q) 自监督聚 类集成 Z~q (Z) φ ( ) Z Τ 图 1 自监督聚类集成模型 Fig. 1 Self-supervised clustering ensemble model x1 x1 x3 x3 x4 x4 x5 x5 x2 x2 π2 π2 C1 1 C1 2 C3 1 C2 1 C2 2 图 2 样本的基聚类结果 Fig. 2 Clustering results C 1 1 C 1 3 C 2 2 图 3 为利用基聚类集合 Π 生成的样本一阶全 局相似性关系图,该图中存在两个不相交的簇能 同时与第 3 个簇相连,从而构成三元组。图 4 表 示簇 、 和 之间的三元组。 0.33 0.25 0.33 0.33 0.26 C1 1 C3 1 C2 1 C1 2 C2 2 图 3 样本的一阶全局相似性关系 Fig. 3 First-order global similarity relation of samples ? 0.25 0.33 C1 1 C3 1 C2 2 图 4 三元组关系 Fig. 4 Connected triple 式 (1) 只能计算存在交集的簇间的相似度,忽 略了不相交的簇间的相似性关系。为此,加权连 通三元组 (weighted connected-triple,WCT) 算法[18] 通过利用三元连通关系来计算不相交簇之间的相 似度,即样本间的二阶全局相似度。WCT 对簇 Ci、Cj、Ck 组成的三元组中 Ci、Cj 的之间的相似度 估算值为 WCTk i j = min( wik,wjk) (2) (1,2,··· ,q) 式中:wik 为簇 Ci 和簇 Ck 之间的相似性;wjk 为簇 Cj 和簇 Ck 之间的相似性。WCT 算法根据簇 Ci、 Cj 之间存在的所有三元组 对 Ci、Cj 之 间相似度的估算值为 WCTi j = ∑q k=1 WCTk i j (3) 簇 Ci、Cj 的相似度,即样本的二阶全局相似 度计算为 simWCT ( Ci ,Cj ) = WCTi j WCTmax ×DC (4) DC ∈ (0,1] 式 (4) 中 WCTmax 是任意两个簇 Cp、Cq 之间 WCTpq 的最大值, 表示置信度。图 5 是 由图 3 生成的样本间的二阶全局相似性关系图。 发掘关系 已知关系 0.39 0.39 0.9 0.33 0.26 0.25 0.78 0.33 0.33 C1 1 C2 1 C3 1 C1 2 C2 2 图 5 样本的二阶全局相似性关系 Fig. 5 Second-order global similarity relation of samples 第 6 期 杜航原,等:一种深度自监督聚类集成算法 ·1115·
·1116· 智能系统学报 第15卷 计算得到样本之间的二阶全局相似度之后, 矩阵。 依据基聚类划分结果获得样本与簇之间的二分图 解码器定义为 关系,图6为样本(x1,2,…,)与簇C、C、C、 A=sigmoid(ZZ) (8) C、C?之间的二分图关系,图中数据点与簇相连 由此得到以下重构损失: 表示该数据点在基聚类中被划分到该簇中。 ◆C 6=2-AE (9) 式中:n为样本的数量;A为图G的邻接矩阵;A C 为图G的重构邻接矩阵。 C 然后,在Z上执行k-means聚类获得初始类 别中心4=(,2,…,4,使用学生1分布测量第 c' i个样本的嵌入点,与第u个簇的类别中心4.之 ◆C 间相似性: 图6样本与簇二分关系 (1+-4) qm (10) Fig.6 Bipartite graph of the samples and dustering ∑1+k-)7 利用式(⑤)计算样本之间的相似度: 式中:q表示样本i被分配到簇“的概率,Q= 1,= [q]表示似然分布。样本i与簇u之间的相似性 sim(xi.x ) DC ∑∑sim(,R),其他 ..o 定义为 (5) 21∑9a 式中:DC∈(O,1]表示置信度;R,、R,分别表示包 Pm三 (11) 含样本x、x的簇;R,、R,分别表示包含样本x /∑ x的簇的集合。 综上,得到样本之间的相似度矩阵表示样本 式中P=P]表示目标分布。聚类集成的目标函 邻接关系,从而将基聚类特征空间表示转化至图 数定义为 数据表示为G=(V,E),其中={v}是图的节点的 L.=KL(PI2)=∑∑Pal1og (12) 集合,E={e}表示两个节点之间的边。 通过最小化分布Q和分布P之间的KL散度 2.2自监督聚类集成算法 利用图自动编码器与自监督聚类集成模型 使嵌入点更接近类别中心。在这一过程中,由分 布Q计算得到分布P,而分布P监督分布Q的更新。 对基聚类的图数据表示G进行图聚类,即利用图 2.3模型优化 自动编码器学习G的低维嵌入并由似然分布监 在训练过程中,基于L。关于“和z的梯度, 督聚类集成,同时利用聚类集成目标指导低维嵌 入学习过程,得到最终聚类集成结果。 使用随机梯度下降(stochastic gradient descent,. 本文采用的自监督聚类集成算法同时优化图 SGD)对簇中心4和低维嵌入Z进行同步更新2四 如式(13)所示。目标分布P在训练过程中监督 自动编码器和聚类集成过程,得到总体目标函数: 分布Q的更新,同时依赖于每次迭代时更新的分 L=L+yLe (6) 布Q。由于目标不断变化会阻碍学习和收敛,在 式中:L,、L分别为图自编码器的重构损失和聚类 每次迭代中用Q更新P会导致自训练过程的不 过程中的聚类损失,超参数>0。 稳定性,因此本文设置了一个迭代间隔T,每 在自监督聚类集成过程中,首先训练图自动 T次迭代更新一次P,以避免上述可能出现的不 编码器得到低维嵌入Z=(2,2,…,zm),图自动编 稳定性。 码器由图卷积网络(graph convolutional network, GCN编码器和简单的内积解码器组成P0,编码器 8L_ a + X(pa-q)(Z:-μ)】 定义为 aL k- Z=A'ReLU(A'XWo)W (7) X(Pi-qin(zi-uu) dμ 式中:ReLU(=max(0,)和A'=D-1/2AD-12是对称 (13) 归一化的邻接矩阵,D为度矩阵,X输入为单位 综上所述,本文算法流程如算法1所示
(x1, x2,··· , x5) C 1 1 C 1 2 C 1 3 C 2 1 C 2 2 计算得到样本之间的二阶全局相似度之后, 依据基聚类划分结果获得样本与簇之间的二分图 关系,图 6 为样本 与簇 、 、 、 、 之间的二分图关系,图中数据点与簇相连 表示该数据点在基聚类中被划分到该簇中。 x1 x2 x3 x4 x5 C1 1 C3 1 C2 1 C1 2 C2 2 图 6 样本与簇二分关系 Fig. 6 Bipartite graph of the samples and dustering 利用式 (5) 计算样本之间的相似度: sim( xi , xj ) = 1 , xi = xj DC ℜxi ℜxj ∑ Rxi ∈ℜx i ∑ Rx j ∈ℜx j sim( Rxi ,Rxj ) ,其他 (5) Rxi Rxj ℜxi ℜxj 式中:DC∈(0, 1] 表示置信度; 、 分别表示包 含样本 xi、xj 的簇; 、 分别表示包含样本 xi、 xj 的簇的集合。 综上,得到样本之间的相似度矩阵表示样本 邻接关系,从而将基聚类特征空间表示转化至图 数据表示为 G=(V, E),其中 V={vi}是图的节点的 集合,E={eij}表示两个节点之间的边。 2.2 自监督聚类集成算法 利用图自动编码器与自监督聚类集成模型[19] 对基聚类的图数据表示 G 进行图聚类,即利用图 自动编码器学习 G 的低维嵌入并由似然分布监 督聚类集成,同时利用聚类集成目标指导低维嵌 入学习过程,得到最终聚类集成结果。 本文采用的自监督聚类集成算法同时优化图 自动编码器和聚类集成过程,得到总体目标函数: L = Lr +γLc (6) 式中:Lr、Lc 分别为图自编码器的重构损失和聚类 过程中的聚类损失,超参数 γ>0。 Z = (z1,z2,··· ,zm) 在自监督聚类集成过程中,首先训练图自动 编码器得到低维嵌入 ,图自动编 码器由图卷积网络 (graph convolutional network, GCN) 编码器和简单的内积解码器组成[20] ,编码器 定义为 Z = A ′ReLU(A ′XW0)W1 (7) A ′ = D −1/2AD 式中:ReLU −1/2 (·)=max(0,·) 和 是对称 归一化的邻接矩阵,D 为度矩阵,X 输入为单位 矩阵。 解码器定义为 Aˆ = sigmoid( ZZT ) (8) 由此得到以下重构损失: Lr = 1 n ∑n i=1 Aˆ i j − Ai j 2 2 (9) 式中:n 为样本的数量;A 为图 G 的邻接矩阵; Aˆ 为图 G 的重构邻接矩阵。 µ = (µ1, µ2, ··· , µn) 然后,在 Z 上执行 k-means 聚类获得初始类 别中心 ,使用学生 t 分布测量第 i 个样本的嵌入点 zi 与第 u 个簇的类别中心 μu 之 间相似性[21] : qiu = (1+∥zi− µu 2 ) −1 ∑ i ( 1+∥zi −µk∥ 2 )−1 (10) 式中:qi u 表示样本 i 被分配到簇 u 的概率,Q= [qiu] 表示似然分布。样本 i 与簇 u 之间的相似性 定义为 piu = q 2 iu/ ∑ i qiu ∑ k q 2 ik/ ∑ i qik (11) 式中 P=[piu] 表示目标分布。聚类集成的目标函 数定义为 Lc = KL(P||Q) = ∑ i ∑ u piu log piu qiu (12) 通过最小化分布 Q 和分布 P 之间的 KL 散度 使嵌入点更接近类别中心。在这一过程中,由分 布 Q 计算得到分布 P,而分布 P 监督分布 Q 的更新。 2.3 模型优化 在训练过程中,基于 Lc 关于 u 和 z 的梯度, 使用随机梯度下降 (stochastic gradient descent, SGD) 对簇中心 μ 和低维嵌入 Z 进行同步更新[22] , 如式 (13) 所示。目标分布 P 在训练过程中监督 分布 Q 的更新,同时依赖于每次迭代时更新的分 布 Q。由于目标不断变化会阻碍学习和收敛,在 每次迭代中用 Q 更新 P 会导致自训练过程的不 稳定性,因此本文设置了一个迭代间 隔 T, 每 T 次迭代更新一次 P,以避免上述可能出现的不 稳定性。 ∂L ∂zi = α+1 α ∑ u ( 1+ ∥zi +µu∥ 2 α )−1 ×(piu −qiu) (zi −µu) ∂L ∂µu = − α+1 α ∑ i ( 1+ ∥zi −µu∥ 2 α )−1 ×(piu −qiu) (zi −µu) (13) 综上所述,本文算法流程如算法 1 所示。 ·1116· 智 能 系 统 学 报 第 15 卷
第6期 杜航原,等:一种深度自监督聚类集成算法 ·1117· 算法1自监督聚类算法 度量: 输入基聚类Ⅱ={ππ2…πn},类别数k,送代 次数Iter,目标分布P更新间隔T,超参数: 6(s:,map(r)) 输出最后聚类集成结果。 ACC= (14) 1)使用式(1(⑤)计算相似度矩阵A; 式中:、S,分别表示数据x,聚类得到的标签和真 2)最小化式(9)得到自动编码器的低维嵌入 实标签;n表示数据总个数;map表示最佳类标的 Z,基于Z计算初始类别中心; 重现分配;δ表示指示函数,表示为 3)for /=0 to Iter-1 do 1, 6(x,y= x=y 使用式(10)基于Z和μ计算分布Q: 10,其他 (15) if 1%T-=0 then 调整兰德系数度量真实标签和聚类标签相似 使用式(11)基于分布Q计算分布P: 性,定义如下: end if 使用式(12)计算聚类集成损失函数L: ARI= 1j1 最小化式(6更新整个算法 (16) end if p+)-n 4)迭代完成后得到聚类集成结果。 式中:p-2(小n2标 3实验结果与分析 准互信息用来度量真实样本簇划分与聚类结果之 3.1数据集 间的相近程度: 为验证算法的有效性,本文选用UCI数据库 ∑b" 中的5个真实数据集进行测试,表1给出了实验 NMI= =1j=1 (17) 中选用的UCI数据集描述。 b 表1UCI数据集描述 n- ",lb Table 1 Description of the UCI data sets 式中:n表示聚类结果的第i个簇中包含原数据 数据集 样本量 特征维度 目标簇数 集类标签为j的样本总数;n,表示聚类结果的第 Wine 178 3 i个簇的样本总数;n,表示原数据集类标签为j的 Glass 214 9 6 样本总数;n表示样本总数;I和J分别表示聚类 Wdbc 569 30 2 得到的簇个数和原数据集的类个数。 Yeast 1484 8 10 ACC、ARI、NM的取值范围为[O,1],且取值 Segment 2310 19 越接近1,表明算法在数据集中获得的聚类效果 7 越好。 在仿真实验中选取HGPA1、CSPA[] 3.3实验结果与分析 MCLA)、基于投票的聚类集成算法I)和谱聚类 对本文算法进行如下设置:将置信度DC的 集成算法PI与本文方法进行对比,HGPA、CSPA、 值设置为0.9,收敛阈值tol设置为0.1%,目标分 MCLA算法属于基于超图的聚类集成算法,其原 布P的“更新间隔设置T”设置为5。为了确定超 理是根据基聚类构造超图,对超图进行分割;基 参数y的取值,在实验中将y分别设置为2、4、6、 于投票的聚类集成算法根据基聚类的划分进行投 8、10,在不同y下获得的ARI、NMI和ACC值如 票,得到样本的集成结果;谱聚类集成算法利用 图7所示。 基聚类得到样本的图数据表示,对图进行分割。 由图7可以看出,当超参数<8时,本文算法 3.2评价指标 在5个数据集上的ARI、NMI和ACC取值随着 本文使用准确率(accuracy,ACC)、调整兰德 y值的增加整体上呈上升趋势。当超参数=8时, 系数(adjusted rand index,ARI)以及标准互信息 取值达到峰值,聚类效果最佳。而当y的取值继 (normalized mutual information,NM⑩)3个指标对各 续增加到10时,取值没有呈现明显的增长趋势。 算法的聚类集成结果进行评价与分析。准确率对 这是因为在自监督聚类集成过程中,通过最小化 样本的真实标签和生成标签的匹配程度进行 目标损失函数L达到优化图自动编码器与聚类集
算法 1 自监督聚类算法 输入 基聚类 Π = {π1π2 ···πn} ,类别数 k,迭代 次数 Iter,目标分布 P 更新间隔 T,超参数 γ; 输出 最后聚类集成结果。 1) 使用式 (1)~(5) 计算相似度矩阵 A; 2) 最小化式 (9) 得到自动编码器的低维嵌入 Z,基于 Z 计算初始类别中心 μ; 3) for l=0 to Iter-1 do 使用式 (10) 基于 Z 和 μ 计算分布 Q; if l% T==0 then 使用式 (11) 基于分布 Q 计算分布 P; end if 使用式 (12) 计算聚类集成损失函数 Lc; 最小化式 (6) 更新整个算法 end if 4) 迭代完成后得到聚类集成结果。 3 实验结果与分析 3.1 数据集 为验证算法的有效性,本文选用 UCI 数据库 中的 5 个真实数据集进行测试,表 1 给出了实验 中选用的 UCI 数据集描述。 表 1 UCI 数据集描述 Table 1 Description of the UCI data sets 数据集 样本量 特征维度 目标簇数 Wine 178 13 3 Glass 214 9 6 Wdbc 569 30 2 Yeast 1484 8 10 Segment 2310 19 7 在仿真实验中选 取 HGPA [ 9 ] 、 CSPA [ 9 ] 、 MCLA[9] 、基于投票的聚类集成算法[13] 和谱聚类 集成算法[23] 与本文方法进行对比,HGPA、CSPA、 MCLA 算法属于基于超图的聚类集成算法,其原 理是根据基聚类构造超图,对超图进行分割;基 于投票的聚类集成算法根据基聚类的划分进行投 票,得到样本的集成结果;谱聚类集成算法利用 基聚类得到样本的图数据表示,对图进行分割。 3.2 评价指标 本文使用准确率 (accuracy,ACC)、调整兰德 系数 (adjusted rand index,ARI) 以及标准互信息 (normalized mutual information,NMI)3 个指标对各 算法的聚类集成结果进行评价与分析。准确率对 样本的真实标签和生成标签的匹配程度进行 度量: ACC = ∑n i=1 δ ( si ,map(ri) ) n (14) 式中:ri、si 分别表示数据 xi 聚类得到的标签和真 实标签;n 表示数据总个数;map 表示最佳类标的 重现分配;δ 表示指示函数,表示为 δ(x, y) = { 1, 0, x = y 其他 (15) 调整兰德系数度量真实标签和聚类标签相似 性,定义如下: ARI = ∑I i=1 ∑J j=1 ( ni j 2 ) −η 1 2 (ρ+ϑ)−η (16) ρ = ∑I i=1 ( ni 2 ) ϑ = ∑J j=1 ( nj 2 ) η = 2ρϑ n(n−1) 式中: 、 、 。标 准互信息用来度量真实样本簇划分与聚类结果之 间的相近程度: NMI = ∑I i=1 ∑J j=1 ni jlb nni j ninj vt∑I i=1 ni lbni n ∑J j=1 nj lb nj n (17) 式中:nij 表示聚类结果的第 i 个簇中包含原数据 集类标签为 j 的样本总数;ni 表示聚类结果的第 i 个簇的样本总数;nj 表示原数据集类标签为 j 的 样本总数;n 表示样本总数;I 和 J 分别表示聚类 得到的簇个数和原数据集的类个数。 ACC、ARI、NMI 的取值范围为 [0,1],且取值 越接近 1,表明算法在数据集中获得的聚类效果 越好。 3.3 实验结果与分析 对本文算法进行如下设置:将置信度 DC 的 值设置为 0.9,收敛阈值 tol 设置为 0.1%,目标分 布 P 的“更新间隔设置 T ”设置为 5。为了确定超 参数 γ 的取值,在实验中将 γ 分别设置为 2、4、6、 8、10,在不同 γ 下获得的 ARI、NMI 和 ACC 值如 图 7 所示。 由图 7 可以看出,当超参数 γ<8 时,本文算法 在 5 个数据集上的 ARI、NMI 和 ACC 取值随着 γ 值的增加整体上呈上升趋势。当超参数 γ=8 时, 取值达到峰值,聚类效果最佳。而当 γ 的取值继 续增加到 10 时,取值没有呈现明显的增长趋势。 这是因为在自监督聚类集成过程中,通过最小化 目标损失函数 L 达到优化图自动编码器与聚类集 第 6 期 杜航原,等:一种深度自监督聚类集成算法 ·1117·
·1118- 智能系统学报 第15卷 成模块的目的,通过L的定义可知,如果y的值过 表2不同算法的ARI比较 小,会使聚类损失对低维嵌人学习过程影响过大 Table 2 Comparison of different algorithms with respect to ARI 从而导致空间扭曲;而当y取值过大时,会影响低 维嵌入空间对聚类损失的优化,从而导致聚类集 数据集本文算法HGPA CSPA MCLA Voting Spectral 成结果变差。分别使用本文算法与5种对比算法 Wine 0.684 0.3010.3690.370 0.3700.422 在5个数据集上进行聚类划分,各方法聚类集成 Glass 0.461 0.1030.1300.171 0.1100.184 结果的ARL、NM和ACC值如表2~4所示。 Wdbc 0.687 0.000 0.1350.4900.491 0.501 0.9 Yeast 0.587 0.1320.2100.3620.2100.380 0.8 0.7 Segment 0.689 0.3510.3530.3900.3630.510 ◆ARI 0.5 一NMI 0.4 ACC 表3不同算法的NMⅡ比较 0.3 8 10 Table 3 Comparison of different algorithms with respect to NMI (a)超参数y的取值对数据集Wine的影响 0.7r 数据集本文算法HGPA CSPA MCLA Voting Spectral 0.6 Wine 0.785 0.3810.3940.426 0.426 0.564 0.5 Glass 0.495 0.2190.2410.3210.2400.256 ◆—ARI 0.3 -NMI Wdbc 0.842 0.0010.0930.4650.465 0.650 -ACC 02 6 8 10 Yeast 0.542 0.1220.1950.2910.1960.352 (b)超参数y的取值对数据集Glass的影响 Segment 0.852 0.4710.4830.5580.4920.658 0.9 0.8 0.7 表4不同算法的ACC比较 号0.6 Table 4 Comparison of different algorithms with respect 0.5 I一NMI to ACC 0.4 ★ACC 0.3 0 10 数据集本文算法HGPA CSPA MCLA Voting Spectral (c)超参数y的取值对数据集Wdbc的影响 Wine 0.874 0.4670.4850.587 0.549 0.682 0.7r Glass 0.612 0.3140.3420.401 0.365 0.385 0.6 Wdbc 0.820 0.010 0.157 0.694 0.658 0.741 ◆一ARI 0.4 ■一NMI ACC Yeast 0.621 0.2560.3510.4150.3540.582 0.3 8 10 Segment 0.834 0.6200.6890.7540.7100.852 (d)超参数y的取值对数据集Yeast的影响 0.9 表2~4中加粗的数字分别表示不同算法在每 0.8 个数据集上取得的最优值。由这些实验结果可以 看出,本文算法在各数据集上获得的ARI、NMI 0.6 ARI 和ACC值整体优于其他5种算法。其中,本文算 一NMI 0.4 —ACC 法在5个数据集上的ARI和NMI取值相较于其 0.3 他算法均有明显提升,仅在Segment数据集的 10 ACC取值稍逊于Spectral算法。这是由于本文算 (e)超参数y的取值对数据集Segment的影响 法生成的基聚类的图数据表示完整反映了样本的 图7超参数?的取值对数据集聚类的影响 全局相似关系,使用了处理属性缺失的图数据更 Fig.7 Effect of parameter y on data sets 具有优势的图神经网络,并且自监督模型使图自
成模块的目的,通过 L 的定义可知,如果 γ 的值过 小,会使聚类损失对低维嵌入学习过程影响过大 从而导致空间扭曲;而当 γ 取值过大时,会影响低 维嵌入空间对聚类损失的优化,从而导致聚类集 成结果变差。分别使用本文算法与 5 种对比算法 在 5 个数据集上进行聚类划分,各方法聚类集成 结果的 ARI、NMI 和 ACC 值如表 2~4所示。 0.3 0.4 0.5 0.6 0.7 0.8 0.9 2 4 6 8 10 ARI NMI ACC ARI NMI ACC ARI NMI ACC ARI NMI ACC ARI NMI ACC γ γ γ Wine 2 4 6 8 10 2 4 6 8 10 2 4 6 8 10 γ γ 2 4 6 8 10 (a) 超参数 γ 的取值对数据集 Wine 的影响 0.2 0.3 0.4 0.5 0.6 0.7 (b) 超参数 γ 的取值对数据集 Glass 的影响 0.3 0.4 0.5 0.6 0.7 0.8 0.9 (c) 超参数 γ 的取值对数据集 Wdbc 的影响 0.3 0.4 0.5 0.6 0.7 (d) 超参数 γ 的取值对数据集 Yeast 的影响 0.3 0.4 0.5 0.6 0.7 0.8 0.9 (e) 超参数 γ 的取值对数据集 Segment 的影响 Glass Wdbc Yeast Segment 图 7 超参数 γ 的取值对数据集聚类的影响 Fig. 7 Effect of parameter γ on data sets 表 2 不同算法的 ARI 比较 Table 2 Comparison of different algorithms with respect to ARI 数据集 本文算法 HGPA CSPA MCLA Voting Spectral Wine 0.684 0.301 0.369 0.370 0.370 0.422 Glass 0.461 0.103 0.130 0.171 0.110 0.184 Wdbc 0.687 0.000 0.135 0.490 0.491 0.501 Yeast 0.587 0.132 0.210 0.362 0.210 0.380 Segment 0.689 0.351 0.353 0.390 0.363 0.510 表 3 不同算法的 NMI 比较 Table 3 Comparison of different algorithms with respect to NMI 数据集 本文算法 HGPA CSPA MCLA Voting Spectral Wine 0.785 0.381 0.394 0.426 0.426 0.564 Glass 0.495 0.219 0.241 0.321 0.240 0.256 Wdbc 0.842 0.001 0.093 0.465 0.465 0.650 Yeast 0.542 0.122 0.195 0.291 0.196 0.352 Segment 0.852 0.471 0.483 0.558 0.492 0.658 表 4 不同算法的 ACC 比较 Table 4 Comparison of different algorithms with respect to ACC 数据集 本文算法 HGPA CSPA MCLA Voting Spectral Wine 0.874 0.467 0.485 0.587 0.549 0.682 Glass 0.612 0.314 0.342 0.401 0.365 0.385 Wdbc 0.820 0.010 0.157 0.694 0.658 0.741 Yeast 0.621 0.256 0.351 0.415 0.354 0.582 Segment 0.834 0.620 0.689 0.754 0.710 0.852 表 2~4 中加粗的数字分别表示不同算法在每 个数据集上取得的最优值。由这些实验结果可以 看出,本文算法在各数据集上获得的 ARI、NMI 和 ACC 值整体优于其他 5 种算法。其中,本文算 法在 5 个数据集上的 ARI 和 NMI 取值相较于其 他算法均有明显提升,仅在 Segment 数据集的 ACC 取值稍逊于 Spectral 算法。这是由于本文算 法生成的基聚类的图数据表示完整反映了样本的 全局相似关系,使用了处理属性缺失的图数据更 具有优势的图神经网络,并且自监督模型使图自 ·1118· 智 能 系 统 学 报 第 15 卷
第6期 杜航原,等:一种深度自监督聚类集成算法 ·1119· 动编码器中的信息传递和数据映射服从最终聚类 427-436 集成目标,从而使产生的低维嵌入有利于获得最 [5]FRIGUI H.KRISHNAPURAM R.A robust competitive 优的聚类集成结果。而HGPA、CSPA、MCLA方 clustering algorithm with applications in computer 法采用的图分割算法趋向于将图形划分为大小相 vision[J].IEEE transactions on pattern analysis and ma- 似的簇,对于真实分布大小不一的簇聚类结果较 chine intelligence,1999,21(5):450-465. 差;投票法只依赖基聚类的划分结果,没有充分 挖掘样本之间的相似性关系;谱聚类集成算法的 [6]FERN X Z,LIN Wei.Cluster ensemble selection[J].Stat- 聚类集成结果很大程度上受到相似度矩阵计算结 istical analysis and data mining,2008,1(3):128-141 果的影响。 [7]罗会兰.聚类集成关键技术研究[D].杭州:浙江大学, 2007 4结束语 LUO Huilan.Research on key technologies of clustering 本文针对聚类集成的一致性函数设计问题, ensemble[D].Hangzhou:Zhejiang University,2007. 提出了一种基于图神经网络的聚类集成算法,主 [8]FRED A L N.Finding consistent clusters in data 要工作包括: partitions[C]//Proceedings of the 2nd International Work- 1)根据基聚类划分结果计算样本之间的相似 shop on Multiple Classifier Systems.Cambridge,UK, 性,完整地反映了样本之间的一阶与二阶相似 2001:309-318 性,在此基础上,用相似度矩阵表示样本之间的 邻接关系,将基聚类在拓扑空间中的表示转化为 [9]STREHL A,GHOSH J.Cluster ensembles-a knowledge 图数据表示,通过图聚类获得聚类集成的最优解; reuse framework for combining multiple partitions[J]. 2)利用图神经网络模型构造自监督聚类集成 Journal of machine learning research,2003,3:583-617. 算法,图自动编码器在聚类集成结果中很好地保 [10]FRED A L N,JAIN A K.Data clustering using evidence 留了样本在空间中的结构,并且自监督优化模型 Accumulation[C]//Proceedings of the 16th International 使图自动编码器中的低维学习服从聚类集成的目 Conference on Pattern Recognition(ICPR'02).Quebec 标,从而得到最优的聚类集成结果; City,Canada,2002:276-280. 3)在数据集上进行了仿真实验,结果表明本 [11]WANG Xi,YANG Chunyu,ZHOU Jie.Clustering ag- 文算法提升了聚类集成结果的准确性。 然而,本文算法的空间复杂度较大,在未来的 gregation by probability accumulation[].Pattern recogni- 工作中,考虑如何降低算法的空间复杂度并且将 tion,2009.42(5:668-675. 算法应用于实际问题。 [12]杨草原,刘大有,杨博,等.聚类集成方法研究仞.计算 机科学,2011.38(2少:166-170 参考文献: YANG Caoyuan,LIU Dayou,YANG Bo,et al.Research [1]HAN Jiawei,KAMBER M,PEI Jian.Data mining:con- on cluster aggregation approaches[J].Computer science, cepts and techniques[M].3rd ed.Amsterdam:Elsevier, 2011,38(2):166-170. 2012:223-259. [13]ZHOU Zhihua,TANG Wei.Clusterer ensemble[J]. [2]孙吉贵,刘杰,赵连宇.聚类算法研究[.软件学报, Knowledge-based systems,2006,19(1):77-83. 2008,19(1):48-61 [14]SCARSELLI F,GORI M,TSOI A C,et al.The graph SUN Jigui,LIU Jie,ZHAO Lianyu.Clustering algorithms neural network model[J].IEEE Transactions on neural research[J].Journal of software,2008,19(1):48-61 networks.2009,20(161-80. [3]JUDD D.MCKINLEY P K,JAIN A K.Large-scale paral- [15]WU Z,PAN S,CHEN F.A comprehensive survey on lel data clustering[J].IEEE transactions on pattern analysis graph neural networks[J].IEEE transactions on neural and machine intelligence,1998,20(8):871-876. networks and learning systems,2019(02):4-24. [4]BHATIA S K,DEOGUN J S.Conceptual clustering inin- [16]VINCENT P,LAROCHELLE H,BENGIO Y,et al.Ex- formation retrieval[J].IEEE transactions on systems,man, tracting and composing robust features with denoising au- and cybernetics,part B(cybernetics),1998,28(3): toencoders[Cl//Proceedings of the 25th International Con-
动编码器中的信息传递和数据映射服从最终聚类 集成目标,从而使产生的低维嵌入有利于获得最 优的聚类集成结果。而 HGPA、CSPA、MCLA 方 法采用的图分割算法趋向于将图形划分为大小相 似的簇,对于真实分布大小不一的簇聚类结果较 差;投票法只依赖基聚类的划分结果,没有充分 挖掘样本之间的相似性关系;谱聚类集成算法的 聚类集成结果很大程度上受到相似度矩阵计算结 果的影响。 4 结束语 本文针对聚类集成的一致性函数设计问题, 提出了一种基于图神经网络的聚类集成算法,主 要工作包括: 1) 根据基聚类划分结果计算样本之间的相似 性,完整地反映了样本之间的一阶与二阶相似 性,在此基础上,用相似度矩阵表示样本之间的 邻接关系,将基聚类在拓扑空间中的表示转化为 图数据表示,通过图聚类获得聚类集成的最优解; 2) 利用图神经网络模型构造自监督聚类集成 算法,图自动编码器在聚类集成结果中很好地保 留了样本在空间中的结构,并且自监督优化模型 使图自动编码器中的低维学习服从聚类集成的目 标,从而得到最优的聚类集成结果; 3) 在数据集上进行了仿真实验,结果表明本 文算法提升了聚类集成结果的准确性。 然而,本文算法的空间复杂度较大,在未来的 工作中,考虑如何降低算法的空间复杂度并且将 算法应用于实际问题。 参考文献: HAN Jiawei, KAMBER M, PEI Jian. Data mining: concepts and techniques[M]. 3rd ed. Amsterdam: Elsevier, 2012: 223−259. [1] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究 [J]. 软件学报, 2008, 19(1): 48–61. SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering algorithms research[J]. Journal of software, 2008, 19(1): 48–61. [2] JUDD D, MCKINLEY P K, JAIN A K. Large-scale parallel data clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 1998, 20(8): 871–876. [3] BHATIA S K, DEOGUN J S. Conceptual clustering in information retrieval[J]. IEEE transactions on systems, man, and cybernetics, part B (cybernetics), 1998, 28(3): [4] 427–436. FRIGUI H, KRISHNAPURAM R. A robust competitive clustering algorithm with applications in computer vision[J]. IEEE transactions on pattern analysis and machine intelligence, 1999, 21(5): 450–465. [5] FERN X Z, LIN Wei. Cluster ensemble selection[J]. Statistical analysis and data mining, 2008, 1(3): 128–141. [6] 罗会兰. 聚类集成关键技术研究 [D]. 杭州: 浙江大学, 2007. LUO Huilan. Research on key technologies of clustering ensemble[D]. Hangzhou: Zhejiang University, 2007. [7] FRED A L N. Finding consistent clusters in data partitions[C]//Proceedings of the 2nd International Workshop on Multiple Classifier Systems. Cambridge, UK, 2001: 309−318. [8] STREHL A, GHOSH J. Cluster ensembles-a knowledge reuse framework for combining multiple partitions[J]. Journal of machine learning research, 2003, 3: 583–617. [9] FRED A L N, JAIN A K. Data clustering using evidence Accumulation[C]//Proceedings of the 16th International Conference on Pattern Recognition (ICPR’02). Quebec City, Canada, 2002: 276−280. [10] WANG Xi, YANG Chunyu, ZHOU Jie. Clustering aggregation by probability accumulation[J]. Pattern recognition, 2009, 42(5): 668–675. [11] 杨草原, 刘大有, 杨博, 等. 聚类集成方法研究 [J]. 计算 机科学, 2011, 38(2): 166–170. YANG Caoyuan, LIU Dayou, YANG Bo, et al. Research on cluster aggregation approaches[J]. Computer science, 2011, 38(2): 166–170. [12] ZHOU Zhihua, TANG Wei. Clusterer ensemble[J]. Knowledge-based systems, 2006, 19(1): 77–83. [13] SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model[J]. IEEE Transactions on neural networks, 2009, 20(1): 61–80. [14] WU Z , PAN S , CHEN F. A comprehensive survey on graph neural networks[J]. IEEE transactions on neural networks and learning systems, 2019(02): 4–24. [15] VINCENT P, LAROCHELLE H, BENGIO Y, et al. Extracting and composing robust features with denoising autoencoders[C]//Proceedings of the 25th International Con- [16] 第 6 期 杜航原,等:一种深度自监督聚类集成算法 ·1119·
·1120· 智能系统学报 第15卷 ference on Machine Learning.Helsinki,Finland,2008 [23]VON LUXBURG U.A tutorial on spectral clustering[J]. 1096-1103 Statistics and computing,2007,17(4):395-416. [17]TIAN Fei,GAO Bin,CUI Qing,et al.Learning deep rep- 作者简介: resentations for graph clustering[C]//Proceedings of the 杜航原,副教授,博士,主要研究 28th AAAI Conference on Artificial Intelligence.Quebec 方向为机器学习、社会网络。主持和 参与国家级、省部级科研项目7项。 City,Canada,2014:1293-1299. 发表学术论文10余篇。 [18]IAM-ON N.BOONGOEN T.GARRETT S.LCE:a link- based cluster ensemble method for improved gene expres- sion data analysis[J].Bioinformatics,2010,26(12): 1513-1519. 张晶,硕士研究生,主要研究方向 为数据挖掘与机器学习。 [19]WANG Chun,PAN Shirui,HU Ruiqi,et al.Attributed graph clustering:a deep Attentional embedding approach[Cl//Proceedings of the 28th International Joint Conference on Artificial Intelligence.Macao,China, 2019:3670-3676. 王文剑,教授,博士生导师,博士, [20]KIPF T N,WELLING M.Variational graph auto-en- 国家自然科学基金委信息学部自动化 coders[J/OLl.Available:http://axrxiv.org/abs/1611.07308. 学科会评专家,中国人工智能学会理 2016. 事、中国人工智能学会机器学习专委 会常务委员、知识工程与分布智能专 [21]VAN DER MAATEN L,HINTON G.Visualizing data 委会委员、粗糙集与软计算专业委员 using t-SNE[J].Journal of machine learning research, 会委员,中国计算机学会人工智能与 2008,9(86):2579-2605. 模式识别专委会委员,中国计算机学会太原分部监督委员会 主席、ACM太原分部副主席,并担任多个国际国内学术会议 [22]XIE J,GIRSHICK R,FARHADI A.Unsupervised deep 的程序委员会主席或委员,主要研究方向为机器学习与数据 embedding for clustering analysis[]].Computer science, 挖掘。主持国家自然科学基金项目4项。发表学术论文 2015:478-487. 150余篇
ference on Machine Learning. Helsinki, Finland, 2008: 1096−1103. TIAN Fei, GAO Bin, CUI Qing, et al. Learning deep representations for graph clustering[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence. Québec City, Canada, 2014: 1293−1299. [17] IAM-ON N, BOONGOEN T, GARRETT S. LCE: a linkbased cluster ensemble method for improved gene expression data analysis[J]. Bioinformatics, 2010, 26(12): 1513–1519. [18] WANG Chun, PAN Shirui, HU Ruiqi, et al. Attributed graph clustering: a deep Attentional embedding approach[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. Macao, China, 2019: 3670−3676. [19] KIPF T N, WELLING M. Variational graph auto-encoders[J/OL]. Available: http://axrxiv.org/abs/1611.07308. 2016. [20] VAN DER MAATEN L, HINTON G. Visualizing data using t-SNE[J]. Journal of machine learning research, 2008, 9(86): 2579–2605. [21] XIE J, GIRSHICK R, FARHADI A. Unsupervised deep embedding for clustering analysis[J]. Computer science, 2015: 478–487. [22] VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4): 395–416. [23] 作者简介: 杜航原,副教授,博士,主要研究 方向为机器学习、社会网络。主持和 参与国家级、省部级科研项目 7 项。 发表学术论文 10 余篇。 张晶,硕士研究生,主要研究方向 为数据挖掘与机器学习。 王文剑,教授,博士生导师,博士, 国家自然科学基金委信息学部自动化 学科会评专家,中国人工智能学会理 事、中国人工智能学会机器学习专委 会常务委员、知识工程与分布智能专 委会委员、粗糙集与软计算专业委员 会委员,中国计算机学会人工智能与 模式识别专委会委员,中国计算机学会太原分部监督委员会 主席、ACM 太原分部副主席,并担任多个国际国内学术会议 的程序委员会主席或委员,主要研究方向为机器学习与数据 挖掘。主持国家自然科学基金项目 4 项。发表学术论文 150 余篇。 ·1120· 智 能 系 统 学 报 第 15 卷