第八章 关联规则(1)

第八章关联规则本章目标解释关联规则技术的建模特性。分析大型数据库的基本特性。描述Apriori算法，并通过示例来解释算法的所有步骤。将频繁模式增长方法同Apriori算法进行比较。概述从频繁集中产生关联规则的方法。第八章关联规则本章目标举例说明使用HITs、LOGSOM和路径遍历算法来进行Web挖掘的可行性。在指定提炼和萃取阶段的基础上定型文本挖掘的构架。关联规则是数据挖掘的主要技术之一，也是在无指导学习系统中挖掘本地模式的最普遍形式。本章除了重点介绍关联规则挖掘的Apriori技术外，还将讨论一些和Web挖掘、文本挖掘相关的数据挖掘方法。8.1购物篮分析购物篮是顾客在一次事务中所购买项的集合，所谓事务是一个明确定义的商业行为。事务数据库研究的一个最普通的例子就是寻找项的集合，或叫做项集。包含i个项的项集被称为i-项集。包含该项集的事务的百分数叫做该项集的支持度。支持度超过指定阈值的项集叫做频繁项集。基本概念：设I={i1,i2,…im}是项的集合，DB为事务集合，其中每个事务T是项的集合，且有。每一个事务有一个标识符，称作TID。设X为一个项集，当且仅当时，即T包含X。关联规则是形如的蕴涵式，其中,,且。规则在事务集DB中成立，具有支持度s，其中s是DB中事务包含X和Y两者的百分比。规则在事务集DB中具有置信度c，如果DB中包含X的事务同时也包含Y的百分比是c。YXITTXIXIXYXYXYX支持度是概率。置信度是概率。置信度可以表示规则的可信性，支持度表示模式在规则中出现的频率。具有高置信度和强支持度的规则被称为强规则。挖掘关联规则的问题可以分两个阶段：1.发掘大项集，也就是事务支持度s大于预先给定的最小阈值的项的集合。2.使用大项集来产生数据库中置信度c大于预先给定的最小阈值的关联规则。Apriori算法是解决这个问题的常用方法。Y)P(XX)|P(Y8.2APRIORI算法Apriori算法利用几次迭代来计算数据库中的频繁项集。第i次迭代计算出所有频繁i项集(包含i个元素的项集)。每一次迭代有两个步骤：产生候选集；计算和选择候选集。在第一次迭代中，产生的候选集包含所有1-项集，并计算其支持度s，s大于阈值的1-项集被选为频繁1-项集。第二次迭代时，Apriori算法首先去除非频繁1-项集，在频繁1-项集的基础上进行产生频繁2-项集。原理是：如果一个项集是频繁，那么它的所有子集也是频繁的。例如，以表8-1中的数据为例。假设smin=50%。在第一次迭代的第一步中，所有单项集都作为候选集，产生一个候选集列表。在下一步中，计算每一项的支持度，然后在smin的基础上选择频繁项集。图8-1中给出第一次迭代的结果。在挖掘2-项集时，因为2-项集的任何子集都是频繁项集，所以Apriori算法使用L1*L1来产生候选集。*运算通常定义为：Lk*Lk={X∪Y其中X,Y∈Lk,|X∩Y|=k+1}注:|X∩Y|=k+1即X和Y合取容量为k+1当k=1时，因此，C2包含在第二次迭代中作为候选集由运算|L1|·|L1-1|/2所产生的2-项集。本例中为：4·3/2=6。用该列表来扫描DB，计算每一个候选集的s，并与smin比较2-项集L2。图8-2给出了所有这些步骤和第二次迭代的结果。候选集C3运用L2*L2来产生，运算结果得到{A,B,C},{A,C,E},{B,C,E}，但只有{B,C,E}的所有子集是频繁项集，成为候选的3-项集。然后扫描DB，并且挖掘出频繁3-项集，见图8-3所示。因为本例的L3无法产生候选的4-项集，所以算法停止迭代过程。该算法不仅计算所有频繁集的s，也计算那些没有被删除的非频繁候选集的s。所有非频繁但被算法计算s的候选项集的集合被称为负边界。因此，如果项集非频繁的，但它的子集都是频繁的，那么它就在负边界之中。在本例中，负边界由项集{D},{A,B},{A,E}组成。负边界在一些Apriori的改进算法中更为重要，例如生成大项集或导出负关联规则时提高了有效性。8.3从频繁项集得到关联规则第二阶段的工作是在第一阶段的基础上，来挖掘关联规则。如果规则为{x1,x2,x3}→x4，那么项集{x1,x2,x3,x4}和{x1,x2,x3}都必须是频繁的。然后，规则置信度c=P({x4}|{x1,x2,x3})=s(x1,x2,x3,x4)/s(x1,x2,x3)。置信度c大于给定的阈值的规则就是强规则。例如，检验表8-1DB中的关联规则{B,C}→{E}是否为强关联规则。由图8-2和图8-3可得支持度：s(B,C)=2,s(B,C,E)=2由支持度得置信度：c({B,C}→{E})=s(B,C,E)/s(B,C)=2/2=1(100%)可见，无论阈值为多少，该规则都能通过，也就是说，如果事务包含B和C，那么它也将包含E。我们现在有目标是在DB频繁集中得到所有的强关联规则。请注意:并不是所有的强关联规则都是有用的或者有意义的。例如，一个谷类早餐的零售商对5000名学生的调查的案例。数据表明：60%的学生打篮球，75%的学生吃这类早餐，40%的学生即打篮球吃这类早餐。假设支持度阈值s=0.4，置信度阈值c=60%。基于上面数据和假设我们可挖掘出强关联规则“(打篮球)→(吃早餐)”，因为其(打篮球)和(吃早餐)的支持度都大于支持度阈值，都是频繁项，而规则的置信度c=40%/60%=66.6%也大于置信度阈值。然而，以上的关联规则很容易产生误解，因为吃早餐的比例为75%，大于66%。也就是说，打篮球与吃早餐实际上是负关联的。为了消除这种误导的规则，应该在关联规则A→B的置信度超过某个特定的度量标准时，定义它为有意义的。因此挖掘关联规则的正确方法是：s(A,B)/s(A)-s(B)d或者：s(A,B)-s(A)·s(B)k式中d或k是适当的常量。（计算上例）8.4提高Apriori算法的效率因为挖掘频繁项集时所处理的数据量越来越大，所以很有必要提高算法的效率。Apriori算法扫描DB的次数完全依赖于最大的频繁项集中项的数量。为了解决这个问题，该算法作了一些改进。基于划分的Apriori算法只需要对DB进行两次扫描。DB被划分成若干个非重叠的分区，分区与内存相匹配。在第一次扫描时，算法读取每一个分区，每个分区内计算局部频繁项集。在第二次扫描时，算法计算整个DB中所有局部频繁集的支持度。如果项集对于整个数据库来说是频繁的，那么它至少需要在一个分区中是频繁的。因此，第二次扫描完成计算所有潜在的频繁项集的超集。随着数据库大小的增加，取样成为数据挖掘的一个不可多得的有效途径，基于取样的算法需要以数据库进行两次扫描。第一次扫描，从DB中选择一个样本，并且产生一个在整个DB中很可能为频繁的候选项集的集合。第二次扫描，算法计算这些项集的实际支持度和它们的负边界的支持度。如果在负边界中没有项集是频繁的，那么说明已挖掘出所有频繁项集。否则，负边界中的项集的一些超集可能就是频繁的，但它的支持度还没有计算出来。取样算法在随后的扫描时，会产生并计算所有这些潜在有频繁项集。图8-4是实际应用的一个例子，该例揭示这样一个问题，事务数据库中的购买模式在最低层上不会显示任何规则，但在一些高的概念层可能会显示一些有意义的规则。Apriori算法的一个扩展在DB项上涉及到is-a层次，它包含数据库结构中已经存在的多抽象层的信息。is-a层次定义哪些项是其他项的一般化或专门化。除了明确列出的项以外，事务还以分类的方式包含了它们的祖先，这样就可以发掘出高层次的关系。8.5频繁模式增长方法(FP-增长方法）一个Apriori算法的可伸缩的问题。如果生成一个长度100的频繁模式，例如{a1,a2,…,a100}，那么所产生的候选集的数量至少为：计算的复杂性成指数增长，这是影响一些新关联规则挖掘算法发展的一个主要因素。301001001012100ii频繁模式增长(FP-growth)方法是在大型数据中挖掘频繁项集的一个有效算法。算法进行中不存在产生候选集的繁琐过程，当DB很大时，FP-增长算法首先进行数据库投影，得到频繁集，然后通过构造一个压缩的数据库结构---FP-树再进行挖掘。例如，表8-3给出DB，它的最小支持度阈值为3。第一步，扫描T，得到频繁集的列表L:L={(f,4),(c,4),(a,3),(b,3),(m,3),(p,3)}按支持度大小递减排列。第二步，创建树的根部(ROOT)，第二次扫描T。对第一个事务的扫描得树的第一个分枝:{(f,1),(c,1),(a,1),(b,1),(m,1),(p,1)}。分枝中节点的计数(都是1)代表了树中该节点项所出现的次数，并按Ｌ中顺序排列。对第二个事务，与第一事务有相同项f,c,a，所有有同一个前缀(f,c,a)，得到一个新的分枝{(f,2),(c,2),(a,2),(b,1),(m,1)}，见图8-5a。其他事务按同样的方式插入到FP-树中，图8-5b给出了最后的FP-树。按照频繁项的表L，整个频繁项的集合被划分为几个没有重叠的子集:1)含有p的频繁项集；2)含有m但不含有p的频繁项集；3)含有b但不含有m,p的频繁项集；…；6)只含有f的大项集。1)有两个路径{(f,4),(c,3),(a,3),(m,2),(p,2)}和{(c,1),(b,1),(p,1)},根据阈值产生新的频繁项集(c,p)2)有两个路径{(f,4),(c,3),(a,3),(m,2)}和{(f,4),(c,3),(a,3),(b,1),(m,1)},满足阈值的频繁项集是{f,c,a,m}。同样地，我们可得到第三到第六个子集，再挖出满足阈值的频繁项集。它们是{f,c,a}和{f,c}，但这两个都是{f,c,a,m}的子集，最终得到频繁集是{c.p}和{f,c,a,m}。FP-增长算法要比Apriori算法大约快一个数据级。它还增加了一些优化技术，并且在约束条件下挖掘排序和模式时还存在其他版本的算法。