发布时间 : 星期六 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
以后这一研究逐渐成为热点,KDD研究的内容是,能自动处理数据库中大量的原始数据,从中挖掘出潜在的可能关系模式以发现新的知识为目标,随着研究对象的扩展,人们开始称之为数据挖掘, 1995年，在加拿大蒙特利尔召开了第一届国际知识发现和数据挖掘学术会议，之后每年召开一次，至2003年已经召开了9次。当今，知识发现和数据库挖掘已经成为一个活跃的IT领域。我国从事数据挖掘的研究起步较晚,大约在90年代中期开始,国内许多高校和科研院所在这一领域内开展研究,并取得了许多成就。
目前数据挖掘技术已能够立即投入使用,这是因为作为支撑的三个基础技术已日趋完善。具体表现为:(1)数据库现在正在以一个空前的速度增长,并且数据库正在广泛地应用于各行各业,解决了海量数据收集。(2)现在已经成熟的并行多处理机的技术形成了强大的多处理器计算机。对数据能做到快速访问。(3)数据挖掘算法经过了最近10多年发展逐渐形成了一种成熟、稳定且易于理解和操作的应用技术。
在事物数据库中挖掘关联规则,关联规则(Association Rules)的挖掘是研究的一个重要方向也是数据挖掘领域中的一个非常重要的研究课题,它是由R.Agrawal等人首先提出的。目前已有许多研究成果,最经典的挖掘关联规则的算法是Apriori。在数据挖掘的研究领域, ,它由美国IBMAlmaden Research Center的R.akeshAgrawal等人于1993年首先提出,是描述数据库中数据项之间存在的一些潜在关系的规则.典型的关联规则算法有R.Agrawal等人提出的Apriori算法和DHP算法,它们属于数据库遍历类算法. R.Agrawal提出的Apriori-Hybrid算法,Park等人提出的DHP算法(Direct Hashing and Pruning)使用的是Hashing技术,这种算法有效地改进了候选集的产生过程.R,Srikant和R.Agrawal基于分类结构(IS-A层次关系),提出了挖掘广义关联规则的问题,它用在高层抽象概念层上挖掘关联规则不仅有助于获得大的支持度、表达普遍的数据关系,而且能减少无兴趣或冗余的规则.H.Toiconen提出的抽样(Samping)方法,用较小的代价从大型数据库中找出关联规则.上述种种算法的提出,均不同程度地改进了关联规则发现的过程. 先前的研究表明随着数据库项目的增多,尤其是当降低支持度和可信度时, Apriori算法所生成的关联规则的数目会以最大频繁项集长度的指数增长,其中包含了大量的冗余规则,不利于企业进行决策,同时也影响了算法的效率。
关联规则挖掘中有关Apriori算法的讨论
R.Agrawal 等在1993年设计了一种基于宽度优先算法，通过对数据库D的多趟扫描来发现所有的频繁项目集。在每一趟扫描中只考虑具有同一长度K（即项目集中所含项
5
山东师范大学硕士学位论文
目的个数）的所有K项集。Apriori算法提出了挖掘关联规则的一个重要方法，是一个基于两阶段频集思想的方法，将关联规则挖掘的设计分解为两个子问题：
（1）找到所有支持度大于最小支持度的项集。这些项集称为频集。 （2）使用第1步找到的频集产生期望的规则。
在关联规则挖掘频繁项集的诸多算法中，Apriori算法是一个最基本的，近年来，研究人员不断努力对这一算法进行改进，提出了基于哈希表、划分数据、采样、动态数据等技术的改进算法，还有人利用树、堆栈和图等数据结构来提高数据挖掘得效率。 很多文献针对算法在运行中存在的上述搜索空间问题提出了改进，例如在每一次生成Lk的同时按照一定的规则缩减数据集的规模，从而大大减少了数据集的个数，有效地提高了算法效率。或者利用Hash表来存放事务数据。:对给定数据库的事务和项数据用若干Hash表来记录,每个项构造一个Hash表,而Hash表中的元素为各事务在该项中出现的事务编号,然后通过扫描各Hash表,实现挖掘频繁项集的目的。如果对于长度大于k的候选项目集，可以采用散列技术，使得提高数据项集频度统计速度和减少不可能成为频繁项目集的候选项目集这两个操作可以在同一个数据结构中实现。借助于邻接矩阵研究频繁集的计数,在减少数据库的扫描次数方面也有很大改进。
1.2 研究意义
1. 关联规则挖掘算法自提出以来已经取得了一定的研究成果，但由于其研究才刚刚开始，研究领域也不全面，因此从群体智能理论出发，多层次多角度研究关联规则挖掘算法尤为必要。
2. 由频繁k-1项集进行自连接生成候选频繁k项集数量巨大，特别是在初期的候选集非常庞大，而在后期候选集将会急剧缩小，尤其在生成二维候选集时问题比较突出，因此需要缩小二维候选集的规模很具有研究意义；
3. 在每一次循环中事务集的个数也将影响整个算法的性能，在数据量比较大时数据仓库问题尤其明显，如何缩减每一次循环中的事务集也是一个很值得考虑的问题。 4. 减少扫描数据库的次数，特别是在验证候选频繁k-2项集的时候需要对整个数据库进行扫描，非常耗时。所以数据库扫描技术的改进还是一个值得考虑的问题。
5. Sampling 算法，该算法的基本思想是选取给定数据库D的随机样本S, 然后,在S而
6
山东师范大学硕士学位论文
不是D中搜索频繁项集该方法以算法的准确性换取了算法的有效性。由于我们搜索S中而不是D中的频繁项集,我们可能丢失一些全局频繁项集，促进搜索的智能性，还是一个新的很有吸引力的研究课题。
1.3本文的主要内容及组织结构 1.3.1主要内容
本文在系统地归纳数据挖掘的一般原理、一般方法以及相关技术的基础上，对群体智能中关键技术之一的微粒群算法进行了探索性的研究，主要内容包括如下几个方面： （1）在简要总结介绍课题的研究背景、国内外研究现状及选题意义的基础上，研究了群体智能和微粒群技术的基本原理、一般方法及其在各个领域的应用。
（2）系统地介绍了关联规则挖掘的基本原理、一般步骤、相关技术以及主要应用，分析了关联规则分析的常用工具，并结合实际应用对其性能进行了比较评价，研究了关联规则中常用的挖掘算法，分析了这些算法各自的优缺点及适用情形，为人们快速准确地找到适合特定领域的挖掘算法提供了技术支撑；。
（3）在认真研究Apriori算法的基础上，针对算法中存在的产生大量的候选项集以及筛选时所造成的浪费运行时间和空间的缺陷，提出了“基于微粒群算法的抽样方法,通过理论分析和实验验证表明新的算法克服了原算法的缺点，提高了关联规则挖掘的质量和效率，具有很强的实用性。
1.3.2本文的结构
本文共分五章，各章的主要内容如下：
第一章绪论，简要介绍了课题的研究背景、当前国内外的研究现状和论文的主要内容及组织结构。
第二章群体智能，内容包括：群体智能的概念、群体智能的总体模式、群体智能的功能、群体智能的模式分类
第三章关联规则挖掘算法分析，内容包括：关联规则挖掘的基本原理、关联规则挖掘算法的一般步骤，着重研究了关联规则挖掘中常用的Apriori算法以及各方面的改进，分析了各自的优缺点及适用条件，介绍分析了进行关联规则挖掘的常用工具,且结合实际
7
山东师范大学硕士学位论文
应用对其性能进行了比较评价。
第四章基于群体智能的微粒群算法，在认真研究“改进的Apriori算法”的基础上，提出了“基于微粒群优化算法的关联规则挖掘算法”，通过理论分析和实验验证表明新的算法克服了原算法的缺陷。
第五章结束语，对本文的研究成果进行概括并指明今后的研究方向。
8