基于改進KD樹的k近鄰算法在欺詐檢測中的應用

吳金娥 段倩倩

摘 要： 面對互聯(lián)網(wǎng)交易中店家靠刷銷量欺騙消費者的問題，提出使用k最近鄰（k-Nearest Neighbor，kNN）算法進行欺詐檢測。 針對傳統(tǒng)kNN算法在搜索k近鄰時耗時過多的問題，提出基于KD樹結(jié)構的kNN算法。 為解決經(jīng)典KD樹算法由于每次回溯都要回溯到根節(jié)點而導致查詢效率低的問題，提出使用最佳桶優(yōu)先（Best-Bin-First，BBF）算法進行k個近鄰的查詢。 算法首先對待測數(shù)據(jù)集進行PCA降維，再構建KD樹結(jié)構，最后使用BBF算法進行k近鄰的查詢。 實驗證明，提出的算法可及時有效地檢測出欺騙行為。

關鍵詞： 異常檢測; k最近鄰; KD樹; BBF算法; PCA技術

文章編號： 2095-2163（2021）03-0138-05 中圖分類號：TP399 文獻標志碼：A

【Abstract】In the face of the problem that stores cheat consumers by brushing sales in Internet transactions， the k-Nearest Neighbor （kNN） algorithm is proposed to detect fraud. Aiming at the problem that traditional kNN algorithm spends too much time in searching k nearest neighbor， a kNN algorithm based on KD tree structure is proposed. In order to solve the problem of low query efficiency caused by the classical KD tree algorithm， Best-Bin-First （BBF） algorithm is used to query k nearest neighbors. First， PCA dimension reduction is performed for the measured data set， then KD tree structure is constructed， finally， BBF algorithm is used for k nearest neighbor query. Experimental results show that the proposed algorithm can detect the cheating behavior in time and effectively.

【Key words】 anomaly detection; k-Nearest Neighbor; KD tree; BBF algorithm; PCA technology

0 引 言

隨著網(wǎng)絡技術的發(fā)展，互聯(lián)網(wǎng)交易現(xiàn)已是人們生活中必不可少的一部分，面對日益激烈的競爭，部分商家通過刷銷量這種不良手段來博得消費者的信任與購買。 面對這種狀況，時下的欺詐檢測方法主要通過區(qū)分正常數(shù)據(jù)與異常數(shù)據(jù)的差異來做出辨別，而異常檢測方法也被公認為是有效的欺詐檢測方法[1]。 其中，基于kNN算法的異常檢測技術即已廣泛應用于各個領域中[2]。 關于該算法在時間效率上的提升，主要分為3種：縮減數(shù)據(jù)集[3]、降低維度[4]、優(yōu)化搜索空間[4]。 KD樹算法則是索引空間優(yōu)化中一種最經(jīng)典、也最常用的算法，該方法可有效減少k個近鄰的查詢時間。

在異常檢測中，準確率和時效性是評判算法優(yōu)劣的重要指標。但是在高維數(shù)據(jù)中，KD樹需要回溯的節(jié)點數(shù)大大增加，這將會導致查詢效率回退至傳統(tǒng)kNN算法的蠻力搜索。 因此改善高維數(shù)據(jù)的k近鄰搜索方法，有助于快速發(fā)現(xiàn)并制止商家的欺騙行為，能有效地保護消費者的權益。

為了減少交易行為中欺詐行為的發(fā)生，學者們致力于研究領域適應且高效快速的欺詐檢測算法。在信用卡欺詐檢測方面，Mases等人[5]分別將BP神經(jīng)網(wǎng)絡和貝葉斯信念網(wǎng)絡模型應用于信用卡反欺詐場景中，實驗結(jié)果表明貝葉斯信念網(wǎng)絡具有更高的檢測率。Liu 等人[6]針對金融欺詐提出了一種基于隨機森林的檢測模型，該模型利用特征選擇，并使用真實數(shù)據(jù)集進行測試，實驗驗證了該算法具有較高的準確率。 針對在線交易，在Chang等人[7]的工作中利用馬爾可夫模型提出一種信譽評估機制，該算法利用粒子群優(yōu)化算法的搜索機制快速捕捉電子商務系統(tǒng)中商家的不良行為，從而保護買家不受欺騙和其他惡意行為的侵擾。 Wang等人[8]提出了一套基于統(tǒng)計距離的監(jiān)督式欺詐檢測技術，該技術主要通過動態(tài)更新的閾值法檢測異常，實驗證明該技術可有效識別出異常。

1 相關技術

1.1 kNN算法

kNN算法[9]在分類和回歸問題中都是常用算法之一，在回歸問題中其判別異常的原理如下：首先基于某種距離度量計算每個待測數(shù)據(jù)點與其他數(shù)據(jù)點之間的距離;再分別找出待測數(shù)據(jù)點的k個最近鄰之和，以和值作為待測數(shù)據(jù)點的異常值;最后通過比較異常值的大小判別異常數(shù)據(jù)點。

1.2 PCA技術

主成分分析（Principal Component Analysis，PCA）技術又叫主分量分析技術[10]。 該技術是一種常用的簡化數(shù)據(jù)集的技術，主要通過利用降維的思想將多個指標轉(zhuǎn)換成少數(shù)幾個綜合指標，現(xiàn)已廣泛應用于模式識別、圖像壓縮以及異常檢測等多個領域。

1.3 KD樹與BBF算法

經(jīng)典的KD樹（K-Dimensional Tree）算法是由Bentley[11]在1975年提出的，KD樹是一種空間劃分數(shù)據(jù)結(jié)構，在kNN算法上的應用包括建樹和索引兩個階段。 其中，索引階段包括二分查找和回溯查找兩個部分，前者確定查詢路徑，后者沿著查詢路徑逆向遞歸查詢k個近鄰至根節(jié)點。

在高維空間中，回溯次數(shù)的明顯增多嚴重影響算法的效率。為解決這一問題，本文提出使用BBF算法[12]進行k個近鄰的搜索。 該算法通過建立優(yōu)先隊列并設置最高回溯次數(shù)與最大運行時間來提高算法執(zhí)行的效率。 在本文中，為高效快速地檢測不良商家的欺詐行為，對傳統(tǒng)的kNN算法進行改進，先使用KD樹算法構建KD樹，再使用BBF算法進行k個近鄰的搜索。

2 基于改進KD樹的k近鄰算法

2.1 模型建立

窮舉法是實現(xiàn)kNN算法最基礎的方法。該方法需要計算每個數(shù)據(jù)點與數(shù)據(jù)集中所有數(shù)據(jù)點兩兩間的距離，當數(shù)據(jù)集較大時，該方法十分耗時，針對該問題，本文提出一種基于改進KD樹的kNN算法。模型主要包括3部分，分別是：數(shù)據(jù)預處理模塊、KD樹構建模塊和BBF算法搜索模塊。 各部分功能簡述如下。

（1）數(shù)據(jù)預處理模塊：在該模塊引入PCA技術對待測數(shù)據(jù)集做降維處理。

（2）KD樹構建模塊：該模塊使用類似于二叉樹的結(jié)構存放數(shù)據(jù)，為k近鄰的搜索做準備。 該模塊首先計算數(shù)據(jù)集X中v個維度的方差，再確定split域與根節(jié)點，最后通過與根節(jié)點split域值比較大小劃分左右子樹，依次遞歸至葉結(jié)點。

（3）BBF算法搜索模塊：BBF算法的應用可有效減少回溯次數(shù)，加快k個最近鄰的搜索。 ?由于KD樹搜索算法在高維數(shù)據(jù)集中的搜索效率因回溯次數(shù)的明顯增加而顯著下降，因此本文提出使用BBF算法替代KD樹搜索算法，加快k個近鄰的查找。該算法先通過節(jié)點自身攜帶的信息建立優(yōu)先隊列，每次回溯均從優(yōu)先隊列中取優(yōu)先級最高的點t-node，并比較該點與目標點的距離，對k近鄰進行更新;然后比較在split域p維上該點與目標點值的大小，分別確定下一搜索節(jié)點與加入優(yōu)先隊列的節(jié)點，并比較下一搜索節(jié)點與目標點的距離，更新k近鄰;最終遞歸搜索至優(yōu)先隊列為空或超出最大回溯次數(shù)，則結(jié)束搜索。

根據(jù)以上描述，算法模型建立如圖1所示。

2.2 KD樹的建立

傳統(tǒng)kNN算法依靠窮舉法搜索k近鄰，但這種方法在數(shù)據(jù)集較大時耗費過多時間，查詢效率低下。而使用KD樹結(jié)構可以在索引階段避免大部分無關數(shù)據(jù)的查詢，有效減少索引量，提高搜索效率。KD樹的構建過程是一個從根節(jié)點開始，自上而下逐級展開的遞歸過程。 KD樹構建算法的詳細描述如下。

2.3 基于BBF算法的k近鄰搜索

KD樹算法在搜索近鄰時分為二分查找和回溯查找兩個部分進行，可見回溯次數(shù)直接決定了算法的運行效率。而基于KD樹搜索的kNN算法，每次搜索都需要回溯到根節(jié)點，出現(xiàn)了很多無關回溯，導致不必要的時間消耗。為提高k近鄰的搜索效率，提出使用BBF算法，該算法提供一個優(yōu)先隊列，存儲二分查找錯過的節(jié)點，按照各節(jié)點所在的超平面到A的距離由小到大進行排序。對于指定查找點A，其基于BBF算法的k近鄰搜索見算法2。

3 算法在欺詐數(shù)據(jù)集中的實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)集

隨著電子商務的興起，部分商家為吸引消費者使用不良手段提升商品銷量。 本文針對該問題，選取來自于阿里巴巴天池大數(shù)據(jù)競賽編號為1629的賣家交易數(shù)據(jù)，并將該數(shù)據(jù)以天為單位劃分為325個集合，每個集合代表一個數(shù)據(jù)點。數(shù)據(jù)集的詳細描述見表1。

由表1描述可知，數(shù)據(jù)集共分為3種類型的數(shù)據(jù)，其中集中式刷銷量數(shù)據(jù)和均衡式刷銷量數(shù)據(jù)描述了2種不同的刷銷量模式。 在檢測時，使用正常交易數(shù)據(jù)混合2種刷銷量數(shù)據(jù)構成待測數(shù)據(jù)集。

3.2 實驗結(jié)果評價指標

混淆矩陣是異常檢測算法實驗結(jié)果最直觀的體現(xiàn)，是其他評價算法優(yōu)劣指標的根本。 研究中會用到的混淆矩陣詳見表2。 為更好地評價算法性能，本文選擇F1值、算法運行時間T、ROC曲線以及PR曲線作為實驗結(jié)果的評價指標。

在異常檢測中，F(xiàn)1很好地綜合了精度（Precision，Pre）和召回率（Recall，Re）指標，是Pre和Re的加權調(diào)和平均。 這里，Pre指的是在預測為異常的集群中真實異常的占比;Re表示預測為異常的集群占總真實異常的比例。如上各數(shù)學指標的計算公式可寫為：

研究可知，F(xiàn)1值越大，則算法性能越好。

ROC曲線被廣泛應用于評估算法的可信度，描述了假陽率（False Positive Rate，F(xiàn)PR）和真陽率（True Positive Rate，TPR）之間的變化關系，其中FPR=FPFP+TN，而TPR等同于Re指標，該曲線越接近坐標系左上角，算法性能越好。 PR曲線分別以Re和Pre為橫縱坐標，曲線越靠近圖形右上角則算法性能越好。

3.3 實驗分析

3.3.1 實驗1

實驗1用于驗證改進算法的時效性。傳統(tǒng)kNN算法時間復雜度為O（n2），而KD樹結(jié)構可將時間復雜度降低為O（nlogn），利用BBF算法進行k近鄰的查詢，能進一步縮短搜索時間。在該組實驗中，驗證算法檢測欺詐行為的時效性。待測數(shù)據(jù)集由正常交易數(shù)據(jù)和20%的刷銷量數(shù)據(jù)構成。其中，BBF-kNN表示使用KD樹結(jié)構存儲數(shù)據(jù)，并使用BBF算法進行k近鄰搜索的算法;PCA-BBF-kNN表示使用PCA降維的BBF-kNN算法。實驗結(jié)果記錄見表3。

由表3可知，集中式刷銷量行為的最優(yōu)F1值可達到98.46%，而均衡式刷銷量模式的最優(yōu)F1值為79.38%。可見均衡式刷銷量模式更難檢測，這是由于該模式下數(shù)據(jù)的分布比較相似增加了檢測的難度。

在集中式刷銷量模式下，kNN算法的F1值最高。BBF-kNN算法在進行搜索時限制了最大回溯次數(shù)，一定程度上減少了數(shù)據(jù)量的對比;而PCA-BBF-kNN算法對BBF-kNN算法在數(shù)據(jù)預處理階段進行了降維處理，信息量有所丟失，因此F1值略低于BBF-kNN算法。 盡管如此，kNN算法下最優(yōu)F1值僅比BBF-kNN算法高0.31%，比PCA-BBF-kNN算法高0.62%;而其消耗的時間卻是BBF-kNN算法的2.6倍，是PCA-BBF-kNN算法的5.4倍。在均衡式刷銷量模式下，BBF-kNN算法的F1值最高，而PCA-BBF-kNN算法該值較低，這是由于在降維時丟失的信息較多，導致檢測效果的下降。而算法的檢測時間仍然是PCA-BBF-kNN算法最優(yōu)。

綜合上述分析可見，使用KD樹結(jié)構合并BBF算法搜索k近鄰的方法可有效檢測出商家的欺詐行為。

3.3.2 實驗2

實驗2為改進算法的可靠性驗證。本組實驗通過ROC曲線和PR曲線進一步驗證算法的可靠性。 仿真后得到，ROC曲線如圖2所示，PR曲線如圖3所示。

對于ROC曲線而言，越接近點（0，1），算法性能越好。由圖2可見，實驗中的3種算法都非常接近點（0，1），因此本文提出的算法具有很好的可靠性。

算法的PR曲線越接近點（1，1），則性能越好，由圖3可見，3種算法的PR曲線表現(xiàn)良好，均接近點（1，1）。 其中，kNN算法最接近點（1，1），盡管如此，BBF-kNN算法和PCA-BBF-kNN算法與kNN算法相差甚微。

4 結(jié)束語

本文針對互聯(lián)網(wǎng)交易中存在的欺詐行為，提出了一種改進KD樹的k近鄰算法應用于其中. 對待測數(shù)據(jù)集進行KD樹的構建，改善數(shù)據(jù)結(jié)構;再使用BBF算法搜索每個數(shù)據(jù)點的k近鄰，減少回溯次數(shù)，縮短搜索時間;最后計算k個近鄰之和，以此作為數(shù)據(jù)點的異常度，按照異常度的大小輸出異常數(shù)據(jù)，從而判別商家的欺詐行為。 實驗驗證了本文提出的算法可有效地減少執(zhí)行時間，且檢測準確率保持在較高的水平。

參考文獻

[1] 高永昌. 醫(yī)療保險大數(shù)據(jù)中的欺詐檢測關鍵問題研究[D]. 濟南：山東大學，2018.

[2] MEHROTRA K G， MOHAN C K， HUANG H M. Anomaly detection principles and algorithms[M]. Switzerland： Springer International Publishing， 2017.

[3] VALERO-MAS J J， CASTELLANOS F J. Data reduction in the string space for efficient kNN classification through space partitioning[J]. Applied Sciences，2020， 10（10）：3356.

[4] 江澤濤，周譚盛子，韓立堯. 基于感知哈希矩陣的最近鄰入侵檢測算法[J]. 電子學報，2019，47（7）：1538-1546.

[5] MASES S， TUYLS K， VANSCHOENWINKEL B， et al. Credit card fraud bayesian and neural networks[C]// Proceedings of the 1st International Naiso Congress on Neuro Fuzzy Technologies. Havana， Cuba：Springer-Verlag， 2002： 16-19.

[6] LIU Chengwei， CHAN Yixiang， KAZMIL S H A， et al. Financial fraud detection model： Based on Random Forest[J]. International Journal of Economics & Finance， 2015， 7（7）： 178-188.

[7] CHANG L， OUZROUT Y， NONGAILLARD A， et al. The reputation evaluation based on optimized Hidden Markov Model in e-commerce[J]. Mathematical Problems in Engineering，2013，2013： 391720.

[8] WANG Ruoyu， HU Xiaobo， SUN D， et al. Statistical detection of collective data fraud[C]//2020 IEEE International Conference on Multimedia and Expo（ICME）. London， UK：IEEE， 2020：1-6.

[9] COVER T， HART P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory， 1967， 13（1）： 21-27.

[10] 杜子芳. 多元統(tǒng)計分析[M]. 北京：清華大學出版社，2016.

[11] BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM， 1975， 18（9）： 509-517.

[12] BEIS J S， LOWE D G. Shape indexing using approximate nearest-neighbour search in high dimensional spaces[C]// Proceeding of the 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR）. SAN JUAN， PR， USA：IEEE， 1997： 1000-1006.