基于混合PSO的K-means算法及并行化研究

摘要

数据挖掘有四种主要任务：关联分析、聚类分析、预测建模、异常检测。其中聚类分析是最重要的使用最广泛的任务之一。高效率和高精度结果一直是数据挖掘追求的目标。为了实现这一目标，人们进行了多种研究，其中一种就是将其它算法应用到数据挖掘中，这些算法包括智能算法、启发式算法，神经网络，模糊理论，粗糙集理论等等。论文中将禁忌搜索思想和粒子群优化算法引入到K-me~s聚类算法中，以此来提高K-means聚类算法的效率和聚类结果的精度。 禁忌搜索(Tabu Search)是一种智能启发式的全局性邻域搜索算法，它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过特赦准则来释放一些被禁忌的优良对象，从而保证搜索的多样化和有效性，研究表明它可以克服演化算法容易陷入早熟的缺陷，最终实现全局优化。粒子群优化算法(Pmicle SwarmOpfimiz~on)是一种演化计算技术，它具有简单、有效、收敛速度较快、全局搜索能力较强等特点，近年来受到学术界的高度关注，但是该算法也具有可能陷入局部最优进而导致结果精度低和收敛速度慢的缺点，因此在论文中使用禁忌搜索和控制参数等方法来改进粒子群优化算法，从而提高该算法的效率和解的精度。K-means是基于划分的聚类方法。它在目前的聚类分析中应用很广泛。但是该算法的缺点是易陷入局部最优，效率不高。而且聚类个数K常常是依据经验来确定，这将影响聚类结果。针对K-means算法的不足，把禁忌搜索思想和粒子群优化算法引入到K-means聚类算法中，以提高K-means算法的效率和结果精度。论文中研究了禁忌对象和禁忌表结构的选取、个体编码方式的选取、惯性权重的改进、罚函数的方式及表达式的选取和构造、适应度函数的构造。实验证明改进后的K-means算法的效率和结果精度都得到了提高。 为了进一步提高算法的执行效率，论文中研究了K-means算法的并行化。通过种群或者子种群之间的等价关系来确定等价类，按等价类初步划分种群，然后把划分好的种群分配到Slave结点上，实现数据并行，最后由Master结点机进行汇总给出结果。论文以时间复杂度和空间复杂度等指标从理论上对并行化的算法进行了评价，理论分析表明并行算法比并行算法具有更高的效率。

目录

文摘

英文文摘

声明

1绪论

1.1研究背景和意义

1.2国内外研究现状

1.3论文研究内容及组织结构

2K-means算法简介

2.1数据挖掘简介

2.1.1数据挖掘的定义

2.1.2数据挖掘的任务

2.1.3数据挖掘的常用算法

2.1.4数据挖掘的应用

2.2 K-means算法简介

2.2.1 K-means算法的基本思想

2.2.2 K-means算法存在的问题

2.2.3现有选取初始聚类中心的方法

2.3 小结

3禁忌搜索和粒子群优化算法

3.1禁忌搜索算法简介

3.1.1禁忌搜索算法的基本思想

3.1.2禁忌搜索算法的描述

3.1.3禁忌搜索算法的应用发展以及研究

3.2粒子群优化算法简介

3.2.1粒子群算法的基本原理

3.2.2粒子群算法的收敛性

3.3 小结

4基于混合PSO的K-means算法

4.1基于禁忌搜索的混合PSO算法

4.1.1对惯性权重的改进

4.1.2对全局极值选取方式的改进

4.1.3基于禁忌搜索的混合PSO算法描述

4.1.4基于禁忌搜索的混合PSO算法有效性的验证

4.2基于混合PSO的K-means算法

4.2.1粒子编码方式的选取及适应度函数构造

4.2.2基于混合PSO的K-means算法描述

4.2.3基于混合PSO的K-means算法有效性验证

4.3 小结

5 K-means算法并行化及分析

5.1相关知识介绍

5.1.1并行算法设计过程

5.1.2并行算法性能评价标准

5.1.3并行算法设计环境

5.2基于混合PSO的K-means算法并行化

5.2.1数据划分策略

5.2.2并行算法描述

5.2.3并行算法的分析

5.3 小结

6论文的总结

6.1论文的主要工作

6.2进一步努力的方向

致 谢

参考文献

附 录