广州seo网站开发,徐州在线网,搜索引擎的作用,做网站需要什么技术人员第十届CCF大数据与计算智能大赛#xff08;2022 CCF BDCI#xff09;已圆满结束#xff0c;大赛官方竞赛平台DataFountain#xff08;简称DF平台#xff09;正在陆续释出各赛题获奖队伍的方案思路#xff0c;欢迎广大数据科学家交流讨论。
本方案为【大规模金融图数据中…第十届CCF大数据与计算智能大赛2022 CCF BDCI已圆满结束大赛官方竞赛平台DataFountain简称DF平台正在陆续释出各赛题获奖队伍的方案思路欢迎广大数据科学家交流讨论。
本方案为【大规模金融图数据中异常风险行为模式挖掘】赛题的一等奖获奖方案赛题地址https://www.datafountain.cn/competitions/586戳底部“阅读原文”可直达 获奖团队简介
团队名称NUFE
团队成员队长韩鲁峰就职于南京财经大学高级工程师。队员张斌就职于南京财经大学工程师。
团队荣誉2018年华为软件精英挑战赛季军、2020年CCF BDCI 基于买方意向的货物撮合交易二等奖、2019华为云鲲鹏开发者大赛决赛第二名、2021 CCF BDCI大规模金融仿真图数据中金融交易环路查询的设计与性能优化二等奖。
所获奖项一等奖
摘 要
图计算在金融场景的运用最为成熟贷前审批、贷后管理、反欺诈、反洗钱等业务均对图计算能力有要求包含但不限于k度邻居、找环、社区发现。业界常用的频繁子图挖掘算法可以帮助发现高频出现的子图结构如何使用频繁子图挖掘算法高效地进行异常风险行为模式挖掘显得尤为重要。
本赛题要求在尽可能短的时间内挖掘出不小于频繁度f 10000的频繁子图模式集合。子图同构是NP难问题。虽然可以使用图的编码来代替同构计算但是此类方法的复杂度也相当高另外还存在历史结果的使用问题。
针对题目要求本文主要做了以下几个方面的工作 在题目要求下输出准确的频繁模式以及模式对应的频繁度。 多次压缩编码数组的长度可以遍历数据集一次求出就将所有的候选模式的频繁度求出。 重新构图减少图结构大小增加缓存命中率。 通过实验验证此方法的高效性准确性。
关 键 词
子图同构频繁模式NP难问题
1 背景及算法介绍
1.1 背景介绍
频繁子图挖掘的两个难点是支持度的计算和候选子图的生成支持度计算中的子图同构是NP 难题虽然可以使用图的编码来代替同构测试但是此类方法的复杂度也相当高另外还存在历史结果的使用问题。如果使用历史同构图的信息可以加快测试的速度但是会极大增加存储量反之不使用在同构测试方面又会做大量的重复工作候选子图生成如果没有高效的剪枝算法会产生大量的冗余结果对存储和支持度的计算都是一个极大的考验。单一大图频繁子图挖掘当前已经多种算法主要包括非精确挖掘算法(SUBDUESEus)、不相交子图挖掘算法GrewSiGram、分布式挖掘算法MRPFMRSUB和CSP 搜索挖掘算法GRAMI[3]等。2014年提出的GRAMI算法将难点转为限制约束问题该算法在单机频繁子图挖掘中效较好。本文简化的编码方式先通过图拓展算出3阶候选模式然后计算候选模式的MNI支持度作为最终模式的支持度。
1.2 算法介绍
赛题使用简化的金融仿真数据数据为带有时间戳和金额的账户间交易、转账等数据。基于此数据自动挖掘出不小于频繁度f 10000的频繁子图模式集合。本次给到的图是属性图结构判定子图同构的方法需要属性值匹配严格匹配属性包括名称、金额、策略名和业务编码。本文算法流程图如图1各个步骤的细节将在下一章详细介绍。 图1
2 本方案流程
2.1 读取数据及优化
点数据和边数据如下所示点数据中有效字段为id和name边数据中有效字段为id金额策略名和业务编码。数据分析后发现点数据中name只有三种类型Jobs、Mike和John需要将name映射成{012}的数字方便编码此处我们计算name每个字节的ASCII和映射到固定数字上而不需要用Hash表。边数据中策略名和业务编码只有最后一个字符不一样所以解析这两个字段时只用解析最后一个字符这样既可以方便后续的编码又可以节省解析时间。
点数据
799999,Jobs,1587334106293,0
799998,John,1585916964769,0
799997,Jobs,1587852713474,0
799996,Jobs,1585425941502,0
799995,Mike,1586242334882,0
799994,Jobs,1584384932575,0
边数据
684821,434860,1590492254126,5.0,strategy_name-4,1590492251120278,buscode3,,,,,,
684821,434860,1591061355388,0.0,strategy_name-4,159106135809535,buscode3,,,,,,
684821,434860,1590945232703,33.0,strategy_name-4,159094523696782,buscode3,,,,,,
349837,98007,1587894603848,2.0,strategy_name-4,158789460447921,buscode1,,,,,,
181713,317857,1588705807550,40.0,strategy_name-4,158870580500216,buscode2,,,,,,
181713,317857,1588326392299,10.0,strategy_name-4,158832639552221,buscode2,,,,,,
104178,101658,1589394253501,11.0,strategy_name-6,158939425206018,buscode1,,,,,,
我们将代码优化前进行了对比测试如下图2。可发现优化后无论是单线程还是多线程的读取速度都得到显著提升。 图2
2.2 图剪枝及重构
Grami在解决单一大图频繁子图挖掘性能表现优异它采用CSP计算子图同构来代替存储实例。并且根据问题的定义在计算支持度时并不计算子图的精确的支持度而是只证明子图的支持度大于阈值就停止。本文采用类似的方法在计算一阶子图频繁度时并不精确算出频繁度只计算其频繁度的最大值,将不满足阈值的边全部删掉保证频繁模式都在剩下边拓展图中即可。为了提高CPU缓存的命中率我们对剩下的边重新构图去掉不可能存在满足条件的3阶子图的边此外我们把每条边数据都存在uint64_t中提高缓存加载条数。虽然图重构增加了此部分的时间开销但在后续三阶子图查找过程中节省了很多的时间整体上程序运行速度得到了提高。
#define MERGE(a,b,c,d) ((uint64_t)(uint64_t(a) 32u|uint64_t(b)16u|uint64_t(c)8u| uint64_t(d)))
#define AIM(a) (uint32_t(a 32u))
#define AMT(a) (uint16_t(a16u))
#define STRATEGY(a) (uint8_t(a8u))
#define BUSCODE(a) (uint8_t(a))
单条边的编码我们采用进制编码的形式具体实现过程如下
radixmax_amt*max_buscode*max_strategy*max_name*max_name;
radix_max_amt*max_buscode*max_strategy*max_name;
radix__max_amt*max_buscode*max_strategy;
radix___max_buscode*max_strategy;
radix____max_buscode;
uint32_tcode0;
coderadix_*account_ids[src_id];
coderadix__*account_ids[aim_ids[edge_id]];
coderadix___*amts[edge_id];
coderadix____*strategy_names[edge_id];
codebuscodes[edge_id];
2.3 确定候选模式
一阶子图使用DFS向后拓展拓展过程不精确计算频繁模式的支持度。虽然会存在不满足MNI支持度的子图但时可以确保正确答案的频繁模式集合是候选模式集合的子集。3阶子图不能直接使用上面的进制编码需要将一阶的进制编码重新编码一阶编码中存在大量小于阈值的编码所以可以将满足阈值的编码重新编码到成新整数减小最大编码的值使三阶子图也可以使用上述编码方法只是每条边都需要二次编码。具体过程如下图3其中阈值为10000对于小于阈值的边不需要二次编码。 图3
2.4 计算频繁度
通过上述方法求出候选模式后分别求出每个模式的频繁度。正常情况下如果有n种候选模式需要搜索n次图由于本题中候选模式较少可以通过二维数组遍历一次图求出所有模式的频繁度。这里需要将三阶子图编码进行再次编码。减小二维数组的规模编码方式参考图3去掉不满足条件的模式编码。在计算频繁度时采用MNIminimum image based suppor支持度就是找到节点映射数量的最小值。具体过程如图4图中MNI值为3。 图4
2.5 充分利用并行运算
在程序的各个阶段都尽量使用并行运算我们使用OpenMP并行库支持程序的任意线程的并行化该并行库编降低的并行编程的难度让我们把时间都投入到优化算法本身而并非并发编程。
3 实验结果与分析
本题数据集有四个文件2个点文件2个边文件
account顶点数800000
card顶点数600000
account_to_card边数3410191
account_to_account边数6010512 表1执行时间
通过表1可以看出本方案执行时间比第二名优化了20%证明本文的优化方案效果更加明显。
致谢
这次比赛让我们深入了解了性能优化相关算法通过阅读大量的前沿论文以及自我思考不断突破自己的极限分数。感谢主办方提供这样的平台让我们有幸参与其中与其他选手共同比拼进步。感谢出题方出了一道这么有趣的题目从实际业务需求抽象成赛题。感谢工作人员的辛苦答疑让我们在比赛中更轻松更快速的解决问题。希望CCF BDCI越办越好。
参考
[1] Wang Wei Zhou Haofeng, Yuan Qingqing, etc., frequent pattern mining based on graph theory[J]. Journal of computer research and development, 2005, and (2) : 230-235.王伟周浩峰袁青青等。基于图论的明频繁模式[J]。计算机研究与发展2005,42(2):230-235。
[2] 李先通,李建中,高宏.一种高效频繁子图挖掘算法[J].软件学报,2007,18(10):2469-2480.LI Xiantong, LI Jianzhong, GAO Hong. AN efficient frequent subgraph mining algorithm [J]. Journal of Software,2007, 18(10) : 2469-2480.
[3] Bhuiyan M A, Hasan M A. An Iterative MapReduce Based Frequent Subgraph Mining Algorithm [J]. Knowledge Data Engineering IEEE Transactions on, 2015, 27(3):608-620. 我是行业领先的大数据竞赛平台 DataFountain 欢迎广大政企校军单位合作办赛推动优秀数据人才揭榜挂帅
