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

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

信息熵

条件熵

相对熵 (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

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180131G1GQQN00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区