基于自然最近邻的无参聚类算法研究.pdf.pdf

基于自然最近邻的无参聚类算法研究



重庆大学硕士学位论文
(学术学位)


学生姓名:黄金龙
指导教师:朱庆生教授
专业:计算机软件与理论
学科门类:工学



重庆大学计算机学院
二 O 一四年四月
Study on non-parametric clustering based
on natural nearest neighborhood


A Thesis Submitted to Chongqing University
In Partial Fulfillment of the Requirement for the
Master‘s Degree of Engineering
By
Huang Jinlong

Supervised by Prof. Zhu Qingsheng
Specialty: Computer Software and Theory




College puter Science of
Chongqing University, Chongqing, China
April 2014
重庆大学硕士学位论文中文摘要

摘要

数据挖掘就是在大量的数据中探索出有价值的模式、规则和规律的过程,即
从海量无规律的数据集中提取出可理解的、之前人们并不清楚的且存在潜在价值
的知识的过程。数据挖掘的主要任务包括回归分析(Regression)、关联分析
(Association rule learning)、分类分析(Classification)、聚类分析(Clustering)以及异
常分析(Outlier detection)等。其中数据聚类则是数据挖掘中一项非常重要的技术,
是人们在认识和挖掘研究对象之间内在联系的一种非常常用的方法,它不但可以
作为独立的数据挖掘工具,从知识库中获取到数据结构的分布信息,还可以对数
据集进行预处理以方便其它一些数据挖掘算法对数据集进行数据挖掘。聚类分析
是一种无监督的数据挖掘分析算法,无监督的聚类分析算法能够挖掘出输入数据
集的内部分布结构以及类簇信息。目前包括计算机模式识别中的视觉分析、图像
识别和分割等领域都在广泛地应用聚类分析技术。同时聚类分析也被应用于统计
分析,医疗信息处理,生物工程,社会科学和心理研究等各个数据分析场合。在
商务管理、市场分析、工程设计等商业领域中也应用到了数据挖掘的聚类分析技
术。所谓聚类就是将需要处理的整个数据集划分成多个不同的类簇,类簇与类簇
之间距离或者相异性尽量的大,而使得类簇内部尽量的紧凑。
最近邻居概念早在 1951 年就已经被提出,一经提出就广泛的受到关注和研究,
且被广泛应用于模式识别、机器学习、数据挖掘等领域。最著名同时也是最基础
的两个最近邻居概念就是 Stevens 所提出的 K-最近邻居和ε-最近邻居概念。现如
今数据挖掘中的很多聚类算法、离群检测算法等都应用到了 K-最近邻和ε-最近邻
的概念,并提出了许多著名的数据挖掘算法,比如 K-NN 分类算法、LOF 和 INFLO
离群检测算法等。但是随着 K-最近邻和ε-最近邻这两个概念的应用越来越深入,
K-最近邻和ε-最近邻的不足和缺点也显露在我们面前。那就是对于一个未知的数
据集,在 K-最近邻的概念下每个数据对象应该有多少邻居才算合适,K 值设为多
少才能够正确地反映出这个未知数据集的结构特性。特别是在如今数据以爆炸式
增长的大数据时代,数据集的复杂度变得越来越高,未知性也越来越强,在利用
基于 K-最近邻的数据挖掘算法对数据进行挖掘时,K 值也越来越难设置。ε-最近
邻在各个邻域中的应用也同样遇到这一问题,ε值大小的设置往往会对数据的最
后挖掘效果产生很大的影响。而在ε-最近邻中一旦ε设置后,密集区域的数据对
象的近邻相对稀疏区域的数据对象较多。无论是 K-最近邻还是ε-最近邻,其近邻
的搜索都是靠人为地设置参数得到的,而不是根据所给数据集自身的特性搜索,
这就是上述问题的根本原因。
I
重庆大学硕士学位论文中文摘要
为了解决 K-最近邻居和ε-最近邻居概念中面临的参数选择的问题,本文引进
了自然最近邻居这一新的最近邻居概念。并在对原有的自然最近邻居搜索算法进
行实验分析后,对自然最近邻居概念及搜索算法进行了改进。自然最近邻居
(Natural Nearest Neighbor:3N)是在 2011 年由邹咸林博士等人提出的一种新的
最近邻居概念。自然最近邻居是一种无尺度的最近邻居概念,