基于密集子图的银行电信诈骗检测方法

刘枭 王晓国

摘 要：目前银行对电信诈骗的标记数据积累少，人工标记数据的代价大，导致电信诈骗检测的有监督学习方法可使用的标记数据不足。针对这个问题，提出一种基于密集子图的无监督学习方法用于电信诈骗的检测。首先，通过在账户资源（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.