Abstract: 机器学习中我们希望从数据中挖掘隐含信息或模型，若将图中的结点作为随机变量，连接作为相关性关系，那么我们就能构造出图模型，并期望解决这一问题。而构造这样的概率图模型需要一定的图论知识。本文就总结了图论的基本概念、以及与ML的关系。

图论：以图为研究对象，描述某些事物间的特定关系。由结点与边组成，G = {V，E}。有向边与无向边。有向图与无向图。

树型结构：树是图的一种；从根节点开始，并能和其他结点相连接的图；有向性

ML X 图论：决策树；概率图模型

图论 GRAPH THEORY

关键图：

路：开路，回路，真路，链，闭链
连通图，连通子图，分图
欧拉图，哈密顿图
树，生成树，最小生成树，有向树
二部图
平面图

机器学习与图论

ML: 从数据中挖掘隐含信息与模型

将图中的结点作为随机变量，边（连接）作为相关性关系，则可构造出图模型。
概率图模型（概率论+图论）是实现这一任务的重要手段

决策树：可表示为给定特征条件下类的条件概率分布。

结点：由表示特征的内部结点和表示类的叶节点构成
决策树的学习包括特征的选择、决策树的生成和决策树的剪枝
树型：包含于图论

图论

数学的分支
以图为研究对象，研究顶点和边组成的图形
图数据结构或树型算法：来源于图论

LOOSEY–GOOSEY图

非线性结构：

最基础特征：数据不遵循特有顺序（至少无明显数值关系），类似数组和链表

树

树型结构：从根节点开始，并能和其他结点相连接；
树由一组规则定义而成：即一个根结点可能连接或不连接到其他结点，但最终所有叶结点或内部结点都能追溯到这个特定的位置。
一些树有更多的特定规则，如二叉搜索树，该树在任意时间内每个结点都只和两个子结点相连
机器学习常用的决策树：可以看成是 IF-THEN 规则的集合；即由决策树的根结点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
树的有向性：一棵树只能朝一个方向传播，即树型是由有向边（directed edge）构成的；每棵树都是由根节点开始，向下往子节点或叶节点传播；每条路径唯一，且路径上所有子节点有且仅有一个父节点；故树型结构一定不会存在循环结构或链路

离散数学：理解图论

图

不存在根节点、叶节点、单向边等概念，图中结点可连接多个子节点和多个父节点，路径可有向或无向

有向图（directed graphs）和无向图（undirected graphs）

图的基本原则：有且至少有1个单结点（才能被看做是图啊）
结点和结点之间的连接并没有确切的规则，边（有时候也称为链接）能以任何方式连接结点

离散数学：理解图论

边的类型（大多数情况下：有向/无向）是图之间最大、最明显的区别之一。
有向边：规定两结点间只有单一方向，origin——>destination

离散数学：理解图论

无向边：两结点间路径双向互通，未固定起始结点和目标结点
有向图：所有边都是有向边；无向图：所有边都是无向边

离散数学：理解图论

图（如何定义图？）

图：一种正式表征网络的结构，基本上是所有互连对象的集合；结点无层次结构

图与函数的一致性：

函数：二维坐标轴上分布的有序对（x，y）集合
图：（x，y）=（点vertices，边edges）/（v，e）；图的正式数学定义即为：G=（V，E）
有序对（V，E）：由2组对象组成，一组结点，一组边

离散数学：理解图论

下图是无向图G={8，12}

离散数学：理解图论

下图是有向图G={3，3}

离散数学：理解图论

图论的应用

1.网络是巨大的图结构

互联网——边、终端——结点、用户——在图中切换（如点击URL来回浏览）

以网页间的切换为例：有向边——只能从一个网页转到另一个；无向边——可在两网页间来回切换

2.社交网络是图结构

微信：大型无向图

微信本身是一个庞大的社交网络图
结点：用户；边：用户间的沟通联系（好友关系）
无向性（理解为信息沟通的双向性）：两个用户间的关系是双向的，可互相传递信息，无起始结点和目标结点的概念

微博：大型有向图

有向性（信息传播的单向性）：用户发微博时博文会在同时间点由用户向粉丝发送，这一过程有方向且不可逆

离散数学：理解图论

概率图模型

ML:从数据中挖掘隐含信息与模型

将图中的结点作为随机变量，边（连接）作为相关性关系，则可构造出图模型。
概率图模型（概率论+图论）是实现这一任务的重要手段

概率图模型

图论定义：概率图模型是一个包含结点与边的图；结点分为2类：隐含结点和观测结点；边分2类：有向边与无向边
概率论定义：概率图模型是一个概率分布，图中的结点对应于随机变量，边对应于随机变量的相关性关系

给定一个实际问题，我们通常会观测到一些数据，并且希望能够挖掘出隐含在数据中的知识。那么怎样才能使用概率图模型从数据中挖掘这些隐藏知识呢？

构建一个图：用观测结点表示观测到的数据，用隐含结点表示潜在的知识，用边来描述知识与数据的相互关系，最后获得一个概率分布。给定概率分布之后，通过进行两个任务获取知识：即推断 (给定观测结点，推断隐含结点的后验分布）和学习 (学习概率分布的参数）。

基本图模型的2个类别

贝叶斯网络（Bayesian Network）
马尔科夫随机场(Markov Random Field)
二者的主要区别：采用不同类型的图来表达变量间的关系；贝叶斯网络采用有向无环图（Directed Acyclic Graph）来表达因果关系；马尔可夫随机场则采用无向图 (Undirected Graph) 来表达变量间的相互作用；