基于层次的聚类算法的研究与实现

I独创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。论文题目：作者签名：日期：年月日论文版权使用授权书本人完全了解吉首大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同意吉首大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。(保密的学位论文在解密后应遵守此协议)论文题目：学生签名：日期：年月日导师签名：日期：年月日II基于层次的聚类算法的研究与实现摘要聚类分析是数据挖掘中的一个重要领域，是数据划分或分组处理的重要手段和方法，聚类分析已经应该于广泛的领域。聚类算法可以分为基于层次的方法、基于划分的方法、基于网格的方法、基于密度的方法和基于模型的方法。层次聚类算法因为算法思想简单，适合于大量数据的聚类，所以是实际应用中聚类分析的支柱。本文重点对层次聚类算法进行了分析和研究，阐述了基于层次聚类的CURE和BIRCH算法，并实现了这两种算法以及给出了它们的聚类结果。CURE算法是利用代表点聚类，它解决了偏好球形和相似大小的问题，可以发现具有任意大小和形状的聚类，而且在处理孤立点上也更加健壮。BIRCH是用聚类中心和半径来代表聚类，具有一定的处理噪音的能力，而且它是一种增量聚类方法，它不要求所有数据一次性读入内存，所以空间复杂度低，但是BIRCH算法无法发现任意形状和大小的聚类。关键词：聚类分析；层次聚类；CURE；BRICHIIIResearchandImplementationofthealgorithmbasedonhierarchicalclusteringSunXili(CollegeofInformationScienceandEngineering,JishouUniversity,Jishou,Hunan416000)Abstract:Clusteringanalysisisanessentialfieldindataminingandalsoimportantmeansandmethodofdataclassificationorgroupingprocessing.Clusteranalysishasplayedanimportantroleinawiderangeofdatapartitioningareas.Clusteringalgorithmscanbedividedintothemethodbasedonhierarchy,themethodsbasedonthepartition,thegrid-basedmethods,thedensity-basedmethodandthemodel-basedmethod.Hierarchicalclusteringalgorithmisamainstayoftheclusteringanalysisinpracticalapplicationforitssimplealgorithmideas,andsuitableforlargeamountsofdataclustering.Thispaperfocusesonthehierarchicalclusteringalgorithmanalysisandresearch,expoundsCUREandBIRCHalgorithmbasedonhierarchyclusteringalgorithm,andimplementsthetwoalgorithmsandtheirclusteringresultsaregiven.CUREalgorithmistheuseoftheclusteringoftherepresentativepoint,itsolvedtheproblemofthepreferenceofsphericalandsimilarsize,clusteringcanbefoundwithanysizeandshape,butalsomorerobustindealingwiththeisolatedpoint.BIRCHisusingtheclusteringcenterandradiustodelegateclustering,alsowiththeabilitytohandlingnoise,anditisakindofincrementalclusteringmethod,itdoes’trequirealldataisreadintomemoryinasingle,sothespacecomplexityislow,buttheBIRCHalgorithmcannotfindclusteringwithanyshapeandsize.Keywords:Clusteranalysis;Hierarchicalclustering;CURE;BRICHIV目录第一章绪论.............................................................................................11.1课题的研究意义..............................................................................11.2课题的主要研究内容.......................................................................11.3论文内容和结构安排.......................................................................2第二章聚类算法研究...............................................................................32.1聚类分析概述..................................................................................32.2主要聚类算法分类..........................................................................42.3聚类分析中的数据类型...................................................................62.4聚类算法的质量评价标准...............................................................92.5小结..............................................................................................10第三章基于层次的聚类算法的分析.......................................................113.1层次聚类方法概述.........................................................................113.2层次聚类方法存在的不足..............................................................13第四章基于层次聚类方法的实现...........................................................154.1CURE算法......................................................................................154.2BIRCH算法....................................................................................224.5小结..............................................................................................38第五章总结............................................................................................39致谢.........................................................................................................40参考文献..................................................................................................41基于层次的聚类算法的研究与实现第一章绪论1第一章绪论1.1课题的研究意义随着信息技术和数据库技术的迅猛发展，人们可以非常方便地存储和获取大量的数据。面对数据的日新月异，人们利用信息技术生产和搜集数据的能力大幅度提高，大量的数据库被用于科学研究、政府办公、商业管理和工程开发等等，以前的的数据分析工具（如管理系统）只能进行一些表层的处理（如统计、查询等），而不能获得数据之间存在的隐含的信息和内在的关联。为了摆脱“数据丰富，知识贫乏”和困境，人们迫切的需要一种能够自动地智能地把数据转换成有用信息和知识的工具和技术，这种对强有力的数据分析工具的迫切需要使得数据挖掘技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。聚类分析是根据一批样品的多个观测指标，找出能够试验样品或变量之间相似程度的统计量，并以此为依据，采用某种聚类算法，将所有样品或变量分别聚合到不同的类中，使同一类中的个体有较大的相似性，不同类中的个体差异较大。聚类分析是一种无监督的学习方法，它已经被广泛地应用于统计学、机器学、空间数据库、生物学以及市场营销等领域，聚类分析还可以作为独立的数据挖掘工具来了解数据分布，或者作为其他数据挖掘算法（如关联规则、分类等）的预处理步骤。聚类算法可以分为基于的层次方法、基于划分的方法、基于网格的方法、基于密度的方法和基于模型的方法[2]。聚类分析已经被广泛的研究了许多年，其中的层次聚类分析是聚类分析中极为重要的一个研究方向。它是由一系列的划分多步完成分类，而不是在一步以内将数据分成n类。层次聚类分为两种，分裂的（divisive）层次聚类和凝聚的（agglomerative）层次聚类。层次聚类算法由于要使用距离矩阵，所以它的时间和空间复杂性都很高，几乎不同在大数据集上使用，而且它在算法执行过程中，一量一个合并或分裂被执行，就不能修正。但是层次聚类算法没有使用准则函数，它所潜含的对数据结构的假设更少，所以它的通用性更强。为了将层次聚类算法应用在大规模的数据集上，许多研究者将采样技术，分块技术及数据压缩技术结合到层次算法中。典型的有：BIRCH、CURE、Chamelcon。1.2课题的主要研究内容本文主要研究层次聚类算法，在系统地归纳层次聚类分析方法的一般原理、一般方法以及相关技术的基础上，分析BIRCH、CURE等层次聚类算法，并对它们加以基于层次的聚类算法的研究与实现第一章绪论2实现并进行聚类分析。具体的来说，本论文所研究的主要内容如下：（1）分析和研究