40近邻团聚类算法研究--聚类算法设计及实现(本科毕业设计)

XX理工学院本科毕业设计（2013届）毕业设计题目：K近邻团聚类算法研究—聚类算法设计及实现摘要：在对K近邻分类算法和聚类算法有了初步认识和掌握了K近邻与逆K近邻的相关定义说明的理论基础上，提出了K近邻团与极大K近邻团的概念。通过度量对象间的相似度，任意两个元素都互为K近邻和逆K近邻的对象集合构成一个K近邻团。对数据挖掘领域中的聚类算法进行分析，选择了一种基于K近邻团的聚类算法进行研究和解决特定问题。论文详细阐述了构建K近邻团的方法步骤和算法思想与代码实现，这些工作将为后续进行特定数据集信息挖掘提供理论支持和有益的参考，同时利用实验来验证此算法的有效性。关键字：K近邻；逆K近邻；K近邻团；聚类算法Abstract:IntheKnearestneighborclassificationalgorithmandclusteringalgorithmshaveapreliminaryunderstandingandmasteringtheK-nearestneighborandinverseK-nearestneighbordescribedtherelevantdefinitionsbasedonthetheoryputforwardtheK-groupwithgreatK-nearestneighborgroupconcept.Toconstructk-nearestclique,wemeasuringthesimilaritybetweenobjectsandcombinationalltheobjectswhichbek-nearestneighborsandreversedk-nearestneighborspairwise.Inthefieldofdataminingclusteringalgorithmtoanalyze,selectagroupbasedonKnearestneighborclusteringalgorithmtoconductresearchandsolvespecificproblems.PaperelaboratesbuildK-nearestneighbormethodstepsandalgorithmsgroupideasandcodeimplementation,theworkwillfollowforaparticulardatasetinformationminingtoprovidetheoreticalsupportandusefulreference,whiletakingadvantageofexperimentstoverifytheeffectivenessofthealgorithm.Keywords:KNN,RKNN,k-nearestclique,clustering目录1绪论..................................................11.1选题背景..................................................11.2课题研究的目的和意义......................................11.3论文的组织结构............................................22K近邻算法和聚类算法的介绍.............................43K近邻图、逆K近邻图、K近邻团和极大K近邻团............63.1K近邻图和逆K近邻图的定义.................................63.2K近邻团和极大K近邻团的定义...............................74K近邻团聚类算法.......................................84.1构造K近邻图，生成邻接矩阵................................84.2构造K近邻团无向图.......................................114.3挖掘极大K近邻团.........................................144.4算法的迭代...............................................174.5算法效率分析.............................................185实验与分析...........................................205.1实验数据集...............................................205.2实验结果.................................................205.2结果分析.................................................21参考文献...............................................2311绪论1.1选题背景数据挖掘（DataMing，DM），自上世纪50年代以来，这个人工智能的一个分支随着数据库的飞速发展的同时也取得了很大进展，是用数据库管理系统来存储关系相应的数据，用机器学习的方法来分析处理数据，这两个部分的有机结合来处理挖掘数据背景隐藏的、有价值的知识。其目的是为了更好的存储管理数据，有效地分析处理数据，挖掘有实用价值的数据支持，以便于更好地做出决策。数据挖掘是机器学习领域内广泛研究的知识领域，是将人工智能技术和数据库技术紧密结合，让计算机帮助人们从庞大的数据中只智能地、自动地抽取出有价值的知识模式，以满足人们不同应用的需要[1]。在分类算法中，K近邻算法是设计实现简单、分类处理效果较好的一种方法。由于它具有简单直观、易于实现和不必先检验统计数据等特点，使得它成为数据挖掘中很常用的分类算法。聚类算法，起源于分类学，但不等于分类。这两者之间的不同在于，聚类所要求划分的类是未知的。聚类分析在数据挖掘领域中处在很重要的地位，是把数据对象分组成多个类或者簇（Cluster），“物以类聚，人以群分”，所以在相同簇的数据对象之间存在较高的相似度，而在不同簇的数据对象之间的差别会比较大。这样，便可发现数据对象之间存在的某种联系，也就是这些优点使得聚类在数据挖掘、统计学和数据分析这些领域中占据着越来越重要的地位。本课题以聚类分析为基础，完成基于K近邻团的聚类算法的设计与实现。利用现有资源：向量集的矩阵标识程序，基于kd-tree的K近邻计算程序，极大团的枚举计算程序等，完成设计K近邻团聚类算法的后继程序，还要对给定数据集来测试算法的有效性。1.2课题研究的目的和意义聚类，将一个数据训练集按照要求来划分成若干个子集，根据不同子集中的数据对象具有不同的特性，所以可以很好很快捷地找出有需要的信息，但是它是2一种自动学习的方法，不会对学习样本集合做出类别识别，如果不提供学习监管，那么学习的模型不会很精确，得到的学习效果往往不满足人们的需求。传统的聚类分析计算方法从宏观上来看，以上的聚类分析计算方法可以划分为两类：从个体出发的聚类有CHAMELEON算法和DBSCAN算法，以及从整体出发的有CURE算法和K-MEANS算法。但是，从整体出发的聚类分析方法难以考虑到个体之间存在的特定的联系和差异，导致难以发现数据对象之间固有存在的联系。反而，从个体出发的聚类分析方法虽然能掌握数据对象之间的关联关系，在聚类过程中能够保持关联的有效性，但还是难以对整体的数据对象指定出具体的参数，对簇的大小和数量也无法确定。为了解决上述问题，优化聚类过程得到的效果，对此提出了一种基于K近邻的聚类算法，这也是本课题的重要研究工作。此算法的目的是为了更好地优化聚类学习的效果，使得能满足人们的需求，对给定的数据的分类更准确。因此，本课题需要在理解相关的定义概念之后，设计出K近邻团聚类算法，对给定数据进行实验，并验证算法的有效性。1.3论文的组织结构聚类分析(Clustering)是数据挖掘的主要任务之一，用于发现在数据库中未知的对象类。通过聚类过程形成的每个组称为一个簇(Cluster)。在数据挖掘之前，对象类划分的数据量与类型均是未知的，因此在数据挖掘后一般需要对数据挖掘结果进行合理的分析与解释。本课题以此为基础，完成基于K近邻团的聚类算法的设计与实现。现有资源：向量集的矩阵标识程序，基于kd-tree的K近邻计算程序，极大团的枚举计算程序。完成本课题则需要了解聚类技术及相关算法、在现有资源的基上完成设计K近邻团聚类算法的后继程序，还要对给定数据集来测试算法的有效性。本论文主要有6个部分组成。第1章主要描述了数据挖掘的发展背景、K近邻算法和聚类算法的一些简单3介绍和了解，介绍了本课题的选题背景和研究目的、意义，也简要地指出了本文的研究工作。第2章简要地介绍K近邻分类算法和聚类算法的基本定义和它分类的原理知识，简单提及分析K近邻算法的基本思想，了解聚类算法的应用领域和常用的聚类算法。分析聚类算法的缺点，想办法优化聚类结果，所以提出K近邻团聚类算法。第3章则简单地介绍本论文所要用到的一些基本定义。在了解了K近邻和聚类的基础上，提出K近邻图、逆K近邻图、K近邻有向图和极大K近邻团的定义，而这些定义将在K近邻团聚类算法的设计上使用到。第4章是本论文的研究重点，分析K近邻团聚类算法算法步骤，解释其关键代码的函数及其功能。之后便按照构建K近邻图，构造K近邻团无向图及逆K近邻团无向图，挖掘极大K近邻团等这几个步骤完成K近邻团聚类算法的设计和实现，之后对算法进行迭代和对它的时间复杂度进行分析计算。第5章按照上一张设计出的算法，用老师给定的样本来进行迭代计算，进而可以得到数据转换的结果，并且可以对算法进行验证。第6章是对本算法和本论文的总结，总结我在这次的毕业设计中所做的工作，和对完成的算法做结论。42K近邻算法和聚类算法的介绍K最近邻（K-NearestNeighborhood，KNN）分类算法，是一个理论上比较成熟的方法，同时也是最简单的机器学习算法之一。KNN最早是由科学家Cover和科学家Hart在1968年提出的，经过了40多年的发展和改进，其分类算法现在已比较成熟、有效，现已被广泛应用在数据挖掘、分类、回归和模式识别等各个领域。它基于传统的非参数的分类，是在统计的基础上的传统的模式识别算法。其算法思想为：在给定的一个需分类的样本训练集X中，找到K个已知类别标签的训练样本集合，使得它与样本X最相似或者最接近，之后便依据这K的值来确定该样本的类别。成熟的K近邻算法有以下的优点：该算法有好的健壮性，不会因为数据库中丢失数据或者在有缺陷的样本数据而影响算法结果有效性；对于大容量的训练样本或者大数据的数据库，算法还是有效的；还有，算法对于空间存储的使用和节约，只需存储训练样本即可。聚类是一种无监督的机器学习模式，是数据挖掘、机器学习以及模式识别领域重要的研究内容，在识别数据集的内在结构方面具有及其重要的地位。聚类算法通常在语音识别、图像处理、数据挖掘、生物学、心理学、考古学等诸多领域和学科中被广泛地应用[2]。传统的聚类分析计算方法主要有如下几种：划分方法(partitioningmethods)，层次方法(hierarchicalmethods)，基于密度的方法(density-basedmethods)，基于网格的方法(grid-basedmethods)和基于模型的方法(model-basedmethods)，也有传递闭包法，布尔矩阵法，直接聚类法，相关性分析聚类，基于统计的聚类方法等方法。从宏观上来看，以上的聚类分析计算方法可以划分为两类：从个体出发的聚类有CHAMELEON算法和DBSCAN算法，以及从整体出发的有CURE算法和K-MEANS算法。但是，从整体出发的聚类分