蚁群算法在挖掘最大频繁项集问题中的应用研究

论文摘要

随着信息技术特别是网络技术的高速发展,数据库技术已渗透到了各行各业,数据存储量大幅度增加,面临这些枯燥无味的海量数据,人工的对之进行分析或理解变得不太现实,因此人们迫切需要一种可以分析大量数据的技术出现。数据挖掘技术正是在这一背景下诞生的一门新学科。关联规则作为数据挖掘中的一个主要模式,一直受到众多学者的关注。它用于发现数据集中各个属性间的联系,从而得到有价值的关联关系。频繁项集是挖掘关联规则的关键步骤,它的挖掘效率直接关系到关联规则的效率。最大频繁项集蕴含着所有的频繁项集,并且数目要比频繁项集少得多,这样生成候选项集数目也会相应减少,从而节省开销。所以本论文集中在挖掘最大频繁项集问题上进行研究。蚁群算法是一种仿生优化算法,采用了正反馈并行自催化机制,具有较强的鲁棒性、优良的分布式计算机制、易于与其它方法结合等优点,已成功应用到了旅行商、二次分配、车辆路由等组合优化问题中。在最大频繁项集挖掘过程中当数据集中的属性项数目很大时,会产生组合爆炸问题,所以本论文利用蚁群算法中的启发式信息和正反馈机制来指导属性项的组合,避免产生大量的候选项集,为解决最大频繁项集问题提供一个新的思路。本论文对最大频繁项集及其挖掘方法进行了研究,从中总结各算法的特点,发现最大频繁项集的特点,将其抽象为子集问题。通过对蚁群算法解决TSP问题的研究学习,结合最大频繁项集问题独有的特点,解决了蚁群算法挖掘最大频繁项集问题中启发式信息的选择、可行解的构造和信息素的更新问题。在构造解的过程中添加了每只蚂蚁构造解的结束条件判断,并采用了回退技术。为了验证蚁群算法挖掘最大频繁项集的可行性和有效性,将蚁群算法和Apriori算法同时在经典测试数据库mushroom上进行了仿真实验,在支持度很小的情况下蚁群算法的运行速度要远远快于传统的Apriori算法。最后本论文将该算法应用到灾害性天气分析问题上,用以发现各种灾害性天气间的内在联系,进一步验证蚁群算法求解最大频繁项集的可行性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• §1-1 课题的研究背景及意义
• 1-1-1 数据挖掘概述
• 1-1-2 关联规则描述及应用
• §1-2 课题的研究现状
• 1-2-1 最大频繁项集挖掘研究现状
• 1-2-2 蚁群算法应用现状
• §1-3 课题的主要研究内容
• 第二章 最大频繁项集挖掘问题分析
• §2-1 基本概念
• §2-2 数据分布
• 2-2-1 水平数据分布
• 2-2-2 垂直数据分布
• §2-3 挖掘频繁项集传统算法
• 2-3-1 Apriori算法
• 2-3-2 频繁模式增长算法
• §2-4 最大频繁项集挖掘技术
• 2-4-1 剪枝技术
• 2-4-2 搜索策略
• 第三章 蚁群算法
• §3-1 蚁群算法的基本原理
• 3-1-1 生物背景
• 3-1-2 基本原理
• 3-1-3 人工蚁基本思想
• §3-2 蚁群算法模型
• §3-3 改进的蚁群算法及ACO
• 3-3-1 改进的蚁群算法
• 3-3-2 蚁群优化ACO
• §3-4 蚁群算法的特点
• 第四章 蚁群算法挖掘最大频繁项集
• §4-1 AS-MFI算法基本思想
• §4-2 数据分布及编码
• §4-3 AS-MFI算法详细设计
• 4-3-1 适应度函数构造
• 4-3-2 子集构建
• 4-3-3 信息素的更新
• §4-4 实验结果与分析
• §4-5 AS-MFI算法在灾害天气分析中的应用
• 4-5-1 灾害天气最大频繁项集挖掘的模型
• 4-5-2 灾害天气表征
• 4-5-3 灾害性天气数据处理
• 4-5-4 AS-MFI挖掘灾害性天气结果分析
• 第五章 结论与展望
• §5-1 本文研究工作总结
• §5-2 今后工作
• 参考文献
• 致谢