一种基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法

摘要

本发明公开了一种基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法，包括如下步骤：步骤1：以转账交易数据构建边，形成一个资金交易的有向图；步骤2：设计一种对适配性强的迭代算法，并基于spark的pregel引擎实现，以此找出成环的资金流向。本发明解决了在利用传统方法求解资金圈形态时，由于潜在的数据倾斜导致性能不佳的问题。本发明方法依旧采用逐层迭代，但不再需要多次大表join，解决了传统做法由于多次join,代码冗余，且不能灵活跟随资金圈的节点个数的问题。本发明在代码完成后，能够支持不改变原有任何代码逻辑，将代码打包，并且只需要在配置文件中配置层次参数，就能动态实现寻找k个节点的资金圈，这更适合真实业务场景，提升效率。

说明书

技术领域

本发明涉及经济风险分析技术领域，更具体地说，它涉及一种基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法。

背景技术

在审计领域里，资金交易分析为其必不可少的一个部分。而资金交易又存在种种形态，比如担保圈，资金圈等。其中，资金圈形态主要指，客户与第三方的资金多次交易，并且相邻两笔交易之间存在一定的约束关系，并最终回流到自身的情况。资金圈形态的出现代表着该链路所形成的社区客户，存在某种非法交易，特殊交易的可能，因而具有审计的需要，以规避可能出现的经济风险。

目前挖掘资金圈以寻找资金流向的具体形态为思路，传统方法以穷举，hivesql或者sparksql遍历为主，但总的来说，该种手段过于复杂，计算量大，且不够灵活，很难做到适配化。比如，

1.资金转账表一般量级很大，用sql去追踪资金交易时，其实就是寻找类似a->b->c的链路，这种实现通过sqljoin来实现。但两大表的join操作会导致笛卡尔积的产生。并且资金圈一般链路较长，因而随着链路变长，会产生多次笛卡尔积。并且，由于资金转账涉及多种业务类型，所以存在着银行业务里最为夸张的数据倾斜(比如多个子公司向母公司转账)。交易数据量巨大，多重笛卡尔积，数据倾斜，这三者对系统内存容量提出了极高的要求。而且运行风险不好评估，难以确保代码能顺利跑通。

2.传统的利用sql来寻找资金圈的办法，很难做到很灵活，例如，比如资金圈历经10个实体，则sql要写9次。如果要找出历经12个实体的，则要写11次sql。这会导致很多重复工作，代码冗长。

基于上面这些存在问题，本发明设计了一种新型的寻找资金圈的办法。该方法放弃sql思路，将所有转账数据构建为一张有向图，并利用pregel框架，分布式迭代遍历有向图中所有边，迭代遍历方向按照业务实际需求而定。该种方法可以解决sql思路下计算量过大，且由于数据倾斜普遍存在而导致的性能不佳的问题。

发明内容

针对现有技术存在的不足，本发明的目的在于提供一种基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法，其以解决上述背景技术中提出的问题。

为实现上述目的，本发明提供了如下技术方案：

一种基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法，其特征在于：包括如下步骤：

步骤1：以转账交易数据构建边，形成一个有向图，图中每一条边都是一个转账交易行为，边的表达形式如下：(a,b,attrs),整个有向图的数学形式为：[(srcId,srcAttr),(dstId,dstAttr),(attr)]；

其中a，b代表企业实体，attrs代表a和b转账行为的自有属性；

其中，srcId为a转账方节点id；

其中，srcAttr为a转账方节点自身属性；

其中，dstId为b转账方节点id；

其中，dstAttr为b转账方节点自身属性；

其中，attr为转账属性

步骤2：利用Spark大数据的pregel，设计迭代算法，基于pregel实现，找出成环的资金流向。

进一步的，attrs代表a和b转账行为的自有属性，该自有属性包括转账的时间、转账的金额、转账设备的ID以及转账设备网络IP地址。

进一步的，srcAttr为a转账方节点自身属性，该自身属性包括企业属性以及个人属性。

进一步的，attr为转账属性，且该转账属性包括转账金额、转账时间、转账类型以及转账用途。

进一步的，所述步骤2中的迭代算法设计依据为根据业务需求而定，且业务需求限定为：Attr(x)＝F(Attr(x-1))，其中，Attr代表某笔交易的转账属性，Attr(x-1)代表x-1刻的交易，Attr(x)代表第x刻的交易，F代表约束关系，或称为迭代条件，任何两笔相邻的转账都符合该种约束关系。

进一步的，当F与转账金额，转账时间有关时，抽象表达如下：

F～(factor1,factor2,..)

其中，Factor，factor2表示迭代条件的要素，也是一笔转账里包含的属性，在图中为边属性。

进一步的，假设限定迭代条件F～(factor1，factor2,...)，迭代算法步骤如下：

S1：对有向图中所有节点设定初始属性attr，且attr包含srcId,作为自身节点的初始化属性id，以及自定义属性，用自己的节点id作为所属强连通分支的id，并将所有节点打上初始标记false；

S2：首先做循环，将只有出边或入边的节点标记为true，将“只存在单向边的或者孤立的节点”和“已经确认且打好标记的强连通分量”中的被标记为true的节点从有向图中去除；

S3：初始化完成自身的属性后，基于Pregel计算框架，开始分布式进行有向图的信息传递，图中每一条边沿着出边由src节点向dst节点发送自己的属性id，并且设置如下规则，只允许属性id小的节点向属性id大的节点传递信息，或者属性值大的往属性小的传递，取决于实现方法，该种操作会决定哪个节点会作为强连通分量的唯一性标记；

其中，在由src节点向dst节点传递的过程中，为了实现两笔转账的约束条件F，需要做如下操作：

在A传递到B的时候，需要连带边属性attr传入给B，作为B的节点属性，也即自定义属性，之后B传递给C时，B的节点属性需要与B-C转账的边属性进行比较，且需要满足F条件，否则B-C不往下传递，抽象表示如下：

F(attrAB,attrBC)＝F(srcAttr_B,attrBC)＝true；

S4：当深搜结束，Pregel中是人为设置遍历深度，默认为原图已被“着色”，有向图开始反向遍历，为着色完成的图中节点反向打标签以确定是否完成强连通分支id标记，在着色完成的图中，节点id与节点属性id相同时，则表明该节点是自身所处强连通分支的root节点，则节点标签标记为true。之后，有向图中所有节点沿着入边由dst节点向src节点发送自身标记情况，只要节点收到true消息，则该节点便标记为true；

S5：反向遍历同样深度(这里指正向遍历深度)后，遍历到的节点完成了强连通分量的标记，然后将该部分节点从原图中删除，作为返回结果的一部分，剩下的节点构成新的原图，重新执行步骤S1-S4，直到整张图所有节点被删除干净。

其中，在由dst节点向src节点传递的过程中，需要满足：

F逆(attrBC,attrAB)＝F逆(srcAttr_C,attrBC)＝true；

其中，F逆表示F的逆转条件，即从dst出发去看待F条件。

综上所述，本发明主要具有以下有益效果：

本发明寻找资金圈的最终效果如下：a->b->c->a，传统做法是基于sql,一层一层的join,当需要寻找n个节点的圈，需要join(n-1)次，并且要判断起点和终点一致。传统做法有多种弊端，本发明方法可以实现解决如下问题：

1.解决传统做法由于多次大表join,产生笛卡尔积导致计算量过大，且由于数据倾斜导致性能不佳的情况，而且该种压力随着join层数越来越深，而越来越大，本发明方法依旧是逐层迭代，但不需要多次大表join；

2.解决传统做法由于多次join,代码冗余，且不能灵活跟随资金圈的节点个数的问题,比如，当想要10个节点数量的资金圈，则要写9次sql,但若下次想要寻找12个节点的圈，则要写11个sql，这样不方便代码迁移,本次发明的做法支持不改变原有任何代码逻辑，将代码打包，并且只需要在配置文件中配置层次参数，就能动态实现寻找k个节点的资金圈。

附图说明

图1为一种实施方式的基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法的流程图；

图2为一种实施方式的基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法的业务需求确定的迭代条件的流程图；

图3为一种实施方式的基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法的由src节点向dst节点传递的流程图；

图4为一种实施方式的基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法的Pregel计算模型图；

图5为一种实施方式的基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法的经典的资金圈形态示意图。

具体实施方式

以下结合附图1-5对本发明作进一步详细说明。

实施例

一种基于Pregel的实现挖掘商业银行交易数据的资金圈分布的方法，包括如下步骤：

步骤1：以转账交易数据构建边，形成一个有向图，图中每一条边都是一个转账交易行为，边的表达形式如下：(a,b,attrs),整个有向图的数学形式为：[(srcId,srcAttr),(dstId,dstAttr),(attr)]；

其中a，b代表企业实体，attrs代表a和b转账行为的自有属性，比如转账的时间，转账的金额、转账设备的ID以及转账设备网络IP地址，举个真实的例子：(a,b,(time,money))；

其中，srcId为a转账方节点id；

其中，srcAttr为a转账方节点自身属性，比如企业属性，个人属性。

其中，dstId为b转账方节点id；

其中，dstAttr为b转账方节点自身属性

其中，attr为转账属性，比如转账金额，时间，转账类型，用途；

步骤2：利用Spark大数据的pregel，设计迭代算法，基于pregel实现，找出成环的资金流向，具体的逻辑，要根据业务需求而定，但本质的迭代是不变的，变的是“业务需求约定的迭代条件”。比如，经典的业务需求为，限定前一笔转账和后一笔转账之间，满足一定的时间间隔条件，金额百分比条件，抽象来说，业务需求确定的迭代条件如图2所示，F代表约束关系，或称为迭代条件，任何两笔相邻的转账都符合该种约束关系，F可以为线性的，也可以为非线性的，但一般在实际业务中，F不会太复杂，一般为线性。比如，F表示后一笔转账金额大于前一笔金的50％，或者是前一笔转账和后一笔转账的时间间隔在15天内。这种情况下，F与转账金额，转账时间有关。抽象表达如下：

F～(factor1,factor2,..)

其中，Factor，factor2表示迭代条件的要素，也是一笔转账里包含的属性，在图中为边属性。

其中，所述步骤2中的迭代算法设计依据为根据业务需求而定，且业务需求限定为：Attr(x)＝F(Attr(x-1))，其中，Attr代表某笔交易的转账属性，Attr(x-1)代表x-1刻的交易，Attr(x)代表第x刻的交易，F代表约束关系，或称为迭代条件，任何两笔相邻的转账都符合该种约束关系。

其中，当F与转账金额，转账时间有关时，抽象表达如下：

F～(factor1,factor2,..)

其中，Factor，factor2表示迭代条件的要素，也是一笔转账里包含的属性，在图中为边属性。

其中，假设限定迭代条件F～(factor1，factor2,...)，迭代算法步骤如下：

S1：对有向图中所有节点设定初始属性attr，且attr包含srcId,作为自身节点的初始化属性id，以及自定义属性，用自己的节点id作为所属强连通分支的id，并将所有节点打上初始标记false；

S2：首先做循环，将只有出边或入边的节点标记为true，将“只存在单向边的或者孤立的节点”和“已经确认且打好标记的强连通分量”中的被标记为true的节点从有向图中去除；

S3：初始化完成自身的属性后，基于Pregel计算框架，开始分布式进行有向图的信息传递，图中每一条边沿着出边由src节点向dst节点发送自己的属性id，并且设置如下规则，只允许属性id小的节点向属性id大的节点传递信息，或者属性值大的往属性小的传递，取决于实现方法，该种操作会决定哪个节点会作为强连通分量的唯一性标记；

其中，在由src节点向dst节点传递的过程中，为了实现两笔转账的约束条件F，需要做如下操作如图3所示：

在A传递到B的时候，需要连带边属性attr传入给B，作为B的节点属性，也即自定义属性，之后B传递给C时，B的节点属性需要与B-C转账的边属性进行比较，且需要满足F条件，否则B-C不往下传递，抽象表示如下：

F(attrAB,attrBC)＝F(srcAttr_B,attrBC)＝true

S4：当深搜结束，Pregel中是人为设置遍历深度，默认为原图已被“着色”，有向图开始反向遍历，为着色完成的图中节点反向打标签以确定是否完成强连通分支id标记，在着色完成的图中，节点id与节点属性id相同时，则表明该节点是自身所处强连通分支的root节点，则节点标签标记为true。之后，有向图中所有节点沿着入边由dst节点向src节点发送自身标记情况，只要节点收到true消息，则该节点便标记为true；

S5：反向遍历同样深度(这里指正向遍历深度)后，遍历到的节点完成了强连通分量的标记，然后将该部分节点从原图中删除，作为返回结果的一部分，剩下的节点构成新的原图，重新执行步骤S1-S4，直到整张图所有节点被删除干净。

其中，在由dst节点向src节点传递的过程中，需要满足：

F逆(attrBC,attrAB)＝F逆(srcAttr_C,attrBC)＝true

其中，F逆表示F的逆转条件，即从dst出发去看待F条件。举个例子,F代表前后两笔转账的金额保证前一笔是后一笔的1倍以上，则F逆表示，后一笔的转账必须要小于前一笔的50％金额。这点很关键，因为两个节点的转账往往在两笔及以上(这点在业务中非常常见)，如果没有满足F逆条件，有可能从dst出发传递到src会找到错的路径。

另外，为了更好的理解本技术方案，以下介绍一些基本概念；

(1)Spark：ApacheSpark是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UCBerkeleyAMPlab(加州大学伯克利分校的AMP实验室)所开源的类HadoopMapReduce的通用并行框架，Spark，拥有HadoopMapReduce所具有的优点；但不同于MapReduce的是——Job中间输出结果可以保存在内存中，从而不再需要读写HDFS，因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce的算法；

(2)pregel技术：pregel是Google自2009年开始对外公开的图计算算法和系统，主要用于解决无法在单机环境下计算的大规模图论计算问题。图计算的实际应用非常广泛，因此自Pregel公开之后，一些开源的方案也被实现出来，其中最出名的实现方案是Spark的graphxpregelapi。Pregel集成在spark中，能够以分布式的方式处理大规模的图数据，并且能和spark的RDD，DataFrameapi无缝结合，实现很多业务上的处理。所以商业银行或金融其他领域中使用最多。Pregel计算模型如附图4所示；

其中，Pregel计算时采用分布式迭代，黑色球代表该节点被激活,被激活代表信息可以继续往下传递。当A-B的边属性与B-C的边属性满足一定约束条件，则B可以往下传递，则C也被激活。同理，当D被激活时，但C-D边属性与A-D属性没有符合约束条件，则D不往E继续传递，此时D就是传递的终点。

(3)有向图强连通分量：在有向图G中，如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(stronglyconnectedcomponents)。

此外，还需奥说明的是经典的资金圈形态大致如附图5所示，图中4个实体形成了圈，每个实体代表一个银行客户，每一条边代表一笔转账交易行为，可以看出，这几个实体形成了一种“闭环”的交易。在商业银行的业务形态里，该种交易类型需要额外关注。形成资金圈的实体个数是不确定的，按照行业经验，一个资金圈中3-10个实体比较多，但其转账形式会错综复杂，并最终形成一个圈，图中金额数字只是为了便于理解而列举，并不是为了限定本发明所要保护的金额范围。

综上所述，本发明寻找资金圈的最终效果如下：a->b->c->a，传统做法是基于sql,一层一层的join,当需要寻找n个节点的圈，需要join(n-1)次，并且要判断起点和终点一致。传统做法有多种弊端，本发明方法可以实现解决如下问题：

1.解决传统做法由于多次大表join,产生笛卡尔积导致计算量过大，且由于数据倾斜导致性能不佳的情况，而且该种压力随着join层数越来越深，而越来越大，本发明方法依旧是逐层迭代，但不需要多次大表join；

2.解决传统做法由于多次join,代码冗余，且不能灵活跟随资金圈的节点个数的问题,比如，当想要10个节点数量的资金圈，则要写9次sql,但若下次想要寻找12个节点的圈，则要写11个sql，这样不方便代码迁移,本次发明的做法支持不改变原有任何代码逻辑，将代码打包，并且只需要在配置文件中配置层次参数，就能动态实现寻找k个节点的资金圈。

本发明中未涉及部分均与现有技术相同或可采用现有技术加以实现。本具体实施例仅仅是对本发明的解释，其并不是对本发明的限制，本领域技术人员在阅读完本说明书后可以根据需要对本实施例做出没有创造性贡献的修改，但只要在本发明的权利要求范围内都受到专利法的保护。