-
基于聚类的离群点检测方法
Rajendra
Pamula, Jatindra Kumar Deka, Sukumar Nandi
Department of Computer Science and
Engineering
Indian Institute of
Technology Guwahati
Guwahati, Assam,
India
Email:
<,jatin,sukumar>@
摘要
< br>:
本论文提出来一个聚类方法用以检测离群点。通过使用
k
均值聚类算
法来从数据集中划分聚类。
离聚类中心比较近的点不太可能是离群点，
同时我们
可以从聚
类中去除掉这些点。
接下来计算剩下的点和离群点的距离。
需要
计算的
离群点度的降低可能是由于一些点的去除。我们声明离群度最高的点作为离群
点。实验数据使用真实数据集，并论证得知，即使所计算的数据比较少，但所提
出的方法比现存的方法优越。
关键字
:
离群点；聚类；基于距离；
1.
引言
离
群点是和数据集中正常点不一致的数据点。
离群点检测在数据清理中有重
要的应用，像欺诈检测，入侵检测，营销，传感网络，垃圾邮件检测。在数据点
中找出异常点是离群点检测的基础理论。离群点检测暗示对象脱离给定的数据
集。
离群点的检测已经广泛地在统计领域研究。
典型地就是用户需要使用统
计分
布对数据点建模，
同时一个点被划为离群点主要看其和假定
模型的关联。
这些技
术的主要问题是许多情况下用户可能对基础
数据分布没有足够的了解。
特别是对数据集中的每一对关联对
象使用距离函数的基于距离的技术。
基于
距离的定义描述了一个
对数据分析有效的工具。
这些定义以计算的方式是有效率
的，而
在部分已经检测的数据集中基于距离的离群点的得分是单调非递增函数。
最近几年已经提
出了许多快速检测基于距离的离群点算法。一些算法在
CPU
消
耗上比较有效，而其他一些主要是侧重于
I/O
消耗。
许多方法用来查找偏离其他点的某个点，
这意味着这个点是离群点。
众所周
知，
数据集中的离群点是相当少的。
因此也没必要为所有点提供这些方法
。
通过
移除可能不是离群点的这些都，我们可以降低计算时间。
1
我们
的工作是使用聚类和距离函数来区别那些不是离群点的点，
然后去除这
< br>些点。
接下来为所有剩余的点预测基于距离的方法，
这些
方法使用一个参数来区
别一个点是不是离群点。
我们假设数据集
中有
n
个离群点，
然后通过我们的方法
得出的前
n
个点作为离群点。我们使用
基于距离的局部离群系数来区别离群点。
2.
相关工作
Knorr and Ng
是第一个提出基于
距离的离群点检测方法。如果数据集中至少
有
pct
部分对象和对象
p
的距离大于
D,
则对象
p
是一个基于距离的关
于参数
pct
和
D
的离群点即
DB
（
pct,D
）离群点。这个定义被广泛接受，因为它归纳了许多
统计离群的测试
。
Ramaswamy
等人提出了以
上定义的扩展。所有点根据离群度划分。给定两
个变量
kn
和
w
，
如果
Dk
中比
p
有更高价
值的对象数少于
w
，
则对象
p
被认为是
离群点，其中
Dk
表示对象
p
的第
< br>k
个最近邻的距离。
随后，
Angiulli
和
Pizzuti
提出了一个通过考虑全部对象领域来决定离群点的
方法。
所有点的划分是基于第
k
个最近邻距离的总和，
而不是单独考虑第
k
个最
近邻的距离。上述的三个定义是紧密相关的。
Breuning
等人提出了数据集中用以表示每个对象离
群程度的局部离群系数。
这是关于离群点离群程度的第一个概念。
离群系数局限在仅考虑一个约束领域的
每个对象。
一个对象的
局部离群系数可以通过和它的领域比较其密度。
它比基于
距离的
方法有更强的模型能力，
因为它仅仅是基于对象本身的密度。
基
于密度的
方法不能明确地把对象归类为离群点或者非离群点。
Zhang
等人提出了局部基于距离的离群点检测方法。基于距
离的局部离群系
数可以确定一个对象偏离其邻域的程度。
计算数
据集中所有点的基于距离的局部
离群系数，其复杂度为
O
(
N
2
)
，其中
N
是数据集中点的个数。
< br>
聚类方法有许多，像
CLARANS,DBSCAN,
BIRCH
和
CURE
都能检测离群点
。然
而，
因为聚类方法的主要目的是发现聚类，
其发展是为了使聚类最优化，
而不是
使离群点检测最优
化。离群点的定义使用的是主观的被这些算法检测到的聚类。
而基于距离的离群点定义则
更加客观并且聚类是怎样在输入的数据中被检测出
来的显得相对独立。
< br>
2
目前关于离群点的工作
主要是仅仅集中在识别方面，在文献
11
中打算提供
有意的知识，它是基于为什么一个待鉴定的离群点是异常的解释。
3.
背景
我
们使用基于距离的局部离群系数，
它能表示一个点偏离其领域的程度。
< br>一
个点的
LDOF
值高就意味着
偏离其领域比较多，同时也就意味着可能是离群点。
LDOF
的
计算如下：
LDOF
中的
p
，其定义如下：
LD
OF
(
p
)
:
?
d
p
D
p
D
p
:
?
1
dist
(
q
,
q
')
?
k
(
k
?
1)
q
,
q
'
?
N
p
,
q
?
q
'
<
/p>
计算所有点
LDOF
值计算消耗比较大，
但算法的复杂度是
O
(
N
2
)
。我们尝试
在去除那些可能不是离群点的点时降低计算复杂度。
4.
基于局部离群点的剪枝
这部分主要描述提出的算法，它是
LDOF
的改
进。在文献
18
中提出的
LDOF
算法的主要缺点是计算消耗巨大。这是因为数据集
DS
中的每个点都要计算其
LDOF
。而我们所关注的仅
仅是离群点，它的数量是非常少的，对于所有点
LDOF
的计算
用处较小，可以一起避免。
我们使用
K
均值算法来对数据集进行聚类。
一旦聚类形成，
则计算每个聚类
的半径。
去除那些离质心的距离比半
径小的点。
然后计算每个聚类中未被剪枝点
的
< br>LDOF
值。记录拥有高
LDOF
值的前
n
个点作为离群点。
A
．
简述
基于剪枝算法的主要思想是首先
对数据集进行聚类，
然后从聚类中剪去那些
可能不是离群点的点
。
而离群点的数目
n
可能会很小，
这种额外的前序步骤可以
帮助去除不是离群点的点。算法
1
描述了我们查找离群点的方法。
我们简要描述一下剪枝算法执行所需要的步骤。
(1)
产生聚类：首先使用
K
均值聚类算法对整个数据集聚类，然后计算每个聚类
3
的半径。
（
2
）剪枝：如果一个聚类包含的点比要求的离群点的数目要少，这个聚类就可
以免去剪枝。
为每个聚类剪枝：
计算聚类中每个点离质心的距离。
如果距离比半径小，
则去除
该点。
(3)
估算离群点：
计算所有聚类中未被剪枝的点的
LDOF
。
则拥有高
LDOF
< br>值的前
n
个点作为离群点。
<
/p>
K
均值算法复杂度为
c*it*N
，其中
c
是聚类的数目，
it
是重复计算的次数，
N
是数据
点的数目。这个算法的总的复杂度是
c*it*N+c*n
p<
/p>
+
(
w
*
N
)
2
，
其中
np
表
示每个聚类中
的点的平均个数，
w
表示剪枝后剩下的点所占的比率，这个值一
般
在
0.4
左右。聚类的数目
c
依赖与离群点的数目。然而
c
和
it
是比较小的，所
以总得
复杂度要小于
N
2
。
< br>
算法
1
离群点检测算法
输入：数据集
DS
，聚类数
c
，重
复次数
it
，离群点个数
n
1.
使用
K
均值聚类算
法得到聚类
,
得到
Y
each cluster
C
j<
/p>
?
Y
do
3.
Radius
j
←
radius
(
C
j
)
for
|Cj|>n then
6. for
each point pi
∈
Cj do
7. if
distance(pi,oj)
8.
prune(pi)
9. else
10. Add pi to U
11. end if
12.
end for
14. for each
point pi
∈
Cj do
4
-
-
-
-
-
-
-
-
-
上一篇：五星级酒店 常见词汇
下一篇：back的反义词和例句