【统计学与数据挖掘】
关联规则挖掘概述
中国人民大学统计学系数据挖掘中心
*
(中国人民大学统计学系,北京 100872) 收稿日期:2002-07-11
*本中心成员有袁卫、吴喜之、谢邦昌、易丹辉、王星、薛薇、赵绍忠、戴稳胜、匡宏波、伍业峰等。本文执笔人为戴稳胜、王星、赵绍忠。摘 要:文章讨论了关联规则的概念与分类,采用简单实例介绍了关联规则判断
标准以及计算机实现过程等几方面内容,全面介绍了关联规则的相关知识。
关键词:关联规则;支持度;置信度;增益
中图分类号:C812文献标识码:A 文章编号:1007-3116(2002)05-0004-06
关联规则的挖掘是数据挖掘的重要问题之一,随着大型连锁零售商店在零售市场上份额的增加,越来越多的超市或连锁店希望发现其庞大的交易数据库中隐含的相关销售信息,因此关联规则的挖掘引起了研究人员与企业界人士的共同关注。
一、关联规则的概念与分类
做关联规则分析之前首先要明白,关联规则是单向的,它是指某类项目或特征与另一类项目或特征间所存在的单向影响关系。一般相关系数对两类特征或项目的描述都是对称的,而且只能处理定序以上层次的数据。而实际经济生活中常会出现两方面的关系并不对称,或者数据仅仅是定类层次的情况。此时用关联规则来描述相当有效,而且对经济决策也相当有用。
因为关联规则通常用于购物篮分析,我们不妨以购物篮数据为例说明关联规则的概念及其分类。
给定一个交易集,其中的每一组交易都包含一组项目(或者说包含一组商品组合),那么关联规则可以表示为:
X →Y
(1)其含义是,在所有交易记录中,包括商品X 的交易有包括商品Y 的趋势,其中X 和Y 既
可以是单一商品,也可以是商品组合,如果是商品组合,则X ∩Y=U 。
关联规则按不同的标准可以分成不同的类别。常见分类包括以下三种。
1、按关联规则中处理的变量类别,可以分为布尔型和数值型
布尔型关联规则中两边变量都是离散变量或类别变量,比如“买啤酒→买婴儿尿布”;数值型关联规则处理则可以与多维关联或多层关联规则相结合,处理数值型变量,如“月收入5000元→每月交通费约800元”。但是要注意,关联规则本身不能处理连续型数值变量,寻求这类变第17卷总第55期2002年9月 统计与信息论坛Statistics &Information Tribune S ept.,2002Vol.17No.5
量的关联规则前要对它进行处理,常见处理即将该变量转换成类别变量,如高、中、低等,然后再进行处理。
2、按关联规则中数据的抽象层次,可以分为单层关联规则和多层关联规则
单层关联规则是指规则没有考虑现实世界中数据的分层,而多层关联规则则充分考虑了数据的多层性。比如“买夹克→买慢跑鞋”是一个细节数据上的单层关联规则,而“买外套→慢跑鞋”是一个较高层次和细节层次间的多层关联规则。
3、按关联规则中涉及到的变量数目可以分为单维(一元)关联规则和多维(多元)关联规则单维关联规则只涉及数据的一个维度(即一个变量),如用户购买的物品;而多维关联规则要处理多维数据,涉及多个变量。单维关联规则处理单一属性中的关系,而多维关联规则处理的是多个属性间的某些关系。比如“买啤酒→买婴儿尿布”只涉及用户购买的商品,属于单维关联规则,而“喜欢野外活动→购买慢跑鞋”涉及到两个变量的信息,属于二维关联规则。
二、关联规则的选择标准
任何两个变量间都可能存在着潜在的关联,判断关联规则可以从两步着手,第一步从技术角度提出一些限制条件,只有满足这些条件的关联规则才会提出作进一步分析;第二步从用户主观角度考虑。即使是满足技术条件的关联规则,也还要满足两个条件才能有用,这两个条件就是,该规则必须出乎常识或意料之外,而且规则必须具有潜在的作用。然而目前任何技术与算法都无法精确判断哪些知识属于常识,也无法判断哪些属于具有潜在作用的规则。因为不同的用户、不同的出发点对规则的作用认识就不同。对甲没有作用的规则,对乙可能就具有很大作用,这不仅取决于技术与常识的结合,而且还取决于决策者的专业知识及决策水平。因此关联规则的挖掘最终离不开人的作用。
1、关联规则选择的技术标准
下面仅仅从技术角度引进三条选择关联规则的标准,即支持度(support,也称广泛度,普遍度。下文以sup(.)表示,括号内是相应的关联规则)、置信度(confidence,也称预测度,下文以con (.)表示)和增益(lift ,下文以lif (.)表示)。
以一个假设的数据来说明这三个条件。假定某体育用品商店经营体育服装与鞋类,其中运动上装包括衬衣、外套,外套包括夹克与滑雪衫两种,而运动鞋则包括球鞋和慢跑鞋,其关系如下图所示
:
图1 关联规则示意例:商品层次结构图[统计学与数据挖掘] 中国人民大学统计学系数据挖掘中心:关联规则挖掘概述
而表1则是假设的购物篮数据库中的一部分:
表1 某体育用品店部分销售数据
交易项目成交次数交易项目成交次数
夹克,球鞋300滑雪衫,慢跑鞋200
滑雪衫,球鞋100衬 衣 10
夹克,滑雪衫,球鞋100夹 克 40
球 鞋50滑雪衫 60
慢跑鞋40合 计1000
夹克,慢跑鞋100
为便于理解,可以将上表整理成交叉表的形式如下:
表2 某体育用品店部分销售数据
运动鞋Y1单独买衣合 计
球鞋Y11慢跑鞋Y12
衫衣X110 10上衣X
外套X2
夹克X2140010040540
滑雪衫X2220020060460
单独买鞋5040
合 计6503401000
该表中数据是交易次数记录,以球鞋一列为例,表中数据表示球鞋交易中与夹克一起交易的有400笔,与滑雪衫一起交易的有200笔,单独购买球鞋的有50笔,共650笔交易涉及到球鞋。其他各行与列的含义与此相同。总交易笔数1000并不等于边缘交易笔数之和,因为其中还包括独立交易及三个或以上项目一起达成的交易。
以该数据为例,可以挖掘出若干关联规则,比如:“夹克→球鞋(X21→Y11)”;“外套→慢跑鞋(X2→Y12)”;“运动鞋→滑雪衫(Y1→X22)”等等。关联规则的支持度、置信度和增益的含义分别为:
(1)支持度sup(.)
表示在购物篮中同时包含关联规则左右两边物品的交易次数百分比,即支持这个规则的交易的次数百分比,相当于联合概率。如规则“夹克→球鞋”的支持度为:
sup(X21→Y11)=P(X21Y11)=400
1000
=40%(2)
(2)置信度con(.)
是指在所有的购买了左边商品的交易中,同时又购买了右边商品的交易概率,是一个条件概率。如规则“夹克→球鞋”的置信度为:
con(X21→Y11)=P(Y11?X21)=P(X21Y11)
P(X21)
=
400
540
74.1%(3)
(3)增益lif(.)
增益是两种可能性的比较,一种是在已知购买了左边商品情况下购买右边商品的可能性,另一种是任意情况下购买右边商品的可能性。比如规则“夹克→球鞋”的增益就是比较以下两种可能性,一是任意情况下买球鞋的可能性,另一是在已知某交易中有夹克的情况下包括球鞋统计与信息论坛 2002年第5期
[统计学与数据挖掘] 中国人民大学统计学系数据挖掘中心:关联规则挖掘概述
的可能性。规则“夹克→球鞋”的增益为:
lif(X21→Y11)=P(Y11?X21)-P(Y11)=74.1%-65%=9.1%(4)这个标准和数据挖掘中其它模型的选择标准一样,通过与“原有”规则的比较,来测量该规则提高预测准确性的程度。有时也把增益称为改良,因为它可以测量预测改进的程度。
2、关联规则挖掘算法的思想
关联规则的挖掘,通常是指定这三个标准的最小值(支持度有时还限定最大值),三个标准的取值都大于临界值的关联规则就被列出。关联规则挖掘的算法有很多,其基本思路一般是采用递推算法,首先将满足支持度要求的规则列出作为候选集(称为频集),然后在候选集中产生满足置信度和增益要求的规则。为了提高挖掘效率,人们又从几个方面提高产生频集的效率,比如划分原数据,采用并行算法产生频集、对数据进行抽样以减少计算量等,从而产生了许多优化的计算方法。
3、注意点
对于以上三个技术选择标准有几点要特别注意,首先是关于支持度,多层关联规则的支持度并不一定是低层单层关联规则支持度之和。如上例,规则“外套→球鞋”是多层关联规则,而“夹克→球鞋”、“滑雪衫→球鞋”为相应的单层关联规则,尽管外套包括且仅包括夹克和滑雪衫,但前者支持度并不等于后两者支持度之和:
sup(X2→Y11)≠(sup(X21→Y11)+sup(X22→Y11)(5)因为购买外套的人中,除了分别购买夹克和滑雪衫的人外,还有人一次交易中既买夹克,又买滑雪衫。
其次,判断关联规则的三个标准缺一不可,孤立地使用这三个标准中的任意一个,都可能导致错误结果。假如该体育商品店的交易可整理如下表:
表3 某体育商品店部分交易记录
运动鞋Y1单独购买合 计
球鞋Y11慢跑鞋Y12
衫衣X110 10
夹克X211 1上衣X
外套X2
滑雪衫X221898959
单独购买90
合 计29881000
该表中规则“夹克→球鞋”的置信度100%,但因为只有一人买了球鞋,规则的支持度只有千分之一,因而是个虚假关联,容易产生误导。
当某种常见现象出现在关联规则右边时,高置信度也会产生误导。因为这种规则根本不会出乎意料,对决策毫无帮助,有时甚至会起相反作用。
这三个规则中,增益是最有可能单独使用而不致产生误导的标准,因为它可以测量关联规则增进预测右边现象的能力。但如果该规则的支持度很低,该规则也可能造成误导。比如如果上述1000笔交易中,只有两人买球鞋,其中一人与夹克一起购买,另一人与滑雪衫一起购买,于是规则“夹克→球鞋”的增益为99.98%,但其支持度只有千分之一,因此该规则也是一条误导规则。
统计与信息论坛 2002年第5期
第三,多层关联规则有效并不意味着其下的单层关联规则就有效,比如“外套→跑步鞋”有效,但“夹克→跑步鞋”或“滑雪衫→跑步鞋子”就不一定有效,因为多层关联规则的支持度等达到最低值要求时,单层关联规则不一定能达到,这也就涉及到多层关联规则标准选择的问题。
三、多层及多维关联规则的挖掘
随着技术进步及对数据挖掘研究的深入,人们不再仅仅满足于单层、一维的关联规则的寻找,而是希望能在多个层次、多个变量角度寻求有用的关联规则。多层关联规则和多维关联规则的挖掘问题随之产生。
1、多层关联规则
关联规则的挖掘需要规定三个标准的最低值。对于很多应用而言,由于数据分布很散,很难在数据最细节层次上发现强关联规则,因而可以在较高的层次上进行挖掘。虽然高层次上得出的规则可能是更普遍而一般的信息,但是对于一个用户而言是普通信息,对另一个用户就可能不一定,所以数据挖掘应该提供在多个层次上进行挖掘的功能。
多层关联规则根据中涉及到的层次可以分为同层关联规则和层间关联规则。它们在支持度设置上有一些要考虑的东西。
同层关联规则最小支持度的设置可以采用两种策略,一是不同层次都使用同一个最小支持度。这样对于用户和算法实现来说都比较容易,但弊端显然。二是采用递减的最小支持度。每个层次都有不同的最小支持度,较低层次的最小支持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤工作。
层间关联规则应该根据较低层次的最小支持度来考虑最小支持度。
2、多维关联规则
它指关联规则涉及两个或以上变量。根据是否允许同一个维重复出现,多维关联规则又可以细分为维间关联规则(不允许维重复出现)和混合维关联规则(允许维在规则的左右同时出现)。比如“年龄20至30,喜欢郊游→喜欢游泳”就是混合维关联规则。
维间关联规则和混合维关联规则的挖掘还要考虑不同的字段种类,即类别数据与数值数据。对于类别资料,一般关联规则算法都可以处理,而对数值型资料,就需要将这些资料转换成类别资料才可以处理。
四、关联规则的实现
以数据挖掘软件eBizm iner为例,该软件的一般界面、功能与使用方法已作过介绍,在此不再赘述。假定数据挖掘前的数据准备工作已经完成,下面开始关联规则的挖掘。
1、定义关联规则挖掘项目
eBizm iner分三步定义数据挖掘项目:(1)点击“Data”选项卡,以数据文件的挖掘为例,将“Open file”按钮 拖放到项目区域;(2)将关联规则“Apriori算法”按钮 拖放至项目区域;(3)建立项目连接并打开数据文件。右击“Open file”,在弹出菜单中选择“Load Data”,选择要进行挖掘的数据文件,打开即可。其结果如下图所示:
[统计学与数据挖掘] 中国人民大学统计学系数据挖掘中心:关联规则挖掘概述
图2 关联规则挖掘图 图3 Apriori算法菜单
2、关联规则的挖掘
定义项目后即可开始关联规则的挖掘。右击“Apriori算法”按钮,出现图3所示菜单:
首先可以选择“Set Alg orithm Properties”,设置关联规则挖掘参数,七个可调整参数的意义分别如下:
Low erBoundSupport:关联规则最低支持度,隐含设置为0.1;
UpperBoundSupport:最高支持度,超过该支持度的关联规则将被忽略;
ConfidenceType:设置置信水平的计量类型、置信水平(Confidence)、增益(Lift)等,隐含设置为Confidence,如前所述,我们一般用Lift衡量;
RemoveAllM issing Cols:是否删除包含缺失值的列;
MinConfidence:最低置信度,置信度高于该值的关联规则才会列出;
SignificanceLev el:关联规则的显著水平;
Decreased Ratio:迭代时的下降比率,隐含值为0.5。
设置完关联规则挖掘的参数值后,在右击后弹出的菜单(图3所示)中选择“Run”,即可执行关联规则挖掘任务,完成后点击“View Result”即可查看结果。
[参考文献]
[1]M ichael J.A.Ber ry,Gor do n L inoof.Data M ining T echniques[M].New Y ork:John W iley&Sons, 1997.
[2]eBizm iner U ser's G uide Pow ered by I ndex Soft war e,Inc.,台湾,2001.
[3]Han,M.Kam ber.Data M ining:Concept and T echniques[M].San Fr ancisco M org an K aufmann Publishers,San Jiejo,2001.
[4]张尧庭,谢邦昌,朱世武.数据采掘入门及应用[M].北京;中国统计出版社,2001.
[5]蔡伟杰,张晓辉,朱建秋,朱扬勇.关联规则挖掘综述[J].计算机工程,2001,(5).
[责任编辑:张治国]