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