论文部分内容阅读
摘 要： 面对互联网交易中店家靠刷销量欺骗消费者的问题，提出使用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算法的蛮力搜索。 因此改善高维数据的k近邻搜索方法，有助于快速发现并制止商家的欺骗行为，能有效地保护消费者的权益。
为了减少交易行为中欺诈行为的发生，学者们致力于研究领域适应且高效快速的欺诈检测算法。在信用卡欺诈检测方面，Mases等人[5]分别将BP神经网络和贝叶斯信念网络模型应用于信用卡反欺诈场景中，实验结果表明贝叶斯信念网络具有更高的检测率。Liu 等人[6]针对金融欺诈提出了一种基于随机森林的检测模型，该模型利用特征选择，并使用真实数据集进行测试，实验验证了该算法具有较高的准确率。 针对在线交易，在Chang等人[7]的工作中利用马尔可夫模型提出一种信誉评估机制，该算法利用粒子群优化算法的搜索机制快速捕捉电子商务系统中商家的不良行為，从而保护买家不受欺骗和其他恶意行为的侵扰。 Wang等人[8]提出了一套基于统计距离的监督式欺诈检测技术，该技术主要通过动态更新的阈值法检测异常，实验证明该技术可有效识别出异常。
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个近邻至根节点。 在高维空间中，回溯次数的明显增多严重影响算法的效率。为解决这一问题，本文提出使用BBF算法[12]进行k个近邻的搜索。 该算法通过建立优先队列并设置最高回溯次数与最大运行时间来提高算法执行的效率。 在本文中，为高效快速地检测不良商家的欺诈行为，对传统的kNN算法进行改进，先使用KD树算法构建KD树，再使用BBF算法进行k个近邻的搜索。
2 基于改进KD树的k近邻算法
2.1 模型建立
穷举法是实现kNN算法最基础的方法。该方法需要计算每个数据点与数据集中所有数据点两两间的距离，当数据集较大时，该方法十分耗时，针对该问题，本文提出一种基于改进KD树的kNN算法。模型主要包括3部分，分别是：数据预处理模块、KD树构建模块和BBF算法搜索模块。 各部分功能简述如下。
（1）数据预处理模块：在该模块引入PCA技术对待测数据集做降维处理。
（2）KD树构建模块：该模块使用类似于二叉树的结构存放数据，为k近邻的搜索做准备。 该模块首先计算数据集X中v个维度的方差，再确定split域与根节点，最后通过与根节点split域值比较大小划分左右子树，依次递归至叶结点。
（3）BBF算法搜索模块：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算法的蛮力搜索。 因此改善高维数据的k近邻搜索方法，有助于快速发现并制止商家的欺骗行为，能有效地保护消费者的权益。
为了减少交易行为中欺诈行为的发生，学者们致力于研究领域适应且高效快速的欺诈检测算法。在信用卡欺诈检测方面，Mases等人[5]分别将BP神经网络和贝叶斯信念网络模型应用于信用卡反欺诈场景中，实验结果表明贝叶斯信念网络具有更高的检测率。Liu 等人[6]针对金融欺诈提出了一种基于随机森林的检测模型，该模型利用特征选择，并使用真实数据集进行测试，实验验证了该算法具有较高的准确率。 针对在线交易，在Chang等人[7]的工作中利用马尔可夫模型提出一种信誉评估机制，该算法利用粒子群优化算法的搜索机制快速捕捉电子商务系统中商家的不良行為，从而保护买家不受欺骗和其他恶意行为的侵扰。 Wang等人[8]提出了一套基于统计距离的监督式欺诈检测技术，该技术主要通过动态更新的阈值法检测异常，实验证明该技术可有效识别出异常。
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个近邻至根节点。 在高维空间中，回溯次数的明显增多严重影响算法的效率。为解决这一问题，本文提出使用BBF算法[12]进行k个近邻的搜索。 该算法通过建立优先队列并设置最高回溯次数与最大运行时间来提高算法执行的效率。 在本文中，为高效快速地检测不良商家的欺诈行为，对传统的kNN算法进行改进，先使用KD树算法构建KD树，再使用BBF算法进行k个近邻的搜索。
2 基于改进KD树的k近邻算法
2.1 模型建立
穷举法是实现kNN算法最基础的方法。该方法需要计算每个数据点与数据集中所有数据点两两间的距离，当数据集较大时，该方法十分耗时，针对该问题，本文提出一种基于改进KD树的kNN算法。模型主要包括3部分，分别是：数据预处理模块、KD树构建模块和BBF算法搜索模块。 各部分功能简述如下。
（1）数据预处理模块：在该模块引入PCA技术对待测数据集做降维处理。
（2）KD树构建模块：该模块使用类似于二叉树的结构存放数据，为k近邻的搜索做准备。 该模块首先计算数据集X中v个维度的方差，再确定split域与根节点，最后通过与根节点split域值比较大小划分左右子树，依次递归至叶结点。
（3）BBF算法搜索模块：BBF算法的应用可有效减少回溯次数，加快k个最近邻的搜索。