基于压缩感知的社团结构深度学习方法

张梁梁,冯 径,胡谷雨

(解放军理工大学a.气象海洋学院;b.指挥信息系统学院,南京210007)

基于压缩感知的社团结构深度学习方法

张梁梁a,冯 径a,胡谷雨b

(解放军理工大学a.气象海洋学院;b.指挥信息系统学院,南京210007)

传统社团结构发现算法复杂度高,且只适合处理小规模低维度的社会网络数据,而无法处理大规模高维度实际网络数据。为此,提出一种基于压缩感知的社团结构深度学习方法。通过随机测量矩阵对社会网络数据进行特征降维,并使用深度信度网(DBN)对降维后的特征样本集进行无监督学习,利用带类标的小样本集进行有监督调优。仿真结果表明,随机测量方法对高维稀疏特征具有较好的降维效果,DBN对大规模数据集具有较好的处理性能,该方法适合对大规模高维度实际社会网络数据进行高效处理。

压缩感知;深度学习;社团发现;深度信念网;社团结构;模块度

1 概述

近年来,人们对社会网络的研究已不再局限于网络结构的基本理论,而是转向研究规模尺度大、连接结构复杂的实际网络。实际网络通常由若干个社团组成[1]。通过剖析社会网络的社团结构,可以进一步挖掘网络的隐含信息,有助于分析网络特性,准确理解社会网络的组织方式,对改善现有网络性能和预测网络行为有重要意义。

目前一些算法能从小规模社会网络中正确提取社团结构,这些算法大致可分为3类:基于图论的方法,如GN算法[2]和FastGN算法[3];基于矩阵分解的方法,如SymNMF算法[4];基于优化的划分方法,如N-Cut算法和A-Cut算法[5]等。人们对网络结构演化过程中展现出的特性给予了极大的关注[6]。然而这些算法在网络规模较小时,社团发现效率较高,但随着网络规模增大,它们的效率明显下降,算法复杂度随着网络维度的增长,呈指数级增长。

为了从大规模高维度社会网络中高效提取社团结构,本文提出基于压缩感知的社团结构深度学习方法。该方法从两方面提升大规模高维度社会网络中社团结构提取的效率:一方面,利用压缩感知理论中的随机测量方法对高维度社会网络特征进行降维;另一方面,利用深度学习理论中的DBN模型[7]对降维后的大规模社会网络特征进行学习和预测。

2 理论基础

2.1 背景介绍

压缩感知理论[8]是应用数学和信号处理领域一个热门的研究方向,这一理论对于稀疏性信息的处理具有明显优势。对于可压缩的信号,压缩感知可以通过远低于奈奎斯特准则的方式进行数据采样,仍能精确恢复出原始信号。对于社会关系数据,其规模越大,数据越稀疏。比如,平时研究较多的MovieLens数据集的稀疏度4.5%,Netflix的稀疏度为1.2%,Bibsonomy的稀疏度为0.35%,Delicious的稀疏度为0.046%。利用压缩感知中的随机测量矩阵对社会关系数据进行降维处理,可提取高维数据中的本质信息,使算法适合处理高维数据。

深度学习[9]是一类新兴的多层神经网络学习算法。该算法解决了传统神经网络训练算法的局部最小性问题和无监督训练问题,引起机器学习领域的广泛关注,并已在图像、语音、语言处理领域以及大数据处理领域取得了很多成果。深度学习在预训练阶段采用无监督学习算法,在最后阶段采用一小部分有类标样本进行有监督调优训练。预训练过程很适合对大规模无类标社会网络数据进行无监督学习,而最后阶段的有监督调优训练需要小部分有类标样本,这可通过从大规模社会网络数据中选择代表集,并通过前文介绍的传统算法提取出代表集的社团结构,从而获得有类标的小样本。

2.2 随机测量方法

文献[8]对压缩感知理论进行了全面介绍。指出压缩感知是一种关于在欠采样条件下重构原始信号的理论。已知某个测量矩阵Φ∈RM×N(M≪N),以及待测信号X在该矩阵下的线性测量值Y∈RM,重构原始信号X。

很显然,由于Y的维数远低于X的维数,式(1)有无穷多个解,即这是一个不适定问题。然而,如果已知所寻找的解X为这无穷多个解中最稀疏的,并且Φ满足约束等距性条件(RIP)[10],压缩感知理论指出,信号X可以由测量值Y通过求解最小l1范数问题精确重构:

式(2)成功重构X的前提有2点:(1)待重构信号X足够稀疏;(2)测量矩阵Φ满足RIP条件。这表明,对于一个稀疏信号,使用满足RIP条件的测量矩阵对其进行压缩,并没有损伤原信号所承载的信息。高维度社会网络特征具有足够的稀疏性,可通过设计合适的测量矩阵,在不损伤原特征所承载信息的前提下对高维特征进行降维处理。

目前已有不少类型的测量矩阵,最常用的包括高斯随机测量矩阵(式(3))和伯努利随机测量矩阵(式(4))等。文献[11]从理论上证明了其满足RIP特性。

为了选定合适的测量矩阵,本文选择社会网络数据集blogcatalog作为测试样本,选择伯努利随机测量矩阵对其进行特征压缩。该数据集包含10 312个结点,经统计,该邻接矩阵的稀疏度为0.63%。测试在4种不同的重构稀疏度下,测量次数与重构正确率的关系。重构算法采用 OMP (Orthogonal Matching Pursuit)算法,4种重构稀疏度分别为60,140,220和300。重构稀疏度是指重构信号X中非零元素的最大个数。

如图1所示,图中实线表示正确重构的比率,虚线表示欠重构的比率,点划线表示过重构的比率。在4种重构稀疏度下,随着测量次数的增加,正确重构的位置在增加,欠重构和过重构的位置在减少。当重构稀疏度不低于220时,当测量次数达到一定值后,信号可被完全重构。当重构稀疏度为220时,测量次数达到1 000后便可完全重构信号。通过随机测量,可在不损失信息的情况下,将维度为10 312的社会关系特征压缩到1 000维。实际上,对于大部分实际社会关系数据,单个结点的邻接特征即使维度非常高,其中非零值的个数也是相当有限的。因此,利用随机测量矩阵对高维社会关系数据进行压缩,可降低维度,从而使本文算法适合处理更高维度的社会关系数据。

图1 测量次数与重构正确率的关系

2.3 DBN模型

深度学习是目前机器学习领域和大数据处理领域的研究热点,对其研究的兴起源于文献[8]提出的DBN模型及其训练算法。相比于传统神经网络, DBN具有很多优点:首先,其是一种无监督学习方法,适合于对无类标大数据进行处理;其次,其训练算法CD(Contrastive Divergence)算法比传统多层神经网络训练算法BP(Back Propagation)算法的效率高很多,且能使训练结果趋于全局最优解,避免BP算法在训练多层神经网络时结果陷于局部最优解的问题。

DBN由多层RBM(Restricted Boltzmann Machines)叠加组成。RBM是一种特殊结构的神经网络,它由一个可见层V和一个隐含层H组成,层内结点无连接,层间结点彼此互连,从而在已知V的情况下,所有H中的结点是条件独立的,即p(H|V)=p(h1|V)p(h2|V)…p(hn|V),同理,在已知隐藏层H的情况下,所有V中的结点也是条件独立的。可见层结点的状态空间为{0,1},或者0～1之间的实数,表示概率;隐含层结点的状态空间为{0,1}。RBM假设V和H的全概率分布p(V,H)满足Boltzmann分布。因此,在已知可见层V的情况下,通过p(H|V)可以得到隐藏层H,得到H后,通过p(V|H)又能得到可见层。通过调整参数,并重复这一过程,使从隐藏层得到的可见层与原来的可见层趋于一致,从而使得隐藏层成为可见层的另一种表达,这一过程称为吉布斯采样,这一训练算法即为CD算法。

如图2所示,将多层RBM叠加,前一层RBM的隐藏层作为后一层RBM的可见层,且在靠近可见层的部分使用贝叶斯信念网络(依然限制层中结点无连接),这样得到的神经网络模型就称作DBN。训练DBN使用CD算法,该训练过程即为模型的预训练过程。为了让DBN具有识别类别的能力,在它顶部叠加一个分类层,该层的输入是DBN的输出,训练该层需要小样本有类标数据,并使用BP算法进行有监督训练,该训练过程即为模型的调优训练过程(Fine-tuning)。

图2 模型结构

3 社团结构深度学习方法

基于压缩感知的社团结构深度学习方法分为4步,如图3所示。(1)从社会关系邻接矩阵中抽取代表集,并使用GN算法提取该代表集的社团结构; (2)利用随机测量矩阵对社会关系邻接矩阵进行降维,获得低维的特征样本;(3)使用该低维特征样本对DBN进行无监督训练;(4)对第(1)步中获得的有类标小样本集进行有监督调优。

图3 深度学习方法步骤

3.1 代表集类标的获取

传统的社团发现算法在小样本集下具有较好的效果,随着网络结点和结点间关联边的增多,传统算法的复杂度将呈指数级增长。对于大规模的复杂网络,使用传统社团发现算法将不再可行。为了给深度学习提供有类标的样本进行调优,可从大规模复杂网络中抽取代表集,并使用传统算法提取代表集中的社团结构。

代表集采用随机的抽取方法,从大规模复杂网络中随机选定若干结点,并将选定结点之间互连的边保留,从而得到适合传统社团发现算法处理的小规模社会关系邻接矩阵。复杂网络的邻接矩阵记为A,其中结点集合记为V,代表集中的结点记为,代表集邻接矩阵记为。

3.2 样本特征维度的降低

大规模社会关系网的结点特征维数动辄上万,甚至上百万,但却具有稀疏性的特点,且随着网络规模的增大,稀疏性越明显。通过压缩感知中的随机测量方法,可在不损失特征信息量的情况下有效降低特征维度,为DBN提供维度可控的训练样本。

采用伯努利随机测量矩阵对高维复杂网络的邻接矩阵进行降维。测量矩阵记为M,压缩后的特征样本记为Ac,Ac=A×M。由于DBN输入样本各维的状态空间为{0,1},或者0～1之间的实数,因此需要对Ac中的数据分布按维度(Ac中的列)进行归一化。本文比较了2种归一化方法对后继社团结构深度学习的影响,一种是重映射方法,另一种是同分布归一化方法。前一种方法为了最大限度地区分各类样本,将所有样本的特征按维度重新映射到0～1之间,且满足平均分布;后一种方法则直接将样本按维度压缩到0～1之间,保持原分布比例不变。

3.3 训练DBN的监督

训练DBN之前首先要确定DBN的结构,DBN结构包括RBM的层数以及各层RBM中可见层和隐藏层的结点数。使用数组[n1,n2,…,nk]表示DBN的结构,其中,k表示DBN层数;n1表示输入层结点数,ni(2≤i≤k)表示第i层隐藏层结点数;使用[W1,W2,…,Wk-1]表示各层之间的传递矩阵。如图4所示,即为所确定的DBN结构。

图4 DBN训练过程

使用CD算法对DBN中每一层RBM进行无监督训练。训练样本集为Ac,输入层结点数n1等于样本集Ac中样本的维数,各结点对应样本的各维。对每一层RBM的训练分别进行,CD算法确保将输入样本映射到不同特征空间时,都尽可能多地保留特征信息。该训练过程可以看作是多一个深层BP神经网络权值参数进行初始化,使DBN克服了BP网络因随机初始化权值参数而容易陷入局部最优和收敛速度慢的缺点。

3.4 有监督模型调优

获得经过预训练的 DBN模型后,可基于该DBN为每一类社团构建一个BP神经网络,该BP神经网络的输出为0/1,即判断输入样本是否属于本社团。如图5所示,为模型的调优训练过程。

3.1 节介绍了通过GN算法提取代表集的社团结构。从代表集中共划分出N个社团,为这N个社团分别建立一个BP神经网络。该BP神经网络基于3.3节预训练得到的DBN构建,在其输出端叠加一个BP神经网络作为分类层,接受DBN的输出特征向量作为其输入特征向量。利用代表集中的有类标样本进行有监督训练。由于DBN中每一层RBM网络只能确保自身层内的权值对该层特征向量映射达到最优,并不是对整个模型达到最优,因此反向传播需要将误差信息自顶向下传播至每一层RBM,从而微调整个模型。

图5 模型调优过程

当N个模型都训练完毕,就获得了一组能通过邻接关系判断社团归属的社团识别模型。识别步骤如下:首先利用该组模型对应的随机测量矩阵将待识别结点的邻接关系向量压缩降维,将降维后的特征向量作为输入分别输入N个模型,N个模型的输出即为判断是否归属于对应社团的依据。

4 实验结果与分析

4.1 评价指标

为了刻画网络中社团划分的好坏,文献[12]提出了Modularity模型,用模块度(Q值)表征社团性质强弱。Q值的物理意义如下:网络中连接2个属于同一社团结点的边的比例,减去任意连接这2个结点边的比例的期望值。Q值通常在0.3～0.7之间。

对大规模高维度社会网络数据进行社团结构发现,除了使用Q值对所提取的社团结构聚类性能进行评估外,算法的时间耗费也是重要的评价指标。

4.2 2种特征归一化方法效果对比

在3.2节中提到,使用伯努利随机测量矩阵对样本进行降维后,所得到的低维样本特征需要进行重映射或者同分布归一化处理。为了对比2种归一化方法对后继DBN学习社团结构的影响,本文进行了实验。

测试样本集为 power,该数据集为一个包含4 914个结点的关系邻接矩阵,其稀疏度为0.054%。从中抽取前1 000个结点组成代表集,使用GN算法提取代表集的社团结构,共划分出33个社团,所提取的社团结构模块度Q=0.723 2。DBN共有3层,输入层结点数为n1,2层隐含层结点数分别为400和200,分类层结点数为100,用伯努利随机测量矩阵对power数据集进行压缩,将特征维度压缩至n1。

如表1所示,测试在不同样本特征维度下,2种归一化方法对社团结构划分性能的影响。从表中数据可知,重映射归一化方法优于同分布归一化方法。

表1 2种归一化方法对社团结构划分性能的影响

从表中数据还可以看出,使用重映射归一化方法,当特征维度n1=1 000时,社团划分性能达到最优(Q=0.391 4),随着n1的增加,社团划分性能反而下降。使用同分布归一化方法同样存在这样的趋势,最优值出现在n1=800。经过分析,出现这种趋势的原因在于,更高的特征维度能更精确地保存原特征的信息,却导致模型的参数增多,在样本数没有增加的情况下,容易导致过拟合。使用重映射归一化方法比使用同分布归一化方法更晚出现过拟合现象,这说明前者通过调整样本特征分布,提高了各类样本的区分度,后继社团结构划分更有利。

4.3 DBN结构调整

DBN的结构对社团结构划分性能具有重要影响。DBN结构包括DBN中隐藏层层数以及各层结点数。为了测试DBN结构对最终社团结构划分性能的影响,采用隐藏层层数递增的方式。固定输入层结点数为1 000,分类层结点数为100。测试样本集及代表集选择方法与4.2节相同,将power数据集进行随机测量,将特征维度压缩至1 000。

首先测试单隐层DBN的社团划分性能。如表2中h=1列所示,通过调整该层结点数n2,发现当n2=400时,模型所提取的社团结构模块度最高(Q=0.376 1)。选定第1层隐藏层结点数n2=400,继续叠加第2层隐藏层,如表2中h=2列所示。调整该层结点数,发现当n3=200时,模型所提取的社团结构模块度最高(Q=0.391 4)。

表2 DBN结构对社团结构划分性能的影响

选定第2层隐藏层结点数n3=200,继续叠加第3层隐藏层,如表2中h=3列所示。调整该层结点数,发现当n4=200时,模型所提取的社团结构模块度最高(Q=0.301 0),但该最优值已经低于仅有2层隐藏层时的最优值。导致性能退化的原因是当层数进一步增加时,模型参数随之增多,会导致模型过拟合现象,就需要更多的样本进行训练。

通过测试,确定了从power数据集中提取社团结构的最优DBN结构,该结构中输入层结点数为1 000,共有2层隐藏层,结点数分别为400和200,分类层结点数为100。

4.4 算法性能对比

本文所提出的社团结构发现方法适合于处理大规模高维度社会网络数据,弥补了传统社团发现算法无法对大规模数据进行有效处理的缺陷。如图6和图7所示,分别为GN算法和SymNMF算法在处理不同规模社会网络时的时间耗费。从测试数据集blogcatalog中抽取前K个结点组成测试集,分别使用GN算法和SymNMF算法提取测试集的社团结构,并记录算法耗时。实验用机配置为:Intel I7处理器,8 GB内存,Win7 64 bit操作系统。

图6 GN算法效率与网络规模的关系

图7 SymNMF算法效率与网络规模和预期社团数的关系

从图中可以看出,随着测试集规模的增大,算法的时间耗费迅速增大,当结点数为800时,GN算法耗时1 340.6 s,当网络规模进一步增大,GN算法耗时将严重恶化。SymNMF算法需要手工指定预期划分的社团数目,而对于大规模的实际社会网络数据,无法准确给出该信息。一般做法是通过遍历不同的社团数目,计算所划分社团结构的模块度,并选择模块度最高的划分结果。

本文所提出的方法适合处理大规模高维度社会网络数据,表3为使用本文方法对3个不同规模的实际社会网络数据集的处理结果。代表集选择各数据集的前1 000个样本,并使用GN算法提取各代表集的社团结构,该过程算法耗时见表中第3列,所划分的社团结构模块度见表中第5列。模型输入层结点数为1 000,2层隐含层结点数分别为400和200,分类层结点数为100。使用伯努利随机测量矩阵对各数据集进行压缩,将特征维度压缩至1 000。实验用机配置与前文相同。

表3 本文方法处理实际数据集的性能

从表3可以看出,对于3个实际数据集,算法的主要时间耗费在于使用GN算法提取代表集的社团结构,但由于控制了代表集规模,该过程的时间耗费并不会随着全集规模的增大而增大(见表中第3列)。而用于模型训练和识别的时间会随着数据集规模的增加而线性递增(见表中第4列),且当数据集规模达到80 513时,依然能在有效时间内完成训练和识别任务。

5 结束语

本文提出的方法首先通过随机测量矩阵对社会网络数据进行特征降维,并使用DBN对降维后的特征样本集进行无监督学习,最终利用有类标小样本集进行有监督调优。随机测量方法对稀疏特征具有良好的降维效果,DBN对大数据具有良好的处理性能,从而使得本文方法适合对大规模实际社会网络数据进行处理。但通过本文方法所提取的社团结构模块度偏低,主要原因在于代表集的社团结构对全集社团结构的表现不完全,从而导致模型的有监督调优过程并不充分。下一步的研究方向是从无监督训练结果中直接提取社团特征信息,避免因代表集的不全面而导致有监督训练不充分。

[1] 骆志刚,丁 凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科学技术大学学报,2011,33 (1):47-52.

[2] Girvan M,Newman M E J.Community Structure in Social and Biological Networks[J].National Academy of Sciences,2002,99(12):7821-7826.

[3] Newman M E J.Fast Algorithm for Detecting Community Structure in Networks[J].American Physical Society,2004,69(6):187-206.

[4] Kuang Da,Ding C,Park H.Symmetric Nonnegative Matrix Factorization for Graph Clustering[C]//Proc.of 2012 SIAM International Conference on Data Mining. Anaheim,USA:[s.n.],2012:106-117.

[5] Shiga M,Takigawa I,Mamitsuka H.A Spectral Clustering Approach to Optimally Combining Numerical Vectors with a Modular Network[C]//Proc.of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:[s.n.], 2007:647-656.

[6] 窦炳琳,李澍淞,张世永.基于结构的社会网络分析[J].计算机学报,2012,35(4):741-753.

[7] 陈 宇,郑德权,赵铁军.基于Deep Belief Nets的中文名实体关系抽取[J].软件学报,2012,23(10): 2572-2585.

[8] Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[9] Hinton G,Osindero S.A Fast Learning Algorithm for Deep Belief Nets[J].Neural Computation,2006,18 (7):1527-1554.

[10] Candes E J.The Restricted Isometry Property and Its Implications for Compressed Sensing[J].Computes Rendus Mathematique,2008,346(9/10):589-592.

[11] Baraniuk R,Davenport M,Devore R,et al.A Simple Proof of the Restricted Isometry Property for Random Matrices[J].Constructive Approximation,2008,28(3): 253-263.

[12] Newman M E J,GirvanM.FindingandEvaluating Community Structure in Networks[J].Physical Review E,2004,69(2).

编辑 顾逸斐

Deep Learning Method for Community Structure Based on Compressive Sensing

ZHANG Liang-lianga,FENG Jinga,HU Gu-yub
(a.College of Meteorology and Oceanography;b.College of Command Information Systems, PLA University of Science and Technology,Nanjing 210007,China)

Traditional community detection methods can only process small-scale low-dimensional social network data because of its complexity.Aiming at this problem,this paper proposes a deep learning method for community structure based on compressive sensing.With the great advantages of reducing the feature dimension of the social network through random measurement matrix,it uses Deep Belief Network(DBN)to learn unsupervised from the low-dimensional samples.The model is fine-tuned by supervised learning from a small scale sample sets with class labels.Experimental results show that random measurement method has a good effect of dimensionality reduction for sparse features,and DBN performs well in processing large data.It is shown to be advantageous over other community detection methods on largescale high-dimensional actual social network data.

compressive sensing;deep learning;community detection;Deep Belief Network(DBN);community structure;modularity

1000-3428(2014)09-0190-06

A

TP393.08

10.3969/j.issn.1000-3428.2014.09.038

国家“863”计划基金资助项目(2012AA01A510);国家自然科学基金资助项目(60603029)。

张梁梁(1989-),女,硕士研究生,主研方向:智能信息处理;冯 径、胡谷雨,教授。

2013-09-04

2013-10-28E-mail:vermouthlove@hotmail.com