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

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