第3章关联分析

关联分析用于分析对象之间的关联性、相关性。关联规则是关联分析的技术之一。关联规则概念的提出最早源自超市购物篮分析(market basket analysis)。它用于分析顾客一次购买的商品之间的关联性，即哪些商品经常被一起购买，这从一定程度上反映了顾客的购买行为模式。这种模式可以被用于辅助零售运营商进行运营管理，例如，货品的布局安排、促销策略的制定、进货管理等方面。然而它的应用远不局限于购物篮分析，还可以用于发现许多其他应用领域数据之间的关联并进而研究其相关性，也可以用于分类、聚类等其他挖掘任务中。
本章将首先介绍关联规则相关的基本概念，如频繁项集、关联规则、闭合项集等，然后介绍几种经典的关联规则和频繁项集的挖掘算法，最后介绍关联分析的兴趣度度量。
3.1频繁模式与关联规则
以购物篮分析为例，关联规则用于分析顾客一次购买的商品的关联性。为了进行此类分析，需要记录顾客每次购买的所有商品，记录该信息的数据库称为交易数据库(transaction database)，如表3.1所示。表中第一列记录的是交易号(transaction identifier，TID)，对应于购物小票的编号，具有唯一标识一个顾客一次购物行为的作用。第二列记录的是一个顾客一次购物所包含的所有商品，用集合变量ti表示，其中i是交易号。表中的一行对应一次交易(transaction)。实际购物小票中通常一种商品在一行中表示，以便记录购买数量、价格和折扣等详细信息。在关联规则的分析中暂且忽略这些信息，并且为了表示的简洁性忽略了每个商品的具体品牌和规格等信息。


表3.1交易数据库示例





交易号(TID)商品(item)交易号(TID)商品(item)


1beer, diaper, nuts4beer, cheese, diaper, nuts
2beer, biscuit, diaper5beer, butter, cheese, nuts
3bread, butter, cheese



在关联规则挖掘中，被研究的对象称为项(item)。例如在购物篮分析应用背景下，顾客购买的每个商品称为一个项。所有项的集合由I表示，I={i1,i2,…,in}。例如，在表3.1中，I={beer,biscuit,bread,butter,cheese,diaper,nuts}。由此，每个交易ti对应的项的集合是I的子集，即tiI。例如，t1={beer,diaper,nuts}I。交易数据库D则是交易的集合，即D={t1,t2,…,tm}。I的任何一个子集称为项集(itemset)。一个项集X包含的项的个数称为该项集的长度。包含k个项的项集称为k项集。一个项集X在数据库D中出现的次数，称为频数，记为count(X)，等于包含该项集的交易的个数。例如，若X={beer,diaper}，则count(X)=3，因为它被t1、t2和t4所包含。一个项集X的支持度(support)记为support(X)，由公式(3.1)定义。


support(X)=count(X)|D|×100%(3.1)
其中,|D|代表D中交易的个数。若X={beer,diaper}，则support(X)=3/5=60%。

0

0
一个项集X的支持度如果大于用户给定的一个最小支持度(minimum support,minsup)阈值，则X被称为频繁项集(或频繁模式)，或称X是频繁的。
给定两个项集X和Y，关联规则是形如X→Y的蕴含式，其中XI称为规则的前件， YI称为规则的后件，且X∩Y=。一个规则X→Y在数据库D中的支持度，记为support(X→Y)，定义为项集X∪Y的支持度，即support(X→Y)=support(X∪Y)。它的置信度记为confidence(X→Y)，定义为项集X∪Y的支持度除以项集X的支持度，即如公式(3.2)定义。


confidence(X→Y)=support(X→Y)support(X)×100%(3.2)

一个规则X→Y如果同时满足support(X→Y)≥minsup和confidence(X→Y)≥minconf，则称该规则在数据库D中成立，其中minsup和minconf分别是用户给定的最小支持度和最小置信度的阈值。例如，给定minsup=40%和minconf=60%，则规则{beer,diaper}→nuts(为了表示的简洁性，将包含一个元素的集合的大括号省略，以下同)在表3.1所示的数据库中成立，因为support({beer,diaper}→nuts)=40%，confidence({beer,diaper}→nuts)=66.7%。
在实际应用中，给定minsup和minconf两个阈值后，一个数据库中存在的频繁项集的数目可能巨大，这是因为频繁项集存在如下性质。
性质3.1给定最小支持度阈值minsup，一个频繁项集的所有非空子集都是频繁的。
例如，若minsup=40%，则项集{beer,diaper,nuts}是频繁的，因为它出现在t1和t4两个交易中,则这两个交易必然同时包含了该项集的所有非空子集，如beer、 diaper、nuts、{beer,diaper}、{beer,nuts}和{diaper,nuts}，共6个项集。那么这些项集至少出现在这两个交易中，因此它们都是频繁的。根据该性质，可以知道“如果一个项集是不频繁的，则其所有超集都是不频繁的”也是成立的。
由于该性质的存在，如果一个数据库中可以发现的频繁项集的最大长度为20，则最终输出的频繁项集个数至少为(220-1)个，其中(220-2)个是该项集的子集。众多的项集给后续的结果分析与评价带来问题，因此，如何减少输出的项集个数，同时又不损失任何信息是需要解决的问题，为此，Pasquier等人首次提出了闭合频繁项集(closed frequent itemset)的概念。
一个频繁项集X被称为闭合频繁项集当且仅当不存在任一个项集Y满足XY且support(Y)=support(X)。闭合频繁项集X被称为是闭合的。
例如，在表3.1中，假设minsup=40%，项集diaper是频繁的，但不是闭合的，因为存在项集{beer,diaper}是diaper的超集且具有和它相同的支持度60%。而{beer,diaper}是闭合频繁项集，因为不存在一个更长的超集具有与它相同的支持度。利用闭合频繁项集，输出的最终满足条件的项集个数将大大降低。举个极端的例子，如果一个长度为20的频繁项集X的所有非空子集的支持度都与该项集相同，则原来结果中的(220-1)个项集都由该项集X所涵盖了。如果只有部分子集具有与X相同的支持度，则这些项集不必输出的同时，又可以通过X推导出它们的存在，所有未出现在结果中的那些X的子集一定是频繁的且具有与X相同的支持度。因此，闭合频繁项集的集合是频繁项集集合的一种信息无损的压缩。
3.2频繁项集的典型挖掘方法
关联规则的挖掘一般分为两个步骤： 第一步发现所有的频繁项集； 第二步从频繁项集中发现关联规则。本节重点介绍频繁项集的生成方法，3.3节介绍关联规则的生成方法。
关联规则自1993年提出以来，至今已有非常多的相关研究。典型的挖掘算法包括Agrawal 和 Srikant 1994年提出的Apriori 算法以及J. Han、J. Pei等提出的FPGrowth 算法和Zaki提出的Eclat算法等。挖掘闭合频繁项集的典型算法包括CLOSET+以及CHARM算法等。在本节中将对上面提到的Apriori、FPGrowth两个算法进行介绍。
3.2.1逐层发现算法Apriori
逐层发现算法Apriori发现频繁项集的过程是按照项集的长度由小到大逐级进行的，即首先发现频繁1项集，然后是频繁2项集，……，最后是频繁N项集。在发现过程中为了减少需要检查的项集的个数，提高发现效率，该算法充分利用了3.1节中给出的性质3.1，即一个项集如果是不频繁的，则其所有超集一定也是不频繁的。
Apriori算法的主要步骤如下所示。



算法3.1：  Apriori

输入： 交易数据库D， 最小支持度阈值minsup

输出： D中的所有频繁项集的集合F

主要步骤： 

(1)Find all of frequent items from D and save them in Fk,k=1;

(2)if Fk is not empty then begin

(3)Ck+1=gen_candidate(Fk);

(4)for each transaction t in D begin 

(5)for any candidate c∈Ck+1

(6)if itemset c occurs in t then

(7)c.count++;

(8)end for

(9)Fk+1={c∈Ck+1|support(c)≥minsup};

(10) k=k+1;

(11) end if

(12) return F=∪kFk;



函数 gen_candidate(Fk)

输入： 所有的频繁k项集的集合Fk

输出： 候选k+1项集的集合Ck+1

主要步骤： 

(1)for each itemset f1∈Fk begin

(2)for each itemset f2∈Fk

(3)if (f1［1］=f2［1］) and (f1［2］=f2［2］) and…and(f1［k-1］=f2［k-1］) and (f1［k］f2［k］)then begin

(4)for(i=1;i≤k;i++) 

(5)c［i］=f1［i］;

(6)c［k+1］=f2［k］;

(7)prune=0;

(8)for each ksubset of c

(9)if it is not in Fk then

(10) prune=1,break; 

(11) if (prune==0) add c to Ck+1;

(12) end if

(13)end for

(14) return Ck+1;





算法从k=1开始，即首先扫描一遍数据库，统计出每个单项的出现次数，得到频繁1项集的集合，记为F1。由F1构造可能会频繁的2项集，这样的项集称为候选项集(candidate itemsets)，候选2项集的集合记为C2，扫描数据库统计所有候选2项集的支持度，选出其中频繁的2项集，得到F2,…,以此类推。因此，在挖掘过程中的两个主要步骤为： 
(1) 利用已经发现的频繁k项集生成候选(k+1)项集。对应算法Apriori中的步骤（3），通过调用函数gen_candidate(Fk)生成候选项集。
(2) 扫描数据库D，对每个候选(k+1)项集统计其出现次数，计算支持度，得到频繁的(k+1)项集集合。对应算法Apriori中的步骤（4）~（9）。
其中生成候选集的过程，即函数gen_candidate(Fk)通过如下两个步骤实现： 
(1) 利用已经发现的频繁k项集来构造候选(k+1)项集。对应函数gen_candidate中的步骤（1）~（6）。
为了快速不重复地生成所有的候选项集，假设项集合I中的项之间存在一个人为定义的顺序，如字典序。一个项a若排在项b的后面，则表示为ab。同样地，每个项集中的项都按照此顺序进行排序。构造候选项集时，对于Fk中的任意两个不同的项集f1和f2，如果其前k-1个项分别对应相同，且f1的最后一项排在f2的最后一项的前面，则新的候选项集由它们的前k-1项，f1的最后一项和f2的最后一项共同构成。例如，假设项按字典序排序，f1={beer,diaper}，f2={beer,nuts}，则构造的候选项集为{beer,diaper,nuts}。同样{beer,diaper}和{beer,cheese}可以生成{beer,cheese,diaper}。
(2) 对每个候选(k+1)项集进行进一步剪裁，去除那些包含非频繁k项集的候选项集。对应函数gen_candidate中的步骤（7）~（11）。
{beer,diaper,nuts}的3个k项子集{beer,nuts}、{diaper,nuts}和{beer,diaper}都是频繁2项集，因此{beer,diaper,nuts}可能会频繁，因而被放到3项候选项集集合C3中。而对于{beer,cheese,diaper}来说，其子集{cheese,diaper}在数据库中仅出现一次，是不频繁的，因此{beer,cheese,diaper}不可能频繁，因而将被删除。
3.2.2无候选集发现算法FPGrowth

Apriori算法在发现频繁项集的过程中采用的是先生成候选项集再验证每个候选项集是否频繁的过程，另一种算法则无须生成候选项集，可以避免大量候选项集的产生。FPGrowth(frequentpattern growth)就是这样一种算法，其主要步骤如下。



算法3.2：  FPgrowth

输入： 交易数据库D，最小支持度阈值minsup

输出： D中的所有频繁项集的集合F

主要步骤

(1) L1=findF1(D,minsup);

(2) T=constructTree(L1,D);

(3) CallmineTree(T,);


函数 mineTree(T,X)

(1) initialize S=,M=;

(2)  if tree T contains a single path P then

(3)  for each combination Y of the nodes in the path P

(4) generate itemset X∪Y with support count=minimum support count of nodes in Y and S=S∪(X∪Y);

(5) let Q be the tree after replacing the single path P with a null node;

(6)  else Q=T;

(7)  for each item h in the header table of tree Q begin

(8)   generate itemset Y=X∪h with support count=h.support count;

(9) construct Y's conditional pattern base and Y's conditional FP tree Ty;

(10)if tree Ty≠ then call mineTree (Ty,Y); 

(11) end

(12)  Let M be the set of frequent itemsets mined from tree Q;

(13)  return (S∪M∪(SM))





下面以表3.1中的数据为例说明该算法的主要步骤，假设minsup=40%，即至少出现2次。
第一步首先扫描数据库，统计各个单项的出现次数(support count)，去掉出现次数少于2次的，然后将它们按照出现次数从大到小排序存放在列表L1中。在本例中L1={beer:4,diaper:3,nuts:3,cheese:3,butter:2}。为了描述的简洁性，将这5个单项分别用字母a、b、c、d和e表示。相应地，表3.1变为表3.2，在此表中，不频繁的单项被删除，剩下的项按照L1中的顺序排序。
第二步调用函数constructTree(L1,D)为数据库构建一棵前缀树，称为频繁模式树(frequent patter tree,简称FP树)。在此树中，每个结点(除根结点外)代表一个单项，在此例中代表一个商品，树中的每条路径代表表3.2中的一个交易中包含的各个项。这种树又称为前缀树。如果把每个交易中的项组合在一起看成一个字符串，则字符串前缀相同时共享相同的路径。表3.2对应的频繁模式树如图3.1所示。


表3.2排序后交易数据库





交易号(TID)商品(item)交易号(TID)商品(item)


1a,b,c4a,b,c,d
2a,b5a,c,d,e
3d,e




图3.1表3.2对应的频繁模式树T




构建该树时，表3.2中的第一个交易对应根结点下的第一条路径abc，每个结点中除了存放项的名字外，还记录一个频数n，即从根结点到当前结点对应的项集在数据库中出现的次数，处理完第一个交易之后，三个结点的该数字均为1。第二个交易包含的项集ab与第一条路径共享前两个结点，因此，只需将这两个结点的频数增加1即可。第三个交易与之前的项集不具有共享前缀的关系，因此在根结点下新建一条路径de； 第四个交易与第一条路径共享前三个结点，第五个交易则共享第一个结点。
图3.1中，除了树外，还有一个称为头表(header table)的表格，存放图中出现的每个单项，出现的次数(即频数)以及一个指针指向图中第一个包含该项的结点，图中同样的结点也都通过指针链接起来，以便访问。至此，原来的交易数据库中的信息已经在频繁模式树中全部保留，下面的挖掘过程只需通过该树即可。
第三步，通过调用函数mineTree(T,)发现所有的频繁项集。该函数是个递归调用的过程。为了充分说明各种可能的情况，以图3.2中的频繁模式树为例说明该函数的运行过程，要求项集最少出现两次。



图3.2频繁模式树T



对于如图3.2所示的频繁模式树，首先判断该树是否只有一个单支路径或根结点下只有一个分支，此处不存在，则将对头表中的每个项依次进行处理，顺序是从表中的最后一项(此处是e)开始，每项的处理方式都相同。下面以处理项e为例，说明挖掘过程。首先根据头表中e的指针链可以找到包含e的所有结点以及从根结点到该结点的所有路径，此处是两条路径，即abc:2和abd:2，存到一个称为条件模式库(conditional pattern base)的数据库中，如表3.3所示。其中，因为e出现在每条路径的最后，因此省略。为了方便，该库也可以简单地以集合{abc:2,abd:2}表示。对于该数据库，其处理方式与处理表3.1的方式一样，即先统计各个单项出现的次数后，去除不频繁的项，此处四个单项全部频繁，为其构建频繁模式树Te(如图3.3),接着递归调用函数mineTree(Te,{e})。


表3.3项e的条件模式库





项集频数
项集频数


abc2abd2

mineTree(Te,{e})函数运行时，首先可以看到此树含有一个单支前缀路径ab:5，这种情况下，可以把挖掘过程分成两部分，对路径ab生成与e的所有组合，即S={ae:4,be:4,abe:4}。然后将此路径用一个空的根结点替换，生成树Q，如图3.4所示。对其中的每个单项c和d分别进行处理，对应的频繁模式树均为空，因此分别生成了一个2项集，得到ce和de，构成集合M={ce:2,de:2}。最后，返回S∪M∪(SM)，其中SM代表将S中的每一个项集与M中的每一个项集进行组合得到的项集集合，即SM={ace:2,ade:2,bce:2,bde:2,abce:2,abde:2}，其中频数取的是两者中较小的。然后返回到mineTree(Te,{e})函数处，继续处理图3.2中的其他项d、c、b、a，处理方法相同。每个单项对应的条件模式库以及最终得到的频繁项集如表3.4所示。



图3.3项e的频繁模式树Te






图3.4频繁模式树Te的多分支部分Q





表3.4条件模式库和频繁项集





项条件模式库频 繁 项 集


eabc:2; abd:2{e:4,ae:4,be:4,abe:4,ce:2,de:2,ace:2,ade:2,bce:2,bde:2,abce:2,abde:2}
dab:2; c:2{d:4,cd:2,ad:2,bd:2,abd:2}
cab:2{c:4; ac:2,bc:2,abc:2}
ba:5{b:5,ba:5}
a{a:5}


3.3关联规则的生成方法
对于规则S→Y来说，称项集S为该规则的前件，Y为后件。找到所有的频繁项集后，就可以生成关联规则。对于任一个频繁项集X和它的一个非空真子集Y，假设S=X-Y，检验是否满足confidence(S→Y)≥minconf，如果满足，则输出规则S→Y。为了快速生成所有规则，对于一个频繁项集X，可以按照特定的顺序进行上述检验，一种高效的方法是按照Y的长度从小到大进行。即先检验X的每个1项子集(即长度为1的子集)作为规则的后件是否满足置信度阈值，然后是2项子集作为后件，……，最后是|X|-1项子集作为后件。若Y和Z是X的两个不同的k项子集，只有当confidence(X-Y→Y)≥minconf和confidence(X-Z→Z)≥minconf都满足时才有必要检验 X-(Y∪Z)→(Y∪Z)是否成立，如果confidence(X-Y→Y)<minconf或confidence(X-Z→Z)<minconf，则confidence(X-(Y∪Z)→(Y∪Z))一定不成立。因为如果confidence(X-Y→Y)<minconf，即


confidence(X-Y→Y)=count(X)count(X-Y)<minconf

则一定有


confidence(X-(Y∪Z)→(Y∪Z))=count(X)count(X-(Y∪Z))≤count(X)count(X-Y)
<minconf
因此，在由k项子集构建k+1项子集后件时可以采用Apriori算法中候选项集的构建方法(步骤3)。例如，假设项集{a,b,c,d}是一个4项频繁集，简写为abcd，假设abc→d、abd→c、acd→b和bcd→a都成立，检验2项子集时发现cd→ab、bd→ac、ad→bc、ac→bd成立，则由前两个规则可以生成d→abc，由后两个规则可生成a→bcd。d→abc需要进一步验证其置信度是否满足阈值的要求，因为cd→ab、bd→ac、ad→bc都成立； 而a→bcd不需要检验，因为ab→cd不成立，且它不可能成立。
3.4关联规则的其他类型
对于购物篮分析，前面提到的方法是针对顾客每次购买的商品的关联性进行分析，本节将介绍如何利用商品的类别层次信息进行关联分析、如何发现包含负项的模式及规则，以及将交易数据库推广到结构化表的数据中的方法。
3.4.1多层次关联规则
如果只对顾客购买的最细节的商品进行关联分析，有可能出现某些商品出现频率太低的情况，如果将商品进行归类，属于一类的商品的支持度会大于其包含的每个商品的支持度，从而有利于发现一些有意义的频繁模式或关联规则。为此研究者提出了多层次关联规则的挖掘方法，该问题最早由Han和Fu，以及Srikant和Agrawal首先提出研究。
商品的类别信息通常可以利用概念层次树来表示，图3.5所示为有关食品的概念层次树。


图3.5概念层次树



在概念层次树中叶子结点通常代表具体商品，而其上层结点代表的是其类别信息。如果一个结点A和结点B之间存在一条从A指向B的有向边，则A称为B的双亲结点，B则为A的子女结点，从根结点到一个结点A的路径中的所有除A外的结点都是B的祖先，同时A也是这些结点的子孙结点。结点的层次从根结点开始，根结点的层次为1，根结点的子女结点的层次为2， 以此类推。
利用项的概念层次信息不仅可以发现涉及哪些出现频率比较低的商品的频繁模式和关联规则，而且也可以发现概括性更强的规则。为了发现包含不同层次商品的频繁模式，可以将交易数据库进行更新，将一行中每个商品的所有祖先结点都添加到该行中，与其他项同等对待，利用频繁模式和关联规则的挖掘算法可以发现类似“牛奶→面包”或“牛奶→义利大果子面包”等类型的关联规则。当然，引入概念层次信息也会有一些问题存在，例如，挖掘效率变低、发现冗余的关联规则等。如果一个规则中的项是另一个规则中项的祖先，则称前者是后者的祖先规则。例如规则“牛奶→面包”是规则“三元脱脂鲜牛奶1.8L→义利大果子面包”的祖先规则。如果一个规则和其祖先规则具有近似相同的置信度，则该规则称为冗余规则。为了减少发现的规则数目，可以将冗余规则从输出的结果中去除。
3.4.2负模式
如前所述，集合I={i1,i2,…,in}包含了交易数据库中出现的所有项，当项ik没有出现在某个给定的交易中时，称该项对于该交易是负项，记为ik，与此对应，出现在该交易中的每个项id称为正项。一个包含负项的项的集合称为负项集。一个负项集的支持度如果不小于用户给定的最小支持度，则称为频繁负项集。给定一个频繁负项集X，如果confidence（subset（X）→Xsubset（X））大于或等于给定的最小置信度阈值则称subset(X)→Xsubset(X)为负关联规则。负项集和负关联规则统称为负模式。
为了发现负模式，将未出现在一个交易中的所有项都以负项的形式加入是不行的，因为毕竟出现在交易中的项的个数是很少的。可以只将那些频繁出现的项或所关注的某些项加入。
3.4.3结构化数据中的关联分析
前面介绍的交易数据库可以看作是非结构化的形式，也可以将其转化为结构化的表的形式存放。方法是将I中的每个项都作为一个属性，对于某个交易，如果某项出现在此交易中，则相应的该属性的取值为1，否则取值为空(或者为0)。例如，表3.1所示的交易数据库可以转化为如表3.5所示的结构化表。


表3.5交易数据库对应的结构化表





交易号(TID)beerdiapernutsbiscuitbreadbuttercheese


1111
2111
3111
41111
51111

同样对于存放在关系数据库表中的数据，可以利用关联分析的方法发现其中的频繁模式和关联规则。例如，对于表3.6所示的数据，可以将其转化为表3.7所示的数据表，这其中包括两种处理： 对于类别取值的属性，将每个取值转化为“属性=值”的形式，以便更好地理解所发现的频繁模式或关联规则； 对于取值连续的属性，首先将其离散化，然后将每个取值区间作为一个值，继而转化为“属性=值”的形式。


表3.6学生及修课信息表1





性别年龄专业类别分数


男21计算机硕士研究生A女22信息系统硕士研究生B男20会计本科生B女28金融博士研究生C男26计算机博士研究生B



表3.7学生及修课信息表2





性别年龄专业类别分数


性别=男年龄=［20~24］专业=计算机类别=硕士研究生分数=A性别=女年龄=［20~24］专业=信息系统类别=硕士研究生分数=B 性别=男年龄=［20~24］专业=会计类别=本科生分数=B性别=女年龄=［25~29］专业=金融类别=博士研究生分数=C性别=男年龄=［25~29］专业=计算机类别=博士研究生分数=B

3.5关联规则的兴趣度的其他度量
前面介绍的关联规则的定义中涉及两个参数： 支持度和置信度，这两种度量是描述一条关联规则是否有意义的常用度量。但是有些情况下，仅仅根据这两个度量发现的规则可能具有误导性。例如，如果利用关联分析的方法分析修商务智能课程的学生的基本信息以及所得成绩之间的关系，可能得到这样一条关联规则： 专业=计算机→成绩=良(53%，72.6%)，这使人感觉计算机专业的学生的成绩更易得良，但是实际上总人数中得良的比例为75%，也就是说如果是计算机专业的学生，得良的可能性反而降低了。那么，如何能避免发现此类关联规则呢？为此，很多研究者提出了不同的度量方法。下面介绍其中的两种： lift和cosine。
1. 度量lift
对于关联规则X→Y，度量lift的计算公式如下： 


lift(X,Y)=confidence(X→Y)support(Y)=P(X∪Y)P(X)P(Y)(3.3)

由公式(3.3)可以看到，lift度量弥补了置信度没有考虑规则后件的支持度的缺陷。如果X和Y相互独立，则P(X∪Y)=P(X)P(Y)。因此，若lift(X,Y)=1，则说明X与Y独立； 若lift(X,Y)>1，则说明X与Y正相关； 若lift(X,Y)<1，则说明X与Y负相关。
假设修商务智能课程的班级中的计算机专业与分数良之间的统计数字如表3.8所示，则由此可以计算其lift(B,C)值为0.53/(0.75×0.73)=0.97，即计算机专业与良之间有些负相关，接近独立。


表3.8计算机专业与分数良的列联表(contingency table)





计算机C非计算机合计


良B532275
非良20525
合计7327100


在此例中可以看到，使用lift度量可以将不相关的关联规则进行进一步筛选。但是，此度量是否在任何情况下都是客观的呢？再来看一个例子。表3.9和表3.10分别给出了有关计算机专业与选商务智能课程的两个不同的列联表，两个表中数据的区别在于AC的取值，即非计算机专业、没选商务智能课程的人数，前者大，后者小。从表中可以看出计算机专业和修商务智能课程之间存在一定的相关性，因为计算机专业选商务智能课程的人数比计算机专业选其他课程的人数以及非计算机专业选商务智能课程的人数都多出很多。根据表3.9计算可得lift(C,A)=2.4，符合相关性，而根据表3.10计算可得lift(C,A)=1.04，接近独立，与实际相悖。


表3.9计算机专业与修商务智能课程的列联表1





计算机C非计算机合计


选A8020100
没选20180200
合计100200300


表3.10计算机专业与修商务智能课程的列联表2





计算机C非计算机合计


选A8020100
没选201030
合计10030130

由此可知，度量lift对于两个项集同时不出现的情况是敏感的，它适用于变量对称的情况，即项集的同时出现和同时不出现同样重要的情况。那么怎么消除这种敏感性？下面介绍另一个度量cosine。
2. 度量cosine
对于关联规则X→Y，度量cosine的计算公式如下： 


cosine(X,Y)=P(X∪Y)P(X)P(Y)=support(X∪Y)support(X)×support(Y)

=confidence(X→Y)×confidence(Y→X)(3.4)

从公式(3.4)可以看到，AC的值不会影响consine的取值。表3.9和表3.10两种情况下cosine(C,A)的值相等，均为0.8，都属于正相关的情况。因此它适用于变量不对称的情况，即项集的同时出现相比于同时不出现更重要的情况。
练习题3
1. 假设记录了一组用户一段时间内的网上购物信息，包括在什么网站、什么时间、购买了哪些商品，每个用户都有一个唯一的用户ID，请回答如下问题： 
(1) 如何构造数据集以进行频繁项集和关联规则的发现？
(2) 根据(1)中构造的数据集所发现的关联规则对于商家有什么意义？
(3) 网上购物与在实体超市购物两种情况下关联分析的不同之处有哪些？
2. 给定表3.11所示的交易数据库，假设minsup=40%和 minconf=60%，请找出所有的频繁项集以及关联规则。


表3.11习题2





TID项TID项


1a,b,d,e4a,b,c,d
2a,c5a,b,c,f
3c,d,f

3. 表3.12中每一行记录了某天中价格上涨的股票，请据此表回答下列问题： 


表3.12习题3





日期股票日期股票


201264A,B,C,D201267A,B,E,F
201265D,E201268D,E
201266A,B

(1) 假设minsup=40%和 minconf=60%，可以发现哪些关联规则？这些规则在现实中有什么意义吗？
(2) 如果要利用关联规则的发现方法发现类似这样的规则“股票A涨、B涨，则第2天股票E涨”，应该如何构造数据集？
(3) 如果发现的规则的形式为“股票A涨、B涨，则第2天股票C跌”，数据集该如何构造呢？
4. 针对题2中发现的关联规则a→b，构造列联表，分别计算度量lift和cosine值，说明其含义。
5. 表3.13中每个项表达成类别商品的格式，如Aa代表的是a的类别是A，设minsup=40%和 minconf=60%，请发现含有类别的频繁项集及关联规则。


表3.13习题5





TID项TID项


1Aa,Ab,Bd,Ce4Aa,Ab,Bc,Bd
2Aa,Bc5Aa,Ab,Bc,Cf
3Bc,Bd,Cf

6. 假设minsup=50%，请找出表3.14中所有的闭合频繁项集。


表3.14习题6





TID项TID项


1a,b,c,d,e3b,d 
2a,c4a,b,c,d,e,f