上海交通大学学报

上海交通大学学报（自然版）, 2021, 55(5): 598-606 doi: 10.16183/j.cnki.jsjtu.2020.011

基于反向k近邻过滤异常的群数据异常检测

吴金娥1, 王若愚2, 段倩倩,1, 李国强1,2, 琚长江2

1.上海工程技术大学 电子电气工程学院, 上海 201600

2.上海交通大学 软件学院, 上海 200240

Collective Data Anomaly Detection Based on Reverse k-Nearest Neighbor Filtering

WU Jin’e1, WANG Ruoyu2, DUAN Qianqian,1, LI Guoqiang1,2, JÜ Changjiang2

1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201600, China

2. School of Software, Shanghai Jiao Tong University, Shanghai 200240, China

通讯作者: 段倩倩,女,讲师,电话(Tel. ):15000688602;E-mail:dqq1019@163.com.

责任编辑: 石易文

收稿日期: 2020-01-8  

基金资助: 国家自然科学基金重点项目(61732013)
国家重点研发计划(SQ2019YFB170208)

Received: 2020-01-8  

作者简介 About authors

吴金娥(1995-),女,安徽省芜湖市人,硕士生,现主要从事数据异常检测研究. 。

摘要

针对无数据标签的群数据异常检测问题,提出在无监督模式下利用k最近邻(kNN)算法检测群数据异常.为减少由于异常值与正常值之间相互干扰而产生的漏报和误报,提出用反向k近邻(RkNN)算法对异常群数据进行反向过滤. 反向k近邻算法首先将统计距离作为不同群数据间的相似性度量,再用kNN算法求得每个集群的异常得分,并获得初始异常,最后使用RkNN算法对初始异常进行过滤.实验结果证明,所提算法能有效减少漏报和误报,且具有较高的异常检测率和良好的稳定性.

关键词： 异常检测; 无监督; k最近邻; 反向k近邻; 统计距离

Abstract

Aimed at the problem of group data anomaly detection with no data labels, a k-nearest neighbor (kNN) algorithm is proposed to detect group data anomalies in the unsupervised mode. In order to reduce false negatives and false positives caused by the mutual interference between abnormal and normal values, a reverse k-nearest neighbor (RkNN) method is proposed to filter the abnormal group data in reverse. First, the RkNN algorithm uses statistical distance as the similarity measure between different groups of data. Then, the anomaly scores of each group and the initial abnormality are obtained by using the kNN algorithm. Finally, the initial abnormality is filtered by using the RkNN method. The experiment results show that the algorithm proposed can not only effectively reduce the false negatives and false positives, but also has a high anomaly detection rate and good stability.

Keywords： abnormal detection; unsupervised; k-nearest neighbor (kNN); reverse k-nearest neighbor (RkNN); statistical distance

PDF (1494KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

吴金娥, 王若愚, 段倩倩, 李国强, 琚长江. 基于反向k近邻过滤异常的群数据异常检测[J]. 上海交通大学学报（自然版）, 2021, 55(5): 598-606 doi:10.16183/j.cnki.jsjtu.2020.011

WU Jin’e, WANG Ruoyu, DUAN Qianqian, LI Guoqiang, JÜ Changjiang. Collective Data Anomaly Detection Based on Reverse k-Nearest Neighbor Filtering[J]. Journal of shanghai Jiaotong University, 2021, 55(5): 598-606 doi:10.16183/j.cnki.jsjtu.2020.011

异常检测技术通过对事物产生的数据进行分析和挖掘,能有效及时地发现事物中的异常数据,有利于预防和制止损失的产生.随着该技术的发展与成熟,已被广泛应用于网络安全、金融、医疗健康、国防军事等多个领域[1].根据待检测数据有无标签可将异常检测算法分为监督[2]、半监督[3]和无监督[4];依据异常类型的不同又可分为点异常、上下文异常和群异常[5].现有的技术大多是在有数据标签的情况下研究单个点的异常,而现实生活中的部分异常只能从无数据标签的群数据中挖掘出来.

监督或半监督的异常检测技术依赖于数据集所提供的带数据标签的正常和异常数据,该方法利用已知正常和异常数据训练模型[6],通过观察待测数据的数据模型与带标签数据训练出的模型之间的符合程度判别是否异常.而当待检测的数据集无已知正常或异常数据,如网络新型攻击发生时,使用监督式方法并不能检测出该异常.而在异常检测技术领域中,高检测率是该领域追求的最终目标,漏报和误报作为影响算法效率的根本原因,也是目前异常检测算法中普遍存在的问题.减少漏报和误报可以提升算法性能,对现实领域的应用具有重大意义.

异常或离群值指的是与正常数据有显著差异的数据点.早在19世纪,关于离群值问题就被统计学界提出并研究[7].直至2000年,Knorr等[8]提出基于距离的异常检测方法,掀起了异常检测技术的发展高潮.在关于群数据的异常检测中,Lee等[9]提出的基于分段检测的轨迹离群点检测 (TRAOD)框架可有效检测出异常的子轨迹.Luan等[10]在传统TRAOD算法的基础上,结合文献[9]中提出的分割检测框架提出一种基于局部密度的轨迹离群算法.Djenouri等[11]提出在给定时间间隔中同时考虑时间和空间因素建立的流量分布概率数据库,结合基于距离的k近邻(kNN)算法检测交通流数据的异常.毛江云等[12]提出通过Markov决策过程实现异常车辆的轨迹检测,该算法分为预处理、离线训练模型和在线检测异常3个阶段.Wang等[13]提出一套基于统计距离的群数据异常检测技术,该技术以已知的正常群数据和异常群数据作为参照系,使用动态更新阈值法对待检测群数据进行异常判别.通过淘宝交易刷信誉的真实数据集进行大量实验,实验结果证明该监督式方法可有效识别出异常.

本文的主要创新点在于:① 为解决无数据标签的群数据异常检测问题,提出一种基于k近邻算法的无监督式异常检测算法;② 为减少算法的漏报、误报率,提出使用反向k近邻(RkNN)算法过滤异常值,优化算法性能;③ 相比于文献[13],本文解决了在无监督模式下对异常群数据的检测问题,并优化了kNN算法的检测质量.

1 相关技术

1.1 相似性度量

相似性度量指的是两个事物间相似程度的一种度量方式.使用统计距离作为不同集群数据间的相似性度量.统计距离度量的是两个群数据在数据分布上的差异,常见的统计距离有相对熵,又被称为Kullback-Leibler散度(KLD)或信息散度[14],该距离度量方式不具有对称性,而Jensen-Shannon散度(JSD)[15]作为相对熵的优化计算方式具有对称性.在实验中选用具有对称性的JSD作为衡量两个群数据间差异的相似性度量.但当出现两个数据分布完全不重叠的极端情况时,JSD不再适用.为此,考虑将集群数据以特定形式引入欧式空间中进行异常检测.对本文中使用到的距离度量方式进行如下定义.

g、l分别表示待检测数据集C中的任意两个群数据,g、l间的距离可记为d(g,l).当相似性度量为JSD距离度量方式时,g、l间的距离表达式如下:

d(g,l)=JSD(G‖L)

式中:G、L分别为g和l的概率分布.KLD的距离表达方式如下:

KLD(G‖L)= ∑L(z)≠0G(z) lb G(z)L(z)

式中:G(z)、L(z)为离散变量.G、L间JSD值的计算方式为

$\begin{aligned} \operatorname{JSD}(G \| L)=& \frac{1}{2}\left[\operatorname{KLD}\left(G \| \frac{G+L}{2}\right)+\right.\\ &\left.\operatorname{KLD}\left(L \| \frac{G+L}{2}\right)\right] \end{aligned}$

当使用欧式距离作为相似性度量时,g、l间的距离表达式则为

d(g,l)=E(X,Y)

式中:X、Y分别为g、l各自在24h中每小时销售统计量构成的24维向量;E(X,Y)为X、Y间的欧式距离.具体定义如下:

E(X,Y)=∑i=124(Xi-Yi)2

1.2 k近邻与反向k近邻

k近邻算法[16]是最简单的机器学习算法之一,最开始被用于求解分类问题[17].随着异常检测技术的发展,该算法被应用于异常检测中,其判别异常的步骤如下:对每个待测样本求得其k个最近邻的集合,再求得每个样本到各自k个最近邻的平均距离,将平均距离表示为该样本的异常得分,异常得分越高表示该样本越异常[18].本文使用该算法求得每个群数据的异常得分后,为了更好地反映不同集群间的差异,使用每个集群到各自k个最近邻的距离总和作为异常得分.g的k个最近邻集合可记作Nk(g),则有:

Nk(g)={l| d(g,l)≤dk(g),
l∈{C-{g}}}

式中:dk(g)为g的k个最近邻.综合以上定义,待测集群g的异常得分定义如下:

α(g)=∑l∈Nk(g)d(g,l)

由于在计算k个最近邻时,不可避免地会受到异常值之间的相互干扰,提出使用反向k近邻法[19]过滤互相干扰的情况.关于反向k近邻的定义如下:

Qk(g)={l|g∈Nk(l),l∈C}

式中:Qk(g)为g的k个反向最近邻的集合;Nk(l)为l的k个最近邻的集合.

2 反向k近邻过滤异常的群数据异常检测

2.1 模型建立

无监督方式下的数据异常检测对数据集的要求较低.当待检测的异常为新发生的异常时,由于缺少先验知识,有监督的算法并不能实现检测,而无监督方式可直接对数据集进行建模,从而检测出异常.针对k近邻算法在检测异常时存在的误报和漏报问题,提出使用反向k近邻法对该算法进行优化,以提升算法的检测效果.模型包括3个部分:① 数据预处理模块;② 初步异常检测模块;③ 算法优化模块.各模块部分的功能简述如下:

(1) 数据预处理模块.将待测数据集划分成多个集群数据,以方便算法的实施.

(2) 初步异常检测模块.对输入的多个集群数据使用k近邻算法实现无监督式的群数据异常检测,获得初步异常群数据.

该模块首先计算两两集群之间的距离,建立起距离权图;再计算每个集群的k个最近邻的距离之和作为该集群的异常得分;最后将异常得分最高的前m个集群Sm作为初始异常输出到算法优化模块.

(3) 算法优化模块.对输入的异常群数据,使用反向k近邻法进行过滤,获得优化后的异常群数据.

由于k近邻算法在计算集群的k个最近邻时存在异常集群和正常集群之间相互干扰的问题,导致检测结果存在漏报和误报.为解决这个问题,该模块提出使用反向k近邻算法对初始异常集群进行反向过滤.首先查找每个异常集群的反向k近邻;再对其中的正常集群更新k近邻,使异常集群不包含在其k近邻中;最后重新计算异常得分,更新异常集群.重复该操作直至最终输出的异常集群的反向k近邻中不再包含正常集群.

根据以上3个模块的功能简述,所建立的算法模型如图1所示.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1   模型建立流程图

Fig.1   Flow chart of model establishment


2.2 基于k近邻的群数据异常检测

2.2.1 JSD相似性度量下的群数据异常检测 在处理无数据标签的数据集时,无法从数据集本身的建模判别异常集群,而建立全局的距离权图有助于解决异常集群的识别问题.利用所建立的距离权图,使用k近邻算法求得每个集群的异常得分,根据异常得分识别异常数据.集群数据之间的差异可以很好地体现在数据分布的差异性上,而统计距离能较好地捕捉不同群数据间的分布差异,因此使用JSD距离度量方式计算两两集群间的距离.为更好地反映集群间的差异性,将待测集群与其k个最近邻集群间的距离之和作为该集群的异常得分,最后输出异常得分排序列表的前m个集群作为异常值,即输出Sm.根据以上分析,基于k近邻算法的统计分布检测(SDD-kNN)算法的伪代码如算法1所示.

算法1 SDD-kNN

输入 数据集C={c1,c2,…,cn},近邻的数量为k

输出 Sm

(1)M←n×n空矩阵

(2) for i←1 to n do

(3) Gi←ci的概率分布

(4) end for

(5) for i←1 to n do

(6) for j←1 to n do

(7) Mij←JSD(Gi‖Gj)

(8) end for

(9) end for

(10) for i←1 to n do

(11) α (ci)←M的第 i 行前 k+1个最小元素和

(12) end for

(13) S←对所有集群按 α(ci) 值进行降序排列

(14) Sm←S 中前m个集群

(15) return Sm

2.2.2 欧式距离的应用 当两个集群的概率分布G和L完全没有重叠的极端情况发生时,JSD不再适用.通过比较式(3)和(5)可以发现,欧式距离对数据的变化更为敏感,因此可将待检测数据集映射到欧式空间中,使用欧式距离作为两两集群间的相似性度量.由于实验数据是淘宝交易数据,所以将待检测数据集按天划分为不同的集群数据,将每天24h的交易量作为欧式距离的24维向量,由此来计算不同集群间的差异.统计日交易数据分布直方图如图2所示.其中:H为不同时间点;V为销售量.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2   日交易数据分布直方图(第156天)

Fig.2   Distribution histogram of daily trading data (156th day )


2.3 基于反向k近邻的过滤法

漏报和误报是异常检测算法普遍存在的问题,产生漏报和误报的情况有两种,一种是算法本身存在局限性,不能准确识别出部分异常集群;另一个原因是在计算k近邻时产生的误差.在SDD-kNN算法中,造成误差的原因是异常值与正常值之间的相互干扰,导致异常集群被误判为正常集群.

SDD-kNN算法之所以能有效检测出异常,这依赖于异常集群与正常集群之间的距离较大,而正常集群之间的距离则相对较小,所以异常集群相对于正常集群而言有更高的异常得分.假设集群g的Nk(g)中包含另一个甚至几个其他异常集群,此时α(g)将会变低,当该值小于噪声点或处于异常边缘的正常集群的异常得分时,g则被误判为正常,而噪声点或处于异常边缘的正常集群被宣布为异常,由此导致算法的误报和漏报率上升.

为解决由上述原因产生的误报和漏报问题,对算法初步输出的异常值使用反向k近邻法进行过滤,从而提升算法的性能.反向分析上述问题产生的原因,如果算法判别为正常集群的k个最近邻中包含判别为异常的集群,那么该正常集群很有可能是受其他异常集群的干扰而被误判的.所以在该方法中应首先找到初步输出的异常集群的反向k近邻,对反向k近邻中被初步识别为正常的集群重新计算k近邻,且该k近邻不再包含已知的异常集群.然后再重新计算异常得分,更新Sm,并重复上述步骤.直至Sm中集群的反向k近邻中不再包含正常集群.根据上述分析,反向k近邻过滤异常算法的伪代码如算法2所示.

算法2 反向k近邻过滤异常法

输入 数据集C={c1,c2,…,cn},初步输出的异常集合θ,近邻的数量为k

输出 Sm

(1) for ci∈θ do

(2) for cj∈Qk(ci) do

(3) if cj∉θ

(4) Nk(cj)={cb|d(cj,cb)≤dk(cj), cb∈{C-{ci,cj}}}

(5) α(cj)= ∑cb∈Nk(cj)d(cj,cb)

(6) end for

(7) end for

(8) S←对所有集群按 α(ci) 值进行降序排列

(9) Sm←S 中前m个集群

(10) return Sm

3 实验及其结果分析

3.1 数据集介绍

选取文献[13]在实验中使用的数据集,该数据集的正常交易数据来自于阿里巴巴天池大数据竞赛.提取编号为 1629 的卖家交易史,记录时间为2015-11-11~2016-10-31,以天为单位将数据集划分成325个集群.关于该数据集的详细描述如图3所示.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3   数据集介绍

Fig.3   Data set introduction


由图3可见,口碑数据集中描述了集中式刷信誉和均衡式刷信誉两种不同的刷信誉模式,这两种模式下的数据是模拟不同刷信誉行为生成的.由于原始数据集只记录了交易成交时间点的小时记录数,所以引入了增强数据集,该数据集添加了时分秒的时间戳.在检测算法性能时,待测数据集由异常群数据中的异常集群替换正常数据中的正常集群,从而组成待测数据集.

3.2 实验结果评价指标介绍

在异常检测问题中,正确率作为直观的评价指标之一,通常被用于度量算法的性能.然而,当异常数据较少时,尽管算法未检测出任何异常,该算法表现出的正确率仍然会很高.因此,除了正确率A之外,还引入假阳率η、精度P、召回率R、综合评价指标F以及运行时间t作为衡量算法有效性的指标.

(1) 正确率:指预测正确的集群个数在待测数据集中的占比, 该值越大,则代表算法性能越好,

A= TP+TNTP+TN+FP+FN

式中:FP为将正常集群误判为异常的数量;TN为正常集群被正确判断的数量;TP为异常集群被正确判别为异常的数量;FN为异常集群被错判为正常的数量.

(2) 假阳率:指正常集群中被预测为异常的比例,该值越小,则代表算法性能越好,

η= FPFP+TN

(3) 精度:指在预测为异常的集群中真实异常的占比,即

P= TPTP+FP

(4) 召回率:指预测为异常的集群占总真实异常的比例,即

R= TPTP+FN

(5) 综合评价指标:该指标是P和R的加权调和平均,其计算公式如下:

F=(β2+1)PRβ2(P+R)

式中:β为参数,此处取β=1,此时将综合评价指标记作F1值,即上式变为

F1=2PRP+R

随着F1值的升高,算法性能也越来越好.

(6) 运行时间:该项指标记录的是算法完成检测所需的时间,该指标越小,则代表算法性能越好.

3.3 实验分析

实验1 k值的选择.由于kNN算法的检测结果在很大程度上受到k值的影响,所以合理地选择k值是保证实验检测效率的条件之一.实验数据集由正常交易数据混合不同数目的集中式刷信誉数据构成.采用单变量控制法,检测在不同异常概率下k值对最终决策的影响,检测结果如图4所示,其中U为异常概率.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4   k值对检测结果的影响

Fig.4   Influence of k values on test results


由图4可见,k值对算法的检测结果有较大的影响.随着k值的增大,F1值呈上升趋势并逐渐趋于平稳.当k值较小时,噪声点不易与异常值区分,导致较低的检测率.因此,当k逐渐增大时,可以获得与待测集群数据更多的相关信息,使噪声点与异常值的异常得分差距增大,算法性能得到提升.

比较图4(a)和(b)可见,在欧式距离相似性度量方式下算法性能比JSD距离度量方式下提升得更快.这是由于欧式距离对微小的变化更敏感,在k值较小的情况下也能有效区别噪声和异常.

实验2 反向过滤干扰值的有效性验证.由于kNN算法在检测异常时存在一定的漏报和误报,为减少由于数据间相互干扰带来的误报和漏报率,使用RkNN算法对kNN算法进行优化.在该组实验中,对反向过滤干扰值方法的有效性进行验证,对两种不同距离度量方式下的算法分别应用该方法.实验数据集由两种不同刷信誉行为下的数据随机替换正常交易数据集中20%的正常数据组成.使用反向k近邻过滤方法下的统计检测方法记作SDD-RkNN;欧式距离度量方式下的基于距离的检测方式记为DBD-kNN;欧式距离度量方式下的基于反向k近邻过滤法的检测方式记为DBD-RkNN;W为各项评价指标的百分比.

由图5可见,A与F1值在SDD-RkNN和DBD-RkNN方法下分别比SDD-kNN和DBD-kNN方法下具有更高的值,同时具有更低的η值.由此可见,无论是在集中式还是在均衡式刷信誉方式下,反向过滤异常干扰方法均能有效提升算法的检测性能,评价指标η、A和F1值均得到了约1%的提升.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5   反向过滤干扰值法在原始数据集下实验结果

Fig.5   Experimental results of reverse filtering interference value method in original data set


由图6(a)可见,使用了反向k近邻法优化算法的SDD-RkNN和DBD-RkNN方法在增强数据集下集中式刷信誉模式的检测性能评测指标η、A和F1值相比于直接使用k近邻算法有所提升.由图6(b)可知,DBD-RkNN方法下的3项性能评价指标均无提升,因此当相似性度量为欧式距离时,对均衡式刷信誉模式应用反向k近邻法并不能提升算法性能,甚至会对原始算法的性能有微小的降低,增强数据集中随机生成的时间戳是导致该情况发生的原因之一.

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6   反向过滤干扰值法在增强数据集下实验结果

Fig.6   Experimental results of reverse filtering interference value method in enhanced data set


综合而言,使用RkNN算法对异常值之间互相干扰的情况进行优化的算法能有效提高SDD-kNN和DBD-kNN算法的检测效果.

实验3 算法性能对比.综合上述实验,基于反向k近邻的优化算法能够对kNN算法的检测结果进行优化,为进一步验证算法的优越性,将SDD-RkNN、DBD-RkNN算法与带证据集的动态统计检测(DSDD-E)算法[13]进行性能比较.为更好地检测均衡式刷信誉的方式引入二阶直方图技术,实验结果如表1和2所示.

表1   原始数据集下的算法性能对比

Tab.1  Comparison of algorithm performance in raw data set

模式算法名称一阶直方图二阶直方图
P/%R/%F1/%t/msP/%R/%F1/%t/ms
集中式刷信誉SDD-RkNN96.3096.3096.304542.8097.2397.2397.231612.45
DBD-RkNN99.6999.6999.692325.9791.6991.6991.69762.44
DSDD-E78.8499.6987.991507.3265.0696.9277.71491.29
均衡式刷信誉SDD-RkNN20.9220.9220.924401.5780.9280.9280.921517.24
DBD-RkNN79.3879.3879.382265.9869.8469.8469.84718.89
DSDD-E23.7813.5417.251400.5454.6780.3164.52494.79

新窗口打开| 下载CSV


表2   增强数据集下的算法性能对比

Tab.2  Comparison of algorithm performance in enhanced data set

模式算法名称一阶直方图二阶直方图
P/%R/%F1/%t/msP/%R/%F1/%t/ms
集中式刷信誉SDD-RkNN94.4694.4694.469671.6788.0088.0088.002108.75
DBD-RkNN96.3096.3096.304637.6774.7774.7774.77995.40
DSDD-E75.17100.0085.702140.2149.1491.3863.90565.68
均衡式刷信誉SDD-RkNN16.9216.9216.9210356.1979.6979.6979.691940.85
DBD-RkNN81.8581.8581.854913.4058.4658.4658.46898.06
DSDD-E23.3513.8417.382280.1553.7775.0860.98550.01

新窗口打开| 下载CSV


由表1可知,集中式刷信誉模式下最好的F1值可达到99.69%,而均衡式刷信誉模式下最高的F1值为80.92%.由表2可知,集中式刷信誉模式下的最优F1值可达到96.30%,而均衡式刷信誉模式下最高的F1值为81.85%.因此,集中式刷信誉模式比均衡式刷信誉模式更易于检测.这是由于集中式刷信誉模式下异常集群的数据分布明显区别于正常集群,所以异常集群具有较高的异常得分.均衡式刷信誉模式由于异常集群与正常集群的数据分布比较相似而较难检测.尽管如此,在一阶直方图下,从表1和2的均衡式刷信誉模式中可见,SDD-RkNN方法下的F1值分别从20.92%、16.92%提升至DBD-RkNN方法下的79.38%与81.85%.可见,对微小变化敏感的欧式距离仍然可以较好地识别均衡式刷信誉模式下的异常集体.均衡式刷信誉模式中,SDD-RkNN方法在一阶和二阶直方图下的F1值分别从20.92%、16.92%提升至80.92%以及79.69%.由此可见,二阶直方图技术的应用有利于发现均衡式异常.这是由于二阶直方图的技术通过改变数据分布放大了异常集体与正常集体的分布差异导致的.

对明显区别于正常集群的集中式异常的检测,由表1的集中式刷信誉模式可见,使用DSDD-E算法时F1值为87.99%,使用DBD-RkNN算法后F1值可达到99.69%.同时,由表1其余内容可见,所提算法的P、R和F1值均优于DSDD-E算法.这是由于DSDD-E算法计算的是局部差异,而SDD-RkNN和DBD-RkNN算法是与待测数据集进行全局数据的差异比较,能够获得更准确的信息.所以与DSDD-E算法相比,所提算法的性能更优.所提算法在建立全局距离权图时,需要计算每两个集群之间的距离,时间复杂度为O(n2),算法的时间资源消耗较高.SDD-RkNN算法性能与DBD-RkNN算法性能几乎一样优秀,但欧式距离的度量方式比JSD方式节省了一半的时间资源,这是由两种不同相似性度量计算方式带来的差异.

实验4 算法稳定性分析.稳定性是评价算法性能的重要指标之一,为更好地观察算法的稳定性,取不同的U对算法的稳定性进行分析.实验数据集由正常交易数据集依次替换不同数目、不同刷信誉模式的异常集群构成.考虑到实际生活中异常出现的概率一般不会超过数据集的总量一半,因此分别取U=10%、20%、30%、40%、50%进行不同衡量指标的检测.对于不能很好地识别出均衡式刷信誉的算法使用二阶技术进行检测.实验结果如图7所示.

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7   不同异常概率下,3种算法的稳定性对比

Fig.7   Comparison of stability of three algorithms under different anomaly probabilities


由图7可知,对于A和F1值这两项评价指标,越平稳的接近图正上方,则算法性能越稳定.SDD-RkNN算法和DBD-RkNN算法的性能评价指标折线图比DSDD-E算法的性能评价指标折线图更接近图的正上方,故所提算法具有更高的稳定性和更好的性能.由图7(d)可知,DSDD-E算法的F1值在不同异常概率下明显偏离SDD-RkNN算法和DBD-RkNN算法的F1值,这是由于SDD-RkNN算法和DBD-RkNN算法总是通过全局比较获得异常得分,因此异常比例对该算法的影响较小.而DSDD-E算法依赖于数据分布估计的准确性,在使用二阶技术时,直方图变得粗糙,因此该算法的检测性能明显较差.

4 结语

本文提出一种无监督式的基于反向k近邻法的群数据异常检测算法.对无数据标签的数据集进行集体数据的划分,直接建立模型检测异常.根据集群数据的分布相似性,使用JSD作为k近邻算法在求取异常得分时的距离度量,针对异常值之间相互干扰的问题提出使用反向k近邻对异常值进行过滤,优化算法性能.

通过大量对比实验可见,基于反向k近邻过滤异常值的方法能有效提高kNN算法的检测质量.欧式距离对微小变化足够敏感,因此在不使用二阶直方图的技术下也能较好地识别出均衡式刷信誉模式.在二阶技术的使用下,SDD-RkNN算法能较好地识别出此异常,同时该算法具有较强的稳定性.通过与引入的DSDD-E算法的对比,所提的SDD-RkNN算法能更好地识别出异常,可应用于相关数据资源的检测和筛选中.

参考文献

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

[本文引用: 1]

TIMČENKO V, GAJIN S.

Ensemble classifiers for supervised anomaly based network intrusion detection

[C]//2017 13th IEEE International Conference on Intelligent Computer Communication and Processing (ICCP). Piscataway, NJ, USA: IEEE, 2017: 13-19.

[本文引用: 1]

HUSSAIN B, DU Q H, REN P Y.

Semi-supervised learning based big data-driven anomaly detection in mobile wireless networks

[J]. China Communications, 2018, 15(4):41-57.

[本文引用: 1]

MILLER D J, KESIDIS G, QIU Z C.

Unsupervised parsimonious cluster-based anomaly detection (PCAD)

[C]//2018 IEEE 28th International Workshop on Machine Learning for Signal Processing (MLSP). Piscataway, NJ, USA: IEEE, 2018: 1-6.

[本文引用: 1]

CHANDOLA V, BANERJEE A, KUMAR V.

Anomaly detection

[J]. ACM Computing Surveys, 2009, 41(3):1-58.

[本文引用: 1]

TAO X T, LI G Q, SUN D, et al.

A game-theoretic model and analysis of data exchange protocols for Internet of Things in clouds

[J]. Future Generation Computer Systems, 2017, 76:582-589.

DOI:10.1016/j.future.2016.12.030      URL     [本文引用: 1]

EDGEWORTH F Y.

On discordant observations

[J]. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 1887, 23(143):364-375.

DOI:10.1080/14786448708628471      URL     [本文引用: 1]

KNORR E M, NG R T, TUCAKOV V.

Distance-based outliers: Algorithms and applications

[J]. The VLDB Journal, 2000, 8(3/4):237-253.

DOI:10.1007/s007780050006      URL     [本文引用: 1]

LEE J G, HAN J W, LI X L.

Trajectory outlier detection: A partition-and-detect framework

[C]//2008 IEEE 24th International Conference on Data Engineering. Piscataway, NJ, USA: IEEE, 2008: 140-149.

[本文引用: 2]

LUAN F J, ZHANG Y T, CAO K Y, et al.

Based local density trajectory outlier detection with partition-and-detect framework

[C]//2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD). Piscataway, NJ, USA: IEEE, 2017: 1708-1714.

[本文引用: 1]

DJENOURI Y, BELHADI A, LIN J C, et al.

Adapted K-nearest neighbors for detecting anomalies on spatio-temporal traffic flow

[J]. IEEE Access, 2019, 7:10015-10027.

DOI:10.1109/Access.6287639      URL     [本文引用: 1]

毛江云, 吴昊, 孙未未.

路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法

[J]. 计算机学报, 2018, 41(8):1928-1942.

[本文引用: 1]

MAO Jiangyun, WU Hao, SUN Weiwei.

Vehicle trajectory anomaly detection in road network via Markov decision process

[J]. Chinese Journal of Computers, 2018, 41(8):1928-1942.

[本文引用: 1]

WANG R Y, SUN D, LI G Q, et al.

Statistical detection of collective data Fraud

[C]//International Conference on Multimedia and Expo. London, UK: IEEE, 2020.

[本文引用: 4]

KULLBACK S, LEIBLER R A.

On information and sufficiency

[J]. Annals of Mathematical Statistics, 1951, 22(1):79-86.

DOI:10.1214/aoms/1177729694      URL     [本文引用: 1]

SALEM O, NAÏT-ABDESSELAM F, MEHAOUA A.

Anomaly detection in network traffic using Jensen-Shannon divergence

[C]//2012 IEEE International Conference on Communications (ICC). Piscataway, NJ, USA: IEEE, 2012: 5200-5204.

[本文引用: 1]

COVER T, HART P.

Nearest neighbor pattern classification

[J]. IEEE Transactions on Information Theory, 1967, 13(1):21-27.

DOI:10.1109/TIT.1967.1053964      URL     [本文引用: 1]

WOHLKINGER W, ALDOMA A, RUSU R B, et al.

3DNet: Large-scale object class recognition from CAD models

[C]//2012 IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2012: 5384-5391.

[本文引用: 1]

AGGARWAL C C. Proximity-based outlier detection[M]// Outlier Analysis. Switzerland: Springer International Publishing, 2016: 111-147.

[本文引用: 1]

陈瑜.

离群点检测算法研究

[D]. 兰州: 兰州大学, 2018.

[本文引用: 1]

CHEN Yu.

Research on the outliers detection algorithm

[D]. Lanzhou: Lanzhou University, 2018.

[本文引用: 1]

/

〈 〉