蚁群算法在聚类分析中的应用研究

论文摘要

M.Dorigo在1991年提出的蚁群算法是一种基于仿生学原理的组合优化算法,它具有其他智能优化算法及群体智能算法的优点,并成功应用于旅行商问题、二次分配问题、车辆调度问题、电路设计以及网络路由设计等问题。近年蚁群算法被用于数据挖掘中,给数据挖掘的聚类分析和分类算法提供了更广阔的思路。本文详细的叙述了蚁群算法的基本思想、原理和理论,在详细分析其优缺点,提出若干改进方法；将蚁群算法应用到数据挖掘的聚类分析,对几种蚁群聚类方法,进行了比较深入的研究和分析,得出改进后的蚁群聚类算法,本文的主要工作如下：（1）蚁群算法的研究。本文简单介绍了蚁群算法的发展现状,并详细阐述了算法的基本思想、原理、数学模型及实现过程,在分析、比较了几种常见蚁群算法的前提条件下,针对这些算法容易陷入局部最优的缺点,给出了基于扰动因子的最大-最小蚁群的改进算法。在最大-最小蚁群算法中,引入了扰动因子,有效地避免算法陷入局部最优。（2）聚类分析的研究。本文简单介绍了几种聚类分析算法的基本思想、原理、数学模型及实现过程,针对传统聚类算法对实际问题的局限性的缺点,并将蚁群算法应用到聚类分析中,利用蚁群算法的特性对聚类问题进行建模,给出了基于混合距离的k-means算法。在基于信息素的k-means算法的基础上,增加了混合距离的概念,使得算法的使用范围更广。（3）组合蚁群聚类算法的研究。本文结合几种蚁群聚类算法的特点,给出了一种新的组合聚类算法：它在初始阶段使用基于混合距离的k-means算法,快速得到一个粗略的聚类集合；在算法的收尾阶段,采用基于信息熵的蚁群聚类算法对数据集进行二次聚类,从而得到最优解。同时,给出了该组合蚁群聚类算法的模型和步骤,并进行了仿真实验,能够得到最优解。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.2.1 蚁群算法
• 1.2.2 聚类分析
• 1.2.3 蚁群聚类算法
• 1.3 本文组织
• 第2章 蚁群算法及改进
• 2.1 基本蚁群算法
• 2.1.1 基本蚁群算法的思想及基本原理
• 2.1.2 基本蚁群算法的数学模型
• 2.1.3 基本蚁群算法的流程
• 2.1.4 基本蚁群算法的实现
• 2.1.4.1 蚁群算法的规则
• 2.1.4.2 规则的实现
• 2.1.5 基本蚁群算法优缺点分析
• 2.2 改进的蚁群算法
• 2.2.1 蚁群系统
• 2.2.2 最大-最小蚁群算法
• 2.2.3 基于扰动因子的MMAS改进算法
• 2.2.3.1 算法改进思路
• 2.2.3.2 算法流程与描述
• 2.3 实验验证
• 2.3.1 数据描述
• 2.3.2 算法比较及分析说明
• 2.4 本章小结
• 第3章 聚类分析
• 3.1 几种常见聚类分析
• 3.1.1 基于蚁堆原理的聚类分析
• 3.1.1.1 LF算法
• 3.1.1.2 基于信息熵的LF算法
• 3.1.2 基于蚂蚁觅食行为的聚类分析
• 3.1.2.1 k-means算法
• 3.1.2.2 基于信息素的k-means算法
• 3.2 基于混合距离的k-means的改进算法
• 3.2.1 算法改进思路
• 3.2.2 改进算法的描述
• 3.3 实验验证
• 3.3.1 数据描述
• 3.3.2 结果比较及分析说明
• 3.4 本章小结
• 第4章 组合蚁群聚类算法
• 4.1 算法思路
• 4.2 算法描述及流程
• 4.3 实验验证
• 4.4 本章小结
• 第5章 总结与展望
• 5.1 本文总结
• 5.2 展望
• 致谢
• 参考文献
• 攻读学位期间的主要研究成果