聚类算法的研究综述Word格式.docx
- 文档编号:7120708
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:16
- 大小:96.37KB
聚类算法的研究综述Word格式.docx
《聚类算法的研究综述Word格式.docx》由会员分享,可在线阅读,更多相关《聚类算法的研究综述Word格式.docx(16页珍藏版)》请在冰点文库上搜索。
本人完全意识到本申明的法律后果由本人承担。
毕业设计(论文)作者签名:
日期:
年月日
毕业设计(论文)版权使用授权书
本毕业设计(论文)作者完全了解学院有关保留、使用毕业设计(论文)的规定,同意学校保留并向国家有关部门或机构送交设计(论文)的复印件和电子版,允许设计(论文)被查阅和借阅。
本人授权华东交通大学理工学院可以将本设计(论文)的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编毕业设计(论文)。
(保密的毕业设计(论文)在解密后适用本授权书)
指导教师签名:
签字日期:
年月日签字日期:
摘要
聚类算法的兴起,大大地改变了我们的生活和工作方式。
这是计算机科学的发展和相关学科发展的必然结果。
聚类算法作为数据挖掘中的一部分,我们不仅利用聚类算法进行我们的科研,而且我们的日常生活中聚类算法的应用也无处不在。
可以说和我们的生活息息相关。
目前这方面的专家也在致力于聚类算法的研究,在现有的聚类算法的基础上改进以及发掘出新的聚类算法。
因为没有什么是一成不变的,聚类算法也有缺点,因此必须不断改进和创新。
例如我们的学校、政府单位、企业都需要用到聚类算法和聚类分析,由于事物的相似性,利用这一方法,我们不仅可以将事物分类,最后得出他们之间的相似性,或者相异性,通过聚类得到我们需要的结果。
利用这些数据和资料我们可以更完美的进行我们的工作和研究。
本文结合一些文献,总结聚类算法的研究的目的、方法、成果和结论。
关键词:
互联网;
数据挖掘;
聚类算法;
算法应用;
算法发展趋势
Abstract
Theriseoftheclusteringalgorithm,greatlychangedthewayweliveandwork.Thisistheinevitableresultofthedevelopmentofcomputerscienceandrelateddisciplinesdevelopment.Wenotonlytakeadvantageofclusteringalgorithmtocarryoutourresearchandourdailylivesclusteringalgorithmapplicationseverywhere.Itcanbesaidthatourlives.Expertsinthisfieldarealsocommittedtotheresearchofclusteringalgorithm,toimproveanddiscovernewclusteringalgorithmonthebasisoftheexistingclusteringalgorithm.Becausenothingissetinstone,theclusteringalgorithmalsohasshortcomings,itisnecessarytocontinuousimprovementandinnovation.
Suchasourschools,governmentagencies,businessesneedtouseclusteringalgorithmandclusteringanalysis,duetothesimilarityofthings,theuseofamethod,notonlycanweclassifythings,theconclusionthatthesimilaritiesbetweenthem,ordissimilarities.Useofthesedataandinformationthatwecouldbemoreperfectforourworkandresearch.Inthispaper,someoftheliterature,thesummaryoftheclusteringalgorithmpurposeofthestudy,methods,resultsandconclusions.
Keywords:
Internet;
clusteringalgorithm;
algorithmisapplied;
algorithmtrends
摘要I
英文摘要II
目录III
引言1
1聚类算法的产生,现状及其发展意义和趋势2
1.1聚类算法的定义和研究聚类算法的意义2
1.1.1何谓聚类算法?
2
1.1.2研究聚类算法的意义2
1.2聚类算法的现状及其发展趋势2
1.2.1聚类算法的基本内容和现状2
1.2.2聚类算法的发展趋势3
2聚类算法的常见方法,常见算法之间的比较,聚类算法的学习
2.1聚类算法现今的常用算法和主要比较4
2.1.1常用聚类算法
(1)4
2.1.2常用聚类算法
(2)4
2.1.3几种聚类算法的优缺点5
2.2聚类算法实际应用的几个领域5
2.2.1聚类算法在商业中的应用5
2.2.2聚类算法在生物学中的应用6
2.2.3聚类算法在地理学中的应用6
3聚类算法的典型要求,聚类算法的特色和目标以及聚类的基本步骤
3.1聚类算法的典型要求和条件8
3.1.1数据集对聚类算法的要求8
3.1.2聚类过程简介9
3.1.3如何选择适当的聚类算法9
3.2聚类算法的特色与研究进度10
3.2.1聚类算法的主要目标10
3.2.2聚类算法的主要特色10
3.2.3聚类算法的研究进度10
3.3新发展的聚类算法11
3.3.1基于模糊的聚类算法和基于粒度的聚类算法11
3.3.2量子聚类和核聚类12
结论13
参考文献14
后记16
引言
由于受到古老分类学的影响,出现了数据挖掘中的聚类算法科学。
这一学科的准则就是围绕着各个类之间的相似性和相异性,找出之间的必然联系以及各自的优缺点。
数据挖掘中的聚类算法是如何帮助我们进行分类以及找出物理和抽象的东西之间的相同点和不同点,根本上帮助我们解决我们的很多问题。
本文会阐述聚类算法研究的意义以及目前聚类算法的现状,还有对聚类算法未来的展望。
以及科学家们所做的努力。
聚类分析的算法多种多样,各有各的差异,优缺点相对来说较为明显,本文会说明几种常见的聚类算法的概念以及它们的长短好坏意义方法。
这一门课题的跨学科性非常的大,我们不仅要学习本身的知识,还要对其他方面的知识有所掌握,这样才能对聚类算法有一个比较强的认识。
实际应用方面聚类算法的用处也是非常的大,本文会重点讲述聚类算法在商业,生物学和地理学中的应用,聚类算法是如何帮助科学家们解决各个领域的问题。
每一个学科都会有一个或者多个执行条件,聚类算法也不例外。
本文会讲述到聚类算法有哪些执行条件和典型要求。
聚类算法最突出的特点是什么,我们要抓住聚类算法的特色去研究学习这个课题。
聚类算法的进步是很快的,本文也会介绍一些新兴的聚类算法,相信通过所有学者的努力,聚类算法肯定有美好的未来。
1聚类算法的产生、现状及其发展意义和趋势
1.1聚类算法的定义和研究聚类算法的意义
聚类算法是数据挖掘中的一个分支,就是将物理或者抽象的东西进行分类比较,前提是基于各个类之间的相似性和相异性,更多的取决的是元素之间的相异性。
我们将我们要进行研究的任务数据集进行分析、计算、比较,最后得出我们需要的结果和数据。
这一课题的研究包括了数学、计算机学、统计学、经济学以及生物学。
1.1.2研究聚类算法的意义
首先我们根据聚类的定义,可以知道聚类的意义就是我们可以得出事物之间的关联。
不管这些事物是实体还是抽象对象,我们都可以了解他们本身的性质和相互之间的关联。
在我们的现实生活中,存在很多这样的例子。
例如古老的时候研究生物学,我们并没有现在的这么多先进的设备。
我们唯一可以依靠的就是比较生物之间的不同,这种不同可以是外形,习性等这些基本特征。
还有我们现在的商业中,就拿一个超市来做例子。
这个超市的消费群体主要是一些什么样的人,我们将所有的消费群体放在一起比较,可以很容易的得出一组数据。
显然,我们可以通过这些数据得出主要消费群体和次要消费群体,从而改进超市的经营策略,获得更大的盈利。
因此,聚类算法存在于我们的生活中以及我们的研究中,它深深的影响着我们的文明和人类的发展。
1.2聚类算法的现状及其发展趋势
1.2.1聚类算法的历史和现状
“物以类聚,人以群分”,在早期的分类学中,我们仅仅只是以一种比较的方法和专业知识来进行分析,一个类或者一个群之间的元素相似性。
这就是最早的统计分析。
但是这种统计分析方法往往是凭借着本身的经验和一些专业知识,并没有利用数学和计算机工具进行测试。
随着现在的社会对分类的要求越来越高,这种分析的结果已经无法满足我们的要求,确切的说是无法满足商业、科研以及生活的需求。
现如今的聚类算法已经多种多样,而且比较完善。
基本如今的聚类算法可以满足我们的要求。
不管我们从事什么样的活动或者工作一定能找到相对适用的聚类算法。
但是目前的聚类算法也不能说是完美的。
由于我们的生活节奏日益加快和我们对工作效率的绝对要求,某些聚类算法太过于复杂,计算工作量大,这并不适合我们。
我们的算法应该围绕这算法的简便性,算法的准确性,算法的实用性以及算法的后期结果可解释性来进行研究。
1.2.2聚类算法的发展趋势
从上文我们可以知道,如今的聚类算法已经无法满足我们快节奏的生活和工作。
这方面的学者和专家正在致力于研究和创新更简便更符合我们生活节奏的算法和分析方法。
其实这也是必然的,当初的windows95经过发展成了windows98,到如今的windowsXP和win8.不管是哪一个学科都是优胜劣汰。
近年来随着人工智能、机器学习、模式类别和数据挖掘等领域传统方法的不断发展和新方法及新技术的出现,聚类算法和聚类分析也得到了长足的发展。
目前常用的几类算法大致方向包括:
1.分类模式。
2.关联规则。
3.决策树。
4.序列模式。
5.聚类分析模式。
6.神经网络算法。
这些方法的优势相对于传统的算法可以适用于更多传统算法无法解决的问题。
而这些超强的新方法可以使我们解决很多瓶颈,使我们的工作研究得以继续进行。
在日新月异的今天,我们有理由可以相信科学家们通过不断的创新可以研发出更好的聚类算法。
2聚类算法的常见方法,常见算法的特性,聚类算法的学习
2.1聚类算法现今的常见算法简介
2.1.1常用聚类算法
(1)
1.层次方法:
层次发对给定的数据集进行层次似的分解。
按照层次分解的方式,层次法可分为分裂和凝聚两大类。
凝聚方法也就是为从下至上的方法,一开始将每个类分成单独的项,然后继续合并相似的项,直到所有的类都合并了,或大道某一个中指条件为止。
分裂方法是从上到下的方法,一开始将所有的项放在一个类中,然后进行迭代。
迭代的过程中,类被分裂为更小的类,知道只包含一个类,或达到某一个终止条件为止。
在层次法中,通常是用户定义的希望得到类的数目作为约束条件。
层次法中的代表算法有:
BIRCH、CURE、ROCK、CHAMEL。
2.划分法:
给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,KN。
而且这K个分组满足下列条件:
(1)每一个分组至少包含一个数据纪录;
(2)每一个数据纪录属于且仅属于一个分组(注意:
这个要求在某些模糊聚类算法中可以放宽);
对于给定的K,算法首先给出一个初始的分组方法,以后通过反复迭代的方法改变分组,使得每一次改进之后的分组方案都较前一次好,而所谓好的标准就是:
同一分组中的记录越近越好,而不同分组中的纪录越远越好。
使用这个基本思想的算法有:
K-MEANS算、K-MEDOIDS算法、CLARANS算法虫包括大部分无脊椎鱼包括鱼类、两栖类、爬行类等低级脊椎动物及鲸和虾、蟹、贝类等,鸟是鸟类;
兽是哺乳动物。
3聚类算法的典型要求,聚类算法的特色和目标以及聚类的基本步骤
3.1聚类算法的典型要求和条件
聚类算法的运行分析计算是需要很严格的条件的,不同数据集需要不同的算法来解决,算法的运行也需要假象模型,初始值等等条件。
由于数据集各种各样,很多数据集没有使用某一种聚类算法的条件,因此这个时候需要选择,选择对了好的算法,不仅可以使我们的工作更加简单,更重要的事可以让我们的计算结果更加准确,更符合实际的要求。
3.1.1数据集对聚类算法的要求
聚类算法的典型要求有:
1.可伸缩性:
许多聚类算法在小于两百甚至更低的小数据集合的情况下可以完成得很好。
但是一但数据集的规模过于庞大,包含了几万、几十万、几百万甚至几千万的数据。
则计算会导致很大的偏差,甚至无法完成计算。
因此,我们需要可伸缩性的聚类算法来帮助我们完成。
2.处理不同类型属性的能力:
有的数据集是数值类型,但有的就不是,比如说二元类型,分类类型,序数型数据等等,或者是这些类型的混搭。
因此只有能处理几个或者多数的类型数据集的算法才是合格的算法。
3.发现任意性状的聚类:
大多数的时候,数据集都是根据距离度量来确定聚类。
但是,像这样的基于度量的算法,碰上了球状簇或者任意性状的簇的时候,就很难确定最后的结论和结果。
4.用于决定输入参数的领域知识最小化:
当我们适用聚类算法在分析问题的时候,我们一定会选择一个参数。
但是由于后期产生的结果跟选择的参数关系非常大,选择的参数不合适可能会造成异常值,结果不稳定,不准确,影响判断。
而且对于用户来讲,没有选对一个好的参数可能会增加非常大的负担,造成运行过程非常艰难。
5.处理“噪声”的能力:
绝大多数的数据库或者数据集都包含有错误的信息或者孤立缺失的元素。
有一些算法对这类的问题非常的敏感,造成错误的判断,可能会因此造成结果的偏差。
6对于输入记录的顺序不敏感:
我们在进行聚类的运算时,可能几次运算会以数据集里面的数据以不同的顺序代入计算。
然而我们有时候会吃惊的发现,这些计算结果竟然会有惊人的偏差,非常影响我们的工作。
所以,聚类算法对记录顺序的不敏感也是非常重要的,也是先进算法一个很重要的一点。
7.高维度:
当代社会,越来越多的产业出现了三维四维等概念,也确实也落实到了我们的生活中。
但是目前仍然有一部分的聚类算法只能满足简单的平面数据集和二维数据集。
显然已经无法满足我们的要求了,这类算法有很大的局限性。
8.基于约束的聚类:
现在的城市,商业产品的复杂度和豪华程度已经今非昔比。
越来越多的新兴产业或者城市里高楼林立,公路错综复杂。
假如我们要选择开一间幼儿园在城市里,我们必须要考虑的因素有很多,比如交通问题,幼儿园离附近的住宅小区是否方便。
或者周边有没有相关的产业。
只有高性能的算法才能满足我们对现今聚类问题的研究。
9.可解释性和可用性:
这个可能就和我们买电子产品一样,我们希望我们买来的电子产品是很轻松的可以使用,并不需要复杂的说明和摸索,而且质量还要非常的好,确保不会出现什么问题。
聚类算法也是如此,我们希望我们的计算结果是可用的,可以解释得通的。
聚类算法中的一些特定的词义解释也必须与应用相联系,不然毫无意义。
3.1.2聚类的过程
聚类的主要过程:
1.特征的选择:
在聚类的过程中,应当选择与任务相关联的特征。
特征的最根本的目的就是使得信息多余减少以及最小化。
2.相似性的度量:
用于定量度量两个类之间的相似性和不相似性。
一个简单的度量如欧式定理就是来表示两个向量之间的不相似性。
3.聚类算法:
通过上文我们得知聚类算法并不是万能的,而数据集也多种多样。
我们需要一个符合我们要求的算法来完成我们的任务。
如图:
3.1.3如何选择适当的聚类算法
根据上面的介绍,我们可以知道聚类算法有很多的典型要求。
有的聚类算法只可以进行简便的运算,数据集一旦过于庞大,则无法运算。
有的聚类算法不能满足多维空间的运算,有的计算强度太高,有的受到本身或者外界的条件约束。
因此,当我们面对各种各样的聚类问题的时候必须选择一个正确的算法。
例如我们要对一个学生具体分类的时候,我们需要考虑的只是他们的成绩,年龄,班级这些因素,我们只需要用普通划分法和层次法就能进行此聚类的分析。
当我们需要短时间内完成一个聚类问题,而大多数的聚类算法比较复杂,不能满足我们的要求,我们应该适用基于网格的算法。
而当我们的数据集里面有孤立点或者有缺陷的时候,我们使用其他的算法也许不能进行此类运算,我们可以利用模型法来完成我们的工作。
总之,没有哪一种的方法适合于所有的聚类问题。
因为聚类算法的研究就是围绕着这一点展开的,我们在利用聚类算法完成我们工作的同时,我们也要不断的研究创新聚类算法。
因为我们自身,要研究的数据集以及聚类算法的本身的约束和局限性还是很大的,我们只有朝着这方面不断的去努力未来就有可能在我们的书本上出现更加先进更方便的聚类算法。
3.2聚类算法的特色与研究进度
3.2.1聚类算法与分类学的区别
通俗地讲,聚类算法是一种有导师的学习,事先并不知道可以分为哪些类。
将数据库中的一个数据集分为一系列有意义的子集。
但是有一个根本特征,就是同一个类中的个体之间的距离很小,而不同类之间的相差很大。
并且聚类的结果有多少是未知的,可以是10个也可以是100个,只是单纯的根本相似性将他们结合在一起,即使有的算法定义了类的数目,到后期也有可能是不准确的。
聚类的数据集要求比较多,都是成堆成堆的。
而分类则是将数据空中的一组对象,找出其共同属性,然后根据分类模型,将他们划分为不同的类别。
分类是首先建立一个模型,然后根据这个分类模型,把他们划分为不同的类别。
分类的根本要求就是首先建立分类模型。
分类的数据集比较小,当然,分类算法可以多可以少,只有越多的时候才能说明分类算法的优异。
3.2.2聚类算法的研究目标
研究目标是指从大量无序的数据中提取隐含的、有效的、可理解的、对决策有潜在价值的知识和规则。
为用户提供问题求解层次的决策支持能力。
针对不断改进各类算法的缺点,将其本身的优点进一步发挥出来。
例如K均值算法的特点就是运算简单,但是后期的异常值会造成偏差,造成数据结构的不稳定。
目前计算机学家正在进行不断的探索,研究开发新一类的聚类算法。
但是凡事都是有一个过程,我们并不能在规定的某一段时间或者靠着假象的概念就能完成这一类的工作。
阐述聚类算法基本原理,总结聚类算法的研究现状,按照聚类算法的分类,分析比较几种典型聚类的性能差异和各自存在的优点及问题,并结合应用需求指出了其今后的发展趋势。
3.2.3聚类算法的主要特色
主要特色是并不是最早的利用专业知识和经验来进行这方面的研究,而是融入了很多其他领域的方法。
上文中已经说道,例如统计学,数学等综合知识。
其实就现在而言,聚类算法已经不止运用到这些方法。
不同的算法可以加入不同的学科来进行研究。
例如,空间概念,数学建模,物理建模,计算机程序等等,都是我们研究聚类算法的帮手。
3.3新发展的聚类算法
3.3.1基于模糊的聚类算法和基于粒度的聚类算法
基于模糊的聚类算法:
传统的聚类分析是一种“硬”聚类的方法,隶属关系采用经典集合论中的要么属于要么不属于来表示,事物之间的界限有着截然不同的区别。
然而,现实生活中很多事物特征无法给出一个精确的描述,例如把人按身高分为“高个子的人”,“矮个子的人”,“不高不矮的人”。
然而,多高算高?
多矮算矮?
这样的分类判别是经典分类解决不了的问题。
模糊聚类分析方法为解决此类问题提供了有理的分析工具。
目前国内外对模糊聚类分析的研究非常重视,参与这个学科研究的国度遍布全球,研究人员与日俱增,模糊新产品不断问世,模糊技术不断应用到高精尖领域,基础理论研究与实际应用研究也取得了丰硕的成果。
模糊数学目前正沿着理论研究和应用研究两个方向迅速发展。
理论研究主要是经典数学概念的模糊化。
由于模糊集自身的层次结构,使得这种理论研究更加复杂,当然也因而更具吸引力。
目前已形成了模糊拓扑,使得这种理论研究更加复杂,当然也因而更具吸引力。
目前也形成了模糊拓扑、模糊代数、模糊分析、模糊测度及模糊计算机等模糊数学分支。
应用研究主要是对模糊性之内在的规律探讨,对模糊逻辑及模糊信息处理技术的研究。
模糊数学的应用范围及自然科学与社会科学的几乎所有的领域。
特别是在模糊的控制、模式识别、聚类分析、系统评价、数据库、系统决策、人工智能及信息处理等方面取得了显著的成就。
伴随着模糊聚类理论的形成、发展和深化,针对不同的应用,人们提出了很多模糊聚类算法,比较典型的有基于目标函数的模糊聚类方法、基于相似性关系和模糊关系的方法、基于模糊等价关系的传递闭包方法、基于模糊图论的最小支撑方法,以及记忆数据集的凸分解、动态规划和难以辨别关系等方法、其中最受欢迎的是基于目标函数的模糊聚类方法,该方法把聚类归结成一个带约束的非线性规划问题,通过优化求解的数据集的模糊划分和聚类。
该方法设计简单,解决问题的范围广,还可以转化为优化问题而借助经典数学的非
线性规划理论求解,并易于在计算机上实现。
因此,随着计算机的应用和发展,基于目标型算法的理论最为完善,应用最为广泛。
基于粒度的聚类算法:
从表面上看,聚类和分类有很大差异――聚类是无导师的学习,而分类是有导师的学习。
具体来说,聚类的目的是发现样本点指尖最本质的抱团性质的一种客观反应:
分类需要一个训练样本集,由领域专家指明,而分类的这种先验知识却长长是主管的。
如果从信息粒度的角度来看,就会发现聚类和分类的相同之处:
聚类操作实际上是一个统一粒度下进行计算的;
分类操作是在不同粒度下进行计算的。
粒度原理下,聚类和分析的相通使得很多分类的方法也可以用在聚类方法中。
作为一个新的研究方向,虽然目前粒度计算还不够成熟,尤其是对粒度计算语义的研究还相当少,但是相信随着粒度计算理论本身的不断完善和发展,在今后你念,它将在数据挖掘中的聚类算法及相关领域获得广泛应用。
3.3.2量子聚类和核聚类
量子聚类:
在现有的聚类算法中,聚类数目一般需要事先制定,如Kohenon自组织算法、K―MEANS算法和模糊K―MEANS聚类算法。
然而,在很多情况下类别数是不可知的,而且绝大多数聚类算法的结果都依赖于处置,即使类别数目保持不变,聚类的结果也可能相差很大。
量子聚类主要是受到物理学中量子概念的特性启发,可以用量子理论解决此类问题。
一个很好的例子就是基于相关点的Pott自旋和统计机理提出的量子聚类模型。
它把聚类问题看作一个物理系统。
并且
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 研究 综述