大数据图数据库之离线挖掘计算模型

本节将常见的计算模型分为两类,一类是图编程模型,另一类是图计算范型。编程模型更多地面向图计算系统的应用开发者,而计算范型则是图计算系统开发者需要关心的问题。在本节中,关于编程模型,主要介绍以节点为中心的编程模型及其改进版本的GAS编程模型;关于计算范型,则重点介绍同步执行模型和异步执行模型。这几类模型已经被广泛采用在目前的大规模图挖掘系统中。

14.4.1以节点为中心的编程模型

以节点为中心的编程模型(Vertex-CenteredProgrammingModel)首先由Pregel系统提出,之后的绝大多数离线挖掘类大规模图计算系统都采用这个模型作为编程模型。

典型的图节点更新函数Function(vertex)基本遵循如下逻辑。

即首先从vertex的入边和出边收集信息,对这些信息经过针对节点权值的函数f()变换后,将计算得到的值更新vertex的权值,之后以节点的新权值和边原先的权值作为输入,通过针对边的函数g()进行变换,变换后的值用来依次更新边的权值。通过vertex的节点更新函数,来达到更新部分图状态的目的。

14.4.2GAS编程模型

GAS模型可以看作是对以节点为中心的图计算编程模型的一种细粒度改造,通过将计算过程进一步细分来增加计算并发性。GAS模型明确地将以节点为中心的图计算模型的节点更新函数Function(Vertex)划分为三个连续的处理阶段:信息收集阶段(Gather)、应用阶段(Apply)和分发阶段(Scatter)。通过这种明确的计算阶段划分,可以使原先的一个完整计算流程细分,这样在计算过程中可以将各个子处理阶段并发执行来进一步增加系统的并发处理性能。

这里假设当前要进行计算的节点是u,并以此为基础来说明GAS模型。

在信息收集阶段,将u节点的所有邻接节点和相连的边上的信息通过一个通用累加函数收集起来:

通过以上三个阶段的操作,可以定义以图节点为中心的高度抽象的GAS计算模型。在GAS模型中,节点的入边和出边在信息收集和分发阶段如何使用取决于具体的应用,比如,在PageRank计算中,信息收集阶段只考虑入边信息,分发阶段只考虑出边信息,但是在类似于Facebook的社交关系图中,如果边表达的语义是朋友关系,那么在信息收集和分发阶段则是所有边的信息都会纳入计算范围。

14.4.3同步执行模型

同步执行模型是相对于异步执行模型而言的。我们知道,图计算往往需要经过多轮迭代过程,在以节点为中心的图编程模型下,在每轮迭代过程中对图节点会调用用户自定义函数Function(vertex),这个函数会更改vertex节点及其对应边的状态,如果节点的这种状态变化在本轮迭代过程中就可以被其他节点看到并使用,也就是说变化立即可见,那么这种模式被称为异步执行模型;如果所有的状态变化只有等到下一轮迭代才可见并允许使用,那么这种模式被称为同步执行模型。采用同步执行模型的系统在迭代过程中或者连续两轮迭代过程之间往往存在一个同步点,同步点的目的在于保证每个节点都已经接受到本轮迭代更新后的状态信息,以保证可以进入下一轮的迭代过程。

14.4.4异步执行模型

异步执行模型相对于同步执行模型而言,因为不需要进行数据同步,而且更新的数据能够在本轮迭代即可被使用,所以算法收敛速度快,系统吞吐量和执行效率都要明显高于同步模型。但是异步模型也有相应的缺点:其很难推断程序的正确性。因为其数据更新立即生效,所以节点的不同执行顺序很可能会导致不同的运行结果,尤其是对图节点并发更新计算的时候,还可能产生争用状况(RaceCondition)和数据不一致的问题,所以其在系统实现的时候必须考虑如何避免这些问题,系统实现机制较同步模型复杂。

在讲解异步模型的数据一致性问题前,先来了解一下GraphLab论文提出的图节点的作用域(Scope)概念。对于图G中的某个节点v来说,其作用域Sv包括:节点v本身、与节点v关联的所有边,以及节点v的所有邻接图节点。之所以定义图节点的作用域,是因为在以节点为中心的编程模型中,作用域体现了节点更新函数f(v)能够涉及的图对象范围及与其绑定的数据。

在并发的异步执行模型下,可以定义三类不同强度的数据一致性条件(见图14-12),根据其一致性限制条件的强度,由强到弱分别为:完全一致性(FullConsistency)、边一致性(EdgeConsistency)和节点一致性(VertexConsistency)。

完全一致性的含义是:在节点v的节点更新函数f(v)执行期间,保证不会有其他更新函数去读写或者更改节点v的作用域Sv内图对象的数据。因此,满足完全一致性条件的情形下,并行计算只允许出现在无公共邻接点的图节点之间,因为如果两个图节点有公共邻接图节点,那么两者的作用域必有交集,若两者并发执行,可能会发生争用状况,而这违反了完全一致性的定义。

比完全一致性稍弱些的是边一致性条件,其含义为:在节点v的节点更新函数f(v)执行期间,保证不会有其他更新函数去读写或者更改节点v,以及与其邻接的所有边的数据。即与完全一致性条件相比,放松了条件,允许读写与节点v邻接的其他图节点的数据。在满足边一致性条件下,并行计算允许出现在无公共边的图节点之间,因为只要两个节点u和v不存在共享边,则一定会满足边一致性条件。

更弱一些的是节点一致性,其含义为:在节点v的节点更新函数f(v)执行期间,保证不会有其他更新函数去读写或者更改节点v的数据。很明显,最弱的节点一致性能够允许最大程度的并发,之所以说其限制条件较弱,是因为除非应用逻辑可以保证节点更新函数f(v)只读写节点本身的数据,否则很易发生争用状况,使得程序运行结果不一致。

如果对所有可能的并发执行顺序总是存在与序列执行完全一致的执行结果,在此种情形下,我们可以将这个并发程序称为是满足序列一致性的。

是否满足序列一致性可以帮助我们验证将一个顺序执行的程序改造为并行执行程序后的正确性。在并行的异步图计算环境下,以下三种情形是可以满足序列一致性的。

情形一:满足完全一致性条件。

情形二:满足边一致性条件,并且节点更新函数f(v)不会修改邻接节点的数据。

情形三:满足节点一致性条件,并且节点更新函数f(v)只会读写节点本身的数据。

上面三种情形可供应用者在设计算法时参考,以在并发性和结果正确性之间做好权衡:一致性条件越弱,则并发能力越强,但是争用状况发生概率越高,即结果可能越难保障正确性。如果应用能够明确节点更新函数的数据涉及范围,就可以根据上述几种情形来进行选择,更好地做到在保证结果正确性的前提下提高并发性能。

THE END
1.数据挖掘概念(AnalysisServices有关如何将 SQL Server 工具应用于业务方案的示例,请参阅数据挖掘基础教程。 定义问题 与以下关系图的突出显示相同,数据挖掘过程的第一步就是明确定义业务问题,并考虑解答该问题的方法。 该步骤包括分析业务需求,定义问题的范围,定义计算模型所使用的度量,以及定义数据挖掘项目的特定目标。这些任务转换为下列问题: https://technet.microsoft.com/zh-cn/library/ms174949(en-us,sql.105).aspx
2.网络资源:数据挖掘实战1(电力窃漏电用户识别)本次学习我们将使用“什么是数据挖掘”中的挖掘过程:根据实际问题定义挖掘目标、取什么样的原始数据、对原始数据的探索分析、如何对数据进行处理、建立合适的模型完成目标、评估模型完成的好不好。 问题背景:实际生活中,有很多人可能会偷别人的电用,或者计量电量的设备坏了,造成无法根据实际用电情况计价,可能导致用户多https://nonlinear.wtu.edu.cn/info/1117/1665.htm
3.艺术档案数字化民间艺术的数字化涉及信息的采集、处理和储存,这其中包含采集设备的选择、数据处理方式、储存格式和数据库技术。但是截止到目前,并没有一个全国统一的数据加工规范或标准,无论在民间艺术普查阶段还是在名录项目申过程中,都不同程度存在一些问题,具体表现在:数据资料保存很好,但标示和描述很差,以至于使潜在的用户无法了解https://www.zboao.com/cgal/8068.html
4.AI知识图谱:机器学习深度学习数据分析数据挖掘「附脑图」数据挖掘与数据分析两者紧密相连,具有循环递归的关系,数据分析结果需要进一步进行数据挖掘才能指导决策,而数据挖掘进行价值评估的过程也需要调整先验约束而再次进行数据分析。 数据量上:数据分析的数据量可能并不大,而数据挖掘的数据量极大。 约束上:数据分析是从一个假设出发,需要自行建立方程或模型来与假设吻合,而数据挖https://www.iyong.com/displaynews.html?id=2974432318981056
5.科学网—一门新的学说《逻辑结构与逻辑工程学》逻辑方程通过代入海量常量求出海量变量的值,实现海量数据方程挖掘。方程由方程项、连接符和等号组成,一个方程项就是一个逻辑函数。逻辑函数第一步把不同类型的函数项通过求指数和加权转化成同一类型,用同一类型的连接符连接,逻辑函数仍然通过求指数和加权形成方程项,用同一类型连接符连接。求逻辑变量的过程是构建逻辑https://blog.sciencenet.cn/blog-3482188-1294934.html
6.15个热门开源免费的数据挖掘数据分析数据质量管理工具数据分析旨在从海量业务数据中获得有用信息,以便更好地为决策服务。 数据分析的完整流程图 数据挖掘,顾名思义,就像从沙子中挖掘黄金。 数据挖掘全过程 数据质量含义还是比较好理解的。简单一点来说,就是对数据进行的质量检测。这个就不过多解释。 数据质量问题 https://www.51cto.com/article/777596.html
7.王树森ReinforcementLearning学习笔记(ing)(2)马尔可夫决策过程的状态转移概率和奖励函数不仅取决于智能体当前状体,还取决于智能体选取的动作。 例子:学生马尔可夫决策过程 解释:黄色字体表示学生采取的动作,框图表示MRP的状态名(避免混淆隐去),R表示奖励函数,其与学生所采取的动作有关。注意:当学生选择“去查阅文献pub”这个动作时,则将进入一个临时状态(图https://zhuanlan.zhihu.com/p/10389734563
8.深度详解:对象检测和图像分割的数据探索过程数据挖掘对于图像分割和目标检测的需要 数据探索是很多机器学习过程的关键。也就是说,当涉及到目标检测和图像分割数据集时,没有直接的方法进行系统地数据探索。 在处理常规图像数据集和分割图像数据集时,有很多东西是可以区分的: 标签被强绑定在图像上。您必须非常小心对图像所做的任何操作,因为它可能破坏图像-标签-https://www.flyai.com/article/703
9.图像分类综述医学图像数据挖掘 图像检测 遥感图像分类 1.5 图像分类的基本过程 基本操作是建立 图像内容的描述,然后利用机器学习方法学习图像类别,最后利用学习得到的模型对未知图像进行分类。 一般来说,图像分类性能主要与图像特征提取和分类方法密切相关。图像特征提取是图像分类的基础,提取的图像特征应能代表各种不同的图像属性; https://www.jianshu.com/p/dc1c81e42897
10.数据挖掘简介数据挖掘是指一个完整的过程,该过程从大型数据库中挖掘先前未知的,有效的,可实用的信息,并使用这些信息做出决策或丰富知识. 数据挖掘环境可示意如下图: 数据挖掘环境框图.gif 2、数据挖掘过程图 下图描述了数据挖掘的基本过程和主要步骤 数据挖掘的基本过程和主要步骤 https://blog.csdn.net/quanzaiwoxin1/article/details/108234828
11.图挖掘算法gSpan元気森林近年来,图挖掘作为,数据挖掘的重要组成部分引起了社会各界的极大关注。图挖掘(Graph Mining)是指利用图模型从海量数据中发现和提起有用知识和信息的过程。通过图挖掘所获取的知识和信息已广泛应用于各种领域,如商务管理、市场分析、生产控制、科学探索和工程设计。 https://www.cnblogs.com/-402/p/16450309.html
12.数据挖掘原理算法及应用章(8)第8章复杂类型数据挖掘 1.空间数据来源和类型繁多,概括起来主要有以下几种类型:(1)地图数据:来源于各种类型的普通地图和专题地图,这些地图的内容丰富,图上实体间的空间关系直观,实体的类别和属性清晰,实测地形图还具有很高的精度。(2)影像数据:主要来源于卫星遥感和航空遥感,包括多平台、多层面、多种https://wenku.baidu.com/view/3328fe8c81c4bb4cf7ec4afe04a1b0717ed5b317.html
13.网络图的motif发现算法研究网络图的motif发现算法研究,图挖掘,数据挖掘,图同构,并行计算,网络图中的motif是一种连通的导出子图,并且满足在原图中出现的次数比它在随机图中出现的次数多很多。这种性质可以解释成这种子图https://wap.cnki.net/lunwen-1015559524.html
14.低代码RPA和AI,有什么区别腾讯云开发者社区头图| 下载于视觉中国 在To B领域,低代码、RPA和AI可谓是“流量担当”,它们自带To B基因,搭载快速发展的企业服务赛道,在企业级IT服务这一细分市场崭露头角。以这三者为代表的前沿理念和科技引领IT产业升级将是To B领域重要的长期趋势。 本文我们将通过对低代码、RPA、AI当下火热背后的观察,以微知著,探索企业级https://cloud.tencent.com/developer/article/2282164
15.图数据库发展综述典型的图挖掘算法包括频繁子图、三角形计数等. 频繁子图算法用于枚举在图中所有出现次数超过设定阈值的子图, 一般采用自底向上(即扩展图规模)的挖掘策略, 包括基于Apriori的Apriori-MaxGraph算法、基于FP-增长的MARGIN算法等. 该类算法缺点在于挖掘过程中需经过多次迭代及多次子图同构的判断, 且子图同构的判断属于NPhttps://c-s-a.org.cn/html/2022/8/8713.html
16.图挖掘技术在京东广告流量风控上的应用与实践目前初步设计出图挖掘算法平台的框架并在不断的进行优化和建设中,未来希望能够建设成为一个具有支持较多主流图挖掘算法的基础算法平台,能够支持 billion 量级、超大规模风控场景下的图挖掘应用需求,设计初期的图挖掘算法平台的架构(图5)。 图5:图挖掘算法平台主要包含六层,从下到上依次为数据层(由业务数据封装成的https://maimai.cn/article/detail?fid=1567807199&efid=OaWNb5R1UOE_ZaDNI3D1mg