没有合适的资源?快使用搜索试试~ 我知道了~
基于双向邻居修正的局部异常因子算法
0 下载量 199 浏览量
2021-01-13
19:18:51
上传
评论
收藏 1.12MB PDF 举报
温馨提示
试读
11页
针对现有离群点检测算法存在参数选取困难、效率差和精度低等问题,提出了基于双向邻居修正的局部异常因子算法。为了解决所提问题,首先提出了基于双向邻居的搜索算法,降低邻居搜索占用时间,然后使用双向邻居的修剪算法减少参数输入以及不必要的异常值计算。同时提出了基于双向邻居的修正因子,并利用反向邻居进一步提高计算精度。实验结果表明,所提算法减少了参数选取,提高了时间效率,同时基于双向邻居的修正因子使算法在合成数据集和UCI数据集上的准确率更高。
资源推荐
资源详情
资源评论
2020 年 8 月 Journal on Communications August 2020
第 41 卷第 8 期 通 信 学 报 Vol.41
No.8
基于双向邻居修正的局部异常因子算法
杨晓晖,刘晓明
(河北大学网络空间安全与计算机学院,河北 保定 071002)
摘 要:针对现有离群点检测算法存在参数选取困难、效率差和精度低等问题,提出了基于双向邻居修正的局部
异常因子算法。为了解决所提问题,首先提出了基于双向邻居的搜索算法,降低邻居搜索占用时间,然后使用双
向邻居的修剪算法减少参数输入以及不必要的异常值计算。同时提出了基于双向邻居的修正因子,并利用反向邻
居进一步提高计算精度。实验结果表明,所提算法减少了参数选取,提高了时间效率,同时基于双向邻居的修正
因子使算法在合成数据集和 UCI 数据集上的准确率更高。
关键词:异常值检测;局部异常因子;双向邻居;修正因子
中图分类号:TP181
文献标识码:A
doi: 10.11959/j.issn.1000−436x.2020119
Local outlier factor algorithm based on correction of
bidirectional neighbor
YANG Xiaohui, LIU Xiaoming
School of Cyber Security and Computer, Hebei University, Baoding 071002, China
Abstract: A local outlier factor algorithm based on bidirectional neighbor correction was proposed to solve the problems
of existing outlier detection algorithms such as difficulty in parameter selection, poor efficiency and low accuracy. The
bidirectional neighbor searching algorithm was used to reduce the neighbor search time. Then the bidirectional neighbor
pruning algorithm was used to reduce the number of parameters and unnecessary calculations. And the correction factor
based on bidirectional neighbors was used to improve the calculation accuracy. Experimental results show that the pro-
posed algorithm has better performance in parameter selection and time efficiency than other outlier detection methods.
The correction factor improves the accuracy of the algorithm, in the synthetic data set and UCI data set.
Key words: outlier detection, local outlier factor, bidirectional neighbor, correction factor
1 引言
离群值检测是数据挖掘领域的热门话题,其任
务是识别与大多数对象明显不同的数据对象,这类
数据与其他现有数据表现形式不一致,通常包含部
分关键信息,且信息不易被发现,但是具有很高的
研究和应用价值。离群挖掘是数据挖掘和数据分析
的重要分支,已广泛应用于欺诈检测
[1]
、垃圾邮件
检测
[2]
、交通异常
[3]
、网络流量异常检测
[4]
、入侵检
测
[5-6]
和社交网络异常用户发现
[7]
等领域。大多数现
有的解决方案通常从全局角度来识别离群值,这不
适用于高维和海量数据集
[8-9]
。随着获取信息技术的
发展和高维、海量数据的爆炸性增长,采用传统方
法进行全局异常值检测将非常困难。
2 相关工作
离群值,即数据中的不合理值,可以由不同的
机制产生。现有检测算法主要分为基于统计、基于
深度、基于聚类、基于距离和基于密度的算法。
在基于统计的离群值检测算法中,偏离标准分
收稿日期:2020−01−15;修回日期:2020−04−30
基金项目:国家重点研发计划基金资助项目(No.2017YFB0802300)
Foundation Item: The National Key Research and Development Program of China (No.2017YFB0802300)
第 8 期 杨晓晖等:基于双向邻居修正的局部异常因子算法 ·131·
布的对象被认为是离群值
[10]
,该类方法需要数据集相
关的先验知识,不适用于高维或分布未知的数据集。
基于深度的离群值检测算法
[11-13]
将数据分成
不同层次,根据分层结果将外层或容易分层的对象判
定为离群点,但该算法在高维数据集上的效率较低。
在基于聚类的离群值检测算法中,距其聚类中
心较远的某些数据对象被视为离群值
[14]
,算法必须
建立聚类模型才能检测离群值,因此检测效率较低。
基于距离的离群值检测算法因简单高效而被
广泛使用。在基于距离的异常检测算法中,通过计
算数据集中一个对象与其他对象之间的距离来发
现异常值,但由于未考虑局部密度的变化,因此只
能检测全局异常值,无法检测局部异常值
[15]
。
在基于密度的离群值检测算法中,Breunig 等
[16]
定义了局部异常因子(LOF, local outlier factor)算
法,通过将每个对象的密度估计值与其 k 个最近
邻居进行比较来计算对象的离群程度。LOF 算法
已经广泛使用,但是存在参数敏感问题。为此,
Ha 等
[17]
于 2014 年提出一种不稳定因子(INS,
instability factor)算法,该算法通过控制参数灵
活地用于局部和全局检测异常值。当参数改变时,
INS 算法的准确率变化很小,但是当精度稳定时,
INS 算法精度并不高。
Jin 等
[18]
改进了 LOF 算法,并提出基于影响域
的异常值(INFLO, influenced outlierness)检测算法,
对邻居的使用比较直接,将正向邻居和反向邻居都
视为同等作用,从而计算得出异常值。由于对邻居
的使用较简单直接,未考虑到最近邻居的异常程
度,因此精确度不高。
Zhu 等
[19]
定义自然邻居(natural neighbor)及
其搜索算法(nan-searching)来利用反向邻居
[20]
,
还定义自然影响空间(natural influence space)和 自
然邻域图(NNG, natural neighbor graph)
[21]
,并在后
续工作中利用自然邻居来约减邻居、降低噪声影响
[22]
。
Ning 等
[23]
通过搜索互邻图(MNG, mutual neighbor
graph)的稳定状态来找到合适的 k 值,虽然避免了
参数的选取问题,但在计算异常值时自然邻居对邻
居的使用比较简单,且准确率和效率较低。
因 LOF 为无监督算法,Auskalnis 等
[24]
提出了
用于网络入侵检测的 LOF 算法模型来检测未知手
段的攻击。Na 等
[25]
提出了数据流异常检测(DiLOF,
distributed local outlier factor)算法,减少了存储开
销和时间开销,但是仍存在参数选取困难的问题。
Yao 等
[26]
提出了一种增量式局部离群值检测模型,
用于数据流中的异常检测,虽然该模型使用了反向
邻居,但只是将反向邻居作为邻居扩充,策略简单,
检测性能略低。Ya ng 等
[27]
提出了一种邻居熵局部离
群值因子(NELOF, neighbor entropy local outlier
factor))检测模型,首先使用改进的自组织特征图
(SOFM, self-organizing feature map)算法对数据集
进行聚类,然后进行离群点检测,精度略有提高,
但因聚类算法的加入,效率较低。Gao 等
[28]
提出了
一种基于多维数据集的离群值检测算法,通过将高
维数据切片并检测,降低了存储和时间开销,但数
据切片会损失原有数据的高维特征,降低检测性能。
Zhao 等
[29]
提出了一种半监督集成算法(ExGBOD,
extreme gradient boosting outlier detection),使用集成
学习的思想结合监督学习和无监督学习的优势,但
弱化了无监督算法的泛化能力。
上述算法由于无法准确把握对象与邻域之间
的关系,导致在复杂数据集上计算准确率较低。如
图 1(a)所示,假设其 k 值为 3,此时对象 p 的 3 个
相邻对象具有比 p 更高的局部密度,即对象 p 将具
有较高的局部异常值。但是在复杂数据集上,常规
局部异常因子算法准确率并不高。如图 1(b)所示,
对象 p 是密集簇 C
1
附近的稀疏簇 C
2
的一部分,与
对象 q 和 r
1
相比,p 应当具有较小的离群值。若使
用常规局部异常因子算法,p 可能被错误地认为与
对象 q 具有相同大小的异常值。因此,现有的离群
值度量方法不适用于数据集包含具有不同密度多
个聚类分布的情况。由于对象最近邻居的错误选
择,导致邻域密度分布的错误估计,从而计算出一
个不准确的异常值。
为了更好地估计邻域的密度分布和计算局部
异常值,使用最近邻居和反向最近邻居是必要的。
如图 1(c)所示,情况与图 1(b)相同,但对象 p 具有
2 个反向最近邻居:s 和 t。这没有将其与反向最近
邻居的对象 q 区分开来,并且对象 r
1
仅具有作为其
反向最近邻居的异常 r
2
对象。因此加入反向最近邻
居能够较好地解决不同密度邻域间对象的异常值
计算问题。
现有算法对参数具有高度依赖性,参数改变对
异常值检测结果影响较大。另外由于没有充分利用
反向最近邻居的属性,导致计算准确率不高。针对
这一问题,本文提出了一种快速异常值检测算法,
既充分利用双向邻居,也避免了参数选取问题。
·132· 通 信 学 报 第 41 卷
图 1 不同密度簇间对象的异常计算问题
3 结合双向邻居的异常值计算算法
针对局部异常因子算法及其他改进算法的不足,
本文提出一种自动确定良好参数的修正局部异常因
子算法模型。受 page-rank 算法启发,CFLOF 算法将
反向邻居经过特殊处理后再参与到对象的异常值计
算中,若所有反向邻居无差别地参与异常值计算,将
存在误判问题,导致计算准确率较低。例如,在微博
用户异常检测中,把“僵尸粉”算作真正的粉丝是一
种错误处理,因此本文提出修正因子的概念来改善这种
问题,并通过第 4 节的实验验证了这种处理是有效的。
算法主要由 2 个部分组成:基于双向邻居的影响
域(IS, influence space)和用于解决不同密度簇之间
对象异常计算问题的修正因子(CF, correction factor),
如式(1)所示。
IS( )
lrd ( )
CFLOF ( ) CF( )
|IS( )|lrd ( )
k
op
k
k
o
pp
pp
∈
=
∑
(1)
其中,IS(p)为对象 p 的影响域,o 为 IS(p)中的对象,
lrd(p)为对象 p 的局部可达密度,CF(p)为对象 p 的
修正因子,则对象 p 的修正局部异常值(CFLOF,
correction factor local outlier factor)被定义为对象 p
局部可达密度与其影响域 IS(p)中对象局部可达密
度均值的比值乘以对象 p 的修正因子 CF(p)。
3.1 基于双向邻居的影响域
在算法计算的过程中,搜索对象的双向邻居需
要占用大量的时间,因此需要采用高效的算法来寻
找邻居节点。目前,主要使用 K-D 树或 R 树来索
引对象,从而加快邻居的搜索速度
[19]
。因此在邻居
搜索过程中,使用空间树结构来索引数据集中的所
有对象,并通过特定的修剪技术降低邻居节点查询
的成本。由于查询对象的最近邻时是通过遍历数据
集的子集来计算临时第 k 距离(k-dist(p)),且 k-dist(p)
的上限值已知,当 p 与 R 树中叶子节点最小边界矩
形(MBR, minimal bounding rectangle)之间的最小
距离(记为 MinDist(p, MBR))大于当前的 k-dist(p)
上限值,则节点中的任何对象都不会是 p 的 k 最
近邻之一。此优化方法可以修剪与 K 近邻(KNN,
K-nearest neighbor)搜索无关的整个子树。随着
KNN 的搜索,每个对象的反向最近邻居(RNN,
reverse nearest neighbor)可以在 R 树中动态维护。
在建立 KNN 和 RNN 索引后,可以计算局部异常
值并对其进行排序。算法 1 是通过在 R 树中构建
KNN 和 RNN 索引来挖掘异常值排名较高的 n 个
对象。
算法 1 双向邻居搜索算法
输入 k, D, R 树的根
输出 双向邻居的堆空间 heap
1) for each object p
∈
D do //遍历数据集
中对象
2) MBRList = root; k-dist(p) = ∞; heap = 0;
3) while (MBRList != empty) do // 遍历
所有 MBR 节点
4) 从 MBRList 从中摘取第一个 MBR;
5) if (第一个 MBR 是叶子节点) then
6) for each object q in 第一个 MBR do
//遍历 MBR 中对象
7) if (dist (p,q) < k-dist(p) and
(heap.size < k)) then
8) heap.insert(q) ;
//插入距离较小对象
9) k-dist(p) = d(p,heap.top); //更新 k-dist(p)
10) end if
11) end for
12) else
13) 将 MBR 的孩子节点附加到 MBRList;
14) 根据 MinDist 大小对 MBRList 排序;
15) for each MBR in MBRList do
16) if (k-dist(p) ≤ MinDist(p,MBR)) then
剩余10页未读,继续阅读
资源评论
weixin_38506835
- 粉丝: 5
- 资源: 958
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功