关联规则挖掘综述

关联规则挖掘综述

摘 要:近年来国内外学者对关联规则进行了大量的研究。为了更好地了解关联规则的挖掘技术,对研究现状有更深入的了解,首先本文对数据挖掘技术进行了介绍,接着介绍了关联数据挖掘的基本原理,最后对经典的挖掘算法进行分类介绍。

关键词:数据挖掘;关联规则;算法;综述 1.引言

数据挖掘是从海量的数据里寻找有价值的信息和数据。数据挖掘中常用的算法[1]有:关联规则分析法(解决事件之间的关联问题)、决策树分类法(对数据和信息进行归纳和分类)、遗传算法(基于生物进化论及分子遗传学理论提出的)、神经网络算法(模拟人的神经元功能)等。 数据挖掘最早使用的方法是关联分析,主要应用于零售业。其中最有名的是售货篮分析,帮助售货商制定销售策略。随着信息时代的到来,数据挖掘在金融[2]、医疗[3]、通信[4]等方面得到了广泛的应用。 2.关联规则基本原理

设项的集合I = { I1 ,I2 ,...,Im },数据库事务的集合为D,我们用|D|表示事务数据库所有事务的个数,其中用T

表示每个事务,使得T I。我们用TID作为每个事务的唯一标识符。用X表示一个项集,满足X T,那么交易T包含X。根据上述相关描述,给出关联规则的相关定义。 2.1项集支持度

用X表示数据库事务D中的项集,项集X的支持度表示项集X在D中事务数所占的比例,用概率P(X)表示,那么 Support(X)=P(X)=COUNT(X)/|D| (1) 2.2关联规则置信度

X Y关联规则的置信度是数据库事务D中包含X Y的事务数与包含X的事务数之比,表示方法如下:

confidence(X Y)= support(X Y)/support(X) = P(Y|X) (2)

3.关联规则算法

3.1经典的Apriori挖掘算法

大多数关联规则的算法是将关联规则挖掘任务分为两个子任务完成。一是频繁项集的产生,频繁项集的目的是找到大于等于给定的最小支持度阈值的所有项集,这些项集我们称之为频繁项集。二是规则的产生,即从频繁项集中找到置信度比较高的规则,我们称之为强规则。Apriori挖掘算法是众多挖掘关联规则中比较经典的算法,它采用布尔关联规则,是一种宽度优先算法。 3.2Apriori算法优化

Apriori算法的思想是每产生一次候选集就需要扫描一次数据库,但是当数据库中的数据庞大,无法直接完全放于内存中,扫描过程中数据需要不断的换入换出,加重了I/O的负担。可见当数据信息大的时候,算法效率低下,同时也消耗的大量的内容。

3.2.1哈希表技术(散列项集到对应的桶中): Park等提出了一种基于散列的产生频繁项集的高效算法DHP算法。即将产生的所有的候选k-项集(k>1)散列到哈希表结构对应的桶中并增加对应的桶计数, 利用哈希表技术可以有效减少候选k-项集(k>1)所占用的空间,进而提高了Apriori算法的效率。

3.2.2 划分技术(为寻找候选项集划分数据): Savasere等提出了一个基于数据划分的算法,即将数据库中的记录划分成几个互不相交的块,各块可以高度并行执行,由最小支持度得到每块中对应的最小支持度。第一次扫描数据库,得到各块的频繁项集,即局部频繁项集。当算法进行数据库的第二次扫描时,需得到每个候选项集的支持数,进而得到全局频繁项集的值。

3.2.3事务压缩技术(即压缩未来迭代扫描的事务数据): 该技术用于压缩迭代扫描数据库的大小,即将不包含任何k-项集的事务肯定不包含任何(k+l)-项集,这种事务在以后考虑时,可以加上标记或者删除项集,因为产生j项集

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4