基于蚁群算法的聚类算法研究

论文摘要

通过对蚂蚁觅食过程中总能找到一条从蚁巢到食物源的最短路径现象的数学建模,得到一种新的算法—蚁群算法。该算法采用正反馈并行自催化机制,具有较强的鲁棒性、优良的分布式计算机制、易于与其它算法融合的优点,对于解决大规模复杂问题表现出了优异的性能和巨大的发展潜力。计算机的广泛使用,越来越多的数据被产生。如何从中找出有用的、完整的、能够为未来决策其作用的知识是一个巨大的挑战。聚类分析总为数据挖掘的重要研究领域之一,具有极其重要的作用和地位。它能根据数据的属性对其进行分组和归类。聚类分析使得同一类中的数据具有最大相似性,不同类中的元素具有最大向异性。本文首先对聚类分析进行了详细总结和介绍,分析和总结了目前流行聚类算法的优缺点;同时介绍了聚类分析中的数据表示、相似性度量准则等内容。随后,对蚁群算法进行了详细的介绍,分析和总结了目前应用于聚类分析中的两种模型:基于蚁堆原理和基于蚂蚁觅食行为原理。本文的重点是提出了一种新的蚁群聚类算法,它利用R只蚂蚁来求解,每只蚂蚁在开始的时候均分配一个空的串S ,该串的大小为N。串S中的数值表示相应的元素被分配到的具体的哪个类。将类中心和元素分别看作是食物源和蚁巢,蚂蚁根据信息素矩阵的值进行类标识分配。为了避免陷入局部最优,一次迭代之后,采用局部搜索技术来试图跳出局部最优。反复重复上述步骤,最终得到预期的解。为了验证本文算法的有效性和优越性,文中引入遗传算法、模拟退火算法和禁忌搜索算法来进行比较实验,实验中采用两个模拟数据集和三个UCI中的数据集。实验结果表明,本文提出的蚁群聚类算法要优于其它三种随机算法。随着Web站点自身信息越来越丰富和结构越来越复杂,目前信息服务中普遍存在着“信息过载”和“资源迷向”的状况,不同的用户有不同的访问目的。因此,将蚁群聚类算法应用于Web日志挖掘,实现网站的自适应,既把从日志数据中提取的知识转换为站点的只能,使其为用户提供更有效的服务。为此,本文设计并实现了一个自适应网站的原型系统,从而验证了运用相关技术实现网站自适应是可行的。本文最后对所有工作进行了总结,并对未来工作进行了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景及意义
• 1.2 研究现状
• 1.2.1 聚类算法研究现状
• 1.2.2 蚁群算法研究现状
• 1.2.3 蚁群聚类算法的研究现状
• 1.3 本文研究目标及主要研究内容
• 1.4 章节安排
• 第二章 蚁群聚类算法理论基础
• 2.1 数据挖掘基本原理
• 2.1.1 数据挖掘的一般过程
• 2.1.2 数据挖掘的一般功能
• 2.1.3 数据挖掘的一般方法
• 2.1.4 数据挖掘的发展
• 2.2 聚类分析理论基础
• 2.2.1 聚类分析在数据挖掘中的应用
• 2.2.2 聚类分析算法的概念与基本分类
• 2.2.3 距离与相似性的度量
• 2.2.4 划分聚类方法
• 2.2.5 k-平均算法分析
• 2.2.6 PAM 算法分析
• 2.2.7 改进的划分聚类算法分析
• 2.2.8 层次聚类方法
• 2.2.9 密度聚类方法分析
• 2.2.10 其他聚类方法分析
• 2.2.11 聚类算法的比较
• 2.3 蚁群算法相关理论
• 2.3.1 蚁群算法基本原理
• 2.3.2 基本蚁群算法的数学模型
• 2.3.3 基本蚁群算法的实现
• 2.3.4 基本蚁群算法的优缺点
• 2.4 蚁群聚类算法
• 2.4.1 基于蚁堆原理的蚁群聚类算法
• 2.4.2 基于信息熵的蚁群聚类算法
• 2.5 本章小结
• 第三章 蚁群聚类算法
• 3.1 智能算法在聚类分析中的应用
• 3.1.1 神经网络在聚类分析中的应用
• 3.1.2 遗传算法在聚类分析中的应用
• 3.2 蚁群聚类算法研究
• 3.2.1 算法具体描述
• 3.3 本章小结
• 第四章 仿真实验与结果分析
• 4.1 实验设计
• 4.2 实验结果分析
• 4.3 本章小结
• 第五章 WEB 日志挖掘的自适应站点原型系统
• 5.1 设计思想
• 5.2 体系结构
• 5.3 离线处理部分
• 5.4 在线推荐部分
• 5.5 系统实现
• 5.6 本章小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 致谢
• 参考文献
• 附录：蚁群聚类的JAVA 实现