第24卷第1期2011年2月

四川理工学院学报(自然科学版)

JournalofSichuanUniversityofScience&Engineering(NaturalScienceEdition)

Vol 24 No 1

Feb 2011

文章编号:1673 1549(2011)01 0066 05

关联规则挖掘的Apriori算法综述

赵洪英,蔡乐才,李先杰

1

2

1

(1.四川理工学院电子与信息工程学院,四川自贡643000;2.四川理工学院计算机学院,四川自贡643000)

摘 要:关联规则挖掘是数据挖掘研究领域中的一个重要任务,旨在挖掘事务数据库中有意义的关联。随着大量数据不停的收集和存储,从数据库中挖掘关联规则显得越来越有必要性,关联规则挖掘的Apriori算法是数据库挖掘的最经典算法并得到广泛应用,在介绍关联规则挖掘和Apriori算法的基础上,发现Apriori算法存在着产生候选项目集效率低和频繁扫描数据等缺点。综述了Apriori算法的主要优化方法,并指出了Apriori算法在实际中的应用领域,提出了未来Apriori算法的研究方向和应用发展趋势。

关键词:数据挖掘;关联规则;Apriori算法;综述中图分类号:TP391 4

文献标识码:A

具有用户给定的满足一定条件的最小支持度Minsup和

引言

现在,数据挖掘作为从数据中获取信息的有效方法,越来越受到人们的重视。关联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后,关联规则就成为数据挖掘的重要研究方向,它是要找出隐藏在数据间的相互关系。定义为,设I={I1,I2, II,Y I,并且X和Ym}是m个不同项的项集,X 是不相交的项集,即X Y= 。关联规则的属性可以用以下三个参数描述:一是支持度,(support)定义为全体事务集T中有s%的事务同时支持事务集X和Y,则称s%为关联规则X Y的支持度。支持度表示规则的频繁程度,用S(X Y)表示。其中,最小支持度用Min sup表示。二是置信度(confidence),定义为全体事务集T中支持事务集X的事务中,有c%的事务同时也支持事务集Y,c%为关联规则X Y的置信度。置信度表示规则的强度,用C(X Y)表示。其中,最小置信度用Minconf表示。三是频繁项集,定义为支持度不小于最小支持度(minsup)的事务集,称为频繁项集。

关联规则的挖掘问题就是在事务数据库D中找出

最小置信度Minconf的关联规则。关联规则的挖掘一般分为以下两个步骤:

(1)找出存在于事务数据库中的所有频繁项集。(2)用频繁项集生成关联规则,即对于每个频繁项集X,若Y X,Y ,且c(Y (X-Y)) Mincon,f构成关联规则Y (X-Y)。

本文分析了Apriori算法,指出其存在的几个缺陷,提出了针对缺陷的主要改进优化的方法,列举了Apriori算法的几个应用领域,展望了Apriori算法的未来研究方向。

1Apriori算法

1 1算法概述

Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉那些没必要的中间结果)组成。该算法中项集(Itemset)的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数,称为项集的频率。如果某项集满足最小支持度,则称它为

收稿日期:2010 07 21

基金项目:四川省科技厅支撑计划项目(2008FZ0109);四川省教育厅科技项目(2007ZL048)(,