精华区文章阅读

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 四）：关联规则
发信站: 哈工大紫丁香 (2001年06月14日16:06:25 星期四), 站内信件

关联规则发现
　
关联规则是形式如下的一种规则，“在购买面包和黄油的顾客中，有90％的人同时也买
了牛奶”（面包＋黄油 T 牛奶）。用于关联规则发现的主要对象是事务型数据库（tr
ansactional databases），其中针对的应用则是售货数据，也称货篮数据。一个事务一
般由如下几个部分组成：事务处理时间，一组顾客购买的物品（items），有时也有顾客
标识号（如信用卡号）。
由于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的售货数据。因此
，如果对这些历史事务数据进行分析，则可对顾客的购买行为提供极有价值的信息。例
如，可以帮助如何摆放货架上的商品（如把顾客经常同时买的商品放在一起），帮助如
何规划市场（怎样相互搭配进货）。由此可见，从事务数据中发现关联规则，对于改进
零售业等商业活动的决策非常重要。
关联规则的形式描述
设I＝{i1,i2,...,im}是一组物品集，D是一组事务集（称之为事务数据库）。D中的每个
事务T是一组物品，显然满足Tí I；每个事务有一个唯一的标识符，称作TID。我们称事
务T支持（support）物品集X，如果Xí T；也称事务T包含（contain）或满足（satisf
y）物品集X。关联规则是如下形式的一种蕴含：XT Y，其中Xì I，Yì I，且X? Y＝?
。称物品集X具有大小为s的支持度，如果D中有s%的事务支持物品集X；即Prob(X)=s%，
记为support(X)=s。称规则XT Y在事务数据库D中具有大小为s的支持度，如果物品集Xè
Y的支持度为s，即support(Xè Y)=s。称规则XT Y在事务数据库D中具有大小为c的可信
度（confidence），如果D中支持物品集X的事务中有c％的事务同时也支持物品集Y，即
Prob(Y|X)=c%，其中Prob(X)相当于支持X的事务在D中出现的频率大小。
如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规则。
事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。在文献中，一般
称满足一定要求的（如较大的支持度和可信度）的规则为强规则（strong rules）。因
此，为了发现出有意义的关联规则，需要给定两个阈值：最小支持度（minimum suppor
t）和最小可信度（minimum confidence）。前者即用户规定的关联规则必须满足的最小
支持度，简称为minsup；后者即用户规定的关联规则必须满足的最小可信度，简称为mi
nconf。称物品集X长度或大小为k，如果X中有k个物品，此时物品集X又可记作k-物品集
。
另外，在关联规则发现方法中还有一个重要的概念：高频物品集（frequent itemset）
。称物品集Xí I是高频物品集，如果事务数据库D中支持物品集X的事务频度大于最小支
持度。高频物品集也称大物品集（large itemset）。
关联规则发现算法
关联规则发现任务或问题是：给定一个事务数据库D，求出所有满足最小支持度minsup和
最小可信度minconf的关联规则。该问题可以分解为两个子问题：①求出D中满足最小支
持度minsup的所有高频物品集；②利用高频物品集生成满足最小可信度的所有关联规则
。子问题②的解决方法较为简单，对每个高频物品集l，计算其所有的非空子集，对每个
非空子集a，考察规则aT （l-a），如果该规则的可信度大于最小可信度minconf，则输
出此规则。
子问题①的求解是关联规则发现的关键部分。解决该问题的基本思路是：⑴先生成长度
为1的高频物品集（即单个物品），记为L[1]，⑵在L[k]的基础上生成候选物品集（can
didate itemset）C[k+1]，候选物品集必须保证包括所有的高频物品集。⑶用事务数据
库D中的事务对C[k+1]进行支持度测试以生成长度为k+1的高频物品集L[k+1]，计算每个
候选物品集的支持度，如果大于minsup，则加入到L[k+1]中（初始为空集）。⑷如果L[
k+1]为空集，则结束，所求结果即为L[1]è L[2]è ···；否则转2，继续。
由上述描述可看出，计算关联规则的关键是如何高效地求出高频物品集。目前在关联规
则发现的研究论文中，提出的好几种方法都是围绕此问题而来的。下面介绍一种称作Ap
riori的方法。Apriori是Agrawal等提出的算法[1]，其原理是如果物品集X是高频物品集
，则X的任一子集必定也是高频物品集；反过来说，如果X有一子集不是高频物品集，则
X肯定也不是。因此，如果已经生成了L[k]，则可根据L[k]来生成C[k+1]；由于C[k+1]中
的候选物品集的长度为k+1，因此要求它的每个子集，比如长度为k-1的物品子集是集合
L[k]中的元素。这样就保证了L[k+1]包含在C[k+1]中了。注意，由L[k]生成C[k+1]的过
程与事务数据库无关。但是，为了检验C[k+1]中的物品集是否是高频物品集，则需要依
据事务数据库。
泛化关联规则发现算法
实际情况下，物品概念间存在一种层次关系（is-a taxonomy），如夹克衫、滑雪衫属于
外套类，外套、衬衣又属于衣服类（称前者为下层物品，后者为上层物品）。有了层次
关系后，可以帮助发现一些更多的有意义的规则。例如，“买外套T 买鞋子”（此处，
外套和鞋子是教高层次上的物品或概念，因而该规则是一种泛化的关联规则[66]）。由
于商店或超市中有成千上万中物品，平均来讲，每种物品（如滑雪衫）的支持度很低，
因此有时难以发现有用规则；但如果考虑到较高层次的物品（如外套），则其支持度就
较高，从而可能发现有用的规则。
发现泛化规则不是一件平凡的任务，它有一些新的特点。例如，“买外套T 买鞋子”可
能成立，但“买夹克衫T 买鞋子”和“买衣服T 买鞋子”不一定成立；又如，“买外套
T 买鞋子”此规则的支持度一般并不等于“买滑雪衫T 买鞋子”和“买夹克衫T 买鞋子
”的支持度之和（假设外套下层只有滑雪衫和夹克衫两种物品）。因此我们需要对前面
的概念或定义做一些补充修改。如下：
设F是一个有向无环图，表示物品的分类层次。用DAG的原因是，物品间存在多种分类情
况，如可以按价格分类，也可以按种类分类，或者按型号分类等等；而DAG相当于一个森
林（多个分类层次树）。F上的每个节点是一个物品或物品种类，F上的有向边表示is-a
关系，如果从物品p有边到物品c，则称物品p是c的父亲，而c是p的孩子。如果在F的传递
闭包图中有一条边从x'到x（或说从x'经有限条边可到达x），则称x'是x的祖先；今后，
x的祖先就记作x'。
设I＝{i1,i2,...,im}是一组物品集，每个物品是F上的一个节点；注意，对于非泛化关
联规则发现，物品仅仅是F的叶子节点（不是任何节点的父亲）。称事务T支持物品x，如
果x∈I或x是T中某些物品的祖先。称事务T支持物品集X，如果T支持X中的每一个物品。
泛化关联规则是如下形式的一种蕴含：XT Y，其中XI，YI，X∩Y＝，且Y中不存在
任何一个物品是X中某些物品的祖先。称物品集Z'是物品集Z的祖先，如果Z'中的物品都
来源于Z中物品的祖先，且Z'和Z中的物品个数一样。例如Z'＝{z1',...,zj',...,zn} 是
Z={z1,...,zn}的祖先，其中z1'到zj'分别是z1到zj的祖先且不同于它们。称规则X'T Y
'，XT Y'，X'T Y是XT Y的祖先。称规则X'T Y'是XT Y的最近祖先（close ancestor），
如果不存在某个规则是X'T Y'的子孙且是XT Y的祖先。物品集Z＝X＋Y基于Z'之上的期望
支持度：E[Z',Z]＝Pr(Z')*(Pr(z1)/Pr(z1')*...*Pr(zj)/Pr(zj'))。规则XT Y基于X'T
Y'之上的期望可信度：E[X'T Y',XT Y]＝Pr(Y'|X')*(Pr(y1)/Pr(y1')*...*Pr(yj)/Pr
(yj'))。称规则XT Y对于规则X'T Y'是R-兴趣度（R-interesting），如果XT Y的支持度
（可信度）等于R乘以规则XT Y基于X'T Y'之上的期望支持度（可信度）。给定一组规则
S和最小兴趣度R，称规则XT Y在S中有趣（interesting），如果它在S中没有祖先，或它
对它的最近祖先具有R-兴趣度。
泛化关联规则发现任务或问题是：给定一个事务数据库D，求出所有满足最小支持度min
sup和最小可信度minconf，以及最小兴趣度min-interest的关联规则。该问题可以分解
为两个子问题：①求出D中满足最小支持度minsup的所有高频物品集；②利用高频物品集
生成满足最小可信度的所有关联规则。
该问题可以分解为三个子问题：①求出D中满足最小支持度minsup的所有高频物品集；②
利用高频物品集生成满足最小可信度的所有关联规则。③剪去所有的不满足最小兴趣度
的规则。
泛化关联规则发现的基本算法是：对每个事务进行变换，把该事务中的所有物品的所有
祖先加入其中，形成扩展事务（extended transaction）。然后用已有的关联规则发现
算法进行处理，求出高频物品集。
多级关联规则发现
泛化关联规则发现的思路是R.Srikant和R.Agrawal提出的，而Han和Fu[32]则提出了另一
种方法－多级关联规则发现。该方法的思路是，对事务数据库中的物品用高层次上的物
品进行替换，对不同层次上的物品进行高频物品集的求解，由于考虑到不同层次级上的
物品的支持度的区别，因此对每个层次上的最小支持度都有不同设置。开始时，所有物
品替换为最高层次上（最抽象）的物品，对此时的最小支持度设置较高。找出满足此处
要求的高频物品集L[1]（包括L[1,1],L[1,2]等等，L[i,j]中，i表示层次，j表示物品数
，如L[1,2]表示层次１上的物品数为２的高频物品集）。在L[1]基础上，将层次１降为
２，设置较小一些的最小支持度，求出L[2]。反复进行，直至L[k]为空。具体实现上，
采用了事务编码技术（hierarchy-information encoded transaction）。如某个事务的
编码表示是：{T1, {111,121,211,221} }。T1表示事务标识符，111等表示物品。对于2
11来讲，其含义是，第一位２表示最高一层（即最抽象层）上的物品编号为２（如牛奶
），第二位１表示第二层上的物品编号为１（如酸牛奶），第三位１表示第三层上的物
品编号为１（如北京酸牛奶）。

--


<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]

Algorithm 版 (精华区)