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

吳金娥 段倩倩

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

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

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

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

1 相關技術

1.1 kNN算法

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

1.2 PCA技術

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

1.3 KD樹與BBF算法

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

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

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

2.1 模型建立

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

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

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

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

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

2.2 KD樹的建立

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

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

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

3 算法在欺詐數據集中的實驗結果與分析

3.1 實驗數據集

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

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

3.2 實驗結果評價指標

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

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

研究可知，F1值越大，則算法性能越好。

ROC曲線被廣泛應用于評估算法的可信度，描述了假陽率（False Positive Rate，FPR）和真陽率（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樹結構可將時間復雜度降低為O（nlogn），利用BBF算法進行k近鄰的查詢，能進一步縮短搜索時間。在該組實驗中，驗證算法檢測欺詐行為的時效性。待測數據集由正常交易數據和20%的刷銷量數據構成。其中，BBF-kNN表示使用KD樹結構存儲數據，并使用BBF算法進行k近鄰搜索的算法;PCA-BBF-kNN表示使用PCA降維的BBF-kNN算法。實驗結果記錄見表3。

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

在集中式刷銷量模式下，kNN算法的F1值最高。BBF-kNN算法在進行搜索時限制了最大回溯次數，一定程度上減少了數據量的對比;而PCA-BBF-kNN算法對BBF-kNN算法在數據預處理階段進行了降維處理，信息量有所丟失，因此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樹結構合并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曲線表現良好，均接近點（1，1）。 其中，kNN算法最接近點（1，1），盡管如此，BBF-kNN算法和PCA-BBF-kNN算法與kNN算法相差甚微。

4 結束語

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

參考文獻

[1] 高永昌. 醫(yī)療保險大數據中的欺詐檢測關鍵問題研究[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.