Spark:有向无环图(DAG)检测 - 大数据技术参考_大数据技术文献_大数据趋势分析 -
当前位置:技术分享 > 技术参考 > 正文

Spark:有向无环图(DAG)检测2018-01-08 16:11:29 | 编辑:hely | 查看: | 评论:0

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

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

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

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

有向无环图(DAG)

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

 

 

入度

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

出度

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

DAG应用的另一个例子

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

 

 

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

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

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

 

 

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

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

那么,如何检测一个有向图是否是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中,所以构成环路,是有环图。

 

 

 

 

总结,以上就是有向图有环,无环检测算法的基本思想。关于有向图有环判断检测的java版源码请参考github之spark文件夹中的directedCycle类(代码参考princeton源码),

上一篇:数据挖掘:关联规则Apriori算法 大数据批处理框架 Spring Batch全面解析下一篇:

公众平台

搜索"raincent"或扫描下面的二维码