基于密集子圖的銀行電信詐騙檢測方法

劉梟 王曉國

摘 要：目前銀行對電信詐騙的標記數據積累少，人工標記數據的代價大，導致電信詐騙檢測的有監督學習方法可使用的標記數據不足。針對這個問題，提出一種基于密集子圖的無監督學習方法用于電信詐騙的檢測。首先，通過在賬戶資源（IP地址和MAC地址統稱為資源）網絡搜索可疑度較高的子圖來識別欺詐賬戶;然后，設計了一種符合電信詐騙特性的子圖可疑度量;最后，提出一種磁盤駐留、線性內存消耗且有理論保障的可疑子圖搜索算法。在兩組模擬數據集上，所提方法的F1-score分別達到0.921和0.861，高于CrossSpot、fBox和EvilCohort算法，與M-Zoom算法的0.899和0.898相近，但是所提方法的平均運行時間和內存消耗峰值均小于M-Zoom算法;在真實數據集上，所提方法的F1-score達到0.550，高于fBox和EvilCohort算法，與M-Zoom算法的0.529相近。實驗結果表明，所提方法能較好地應用于現階段的銀行反電信詐騙業務，且非常適合于實際應用中的大規模數據集。

關鍵詞：?電信詐騙;無監督學習;欺詐檢測;密集子圖;貪心算法

中圖分類號：TP391.4

文獻標志碼：A

文章編號：1001-9081（2019）04-1214-06

Abstract： Lack of labeled data accumulated for telecommunication fraud in the bank and high cost of manually labeling cause the insufficiency of labeled data that can be used in supervised learning methods for telecommunication fraud detection. To solve this problem， an unsupervised learning method based on dense subgraph was proposed to detect telecommunication fraud. Firstly， subgraphs with high anomaly degree in the network of accounts and resources （IP addresses and MAC addresses） were searched to identify fraud accounts. Then， a subgraph anomaly degree metric satisfying the features of telecommunication fraud was designed. Finally， a suspicious subgraph searching algorithm with resident disk， efficient memory and theory guarantee was proposed. On two synthetic datasets， the F1-scores of the proposed method are 0.921 and 0.861， which are higher than those of CrossSpot， fBox and EvilCohort algorithms while very close to those of M-Zoom algorithm （0.899 and 0.898）， but the average running time and memory consumption peak of the proposed method are less than those of M-Zoom algorithm. On real-world dataset， F1-score of the proposed method is 0.550， which is higher than that of fBox and EvilCohort while very close to that of M-Zoom algorithm （0.529）. Theoretical analysis and simulation results show that the proposed method can be applied to telecommunication fraud detection in the bank effectively， and is suitable for big datasets in practice.

Key words： telecommunication fraud; unsupervised learning; fraud detection; dense subgraph; greedy algorithm

0?引言

隨著互聯網技術的發展， 人們越來越多地使用電子銀行進行資金操作，據《2016中國電子銀行調查報告》顯示，全國個人網銀用戶和個人手機銀行用戶比例分別達到46%和42%。 據《騰訊2017年第三季度反電信網絡詐騙大數據報告》，顯示網絡詐騙、電話欺詐和短信詐騙合計造成資金損失44.1億，并且已經形成了完整的黑色產業鏈。本文根據合作銀行的需求，對電信詐騙的檢測方法展開研究。

電信詐騙雖然表現形式繁多，但是從銀行交易的角度來看其流程可以概括為圖1所示。電信詐騙的第一步是欺詐者通過詐騙使正常賬戶向欺詐者控制的賬戶轉賬，正常賬戶向欺詐賬戶的轉賬稱為詐騙交易;第二步是欺詐者將騙取的資金通過大量欺詐賬戶進行分散轉移，使其難以被追回，這部分交易稱為洗錢交易;最后一步是欺詐者通過各種途徑對欺詐得到的資金進行提現，這部分交易稱為提現交易。有時提現交易也會直接在詐騙交易后進行。根據電信詐騙的流程，對電信詐騙的檢測可以從詐騙交易的特征、洗錢交易的特征和提現交易的特征三方面進行。本文從洗錢交易的特征入手，對欺詐者控制的賬戶的識別進行研究。

本文經研究發現許多欺詐賬戶共用一組相同的互聯網協議（Internet Protocol， IP）地址或者媒體訪問控制（Media Access Control， MAC）地址，如圖2（a）中顯示的45個欺詐賬戶的IP地址使用情況;而圖2（b）中正常賬戶使用的IP地址則比較分散。本文推測該現象產生的原因是欺詐者的人力、設備和網絡資源通常有限，但是控制的欺詐賬戶和需要的洗錢交易數量都比較大。這就會造成部分欺詐賬戶使用相同的設備和網絡資源進行交易的現象。

本文根據上述現象，提出了一種符合電信詐騙特征的子圖可疑度量，通過在賬戶資源網絡（IP地址和MAC地址統稱為資源）搜索可疑度較高的子圖來識別欺詐者控制的賬戶。

1?相關工作

基于賬戶交易特征的有監督學習方法在銀行欺詐檢測中應用廣泛。 這類方法通過在大量已標記的數據中提取能夠有效區分正常交易和欺詐交易的特征， 例如交易頻度、交易平均金額和交易網絡結構等，并使用這些特征，通過機器學習的方法訓練分類器，最終利用訓練好的分類器來識別交易是否為欺詐交易。Jha等[1]提取了基于不同時間窗口的RFM（Recency， Frequency and Monetary）特征用于訓練邏輯回歸分類模型，并以此模型來檢測信用卡欺詐。van Vlasselaer等[2]在RFM特征中加了基于PageRank的交易網絡結構特征，發現該特征可以提升模型的分類性能。Bahnsen等[3]在研究中發現許多賬戶的交易通常發生在每天的固定時間段內，呈現出一定的周期性。 針對這一發現，他們構建了基于von Mises分布的交易周期特征，與RFM特征結合可以進一步提升信用卡欺詐的識別率。相似的方法也應用于銀行的洗錢交易識別[3-6]。在電信詐騙問題中獲取大量的人工標記樣本成本高，有監督學習的方法將面臨標記數據不足的問題，特別是工作剛展開的時候。

在反洗錢的研究中，也有部分學者采用無監督學習的方法[7-9]。Michalak等[7]認為洗錢賬戶在交易網絡中通常會構成特定結構的子圖，并提出了一種基于模糊子圖匹配的方法來檢測洗錢賬戶。喻煒等[8]提出了基于交易網絡特征向量中心度量，并結合時序檢測分析用于檢測洗錢交易。Soltani等[9]認為洗錢賬戶在交易網絡中通常具有相似的結構特征，并提出一種基于結構相似性的聚類方法來檢測洗錢賬戶。Soltani等[9]提出了交易匹配的概念：如果交易A的轉入賬戶和交易B的轉出賬戶相同， 且交易A和B的交易時間與交易金額都相近， 則交易A和B匹配。在由匹配交易構成的交易網絡的子圖中，使用SHRINK算法[10]進行聚類來識別洗錢賬戶。文獻[7-9]的無監督方法僅適用于賬戶交易網絡，而不適用于本文需要分析的賬戶資源網絡。

在社交網絡的研究中，對基于密集子圖的欺詐檢測方法有著廣泛研究。文獻[11]中發現在郵件系統和社交網絡中的欺詐賬戶經常會使用相同的IP地址，并依此提出了EvilCohort算法。EvilCohort首先根據賬戶間共用IP地址的數量構建賬戶相似網絡，網絡中邊的權重表示兩個賬戶間共用IP地址地數量，然后使用Louvain算法[12]優化賬戶相似網絡的Modularity，從而找出網絡中較大的賬戶社區并認為社區中的賬戶均為欺詐賬戶。Prakas等[13]提出了EigenSpokes算法，該方法使用奇異值分解（Singular Value Decomposition， SVD）對圖的鄰接矩陣進行分解，然后根據特征值較大的特征向量的特征來識別欺詐賬戶。EigenSpokes通常能發現規模較大且密度較高的欺詐賬戶社區，無法檢測到規模較小且密度較高的欺詐賬戶社區[14]。針對這個問題，Shah等[14]提出了fBox算法， fBox比較通過特征向量重構得到的節點度數和節點原始度數，來識別規模較小的欺詐賬戶組。Jiang等[15]提出了一種子圖可疑度量和其優化算法CrossSpot，用于發現數據中密度較高的行為。基于文獻[16]中提出的密集子圖貪心搜索算法，Shin等[17-18]提出了M-Zoom算法。但是文獻[16]中的搜索算法需要將整個圖讀入內存，空間復雜度較高。本文借鑒社交網絡的研究，設計了一種子圖可疑度量，并提出了一種空間復雜度較低且有理論保障的密集子圖搜索算法用于電信詐騙的檢測。該搜索算法只需對存儲中的圖文件進行順序讀寫，而不需要將整個圖讀入內存，從而減少了內存消耗，更適合于實際應用中的大規模數據集。

2?檢測方法

圖3中展示了兩種不同的圖結構，兩個圖有相同的節點數和相同的邊數，但是兩類節點的比例不同。假設圖3中兩個圖中的所有邊的權重都設置為1。dbiased在圖3（a）中等于3，在圖3（b）中等于1.8。dbalanced在圖3（a）和圖3（b）中都等于1.8。dbalanced不受兩類節點的比例的影響，而dbiased會給不平衡度越高的子圖越大的可疑值。

2.2?電信詐騙檢測應用中的可疑度量設置

通過分析電信詐騙的數據，本文發現有一部分正常資源節點和大量的正常賬戶節點之間存在連接（呈圖3（a）中的結構），推測產生這種現象的原因是：1）目前許多公共場所都提供了互聯網接入點，這些接入點會導致許多賬戶使用相同的IP地址;2）部分電信服務供應商頻繁更換分配給用戶的IP地址[12]。

針對這種現象，對于圖3中的兩種圖結構，可疑度量應該給圖3（b）更高的可疑值，以避免檢測到由部分度數較高的正常資源節點所構成的子圖。

通過設置適當的邊權重，可以使可疑度量dbiased和dbalanced滿足上述需求。直觀上，隨著資源節點度數的增加，資源節點和其鄰居構成的子圖的質量增加速度應該逐漸降低。定義邊的權重w（u，v）=h（deg（v）），其中v是資源節點。滿足當x>1時，1/x

該設置如下：對于圖3（a），dbiased=1.3，dbalanced=0.78;

而對于圖3（b），dbiased和dbalanced都等于1.7。

2.3?搜索算法

本文的搜索算法受啟發于文獻[19]中提出的Rank Subgraph。給定正整數n，刪除圖G中所有度數小于n的節點，重復該過程直到得到的子圖Gn的所有節點的度數都大于等于n，稱該子圖Gn是圖G的rank為n的Rank Subgraph。如果Gn不為空，那么Gn的節點平均度數至少是圖G的所有子圖中節點平均度數最高的子圖的一半[19]。

算法1描述了本文欺詐檢測方法的基本框架。假設圖文件以（u，v，w（u，v））的形式存儲。根據輸入的圖文件f和給定的可疑度量d，算法1每次迭代先通過算法DENSEST_SUBGRAPH找出當前圖中可疑值最高的子圖（第3）行），然后將該子圖從當前圖中去除（第4）行），以避免找到重復的子圖。

算法2描述了DENSEST_SUBGRAPH的實現。定義δv（V）表示在圖G（V，E，w）中移除節點v后，圖的質量的減少量：

其中：N（v）表示節點v的鄰居節點集合。

算法2首先順序讀取一遍文件f，對每一個節點v，計算其在當前圖中移除后，圖的質量減少量δv和圖質量M（V）（第1）行）。然后選擇S和T中節點數較多的集合記為R（第5）～9）行），將R中所有δv小于或等于M（V）/|R|的節點按δv升序排列得到Δ（第10）～11）行）。逐個移除Δ中的節點，計算移除后的子圖的可疑值d（V），如果大于遇到過的最大可疑值，則記錄下當前子圖（第12）～19）行）。最后順序讀取一遍文件f，移除Δ中的節點，并更新f。重復上述步驟直到圖為空。

算法2中第4）～21）行的循環每次至少會移除一個節點，所以最多執行O（|V|）次。最壞情況下，第4）～21）行的循環一次耗時O（|E|），所以最壞情況下算法2的時間復雜度是O（|V||E|）。但是，在實驗中本文發現算法2的平均時間復雜度要遠好于O（|V||E|）。

算法2只需要保存每個節點的δv和目前找到的最佳子圖的節點，所以空間復雜度是O（|V|）。

2.4?理論界限分析

3?實驗與結果分析

3.1?模擬數據

本節在模擬數據上進行實驗，并將本文方法與CrossSpot、 fBox、EvilCohort和M-Zoom進行比較，來驗證本文方法的有效性。本文使用精準率、召回率和F1-score來評估算法性能。

本文生成了兩類模擬數據集：1）數據集1包含10000個正常賬戶和20000個正常資源。每個正常賬戶使用的資源數X滿足X～Bin（n， p）+1，其中Bin（n， p）是二項分布，n=10， p=0.1。每個正常賬戶節點按照均勻分布隨機連接到X個正常資源節點。數據集1中還包含5個欺詐組，每個欺詐組有10～30個欺詐賬戶和10～30個欺詐資源，實際數量都服從均勻分布。每個欺詐賬戶使用的資源的數量服從Bin（15，0.3）+1。每個欺詐賬戶節點隨機連接到各自所在組的欺詐資源節點。

2）數據集2在數據集1的基礎上生成。在20000個正常資源節點中隨機選擇50個，然后被選到每個資源節點隨機連接到1%～5%的正常賬戶節點。

實驗中，算法1使用了以下四種不同的參數配置：1）Balanced：使用dbalanced度量，不使用2.2節的加權策略，k取5，最終輸出可疑值大于4.5的子圖中的賬戶為欺詐賬戶;

2）Biased：使用dbiased度量，不使用2.2節的加權策略，k取5，最終輸出可疑值大于4.5的子圖中的賬戶為欺詐賬戶;

3）Balanced-w：使用dbalanced度量，使用2.2節的加權策略，k取5，最終輸出可疑值大于2的子圖中的賬戶為欺詐賬戶;

4）Biased-w：使用dbiased度量，使用2.2節的加權策略，k取5，最終輸出可疑值大于2的子圖中的賬戶為欺詐賬戶。

CrossSpot、 fBox、EvilCohort和M-Zoom的參數配置如下：1）fBox：使用2.2節的加權策略。SVD取前50個最大的特征值對應的特征向量，篩選閾值取0.99。

2）CrossSpot：隨機種子數量設置為50。

3）EvilCohort：使用2.2節的加權策略。賬戶節點的度數閾值設置為5，最終輸出社區大小大于4的賬戶社區中的所有賬戶為欺詐賬戶。

4）M-Zoom：使用2.2節的加權策略。使用算術度量，k取5，輸出所有可疑值大于2的子圖中的賬戶為欺詐賬戶。

所有算法在隨機生成的50個數據集上運行，結果取50次的平均值。實驗結果見表1。

在模擬數據集1上，M-Zoom和本文方法的性能相近，并且結果好于其他算法。對比Balanced和Balanced-w的結果，可以發現2.2節的加權策略能夠提高本文方法在模擬數據集1上的召回率。

在模擬數據集2上，EvilCohort、CrossSpot、Balanced和Biased的精準率都出現了明顯的下降，因為它們將2.2節中描述的資源節點和其相連的賬戶節點識別為了欺詐節點。 fBox在模擬數據集2上性能出現了上升，這是因為在模擬數據集2上，欺詐賬戶形成的社區的大小明顯小于正常賬戶形成的社區的大小，而在模擬數據集1中欺詐賬戶社區的大小大于正常賬戶社區。雖然文獻[13]稱fBox能找出規模較小且密度較高的欺詐賬戶社區，但實際fBox只能有效地找到規模相對正常賬戶社區較小且密度較高的欺詐賬戶社區。M-Zoom的性能基本沒有變化。Balanced-w和Biased-w的精準率與在模擬數據集1上的精準率基本一樣，說明加權策略有效地解決了2.2節中所述的問題。

圖4～5顯示了M-Zoom的密集子圖搜索算法和DENSEST_SUBGRAPH算法的算法復雜度。實驗中的圖使用文獻[20]方法生成，實驗時保持p=0.001不變，然后逐步增加圖中的節點數。

圖4顯示了算法平均運行時間和|V||E|的關系，雖然DENSEST_SUBGRAPH算法在最壞情況下的時間復雜度是O（|V||E|），但是實際的平均運行時間要好于最壞的情況，且比M-Zoom的平均運行時間更短。

圖5顯示了算法峰值內存消耗和|V|的關系，可以發現本文方法的內存消耗要小于M-Zoom。

3.2?真實數據

本節在真實數據上進行實驗。數據由合作銀行提供，包含從2016年1月1日至2017年7月1日的銀行交易日志。去除如企業交易、內網交易等特殊交易后，數據基本情況見表2。

由于銀行提供的欺詐賬戶僅包含本行賬戶，而且非本行的賬戶交易的MAC地址和IP地址缺失，實驗僅從本行賬戶中選取標記樣本作為測試數據。測試數據選取195個已確認的本行欺詐賬戶和10000個已確認的本行正常賬戶作為標記樣本，來測試不同算法對欺詐賬戶的識別性能。

對比的算法去除了效果較差的CrossSpot;EvilCohort中的度數閾值設置為3，最終輸出大小大于10的社區;M-Zoom、Biased-w和Balanced-w輸出可疑值大于1.9的子圖，而Balanced和Biased輸出可疑值大于4的子圖，其余參數設置同3.1節相同。實驗中，使用連續3d的交易記錄構成的賬戶資源網絡作為算法的輸入，最后合并所有網絡上算法運行的結果。

實驗結果見表1中的真實數據集部分。同模擬數據實驗相同，本文方法與M-Zoom算法的性能相近，且優于fBox和EvilCohort算法。M-Zoom、Balanced-w和Biased-w算法的精準率相比模擬數據上的出現了較大的下降，下降的原因是部分正常賬戶間也存在共用IP地址和MAC地址的情況，但是這部分賬戶數量較少，實際應用中可以結合有監督學習的方法對這部分賬戶作更準確的識別。

4?結語

本文根據電信詐騙中欺詐賬戶共用一組相同的IP地址或者MAC地址的現象，提出了一種基于密集子圖的無監督欺詐檢測算法。設計了符合電信詐騙特征的子圖可疑度量，提出了一種高效的可疑子圖搜索算法并對其理論保障進行了證明。通過在賬戶資源網絡中搜索可疑度較高的子圖來識別欺詐賬戶。本文方法對電信詐騙的識別性能優于fBox和EvilCohort，與M-Zoom的性能相近，但是算法復雜度低于M-Zoom，更適合于實際應用中的大規模數據集。

未來的工作中，將研究本文算法的分布式實現，從而使其更好地應用于實際應用。

參考文獻（References）

[1] JHA S， GUILLEN M， CHRISTOPHER W J. Employing transaction aggregation strategy to detect credit card fraud [J]. Expert Systems with Applications， 2012， 39（16）： 12650-12657.

[2] van VLASSELAER V， BRAVO C， CAELEN O， et al. APATE： a novel approach for automated credit card transaction fraud detection using network-based extensions[J]. Decision Support Systems， 2015， 75： 38-48.

[3] BAHNSEN A C， AOUADA D， STOJANOVIC A， et al. Detecting credit card fraud using periodic features [C]// ICMLA 2015： Proceedings of the 2015 IEEE 14th International Conference on Machine Learning and Applications. Piscataway， NJ： IEEE， 2015： 208-213.

[4] SAVGE D， WANG Q M， CHOU P L， et al. Detection of money laundering groups using supervised learning in networks [EB/OL]. [2018-05-10]. https：//arxiv.org/pdf/1608.00708.

[5] KHAC N A L， MARKOS S， KECHADI M. A data mining-based solution for detecting suspicious money laundering cases in an investment bank [C]// DBKDA 2010： Proceedings of the 2010 Second International Conference on Advances in Databases， Knowledge， and Data Applications. Piscataway， NJ： IEEE， 2010： 235-240.

[6] NEDA H， ALI H， MEHDI S. An intelligent anti-money laundering method for detecting risky users in the banking systems [J]. International Journal of Computer Applications， 2014， 97（22）： 35-39.

[7] MICHALAK K， KORCZAK J. Graph mining approach to suspicious transaction detection [C]// FedCSIS 2011： Proceedings of the 2011 Federated Conference on Computer Science and Information Systems. Piscataway， NJ： IEEE， 2011： 69-75.

[8] 喻煒， 王建東. 基于交易網絡特征向量中心度量的可疑洗錢識別系統[J]. 計算機應用， 2009， 29（9）： 2581-2585. （YU W， WANG J D. Suspicious money laundering detection system based on eigenvector centrality measure of transaction network[J]. Journal of Computer Applications， 2009， 29（9）： 2581-2585.）

[9] SOLTANI R， NGUYEN U， YANG Y， et al. A new algorithm for money laundering detection based on structural similarity [C]// UEMCON 2016： Proceedings of the 2016 IEEE 7th Annual Ubiquitous Computing， Electronics and Mobile Communication Conference. Piscataway， NJ： IEEE， 2016： 1-7.

[10] HUANG J， SUN H， HAN J， et al. SHRINK： a structural clustering algorithm for detecting hierarchical communities in networks [C]// Proceedings of the 19th ACM International Conference on Information and Knowledge Management. New York： ACM， 2010： 219-228.

[11] GIANLUCA S， PIERRE M， GREGOIRE J， et al. EVILCOHORT： detecting communities of malicious accounts on online services [C]// SEC 2015： Proceedings of the 24th USENIX Conference on Security Symposium. Berkeley： USENIX Association， 2015： 563-578.

[12] BLONDEL V D， GUILAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（10）： P10008.

[13] PRAKAS B A， SRIDHARAN A， SESHADRI M， et al. EigenSpokes： surprising patterns and scalable community chipping in large graphs [C]// PAKDD 2010： Proceedings of the 2010 Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin： Springer， 2010： 435-448.

[14] SHAH N， BEUTEL A， GALLAGHER B， et al. Spotting suspicious link behavior with fBox： an adversarial perspective [C]// ICDM： Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway， NJ： IEEE， 2014： 959-964.

[15] JIANG M， BEUTEL A， CUI P， et al. Spotting suspicious behaviors in multimodal data： a general metric and algorithms [J]. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（8）： 2187-2200.

[16] CHARIKAR M. Greedy approximation algorithms for finding dense components in a graph [C]// APPROX 2000： Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization. Berlin： Springer， 2000： 84-95.

[17] SHIN K， HOOI B， FALOUTSOS C. M-Zoom： fast dense-block detection in tensors with quality guarantees [C]// Proceedings of the 2016 Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin： Springer， 2016： 264-280.

[18] SHIN K， HOOI B， FALOUTSOS C. Fast， accurate and flexible algorithms for dense subtensor mining [J]. ACM Transactions on Knowledge Discovery from Data， 2018， 12（3）： 1-30.

[19] JIN R， XIANG Y， RUAN N， et al. 3-HOP： a high-compression indexing scheme for reachability query [C]// SIGMOD 2009： Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. New York： ACM， 2009： 813-826.

[20] BATAGELJ V， BRANDES U. Efficient generation of large random networks [J]. Physical Review E： Covering Statistical， Nonlinear， Biological， and Soft Matter Physics， 2005， 71（3）： 036113.