软膜做网站有用吗,优化系统是什么意思,怎么才能制作网站呢,长沙做一个网站多少钱第十届CCF大数据与计算智能大赛#xff08;2022 CCF BDCI#xff09;已圆满结束#xff0c;大赛官方竞赛平台DataFountain#xff08;简称DF平台#xff09;正在陆续释出各赛题获奖队伍的方案思路#xff0c;欢迎广大数据科学家交流讨论。
本方案为【大规模金融图数据中…第十届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[s1]]。结构体中只存边的属性和目标点的信息。
2.2 剪枝
读取的原始数据中很多边是不能满足频繁度要求的根据单调性的约束这些边的拓展边也不会满足单调性约束所以需要将这些无效边删除这样可以加速后续的处理。本方案使用flag数组标记边的有效性遍历时遇到无效边就直接跳过。为了高效计数我们没有使用dfs-code编码而是根据边的属性映射到整数上通过一个整型数组作为计数器。例如一条边的属性为{from1to1aim0strategy1buscode1}由于顶点只有3种类型account_to_card可以用strategy区分amt通过剪枝后有10种strategy有6种buscode有4种这条边可以描述为1*3*10*6*41*10*6*40*6*46*44所有边都可以通过此方法映射到对应的整数上。这里有个提升性能的方法在不影响正确结果的情况下可以适当将调整阈值调大不过这样会导致和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 欢迎广大政企校军单位合作办赛推动优秀数据人才揭榜挂帅
