基于记忆效应的局部异常检测算法_李健1
需积分: 0 172 浏览量
2022-08-03
12:10:50
上传
评论
收藏 1.16MB PDF 举报
—4—
基于记忆效应的局部异常检测算法
李 健
1,2
，阎保平
1
，李 俊
1
(1. 中国科学院计算机网络信息中心，北京 100080；2. 中国科学院研究生院，北京 100080)
摘 要：基于密度的局部异常检测算法(LOF 算法)的时间复杂度较高，限制了其在高维数据集以及大规模数据集中的使用。该文通过分析
LOF 算法，引入记忆效应概念，提出具有记忆效应的局部异常检测算法——MELOF 算法。实验测试表明，该算法的计算结果与 LOF 算法
完全相同，而且能够大大缩短运行时间。
关键词：数据挖掘；异常检测；局部异常因子；记忆效应；MELOF 算法
Memory-effect-based Local Outlier Detection Algorithm
LI Jian
1,2
, YAN Bao-ping
1
, LI Jun
1
(1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100080;
2. Graduate University of Chinese Academy of Sciences, Beijing 100080)
【Abstract】The computational complexity of algorithm for identifying density-
b
ased local outliers (LOF algorithm) is not ideal, which affects its
applications in large scale data sets, especially in high dimensional data sets. Under such circumstances, the concept of memory effect is introduced,
which lays the foundation for the newly enhanced algorithm called MELOF. Experimental result shows that MELOF algorithm obtains the same
result as LOF algorithm, and shortens the execution time obviously.
【Key words】data mining; outlier detection; Local Outlier Factor(LOF); memory effect; MELOF algorithm
计 算 机 工 程
Computer Engineering
第 34 卷 第 12 期
Vol.34 No.12
2008 年 6 月
June 2008
·博士论文·
文章编号：1000—3428(2008)12—0004—03
文献标识码：A
中图分类号：TP311.13
异常检测是数据挖掘领域的基本问题之一，用于发现数
据集中与其他数据明显不同的对象。
LOF(Local Outlier Factor)
算法
[1]
在异常检测算法中占据着非常重要的地位。但是
LOF
算法的时间复杂度为
O
(
n
2
)
，虽然可以采用基于树的索引结构
将时间复杂度降到
O
(
n
log
n
)
，但是建立索引结构的过程复杂
而且耗时，限制了该算法在大规模数据集中的应用。本文分
析了
LOF
算法的特点，在邻域查询过程中充分利用邻居对象
的信息，引入记忆效应的概念，提出了基于记忆效应的局部
异常检测算法——
MELOF
算法。
1 LOF
算法
到目前为止，异常检测算法分为基于统计的算法、基于
距离的算法、基于密度的算法和基于偏差的算法等
[2]
。
Breunig
提出基于密度的局部异常检测算法，给出了局部异常因子的
概念。
邻域查询是基于密度的数据挖掘算法中最基本的概念。
对于数据集
D
，计算某对象
p
与
D
内所有对象之间的距离并
获取其中符合一定条件的对象集合，该过程称为针对对象
p
的一次邻域查询。
假设数据集
D
包含
n
个对象，
LOF
算法需要一个参数
MinPts
用于指定邻域中对象的最小个数。
LOF
算法按以下
3
步进行
[3]
：
(1)
对数据集
D
中每个对象进行邻域查询，计算其
MinPts-
距离邻域，并将该对象与该邻域中每个对象的距离存入数
据库。
(2)
利用存储在数据库的计算结果，计算每个对象的局部
异常因子。需要扫描数据库
2
次：计算每个对象的局部可达
密度；计算每个对象的局部异常因子。
(3)
根据用户输入的
LOF
阈值，将
LOF
值高于该阈值的
对象判定为异常。
一些基本概念介绍如下：
定义
1
对象
p
的
MinPts
-
距离邻域，即所有与对象
p
的
距离不超过
MinPts-distance
(
p
)
的对象组成的集合。形式化表
示为
N
MinPts-distance
(
p
)={
q
∈
D
\{
p
} |
d
(
p
,
q
)
≤
MinPts-distance
(
p
)}
简写为
N
MinPts
(
p
)
，其中，
MinPts-distance
(
p
)
表示对象
p
的
MinPts
-
距离。当某对象
o
满足如下条件：
(1)
至少存在
MinPts
个对象
s
∈
D
\{
p
}
，使得
d
(
p
,
s
)
≤
d
(
p
,
o
)
；
(2)
至多存在
MinPts
-1
个对象
s
∈
D
\{
p
}
，使得
d
(
p
,
s
)<
d
(
p
,
o
)
。
则对象
p
与
o
的距离
d
(
p
,
o
)
记为
MinPts-distance
(
p
)
，简
写为
MinPts-d(p
)
。
定义
2
对象
p
的局部可达密度
lrd
MinPts
(
p
)
表示如下：
()
(,)
() 1/
|()|
MinPts
MinPts
sN p
MinPts
MinPts
reach dist p s
lrd p
Np
∈
−
∑
⎛⎞
⎜⎟
=
⎜⎟
⎝⎠
其中，
reach-dist
MinPts
(
p
,
s
)
表示对象
p
相对于
s
的可达距离，
定义为
reach-dist
MinPts
(
p
,
s
)=max{
MinPts-d
(
s
),
d
(
p
,
s
)}
。
定义
3
对象
p
的局部异常因子，其计算公式为
()
()
()
()
|()|
MinPts
MinPts
sN p
MinPts
MinPts
MinPts
lrd s
lrd p
LOF p
Np
∈
∑
=
可以看出，
LOF
算法的时间复杂度取决于邻域查询操作。
作者简介：李 健(1979－)，男，博士研究生，主研方向：网络安全，
网络管理，数据挖掘；阎保平、李 俊，研究员
收稿日期：2007-08-17 E-mail：[email protected]
评论0