蚁群算法及其在聚类中的应用

论文摘要

蚁群算法是通过对自然界中真实蚂蚁的集体行为的观察、模拟而得到一种仿生优化算法,它具有很好的并行性、分布性。根据蚂蚁群体不同的集体行为特征,蚁群算法可分为受蚂蚁觅食行为启发的模型和受孵化分类启发的模型、受劳动分工和协作运输启发的模型。本文重点研究了前两种蚁群算法模型。受蚂蚁觅食行为启发的模型又称为蚁群优化算法(ACO),是继模拟退火算法、遗传算法、禁忌搜索等之后又一启发式智能优化算法。目前它已成功应用于求解TSP问题、地图着色、路径车辆调度等优化问题。本文针对蚁群算法收敛时间长、易陷入局部最优的缺点,通过对路径上信息素的更新方式作出动态调整、建立信息素平滑机制,进而使得不同路径上的信息素的更新速度有所不同,从而使改进后算法能够有效地缩短搜索的时间,并能对最终解进行优化,避免过早的陷入局部最优。聚类是数据挖掘的重要技术之一,它可按照某种规则将数据对象划分为多个类或簇,使同一类的数据对象有较高的相似度,而不同类的数据对象差异较大。受蚂蚁的觅食过程启发的聚类算法又被称为基于蚂蚁觅食原理的聚类算法。把蚂蚁觅食行为分为搜索食物和搬运食物两个环节,同时把数据对象视为蚂蚁,把聚类中心视为“食物源”,这样数据对象的聚类过程就可以转化为蚂蚁觅食的过程,在信息素的引导下蚂蚁就可以完成数据对象的聚类。但在该算法中没有区分数据对象不同属性的重要性,本文通过采用离差最大化方法,对每个属性根据它的重要性为它赋予一个权值,从而改进了原算法中的距离计算,使得相似的数据对象能快速的聚集到一起,从而避免了大量无效的相似度计算,提高了算法的效率。受孵化分类启发的模型又称为蚂蚁堆形成原理聚类算法。很多种类的蚂蚁都能够将卵和小幼虫紧密地排列成束并放置在巢穴孵化区的中心,而最大的幼虫位于孵化束的外围。Deneubourg等人根据这一现象最先提出了一个基本模型(BM)来模拟该现象,对基本模型比较成功的改进有LF算法。模糊聚类算法思想来源于Ruspini于1969年提出的模糊划分思想,是指在涉及事物之间的模糊界限时按一定要求对事物进行分类的数学方法,本文所介绍的FCM是其中的一种。本文通过分析LF算法和FCM算法的优缺点,以及它们的互补性,提出了基于LF算法的改进FCM算法,即将这两个算法进行融合,同时也采用了离差最大化赋权方法,对算法中的距离计算进行改进,进一步提高了算法的性能。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 数据挖掘
• 1.2 聚类分析
• 1.2.1 聚类分析的概念
• 1.2.2 聚类中的相似度计算
• 1.2.3 几种聚类分析方法
• 1.3 蚁群算法
• 1.3.1 蚁群算法模型的建立
• 1.3.2 蚁群算法在数据挖掘中的应用
• 1.4 本文的组织
• 第2章 蚁群算法与蚁群聚类算法
• 2.1 蚁群算法的概念
• 2.1.1 蚁群算法的分类
• 2.1.2 蚁群算法的研究现状及发展趋势
• 2.2 蚁群聚类算法的基本模型
• 2.3 蚁群聚类算法
• 2.3.1 蚁群聚类算法分类
• 2.3.2 几种蚁群聚类算法
• 2.4 小结
• 第3章 信息素增量动态更新的改进蚁群算法
• 3.1 求解TSP问题的基本蚁群算法
• 3.2 蚁群系统
• 3.3 信息素增量动态更新的改进蚁群算法
• 3.3.1 基本蚁群算法的不足
• 3.3.2 蚁群优化算法的改进策略
• 3.3.3 改进后蚁群算法的流程
• 3.3.4 实验结果及分析
• 3.4 小结
• 第4章 离差最大化赋权的蚁群聚类算法
• 4.1 基于蚂蚁觅食原理的聚类算法
• 4.2 离差最大化赋权算法
• 4.2.1 多属性决策
• 4.2.2 离差最大化赋权算法
• 4.3 基于离差最大化赋权的蚁群聚类算法
• 4.3.1 属性权重对算法聚类结果的影响
• 4.3.2 改进后的算法
• 4.4 小结
• 第5章 基于LF算法的改进FCM算法
• 5.1 模糊聚类算法
• 5.1.1 系统聚类法
• 5.1.2 逐步聚类法
• 5.1.3 模糊C均值聚类算法
• 5.2 LF算法
• 5.3 基于LF算法的改进FCM算法
• 5.3.1 两种算法的互补性分析
• 5.3.2 算法描述
• 5.3.3 仿真实验和结果分析
• 5.4 小结
• 第6章 总结与展望
• 6.1 本文的工作总结
• 6.2 进一步的工作
• 参考文献
• 致谢
• 攻读硕士学位期间发表学术论文情况