数据挖掘の基本关联分析

第6章：关联分析—基本概念和算法数据挖掘导论 主讲：杜剑峰 4/18/20101关联分析的预备知识频繁项集产生规则产生关联模式的评估目的：介绍关联分析的基本概念、关联规则挖掘的基本方法，以及关联模式评估的度量要求：掌握关联规则挖掘的Apriori算法，了解关联规则挖掘的其他方法，熟悉关联模式评估的典型度量重点：用于频繁项集产生和规则产生的Apriori算法难点：使用散列树（HashTree）的支持度计算方法第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估关联分析给定一组事务，寻找预测“某些项将会随其他项的出现而出现”的规则挖掘关联规则购物篮事务数据库关联规则的例子{Diaper}{Beer},

{Milk,Bread}{Eggs,Coke},

{Beer,Bread}{Milk},蕴含符号“”表示共现关系，而不是因果关系定义:频繁项集项集一个或多个项的集合例子:{Milk,Bread,Diaper}k-项集包含k个项的项集支持度计数(supportcount)给定项集的出现次数比如({Milk,Bread,Diaper})=2支持度(support)覆盖给定项集的事务数占所有事务数的比例比如s({Milk,Bread,Diaper})=2/5=40%频繁项集支持度大于等于给定阈值

minsup

的项集定义:关联规则例子:关联规则形式为XY的蕴含表达式，其中X和Y是项集例子:

{Milk,Diaper}{Beer}

规则评估度量支持度(s)s(XY)=(X∪Y)/|T|包含X和Y的事务个数占所有事务个数的比例置信度(c)c(XY)=(X∪Y)/(X)在包含X的事务集合中，包含Y的事务个数占事务总数的比例关联规则挖掘任务给定一个事务集合T，关联规则挖掘的目标是寻找所有满足下面条件的规则支持度≥minsup置信度≥minconfBrute-force（蛮力）方法:列出所有可能的关联规则计算每条规则的支持度和置信度删除支持度不足minsup或置信度不足minconf的规则 代价极高!

因为从包含d个项的数据集提取的可能规则的总数是R=3d-2d+1+1，比如d=6则R=602挖掘关联规则规则的例子:

{Milk,Diaper}{Beer}(s=0.4,c=0.67)

{Milk,Beer}{Diaper}(s=0.4,c=1.0){Diaper,Beer}{Milk}(s=0.4,c=0.67){Beer}{Milk,Diaper}(s=0.4,c=0.67)

{Diaper}{Milk,Beer}(s=0.4,c=0.5){Milk}{Diaper,Beer}(s=0.4,c=0.5)观察结果:

上面所有的规则都是同一个项集的二分:{Milk,Diaper,Beer}

由同一个项集得到的规则具有相同的支持度和不同的置信度

因此，我们可以将支持度和置信度分开处理挖掘关联规则两步方法:频繁项集的产生产生支持度

minsup

的所有项集规则的产生由每个频繁项集产生置信度

minconf

的规则，其中每个规则都是该频繁项集的二分第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估频繁项集的产生给定d个项，一共有2d

个项集频繁项集的产生Brute-force（蛮力）方法:在项集格中的每个项集都是一个候选频繁项集扫描事务数据库计算每个候选频繁项集的支持度将每个事务与每个候选频繁项集匹配比较次数~O(NMw)=>代价极高，因为M=2d

!!!第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估频繁项集产生的优化策略减少候选频繁项集的个数(M)完全搜索:M=2d使用剪枝计数减少M减少事务的个数

(N)当项集的大小增加时，减少N在基于垂直数据分布的挖掘算法中使用减少比较的次数(NM)使用高效的数据结构保存候选频繁项集或事务不需要匹配每个候选和每个事务垂直数据分布优化策略1:减少候选频繁项集的个数先验原理（Aprioriprinciple）:如果一个项集是频繁的，那么它的所有子集都是频繁的先验原理成立的原因:一个项集的支持度不会超过其任何子集的支持度该性质称作支持度的反单调性质发现是非频繁的先验原理的图示被剪枝的超集先验原理的图示1-项集2-项集(不需要生成涉及Coke或Eggs的候选频繁项集)3-项集最小支持度计数=3如果考虑所有项集，6C1+6C2+6C3=41使用基于支持度的剪枝，6+6+1=13Apriori算法算法流程:设定k=1扫描事务数据库一次，生成频繁的1-项集如果存在两个或以上频繁k-项集，重复下面过程：[候选产生]

由长度为k的频繁项集生成长度为k+1的候选项集[候选前剪枝]

对每个候选项集，若其具有非频繁的长度为k的子集，则删除该候选项集[支持度计算]

扫描事务数据库一次，统计每个余下的候选项集的支持度[候选后剪枝]

删除非频繁的候选项集，仅保留频繁的(k+1)-项集设定k=k+1Apriori算法的核心步骤候选产生 设A={a1,a2,…,ak}和B={b1,b2,…,bk}是一对频繁k-项集，当且仅当ai=bi(i=1,2,k-1)并且ak≠bk时，合并A和B，得到{a1,a2,…,ak,bk}比如合并{Bread,Milk}和{Bread,Diaper}得到{Bread,Milk,Diaper}，但{Milk,Bread}和{Bread,Diaper}不能合并候选前剪枝 设A={a1,a2,…,ak,ak+1}是一个候选(k+1)-项集，检查每个A’是否在第k层频繁项集中出现，其中A’由A去掉ai(i=1,…,k-1)得到

若某个A’没有出现，则A是非频繁的Apriori算法的例子考虑下面的事务数据库最小支持度计数阈值=2Apriori算法的例子…(生成频繁1-项集)(候选产生)(候选后剪枝)(支持度计算)(候选产生和候选前剪枝)(支持度计算)(候选后剪枝)优化策略2:减少比较次数候选项集的支持度计算:扫描事务数据库，决定每个候选项集的支持度为了减少比较次数，将候选项集保存在散列（hash）结构中

将每个事务与保存在散列结构的候选项集作匹配生成候选的散列树2345671451361244571254581593453563576893673681,4,72,5,83,6,9散列函数假设有15个长度为3的候选项集:{145},{124},{457},{125},{458},{159},{136},{234},{567},{345},{356},{357},{689},{367},{368}散列树（hashtree）参数:

散列函数(hashfunction)

叶子大小限制:保存在一个叶子结点的项集个数的上限(如果候选项集的个数超过该限制，则分裂叶子结点)叶子大小限制：3生成候选的散列树1591451363453673683563576892345671244571254581,4,72,5,83,6,9散列函数散列树生成候选的散列树1591451363453673683563576892345671244571254581,4,72,5,83,6,9散列函数散列树生成候选的散列树1591451363453673683563576892345671244571254581,4,72,5,83,6,9散列函数散列树子集操作给定一个事务t，t包含哪些长度为3的可能子集?使用散列树的子集操作159145136345367368356357689234567124457125458123561+23563562+563+1,4,72,5,83,6,9散列函数事务给定一个事务t，t包含散列树中哪些子集?使用散列树的子集操作1591451363453673683563576892345671244571254581,4,72,5,83,6,9散列函数1235635612+5613+615+3562+563+1+2356事务给定一个事务t，t包含散列树中哪些子集?635+使用散列树的子集操作1591451363453673683563576892345671244571254581,4,72,5,83,6,9散列函数1235635612+5613+615+3562+563+1+2356事务给定一个事务t，t包含散列树中哪些子集?9个候选3-项集与事务的当前子集比较635+123125126156第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估计算复杂度的影响因素最小支持度阈值的选择低支持度阈值导致更多频繁项集将会增加候选项集的个数和频繁项集的最大长度数据库的维度，即项的个数需要更多空间保存每个项的支持度计数如果频繁项集的个数增加，则计算量和I/O开销也增加数据库的大小由于Apriori多次访问数据库，算法的运行时间将随事务个数的增加而增加平均事务长度事务长度随数据库密度的增加而增加可能会增加频繁项集的最大长度和散列树的遍历时间（因为事务的子集个数随着其长度的增加而增加）作业将Apriori算法应用于下面的事务数据库，最小支持度为30%，画出Apriori算法的运行过程。P253:10第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估频繁项集的紧凑表示某些项集是冗余的，因为它们具有与它们超集相同的支持度频繁项集的个数需要紧凑的表示最大频繁项集边界非频繁项集最大频繁项集如果一个频繁项集没有任何频繁的直接超集，则该项集称作最大频繁项集频繁闭项集如果一个项集的任何直接超集都不具有和它相同的支持度计数，则该项集称为闭项集如果一个闭项集是频繁的，则它称为频繁闭项集最大频繁项集vs

频繁闭项集事务ID不被任何事务支持最大频繁项集vs

频繁闭项集最小支持度计数=2#频繁闭项集=9#最大频繁项集=4频繁闭项集，而且是最大的频繁闭项集，但不是最大的最大频繁项集、频繁闭项集和频繁项集第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估产生频繁项集的其他方法项集格的遍历一般到特殊vs

特殊到一般产生频繁项集的其他方法项集格的遍历等价类产生频繁项集的其他方法项集格的遍历宽度优先vs

深度优先产生频繁项集的其他方法事务数据库的表示水平数据布局vs

垂直数据布局FP增长算法使用事务数据库的紧凑数据结构－FP树一旦FP树构建完成，该算法使用一个递归的分而治之的方法挖掘频繁项集FP树的构建nullA:1B:1nullA:1B:1B:1C:1D:1读入TID=1后:读入TID=2后:事务数据库中已经去掉非频繁的项，并且事务中余下的项已按照支持度递减排序FP树的构建nullA:7B:5B:3C:3D:1C:1D:1C:3D:1D:1E:1E:1指针用于辅助频繁项集生成D:1E:1事务数据库头指针表FP增长过程nullA:7B:5B:1C:1D:1C:1D:1C:3D:1D:1从D开始开始直到A逐个处理条件模式库关于D的条件模式库是D的所有前缀路径的集合：P={(A:1,B:1,C:1),

(A:1,B:1),

(A:1,C:1),

(A:1),

(B:1,C:1)}对P递归应用FP增长过程发现频繁项集(sup>1):

AD,BD,CD,ACD,BCDD:1ECLAT算法使用垂直数据布局：对于每个项，保存事务ID列表(TID列表)TID列表ECLAT算法通过计算两个k-1子集的TID列表的交集，决定k-项集的TID列表三种遍历方法:自顶向下、自底向上和混合方法优点:计算支持度很快缺点:计算过程产生的TID列表可能占用很大内存

第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估规则产生给定一个频繁项集L，寻找L的所有非空真子集f使fL－f的置信度大于等于给定的置信度阈值如果{A,B,C,D}是频繁项集，则候选的规则包括:ABCD, ABDC, ACDB, BCDA,

ABCD, BACD, CABD, DABC

ABCD, ACBD, ADBC, BCAD,

BDAC, CDAB,

如果|L|=k，则有2k–2个候选的关联规则(忽略L

和L)规则产生如何从频繁项集高效生成规则?一般地说，置信度没有反单调性质比如，c(ABCD)可以大于或小于c(ABD)但从同一个项集生成的规则的置信度具有反单调性质比如，L={A,B,C,D}:

c(ABCD)c(ABCD)c(ABCD)针对规则后件的项集，置信度是反单调的：如果规则XY－X不满足置信度阈值，则形如X’Y－X’的规则也不满足置信度阈值，其中X’是X的子集规则产生的Apriori算法规则格剪掉的规则低置信度规则规则产生的Apriori算法[候选产生]

候选规则通过合并两个具有相同规则后件前缀的规则产生， 比如合并(CD=>AB,BD=>AC)

得到候选规则D=>ABC[候选前剪枝]

如果规则 D=>ABC的子集AD=>BC 不满足置信度阈值，则 删除该规则[置信度计算][候选后剪枝]第6章：关联分析—基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估关联模式评估关联规则算法倾向于产生大量的规则很多产生的规则是不感兴趣的或冗余的如果{A,B,C}{D}和{A,B}{D}具有相同的支持度和置信度，则{A,B,C}{D}是冗余的兴趣度可以用于对产生的规则进行过滤或排序在原来的关联规则定义中，支持度和置信度是唯一使用的度量兴趣度度量客观度量:基于从数据推导出的统计量来确定模式是否有趣比如21个关联度量(支持度、置信度、拉普拉斯、Gini指标、互信息、Jaccard，等等)主观度量:根据用户的解释来确定模式是否有趣

如果一个模式揭示料想不到的信息，那么它是主观有趣的(Silberschatz&Tuzhilin)

如果一个模式是可操作的(actionable)，即提供导致有益行动的有用信息，那么它是主观有趣的(Silberschatz&Tuzhilin)兴趣度的应用兴趣度度量计算客观兴趣度给定规则XY，计算规则兴趣度的信息可以从以下相依表（contingencetable）中获取YYXf11f10f1+Xf01f00fo+f+1f+0|T|规则XY的相依表用于定义不同的度量

支持度、置信度、提升度、Gini、J度量，等等f11:X和Y共现的支持度计数

f10:X和Y共现的支持度计数

f01:X和Y共现的支持度计数

f00:X和Y共现的支持度计数支持度－置信度的局限性CoffeeCoffeeTea15520Tea755809010100支持度的缺点若支持度阈值过高，则许多潜在的有意义的模式被删调若支持度阈值过低，则计算代价很高而且产生大量的关联模式置信度的缺点关联规则:TeaCoffee 置信度 =P(Coffee|Tea) =0.75 但P(Coffee)=0.9 虽然置信度很高，但规则是误导的

置信度忽略了规则前件和后件的统计独立性统计独立性1000个学生的群体600个学生知道如何去游泳(S)700个学生知道如何去骑单车(B)420个学生知道如何去游泳和骑单车(S,B)P(SB)=420/1000=0.42P(S)P(B)=0.60.7=0.42P(SB)=P(S)P(B)=>统计独立P(SB)>P(S)P(B)=>正相关P(SB)<P(S)P(B)=>负相关基于统计的度量部分考虑统计独立性的度量提升度