第十屆CCF大數(shù)據(jù)與計算智能大賽（2022 CCF BDCI）已圓滿結(jié)束，大賽官方競賽平臺DataFountain（簡稱DF平臺）正在陸續(xù)釋出各賽題獲獎隊伍的方案思路，歡迎廣大數(shù)據(jù)科學家交流討論。

本方案為【大規(guī)模金融圖數(shù)據(jù)中異常風險行為模式挖掘】賽題的二等獎獲獎方案，賽題地址：https://www.datafountain.cn/competitions/586

獲獎團隊簡介

團隊名稱：Aries

團隊成員：本團隊屬校企聯(lián)合團隊，由江蘇電信和北京師范大學組成，主要研究方向包括數(shù)據(jù)挖掘，云原生，AI，應用統(tǒng)計分析等，團隊具有一定的項目經(jīng)歷和比賽經(jīng)驗。

所獲獎項：二等獎

摘? ?要

隨著圖數(shù)據(jù)的日益普及,圖挖掘已成為圖分析的一項基本任務,其中頻繁子圖及模式挖掘作為重要一環(huán)已經(jīng)被廣泛應用在各個領域。在這個方向已經(jīng)有大量的文獻被發(fā)表,并取得了巨大的進步。隨著頻繁模式挖掘的深入研究,圖模型被廣泛地應用于為各種事務建模,因此圖挖掘的研究顯得越來越重要。

針對本賽題要求，本文主要做了以下四個方面工作：1、挖掘出滿足閾值要求的的頻繁模式。2、精確計算模式頻繁的頻繁度。3、面向數(shù)據(jù)編程，盡可能優(yōu)化程序處理時間。4、使用OpenMP多線程框架，使程序在各個階段的性能都得到優(yōu)化。根據(jù)本隊伍實際執(zhí)行結(jié)果證明上述處理過程可以快速解決問題。

關 鍵 詞

頻繁子圖，模式挖掘，頻繁度

1 背景介紹

1.1 頻繁子圖挖掘介紹

頻繁子圖挖掘是數(shù)據(jù)挖掘中一個非常廣泛的應用。頻繁子圖挖掘是指從大量的圖中挖掘出滿足給定支持度的頻繁子圖，同時算法需要保證這些頻繁圖不能重復。頻繁模式挖掘主要就是應用兩種策略——Apriori和Growth。最早的AGM和FSG就分別實現(xiàn)了這兩重策略的基本思想。gSpan是一個非常高效的算法，它利用dfs-code序列對搜索樹進行編碼，并且制定一系列比較規(guī)則，從而保證最后只得到序列“最小”的頻繁圖集合。在頻繁模式挖掘算法中，常用方法是先計算候選模式的可能性空間，再確定頻繁度，由于查找子圖模式需要判斷子圖同構(gòu)，而判斷子圖同構(gòu)是NP完全問題[1]，因此計算代價非常大?；趩我淮髨D頻繁子圖挖掘、頻繁圖模式挖掘算法GRAMI[2]可以利用多種巧妙的剪枝算法提升挖掘性能。子圖生成過程中采用了GSAPN中的最右路擴展，從而保證了搜索空間是完備的。在計算圖的支持度時，理論上也是精確的。但算法也提供了支持度的近似算法，近似算法保證了挖掘的子圖一定是頻繁的，但不是所有頻繁的子圖都能獲得，如果要獲得所有頻繁子圖需要調(diào)整支持度大小。?

1.2 本題方案簡介

本賽題使用簡化的金融仿真數(shù)據(jù)，數(shù)據(jù)帶有時間戳和金額的賬戶間交易、轉(zhuǎn)賬等數(shù)據(jù)。基于此數(shù)據(jù)自動挖掘出不小于頻繁度（f >= 10000）的頻繁子圖模式集合。判定子圖同構(gòu)的方法需要屬性值匹配，包括交易金額、策略名、業(yè)務編碼及名稱。子圖只需匹配到3階（3條邊）子圖，頻繁度指標需滿足單調(diào)性要求。

本方案主要將頻繁子圖挖掘分為兩個個階段：1：剪枝階段。按題目模式匹配的要求計算出每條邊的頻繁度，根據(jù)單調(diào)性要求，將不滿足支持度的邊去掉，可以為后面挖掘二階三階子圖省去大量無效遍歷。2：精確計算頻繁度階段。利用近似的頻繁模式，根據(jù)單調(diào)性要求，精確計算出滿足閾值要求的模式頻繁度。具體流程圖見圖1.

圖1

2 算法設計與實現(xiàn)

我們將整體流程細分為5個步驟，分別是輸入、構(gòu)圖、剪枝、頻繁度計算和輸出。首先，需要將數(shù)據(jù)文檢讀取進內(nèi)存，用方便讀取的數(shù)據(jù)結(jié)構(gòu)存儲，因為是有向圖需要用偏移范圍作索引，可以實現(xiàn)根據(jù)邊起點的隨機遍歷。之后利用邊數(shù)據(jù)屬性值將邊編碼成一個整數(shù)，用整型數(shù)組對模式計數(shù)，刪除不滿足支持度要求的邊，因為基于單調(diào)性，其拓展的圖也不頻繁。這樣可以大大縮小了邊的數(shù)據(jù)規(guī)模。對候選模式求頻繁度，由于候選模式較少，可以用二維數(shù)組遍歷一次即可求出所有模式的頻繁度。在輸入、構(gòu)圖、剪枝和頻繁度四個階段都是用OpenMP并行處理，大大提高了程序運行效率。

2.1 輸入和構(gòu)圖

輸入部分主要是從點數(shù)據(jù)文件和邊數(shù)據(jù)文件讀入數(shù)據(jù)，數(shù)據(jù)約748MB，因為數(shù)據(jù)量較大，讀數(shù)據(jù)需要花很多時間，因此需要提高文件讀取速度，我們團隊采用mmap系統(tǒng)調(diào)用的方法讀取文件，將數(shù)據(jù)存儲到數(shù)組中。由于本賽題不僅考察答案的準確率，相同答案的情況下程序的運行時間也作為考察依據(jù)，為了加速文件讀取速度，我們采用多線程讀取，使用mmap映射后，根據(jù)文件的首地址和文件長度，按照字節(jié)長度將文件分配到多個任務中。上述為點數(shù)據(jù)的讀取。

struct Edge {

????uint32_t to;

????uint32_t amt;

????uint32_t strategy;

????uint32_t buscode;

} *edges;

uint32_t *loc;

邊數(shù)據(jù)讀取較為特殊，為了能方便后續(xù)算法根據(jù)起點可以快速遍歷，首先用多線程遍歷一次邊文件，將每個線程計算出的起點邊數(shù)和匯總在一個數(shù)組loc中，這樣若搜索定點s的邊的時候，其邊的范圍就是[loc[s],loc[s+1]]。結(jié)構(gòu)體中只存邊的屬性和目標點的信息。

2.2 剪枝

讀取的原始數(shù)據(jù)中，很多邊是不能滿足頻繁度要求的，根據(jù)單調(diào)性的約束，這些邊的拓展邊也不會滿足單調(diào)性約束，所以需要將這些無效邊刪除，這樣可以加速后續(xù)的處理。本方案使用flag數(shù)組標記邊的有效性，遍歷時遇到無效邊，就直接跳過。為了高效計數(shù)，我們沒有使用dfs-code編碼，而是根據(jù)邊的屬性映射到整數(shù)上，通過一個整型數(shù)組作為計數(shù)器。例如一條邊的屬性為{from：1，to：1，aim：0，strategy：1，buscode：1}，由于頂點只有3種類型（account_to_card可以用strategy區(qū)分），amt通過剪枝后有10種，strategy有6種，buscode有4種，這條邊可以描述為1*3*10*6*4+1*10*6*4+0*6*4+6*4+4，所有邊都可以通過此方法映射到對應的整數(shù)上。這里有個提升性能的方法，在不影響正確結(jié)果的情況下，可以適當將調(diào)整閾值調(diào)大，不過這樣會導致和GRAMI[2]算法同樣的問題，如果將閾值調(diào)整過大，只能保證挖掘的子圖一定是頻繁的，但不是所有頻繁的子圖都能獲得，所以要根據(jù)圖調(diào)整。?

2.3 三階邊頻繁度計算

三階頻繁度計算就是根據(jù)單調(diào)性的約束和閾值約束，求出滿足條件的模式的頻繁度。通過上述對一階邊的剪枝，可以將剩下的邊繼續(xù)拓展到二階三階中，也利用單調(diào)性和閾值的約束計算，但由于在處理三階邊的時候數(shù)值過大，無法將編碼映射到整數(shù)中，所以在剪枝后要將邊的值重新映射到數(shù)組中。重新映射后三階邊也可以映射到數(shù)據(jù)中，映射方式和一條邊類似。這樣就可以求出滿足條件模式的頻繁度。

2.4 輸出

將計算出的結(jié)果使用fastjosn輸出到文件中，輸出時間占比較少，所以沒用多線程處理。

3 實驗結(jié)果

程序測試的物理機配置為4核 3.4Ghz服務器，操作系統(tǒng)為ubuntu20.04。我們對程序的各個階段4個線程和單線程進行了比較，結(jié)果如下圖2，多線程在各個階段都顯著提高運行速度，整個程序在4個線程下只需要執(zhí)行0.92s，當然這是本地測試環(huán)境的結(jié)果，由于硬件配置不同，與線上結(jié)果有一些差別。

圖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)

---

我是行業(yè)領先的大數(shù)據(jù)競賽平臺?@DataFountain?，歡迎廣大政企校軍單位合作辦賽，推動優(yōu)秀數(shù)據(jù)人才揭榜掛帥！