掌握机器学习数学基础之信息论及其他（三）

这篇文章讲述图论和树论的基础知识，下面是目录：

信息熵

条件熵

相对熵 (KL散度)

互信息

几种常用的距离度量

图论

树论

图论

图论是数学的一个分支，而在计算机科学中，它是一种数据结构，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。而图论是一种表示 "多对多" 的关系，下面主要讲述图的概念，表达和搜索方式：

一些概念：

其中带箭头的称为有向图,否则称为无向图.

如果一个图的任意两个结点之间有且只有一条边，则称此图为无向完全图，若任意两个结点之间有且只有方向相反的两条边，则称为有向完全图.

度是针对结点来说的， 又分为出度和入度,对于有向图来说，出度就是指以这个结点为起始的边的条数（箭头向外），入度则是以这个点为终点的边的条数（箭头向内）.

权是指一条边所附带的数据信息，比如说一个结点到另一个结点的距离，或者花费的时间等等都可以用权来表示。

图的表示：

邻接矩阵 ：如下图，对于N个点的图，需要N×N的矩阵表示点与点之间是否有边的存在。这种表示法的缺点是浪费空间，尤其是对于N×N的矩阵是稀疏矩阵，即边的数目远远小于N×N的时候，浪费了巨大的存储空间。

邻接链表：如下图，对于任何一个node A，外挂一个邻接链表，如果存在 A->X这样的边，就将X链入链表。 这种表示方法的优点是节省空间，缺点是所有链表都存在的缺点，地址空间的不连续造成缓存命中降低，性能有不如临界矩阵这样的数组。

邻接矩阵和链表对比：

邻接矩阵由于没有相连的边也占有空间，因此存在浪费空间的问题，而邻接链表则比较合理地利用空间。

邻接链表比较耗时，牺牲很大的时间来查找，因此比较耗时，而邻接矩阵法相比邻接链表法来说，时间复杂度低。

图的遍历

1. 深度优先遍历：(Depth First Search, DFS)，基本思路：深度优先遍历图的方法是，从图中某顶点 v 出发

访问顶点 v

从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历

重复上述两步，直至图中所有和v有路径相通的顶点都被访问到

2. 广度优先搜索：(Breadth First Search, BFS)

广度优先搜索，可以被形象地描述为 "浅尝辄止"，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。

实现思路：

顶点 v 入队列

当队列非空时则继续执行，否则算法结束

出队列取得队头顶点 v；访问顶点 v 并标记顶点 v 已被访问

查找顶点 v 的第一个邻接顶点 col

若 v 的邻接顶点 col 未被访问过的，则 col 继续

查找顶点 v 的另一个新的邻接顶点 col，转到步骤 5 入队列，直到顶点 v 的所有未被访问过的邻接点处理完。转到步骤 2

深度及广度优先算法的总结：

深度优先就是，从初始点出发，不断向前走，如果碰到死路了，就往回走一步，尝试另一条路，直到发现了目标位置。这种不撞南墙不回头的方法，即使成功也不一定找到一条好路，但好处是需要记住的位置比较少。

广度优先就是，从初始点出发，把所有可能的路径都走一遍，如果里面没有目标位置，则尝试把所有两步能够到的位置都走一遍，看有没有目标位置；如果还不行，则尝试所有三步可以到的位置。这种方法，一定可以找到一条最短路径，但需要记忆的内容实在很多，要量力而行。

但总之，两种算法都是盲目搜索的方式，在机器学习中，也有其他很多带先验的更智能的查询方式，可了解。

以上的知识是数据结构的基础，其实人工神经网络就是一种图，我们要理解其搜索方式和一些概念

树论

树状图是另一种数据结构，它是由个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树，而在数据结构中的特点，也是表示一对多（链表是一对一，图是多对多）的关系

最上面；树根;中间：树枝;最下：树叶

二叉树：树的一种。其特征是，除了叶以外的结点，都有两个子。（叶就是在它和根的路径上，没有比他更远的结点了，也可以理解为，只有一个结点和它相连，并且它不是根，那么他就是叶），简单来说，就是在有根树的基础上，一个结点，往更深的地方延伸时，最多只能延伸出来零个，或者两个结点（只能是0个或者2个，不能是1个。如果是0个就是叶，否则就是结点），那么他就是二叉树。（注意：二叉树是一种比较重要的树，在机器学习中有广泛的应用）

例如：图中延伸出0个结点（叶）有：E，G,H,I,J,K，而延伸出2个结点的有：A,B,C,D,F

二叉树的遍历方法主要有三种：

前序遍历；（先访问根结点，再访问子结点）

后序遍历；（先访问子结点，再访问根结点）

中序遍历（只适用于二叉树）

完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，具体可以看下图：

树论在决策树，随机森林等和树有关的模型中都有应用，特别地，最近周志华教授发表的深度森林也是应用了树的结构，在当下神经网络过热的情况下给出了另一种选择，意义重大！

关于基础数学系列的总结：

首先是我能力有限，写的内容可能不够全面，若之后发现有其他缺漏，会添加。

然后是文章写的方式，技术文，我觉得要讲究通俗，生动，有深度，受启发。可能这个系列写下来，有很多问题，我也在学习怎么写好可以达到以上要求的文章。

最后是刚开始写文章，感谢越来越多的你们的支持有什么建议和意见，真诚邀请你们提出。也欢迎多多转发！

AI遇见机器学习

mltoai