数据挖掘の基本关联分析.ppt

《数据挖掘の基本关联分析.ppt》由会员分享，可在线阅读，更多相关《数据挖掘の基本关联分析.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法数据挖掘导论 主讲：杜剑峰 4/18/2010 11.关联分析的预备知识关联分析的预备知识2.频繁项集产生频繁项集产生3.规则产生规则产生4.关联模式的评估关联模式的评估l目的：目的：介绍关联分析的基本概念、关联规则挖掘的基本介绍关联分析的基本概念、关联规则挖掘的基本方法，以及关联模式评估的度量方法，以及关联模式评估的度量l要求：要求：掌握关联规则挖掘的掌握关联规则挖掘的Apriori算法，了解关联规则算法，了解关联规则挖掘的其他方法，熟悉关联模式评估的典型度量挖掘的其他方法，熟悉关联模式评估的典型度量l重点：重点：用于频繁项集产生和

2、规则产生的用于频繁项集产生和规则产生的Apriori算法算法l难点：难点：使用散列树（使用散列树（Hash Tree）的支持度计算方法）的支持度计算方法数据挖掘导论 主讲：杜剑峰 4/18/2010 2第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/20

3、10 3关联分析关联分析l给定一组事务，寻找预测“某些项将会随其他项的出现而出现”的规则挖掘挖掘关联规则关联规则购物篮事务数据库购物篮事务数据库关联规则的例子关联规则的例子Diaper Beer,Milk,Bread Eggs,Coke,Beer,Bread Milk,蕴含符号“”表示共现关系，而不是因果关系数据挖掘导论 主讲：杜剑峰 4/18/2010 4定义定义:频繁项集频繁项集l项集项集一个或多个项的集合u例子:Milk,Bread,Diaperk-项集u包含k个项的项集l支持度计数支持度计数(support count)给定项集的出现次数比如(Milk,Bread,Diaper)=2

4、l支持度支持度(support)覆盖给定项集的事务数占所有事务数的比例比如 s(Milk,Bread,Diaper)=2/5=40%l频繁项集频繁项集支持度大于等于给定阈值 minsup 的项集数据挖掘导论 主讲：杜剑峰 4/18/2010 5定义定义:关联规则关联规则例子:l关联规则关联规则形式为 X Y 的蕴含表达式，其中X 和Y是项集例子:Milk,Diaper Beer l规则评估度量规则评估度量支持度(s)us(XY)=(XY)/|T|u包含X和Y的事务个数占所有事务个数的比例置信度(c)uc(XY)=(XY)/(X)u在包含X的事务集合中，包含Y的事务个数占事务总数的比例数据挖掘导

5、论 主讲：杜剑峰 4/18/2010 6关联规则挖掘任务关联规则挖掘任务l给定一个事务集合T，关联规则挖掘的目标是寻找所有满足下面条件的规则支持度 minsup置信度 minconflBrute-force（蛮力）方法:列出所有可能的关联规则计算每条规则的支持度和置信度删除支持度不足minsup或置信度不足minconf的规则代价极高!因为从包含d个项的数据集提取的可能规则的总数是R=3d-2d+1+1，比如d=6则R=602数据挖掘导论 主讲：杜剑峰 4/18/2010 7挖掘关联规则挖掘关联规则规则的例子:Milk,Diaper Beer(s=0.4,c=0.67)Milk,Beer Di

6、aper(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 由同一个项集得到的规则具有相同的支持度和不同的置信度 因此，我们可以将支持度和置信度分开处理数据挖掘导论 主讲：杜剑峰 4/18/2010 8挖掘关联规则挖掘关联规则l两步方法:1.频繁项集的产生产生 支持度minsup 的所有项集2.规则的产生由每

7、个频繁项集产生 置信度minconf 的规则，其中每个规则都是该频繁项集的二分数据挖掘导论 主讲：杜剑峰 4/18/2010 9第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 10频繁项集的产生频繁项集的产生给定给定d个项，一共有个项，一共有2

8、d 个项集个项集数据挖掘导论 主讲：杜剑峰 4/18/2010 11频繁项集的产生频繁项集的产生lBrute-force（蛮力）方法:在项集格中的每个项集都是一个候选频繁项集扫描事务数据库计算每个候选频繁项集的支持度将每个事务与每个候选频繁项集匹配比较次数 O(NMw)=代价极高，因为M=2d!数据挖掘导论 主讲：杜剑峰 4/18/2010 12第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧

9、凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 13频繁项集产生的优化策略频繁项集产生的优化策略l减少候选频繁项集的个数(M)完全搜索:M=2d使用剪枝计数减少Ml减少事务的个数(N)当项集的大小增加时，减少N在基于垂直数据分布的挖掘算法中使用l减少比较的次数(NM)使用高效的数据结构保存候选频繁项集或事务不需要匹配每个候选和每个事务垂直数据分布垂直数据分布数据挖掘导论 主讲：杜剑峰 4/18/2010 14优化策略优化策略1:减少候选频繁项集的个数减少候选频繁项集的个数l先验原理（Apri

10、ori principle）:如果一个项集是频繁的，那么它的所有子集都是频繁的l先验原理成立的原因:一个项集的支持度不会超过其任何子集的支持度该性质称作支持度的反单调反单调性质数据挖掘导论 主讲：杜剑峰 4/18/2010 15发现是非频繁的先验原理的图示先验原理的图示被剪枝的超集数据挖掘导论 主讲：杜剑峰 4/18/2010 16先验原理的图示先验原理的图示1-项集2-项集(不需要生成涉及Coke或 Eggs的候选频繁项集)3-项集最小支持度计数=3如果考虑所有项集，6C1+6C2+6C3=41使用基于支持度的剪枝，6+6+1=13数据挖掘导论 主讲：杜剑峰 4/18/2010 17Apri

11、ori算法算法l算法流程:设定k=1扫描事务数据库一次，生成频繁的1-项集如果存在两个或以上频繁k-项集，重复下面过程：候选产生候选产生 由长度为k的频繁项集生成长度为k+1的候选项集候选前剪枝候选前剪枝 对每个候选项集，若其具有非频繁的长度为k的子集，则删除该候选项集支持度计算支持度计算 扫描事务数据库一次，统计每个余下的候选项集的支持度候选后剪枝候选后剪枝 删除非频繁的候选项集，仅保留频繁的(k+1)-项集设定k=k+1数据挖掘导论 主讲：杜剑峰 4/18/2010 18Apriori算法的核心步骤算法的核心步骤l候选产生设A=a1,a2,ak和B=b1,b2,bk是一对频繁k-项集，当且

12、仅当ai=bi(i=1,2,k-1)并且akbk时，合并A和B，得到a1,a2,ak,bk比如合并Bread,Milk和Bread,Diaper得到Bread,Milk,Diaper，但Milk,Bread和Bread,Diaper不能合并l候选前剪枝设A=a1,a2,ak,ak+1是一个候选(k+1)-项集，检查每个A是否在第k层频繁项集中出现，其中A由A去掉ai(i=1,k-1)得到 若某个A没有出现，则A是非频繁的数据挖掘导论 主讲：杜剑峰 4/18/2010 19Apriori算法的例子算法的例子l考虑下面的事务数据库l最小支持度计数阈值=2数据挖掘导论 主讲：杜剑峰 4/18/201

13、0 20Apriori算法的例子算法的例子(生成频繁生成频繁1-项集项集)(候选产生候选产生)(候选后剪枝候选后剪枝)(支持度支持度计算计算)(候选产生和候选产生和候选前剪枝候选前剪枝)(支持度支持度计算计算)(候选后剪枝候选后剪枝)数据挖掘导论 主讲：杜剑峰 4/18/2010 21优化策略优化策略2:减少比较次数减少比较次数l候选项集的支持度计算:扫描事务数据库，决定每个候选项集的支持度为了减少比较次数，将候选项集保存在散列（hash）结构中u 将每个事务与保存在散列结构的候选项集作匹配数据挖掘导论 主讲：杜剑峰 4/18/2010 22生成候选的散列树生成候选的散列树2 3 45 6 7

14、1 4 51 3 61 2 44 5 71 2 54 5 81 5 93 4 53 5 63 5 76 8 93 6 73 6 81,4,72,5,83,6,9散列函数散列函数假设有假设有15个长度为个长度为3的候选项集的候选项集:1 4 5,1 2 4,4 5 7,1 2 5,4 5 8,1 5 9,1 3 6,2 3 4,5 6 7,3 4 5,3 5 6,3 5 7,6 8 9,3 6 7,3 6 8散列树（散列树（hash tree）参数）参数:散列函数散列函数(hash function)叶子大小限制叶子大小限制:保存在一个叶子结点的项集个数的上限保存在一个叶子结点的项集个数的上限(

15、如果候选项集的个数超如果候选项集的个数超过该限制，则分裂叶子结点过该限制，则分裂叶子结点)叶子大小限制：叶子大小限制：3数据挖掘导论 主讲：杜剑峰 4/18/2010 23生成候选的散列树生成候选的散列树1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9散列函数散列树散列树数据挖掘导论 主讲：杜剑峰 4/18/2010 24生成候选的散列树生成候选的散列树1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71

16、 2 44 5 71 2 54 5 81,4,72,5,83,6,9散列函数散列树散列树数据挖掘导论 主讲：杜剑峰 4/18/2010 25生成候选的散列树生成候选的散列树1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9散列函数散列树散列树数据挖掘导论 主讲：杜剑峰 4/18/2010 26子集操作子集操作给定一个事务t，t包含哪些长度为3的可能子集?数据挖掘导论 主讲：杜剑峰 4/18/2010 27使用散列树的子集操作使用散列树的子集操作1 5 91 4 51

17、 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81 2 3 5 61+2 3 5 63 5 62+5 63+1,4,72,5,83,6,9 散列函数事务给定一个事务t，t包含散列树中哪些子集?数据挖掘导论 主讲：杜剑峰 4/18/2010 28使用散列树的子集操作使用散列树的子集操作1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9 散列函数1 2 3 5 63 5 61 2+5 61

18、3+61 5+3 5 62+5 63+1+2 3 5 6事务给定一个事务t，t包含散列树中哪些子集?63 5+数据挖掘导论 主讲：杜剑峰 4/18/2010 29使用散列树的子集操作使用散列树的子集操作1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9 散列函数1 2 3 5 63 5 61 2+5 61 3+61 5+3 5 62+5 63+1+2 3 5 6事务给定一个事务t，t包含散列树中哪些子集?9个候选3-项集与事务的当前子集比较63 5+1 2 31 2

19、 51 2 61 5 6数据挖掘导论 主讲：杜剑峰 4/18/2010 30第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 31计算复杂度的影响因素计算复杂度的影响因素l最小支持度阈值的选择低支持度阈值导致更多频繁项集将会增加候选项集的个数和频

20、繁项集的最大长度l数据库的维度，即项的个数需要更多空间保存每个项的支持度计数如果频繁项集的个数增加，则计算量和 I/O开销也增加l数据库的大小由于Apriori多次访问数据库，算法的运行时间将随事务个数的增加而增加l平均事务长度事务长度随数据库密度的增加而增加可能会增加频繁项集的最大长度和散列树的遍历时间（因为事务的子集个数随着其长度的增加而增加）数据挖掘导论 主讲：杜剑峰 4/18/2010 32作业作业1.将Apriori算法应用于下面的事务数据库，最小支持度为30%，画出Apriori算法的运行过程。2.P253:10数据挖掘导论 主讲：杜剑峰 4/18/2010 33第第6章：关联分析

21、章：关联分析 基本概念和算法基本概念和算法1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 34频繁项集的紧凑表示频繁项集的紧凑表示l某些项集是冗余的，因为它们具有与它们超集相同的支持度l频繁项集的个数l需要紧凑的表示数据挖掘导论 主讲：杜剑峰 4/18/2010 35最大频繁项集最大频繁项集边界边界非频

22、繁项非频繁项集集最大频繁最大频繁项集项集如果一个频繁项集没有任何频繁的直接超集，则该项集称作最大频繁项集最大频繁项集数据挖掘导论 主讲：杜剑峰 4/18/2010 36频繁闭项集频繁闭项集l如果一个项集的任何直接超集都不具有和它相同的支持度计数，则该项集称为闭项集闭项集l如果一个闭项集是频繁的，则它称为频繁闭项集频繁闭项集数据挖掘导论 主讲：杜剑峰 4/18/2010 37最大频繁项集最大频繁项集 vs 频繁闭项集频繁闭项集事务事务ID不被任何事务支持不被任何事务支持数据挖掘导论 主讲：杜剑峰 4/18/2010 38最大频繁项集最大频繁项集 vs 频繁闭项集频繁闭项集最小支持度计数最小支持度

23、计数=2#频繁闭项集频繁闭项集=9#最大频繁项集最大频繁项集=4频繁闭项集，频繁闭项集，而且是最大的而且是最大的频繁闭项集，频繁闭项集，但不是最大的但不是最大的数据挖掘导论 主讲：杜剑峰 4/18/2010 39最大频繁项集、频繁闭项集和频繁项集最大频繁项集、频繁闭项集和频繁项集数据挖掘导论 主讲：杜剑峰 4/18/2010 40第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁

24、项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 41产生频繁项集的其他方法产生频繁项集的其他方法l项集格的遍历一般到特殊 vs 特殊到一般数据挖掘导论 主讲：杜剑峰 4/18/2010 42产生频繁项集的其他方法产生频繁项集的其他方法l项集格的遍历等价类数据挖掘导论 主讲：杜剑峰 4/18/2010 43产生频繁项集的其他方法产生频繁项集的其他方法l项集格的遍历宽度优先 vs 深度优先数据挖掘导论 主讲：杜剑峰 4/18/2010 44产生频繁项集的其他方法产生频繁项集的其他方法l事务数据库的表示水平数据布

25、局 vs 垂直数据布局数据挖掘导论 主讲：杜剑峰 4/18/2010 45FP增长算法增长算法l使用事务数据库的紧凑数据结构 FP树l一旦FP树构建完成，该算法使用一个递归的分而治之的方法挖掘频繁项集数据挖掘导论 主讲：杜剑峰 4/18/2010 46FP树的构建树的构建nullA:1B:1nullA:1B:1B:1C:1D:1读入读入 TID=1 后后:读入读入 TID=2 后后:事务数据库中已经去掉非频事务数据库中已经去掉非频繁的项，并且繁的项，并且事务中事务中余下的余下的项已按照支持度递减排序项已按照支持度递减排序数据挖掘导论 主讲：杜剑峰 4/18/2010 47FP树的构建树的构建n

26、ullA:7B:5B:3C:3D:1C:1D:1C:3D:1D:1E:1E:1指针用于辅助频繁项集生成指针用于辅助频繁项集生成D:1E:1事务数据库事务数据库头指针表头指针表数据挖掘导论 主讲：杜剑峰 4/18/2010 48FP增长过程增长过程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增长过

27、程增长过程发现频繁项集发现频繁项集(sup 1):AD,BD,CD,ACD,BCDD:1数据挖掘导论 主讲：杜剑峰 4/18/2010 49ECLAT算法算法l使用垂直数据布局：对于每个项，保存事务ID列表(TID列表)TID列表列表数据挖掘导论 主讲：杜剑峰 4/18/2010 50ECLAT算法算法l通过计算两个k-1子集的TID列表的交集，决定k-项集的TID列表l三种遍历方法:自顶向下、自底向上和混合方法l优点:计算支持度很快l缺点:计算过程产生的TID列表可能占用很大内存 数据挖掘导论 主讲：杜剑峰 4/18/2010 51第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法

28、1.关联分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 52规则产生规则产生l给定一个频繁项集L，寻找L的所有非空真子集 f 使 f Lf 的置信度大于等于给定的置信度阈值如果A,B,C,D是频繁项集，则候选的规则包括:ABC D,ABD C,ACD B,BCD A,A BCD,B ACD,C ABD,D AB

29、CAB CD,AC BD,AD BC,BC AD,BD AC,CD AB,l如果|L|=k，则有2k 2个候选的关联规则(忽略 L 和 L)数据挖掘导论 主讲：杜剑峰 4/18/2010 53规则产生规则产生l如何从频繁项集高效生成规则?一般地说，置信度没有反单调性质u 比如，c(ABC D)可以大于或小于 c(AB D)但从同一个项集生成的规则的置信度具有反单调性质u 比如，L=A,B,C,D:c(ABC D)c(AB CD)c(A BCD)u 针对规则后件的项集，置信度是反单调的：如果规则 X YX 不满足置信度阈值，则形如XYX的规则也不满足置信度阈值，其中X是X的子集数据挖掘导论 主讲

30、：杜剑峰 4/18/2010 54规则产生的规则产生的Apriori算法算法规则格剪掉的规剪掉的规则则低置信度规低置信度规则则数据挖掘导论 主讲：杜剑峰 4/18/2010 55规则产生的规则产生的Apriori算法算法l候选产生候选产生 候选规则通过合并两个具有相同规则后件前缀的规则产生，比如合并(CD=AB,BD=AC)得到候选规则D=ABCl候选前剪枝候选前剪枝 如果规则D=ABC的子集AD=BC不满足置信度阈值，则删除该规则l置信度计算置信度计算l候选后剪枝候选后剪枝数据挖掘导论 主讲：杜剑峰 4/18/2010 56第第6章：关联分析章：关联分析 基本概念和算法基本概念和算法1.关联

31、分析的预备知识关联分析的预备知识2.频繁项集的产生频繁项集的产生l频繁项集产生的优化策略频繁项集产生的优化策略l计算复杂度的影响因素计算复杂度的影响因素l频繁项集的紧凑表示频繁项集的紧凑表示l产生频繁项集的其他方法产生频繁项集的其他方法3.规则产生规则产生4.关联模式的评估关联模式的评估数据挖掘导论 主讲：杜剑峰 4/18/2010 57关联模式评估关联模式评估l关联规则算法倾向于产生大量的规则很多产生的规则是不感兴趣的或冗余的如果 A,B,C D 和 A,B D 具有相同的支持度和置信度，则A,B,C D 是冗余的l兴趣度可以用于对产生的规则进行过滤或排序l在原来的关联规则定义中，支持度和置

32、信度是唯一使用的度量数据挖掘导论 主讲：杜剑峰 4/18/2010 58兴趣度度量兴趣度度量l客观度量:基于从数据推导出的统计量来确定模式是否有趣比如21个关联度量(支持度、置信度、拉普拉斯、Gini指标、互信息、Jaccard，等等)l主观度量:根据用户的解释来确定模式是否有趣u 如果一个模式揭示料想不到的信息，那么它是主观有趣的 (Silberschatz&Tuzhilin)u 如果一个模式是可操作的(actionable)，即提供导致有益行动的有用信息，那么它是主观有趣的 (Silberschatz&Tuzhilin)数据挖掘导论 主讲：杜剑峰 4/18/2010 59兴趣度的应用兴趣度

33、的应用兴趣度度量数据挖掘导论 主讲：杜剑峰 4/18/2010 60计算客观兴趣度计算客观兴趣度l给定规则 X Y，计算规则兴趣度的信息可以从以下相依表相依表（contingence table）中获取YY Xf11f10f1+X f01f00fo+f+1f+0|T|规则X Y的相依表用于定义不同的度量u 支持度、置信度、提升度、Gini、J度量，等等f11:X和Y共现的支持度计数f10:X和Y共现的支持度计数f01:X和Y共现的支持度计数f00:X和Y共现的支持度计数数据挖掘导论 主讲：杜剑峰 4/18/2010 61支持度置信度的局限性支持度置信度的局限性CoffeeCoffeeTea15

34、520Tea755809010100l支持度的缺点若支持度阈值过高，则许多潜在的有意义的模式被删调若支持度阈值过低，则计算代价很高而且产生大量的关联模式l置信度的缺点关联规则:Tea Coffee置信度=P(Coffee|Tea)=0.75但 P(Coffee)=0.9虽然置信度很高，但规则是误导的置信度忽略了规则前件和后件的统计独立性置信度忽略了规则前件和后件的统计独立性数据挖掘导论 主讲：杜剑峰 4/18/2010 62统计独立性统计独立性l1000个学生的群体600个学生知道如何去游泳(S)700个学生知道如何去骑单车(B)420个学生知道如何去游泳和骑单车(S,B)P(SB)=420/

35、1000=0.42P(S)P(B)=0.6 0.7=0.42P(SB)=P(S)P(B)=统计独立P(SB)P(S)P(B)=正相关P(SB)负相关数据挖掘导论 主讲：杜剑峰 4/18/2010 63基于统计的度量基于统计的度量部分考虑统计独立性的度量l提升度l兴趣因子l相关系数l余弦数据挖掘导论 主讲：杜剑峰 4/18/2010 64例子例子:提升度提升度/兴趣因子兴趣因子CoffeeCoffeeTea15520Tea755809010100 关联规则:Tea CoffeeConfidence=P(Coffee|Tea)=0.75但 P(Coffee)=0.9 Lift=0.75/0.9=0

36、.8333(1,说明Coffee和Tea是负相关的)数据挖掘导论 主讲：杜剑峰 4/18/2010 65上述兴趣度的局限性上述兴趣度的局限性YYX10010X090901090100YYX90090X010109010100YYX403070X300307030100 现有文献提供现有文献提供了大量的兴趣度了大量的兴趣度度量度量 当这些度量应当这些度量应用到一组关联模用到一组关联模式时是否会产生式时是否会产生类似的有序结果类似的有序结果？如何通过考察如何通过考察度量的性质了解度量的性质了解度量之间的差异度量之间的差异？数据挖掘导论 主讲：杜剑峰 4/18/2010 67客观度量的一致性客观度量

37、的一致性相依表显示的10个关联模式:使用不同的度量对相依表排序的结果:数据挖掘导论 主讲：杜剑峰 4/18/2010 68对称性对称性是否 M(A,B)=M(B,A)?对称度量:u 支持度、提升度、集体强度、余弦、Jaccard，等等非对称度量:u 置信度、可信度因子、拉普拉斯、J度量，等等数据挖掘导论 主讲：杜剑峰 4/18/2010 69缩放不变性缩放不变性MaleFemaleHigh235Low1453710MaleFemaleHigh43034Low2404267076成绩性别例子(Mosteller,1968):关联应该独立于例子中男生和女生的相对人数2x10 xBBApqArsBBAk1k3pk2k3qAk1k4rk2k4s数据挖掘导论 主讲：杜剑峰 4/18/2010 70反演性反演性BBApqArsBBAprAqsBBApqArsBBAsqArpBBApqArsBBAsrAqp数据挖掘导论 主讲：杜剑峰 4/18/2010 71零加性零加性不变度量:u 支持度、余弦、Jaccard，等等变化度量:u 相关系数、Gini指标、互信息，等等数据挖掘导论 主讲：杜剑峰 4/18/2010 72不同的度量具有不同的性质不同的度量具有不同的性质O1:对称性对称性O2:缩放不变性缩放不变性O3:反演性反演性O4:零加性零加性