基于改进KD树的k近邻算法在欺诈检测中的应用

吴金娥 段倩倩

摘 要： 面对互联网交易中店家靠刷销量欺骗消费者的问题，提出使用k最近邻（k-Nearest Neighbor，kNN）算法进行欺诈检测。 针对传统kNN算法在搜索k近邻时耗时过多的问题，提出基于KD树结构的kNN算法。 为解决经典KD树算法由于每次回溯都要回溯到根节点而导致查询效率低的问题，提出使用最佳桶优先（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 引 言

随着网络技术的发展，互联网交易现已是人们生活中必不可少的一部分，面对日益激烈的竞争，部分商家通过刷销量这种不良手段来博得消费者的信任与购买。 面对这种状况，时下的欺诈检测方法主要通过区分正常数据与异常数据的差异来做出辨别，而异常检测方法也被公认为是有效的欺诈检测方法[1]。 其中，基于kNN算法的异常检测技术即已广泛应用于各个领域中[2]。 关于该算法在时间效率上的提升，主要分为3种：缩减数据集[3]、降低维度[4]、优化搜索空间[4]。 KD树算法则是索引空间优化中一种最经典、也最常用的算法，该方法可有效减少k个近邻的查询时间。

在异常检测中，准确率和时效性是评判算法优劣的重要指标。但是在高维数据中，KD树需要回溯的节点数大大增加，这将会导致查询效率回退至传统kNN算法的蛮力搜索。……