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

摘要

面对互联网交易中店家靠刷销量欺骗消费者的问题,提出使用k最近邻(k-Nearest Neighbor,k NN)算法进行欺诈检测。针对传统k NN算法在搜索k近邻时耗时过多的问题,提出基于KD树结构的k NN算法。为解决经典KD树算法由于每次回溯都要回溯到根节点而导致查询效率低的问题,提出使用最佳桶优先(Best-Bin-First,BBF)算法进行k个近邻的查询。算法首先对待测数据集进行PCA降维,再构建KD树结构,最后使用BBF算法进行k近邻的查询。实验证明,提出的算法可及时有效地检测出欺骗行为。