第十届CCF大数据与计算智能大赛(2022 CCF BDCI)已圆满结束,大赛官方竞赛平台DataFountain(简称DF平台)正在陆续释出各赛题获奖队伍的方案思路,欢迎广大数据科学家交流讨论。
本方案为【大规模金融图数据中异常风险行为模式挖掘】赛题的二等奖获奖方案,赛题地址:https://www.datafountain.cn/competitions/586
获奖团队简介
团队名称:Aries
团队成员:本团队属校企联合团队,由江苏电信和北京师范大学组成,主要研究方向包括数据挖掘,云原生,AI,应用统计分析等,团队具有一定的项目经历和比赛经验。
所获奖项:二等奖
摘 要
随着图数据的日益普及,图挖掘已成为图分析的一项基本任务,其中频繁子图及模式挖掘作为重要一环已经被广泛应用在各个领域。在这个方向已经有大量的文献被发表,并取得了巨大的进步。随着频繁模式挖掘的深入研究,图模型被广泛地应用于为各种事务建模,因此图挖掘的研究显得越来越重要。
针对本赛题要求,本文主要做了以下四个方面工作:1、挖掘出满足阈值要求的的频繁模式。2、精确计算模式频繁的频繁度。3、面向数据编程,尽可能优化程序处理时间。4、使用OpenMP多线程框架,使程序在各个阶段的性能都得到优化。根据本队伍实际执行结果证明上述处理过程可以快速解决问题。
关 键 词
频繁子图,模式挖掘,频繁度
1 背景介绍
1.1 频繁子图挖掘介绍
频繁子图挖掘是数据挖掘中一个非常广泛的应用。频繁子图挖掘是指从大量的图中挖掘出满足给定支持度的频繁子图,同时算法需要保证这些频繁图不能重复。频繁模式挖掘主要就是应用两种策略——Apriori和Growth。最早的AGM和FSG就分别实现了这两重策略的基本思想。gSpan是一个非常高效的算法,它利用dfs-code序列对搜索树进行编码,并且制定一系列比较规则,从而保证最后只得到序列“最小”的频繁图集合。在频繁模式挖掘算法中,常用方法是先计算候选模式的可能性空间,再确定频繁度,由于查找子图模式需要判断子图同构,而判断子图同构是NP完全问题[1],因此计算代价非常大。基于单一大图频繁子图挖掘、频繁图模式挖掘算法GRAMI[2]可以利用多种巧妙的剪枝算法提升挖掘性能。子图生成过程中采用了GSAPN中的最右路扩展,从而保证了搜索空间是完备的。在计算图的支持度时,理论上也是精确的。但算法也提供了支持度的近似算法,近似算法保证了挖掘的子图一定是频繁的,但不是所有频繁的子图都能获得,如果要获得所有频繁子图需要调整支持度大小。
1.2 本题方案简介
本赛题使用简化的金融仿真数据,数据带有时间戳和金额的账户间交易、转账等数据。基于此数据自动挖掘出不小于频繁度(f >= 10000)的频繁子图模式集合。判定子图同构的方法需要属性值匹配,包括交易金额、策略名、业务编码及名称。子图只需匹配到3阶(3条边)子图,频繁度指标需满足单调性要求。
本方案主要将频繁子图挖掘分为两个个阶段:1:剪枝阶段。按题目模式匹配的要求计算出每条边的频繁度,根据单调性要求,将不满足支持度的边去掉,可以为后面挖掘二阶三阶子图省去大量无效遍历。2:精确计算频繁度阶段。利用近似的频繁模式,根据单调性要求,精确计算出满足阈值要求的模式频繁度。具体流程图见图1.
图1
2 算法设计与实现
我们将整体流程细分为5个步骤,分别是输入、构图、剪枝、频繁度计算和输出。首先,需要将数据文检读取进内存,用方便读取的数据结构存储,因为是有向图需要用偏移范围作索引,可以实现根据边起点的随机遍历。之后利用边数据属性值将边编码成一个整数,用整型数组对模式计数,删除不满足支持度要求的边,因为基于单调性,其拓展的图也不频繁。这样可以大大缩小了边的数据规模。对候选模式求频繁度,由于候选模式较少,可以用二维数组遍历一次即可求出所有模式的频繁度。在输入、构图、剪枝和频繁度四个阶段都是用OpenMP并行处理,大大提高了程序运行效率。
2.1 输入和构图
输入部分主要是从点数据文件和边数据文件读入数据,数据约748MB,因为数据量较大,读数据需要花很多时间,因此需要提高文件读取速度,我们团队采用mmap系统调用的方法读取文件,将数据存储到数组中。由于本赛题不仅考察答案的准确率,相同答案的情况下程序的运行时间也作为考察依据,为了加速文件读取速度,我们采用多线程读取,使用mmap映射后,根据文件的首地址和文件长度,按照字节长度将文件分配到多个任务中。上述为点数据的读取。
struct Edge {
uint32_t to;
uint32_t amt;
uint32_t strategy;
uint32_t buscode;
} *edges;
uint32_t *loc;
边数据读取较为特殊,为了能方便后续算法根据起点可以快速遍历,首先用多线程遍历一次边文件,将每个线程计算出的起点边数和汇总在一个数组loc中,这样若搜索定点s的边的时候,其边的范围就是[loc[s],loc[s+1]]。结构体中只存边的属性和目标点的信息。
2.2 剪枝
读取的原始数据中,很多边是不能满足频繁度要求的,根据单调性的约束,这些边的拓展边也不会满足单调性约束,所以需要将这些无效边删除,这样可以加速后续的处理。本方案使用flag数组标记边的有效性,遍历时遇到无效边,就直接跳过。为了高效计数,我们没有使用dfs-code编码,而是根据边的属性映射到整数上,通过一个整型数组作为计数器。例如一条边的属性为{from:1,to:1,aim:0,strategy:1,buscode:1},由于顶点只有3种类型(account_to_card可以用strategy区分),amt通过剪枝后有10种,strategy有6种,buscode有4种,这条边可以描述为1*3*10*6*4+1*10*6*4+0*6*4+6*4+4,所有边都可以通过此方法映射到对应的整数上。这里有个提升性能的方法,在不影响正确结果的情况下,可以适当将调整阈值调大,不过这样会导致和GRAMI[2]算法同样的问题,如果将阈值调整过大,只能保证挖掘的子图一定是频繁的,但不是所有频繁的子图都能获得,所以要根据图调整。
2.3 三阶边频繁度计算
三阶频繁度计算就是根据单调性的约束和阈值约束,求出满足条件的模式的频繁度。通过上述对一阶边的剪枝,可以将剩下的边继续拓展到二阶三阶中,也利用单调性和阈值的约束计算,但由于在处理三阶边的时候数值过大,无法将编码映射到整数中,所以在剪枝后要将边的值重新映射到数组中。重新映射后三阶边也可以映射到数据中,映射方式和一条边类似。这样就可以求出满足条件模式的频繁度。
2.4 输出
将计算出的结果使用fastjosn输出到文件中,输出时间占比较少,所以没用多线程处理。
3 实验结果
程序测试的物理机配置为4核 3.4Ghz服务器,操作系统为ubuntu20.04。我们对程序的各个阶段4个线程和单线程进行了比较,结果如下图2,多线程在各个阶段都显著提高运行速度,整个程序在4个线程下只需要执行0.92s,当然这是本地测试环境的结果,由于硬件配置不同,与线上结果有一些差别。
图2
致谢
感谢赛事的所有工作人员,他们默默无闻的努力,无微不至的付出,是支撑大赛顺利运行的坚定基石。感谢队友的努力付出,才能让我们团队进入最终决赛。
参考
[1] Wernicke S. Rasche F. FANMOD: A tool for fast network motif detection. Bioinformatics. 2006. 22(9) : 1152-1153
[2] GraMi:frequent subgraph and pattern mining in a single large graph [J] . Elseidy Mohammed,Abdelhamid Ehab,Skiadopoulos Spiros,Kalnis Panos. Proceedings of the VLDB Endowment . 2014 (7)
我是行业领先的大数据竞赛平台 @DataFountain ,欢迎广大政企校军单位合作办赛,推动优秀数据人才揭榜挂帅!