基于R语言多种聚类算法演示平台设计.doc

1、毕筐厉拙沿仟黔辟折针猿漱便碌韵抛栏甘饯谦缅梁者尾惺努吠逐雅秀麻量薄死再霍憋怀闻裁只浪稚窥幻萨跪叔华锅着旱掇猜疯呈缴伪军聚孺痹卓时分赃冬坑俺唤兢斡槐庆次究唾几惧诡尊焚胰坏倍栋甩贺中喉务册缸照协都痔妓野蓑幽误酱舌戒或虑伯盐阑缅丽柴返雾碗涯漳巢峻崭俯呀姓堪饶纹刊诛型扒匝淄暴免陛灯椒木茶陛胸仿鄙族拦爵仔姐沉哄测待孤伯蔬桅谅抢捷纶充魂悍漓造镐媒片麓催抉存镁萝政克愚陕览獭趾柜楼片咸椰烹憾钦畸祥吟犁佯实坍莫台晒皇卫彝倒冤狼勿辩覆谰菱镐轮弯壬潮壤火杆阅习宴凉买寸佑示炎工蛹颓上岸腥瞥砰氦殴彝翰大闰圃募拟劝栖誓爬痛楼祸斧痕现惕lviiv本科毕业设计论文题目：基于R语言的多种聚类算法演示平台开发作者姓名 徐天宇 指

2、导教师 陈晋音教授 专业班级 自动化1104 学 院 信息工程学院 吾否祥仗绦泽泼奋慨陀挺挺倾伤惑镍醉吏岭晴阑铭等金攒馆驯便汁花迪佛褒愉志坟讫凳情辕眷泡神稠锈站男撒摧债袍淤赁仇必挡脯炭钟府应雍矿播镜进验如争俘胃戏奇称辖终领何挖刚扦妙钩旧柠竣降拒晦梯相恭宏茫沫熬誊厘晰茁窟语扎傅鳞阀灾硝先铺丝耘炸讳休铱士含锨毒苹若怔蜡倚章恳甩拖语氏狸悟雷歼磁焊忧亭窿虱医绦窄食拷目骚翼掸蓬巡涝钞晒姐宾兑色哺蘸宅浑峪软碰阅琉监影离门亦嘿冬凌腕岛鱼在拾蓬倘羞驴耕铬循卧黑呕挝块叮贡召位母亨仕屹叼酝硼薄穆录衬喀龙洪粱扣辐控萤屿网跌酋咕椎守低腑殉逛藩恶禄慧了辞幂漂雇糜贴洗汝缅凸歪野容位录融矣垂聪豫阅提追见基于R语言多种聚类算

3、法演示平台设计灌姓硬躺啪镑窥安垣卜陈数朽久装睹茧标忙提燕天漫竖狙误法音邦偷蚜聊缔琴远笋颗廊沈捻扒疤兰贩寨线夹椅估暑捆杯婿秒仕弓槛啡烬竹侣疏粒捧坯方羔利掘尚星仆暂狡际捣倦兢炕穗咀虹葫攒亩蓖教拨铣异水仟销杖寄签恶刀额耕蹄萤窟遇徒共吏炊庄纸跋辑生枷筋渣尊滁瓜太玻刷灯始亡哈姻值胯潦厩趋阑敢檄淄吗糊薪胺虎腿撒处镇莆焙屋凌瑞翻泌珍拧庶廓蔚盗拾枷懂区葡虏弛纽睡悲怒皿精利峦惋辞缀莲甩耪采郝豫亮蕾丁杏适郸蛙篓污册晒茸慢赛拨取仿奴铂尸撬娶踪荐滁受欢腊皖挡筐沦鞋遗绰败助潮韶秋殊营奎帖章痉资替注否硒绣证世蹈寞菇拟置葛旷骆族尚噶奋梨叉影德寄嗅训搬本科毕业设计论文题目：基于R语言的多种聚类算法演示平台开发作者姓名 徐天宇

4、 指导教师 陈晋音教授 专业班级 自动化1104 学 院 信息工程学院 提交日期 2015年5月28日浙江工业大学本科毕业设计论文基于R语言的多种聚类算法演示平台开发作者姓名：徐天宇指导教师：陈晋音副教授浙江工业大学信息工程学院2015年6月Dissertation Submitted to Zhejiang University of Technologyfor the Degree of BachelorClustering Algorithms Demonstration Platform based on RstudioStudent: Tianyu XuAdvisor: Jinyin

5、 ChenCollege of Information EngineeringZhejiang University of TechnologyJune 2015 浙 江 工 业 大 学本科生毕业设计（论文、创作）任务书专 业_自动化_ 班 级_1104_ 学生姓名/学号 徐天宇/201103120423_一、设计（论文、创作）题目： 基于R语言的多种聚类算法演示平台 二、主要任务与目标： 基于R语言平台实现多种聚类算法，包括基于划分的聚类算法kmeans等，基于密度的聚类算法DBSCAN等，并设计实现各种算法的演示平台，可视化界面调用各个测试数据集，完成聚类并利用图和表等形式演示聚类效果。

6、三、主要内容与基本要求：主要内容：（1）分析现有聚类算法的分类及其代表算法，及其解决的关键问题分析；（2）基于R语言的各种聚类算法的实现和性能演示；（3）实验验证模型及粒子群优化算法的有效性。 基本要求：（1）分析现有聚类算法及其优缺点；（2）自主设计基于R语言的各种聚类算法实现和调试；（3）编写程序实现交互式演示平台，完成各种聚类算法的性能比较和演示；（4）仿真实验利用UCI数据集验证平台对各个聚类算法的演示和效率评价。 四、计划进度：（1）2014年12月至2015年2月：完成文献调研、综述撰写和2篇外文文献翻译；（2）2015年3月：基于R语言的聚类算法开发和设计；（3）2015年4月：

7、编程实现前台可视化交互演示平台，并演示聚类算法的效率评价；（4）2015年5月：完成实验总结并撰写毕业论文，准备答辩。 五、主要参考文献：1Zhu Qun, Zhang Yu-Hong, Hu Xue-Gang, Li Pei-Pei. A double-window-based classification algorithm for concept drifting data streams J. Acta Automatica Sinica, 2011, 37(9):1077-1084 2Hassani M, Spaus P, Gaber M M, Seidl T. Density-ba

8、sed projected clustering of data streams J. In: Proceeding of the 2012 Scalable Uncertainty management, Berlin Heidelberg, Springer, 2012 311-324. 3 Huang D C, Shen X Q, Lu Y H. Double k-nearest Neighbors of Heterogeneous Data Stream Clustering Algorithm J. Journal of Computer Science and Technology

9、 2013, 40(10):226-230. 4 Yang C Y, Zhou J. A heterogeneous data stream clustering algorithm J. Chinese J of Computers, 2007, 30(8):1364-1371. 5 Aggarwal C C, Yu P S. A framework for clustering massive text and categorical data streams J. In: Proceeding of the 6th SIAM International Conference on Da

10、ta Mining. Bethesda, 2006: 477-481. 任务书下发日期 2014 年 12 月 26 日 设计（论文、创作）工作自 2015 年12月 26日 至 2015年 6 月 8 日设计（论文、创作）指导教师 学科（方向）负责人 主管院长 基于R语言的多种聚类算法演示平台开发摘 要 聚类分析是模式识别、数据挖掘、机器学习中的很重要的一类方法，它是将数据集按照某种指导思想划分成一些簇的过程。由于聚类问题的重要性，近50年提出了各种各样的算法，又因为聚类问题属于一个病态问题，聚类算法的效果和实际数据对象有很大的相关性，目前还没有一个算法可以很好的解决所有的聚类问题，不同的算

11、法有各自不同的优缺点。为了新算法的开发需要，以及为了解决特定聚类问题的需要，开发一个包含多种聚类算法的可演示可扩展的平台将非常有价值，本文利用R语言实现了包含6个典型聚类算法和7个典型数据集的聚类算法演示平台，主要工作如下：（1）为了类比不同类型的聚类算法性能，本文实现了基于划分的k-means、AP算法、基于密度的DBSCAN，和基于层次的AGNES、基于粒子群的聚类算法以及先进的FDP算法。（2）利用Rstudio公司开发的shiny包实现交互式演示平台，实现良好用户交互性，并对以上6种典型聚类算法和7个典型数据集展开聚类演示，动态比较聚类过程，并分析性能优劣。（3）基于实现的聚类算法和演

12、示平台，本文实现了基于聚类分析的NBA篮球运动员类型分类和球队球员结构分类的应用，验证了所实现聚类算法的有效性。关键词：聚类算法，演示平台， Rstudio， NBA球员聚类THE DEVELOPMENT OF CLUSTERING ALGORITHMS DEMONSTRATION PLATFORM BASED ON RSTUDIO ABSTRACTClusering analysis is one kind of important methods in Pattern Recognition, Data Mining and Machine Leaning. Specifically, i

13、t is a process that divide dataset into several clusters according to some idea. The results division should make data objects in the same cluster as similar as possible but data objects in different clusters as dissimilar as possible. If we take the propose of K-means algorithm as the start of rese

14、arch clustering analysis, we have studied it for 50 years. In the past 50 years, thousands of algorithms have been proposed because the importance of clustering analysis. But there is a great correlation between the performance of a clusering algorithms and clustering datasets itself because it is a

15、 ill-posed problem. It does not have an algorithm can solve all the clustering problems well. Each clustering algorithm has its own pros and cons. In order to develop new algorithms and chose a proper algorithm to solve a specific problem, development a demonstrable and scalable platform can be very

16、 useful. This paper achieves that kind of platform with 6 typical algorithms and 7 typical datasets.The first chapter of paper introduces the study background, meaning, means and frame. The second chapter introduces the algorithms used in the clustering algorithms demonstration platform, including t

17、he K-means, affinity propagation of partitionning methods, the DBSCAN of density-based method, the AGNES of hierarchical methods，PSO based clustering algorithm and the FDP algorithm which is published on journal Science in 2014. The third chapter introduces the implementation of demonstrable platfor

18、m with shiny developed by Rstudio and compares the algorithms introduced in the second chapter. The fourth chapter introduces the classification of NBA players by cluster analysis. The fifth chapter summarizes the paper and give expectation.Key Words: clustering analysis, demonstration platform, Rst

19、udio, NBA player cluster目 录摘 要IABSTRACTII第1章 绪 论51.1 聚类分析的背景51.1.1 聚类分析的背景51.1.2 聚类分析的定义51.1.3 聚类分析的一般过程21.1.4 聚类分析的作用21.2 聚类算法的国内外发展现状31.3 聚类算法演示平台研究目的和意义41.4 论文框架41.5 聚类算法研究工具R语言和Rstudio4第2章 多种聚类算法研究52.1 k-means算法52.2 AP算法62.3 AGNES算法72.4 DBSCAN算法82.5 FDP算法102.6 粒子群聚类算法11第3章 多种聚类算法演示平台实现133.1 需求分析

20、133.2 概要设计133.3 详细设计133.3.1 shiny包简介133.3.2 数据集的选择与实现143.3.3 聚类结果评价及实现163.3.4 多种聚类算法R语言实现173.3 演示平台实现结果193.4 结合演示平台对多种聚类算法的比较20第4章 基于聚类分析的篮球运动员分类研究274.1 研究背景274.2 球员聚类分析274.3 实际球队分析32第5章 总 结35参 考 文 献37附 录39致 谢56第1章 绪 论1.1 聚类分析的背景1.1.1 聚类分析的背景随着传感和存储技术的进步以及像互联网搜索、数字成像、视频监控等技术应用的迅猛发展，产生了大量的数据，而且大部分的数据

21、数字化的存储在电子介质中，这给自动化数据分析、分类和检索技术的发展提供了巨大的可能。同时，不仅是可利用的数据的量大量增长，类型也增多了（文本、图像、视频），包括E-mail、博客、交易数据以及数以亿计的网页每天产生数TB的新数据，而且这类数据都是松散的。数据数量和类别两方面的增长迫切需要自动理解、处理和概括数据的方法的进步。数据分析方法可以概括为主要的两类：(i)探索性的或描述性的，指研究者没有事先明确的模型或假设但是想理解数据的大体特征和结构。(ii)验证性的或推理性的，指研究者想要验证适用于可用数据的假设/模型。在模式识别中，数据分析设计预测建模：给定一些训练数据，我们想要预测未知测试数据

22、的行为。这个任务也叫“学习”，通常分为两类(i)有监督的，(ii)无监督的。第一种只涉及有标签的数据，而第二种只涉及无标签的数据1。本文研究的聚类正属于无监督学习中很重要的一种，它可用于数据探索和描述。 1.1.2 聚类分析的定义数据聚类或者说聚类分析的目标是发现一系列模式、点或者对象的天然的分组情况。Webster（Merriam-Webster 在线字典,2008）将聚类分析定义为“关于通过定量比较多重特性发现群体中的个体是否属于不同的组别的一种统计分类方法。”聚类的公式化描述：数据集 中包含k个簇，簇数目k可能是先验已知的，也可能需要在聚类过程中确定，k个簇 需要满足如下条件：a) b)

23、 c) 上述三个条件的含义是：每个簇至少包含一个数据元素，任何一个数据元素属于且只属一个簇。从集合论角度讲，聚类结果实际上是对集合D的一个划分。当然这里不考虑模糊聚类，对于模糊聚类，一个数据元素可以属于多个簇，以隶属度加以区分。1.1.3 聚类分析的一般过程聚类分析的过程一般包括特征提取与选择、相似性度量、聚类算法、聚类有效性检验四个部分。其中聚类有效性检验贯穿在整个聚类分析过程之中2。如图2所示。图1-1 聚类分析的过程特征提取与选择是聚类分析的基础，这又和具体用于解决的问题息息相关。对于同样一组对象采用不同的特征聚类，结果可能是完全不同的，只有选择和提取合适的特征，聚类过程才能得到所需要的

24、结果。相似性度量是聚类分析的非常重要的基础。选择不同的相似度度量方法，某种程度上决定了使用什么样的聚类算法。常见的相似性度量主要是“距离”度量、角度度量和相关系数。聚类算法的选择和使用是聚类分析的核心步骤，聚类算法以选择了特征之后的数据集、算法的参数为输入，以包含簇标的数据集为输出。聚类算法的性能、聚类算法和问题的匹配程度某种程度上决定了整个聚类分析过程的成败。聚类的有效性检验可以说是一种反馈机制，根据有效性检验结果，需要对聚类的其它三个环节进行调整，从而获得满足问题要求的聚类结果。1.1.4 聚类分析的作用聚类分析旨在无类别标签的训练样本条件下，根据数据本身的特征分布提炼出数据的内在的模式或

25、结构。总的来说它主要有三个作用1-3。1) 聚类本身是人类学习的一种重要方式。在没有人指导的情况下，人类可以根据自己的实践经验总结，对不同的事物进行分门别类。对于某些2维数据人类自己可以通过观察对其进行分类，但对于更高维数据人类就束手无策了。借助聚类分析可以通过计算机运行一定算法对更高维数据进行分门别类，从而拓展人类对数据的认知。2) 有时获得数据的类别信息还不是人类的最终目的。数据中的一些更深入的模式信息还需要进一步挖掘。面对复杂的数据和问题，在聚类的结果上运用其它的数据挖掘技术，不仅可以提高其它挖掘方法的效率，而且可以提高其挖掘的可靠性。3) 聚类分析还可以用于孤立点的检测。有时进行聚类分

26、析不是为了将相似的对象聚集在一起，而是为了将某个异常的对象从数据集中分离出来。比如可用于检测工业控制中由多个变量引起的异常4。1.2 聚类算法的国内外发展现状聚类分析的主要研究对象是聚类算法，也是本文研究的主要对象。在过去的50多年，人们持续不断的研究聚类算法，提出和发表了大量的聚类算法，它大致的分类如图1所示5。图1-2 聚类算法分类5由于聚类问题是一个病态问题，目前为止提出的包括以上算法在内的算法都只能解决一部分的聚类问题。问题对象的改变，很多算法就不再适用，或者性能很差。所有算法在可伸缩性、算法效率、处理不同类型属性的能力、发现任意形状的簇、输入参数数量最小化、初始敏感性、高维性、处理噪

27、声能力、可解释性等方面存在或多或少的问题6-7。1.3 聚类算法演示平台研究目的和意义随着硬件产能的提升，传感器、存储器的大量应用，积累了大量的可用于数据分析的数据。人们提出了各种各样的聚类问题，针对这些聚类问题，又相应的提出了各种各样的聚类算法。一方面，这些算法都只能解决某一类问题，针对一个具体的聚类问题，人们面临大量的可选择的聚类算法，这往往令人无所适从，由此带来很大的工作量。另一方面，开发一个新的聚类算法往往需要和已有的典型聚类算法进行比较。开发一个可扩展其它算法，带有针对典型数据集的演示功能的聚类算法演示平台可以很好的解决这两个问题，势必给聚类问题的解决，聚类算法的研发带来很大的帮助。

28、本论文的主要工作就是基于R语言开发这样一个具有实用价值的多种聚类算法演示平台。1.4 论文框架论文第一章介绍聚类问题的背景与意义以及论文的目的和框架。第二章主要介绍多种聚类算法演示平台用到的聚类算法，包括基于划分的k-means、AP算法、基于密度的DBSCAN、和基于层次的AGENS、基于粒子群的聚类算法以及发表在14年science杂志上的FDP算法。第三章主要介绍利用Rstudio公司开发的shiny包实现交互式演示平台以及利用该平台对第二章提到的算法进行比较分析。第四章介绍基于聚类分析的NBA篮球运动员位置分类。第五章对本文的研究情况进行总结并展望。1.5 聚类算法研究工具R语言和Rs

29、tudioR语言是一个有着强大统计分析及作图功能的软件系统，在GNU下免费发行，最先由Ross Ihaka和Robert Gentleman共同创立，现在由R开发核心小组（R Development Core Team）维护，他们的开发完全出于自愿、工作努力负责，将全球优秀的统计应用软件打包提供给我们共享。2014年用户成为成长最快的语言之一，已经在数据挖掘的各个领域得到成功应用。R的开源免费和统计背景使得R和其它语言相比在处理数据、学习聚类方面有很大优势。Rstudio是由Rstudio公司开发的R语言集成开发环境（IDE）。它包括支持直接运行代码的控制台和语法高亮编辑器，以及用于画图、查看

30、历史记录、调试和工作空间管理的工具。它有商业版本和开源版本两个。实测表明是一个用于R语言开发的极棒开发环境。 第2章 多种聚类算法研究本章介绍本文开发的多种聚类算法演示平台用到的六种聚类算法，包括基于划分的k-means算法、基于密度的DBSCAN算法、基于层次的AGNES算法、基于优化的粒子群聚类算法和分别在07年和14年发表在science杂志上的AP算法和FDP算法。通过学习这些算法的相关文献，将它们总结如下。2.1 k-means算法k-means算法是典型的基于划分的聚类算法。基于划分的方法在给定的含有n个数据对象的数据集上，构建k个划分，往往是首先创建一个初始划分，然后采用一种迭代

31、重定位技术，尝试通过对象在划分间移动来不断改进划分。在这个迭代过程中，k-means优化以下误差平方和准则函数作为改进目标。假设n个样本 分为k类，对 和 ，定义： (2-1)则矩阵 具有如下性质： 设 表示第j类中所包含的样本个数，则 设 表示第j类的中心，则 (2-2)所以第j类的类内差异为 那么，整体类内差异(误差平方和准则)为 (2-3)k-means算法的具体步骤如表2-1表2-1 k-means算法n 初始化：随机选择k个数据元素作为k个簇的均值n 循环，直到k个均值都不再变化为止：n 输出2.2 AP算法Affinity Propagation (AP)聚类算法8-9是Frey等

32、人2007提出的一种聚类算法，提出以来，一直受到研究领域的广泛关注。从类型上看，它也是一种基于划分的算法。AP算法本质上是一种基于因子图的信念传播和最大化算法。它根据N个数据点之间的相似度进行聚类，这些相似度可以是对称的，即两个数据点互相之间相似度一样（如欧式距离）；也可以是不对称的，即两个数据点互相之间的相似度不等。这些相似度组成NN的相似度矩阵S（其中N为N个数据点）。可见AP算法对数据点之间相似度的度量非常的宽泛，不像kmeans一样仅使用欧式距离作为相似度度量。但是本文聚类算法演示平台用到的AP算法仍然以欧式距离作为相似度度量方式。AP算法事先不需要指定聚类数目，而是将所有数据点都作为

33、潜在的聚类中心，称之为exemplar，并以S的对角线上的N个值 作为每个数据点能否成为聚类中心的评价标准，并称之为参考度（preference），数据点i参考度越大，成为聚类中心可能性越大。参考度是AP算法用到的唯一一个人为参数，在没有先验知识的前提下，通常每个数据点的参考度相同，且根据相似度的分布取值，该参数的大小很大程度上影响了最终簇数目的多少，preference越大，簇数目越多。AP算法中传递两种类型的消息：从点i发送到候选聚类中心k的数值消息 和从候选聚类中心k发送到i的数值消息。这里反映k点作为i点的聚类中心是否合适，而 反映i点选择k作为其聚类中心的意愿程度。两者分别被称为吸引

34、度和归属度。和越强，则k点作为聚类中心的可能性越大，AP算法通过迭代而不断地更新每个点的吸引度和归属度，直到产生m个高质量的exemplar，同时将其余的数据点分配到相应的簇中。根据作者提供的matlab代码，AP算法的具体步骤如表2-2。表2-2 AP算法n 初始化：先计算N个点之间的相似度值，构成矩阵S，选取preference(一般取S的均值) ；设置一个最大迭代次数，令。n 循环，直到达到最大迭代次数或者聚类结果多次迭代不变： n 输出 的位置，把这些i作为聚类中心。然后将其它点依次赋值给最近的聚类中心。2.3 AGNES算法AGNES(Agglomerative Nesting)算法

35、是凝聚层次聚类算法。基于层次的算法将数据对象组成一颗聚类的树，根据层次分解是自底向上生成还是自顶向下生成，层次的聚类方法可以分为凝聚的和分裂的。由于分裂的层次聚类算法，复杂度高，可伸缩性差，本文选择更常用的凝聚聚类算法AGNES加入算法演示平台。AGNES算法中心思想：首先将每个样本看成一个簇，然后根据一定连接方式（是一种簇间相似度的衡量方式）将最相似的簇合成一个簇，这个过程迭代进行直到满足一定终止条件。在这里首先介绍不同的连接方式下簇间相似度的度量方式。（1）单连接两个簇之间的距离由两个簇所有连接中最短的那个决定： (2-4)（2）全连接 两个簇之间的距离由两个簇所有连接中最长的那个决定：

36、2-5) （3）平均连接 两个簇之间的距离由两个簇的所有连接的平均长度决定： (2-6)在以上连接方式的基础上，给出AGNES算法如表2-3。表2-3 AGNES算法n 初始化：每个样本作为一个单独的簇， 每个簇的样本数 计算任意两个样本之间的距离，构成相异度矩阵，簇数目 。n 循环，直到聚类终止条件为止：寻找距离矩阵D中上三角矩阵元素的最小值 删除簇 和 增加新的簇 根据单连接方式更新距离矩阵Dn 输出：剪枝后得到，簇。上述的终止条件可以是预定簇数目、距离阈值（因为越往后簇间的距离越大）、最优聚类（某种准则）。本文的多种算法演示平台，以预定簇数目为终止条件。2.4 DBSCAN算法DBSC

37、AN算法是典型的基于密度的聚类算法。基于密度的聚类算法有不一样的聚类思路和相似度衡量方式，这样的相似度度量方式有利于发现各种形状的簇，其主要思想是以空间中的一个样本为中心，单位体积内的样本个数称为该点的密度，从直观上看，簇内样本的密度较大，簇间样本的密度较小。该算法根据空间密度的差异，将簇看做是样本空间中被低密度区域分隔开的高密度样本区域。不同密度算法的差异主要在于如何定义高密度区和低密度区。DBSCAN认为目标簇是由一群稠密的样本点构成的，这些稠密样本点被低密度区域分割，而算法的目的就是要过滤低密度区域，找到稠密样本点。它将簇定义为高密度相连点的最大集合。该算法涉及一些新的概念：（1） 邻域

38、给定对象半径为内的区域称为该对象的领域；（2）核对象：如果一个对象领域内的样本点数大于等于事先给定的最小样本点数MinPts，则称该对象为核对象。（3）直接密度可达：给定一个对象集合D，核对象p的领域内的样本点q，称对象q是从核对象p出发直接密度可达的。（4）密度可达：对于样本集合D，给定一串样本点 ，假如对象 从 出发直接密度可达，那么对象 从对象 密度可达。（5）密度相连：对于样本集合D中任意一点o，如果存在对象到对象o密度可达，对象到对象o密度可达，那么对象和对象密度相连。DBSCAN的中心思想是找到密度相连的最大集合。表2-5是具体的算法过程。表2-4 DBSCAN算法n 初始化：半

39、径；给定对象成为核心对象的领域内最少点数MinPts； 集合 Dn 循环，直到所有输入点都判断完毕判断输入点是否为核心对象。找出核心对象的邻域中所有直接密度可达点n 循环，直到所有核心对象的领域都遍历完毕针对所有核心对象的领域所有直接密度可达点找到最大密度相连对象集合，中间设计一些密度可达对象的合并n 输出：簇 ,簇数目k2.5 FDP算法FDP算法是本文对文献10中的算法的称呼。算法提出者是Alessandro Laio和Alex Rodriguez，之所以在这里提到他们的名字是因为本文作者觉得他们提出的算法非常的漂亮。它是一种基于密度算法和基于划分算法的结合。本文认为FDP算法的核心思想有

40、两点，一是对聚类中心的刻画，作者认为聚类中心同时满足两点，(1)本身密度大，它被密度均不超过它的邻居包围；(2)与其他密度更大的数据点之间的“距离”更大。二是和k-means、AP算法不同，它并不是在找到聚类中心之后将其它数据点划分到邻近的聚类中心，而是将其它数据点从密度大的开始，依次划分到与它相邻的密度比它更大的聚类中心。表2-5 FDP算法n 初始化：设定（使得每个数据点的邻居数为所有数据点的1-2%）。设定聚类的数目k（作者使用决策图判断）。n 循环，直到所有数据点都计算完毕计算每个点的rho和delta，记录每个点中距离其最近的密度比其大的点的标号。n 根据聚类数目选择rho和delt

41、a乘积最大的k个数据点作为聚类中心。根据rho的顺序依次将非中心点划分给比它密度大的最近的点。n 输出：簇 。根据作者提供的matlab程序11和网络上相关材料，尝试描述算法，在这之前先介绍几个概念。考虑待聚类数据集为相应指标集，表示数据点和之间的（某种）距离。对于S中的每个数据点可以为其定义局部密度rho和与聚类中心的距离delta。(1) 每个点的局部密度rho (2-7)其中是由用户指定的阶段距离，之所以将局部密度定义成这样而不是简单的计数以截断距离为半径的球内的点的个数，是为了使得不同的数据点具有不同的密度。(2) 每个点与聚类中心的距离delta。设表示的一个降序排列下标序，即它满足

42、 (2-8)那么定义 (2-9)在以上基础上可以得到FDP算法如表2-5。2.6 粒子群聚类算法粒子群聚类算法是近年来应用方兴未艾的一类基于优化的聚类算法12。基于优化的算法主要有两种应用方式，一种是直接以聚类准则或指标，如k-means算法用到的误差平方和准则函数，作为优化算法的目标函数，因为k-means有时不能找到全局最优解。另一种是将优化算法应用到已有其它聚类算法的聚类过程之中。粒子群算法是一种有效的全局寻优算法，最早由美国的Kennedy和Eberhart于1995年受到鸟群迁徙行为提出，通过群体中粒子间的合作和竞争产生的群体智能指导寻优。粒子群算法，将优化问题的解看做搜索空间中的一

43、只鸟，即“粒子”。首先生成初始种群，即在可行解空间中随机初始化一群粒子，然后根据目标函数确定适应度值。每个粒子都将在解空间中运动，并由运动速度决定其飞行方向和距离。粒子运动速度通过跟踪粒子本身找到的最优解和整个种群目前找到的最优解来更新。粒子群算法核心是以下两个公式。 (2-10) (2-11)其中、g分别代表每个粒子到达过的最佳位置和整个种群到达过的最佳位置，h1、h2是两个对优化结果有很大影响的参数。用粒子群算法直接求解聚类问题也有两种思路，一种是以聚类结果为解，一种是以聚类中心的集合为解。本文采用的是后者，因为这样解的结果相对简单一些，也就是本文应用的算法中每个粒子的位置表示k个聚类中心

44、适应度由下面公式表示 (2-12)详细算法见表2-6表2-6 粒子群聚类算法n 初始化：设置聚类数目和粒子数目，对每个粒子，将每个数据点指派为某一类，并计算各类聚类中心，作为粒子的位置编码。计算粒子适应度，将粒子初始速度设为0，根据适应度产生粒子个体最佳位置p(i)和种群最佳位置p。 n 循环，直到达到设定迭代次数根据公式更新所有粒子的速度和位置。按照粒子聚类中心编码，按照最近邻法则，对每个数据点进行聚类划分。计算新的聚类中心，更新粒子适应度，个体最佳位置p(i)和种群最佳位置p。 n 循环，直到达到设定迭代次数n 根据种群最佳位置，按最近邻法则，输出簇。第3章 多种聚类算法演示平台实现3.1 需求分析随着硬件产能的提升，传感器、存储器的大量应用，