数据挖掘是从大量数据中发现潜在的有价值的知识,其主要任务包括回归分析(Regression)、关联分析(Association rule learning)、分类分析(Classification)、聚类分析(Clustering)以及异常分析(Outliers detection)等。聚类分析是其中的一个重要分支。所谓聚类就是将需要处理的整个数据集划分成多个不同的类簇,使得簇内对象彼此相似,而簇间对象彼此相异。聚类分析不仅可以作为独立的数据挖掘工具对数据集进行分析,聚类后通过对相似或相异的对象进行分析(集中对某些对象进行分析),可以帮助人们有效地提取共同的特征和发现有价值的信息,还可以在使用其他算法(如特征提取、离群检测、和分类)之前,先利用聚类算法将数据集中相似的对象划分到一起,不同的对象分开。聚类分析作为一种无监督的学习方法,在计算机领域(如图像处理、计算机视觉、模式识别、机器学习等),统计分析,社会学等邻域都有较为广泛的应用。针对不同的目的、方法,很多聚类算法已经被提出。其中层次聚类算法由于其思想比较简单,且能有效帮助分析具有层次结构的实际问题,因此成为应用较为广泛的一类算法。Chameleon算法是层次聚类算法中具有代表性的一个算法。它通过构造K-最近邻图,划分和利用基于互连度和接近度的簇与簇之间的相似性度量方法对划分得到的初始子簇进行合并等操作,使得Chameleon算法在发现任意形状的簇方面更具有优势。但是Chameleon算法需要进行参数设定,如设定构造K-最近邻图时的K值,对K-最近图进行划分时的子簇大小的阈值和进行子簇合并时的相似度阈值或期望的聚类数目。针对此问题,本文将自然邻居的概念引入到层次聚类算法中。自然邻居(Natural Neighbor:NaN)是我们提出的一种新的邻居概念,与以前的K-最近邻居和?-最近邻居不同的是它是一种无尺度的邻居概念。K-最近邻居和?-最近邻居,由于其方法比较简单,而且能够较好地反映数据集的分布特征,一经提出就被广泛应用于很多的分类算法如KNN分类算法、聚类算法如Chameleon算法和DBSCAN算法、离群检测算法如LOF和INFLO中。但是K-最近邻居和?-最近邻居在使用中都需要设定参数,特别是对于一个分布结构未知的数据集,K-最近邻居中的K值或者?-最近邻居中的?应设为多少才能够反映这个数据集的结构特性,越来越成为人们需要关注的问题。自然邻居在使用过程中不需设定任何参数,而是通过在给定的数据集上不断地扩大邻域搜索范围进行自适应学习,从而得到数据集的分布特征。在自然邻居的概念下,分布在密集区域的数据对象的自然邻居数较多,而分布在稀疏区域的数据对象的自然邻居数则较少。本文将自然邻居的概念与Chameleon算法相结合,提出了一种新的聚类算法——基于自然邻居的层次聚类算法Hi-CLUBS。首先利用自然邻搜索算法构造饱和自然邻域图,并提出了一种基于模块度的图划分算法将饱和自然邻域图划分成初始子簇,然后利用一种新的基于子簇互连度和子簇接近度的相似性度量方法对划分得到的初始子簇进行合并,直到得到期望的聚类数目。通过与其他算法的对比实验证明了Hi-CLUBS算法减少了对参数的依赖,而且在发现任意形状的簇方面更具优势。针对数据集中可能存在噪声点的问题,我们考虑先去除数据集中的噪声点,然后再对其进行聚类。由此本文提出了基于噪声去除的层次聚类算法HCBNR。首先利用自然邻居计算法每个数据对象的密度,根据密度递增曲线确定密度阈值,去掉数据集中的噪声点,然后利用我们在本文提出的Hi-CLUBS算法对剩余的数据集进行聚类。通过与DBSCAN、Chameleon、cluster_dp等算法进行对比,证明了HCBNR算法能够快速识别数据集中的噪声点,并对数据集中的非噪声点准确聚类。