文档介绍：基于自然最近邻居的离群检测算法研究
重庆大学硕士学位论文
(学术学位)
学生姓名:唐汇
指导教师:朱庆生教授
专业:计算机软件与理论
学科门类:工学
重庆大学计算机学院
二 O 一四年四月
An outlier detection algorithm based on
natural nearest neighbor
A Thesis Submitted to Chongqing University
in Partial Fulfillment of the Requirement for the
Master’s Degree of Engineering
By
Tanghui
Supervised by Zhu Qingsheng
puter software and theory
College puter Science and technology of Chongqing
University , Chongqing, China
April 2014
重庆大学硕士学位论文中文摘要
摘要
在数据挖掘领域中,k 最近邻域是一个最基本的并被广泛采用的邻域概念,它
是由离数据对象最近的 k 个点所形成的一个局部数据子集。国内外众多学者以 k
最近邻域概念为基础提出了大量的优秀的数据挖掘算法。但是在解决实际问题的
时候,任何涉及 k 近邻的算法,当参数 k 值选择不同时,都会明显影响算法产生
的实际性能和检测结果。即使是采用同一个算法,由于被处理的数据集特征不同,
k 值选择也没有可借鉴性,通常 k 值的选择都是依靠用户经验和大量实验来决定,
在 k 近邻算法中如何选择一个合适的参数 k 值一直是一个研究难点。
本文引入了一种新的邻域技术—自然最近邻居,它不需要设置参数 k,每个节
点的邻居是由算法自适应计算而形成的。针对离群检测的特殊性,我们改进了自
然最近邻居搜索算法的终止条件,并且综合了数据对象在自然最近邻域中的三类
不同的离群指数,包括频率离群指数,局部离群指数以及簇离群指数,提出了一
种新的基于自然最近邻居的离群点检测算法 ODB3N。实验表明,该算法不仅避免
了 k 近邻中参数选择问题,而且能够更有效地发现离群簇。
本文的主要工作和创新包括以下部分:
①分析了离群数据挖掘的研究背景及国内外发展现状和趋势。
②详细介绍了离群数据挖掘的典型算法和思想,以及数据挖掘的具体流程。
③引入了自然最近邻居技术,并且改进了自然最近邻居搜索算法的终止条
件。通过在随机测试数据集上验证了改进后的算法的稳定性,在不同密度分布的
数据集上分析验证了自然最近邻域图 3NG 自动聚类的特性。
④提出了一种无参数的基于自然最近邻居的离群点检测算法,通过分析每个
数据对象在自然最近邻居中的离群特征,提出了频率离群指数,局部离群指数以
及簇的离群指数相关定义,形成了一种能够更加完整地描述数据离群特征的新标
准。
⑤在人工数据集和真实数据集上进行了验证,同时比较了传统的 KNN 算法
和 LOF 算法在相同数据集上的检测效果。
关键词:k 近邻;自然最近邻;离群检测;离群簇
I
重庆大学硕士学位论文英文摘要
ABSTRACT
k-nearest neighbor is a basic concept of neighborhood,which is widely used in the
fields of data mining. k-nearest neighbor of the data object is a data subset which
formed by the its k nearest years, k-nn has attracted the interest of
expects and scholars, and many outlier detection algorithms based on the k-nearest
neighbor have been presented. When the k-nearest neighbor method is used, it is
difficult to choose an appropriate parameter k of the algorithm which affects