基于复杂网络的机器学习方法

本书结合两个重要和流行的研究领域：复杂网络和机器学习，不仅包括基础背景知识，还包含近期*新的研究进展。书中包括大量插图和例题帮助读者理解主要思想和实现细节。

迪亚戈·克里斯蒂亚诺·席尔瓦（Thiago Christiano Silva） 巴西中央银行研究员，博士毕业于巴西圣保罗大学，目前的研究领域包括机器学习、复杂网络、金融稳定性、系统风险和银行业务等。

赵亮（Liang Zhao） 巴西圣保罗大学教授，计算机科学与数学系主任，博士毕业于巴西航空技术学院，目前的研究兴趣包括机器学习、复杂网络、人工神经网络和模式识别。

机器学习是计算机科学的一个重要研究领域之一，主要指计算机利用已有的经验来获得学习能力的一种计算方法。虽然已经有众多的机器学习方法被提出并且在各类实际系统中成功应用，但是仍然有很多挑战性的问题需要解决。在过去的几年里，基于复杂网络（大规模的具有复杂连接模式的图）的机器学习方法越来越受到关注。该方法的出现是因为其具有内在的优点，即数据表示是基于网络特性的，能有效捕获数据的空间、拓扑和功能关系。本书介绍了在机器学习领域复杂网络理论的特性和优势。在前七章，我们首先介绍机器学习和复杂网络的一些基本概念，提供必要的背景知识。然后，简要描述基于网络的机器学习技术。在后三章，我们将介绍一些基于网络的监督学习、无监督学习和半监督学习方法，并提供详细的案例分析。特别是，针对无监督和半监督学习，我们探讨了使用随机非线性动力系统的粒子竞争技术。同时，分析了竞争系统内的各类影响因素，以确保该技术的有效性。另外，对于学习系统存在的不完善性，比如半监督学习的数据可靠性问题，可以采用竞争机制来消除训练数据集的缺陷。识别并预防误差传播具有重要的实际意义，但文献中关于这方面的研究很少。在案例分析中，我们提出了一个结合低阶和高阶的混合监督分类技术，低阶项通过传统的分类方法实现，而高阶项通过提取由输入数据构造的底层网络的特征实现。换句话说，其主要思路是低阶项利用数据的物理特征实现测试样本的分类，而高阶项进行测试样本模式的一致性检验。可以看出，该技术可以根据数据的语义特征实现样本分类。
本书旨在融合两个目前被广泛研究的领域：机器学习和复杂网络。所以，我们希望本书能在科学界引起更多学者的兴趣。本书是自成体系的，介绍基于网络的机器学习技术的建模、分析和应用，不仅包含两个领域的基础知识，还介绍了一些新的研究成果，主要面向对机器学习和复杂网络感兴趣的研究人员和学生。对于每一个可探索的话题，我们还提供了相应的参考文献。此外，众多的说明性图例也可以帮助读者理解各类方法的主要思路和实现细节。
致谢感谢Marcos Gonalves Quiles博士、Fabricio Aparecido Breve博士、Joo Roberto Bertini Jr博士、Thiago Henrique Cupertino博士、Andrés Eduardo Coca Salazar博士、Bilz Marques de Araújo博士、Thiago Ferreira Coves博士、Elbert Einstein Nehrer Macau博士、Alneu Andrade Lopes博士、Xiaoming Liang博士、Zonghua Liu博士、Antonio Paulo Galdeano Damiance Junior先生、Tatyana Bitencourt Soares de Oliveira女士、Lilian Berton女士、Jean Pierre Huertas Lopez先生、Murillo Guimares Carneiro先生、Leonardo Nascimento Ferreira先生、Fabio Willian Zamoner先生、Roberto Alves Gueleri先生、Fabiano Berardo de Sousa先生、Filipe Alves Neto Verri先生和Paulo Roberto Urio先生过去的几年里在该领域内的合作。感谢Jorge Nakahara Jr博士仔细审阅了本书，并在整个出版过程中给予我们持续支持。感谢YingCheng Lai博士引导我们进入迷人的复杂网络研究领域。感谢Hamlet Pessoa Farias Junior先生和Victor Dolirio Ferreira Barbosa先生热烈的讨论成果。也要感谢Joo Eliakin Mota de Oliveira先生为我们提供了两张图。同时，感谢巴西圣保罗大学数学与计算机科学研究所（ICMC）和里贝朗普雷图分校哲学、科学与文学学院，以及巴西中央银行的大力支持。最后，感谢巴西圣保罗研究基金会（FAPESP）、巴西国家科学技术发展委员会（CNPq）和巴西高等教育基金会（CAPES）为我们的研究工作提供资金支持。
Thiago Christiano SilvaLiang Zhao巴西，巴西利亚和里贝朗普雷图2015年11月

译者序
前言
作者简介
符号列表
第1章概述
1.1背景
1.2本书主要内容
1.3本书结构
参考文献
第2章复杂网络
2.1图论简介
2.1.1图的定义
2.1.2图的连通性
2.1.3路径和环路
2.1.4子图
2.1.5树和森林
2.1.6图的矩阵表示
2.2网络演化模型
2.2.1随机网络
2.2.2小世界网络
2.2.3无标度网络
2.2.4随机聚类网络
2.2.5核心边缘网络
2.3复杂网络的统计描述
2.3.1度和度相关性
2.3.2距离和路径
2.3.3网络结构
2.3.4网络中心性
2.3.5复杂网络度量方法的分类
2.4复杂网络上的动力学过程
2.4.1随机游走
2.4.2惰性随机游走
2.4.3自避行走
2.4.4游客漫步
2.4.5流行病传播
2.5本章小结
参考文献
第3章机器学习
3.1引言
3.2监督学习
3.2.1数学表达式和基本假设
3.2.2主要算法
3.3无监督学习
3.3.1数学表达式和基本假设
3.3.2主要算法
3.4半监督学习
3.4.1研究目的
3.4.2数学表达式和基本假设
3.4.3主要算法
3.5基于网络的机器学习方法概述
3.6本章小结
参考文献
第4章网络构建技术
4.1引言
4.2相似性与相异性
4.2.1定义
4.2.2基于向量形式的相似性函数实例
4.3向量数据的网络转化
4.3.1k近邻和半径网络
4.3.2k近邻和半径组合的网络构建技术
4.3.3b匹配网络
4.3.4线性邻域网络
4.3.5松弛线性邻域网络
4.3.6聚类启发式网络
4.3.7重叠直方图网络
4.3.8其他网络构建技术
4.4时间序列数据的网络转化
4.4.1周期网络
4.4.2相关网络
4.4.3循环网络
4.4.4转移网络
4.5网络构建方法分类
4.6非结构化数据网络转化的难点
4.7本章小结
参考文献
第5章基于网络的监督学习
5.1引言
5.2典型的基于网络的监督学习技术
5.2.1基于k关联图的分类算法
5.2.2网络学习工具：NetKit
5.2.3易访问启发式的分类算法
5.3本章小结
参考文献
第6章基于网络的无监督学习
6.1引言
6.2社团检测算法
6.2.1相关概念
6.2.2数学表达式和基本假设
6.2.3前沿技术综述
6.2.4社团检测基准
6.3典型的基于网络的无监督学习技术
6.3.1介数
6.3.2模块度最大化
6.3.3谱平分法
6.3.4基于粒子竞争模型的社团检测
6.3.5变色龙算法
6.3.6基于空间变换和群体动力学的社团检测
6.3.7同步方法
6.3.8重叠社团挖掘
6.3.9网络嵌入与降维
6.4本章小结
参考文献
第7章基于网络的半监督学习
7.1引言
7.2数学假设
7.3典型的基于网络的半监督学习技术
7.3.1最大流和最小割
7.3.2高斯随机场和调和函数
7.3.3Tikhonov正则化框架
7.3.4局部和全局一致性算法
7.3.5附着法
7.3.6模块化方法
7.3.7相互作用力
7.3.8判别式游走
7.4本章小结
参考文献
第8章基于网络的监督学习专题研究：高级数据分类
8.1引言
8.2问题提出
8.3高级分类模型
8.3.1高级分类模型的总体思路
8.3.2混合分类框架的构建
8.4高级分类器的构建方法
8.4.1传统的基于网络度量方法的高级分类器构建
8.4.2基于随机游走的高级分类器构建
8.5高级分类器的数值分析
8.5.1高级分类器应用样本
8.5.2参数敏感性分析
8.6应用：手写数字识别
8.6.1相关研究
8.6.2手写数字数据集MNIST
8.6.3图像相似性计算算法
8.6.4混合分类框架中的低级分类技术
8.6.5混合分类器的性能
8.6.6手写数字识别样本8.7本章小结
参考文献
第9章基于网络的无监督学习专题研究：随机竞争学习
9.1引言
9.2随机竞争学习算法模型
9.2.1模型原理
9.2.2转移矩阵的推导
9.2.3随机非线性动力系统的定义
9.2.4计算社团数目的方法
9.2.5重叠结构的检测方法
9.2.6参数敏感性分析
9.2.7收敛分析
9.3模型的理论分析
9.3.1数学分析
9.3.2粒子竞争模型与传统的多粒子随机游走
9.3.3样本分析
9.4重叠节点及社团检测的数值分析
9.4.1扎卡里空手道俱乐部网络
9.4.2海豚社交网络
9.4.3《悲惨世界》人物关系网络
9.5应用：手写数字识别和字母聚类
9.5.1数据集情况
9.5.2最优粒子数和集簇数
9.5.3手写数字或字母聚类
9.6本章小结
参考文献
第10章基于网络的半监督学习专题研究：随机竞争合作学习
10.1引言
10.2随机竞争合作模型
10.2.1半监督学习与无监督学习的差异
10.2.2半监督学习环境
10.2.3竞争转移矩阵的修正
10.2.4系统初始条件的修正
10.3模型的理论分析
10.3.1数学分析
10.3.2样本分析
10.4模型的数值分析
10.4.1人工合成数据集上的模拟
10.4.2真实数据集上的模拟
10.5应用：错误标记数据集上的错误标签传播检测和预防
10.5.1问题提出
10.5.2错误标记训练集的检测
10.5.3错误标签传播的预防
10.5.4竞争合作模型学习系统的修正
10.5.5参数敏感性分析
10.5.6计算机模拟
10.6本章小结
参考文献