基于r语言多种聚类算法演示平台毕业设计论文(编辑修改稿)

基于r语言多种聚类算法演示平台毕业设计论文(编辑修改稿)内容摘要：

败。 聚类的有效性检验可 以说是一种反馈机制，根据有效性检验结果，需要对聚类的其它三个环节进行调整，从而获得满足问题要求的聚类结果。 聚类分析的作用 聚类分析旨在无类别标签的训练样本条件下，根据数据本身的特征分布提炼出数据的内在的模式或结构。 总的来说它主要有三个作用 [13]。 1) 聚类本身是人类学习的一种重要方式。 在没有人指导的情况下，人类可以根据自己的实践经验总结，对不同的事物进行分门别类。 对于某些 2 维数据人类自己可以通过观察对其进行分类，但对于更高维数据人类就束手无策了。 借助聚类分析可以通过计浙江工业大学本科毕业设计论文 3 算机运行一定算法对更高维 数据进行分门别类，从而拓展人类对数据的认知。 2) 有时获得数据的类别信息还不是人类的最终目的。 数据中的一些更深入的模式信息还需要进一步挖掘。 面对复杂的数据和问题，在聚类的结果上运用其它的数据挖掘技术，不仅可以提高其它挖掘方法的效率，而且可以提高其挖掘的可靠性。 3) 聚类分析还可以用于孤立点的检测。 有时进行聚类分析不是为了将相似的对象聚集在一起，而是为了将某个异常的对象从数据集中分离出来。 比如可用于检测工业控制中由多个变量引起的异常 [4]。 聚类算法的国内外发展现状 聚类分析的主要研究对象是聚类算法，也是本 文研究的主要对象。 在过去的 50 多年，人们持续不断的研究聚类算法，提出和发表了大量的聚类算法，它大致的 分类 如图1 所示 [5]。 图 12 聚类算法 分类 [5] 由于聚类问题是一个病态问题，目前为止提出的包括以上算法在内的算法都只能解决一部分的聚类问题。 问题对象的改变，很多算法就不再适用 ，或者性能很差。 所有算浙江工业大学本科毕业设计论文 4 法在可伸缩性、算法效率、处理不同类型属性的能力、发现任意形状的簇、输入参数数量最小化、初始敏感性、高维性、处理噪声能力、可解释性等方面存在或多或少的问题[67]。 聚类算法演示平台 研究目的 和意义 随着硬件产能的提升，传感器、存储器的大量应用，积累了大量的可用于数据分析的数据。 人们提出了各种各样的聚类问题，针对这些聚类问题，又相应的提出了各种各样的聚类算法。 一方面，这些算法都只能解决某一类问题，针对一个具体的聚类问题，人们面临大量的可选择的聚类算法，这往往令人无所适从，由此带来很大的工作量。 另一方面，开发一个新的聚类算法往往需要和已有的典型聚类算法进行比较。 开发一个可扩展其它算法，带有针对典型数据集的演示功能的聚类算法演示平台可以很好的解决这两个问题，势必给聚类问题的解决，聚类算法的研发带来很 大的帮助。 本论文的主要工作就是基于 R 语言开发这样一个具有实用价值的多种聚类算法演示平台。 论文框架 论文第一章介 绍聚类问题的背景与意义以及论文的目的和框架。 第二章主要介绍多种 聚类算法演示平台用到的聚类算法，包括基于划分的 kmeans、 AP 算法、基于密度的 DBSCAN、和基于层次的 AGENS、基于粒子群的聚类算法以及发表在 14 年 science杂志上的 FDP 算法。 第三章主要介绍利用 Rstudio 公司开发的 shiny 包实现交互式演示平台以及利用该平台对第二章提到的算法进行比较分析。 第四章介绍基于聚类分 析的NBA 篮球运动员位置分类。 第 五 章对本文的研究情况进行总结并展望。 聚类算法研究工具 —— R 语言和 Rstudio R 语言是一个有着强大统计分析及作图功能的软件系统，在 GNU 下免费发行，最先由 Ross Ihaka 和 Robert Gentleman 共同创立，现在由 R 开发核心小组（ R Development Core Team）维护，他们的开发完 全出于自愿、工作努力负责，将全球优秀的统计应用软件打包提供给我 们共享。 2020 年 用户成为成长最快的语言之一， 已经在数据挖掘的各个领域得到成功应用。 R 的开源免费和 统计背景使得 R 和其它语言相比在处理数据、学习聚类方面有很大优势。 Rstudio 是由 Rstudio 公司开发的 R 语言集成开发环境（ IDE）。 它包括支持直接运浙江工业大学本科毕业设计论文 5 行代码的控制台和语法高亮编辑器，以及用于画图、查看历史记录、调试和工作空间管理的工具。 它有商业版本和开源版本两个。 实测表明是一个用于 R 语言开发的极棒开发环境。 浙江工业大学本科毕业设计论文 6 第 2 章 多种聚类算法 研究 本章介绍本文开发的多种聚类算法演示平台用到的 六种 聚类算法 ， 包括基于划分的kmeans 算法、基于密度的 DBSCAN 算法、基于层次的 AGNES 算法、基于优化的粒子群聚 类算法和 分别在 07 年和 14 年发表在 science 杂志上的 AP算法和 FDP 算法。 通过学习这些算法的相关文献，将它们总结如下。 kmeans 算法 kmeans 算法是典型的基于划分的聚类算法。 基于划分的方法在给定的含有 n 个数据对象的数据集上，构建 k 个划分，往往是首先创建一个初始划分，然后采用一种迭代重定位技术，尝试通过对象在划分间移动来不断改进划分。 在这个迭代过程中， kmeans优化以下误差平方和准则函数作为改进目标。 假设 n 个样本  1, 2, ,Nix R i n L 分为 k 类，对 1,2 ,jk L 和 1,2,in L ，定义： 1 , 0 , ij ij   如 果 第 个 样 本 属 于 类否 则 (21) 则矩阵  = ijμ 具有如下性质：    10 , 1 = 1 1 , 2 ,kij ijj in 且 设 jn 表示第 j 类中所包含的样本个数，则  1 1, 2 ,nj ijin j k 设 NjmR 表示第 j 类的中心，则  1111 1 , 2 ,ni j i nij i j iniijixm x j kn    (22) 所以第 j 类的类内差异为 21()njij i jiJ x mμ 那么，整体类内差异 (误差平方和准则 )为   21 1 1() k k njW ij i jj j iJ J x m      μ μ (23) kmeans 算法的具体步骤如表 21 浙江工业大学本科毕业设计论文 7 表 21 kmeans 算法  初始化：随机选择 k 个数据元素作为 k 个簇的均值 1, 2 ,Njm R j k  循环，直到 k 个均值都不再变化为止：  1111 1 a r g m in , 1 1 1 , 2 ,i j iljknij i nij ij iniijifo r i to nl x m ue n d fo rxm x j kn    μ 0  输出 μ AP 算法 Affinity Propagation (AP)聚类算法 [89]是 Frey 等人 2020 提出的一种聚类算法，提出以来，一直受到研究领域的广泛关注。 从类型上看，它也是一种基于划分的算法。 AP算法本质上是 一种基于因子图的信念传播和最大化算法。 它根据 N 个数据点之间的相似度进行聚类，这些相似度可以是对称 的，即两个数据点互相 之间 相似度一样（如欧式距离）；也可以是不对称的，即两个数据点互相之间的相似度不等。 这些相似度组成 N N 的相似度矩阵 S（其中 N 为 N 个数据点）。 可见 AP 算法对数据点之间相似度的度量非常的宽泛，不像 kmeans 一样仅使用 欧式距离作为相似度度量。 但是本文聚类算法演示平台用到的 AP 算法仍然以欧式距离作为相似度度量方式。 AP 算法事先不需要指定聚类数目，而是将所有数据点都作为潜在的聚类中心，称之为 exemplar，并以 S 的对角线上的 N 个值 ,iiS 作为每 个数据点能否成为聚类中心的评价标准，并称之为参考度（ preference），数据点 i 参考度越大，成为聚类中心可能性越大。 参考度是 AP 算法用到的唯一一个人为参数，在没有先验知识的前提下，通常每个数据点的参考度相同，且根据相似度的分布取值，该参数的大小很大程度上影响了最终簇数目的多少， preference 越大，簇数目越多。 AP 算法中传递两种类型的消息：从点 i 发送到候选聚类中心 k 的数值消息 ,ikr 和从候选聚类中心 k 发送到 i 的数值消息 ,ika。 这里 ,ikr 反映 k 点作为 i 点的聚类中心是否合浙江工业大学本科毕业设计论文 8 适，而 ,ika 反映 i 点选择 k 作为其聚类中心的意愿程度。 两者分别被称为吸引度和归属度。 ,ikr 和 ,ika 越强，则 k 点作为聚类中心的可能性越大， AP 算法通过迭代而不断地更新每个点的吸引度和归属度，直到产生 m 个高质量的 exemplar，同时将其余的数据点分配到相应 的簇中。 根据作者提供的 matlab 代码， AP 算法的具体步骤如表 22。 表 22 AP 算法  初始化：先计算 N 个点之间的相似度值，构成矩阵 S，选取 preference(一般取 S 的均值 ) ；设置一个最大迭代次数， 令 , 0ika 。  循环，直到达到最大迭代次数或者聚类结果多次迭代不变： , , , 39。 , 39。 39。 s .t . 39。 m a x { }i k i k i k i kk k kr S a S   , , 39。 ,39。 s . t . 39。 { , }m in 0 , m a x { 0 , }i k k k i ki i i ka r r , 39。 ,39。 s .t. 39。 m a x {0 , }k k i ki i kar   输出 ,0i i i ira 的位置，把这些 i 作为聚类中心。 然后将其它点依次赋值给最近的聚类中心。 AGNES 算法 AGNES(Agglomerative Nesting)算法是凝聚层次聚类算法。 基于层次的算法将数据对象组成一颗聚类的树，根据层次分解是自底向上生成还是自顶向下生成，层次的聚类方法可以分为凝聚的和分裂的。 由于分裂的层次聚类算法，复杂度高，可伸缩性差，本文选择更常用的凝聚聚类算法 AGNES 加入算法演示平台。 AGNES 算法中心思想：首先将每个样本看成一个簇，然后根据一定连接方式（是一种簇间相似度的衡量方式）将最相似的簇合成一个簇，这个过程迭代进行直到满足一定终止条件。 在这里首先介绍不同的连接方式下簇间相似度的度量方式。 （ 1）单连接 两个簇之间的距离由两个簇所有连接中最短的那个决定：     , , m a x ,ijij x C y Cd C C d x y (24) （ 2）全连接 浙江工业大学本科毕业设计论文 9 两个簇之间的距离由两个簇所有连接中最长的那个决定：     , , m in ,ijij x C y Cd C C d x y (25) （ 3）平均连接 两个簇之间的距离由两个簇的所有连接的平均长度决定：     , 1, , ijij x C y Cijd C C d x ynn   (26) 在以上连接方式的基础上，给出 AGNES 算法如表 23。 表 23 AGNES 算法  初始化：每个样本作为一个单独的簇，  , 1, ,。 iiC x i n 每个簇的样本数1in 计 算任意两个样本之间的距离，构成相异度矩阵   ,ij i j nnD d x x D，簇数目 kn。  循环，直到聚类终止条件为止： 寻找距离矩阵 D 中上三角矩阵元素的最小值 ijD 删除簇 iC 和 jC 增加新的簇 , , 1。 q i j q i jC C C n n n k k     根据单连接方式更新距离矩阵 D  输出：剪枝后得到 ，簇  1,kCC。 上述的终止条件可以是预定簇数目、距离阈值（因为越往后簇间的距离越大）、最优聚类（某种准则）。 本文的多种算法演示平台，以预定簇数目为终止条件。 DBSCAN 算法 DBSCAN 算法是典型的基于密度的聚类算法。 基于密度的聚类算法有不一样的聚类思路和相。