毕业论文网
本论文是一篇免费优秀的关于算法研究论文范文资料，可用于相关论文写作参考。
聚类分析与算法
王国祝
（河北省张家口市桥西区人防信息保障中心,河北 张家口 075000）
摘 要：聚类分析已经成为数据挖掘中的一项重要技术,是分析数据并从中发现有用信息的一种有效手段.伴随着计算机存储技术和计算能力的提升,仿生学、人工智能技术的进步,为聚类分析的发展创造了良好的条件,各种聚类分析算法层出不穷.因此基本的聚类的类型特征基础上,对基于这些类型且应用较为广泛的算法思想归纳总结,比较算法的优劣,指出存在的问题和不足,寄希望于从中得到一些启发,使聚类分析的方法有新的发展和发现.
关键词：数据挖掘；聚类分析；聚类方法
中图分类号：F23文献标识码：Adoi：10.19311/j.cnki.16723198.2017.22.051
1 引言
随着数据收集和数据存储技术的快速进步使得各组织机构可以积累海量数据,如何从大规模的数据存储中自动地发现有用信息,从而诞生了数据挖掘技术.数据挖掘技术不但发现未知数据库的应用模式,而且,通过数据挖掘还可以预测未来结果.聚类分析作为统计学的一个基本方法,已不断的发展为数据挖掘中的一项重要技术,成为从数据库中发现有用信息的一种有效手段.应用于生物学、社会学、医学、环境科学、信息检索、商业策划、图像处理等诸多领域.例如,生物学家从早期创建所有生物体的系统分类学,到如今使用聚类分析大量的遗传信息,发现具有类似功能的基因组；通过搜索引擎可以从数以亿计的Web页面中搜索到数百上千个具有共同性质或特征的网页；分析客户的购买数据或销售数据预测客户未来的需求,为商业策划提供决策依据.
聚类分析是从海量的数据中发现有用信息的过程,其本质是把不同类别或不同属性的数据区别开来,其核心的依据数据样本的特征不同,采用不同的方法即算法实现聚类,随着数字化的迅速发展,数据不论是数量还是类型都在不断的扩展,各种聚类分析算法也层出不穷,针对各种算法存在的缺陷和不足,新的改进算法和探索途径在不断产生.针对不同的数据对象,依据什么选择算法以及选择哪种算法,给应用者带来困惑.本文在阐述基本的聚类分析的类型特征的基础上,对基于这些类型且应用较为广泛的算法思想归纳总结,比较算法的优劣,指出存在的问题和不足,寄希望于从中得到一些启发,使聚类分析的方法有新的发展和发现.
2 聚类的基本类型
人类早先基于“物以类聚”的朴素思想,运用统计学的方法对事物进行分类,这就是最原始的聚类,比如物种的分类,就是从数据中发现所描述的对象及其关系的信息.聚类分析与分类不同,信息时代,聚类的含义已发生了深刻的变化,它是从海量数据库或数据对象中,去发现数据对象的相似或相异（不相似）,究竟有无相异的对象子集？这样的子集又有多少？这些事先都是未知的.也就是说,聚类分析所要发现的类及其类的数量都是未知的.
聚类分析发现知识和信息的过程分以下四个步骤：
(1)数据预处理,从数据库中选择与目标任务相关的数据集,或者具有某种特征的数据集,转换或规范成适合分析的数据.
(2)分析数据特征,判断聚类的类型,选择合适的聚类算法对数据集进行聚类,发现相似的或共同性质的类.
(3)验证和评价聚类结果,以确定对数据集的划分和评判所得结果是否是有效的、正确的.
(4)对结果进行解释,即分析和理解聚类结果,从中得到有用的信息.
数据集经过聚类分析划分成若干个子集,即分成不同的类或组,每个子集在聚类分析中通常称为一个簇.所有簇的集合称为聚类.依据簇的不同形态,存在不同类型特征的聚类.
2.1基于原型的聚类——划分聚类
仅当数据包含在相互远离的自然簇时,簇中每个对象到同簇中的其他对象的距离比到不同簇中任意对象的距离都近（或更加相似）.这种聚类称为基于原型的.其聚类的特征是簇相互之间是明显分离的,如图1（a）所示.通过划分可将数据集分割成三个相互独立的子集.
划分聚类也叫分割聚类.通过分割将数据划分为K组.典型算法有K-均值算法,Clara 算法和Clarans 算法.
2.2层次聚类
如果聚类是嵌套的,如图1（b）,并且允许簇具有子簇,则聚类组成一棵树,树中每一个节点（簇）都是其子女（子簇）的并,而树根就是包含所有对象的簇,这种聚类称为层次聚类.
如图2（a）所示,数据集为{a,b,c,d,e,f,g,h,k},如果按自上而下进行分解,称为分裂式层次聚类,第1步将数据集分解为{a,b,c,g,h,k} 和 {d,e,f}；第2步将 {a,b,c,g,h,k} 分解为 {a} 和 {b,c,g,h,k}；第3步将 {b,c,g,h,k} 分解为{b,c} 和 {g,h,k}；第4步将{d,e,f}分解为{d}和{e,f}；第5、6、7步分别将{e,f}、{b,c}、{g,h,k}分解为只有一个元素的叶子节点,算法结束.其结果如图2（b）所示,簇的形成自左到右的过程.反之,如果自下而上由单个元素逐步聚合成大类的过程,称为凝聚式层次聚类.如图2（b）中自右至左的聚类过程.代表的算法是 BIRCH算法,CURE算法等.
2.3基于密度聚类
簇是对象的稠密区域,或者,簇的分布是不规则或是重叠的,如图1（b）所示.这种情况下难以分割或分层,根据数据分布密度的不同,把相同或相近密度的数据分到一个簇中,从中可以发现数据的分布模式,或者不同密度之间的关联关系,从而发现有用信息.其特点是适合于发现不同形状的簇.代表算法有DBSCAN算法DENCLUE算法.
3 聚类分析算法
数据对象所拥有的簇不同,采取的聚类方法也不同.随着聚类分析技术的不断发展,各种聚类方法或算法改进应运而生.本文介绍划分聚类、层次聚类、基于密度的聚类的常用算法.
3.1划分聚类
3.1.1K均值聚类算法
K均值聚类算法是由 J. B. Mac Queen 于 1967 年提出来的一种基于划分的经典聚类算法.它是基于原型的聚类技术创建数据对象的单层划分.
算法的基本思想是：首先,选取K个初始质心（质心点到簇中其他数据之间欧式距离的平均值或是簇的中心点）,初始质心是随机选择的某个数据元素,其中K是用户指定的参数,即指定需要划分的簇的个数 K 值,对欧式空间中的点使用欧几里得距离度量数据对象的相似性,通过计算各个数据对象到 K 个初始质心的距离,按照最近邻原则将数据对象指派到距离它最近的质心所在的簇中,形成初次划分.然后,根据初始产生的簇更新每个簇的质心,重复指派和更新步骤,直到簇不发生变化,即等价于质心不发生变化或变化到达给定条件的阈值,终止算法.
3.1.2CLARA 聚类算法
算法的基本思想是：首先,从数据集随机选取一定数量的样本（一般设为40+2*k）, k为预设的聚类数目,从样本中选k个元素作为中心点,用PAM算法,在整个数据集中找到更具有代表性的元素替换现有中心点位置,得到目前为止具有代表性的中心点.再次随机选取样本,重复PAM算法过程.选择q次样本,进行q次迭代, CLARA算法最终从q个样本中得到最佳的聚类结果.
比较（1）和（2）,两者的共同点是K值都需要经验给出.两者的不同之处是, K均值算法适用于呈球形状的数据聚类,初始质心的随机选取影响聚类的结果,对离群点和噪声都敏感.CLARA算法是在随机选取样本的基础上聚类,所以适用于大数据量的聚类,通过样本不断更新中心对象,与初始质点没有关系,同时,也避免了噪声或离群点的干扰.
3.2分层聚类
3.2.1BIRCH算法
算法的基本思想是：BIRCH算法是把层次聚类过程看作是一棵树的分解或凝聚.第1步遍历整个数据集,按照事先确定的初始阈值,建立初始聚类特征树簇；第2步增加阈值,把满足条件的特征簇加入合并构成一颗新树即为凝聚,并用新的阈值所有结点是否满足阈值,大于阈值的结点进行删减即为分裂,分裂的结点合并到最邻近的特征树中.重复第2步,随着阈值的增大最终凝聚成一颗完整的树,得到层次聚类的结果.
3.2.2CURE 算法
算法的基本思想是：CURE 算法是介于均值聚类选取质心和CLARA聚类选择中心对象之间的策略.数据集的每个点看成是一个类,给定常数c,第1步将c个较为分散的点“收缩”成一个类,收缩因子为小于1的数,根据目标任务设置.第2步改变收缩因子,将最相似或相近的两个类再“收缩”；重复第2步,直到收缩因子为1时,所有对象都收缩成一点,完成分层聚类.CURE 算法是一种界于基于层次和基于划分的方法.CURE算法有效的解决了非球状类或相似性大小不均匀的类.
比较（1）和（2）都是通过逐步凝聚的过程聚类,适用于呈球形或相似度（或距离）变化较大的类；采用凝聚或收缩的方式,不容易受到噪声或离群点的影响.（1）通过遍历建立特征树,需要增加内存开销,对于大数据量的聚类,可通过选取样本的方式进行.（2）能够较好的解决呈非球类的聚类,过滤噪声或离群点.
3.3基于密度的聚类
3.3.1DBSCAN 算法
DBSCAN 算法是由Ester等人1996年在第二届关于知识发现和数据挖掘的国际会议的会议上提出的,关于大型空间数据库中发现集群的一种基于密度的算法.
算法的基本思想是：第1步根据目标距离设邻域为r的参数,邻域内的点标记为核心点,落在多个邻域的点标记为边界点,不属于任何邻域的点为噪声点.以此法将数据集表示的点都做标记；第2步删除噪声点；第3步将最相似（或最近）的核心点聚合成一个簇,与簇相关的边界点聚合到簇中；重复第3步直到得到聚类结果.
3.3.2DENCLUE算法
DENCLUE算法是由Hinneburg等人1998年在知识发现和数据挖掘的第四届ACM SIGKDD会议上提出的,解决多媒体数据库与噪声聚在一起的有效算法.
算法的基本思想是：构造一个影响函数,将数据集所表示的数据空间的整体密度模型化为所有数据点的影响函数的总和,将局部最大的密度点聚集在一起,最终得到聚类的结果.
比较（1）和（2）,两者对对噪声点不敏感.（1）只需要确定1个参数,相对容易；不适合处理高维数据和密度变化较大的数据；（2）中需要确定2个参数来构造影响函数,且参数选择比较困难,但（2）的方法适合高维数据的聚类和不同密度的数据.
4 结论
聚类分析技术是一项正在蓬勃发展的新型技术,基本理论还处在不断发展和完善过程中.为了适应不同数据类型的分析研究,经典算法也在不断得到改进以适应实际问题的需要.文章分析了划分聚类、层次聚类、基于密度的聚类的基本特征,并概括总结了这几种聚类分析算法的基本思想,比较了它们的优劣.聚类分析值得研究和解决的问题还很多,有待于进一步丰富聚类分析的理论方法和针对性的技术研究.
参考文献
［1］周世兵. 聚类分析中的最佳聚类数确定方法研究及应用［D］. 无锡： 江南大学, 2011.
［2］朱峰. 蚁群算法在聚类分析中的应用研究［D］. 西安：西北大学, 2009.
［3］陈志强,刘钊,张建辉. 聚类分析中PAM算法的分析与实现［J］. 计算机与现代化, 2003, (9): 1-3, 6.
［4］仝磊光,谢景新,高明亮. CLARA算法聚类蛋白质序列的实现［J］. 微计算机信息, 2010, (13): 231-233.
［5］蒋盛益,李霞. 一种改进的BIRCH聚类算法［J］. 计算机应用, 2009, (1): 293-296.
［6］王鸿遥,孙璐,游克思. 基于DENCLUE聚类算法的交通事故多发点鉴别方法［J］. 交通运输工程与信息学报, 2013, (2): 5-10.
算法研究论文范文结:
关于本文可作为相关专业算法研究论文写作研究的大学硕士与本科毕业论文算法研究论文开题报告范文和职称论文参考文献资料。