【一等奖方案】大规模金融图数据中异常风险行为模式挖掘赛题「NUFE」解题思路

第十届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难问题。虽然可以使用图的编码来代替同构计算，但是此类方法的复杂度也相当高，另外还存在历史结果的使用问题。

针对题目要求本文主要做了以下几个方面的工作：

  1. 在题目要求下输出准确的频繁模式以及模式对应的频繁度。

  2. 多次压缩编码数组的长度，可以遍历数据集一次求出就将所有的候选模式的频繁度求出。

  3. 重新构图，减少图结构大小，增加缓存命中率。

  4. 通过实验验证此方法的高效性，准确性。

关 键 词

子图同构，频繁模式，NP难问题

1 背景及算法介绍

1.1 背景介绍

频繁子图挖掘的两个难点是支持度的计算和候选子图的生成，支持度计算中的子图同构是NP 难题，虽然可以使用图的编码来代替同构测试但是此类方法的复杂度也相当高，另外还存在历史结果的使用问题。如果使用历史同构图的信息可以加快测试的速度，但是会极大增加存储量，反之不使用，在同构测试方面又会做大量的重复工作；候选子图生成如果没有高效的剪枝算法会产生大量的冗余结果，对存储和支持度的计算都是一个极大的考验。单一大图频繁子图挖掘当前已经多种算法，主要包括非精确挖掘算法(SUBDUE，SEus)、不相交子图挖掘算法（Grew，SiGram）、分布式挖掘算法（MRPF，MRSUB）和CSP 搜索挖掘算法（GRAMI[3]）等。2014年提出的GRAMI算法将难点转为限制约束问题，该算法在单机频繁子图挖掘中效较好。本文简化的编码方式，先通过图拓展算出3阶候选模式，然后计算候选模式的MNI支持度作为最终模式的支持度。

1.2 算法介绍

赛题使用简化的金融仿真数据，数据为带有时间戳和金额的账户间交易、转账等数据。基于此数据自动挖掘出不小于频繁度（f >= 10000）的频繁子图模式集合。本次给到的图是属性图结构，判定子图同构的方法需要属性值匹配，严格匹配属性包括：名称、金额、策略名和业务编码。本文算法流程图如图1，各个步骤的细节将在下一章详细介绍。

图片

图1

2 本方案流程

2.1 读取数据及优化

点数据和边数据如下所示，点数据中有效字段为id和name，边数据中有效字段为id，金额，策略名和业务编码。数据分析后发现，点数据中name只有三种类型Jobs、Mike和John，需要将name映射成{0，1，2}的数字方便编码，此处我们计算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(a>>16u))

#define STRATEGY(a) (uint8_t(a>>8u))

#define BUSCODE(a) (uint8_t(a))

单条边的编码我们采用进制编码的形式，具体实现过程如下：

radix=max_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_tcode=0;

code+=radix_*account_ids[src_id];

code+=radix__*account_ids[aim_ids[edge_id]];

code+=radix___*amts[edge_id];

code+=radix____*strategy_names[edge_id];

code+=buscodes[edge_id];

2.3 确定候选模式

一阶子图使用DFS向后拓展，拓展过程不精确计算频繁模式的支持度。虽然会存在不满足MNI支持度的子图，但时可以确保正确答案的频繁模式集合是候选模式集合的子集。3阶子图不能直接使用上面的进制编码，需要将一阶的进制编码重新编码，一阶编码中存在大量小于阈值的编码，所以可以将满足阈值的编码重新编码到成新整数，减小最大编码的值，使三阶子图也可以使用上述编码方法，只是每条边都需要二次编码。具体过程如下图3，其中阈值为10000，对于小于阈值的边，不需要二次编码。

图片

图3

2.4 计算频繁度

通过上述方法求出候选模式后，分别求出每个模式的频繁度。正常情况下如果有n种候选模式，需要搜索n次图，由于本题中候选模式较少，可以通过二维数组遍历一次图求出所有模式的频繁度。这里需要将三阶子图编码进行再次编码。减小二维数组的规模，编码方式参考图3，去掉不满足条件的模式编码。在计算频繁度时，采用MNI（minimum 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 ，欢迎广大政企校军单位合作办赛，推动优秀数据人才揭榜挂帅！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/102124.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JDBC使用了哪种设计模式

JDBC使用了哪种设计模式

JDK中提供了操作数据库的接口&#xff0c;比如 java.sql.Driver java.sql.Connection java.sql.Statement java.sql.PreparedStatement 不同的数据库厂商提供操作自己数据库的驱动包&#xff0c; 比如mysql public class Driver extends NonRegisteringDriver implements jav…
阅读更多...
10. selenium API （二）

10. selenium API （二）

目录 1. 多层框架/窗口定位 2. 下拉框处理 2.1 前端界面 2.2 代码 3. 针对 alert 弹窗进行操作 3.1 前端界面 3.2 代码 4. 文件提交 4.1 前端界面 4.2 代码 5. 显示等待 6. 操作浏览器滚动条 7. 截图 8. 浏览器关闭 9. 窗口切换 在上篇文章中&#xff0c;我们学…
阅读更多...
Django请求的生命周期

Django请求的生命周期

Django请求的生命周期是指: 当用户在浏览器上输入URL到用户看到网页的这个时间段内&#xff0c;Django后台所发生的事情。 直白的来说就是当请求来的时候和请求走的阶段中&#xff0c;Django的执行轨迹。 一个完整的Django生命周期: 用户从客户端发出一条请求以后&#xff…
阅读更多...
css3英文文字换行，超过两行...展示

css3英文文字换行，超过两行...展示

需求&#xff1a;超过两行...展示 开发的过程中发现div内容中文可以换行英文不换行&#xff0c;导致长度会溢出。 是英文全英文的话浏览器会解析成一个单词&#xff0c; 加上这句就好了 word-break:break-all; 一开始不知道是会解析成一个单词&#xff0c;用字符串拼接处理…
阅读更多...
华为云新生代开发者招募

华为云新生代开发者招募

开发者您好&#xff0c;我们是华为2012UCD的研究团队 为了解年轻开发者的开发现状和趋势 正在邀请各位先锋开发者&#xff0c;与我们进行2小时的线上交流&#xff08;江浙沪附近可线下交流&#xff09; 聊聊您日常开发工作中的产品使用需求 成功参与访谈者将获得至少300元京…
阅读更多...
基于亚马逊云科技无服务器服务快速搭建电商平台——性能篇

基于亚马逊云科技无服务器服务快速搭建电商平台——性能篇

使用 Serverless 构建独立站的优势 在传统架构模式下&#xff0c;如果需要进行电商大促需要提前预置计算资源以支撑高并发访问&#xff0c;会造成计算资源浪费并且增加运维工作量。本文介绍一种新的部署方式&#xff0c;将 WordPress 和 WooCommerce 部署在 Amazon Lambda 中。…
阅读更多...
CVPR2022 Semi-Supervised Semantic Segmentation Using Unreliable Pseudo-Labels

CVPR2022 Semi-Supervised Semantic Segmentation Using Unreliable Pseudo-Labels

Semi-Supervised Semantic Segmentation Using Unreliable Pseudo-Labels 使用不可靠的伪标签的半监督语义分割 Paper&#xff1a;https://openaccess.thecvf.com/content/CVPR2022/html/Wang_Semi-Supervised_Semantic_Segmentation_Using_Unreliable_Pseudo-Labels_CVPR_202…
阅读更多...
Docker 容器逃逸漏洞 (CVE-2020-15257)复现

Docker 容器逃逸漏洞 (CVE-2020-15257)复现

漏洞概述 containerd是行业标准的容器运行时&#xff0c;可作为Linux和Windows的守护程序使用。在版本1.3.9和1.4.3之前的容器中&#xff0c;容器填充的API不正确地暴露给主机网络容器。填充程序的API套接字的访问控制验证了连接过程的有效UID为0&#xff0c;但没有以其他方式…
阅读更多...
C语言：大小端字节序存储

C语言：大小端字节序存储

一、大小端字节序存储介绍 大端字节序存储模式&#xff1a;把一个数据低位字节处的数据存放在高地址处&#xff0c;数据高位字节处的数据存放在低地址处 小端字节序存储模式&#xff1a;把一个数据低位字节处的数据存放在低地址处&#xff0c;数据高位字节处的数据存放在高地址…
阅读更多...
论文阅读_医疗知识图谱_GraphCare

论文阅读_医疗知识图谱_GraphCare

英文名称: GraphCare: Enhancing Healthcare Predictions with Open-World Personalized Knowledge Graphs 中文名称: GraphCare&#xff1a;通过开放世界的个性化知识图增强医疗保健预测 文章: http://arxiv.org/abs/2305.12788 代码: https://github.com/pat-jj/GraphCare 作…
阅读更多...
mall ：hutool项目源码解析

mall ：hutool项目源码解析

文章目录 一、mall开源项目1.1 来源1.2 项目转移1.3 项目克隆 二、Hutool工具类库2.1 Hutool 简介 三、源码解析3.1 集成与配置3.1.1 导入依赖3.1.2 添加配置 3.2 核心工具类3.2.1 AnnotationUtil使用&#xff1a;注解工具类3.2.2 BeanUtil使用&#xff1a;JavaBean的工具类3.2…
阅读更多...
redis实战-实现优惠券秒杀解决超卖问题

redis实战-实现优惠券秒杀解决超卖问题

全局唯一ID 唯一ID的必要性 每个店铺都可以发布优惠券&#xff1a; 当用户抢购时&#xff0c;就会生成订单并保存到tb_voucher_order这张表中&#xff0c;而订单表如果使用数据库自增ID就存在一些问题&#xff1a; id的规律性太明显&#xff0c;容易被用户根据id的间隔来猜测…
阅读更多...
【Linux】【驱动】注册字符设备号

【Linux】【驱动】注册字符设备号

【Linux】【驱动】注册字符设备号 1. 绪论1 、静态分配设备号2、动态分配设备号3、注销设备号 2 实现的代码3 加载驱动程序 1. 绪论 在之前杂项设备的时候&#xff0c;设备号是固定的&#xff0c;字符设备就需要自己去申请设备号了&#xff0c; 申请设备号有两个方式&#xff…
阅读更多...
Python入门教程 - 基本语法 （一）

Python入门教程 - 基本语法 （一）

目录 一、注释 二、Python的六种数据类型 三、字符串、数字 控制台输出练习 四、变量及基本运算 五、type()语句查看数据的类型 六、字符串的3种不同定义方式 七、数据类型之间的转换 八、标识符命名规则规范 九、算数运算符 十、赋值运算符 十一、字符串扩展 11.1…
阅读更多...
如何飞速成为开源贡献者(Contributor)

如何飞速成为开源贡献者(Contributor)

如何飞速成为开源贡献者Contributor 一、环境信息1.1 硬件信息1.2 软件信息 二、Git安装2.1 Git介绍2.2 Git下载安装 三、开源项目选定四、GitHub参与开源流程4.1 Fork项目4.2 SSH配置4.2.1 为什么要配置SSH4.2.2 如何配置SSH 4.3 Clone项目4.4 IDEA关联4.5 PR生成4.6 PR提交 一…
阅读更多...
OceanBase 4.x改装：另一种全链路追踪的尝试

OceanBase 4.x改装：另一种全链路追踪的尝试

本文作者&#xff1a;夏克 OceanBase 社区文档贡献者&#xff0c;曾多次参与 OceanBase 技术征文比赛&#xff0c;获得优秀名次。从事金融行业核心系统设计开发工作多年&#xff0c;服务于某交易所子公司&#xff0c;现阶段负责国产数据库调研。 本文为 OceanBase 第七期技术征…
阅读更多...
java-数组

java-数组

数组静态初始化写法&#xff1a; //静态初始化数组 int[] age new int[] {7,18,19}; double[] scores new double[]{67.5,77.8,94.2,99};//静态初始化数组简化写法 int[] age1 {7,18,19}; double[] scores2 {67.5,77.8,94.2,99};数组在内存中定义方式&#xff1a; 1.在内…
阅读更多...
飞天使-python的面向对象

飞天使-python的面向对象

文章目录 面向对象面向对象思想类的定义和使用继承封装多态访问控制 参考视频 面向对象 面向对象思想 面向过程和面对对象的区别是什么&#xff1f; 答: 复用性高&#xff0c;面向对象类的定义和使用 类型里面的定义的时候 self 不能省去&#xff0c;应该写出 class person:…
阅读更多...
开源项目如何推进人工智能

开源项目如何推进人工智能

推荐&#xff1a;使用 NSDT场景编辑器快速搭建3D应用场景 对于那些不熟悉这个概念的人来说&#xff0c;开源软件或项目是那些向公众提供源代码的软件或项目&#xff0c;允许他们查看、使用和修改它。使用开源软件和工具具有多种优势&#xff0c;尤其是在构建复杂的基于 AI 的产…
阅读更多...
pytorch异常——RuntimeError:Given groups=1, weight of size..., expected of...

pytorch异常——RuntimeError:Given groups=1, weight of size..., expected of...

文章目录 省流异常报错异常截图异常代码原因解释修正代码执行结果 省流 nn.Conv2d 需要的输入张量格式为 (batch_size, channels, height, width)&#xff0c;但您的示例输入张量 x 是 (batch_size, height, width, channels)。因此&#xff0c;需要对输入张量进行转置。 注意…
阅读更多...
最新文章

Copyright @ 2022~2023