基于复杂网络上监督学习方法的研究综述

袁 源, 郭进利

(上海理工大学 管理学院,上海 200093)

0 引言

网络无处不在，作为个体，我们是各种社会关系的单位；作为生物系统，我们又是生物网络微妙反应的结果。复杂的网络结构能够描述多种具有复杂性和高智能的系统。例如，细胞可以被描述为由生物反应连接起来的复杂的生命体网络[1]；因特网是由各种物理或无线链路连接的路由器和计算机组成的复杂网络[2]；思想和观点在社会网络中传播，社会网络的节点是人，边缘代表各种社会关系[3]。人们对这些复杂系统探索的兴趣驱动了复杂网络的发展。随着海量数据的出现和计算机计算能力的显著提高，复杂系统中的复杂网络理论被广泛地应用于其他学科[4～7]，许多非结构化的数据可以通过合适的网络构建技术向网络结构数据转换。复杂网络不仅可以描述节点特征以及节点之间的相互关系，而且揭示了这种局部和全局结构如何影响网络的整体功能。因此，以网络表示的数据比以向量形式表示的数据能编码更多的信息，复杂网络理论在处理机器学习或者数据挖掘更具优势，可以在监督学习中利用已知节点的和未知节点的网络关系预测测试节点的分类标签。

将机器学习和复杂网络两大工具应用于研究复杂系统，不仅具有理论基础，还具有广阔的应用前景。比如，利用机器学习技术通过网络视角将不同的区域空间结构概念化，了解大型区域空间中尺度结构。Zhang和Fang[8]收集手机信号数据，构建了一个以60个子城市为节点的更细粒度的交通网络，采用一种新的基于机器学习的加权随机块体模型及视觉分析方法，检测到两个以深圳和广州为中心的核心-外围结构，为大型区域协调政策及空间规划策略的制定提供建议；在气象领域，通过整合网络科学和机器学习用来分析全球气候系统这样复杂的数据。Santos和Vega-Oliveros[9]利用地表气温时间序列构建时间气候网络，并计算网络指标来表征EI Nio-Southern Oscillation(ENSO)的暖、冷期，利用机器学习创建模型来划分ENSO的不同类别；在物理学科，使用机器学习来预测和识别物理系统(如多体量子系统)中的关键动态相变，Ni和Tang[10]使用复杂网络上的流行病传播动力学作为范例设置，结合了监督和非监督学习，得到一个通用的全面的机器学习框架，用于检测相变和准确地识别临界过渡点，具有很强的鲁棒性，计算效率高，并普遍适用于任意大小和拓扑的复杂网络。在生物领域，可以用基于监督学习的方法来预测蛋白质相互作用网络中的蛋白质复合物。Zhou和Gui[11]认为现有的复合物检测方法大多是基于图论的，不能充分利用已知复杂的信息，提出了一种监督学习的方法来检测蛋白复合物。Razaghi[12]利用支持向量机，根据从转录组数据的图形中获得的距离曲线来重建基因调控网络。Liu和Yang[13]从人类蛋白质相互作用网络中获取节点嵌入，通过节点嵌入之间的相似性对蛋白质相互作用进行加权，使用监督学习的方法检测蛋白复合物，提供了一种从人类和酵母蛋白相互作用网络中识别蛋白复合物的新方法。

综上所述，本文对基于复杂网络的监督学习方法进行综述。第一部分系统梳理了使用监督学习方法所需要的复杂网络构建技术。第二部分理清了基于复杂网络监督学习常用算法的原理、适用范围和研究现状。并在此基础上，第三部分提出了基于复杂网络监督学习方法的未来发展方向。第四部分明晰了目前基于复杂网络监督学习方法的局限性，为用复杂网络理论研究监督学习方法提供了借鉴。

1 理论基础

在处理机器学习问题时，利用网络的形式不仅能更直观地展示数据样本点的特征，并且相比于非结构化数据，网络结构数据能够保留更多的信息，如样本之间的关系和全局拓扑结构。因此用机器学习方法处理非结构化数据时，就需要一座将非结构化数据转化为结构化数据的桥梁，将非网络化数据的关键信息提取出来，也就是这部分要被讨论的复杂网络的构建方法。

1.1 复杂网络的构建

1.1.1 相似性函数和相异性函数

复杂网络G=(V,E)由节点和连边构成，数据样本中的每个数据项对应网络中的节点，网络中的连边反映了节点之间的关系，在机器学习中利用相似度(或相异度)确定是否存在连边。

相似性函数的定义如下：

设X是一个非空集合，并定义了一个等价关系。假设s是一个相似性函数

s:X×X→IS⊂R

(1)

假设s是有上界的，意味着supRIS是存在的。

相异性函数的定义如下：

设X是一个非空集合，并定义了一个等价关系。假设d是一个相异性函数

d:X×X→Id⊂R

(2)

假设d是有下界的，意味着infRId是存在的。

定义smax≡supRIS和dmin≡infRId，且smax≥0，dmin≥0，相似性函数和相异性函数有4个主要性质。

1.1.2 相似性和相异性度量

数据集Ω={x1,…,xN},N>1是一个非空集合，每个数据项存在一个特征向量xi=(xi1,…,xip)，P>0,数据项分为类别特征、顺序特征和数值特征三大类，类别特征和顺序特征统称为定性特征，数值特征又称为定量数据，可以进行数值运算。本文给出了几个常用的定量数据相似性和距离测量公式[14]。

1.1.3 网络构建技术

如果只是把相似性和相异性度量的结果作为节点之间连边的权重，那么相似性很小的节点之间会存在连边。大量带噪音的连边甚至被扭曲的点之间也会存在连边，就会引发网络存在连接过密的问题，甚至变成全连接网络。全连接网络中的社团结构特征难以被识别，稀疏性更有利于网络的拓扑结构。因此，选择合适的网络构建技术最大程度地过滤噪音、反映样本信息，是取得较好学习效果的前提。本节讨论两种典型的网络构建算法[15]：

(1)k-近邻网络(参数n∈V)。如果节点i在节j点的n个最近邻之内，或者节j点在节i点的n个最近邻之内，则节点i和j通过一条边连接，显然这种关系是对称的。这种构建方法的优点在于更容易选择节点；每个节点都有k条边连接，不会出现孤立的节点。缺点是相对于ε-半径网络技术，缺乏几何直观。

(2)ε-半径网络(参数ε∈R)。如果‖xi-xj‖2<ε，则节点i和节点j相连，‖xi-xj‖2是指欧氏距离。ε-半径网络是由几何驱动，关系自然对称，但往往导致图中有几个连接组件，难以选择。

1.2 监督学习的理论基础

机器学习按照训练方法的不同可以分为监督学习、无监督学习和强化学习。监督学习就是给出一部分已标记的样本让机器学习，得出训练模型，在未标记的数据集上使用我们得出的训练模型对结果进行预测。在监督学习中进行系统的输入和输出，并希望预测未知的输出与已知的输入相对应。监督学习方法包括分类问题和回归问题，输出变量是连续具体的数值，且输出变量会随着输入变量变化而变化，预测问题是回归问题；当样本标签是非连续的、有限个离散值时，预测问题是分类问题。常见的分类算法有：决策树，支持向量机、朴素贝叶斯和k近邻算法；回归问题常用的回归模型包括线性回归、logistic回归和多项式回归。

与监督学习不同的是，无监督学习没有已标记的数据集，需要由机器从未标记的数据集中发现一些结构问题。我们见到的半监督学习属于监督学习和无监督学习的折中，研究已标记的和未标记的混合数据算法，降低监督学习中需要标记大量数据的成本。相比于监督学习和半监督学习，强化学习不需要大量的数据，需要多次尝试来获得某项技能，大多应用在游戏场景[16,17]。由于本文讨论的是监督学习，对无监督学习和强化学习不再赘述。

2 监督学习的主要算法

我们将数据集及其标签分为训练数据和测试数据，对训练数据进行训练得到分类器，利用测试数据判断其分类精度。监督学习分类器的算法分为两类：一是分类问题。该类问题的算法有贝叶斯算法、人工神经网络算法、统计学习理论、决策树、随机森林和k-近邻算法等。二是回归问题。该类的算法有线性回归、logistic回归和多项式回归，分别用直线、logistic曲线和n次多项式曲线来拟合自变量和因变量的关系。本文主要介绍分类问题的前四种算法，第二类问题可以参见Taneja[18]和Torre[19]等的研究。

2.1 贝叶斯算法

监督学习算法中朴素贝叶斯分类器基于贝叶斯定理，假设条件是样本的各特征之间是相互独立的。这样的条件在现实中往往很难满足，而样本的各个特征如果存在很强的相关性，会导致朴素贝叶斯分类器的分类效果较差，限制了朴素贝叶斯分类器的推广。为了改进这种假设，学者们进行了大量研究，Zhang和 Huan[20]认为现有加权贝叶斯模型很少同时关注属性值的水平粒度和类标签的垂直粒度，提出一种新的细粒度属性加权范式，即类特有属性值加权(CAVWNB)；Chen和Webb[21]提出了一种有效的选择性朴素贝叶斯算法，该算法仅采用部分属性来构造选择性朴素贝叶斯模型，模型的构建方式使得每个模型都是另一个模型的简单扩展。另外，当数据特征过多时，往往会出现类别分布不均匀问题，如在金融欺诈检测、网络入侵检测等领域。总而言之，利用贝叶斯分类器在对具有复杂结构的数据进行分类时有很好的效果，但同时也还有很大的提升空间。

2.2 人工神经网络算法

人工神经网络是一种以神经元为基本计算单元的计算模型，神经元之间的信息交换是通过突触完成的。目前尖峰神经网络的监督学习是一个重要的研究领域。学者们对尖峰神经网络的监督学习进行了大量的研究，并取得了一定的成果。尖峰神经网络被证明是处理时空信息的合适工具。然而，由于尖峰神经网络具有复杂的不连续和隐式非线性机制，因此高效的尖峰神经网络监督学习算法的制定十分困难，已成为该领域研究的一个重要问题。Lin[22]提出了一种新的多层尖峰神经网络有监督的多尖峰学习算法，该算法首先通过定义内积算子来对脉冲序列进行数学描述和操纵，从而解决了学习过程中多个输出脉冲之间的误差函数构造和反向传播问题，实现了尖峰序列复杂的时空模式学习。Patino和Alberto[23]证明了在神经形态硬件上实现MNIST和基于事件的NMNIST数字识别数据集的最新模型是可能的，通过这种方法对尖峰神经元网络有效编码时空信息的能力有了新的认识。但是现有的研究对神经元网络产生时空活动序列的机制仍不清楚。模型有的需要人工在随机网络中嵌入前馈网络，有的需要监督学习来训练网络的连通性以生成序列，并没有获得生物学支持。

2.3 统计学习理论

统计学习理论和其他理论差别在于使用了统计方法，关于这类理论使用最广泛的算法是近似实现结构化风险最小化的支持向量机(SVM)。目前支持向量机已经成功地应用到不同领域的分类和回归问题。如果未标记样本的数量远远大于标记样本的数量，SVM分类器的分类性能可能会较差。在带标记样本较少或未带标记样本过多的情况下，SVM分类器使用受到限制。为了扩展支持向量机的适用性，Li提出了一种引入边缘分布的鲁棒转换支持向量机(RTSVM)，将一阶统计量(margin mean)和二阶统计量(margin variance)正则化为TSVM，以获得较强的泛化性能[24]。相比于人工神经网络，支持向量机的核函数不容易确定，且灵活性和扩展性也更差[25]。

2.4 决策树

决策树是二叉树或者非二叉树的树形结构，由根节点、内部节点和叶节点三种元素组成。决策树根据层层推进的方式获得决策结果，在这个过程中特征值的选择尤为重要，特征值的选择直接影响分类器的分类效果，通常样本的属性有很多种，不同属性对分类结果的影响大小不同，需要筛选出与样本相关度高的属性特征。决策树有三种常用算法[26]，ID算法最早引入了信息论方法中熵的概念，把每个分裂属性当作根节点来对度量信息增量，选择信息量最高的属性。但ID算法没有考虑到缺失值的情况和连续特征情况，在ID算法的基础上，C4.5算法是对ID算法的优化，对连续特征离散化，在某些特征缺失的情况下划分属性。ID算法和C4.5算法都存在过度拟合问题，CART算法采用减枝方法避免过度拟合，采用构建二叉树方法取代非二叉树方法提高搜索效率。相比于其他算法决策树算法具有简单的结构层次更容易理解和操作，且直观性较强能够进行可视化分析，能够处理不相关的特征，但容易忽略属性之间的相互关联性。

3 基于复杂网络监督学习方法的发展方向

在基于复杂网络监督学习方法中，让计算机对训练的数据和标签进行建模，来预测输入新数据的标签。监督学习方法利用训练数据及标签，往往能取得很好的预测结果。这种对标签分类方法实践中被广泛应用，比如章成志[27]把学术论文全文作为研究对象，对论文中的研究方法进行分类，为科研工作者推荐合适的研究方法。

另一种基于复杂网络监督学习方法的分类方式是关系分类，关系分类认为数据之间是非独立的，数据的标签不仅依赖于本身的属性还依赖于邻域数据的标签。链接预测就是预测网络中没有连边的两个节点在未来某个时间是否会产生连接。链接预测的研究分为基于网络拓扑的和基于学习的两种方法。近些年来随着人工智能的快速发展，后者成为了机器学习领域的新兴研究方向。这种基于机器学习的链路预测可以应用于解决多个领域问题。比如在社交平台预测社交网络中可能的好友、在科研合作网络中对专家合作的预测[28]；在生物领域预测蛋白质之间是否会发生相互作用，预防和研究人类疾病[29]；在电子商务网站学习消费者过去的购买特征预测未来消费行为，推荐可能购买的商品[30]。

基于机器学习的链接预测方法首先需要从网络中得到各个节点的特征向量，然后将节点的特征向量作为机器学习算法特征值的输入。Jalili[31]考虑一个由Twitter(微博服务)和Foursquare(基于位置的社交网络)组成的多路网络，分别用朴素贝叶斯分类器、支持向量机分类器和近邻分类器来分类，开发了一种基于元路径的算法来预测链接。Yuan和He[32]提出了一种新的基于图核的链路预测方法，通过签名社交网络的结构信息比较用户相似度，最后利用用户相似度信息训练SVM分类器来预测链接。Wang和Lv[33]提出了一种有效预测药物-蛋白相互作用(DPIs)的方法，基于药物-蛋白相互作用(DPI)局部结构相似性(DLS)的链接预测方法来预测药物-蛋白相互作用，将链路预测和二值网络结构相结合。

以上对于监督学习的链路预测都是基于静态网络，近些年来动态网络中的链路预测在实际应用中的重要价值日益凸显，因而受到学者越来越多的关注。Chen[34]提出了一种新的链路预测方法，该方法首先表示了动态网络中结构性质的变化，然后，为每个属性训练一个分类器。最后利用所有分类器的集成结果进行链路预测。实验表明网络的演化信息有利于链路预测性能的提高。Ma[35]提出了一种新的图正则非负矩阵分解算法(GrNMF)，用于不破坏动态网络的时间链路预测问题。为了获得每个网络从1到的特征，GrNMF通过将剩余网络设置为正则化，对与网络相关的矩阵进行分解，为表征时间链路的拓扑信息提供了更好的方法。Yang[36]将动态网络转换为静态图像序列，并将时间链路预测作为条件图像生成问题，提出了一种新的深度生成框架，它利用深度学习技术同时对动态网络中的时空特征建模。由于现实网络中节点通常含有多类异构信息，在链接预测中加入更多异质性信息，将是一个重要的发展方向。

4 基于复杂网络监督学习方法的局限性

4.1 训练数据的选择

使用监督学习方法对标记数据进行训练得到训练网络，再利用这个训练网络对标签未知的测试样本进行预测。因此训练数据是否适当，就直接影响到输出结果的准确性。通常使用的误差估计方法是K倍交叉检验。当我们在对不同的模型进行选择时，往往选择误差结果最小的模型，但事实上K倍交叉检验的结果也是有一定偏差的。因为交叉检验所使用的训练样本是有重叠的，表明模型并不是相互独立的，相关变量总体方差随着协方差的增大而增大。误差估计的结果偏差越大，则越有可能出现不匹配识别。Rodriguez-Vidal和Gonzalo[37]在社交网络中对影响者使用的领域特定词汇进行语言建模，研究发现训练数据集的可用性是在任务中获得竞争结果的关键。

4.2 对比分析

获得训练函数过程中对训练数据的过度拟合，正如在回归分析中的过度拟合问题一样。为了能完美拟合样本集，引入过多的变量，虽然分类器在训练数据中表现良好，但在对未知数据进行测验以验证其泛化能力的效果却不佳，并且随着数据量的增大，预测效果进一步减弱。加入大量的变量，虽然可以在训练集中完美拟合，在实践中可能就会表现极差。

4.3 性能和效率问题

在监督学习中，性能解决的问题是如何开发机器学习算法来实现对训练集之外的样本的最优性能。监督学习系统的性能特征是其泛化误差，它测量的是训练模型的输出函数和潜在目标函数之间的距离。大多数现有的监督学习训练方法都存在模式识别的固有问题：偏差和方差困境。例如：一个神经网络太大，它可能会过度拟合一个特定的训练集合从而不能保持良好的泛化误差。然而，一个小的神经网络可能足以近似一个最优解。此外，一个重要的算法问题是如何处理一个可能有许多局部极小值的复杂优化问题。效率处理的是监督学习在空间和训练时间上的复杂性。机器学习的大小可以通过空间复杂度来表征，空间复杂度与自由参数的数量有关(例如，神经网络的权值的数量)。学习时间可以用时间复杂度来表征，时间复杂度是一种相对于特征向量维数的尺度属性。随着数据项数量和维数的增多，计算时间也随之增加，面临性能和效率的取舍问题。对于大问题，训练数据就会变得很慢，这也制约了它的使用范围。

5 结束语

机器学习是大势所趋，也是目前社会关注的重要领域之一，本文在这个背景下，从复杂网络的视角切入机器学习下的监督学习这一主题。本文梳理了复杂网络的构建方法和监督学习的概念，通过归纳总结现有基于复杂网络监督学习分类算法，阐明了算法原理及发展现状，提出了基于复杂网络监督学习的链接预测是重要的发展方向，最后剖析了目前基于复杂网络监督学习算法的局限性，为下一步的研究工作提供参考。基于复杂网络监督学习算法的研究刚刚起步，有很多的问题需要深入系统的研究。