发布时间 : 星期四 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
a单位代码 10445 学 号2 0032631 分 类 号 TP391.72
硕 士 学 位 论 文
论文题目 基于群体智能的关联规则挖掘及应用
学科专业名称：计算机软件与理论 申 请人姓 名： 王伟伟 指 导 教 师： 刘 希 玉 教授 论文提交时间：2007年 04月19日
1
山东师范大学硕士学位论文
第一章 绪论
本章首先介绍了群体智能的研究背景及前沿，其次阐述微粒群算法的发展现状，最后介绍了本文的主要工作和组织结构。
1.1研究现状
1.1.1群体智能的研究背景及现状
人们在很早的时候就对自然界中存在的群集行为感兴趣,如大雁在飞行时自动排成人字形,蝙蝠在洞穴中快速飞行却可以互不碰撞等。同时受蚂蚁、飞鸟等社会性昆虫行为的启发, 单个的个体智能并不高, 但依靠群体的能力, 却发挥出超出个体的智能。这种现象揭示了简单智能的主体通过合作可以表现出复杂智能行为的特性。通过对其行为的模拟,产生了一系列解决复杂优化问题的新思路和方法, 用于解决组合优化问题和其它一些实际应用问题的新方法相继产生。 一些启发于群居性生物的寻食、打扫巢穴等行为而设计的算法成功地解决了组合优化、通信网络和机器人等领域的实际问题，这些研究被称为对群体智能(SwarmIntelligence) 的研究。对于这些现象的一种解释是,群体中的每个个体都遵守一定的行为准则,当它们按照这些准则相互作用时就会表现出上述的复杂行为。作为一个新兴领域，自从20世纪80年代出现以来，引起了多个学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学科的热点和前沿领域。基于这一思想,Craig Reynolds在1986年提出一个仿真生物群体行为的模型BOID。这是一个人工鸟系统,其中每只人工鸟被称为一个BOID,它有三种行为:分离、列队及聚集,并且能够感知周围一定范围内其它BOID的飞行信息。BOID 根据该信息,结合其自身当前的飞行状态,并在那三条简单行为规则的指导下做出下一步的飞行决策。Reynolds 用计算机动画的形式展现了该系统的行为,每个BOID能够在快相撞时自动分开,遇到障碍物分开后又重新合拢。这实际上就是一种群体智能模型。尽管这一模型出现在1986 年,但是群体智能(Swarm Intelligence) 概念被正式提出的时间并不长。一个显著的标志是1999 年由牛津大学出版社出版的E Bonabeau 和M Dorigo 等人编写的一本专著《群体智能: 从自然到人工系统》(“SwarmIntelligence : From Natural to Artificial System”)，群体智能由单个复杂个体完成的任务可由大量简单的个体组成的群体合作完成，而后者往
2
山东师范大学硕士学位论文
往更具有健壮性、灵活性和经济上的优势。Bonabeau, Do rigo 等人于1999 年给出群体智能的定义: 群体智能是指任何受到社会昆虫群体和其它动物群体的集体行为的启发而设计的算法和分布式问题解决装置，对这些新方法的研究可将其称之为群体智能( Swarm Intelligence ) 的研究。
目前,对群体智能的研究尚处于初级阶段,但是它越来越受到国际智能计算研究领域学者的关注,逐渐成为一个新的重要的研究方向，并且已初见成果。2003年，在印第安那州召开的IEEE国际会议上，首次发起了对群体智能的系列研究。2005年，进行了第二次关于群体智能的IEEE国际会议，物理学家、工程师、计算机科学家、生物学家、经济学家、生态学者等在广义群体智能的定义下，展示和讨论了他们在各自领域中使用群体智能得到的成果，以及群体智能在这个新兴领域中的发展潜力和趋势。
群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制,并具有自组织、可扩展性、健壮性等特性。利用群体优势，在没有集中控制，不提供全局模型的前提下，为寻找复杂问题解决方案提供了新的思路。对群体智能的定义进行扩展，普遍意义上有以下几种理解。一是由一组简单智能体(agent)涌现出来的集体的智能(collective intelligence)，以蚁群优化算法(AntColony Optimization，ACO)和蚂蚁聚类算法等为代表；二是把群体中的成员看作粒子，而不是智能体，以粒子群优化算法(Particle Swarm Optimization，PSO)为代表。群体智能是对生物群体的一种软仿生，即有别于传统的对生物个体结构的仿生。可以将个体看成是非常简单和单一的，也可以让它们拥有学习的能力，来解决具体的问题。
现有的对群体智能的研究，大都是从某一种由大量个体表现出来的群体行为出发，从它们的群体行为中提取模型，为这些行为建立一些规则，从而提出算法，应用于解决实际中的问题。
目前,群体智能主要有两种算法,分别是微粒群优化算法(Particle Swarm Optimization,简称PSO)和蚁群算法(Ant Colony System,简称ACS)。
微粒群优化算法最早是由Kennedy和Eberhart于1995年提出的,是一种基于种群寻优的启发式搜索算法。它的基本概念源于对鸟群群体行为的研究。在自然界中,尽管每只鸟的行为看起来似乎是简单和随机的,但是它们之间却有着惊人的同步性,使得整个鸟群在空中的形态非常流畅优美。鸟群具有这样复杂的行为特征,可能是因为每只鸟在飞行时都遵循一定的行为准则,并且能够了解其相邻区域内其它鸟的飞行信息，从而调节自身的飞行位置和速度，实现鸟群的整体的和谐。微粒群优化算法的提出就是借鉴了这样的思
3
山东师范大学硕士学位论文
想。在微粒群优化算法中,每个微粒代表待求解问题的一个潜在解。每个微粒都可获得其邻域内其它微粒个体的信息,并可根据该信息以及简单的位置和速度更新规则,改变自身的状态量,以便更好地适应环境。随着这一过程的反复进行,微粒群最终能够找到问题的近似最优解。由于微粒群优化算法概念简单, 易于实现,并且具有较好的寻优特性,因此它在短期内得到迅速发展,目前已在许多领域中得到应用,如电力系统优化、TSP问题求解、神经网络训练、交通事故探测、参数辨识、模型优化等。
蚁群算法是由M Dorigo等人于1991年首先提出的,是受到自然界中蚂蚁群的社会性行为启发产生的,模拟了实际蚁群寻找食物的过程。在自然界中,蚂蚁群总是能够找到从巢穴到食物源之间的一条最短路径。因为蚂蚁在运食过程中,能在其经过的道路上留下一种被称之为“外激素(pheromone)”的化学气味。该气味能够被后来的蚂蚁感知到,并且会随时间逐渐挥发。每个蚂蚁根据道路上信息素的强弱来指导自己的运动方向。随着时间的推移，在某一道路上走过的蚂蚁越多,因为重复注入信息素，积累的信息素就越多,该道路在下一时间内被其它蚂蚁选中的概率就越大。根据这样的简单逻辑规则，蚂蚁最终会找到通往食物源的最短路径。蚁群算法正是利用了蚁群的这一特性来对问题进行求解。目前,蚁群算法已在组合优化问题求解,以及电力、通信、化工、交通、机器人、冶金等多个领域中得到应用,都表现出了令人满意的性能。例如多代理程序系统，通过增加“外激素”强化好路由，使数字信息素“蒸发”抑制差路由，从而解决路由选择问题。
1.1.2关联规则挖掘的研究背景及现状
随着数据库技术的迅速发展以及数据库管理系统的广泛应用,人们积累的数据越来越多,面对海量的存储数据,如何从中发现有价值的信息或知识是一项非常艰巨的任务。数据挖掘就是为了满足这种要求而迅速发展起来的。数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。数据挖掘是人工智能和数据库发展相结合的产物，是数据库和信息决策系统目前最前沿的研究方向之一，已引起了学术界和工业界的广泛关注。关联规则的发现是数据挖掘中最成功和最重要的一项任务，它的目标是发现数据集中所有的频繁模式。数据挖掘(Data Mining)又称数据库中的知识发现(Knowledge Discovery in Database , KDD),是一个从大量数据中挖掘出隐含的、未知的、可理解的、对决策有潜在价值的知识发现过程.数据挖掘出现于20世纪80年代末,最早是在数据库领域发展起来的,称为数据库中的知识发现(KDD，Knowledge Discovery in Database),KDD一词首先出现在1989年人工智能国际会议上,
4