《数据挖掘基础及其应用》课件第8章

第8章关联规则Ⅱ:关联规则挖掘8.1引言8.2关联规则提取8.3规则评价标准8.4规则评价指标8.5一致性问题8.6关联规则的应用本章小结

8.1引言

关联规则最初是针对购物篮分析(MarketBasketAnalysis)问题提出的。假设分店经理想更多地了解顾客的购物习惯,特别是想知道对于哪些商品,顾客可能会在一次购物时同时购买。为回答该问题,可以对商品零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联,分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁地被顾客同时购买,从而帮助他们开发更好的营销策略。

关联规则挖掘还可用于寻找数据集中各项之间的关联关系。根据所挖掘的关联关系,可以从一个属性的信息来推断另一个属性的信息。当置信度达到某一阈值时,可以认为规

则成立。例如,在网上购物时,系统会主动推荐一些商品,赠送一些优惠券,并且这些推荐的商品和赠送的优惠券往往都能直抵我们的需求,诱导我们消费。从大规模数据中挖掘对象之间的隐含关系被称为关联分析(AssociateAnalysis)或者关联规则学习(AssociateRuleLearning),可以揭示数据中隐藏的关联模式,帮助人们进行市场运作、决策支持等。

8.2关联规则提取

定义8.1(关联规则挖掘)给定频繁项集L,挖掘出所有非空子集f,使得规则f→L-f满足置信度要求。与频繁模式挖掘相似,关联规则挖掘也分为两步:①候选规则创建;②强规则(关联规则)判定。

8.2.1候选规则创建

候选频繁项集存在项集数量多、枚举困难等问题,这些问题同样出现在候选规则的创建中。例如,若频繁项集L={A,B,C,D},则该频繁项集所有的候选规则有:

图8-1中的每个节点都对应一个候选项集,并不对应一个候选规则,因此不能直接套用,需要进行修改,使项集树结构的每个节点不再表示项集,而对应一个候选规则。其难度在于如何通过上一层的候选规则创建当前层的候选规则。图8-2右侧为枚举候选集,本书采用的策略是前缀取交集、后缀取并集。图8-1候选频繁项集的构建

创建方法:给定两个候选规则f1→L-f1与f2→L-f2,|f1|=|f2|,则可产生规则f'→L-f'。其中:

如图8-2所示,f1={C,D},f2={A,D},L={A,B,C,D},创建候选规则D→ABC。图8-2候选规则枚举示意图

8.2.2关联规则挖掘

频繁模式挖掘面临的第二个大问题是候选项集呈指数级增长,同样的问题也出现在关联规则挖掘中,即给定频繁项集L,若L=d,则共计有2d-2个候选规则,如何利用如下剪枝原理。

我们希望通过Apriori剪枝原理,得到如下结论:

但是该结论不一定成立,因此不能直接利用Apriori剪枝原理。虽然上式不成立,但是下式恒成立:

定理8.1给定频繁项集L,其规则满足如下的单调性:

证明:

由Apriori算法中频繁项集的反单调性可得:

故结论恒成立。

该性质称为规则反单调性。利用该性质,可以构建规则剪枝方法,如给定频繁项集I={A,B,C,D},利用规则的单调性进行剪枝操作,可以减少候选规则的无用操作次数,如图8-3所示。图8-3候选规则剪枝示意图

关联规则产生的步骤:

第一步,对于每一个频繁项集I,产生I的所有非空子集。

第二步,对于I的每一个非空子集s,如果支持度大于事先设定的阈值,则输出关联规则s→(I-s)。

例8.2以表8-1所示的事务集为例,其中C[i]=是候选项集,L[i]是大数据项集。假设最小支持度为40%,最小置信度为70%,则数据项在候选项集中至少要出现4次以上才能满足大数据项的条件,规则的可信度至少要大于70%才能形成关联规则。Apriori关联规则挖掘过程如图8-4~图8-6所示。

计算过程:

(1)扫描计算1-项集,如图8-4所示。图8-4

(2)通过扫描数据库一次获取1-项集的支持度,如图8-5所示。图8-5

(3)通过频繁1-项集创建2-项集,通过筛选频繁2-项集选择3-项集,如图8-6所示。图8-6

由图8-6可以看出,从L[3]中不能再构造候选集C[4],所以算法终止。根据最小可信度,可生成规则如表8-2所示。

8.3规则评价标准

关联规则是用支持度和置信度来评价的,如果一个规则的置信度高,则称之为一条强规则(关联规则),但是置信度和支持度有时候并不能度量规则的实际意义和业务关注的兴趣点,但数据决定模式,背景决定效用。

8.3.1支持度与置信度缺陷

关联规则存在两大标准:支持度与置信度:

定义8.2(关联规则)给定I={I1,I2,…,In}是项集,D={T1,T2,…,Td}是全体事务数据集,规则X→Y是关联规则,当且仅当如下两个条件得到满足:

(1)规则支持度大于事先设定阈值,即s(X→Y)≥sminsup

(2)规则置信度大于事先设定阈值,即c(X→Y)≥cminsup

例如,我们分析一个购物篮数据中购买游戏光碟和购买影片光碟之间的关联关系。交易数据集共有10000条购买记录,其中6000条包含游戏光碟,7500条包含影片光碟,4000条既包含游戏光碟又包含影片光碟。数据集如表8-3所示。

以上结论告诉我们,计算层面的指标不能够覆盖背景验证,需要更多的指标。如图8-7所示,仔细分析数据挖掘的过程可以发现,创建更多的指标意味着需要将更加丰富的背景知识融入系统。此外,我们还需要做到关联规则的可解释性,创建更严格的计算指标,从更复杂的层面描述关联规则。图8-7数据挖掘整体过程中从模式到知识还需要更多的验证与计算

8.3.2关联规则价值衡量的方法

关联分析算法具有产生大量模式的潜在能力。例如,表8-4中显示的数据集虽然只有五项,但在特定的支持度和置信度阈值下,也能够产生数以百计的关联规则。

下面是一些将主观信息加入到模式发现任务中的方法。

(1)可视化(Visualization)。这种方法需要友好的环境,保持用户参与,允许领域专家解释和检验被发现的模式,与数据挖掘系统交互。

(2)基于模板的方法。这种方法允许用户限制挖掘算法提取的模式类型,只把符合模板规则的模式提供给用户,而不是报告中提取的所有模式。

(3)主观兴趣度度量(SubjectiveInterestingnessMeasure)。主观度量可以基于领域信息来定义,如概念分层或商品利润等,随后使用这些度量来过滤那些显而易见和没有实际价值的模式。

8.4规则评价指标

8.4.1兴趣度客观度量是一种评估关联模式质量的数据驱动方法。它不依赖于领域,只需要最小限度用户的输入信息;它不需要通过设置阈值来过滤低质量的模式。客观度量常常基于相依表(ContingencyTable)中列出的频度计数来计算。表8-5显示了一对二元变量A和B的相依表。

假定希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息,并汇总在表8-6中。

茶与咖啡的例子表明,由于置信度度量忽略了规则后件中出现的项集的支持度,高置信度的规则有时可能出现误导。解决这个问题的一种方法是使用被称为提升度(Lift)的度量:

它计算规则置信度和规则后件中项集的支持度之间的比率。对于二元变量,提升度等价于另一种被称为兴趣因子(InterestFactor)的客观度量,其定义为

兴趣因子比较模式的频率与统计独立假定下计算的基线频率。对于相互独立的两个变量,基线频率为

图8-8显示了两对词{p,q}和{r,s}出现的频率。{p,q}和{r,s}的兴趣因子分别为1.02和4.08。由于下面的原因,这些结果多少有点问题:虽然p和q同时出现在88%的文档中,但是它们的兴趣因子接近于1,表明二者是相互独立的;另一方面,{r,s}的兴趣因子比{p,q}的高,尽管r和s很少同时出现在同一个文档中。在这种情况下,置信度可能是一个更好的选择,因为置信度表明p和q之间的关联(94.6%)远远强于r和s之间的关联(28.6%)。图8-8-词对{p,q}和{r,s}的相依表

相关分析是基于统计学分析一对变量之间关系的技术。对于连续变量,相关度用皮尔森相关系数定义。对于二元变量,相关度可以用ϕ系数度量,其定义为

IS度量:IS是另一种度量,用于处理非对称二元变量。该度量的定义为

因为IS值取决于s(A)和s(B),所以IS存在与置信度度量类似的问题———即使是不相关或负相关的模式,度量值也可能相当大。例如,尽管表8-7中所显示的项p和q之间的IS值相当大(0.889),但当项统计独立时,它仍小于期望值(ISindep=0.9)。

8.4.2其他度量

除了迄今为止介绍的度量外,仍有另外一些分析二元变量之间联系的度量方法。这些度量可以分为两类:对称的度量和非对称的度量。如果M(A→B)=M(B→A),则度量M是对称的。例如,兴趣因子是对称的度量,因为规则A→B和B→A的兴趣因子的值相等;相反,置信度是非对称度量,因为规则A→B和B→A的置信度可能不相等。对称度量常常用来评价项集,而非对称度量方法更适合于分析关联规则。表8-8和表8-9用2×2相依表的频度计数,给出了这些度量的部分定义。

8.5一致性问题

给定各种各样的可用度量后,产生的一个合理问题是:当这些度量应用到一组关联模式时,是否会产生类似的有序结果。如果这些度量是一致的,则可以选择它们中的任意一个作为评估度量。否则的话,为了确定哪个度量更适合分析某个特定类型的模式,了解这些度量之间的不同点是非常重要的。

假设使用对称度量和非对称度量确定表8-10中的10个相依表的秩,这些相依表用来解释已有度量之间的差异。这些度盘产生的序分别显示在表8-11和表8-12中(1是最有趣的,10是最无趣的)。虽然某些度量值看上去是一致的,但是仍有某些度量会产生十分不同的次序结果。例如,ϕ系数与κ和集体强度产生的秩是一致的,但是与兴趣因子和几率产生的秩有些不同。此外,相依表E10根据ϕ系数具有最低秩,而根据兴趣因子却具有最高秩。

表8-11中的结果数据表明,很多度量对同一个模式的质量提供了互相矛盾的信息。为了了解它们之间的差异,需要考察这些度量的性质:

(1)反演性。考虑表8-13中显示的位向量,每个列向量中的0/1位表示一个事务(行)是否包含某个特定的项(列)。

定义8.3(反演性)客观度量M在反演操作下是不变的,如果交换频度计数f11和f00,f10和f01,它的值保持不变。

在反演操作下保持不变的度量有ϕ系数、几率、κ和集体强度。这些度量可能不适合分析非对称的二元数据。例如,向量C和D之间的ϕ系数与向量A和B之间的ϕ系数相等,尽管项c和d同时出现,且项a和b同时出现得更加频繁。此外,向量C和D之间的ϕ系数小于向量E和F之间的ϕ系数,虽然项e和f仅有一次同时出现。前面讨论ϕ系数的局限性时,已经提到了该问题。对于非对称的二元数据,使用非反演不变的度量更可取。一些非反演不变的度量包括兴趣因子、IS、PS和Jaccard系数。

(2)零加性。假定对分析文档集中的一对词(如“数据”和“挖掘”)之间的联系感兴趣。如果向数据集中添加有关冰下捕鱼的文章,对分析词“数据”和“挖掘”之间的关联有影响吗?这种向数据集(在此情况下为文档)中添加不相关数据的过程就是所谓的零加(NullAddition)操作。

定义8.4(零加性)客观度量M在零加操作下是不变的,如果增加f00而保持相依表中所有其他的频度不变,并不影响M的值。

(3)缩放性:图8-9显示了1993年和2004年注册某课程的学生性别和成绩的相依表。图中的数据表明自1993年以来男生的数量翻了一番,而女生的则是原来的3倍。然而,2004年的男生并不比1993年表现得更好,因为高分和低分男同学的比率保持不变,即3∶4。与之类似,2004年的女同学也并不比1993年表现得更好。尽管抽样分布发生了变化,但是成绩和性别之间的关联预期保持不变。图8-9成绩和性别的例子

定义8.5(缩放不变性)客观度量M在行/列缩放操作下是不变的,如果M(T)=M(T'),其中T是频度计数为[f11;f10;f01.f00]的相依表,T'是频度计数为[k1k3f11;k2k3f10;k1k4f01;k2k4f00]的相依表,而k1,k2,k3,k4是正常量。由表8-14可知,只有几率(α)在行和列缩放操作下是不变的。所有其他的度量,如ϕ系数、κ、IS、兴趣因子和集体强度(S),当相依表的行和列缩放时,它们的值也发生变化。本书虽然没有讨论非对称度量(如置信度、J度量、Gini指标和信任度)的性质,但很明显,在反演和行/列缩放

操作下,这些度量不可能保持相同的值,不过它们在零加操作下是不变的。

8.6关联规则的应用8.6.1关联规则与CRM企业所能做的就是尽可能多地收集顾客的信息,并借助各种分析方法,透过无序的、表层的信息挖掘出内在的知识和规律,这就是当前十分流行的数据挖掘技术所研究的。在挖掘出大量信息后,企业就可以根据这些规律或使用这些信息设计数学模型,对未发生行为做出结果预测,为企业的综合经营决策、市场策划提供依据。在CRM中,数据挖掘是从大量的有关客户的数据中挖掘出隐含的、先前未知的、对企业决策有潜在价值的知识和规则。

这些潜在价值的知识和规则有:

(1)客户特征。数据挖掘的第一步就是挖掘出顾客的特征描述。

(2)“黄金客户”。通过客户行为分析,归类出消费额最高、最为稳定的客户群,确定为“黄金客户”。

(3)客户关注点。通过与客户接触,收集大量客户消费行为信息;通过分析,得出客户最关注的方面,从而有针对性地进行营销活动,把钱花在“点”上。

(4)客户忠诚度。得出客户持久性、牢固性及稳定性分析。

8.6.2CRM关联规则挖掘

次序关联分析的侧重点在于分析事件的前后序列关系,发现诸如“在购买A商品后,一段时间里顾客会接着购买商品B,而后购买商品C”的知识,形成一个客户行为的“A→B

→C”模式。可以预见,一个顾客在买了计算机后,就很有可能购买打印机、扫描仪等配件。不过,要是通过数据挖掘找出“刮胡刀→抽水马桶→钻石戒指”这样的模式,估计企业客户服务部门就要忙乎一阵才能搞明白其中潜在的联系。

现以连锁药店管理的CRM系统为例来讲述数据挖掘。为了能更好地帮助药店选择适当的药材进货,利用关联规则挖掘来设计该系统,在得到销售记录的同时,先对其记录做

一定的统计,根据顾客同时购买的药物来挖掘其中的关联规则,然后列出订货清单进货。关联规则挖掘在CRM中的应用类别主要可分为:

(1)建立数据库。

在销售浏览表中设置四个字段:Saleno、Mname、Data和Price,将它们的属性设置为字符串型,并规定各个字段的长度。数据库界面如图8-10所示。图8-10数据库界面设计

(2)关联规则挖掘。