聚类算法综述(共9页).docx
《聚类算法综述(共9页).docx》由会员分享,可在线阅读,更多相关《聚类算法综述(共9页).docx(9页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上学术型硕士课程论文(或读书报告)课程名称: 科技论文写作 题 目: 数据挖掘中聚类算法的综述 题目类型(课程论文或读书报告): 课程论文 学 院: 计算机科学与工程学院 专业名称: 计算机科学与技术 姓 名: 王银 学 号: 任课教师: 潘地林 授课时间:2015年9月6日2015年11月7日提交时间: 2015年12月10日 专心-专注-专业数据挖掘中聚类算法的综述王银(安徽理工大学计算机科学与工程学院,安徽)摘要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。本综述按照聚类算法的分类,对每一类中具有代表性的算法进行介绍,分析和评价。最后从发现聚类形状、
2、所适用的数据库和输入数据顺序的敏感性等方面进行了算法推荐,以便对聚类算法作进一步的研究。关键词:数据挖掘;聚类分析;聚类算法Review of Clustering Algorithm in Data MiningAbstract:Clustering is an important technology in Data Mining to discovery data distribution and implicit model. the classification of clustering algorithms was proposed in this paper.Each clas
3、s has a representative algorithm is introduced,analysis and evaluation.In the end,it is suggested that the algorithm can be used to further study the clustering algorithm,which is based on the shape of the discovery,the database and the order of input data.Keywords:Data Mining;Clustering analysis;Cl
4、ustering Algorithm1 引言随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data Mining,DM)技术应运而生。所谓数据挖掘,就是从大量无序的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。典型的聚类过程主要包括数据准备、特征选择和特征提取、接近度计算、聚类(或分组)、对聚类结果进行有效性评估等7步骤。聚类过程:(1)
5、数据准备:包括特征标准化和降维。(2)特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中。(3)特征提取:通过对所选择的特征进行转换形成新的突出特征。(4)聚类(或分组):首先选择合适特征类型的某种距离函数或构造新的距离函数进行接近程度的度量,然后执行聚类或分组。(5)聚类结果评估:是指对聚类结果进行评估。评估主要有3种:外部有效性评估、内部有效性评估和相关性测试评估。2 聚类算法的分类聚类属于无监督学习,它是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理
6、对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。本文将聚类算法分为划分聚类算法、层次聚类算法、基于密度的聚类算法、基于网格的聚类算法以及基于模型的聚类算法。2.1 划分聚类算法给定一个包含n个样本的数据对象的数据集,构建数据的k个划分(kn),每个划分表示一个聚类。要满足每个类至少包含一个对象、每个对象属于且仅属于一个类这两个条件。创建一个划分的数目为k的初始划分,然后采用一种迭代的重定位技术,通过反复迭代来改进划分,直到满足一个最优的划分。一个好的划分的一般准则是:在同一类中的对象之间尽可能“相似”,不同类中的对象之间尽可能“相异”4。其代表算法有K-means、K
7、-medoids5、大型数据库划分方法(CLARANS)等。很多算法都是由这三个算法改进而来的,为了对大规模的数据集进行聚类,以及处理复杂形状的聚类,基于划分的方法需要进一步的扩展。2.2 层次的聚类算法层次法对给定的数据对象集合像树一样进行层次似的分解,形成一棵聚类树。按层次分解的形成方式自底向上还是自顶向下,层次法可分为凝聚和分裂两大类。凝聚的方法,也称为自底向上的方法,首先将每个对象作为单独的一个聚类,然后根据性质和规则相继地合并相近的类。直到所有的对象都合并为一个聚类中(层次的最上层),或者满足一定的终止条件为止。而分裂的方法,也称为自顶向下的方法,正好与凝聚法相反,首先将所有的对象都
8、看做是一个聚类,然后在每一步中,上层类被分裂为下层更小的类,直到每个类只包含一个单独的对象,或者也满足一个终止条件为止。分裂算法将生成与凝聚方法完全相同的类集,只是生成过程的次序完全相反 。层次的方法的缺陷在于,一旦一个步骤(合并或分裂)完成,它就不能被撤消。这个严格规定是有用的,由于不用担心组合数目的不同选择,计算代价会较小。代表算法有BIRCH,CURE等算法。2.3基于密度的聚类算法绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇,而在发现任意形状的簇上遇到了困难随之提出了基于密度的另一类聚类方法,其主要思想是:只要临近区域的密度(对象或数据点的数目)超过某个阈值,
9、就继续聚类。也就是说,对给定类中的每个数据点,在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪音”数据,发现任意形状的簇。DBSCAN是一个有代表性的基于密度的方法,它根据一个密度阈值来控制簇的增长。OPTICS 是另一个基于密度的方法,它为自动的,交互的聚类分析计算一个聚类顺序。2.4 基于网格的聚类算法基于网格的方法把对象空间量化为有限数目的单元,形成一个网格结构。所有的聚类操作都基于这个网格结构(即量化空间)上进行。这种算法的优点就是处理速度很快,并且其处理速度独立于数据对象的数目,只与量化空间中每一维的单元数目有关。缺点是只能发现边界是水平或垂直的聚类,而不能
10、检测到斜边界。此类算法也不适合维数较多的情况,因为维数的增加,网格单元会随之呈指数增加。常见的基于网格的代表算法有STING、CLIQUE、WAVE-CLUSTER等8。2.5 基于模型的聚类算法基于模型的聚类方法就是设法优化给定的数据和某些数学模型之间的适应性,找出数据对给定模型的最佳拟合。该算法通过构建反映数据点空间分布的密度函数来实现聚类。它也基于标准的统计数字自动决定聚类的数目。通过统计数字来分析噪声数据或孤立点,从而产生优化的聚类方法。基于模型的方法主要有两类:统计学方法和网络神经方法8。其中,统计学方法有COBWEB算法,网络神经方法有SOM算法。3 典型的聚类算法分析3.1 K-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 综述
限制150内