有向无环图检测

01

Spark背景介绍

Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环境,拥有Hadoop MapReduce所具有的优点;但不同于MapReduce的是——Job中间输出结果可以保存在内存中,从而不再需要读写HDFS,因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce的算法。

RDD,全称为Resilient Distributed Datasets,中文翻译弹性分布式数据集,是一个容错的、并行的数据结构,可以让用户显式地将数据存储到磁盘和内存中,并能控制数据的分区。RDD是Spark的灵魂,一个RDD代表一个可以被分区的只读数据集。RDD内部可以有许多分区(partitions),每个分区又拥有大量的记录(records)。

RDD之间的依赖关系是靠有向无环图(DAG)表达的,下面看下有向无环图的基本理论和算法。

02

有向无环图(DAG)

在图论中,边没有方向的图称为无向图,如果边有方向称为有向图。在无向图的基础上,任何顶点都无法经过若干条边回到该点,则这个图就没有环路,称为有向无环图(DAG图),如下图所示,4->6->1->2是一个路径,4->6->5也是一条路径,并且图中不存在顶点经过若干条边后能回到该点,可以得出下图为DAG。

入度

入度是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和,也就是项点的入边条数称为该项点的入度。如上图所示,顶点4的入度为0.

出度

对应于入度,顶点的出边条数称为该顶点的出度。如上图所示,顶点3的入度为2.

03

DAG应用的另一个例子

在一些任务安排和调度的问题里。不同的问题或者任务之间又一些依赖的关系,有的任务需要在某些任务完成之后才能做。就像一些学校的教学课程安排。设置某一门课程需要依赖于一个前置的课程,只有学生学习了前置课程之后才能取学习该课程。如果将一门课程当做一个节点,从它引出一个指针指向后序依赖它的课程。就可能有一个类似这样的图:

Algorithms课指向Theoretical CS,意思是选修后者需要先修完Algorithms这门课,Artificial Intelligence依赖Theoretical CS,Machine learning 依赖Artificial Intelligence,Neural Networks依赖Machine learning这门课,这称为一条路径。

还可以看到,上图中入度为0的节点有 Introduction to CS,这个节点在有向图遍历中具有重要意义,下面会说到。

04

如果上图有环,还正确吗?

如上所示,如果Machine learning再指向Theoretical CS,意思是选修Theoretical CS的同学需要先修Machine learning,这个就和原来的路径Artificial Intelligence依赖Theoretical CS,Machine learning 依赖Artificial Intelligence,违背!,并且也不合常理,Theoretical CS是一门基础性的理论课,怎么可能选修它之前要先修完machine learning呢?所以不能有环路,这个图是不正确的。所以,这个图必须为有向无环图!

05

有向图如何检测有、无环?

那么,如何检测一个有向图是否是DAG呢?

有向图的环检测,首先对照着无向图的环检测来理解,在无向图中,我们要检测一个图中间是否存在环,需要通过深度优先或广度优先的方式,对访问过的元素做标记。如果再次碰到前面访问过的元素,则说明可能存在环。只做标记,在有向图中检测环路的办法可行吗?

如下图所示,深度优先遍历方法,已经遍历了节点2和6,并marked了,现在遍历节点1的另一条边,依次遍历3,4,5,6,因为6已经遍历,所以说形成了环路,但是实际上并没有,因此,与实际不符合,只对访问过的元素做标记判断有无环路是错误的。

感觉是要加条件,加什么条件? 如果我们加一个数组保存当前节点是否位于递归栈onStack中,就可以排除上面的问题,因为2,6被标记后,依次递归出栈,然后到1,深度遍历1的另一条边(3->4->5->6),所以6此时不在onStack上,第一次被检测到,所以没有环路。

因此,有向图的无环检测,需要同时借助两个限制条件:

对访问过的元素做标记

当前节点是否位于递归栈onStack中

在上图的基础上,增加节点7和8,如下图所示,可以预见,按照深度优先搜索到节点4时,会找到子节点5,节点5的其中一个边找到7,找到8,找到4,节点4此时已经位于onStack中,所以构成环路,是有环图。

算法channel会有系统地,认真地推送:机器学习(包含深度学习,强化学习等)的理论,算法,实践,源码实现。期待您的参与!

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏携程技术中心

干货 | ElasticSearch相关性打分机制

作者简介 孙咸伟,后端开发一枚,在携程技术中心市场营销研发部负责“携程运动”项目的开发和维护。 携程运动是携程旗下新业务,主要给用户提供羽毛球、游泳等运动项目的...

1.2K8
来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最大流算法(附C++代码及算例)

—“运筹教科书到底能给你啥?” —“算法和实现离教科书有多远?” —“问题解决能力到底从哪来?” 今天刚起床就接到了BOSS的 提·问·三·连 小编表示 收到直...

4325
来自专栏机器之心

资源 | 囊括欧亚非大陆多种语言的25个平行语料库数据集(拿走不谢!)

原文链接:https://gengo.ai/datasets/25-best-parallel-text-datasets-for-machine-transl...

1063
来自专栏数说工作室

海量文本用 Simhash, 2小时变4秒! | 文本分析:大规模文本处理(2)

这是一个相似匹配的问题(文本相似匹配基础→ 词频与余弦相似度)。但是,亿级数据库,用传统的相似度计算方法太慢了,我们需要一个文本查询方法,可以快速的把一段文本的...

1603
来自专栏张俊的专栏

【SPA大赛】机场客流量的时空分布预测比赛经验分享

1. 问题描述机场拥有巨大的旅客吞吐量,与巨大的人员流动相对应的则是巨大的服务压力。安防、安检、突发事件应急、值机、行李追踪等机场服务都希望能够预测未来的旅客吞...

5110
来自专栏大数据智能实战

基于seq2seq的中国对联自动配对技术实践

Sequence to Sequence模型这种基于编码--解码的模型已经被谷歌成功应用于机器翻译上。而理论上任意的序列到序列的有监督问题都可以用这种模型。如...

2968
来自专栏斑斓

Spark 1.4为DataFrame新增的统计与数学函数

Spark一直都在快速地更新中,性能越来越快,功能越来越强大。我们既可以参与其中,也可以乐享其成。 目前,Spark 1.4版本在社区已经进入投票阶段,在Gi...

3527
来自专栏kalifaの日々

机器学习CS229:朴素贝叶斯&exercise6

用朴素贝叶斯实现垃圾邮件分类器,解题代码如下 numTrainDocs = 700; numTokens = 2500; M = dlmread('F:...

3317
来自专栏量化投资与机器学习

【高能】用PyMC3进行贝叶斯统计分析(代码+实例)

问题类型1:参数估计 真实值是否等于X? 给出数据,对于参数,可能的值的概率分布是多少? 例子1:抛硬币问题 硬币扔了n次,正面朝上是h次。 参数问题 想知道...

5919
来自专栏人工智能头条

百度Deep Image论文被质疑过度使用ImageNet评价服务器【英】

1625

扫码关注云+社区