内容发布更新时间 : 2024/11/15 3:47:35星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

关联规则挖掘方法研究

作者：刘 凯 彭国志

来源：《电脑知识与技术》2010年第05期

摘要:关联规则是数据挖掘研究的一个重要分支。阐述了关联规则的基本概念、关联规则挖掘的基本模型;详细分析了关联规则挖掘的经典算法—Apriori算法,Apriori算法核心思想、性能分析及其改进技术。

关键词:关联规则;Apriori算法;数据挖掘;频繁项目集

中图分类号:TP315文献标识码:A 文章编号:1009-3044(2010)05-1029-03 The Method Research of Mining Association Rules LIU Kai, PENG Guo-zhi

(Anhui University of Technology,Ma'anshan 243000,China)

Abstract: Association rules is an important branch of the research of The Data Mining.The paper illustrates the basic concepts and the basic model in mining association rules.It also detailedly

analyzes the classic algorithm in mining association rules-Apriori.Finally,the paper discusses the main concept and the performance analysis and the improve of technology of Apriori. Key words: association rules; apriori algorithm; data mining; frequent itemsets

关联规则技术是数据挖掘技术的一个重要分支,最早是由Agrawal等人于1993年提出的。最初主要是针对超市购物篮问题分析,其目的是为了获得交易数据库中不同商品之间的关联。这些关联反映了顾客的购买行为模式,可以用来指导商家科学地安排进货、库存以及货架设计等。

关联规则挖掘是帮助发现大量数据库中项集之间的关联关系。通过描述数据库中数据项之间存在的潜在规则,找出满足给定支持度和置信度阈值的多个域之间的依赖关系,这些关系是预先未知的隐藏的,是不能通过数据库的逻辑操作或统计的方法得出的。因为它们不是基于数据自身的固有属性,而是基于数据项目同时出现的特征。关联规则案例中最典型的例子就是:“80%的客户在购买啤酒的同时也会购买尿布”,其直观意义为,顾客在购买某些商品的时候有多大的倾向会购买另外一些商品。发掘类似这样的规则,对于设定市场策略是很有价值的。关联规则可以应用于顾客购物分析、商品货架设计、商品货架设计、商品广告邮寄分析、目录设计、追加销售、仓储规划、网络故障分析以及根据购买模式对用户进行划分分类等。

关联规则的数据挖掘在商业等领域中的成功应用,使得它已成为数据挖掘领域中最成熟、最活跃、最重要的研究内容。随着大量数据的增加和储存,许多人士对于从数据库中挖掘关联

龙源期刊网 http://www.qikan.com.cn

规则越来越感兴趣,已经引起了数据库、人工智能、统计学、信息检索、可视化及信息科学等诸多领域的广大学者和研究机构的高度重视,取得了众多研究成果。在提高挖掘规则算法的效率、可用性、适应性以及应用推广等方面,许多学者仍在不懈的努力着。关联规则模式属于描述型模式,其形式简洁、易于解释和理解并可以有效地扑捉数据间的重要关系,发现关联规则的算法属于无监督学习的方法。 1 关联规则基本概念

为了使后面算法的描述更加清晰准确,现对关联规则挖掘中涉及到的基本概念作以简单的介绍。

定义1.1 关联规则的数据集记为D,D为事务数据

库,D={t1,t2…tk…tn},tk={i1,i2, …im…tp},tk (k=1,2,…n)称为一个事务(Transaction),im(m=l,2,…p)称为项目(Item)。在事务数据库中,项目就是商品或者服务的名称,事务还包括其他一些信息,如日期、客户编号等。简单的说,事务就是项目的集合。

定义1.2 设I={ i1,i2, …im }是D中全体项目组成的一个集合,I中的任何一个子集X称为D中的项目集(Itemset), │X│=k称集合X为k项目集(k-Itemset)。设tk和X分别为D中的事务和项目集,如果X?哿tk,则称事务tk包含项目集X。每一个事务都有自己唯一的标识符,称为TID。

定义1.3 数据集D中包含项目集X的事务数,称为项目集X的支持数,记作σx。项目X的支持度记为Support(X),其中: Support(X)=( σx/│D│)*100%

其中│D│是数据集D的事务数,若X的支持度不小于用户指定的最小支持度(MinSupport),则X称为频繁项目集,简称频集(或者大项目集);若X的支持度小于用户指定的最小支持度(MinSupport),则称X为非频繁项目集,简称非频集(或者小项目集)。

定义1.4 关联规则可以简单的表示为:R:X?圯Y,其中:X?奂I,Y?奂I,并且X∩Y=?覫,它表示如果项目集X在某一事务中出现,则必然会导致项目集Y也会在该事务中出现。因此,X被称为规则的先决条件,Y为规则的结果。

定义1.5 对于关联规则R:X?圯Y,其中:X?奂I,Y?奂I,并且X∩Y=?覫。规则R的置信度(Confidence)的定义是:

置信度反映了包含X的事务中同时出现Y的条件概率。

定义1.6 关联规则的支持度是交易集中同时包含X和Y的事务数与所有事务数之比,记作Support(X?圯Y),即:

龙源期刊网 http://www.qikan.com.cn

Support(X?圯Y)=Support(X∪Y)

支持度反映了X和Y中所含的项在事务集中同时出现的频率。

支持度和置信度是描述关联规则的两个重要概念,如果不考虑支持度和置信度,那么事务数据库中存在着数量庞大的关联规则。事实上,大多人一般只对满足一定的支持度和可信度的关联规则感兴趣。为了发现有价值的关联规则,需要指定两个阀值:最小支持度(minSupport)和最小置信度(minConfidence)。前者即为用户指定的关联规则必须满足的最小支持度,它表示了一组物品集在统计意义上的需满足的最低程度;后者即用户指定的关联规则必须满足的最小可信度,它反应了关联规则的最低可靠度。 2关联规则挖掘的基本模型

关联规则挖掘的任务就是要在事务数据库D中找出具有用户给定的最小支持度和最小置信度的的所有强关联规则。强关联规则A→B对应的项集必定是频繁项目集,而频繁项集A∪B导出的关联规则A→B的置信度又可由频繁项目集A和A∪B的支持率计算。因此,关联规则挖掘可分解为2个步骤:

第一个步骤的任务是迅速高效地找出D中全部频繁项目集,是关联规则挖掘的中心问题。 第二个步骤是由频繁项目集产生强规则的枚举探查过程。利用频繁项集生成所需要的关联规则,依据用户设定的最小置信度进行取舍,最后得到强关联规则。 综上所述,关联规则挖掘的基本模型可用图1表示。

算法1为频繁项目集的搜索算法,算法2为关联规则的产生算法。用户通过制定最小支持度阀值和最小置信度阀值分别与算法1和算法2交互,并通过与规则结果集的交互对挖掘结果进行解释和评价。

关联规则挖掘所面临的主要问题是数据库规模之巨大,如何提高算法效率是算法的关键问题。对于第二个子问题,即由频繁项目集产生强规则的枚举探查过程相对较为简单直观,但对于第一个子问题,即如何快速有效地找出数据库中的频繁项集,它是关联规则挖掘算法中最复杂的问题之一。因此目前大量的研究工作都集中在第一个子问题上,第一个子问题是关联规则挖掘算法的核心。

3 关联规则经典算法—Apriori算法 3.1 Apriori算法概述