基于改进布谷鸟算法的K中心点聚类分析及并行实现

发布时间：2020-11-01 07:51

　　 近20年来,随着信息技术发展的越来越迅速,各个领域产生的数据量也越来越多,因此大数据的概念也随之引起了社会各界的重视。面对大量繁杂的数据人们逐渐发觉其是人类进步的重要资源,急需从这些海量数据中发现有价值的信息。数据挖掘是通过算法搜索出隐藏于海量数据中的信息的过程,通过这个过程可以从大量繁杂的数据中找到有价值的信息。其中K中心点聚类算法具有易实现、效率高等优点,因而被人们广为接受。随着人们对数据挖掘技术不断探究,数据挖掘领域有了众多的创新发展,将智能优化算法较好地应用到K中心点之中就是创新发展之一。布谷鸟算法作为进化计算范畴里新兴起的一种群体智能优化方法,引用了生物学进化论,参数更少,随机搜索更有效。本文首先对布谷鸟算法进行改进,之后将改进布谷鸟算法与K中心点进行结合,使其在指定初始质心的情况下完成聚类分析。最后将结合算法运用到Map Reduce框架下进行并行实验分析。具体工作如下:(1)简述了聚类分析、K中心点算法、布谷鸟算法、Map Reduce框架的相关概念、分析了两种算法的思想、流程、优缺点等。(2)对布谷鸟算法引入自适应发现概率。通过将布谷鸟算法中的固定值参数发现概率改为动态变化的自适应发现概率,使算法在前期加快收敛速度,后期提高收敛精度,更有效更快速地搜寻到最优解。(3)将改进后的布谷鸟算法运用到K中心点算法中,得到了基于改进布谷鸟算法的K中心点优化算法。此算法利用了基于自适应发现概率的布谷鸟算法以及K中心点算法在数据集中各自搜索寻优的优势,弥补了原始K中心点算法受初始质心影响较大和难免陷入局部极值的缺陷,提升了算法的效果。(4)将基于自适应发现概率的布谷鸟算法的K中心点优化算法运用到大数据平台上进行并行实验,表明该算法在大数据聚类分析方面有着优越的应用远景。通过算法在测试函数和数据集上的实验表明,改进布谷鸟算法具有更快的收敛速度和更好的寻优效果。布谷鸟算法与K中心点的结合算法具有更高的聚类质量和准确性,同时收敛速度也有所提升。最后结合算法的并行实验也进一步证明了该算法的高性能。
【学位单位】：西北师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP18
【部分图文】：

经过 Map 和 Reduce 两个过程来完成。首先 Map 过程并行处理和计算分割后的相互独立的数据块文件，计算处理后的结果再经过 Reduce 过程进行一定的汇总整合，最后返回输出。MapReduce工作过程：(1) 分割数据源：根据 MapReduce 所供给的库将源文件数据分为 M 份数据块文件。(2) 进行Map 过程：Master服务器给不同的Worker 服务器分配不同的数据块文件，之后执行Map 过程分别对数据块文件进行处理。不同的Map 之间互相独立、高度并行，它读入数据以〈Key， V alue〉的形式进行，把运算后的中间结果输入本地硬盘也采用〈Key， V alue〉的形式。(3) 进行 Reduce 过程：Master服务器分配不同的Worker 服务器进行 Reduce任务，将〈Key， V alue〉形式的中间结果进行合并整理并输出。MapReduce 的工作过程如图 2.1 所示。

16图 3.1 Rosenbrock 函数三维图利用 CS 算法对上述标准测试函数进行实验。参数设置如下：在 CS 算法群规模为 25，Pa1=0.55，Pa2=0.25，Pa3=0.05，最大迭代次数为 50。对测数在不同发现概率设置下分别进行实验，结果如图 3.2 所示。由图 3.2 可知，发现概率为 0.55 时，算法在第 13 代就达到了收敛。收敛极快，但是目标函数在 300 左右，距离最优值 0 有很大距离；发现概率为 ，算法在第 25 代收敛，目标函数为 200 左右；发现概率为 0.05 时，算法虽 37 代才收敛，但是目标函数接近于理论最优值 0。

图 3.2 不同发现概率 CS 算法分析图因此，在解决全局寻优问题的算法中，在算法前期的时候应保持一定的收度，以加快算法的运行为目的，进而使迭代的次数减少；当算法运行到后期候，应该减小收敛的速度，着重搜寻算法的全局最优解，加强寻优效果，最到最好的解。所以在算法整体运行过程中设定固定不变的参数，不能满足算行时自适应的需求。为了让算法能够满足在不过分增加迭代次数的前提下最找到更好的解，应该根据迭代的次数来设置自适应变化的参数。1.2 ECS 算法思想本章提出的改进布谷鸟算法（Evolutionary Cuckoo Search，ECS），将传谷鸟算法中的固定发现概率改进为自适应发现概率。ECS 算法的主要思想为：在对所求问题求解的过程中，将种群中的每一个位置视为所求问题解空间中的一个解，并用所要求解问题的目标函数值来衡巢位置的优劣。传统布谷鸟算法中，根据式（2-5）进行位置更新后，会产nd（0 h）随机数 r 与发现概率比较，若 r > P，此时需要随机变化鸟巢位置
【参考文献】

相关期刊论文 前10条

1 李涛;曾春秋;周武柏;周绮凤;郑理;;大数据时代的数据挖掘——从应用的角度看大数据挖掘[J];大数据;2015年04期

2 潘楚;张天伍;罗可;;两种新搜索策略对K-medoids聚类算法建模[J];小型微型计算机系统;2015年07期

3 徐焕良;翟璐;薛卫;任守纲;;Hadoop平台中MapReduce调度算法研究[J];计算机应用与软件;2015年05期

4 颜宏文;周雅梅;潘楚;;基于宽度优先搜索的K-medoids聚类算法[J];计算机应用;2015年05期

5 程学旗;靳小龙;王元卓;郭嘉丰;张铁赢;李国杰;;大数据系统和分析技术综述[J];软件学报;2014年09期

6 苏芙华;刘云连;伍铁斌;;求解无约束优化问题的改进布谷鸟搜索算法[J];计算机工程;2014年05期

7 胡欣欣;;求解函数优化问题的改进布谷鸟搜索算法[J];计算机工程与设计;2013年10期

8 邵鹏;吴志健;;基于改进PSO算法的Rosenbrock函数优化问题的研究[J];计算机科学;2013年09期

9 柳新妮;马苗;;布谷鸟搜索算法在多阈值图像分割中的应用[J];计算机工程;2013年07期

10 冯登科;阮奇;杜利敏;;二进制布谷鸟搜索算法[J];计算机应用;2013年06期

相关硕士学位论文 前4条

1 丁斌;基于布谷鸟算法的K-means聚类挖掘算法研究[D];合肥工业大学;2015年

2 韩晓慧;基于改进混合蛙跳算法的K-means聚类算法研究[D];甘肃农业大学;2012年

3 邓现伦;基于模糊商空间理论的模糊聚类研究[D];中南大学;2011年

4 雷达;数据聚类方法研究及其在软测量中的应用[D];青岛科技大学;2011年

本文编号：2865241