频繁模式挖掘与关联规则挖掘

数据挖掘

第六章挖掘大型数据库中的关联规则孙玉芬yufen@武汉理工大学计算机科学与技术学院计算机科学系2023/2/11数据挖掘挖掘大型数据库中的关联规则6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关分析6.6基于约束的关联挖掘6.7小结2023/2/12数据挖掘6.1关联规则挖掘由Agrawal，Imielinski，与Swami[AIS93]首次提出频繁项集（frequentitemsets）与关联规则挖掘（associationrulemining）动机：找出数据中存在的规则AB哪些产品总是被同时购买？—啤酒与尿布？！顾客购买PC后，还会购买哪些商品？哪种DNA会对某种新药敏感？先挖掘频繁模式，然后挖掘关联规则频繁模式：在一个数据集中频繁出现的模式（数据项集，子序列，子结构，等）2023/2/13数据挖掘基本概念：频繁模式与关联规则项集X={x1,…,xk}找出所有置信度与支持度超过阈值的规则

XY支持度（support），s，包含XY的事务出现的概率置信度（confidence），c，事务包含X时，也包含Y的条件概率置supmin=50%，confmin=50%频繁模式：

{A:3,B:3,D:4,E:3,AD:3}关联规则：AD(60%,100%)DA(60%,75%)购买尿布的顾客两样都买的顾客购买啤酒的顾客事务号购买的项10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F2023/2/14数据挖掘为什么频繁模式挖掘是重要的？能发现数据集中内在的特性是许多重要的数据挖掘任务的基础关联分析，相关分析，与因果分析序列模式，结构模式（如：子图）时空数据、多媒体数据、时序数据、流数据中的模式分析分类：关联分类聚类：基于频繁模式的聚类数据仓库：冰山数据立方语义数据压缩广泛的应用购物篮数据分析，Web点击流分析，打折销售分析，DNA序列分析2023/2/15数据挖掘关联规则的分类布尔关联规则与量化关联规则计算机

财务管理软件年龄（X，”30…39”）收入（X，”42k…48k”）购买（X，”高清晰电视”）单维关联规则与多维关联规则单层关联规则与多层关联规则年龄（X，”30…39”）购买（X，”笔记本”）年龄（X，”30…39”）购买（X，”计算机”）闭模式与最大模式2023/2/16数据挖掘闭模式与最大模式一个长模式包含大量子模式。例如：{a1,…,a100}包含

C1001+C1002+…+C110000=2100–1=1.27*1030子模式！解决方法：挖掘闭模式（closedpatterns

）与最大模式（

max-patterns）一个项集X是闭模式，如果X是频繁的，且不存在超模式YכX具有与X同样的支持度（Pasquier，ICDT’99）一个项集X是一个最大模式，如果X是频繁的，并且不存在频繁超模式YכX（Bayardo，SIGMOD’98）闭模式是频繁模式集的无损压缩压缩了模式与规则的数目2023/2/17数据挖掘闭模式与最大模式例子：DB={<a1,…,a100>,<a1,…,a50>}最小支持度=1有哪些闭模式?<a1,…,a100>:1<a1,…,a50>:2有哪些最大模式？<a1,…,a100>:1所有模式!!2023/2/18数据挖掘挖掘大型数据库中的关联规则6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关分析6.6基于约束的关联挖掘6.7小结2023/2/19数据挖掘6.2由事务数据库挖掘单维布尔关联规则挖掘最简单形式的关联规则：单维单层布尔两个主要方法Apriori（Agrawal&Srikant@VLDB’94）频繁模式增长方法（FPgrowth—Han,Pei&Yin@SIGMOD’00）2023/2/110数据挖掘6.2.1Apriori：一个基于候选集的方法Apriori性质：一个频繁项集的所有非空子集都必定是频繁的如果{啤酒，尿布，坚果}是频繁的，则{啤酒，尿布}必定是频繁的每个包含{啤酒，尿布，坚果}

的事务，必定包含{啤酒，尿布}

反单调Apriori

修剪原则:如果某个项集是不频繁的，则它的超集不需要被考虑2023/2/111数据挖掘Apriori方法逐层搜索：由K－项集到

k+1－候选项集方法：扫描数据集一次，得到所有长度为1的频繁项集基于长度为K的频繁项集，生成长度为k+1的候选项集扫描数据集，检测候选项集是否频繁当没有频繁项集或候选项集生成时，中止算法。2023/2/112数据挖掘例子：Apriori算法

事务数据库第一遍扫描C1L1L2C2C2第二遍扫描C3L3第三遍扫描事务号项10A,C,D20B,C,E30A,B,C,E40B,E项集S{A}2{B}3{C}3{D}1{E}3项集S{A}2{B}3{C}3{E}3项集{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}项集S{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2项集S{A,C}2{B,C}2{B,E}3{C,E}2项集{B,C,E}项集S{B,C,E}2Smin=22023/2/113数据挖掘Apriori算法伪码：Ck

：长度为k的候选项集Lk：长度为k的频繁项集L1={频繁项};for

(k=1;Lk!=;k++)dobegin

Ck+1=由Lk

生成的候选项集；

对数据库中的每个事务t

do

将Ck+1中所有在t中出现的候选项集的计数分别加1

Lk+1=Ck+1

中所有计数超过支持度阈值的候选项集

endreturn

k

Lk;2023/2/114数据挖掘Apriori中的重要细节如何生成候选项集？第一步：self-joiningLk第二步：修剪生成候选项集的例子L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3由abc

与abd

得到

abcd由acd

与ace得到acde修剪：由于

ade

不在L3

中，acde

被删除C4={abcd}2023/2/115数据挖掘如何生成候选项集？假设Lk-1

中的项按某个次序排列第一步：self-joiningLk-1

insertinto

Ckselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1第二步：修剪Forall项集

cinCk

doForall(k-1)-子集

sofcdoif(sisnotinLk-1)thendeletecfromCk2023/2/116数据挖掘6.2.2由频繁项集产生关联规则强关联规则：满足支持度阈值和置信度阈值的规则基于频繁项集生成关联规则对每个频繁项集L，产生L的所有非空子集对于L的每个非空子集S，如果支持度（L）/支持度（S）大于或等于置信度阈值，则输出规则“S(L-S)”例子：支持度阈值为2，置信度阈值为70％BCE事务号项10A,C,D20B,C,E30A,B,C,E40B,E2023/2/117数据挖掘6.2.3提高Apriori的有效性挑战多遍事务数据库扫描候选频繁项集的数目巨大候选项集的计数工作量较大改进Apriori：思路减少事务数据库扫描次数减少候选项集数目有效支持候选项集的计数2023/2/118数据挖掘提高Apriori的有效性基于散列的技术对于一个长度为k的项集，若它所对应的哈希桶计数小于阈值，则它不可能是频繁的可有效减少守候选项集的数目例子：候选项集：a,b,c,d,e哈希桶：{ab,ad,ae}{bd,be,de}…长度为1的频繁项集：a,b,d,e如果{ab,ad,ae}的计数之和小于支持度阈值，则ab

不是长度为2的候选项集2023/2/119数据挖掘提高Apriori的有效性事务压缩不包含任何k－项集的事务不可能包含任何（k+1）－项集划分方法：仅扫描数据库两次将数据库中的数据划分为几个子集，原数据库中任意一个频繁项集至少在一个子集中是频繁的第一遍扫描：划分数据库，并找到各个子集中的频繁项第二遍扫描：计算全局频繁项2023/2/120数据挖掘提高Apriori的有效性选样从原数据库中选取一个样本，使用Apriori算法挖掘此样本中的频繁项集（使用较小的支持度阈值）扫描数据库，验证样本中的频繁项集在原数据库中是否频繁。仅验证频繁项集闭包的边界例子：仅检查

abcd，不用检查

ab,ac,…,等重新扫描数据库，找出遗漏的频繁项集2023/2/121数据挖掘提高Apriori的有效性ABCDABCABDACDBCDABACBCADBDCDABCD{}项集网动态项集计数：减少扫描次数一旦A与D都被确定是频繁的，马上开始对AD的计数一旦项集BCD的所有长度为2的子集都被确定是频繁的，马上开始对BCD的计数事务1-项集2-项集…Apriori1-项集2-项集3-项集DIC2023/2/122数据挖掘6.2.4不产生候选挖掘频繁项集对数据库的多遍扫描代价昂贵（costly）挖掘长模式需要对数据库的多遍扫描，并会产生大量候选项集为找到频繁项集i1i2…i100扫描遍数：100产生的候选项集数目：C1001+C1002+…+C110000=2100-1=1.27*1030!瓶颈：候选的产生与验证能否不生成候选项集？2023/2/123数据挖掘无候选生成的频繁模式挖掘基于短模式，使用局部频繁项得到长模式“abc”是一个频繁模式找出所有包含“abc”的事务:DB|abc“d”是DB|abc

中的局部频繁项abcd

是一个频繁模式2023/2/124数据挖掘构建事务数据库的FP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项的支持度计数f 4c 4a 3b 3m 3p 3min_support=3事务号

购买的项

（有序）频繁项100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o,w}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}扫描数据库1遍，找出所有频繁项将频繁项按它们支持度计数的降序排列，f-list重新扫描数据库，构建FP-treeF-list=f-c-a-b-m-p2023/2/125数据挖掘FP-tree结构的优点完全性保留了频繁项挖掘所需的所有信息没有将事务中的长模式打断压缩性减少不相关信息—删掉了不频繁项项按支持度计数的降序排列：出现次数越多的项，越可能被多个模式所共享永远不可能比原数据库大（不计节点间的连接与计数域）2023/2/126数据挖掘划分模式与数据库可以根据f-list

，将频繁模式划分为多个子集F-list=f-c-a-b-m-p模式包含p模式包含m，但不包含p…模式包含c，但不包含a，b，m，p模式f完全且无冗余2023/2/127数据挖掘从P-条件模式集中找出所有包含P的模式以FP-树的项头表为起点沿着频繁项p

的链接横穿FP-树基于项p在树中的前缀生成p的条件模式集条件模式集项

条件模式集c f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项的支持度计数f 4c 4a 3b 3m 3p 32023/2/128数据挖掘由条件模式集生成条件FP-树

对每个模式集计算集中每个项的支持度计数为模式集中的频繁项构建FP-树m-条件模式集fca:2,fcab:1{}f:3c:3a:3m-条件

FP-树所有包含

m的频繁模式m,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项的支持度计数f 4c 4a 3b 3m 3p 32023/2/129数据挖掘递归：挖掘每个条件FP-tree{}f:3c:3a:3m-条件

FP-树“am”的条件模式集：(fc:3){}f:3c:3am-条件

FP-树“cm”的条件模式集：(f:3){}f:3cm-条件

FP-树“cam”的条件模式集：(f:3){}f:3cam-条件

FP-树2023/2/130数据挖掘特殊情况：FP-树中的单条前缀路径假设一个（条件）FP-树T中有一条共享的前缀路径P可以将挖掘分解为两部分将单条前缀路径压缩为一个节点综合此条前缀路径与压缩后FP-树的挖掘结果a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=2023/2/131数据挖掘基于FP-树挖掘频繁模式思路：频繁模式增长通过数据库划分，递归增长频繁模式方法对每个频繁项，构建它的条件模式集与条件FP-树在新构建的条件FP-树上重复上述步骤直到结果FP-树为空，或者仅包含一条路径—这条路径的所有子路径都代表一个频繁模式2023/2/132数据挖掘FP-增长vs.Apriori：对支持度阈值的可伸缩性数据集T25I20D10K2023/2/133数据挖掘为什么FP-增长的性能更好？分而治之：基于当前得到的频繁模式分解挖掘任务与数据库只需仔细搜索较小的数据库其他因素无候选项集（模式）生成，无候选项集验证数据库压缩：FP-树结构不需要对整个数据库进行重复扫描只需计算局部频繁项，并构建条件FP-树，不需要模式搜索与匹配2023/2/134数据挖掘6.2.5冰山查询冰山查询：在一个属性或属性集上计算一个聚集函数，以找出大于某个指定阈值的聚集值。例子：selectP.cust_ID,P.item_ID,SUM(P.qty)fromPurchasesPgroupbyP.cust_ID,P.item_IDhavingSUM(P.qty)>=3产生候选selectP.cust_IDselectP.item_IDfromPurchasesPfromPurchasesPgroupbyP.cust_IDgroupbyP.item_IDhavingSUM(P.qty)>=3havingSUM(P.qty)>=32023/2/135数据挖掘挖掘大型数据库中的关联规则6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关分析6.6基于约束的关联挖掘6.7小结2023/2/136数据挖掘6.3.1多层关联规则数据库中的项经常形成层次关系多层关联规则：由具有概念分层的关联规则挖掘产生的规则为什么要挖掘多层关联规则在低层/原始层的数据项之间很难找出强关联规则用户的需求例子：2023/2/137数据挖掘6.3.2挖掘多层关联规则的方法通常采用自顶向下的策略对于所有层使用一致的最小支持度递减的支持度阈值设置较低层次的项通常具有较低的支持度统一的支持度阈值computer[支持度=10%]laptop[支持度=6%]desktop[支持度=4%]层1支持度阈值=5%层2支持度阈值=5%层1支持度阈值=5%层2支持度阈值=3%不统一的支持度阈值2023/2/138数据挖掘频繁项集搜索策略逐层独立没有剪枝层交叉单项过滤一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的computer[支持度=10%]laptop（未考察）desktop（未考察）层1支持度阈值=12%层2支持度阈值=3%2023/2/139数据挖掘频繁项集搜索策略层交叉k-项集过滤一个第i层的k-项集被考察，当且仅当它在第（i-1）层的对应父节点k-项集是频繁的Computerandprinter[支持度=7%]Laptopcomputerandb/wprinter[支持度=1%]Desktopcomputerandb/wprinter[支持度=1%]层1支持度阈值=5%层2支持度阈值=2%Laptopcomputerandcolorprinter[支持度=2%]Desktopcomputerandb/wprinter[支持度=3%]2023/2/140数据挖掘频繁项集搜索策略受控的层交叉单项过滤策略层传递阈值下一层的最小支持度阈值与当前层的最小支持度阈值之间的值computer[支持度=10%]laptop[支持度=6%]desktop[支持度=4%]层1支持度阈值=12%层传递阈值=8%层2支持度阈值=3%2023/2/141数据挖掘6.3.3检查冗余的多层关联规则由于项之间的层次关系，一些规则之间可能存在冗余例子Desktopcomputerb/wprinter[支持度=8%，置信度=70%]IBMdesktopcomputer

b/wprinter[支持度=2%，置信度=72%]我们称第一个规则是第二个规则的祖先若一个规则的支持度与基于其祖先规则推导出的期望的支持度相似，则称这个规则是冗余的2023/2/142数据挖掘挖掘大型数据库中的关联规则6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关分析6.6基于约束的关联挖掘6.7小结2023/2/143数据挖掘6.4.1多维关联规则单维规则：购买（X，”desktopcomputer”）购买（X，”b/wprinter”）多维关联规则:

2维或谓词维间关联规则（没有重复的谓词）年龄（X，”19-25”）职业（X，“学生”）购买（X，“可乐”）混合维关联规则（有重复出现的谓词）年龄（X，”19-25”）购买（X，”爆米花”）购买（X，”可乐”）单维关联规则挖掘：搜索频繁项集多维关联规则挖掘：搜索频繁谓词集分类属性：具有有限数目的可能取值，值之间无次序关系量化属性：数值型数据，值之间存在次序关系2023/2/144数据挖掘对量化属性的处理使用预定义的概念分层将量化属性离散化（静态离散化）根据数据的分布，将量化属性离散化到“箱”（动态离散化）基于数据点之间的距离将量化属性离散化（使用聚类方法）2023/2/145数据挖掘6.4.2使用量化属性的静态离散化挖掘多维关联规则在挖掘前，使用概念层次将属性离散化数值型属性的取值用取值区间表示在关系数据库中，找出所有k-谓词频繁集需要k

或k+1次扫描数据立方体适合于关联规则挖掘n-维立方体中的节点表示谓词集在数据立方体上挖掘可以减少挖掘所需时间(收入)(年龄)()(购买)(年龄，收入)(年龄，购买)(收入，购买)(年龄，收入，购买)2023/2/146数据挖掘6.4.3挖掘量化关联规则分箱：等宽分箱等深分箱基于同质的分箱找频繁谓词集关联规则聚类2023/2/147数据挖掘6.4.4挖掘基于距离的关联规则考虑数据点之间或区间之间的相对距离，紧扣区间数据的语义，并允许数据值的近似两遍算法：使用聚类找出区间或簇搜索频繁地一起出现的簇的集合，得到基于距离的关联规则2023/2/148数据挖掘挖掘大型数据库中的关联规则6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关分析6.6基于约束的关联挖掘6.7小结2023/2/149数据挖掘6.5.1强关联规则不一定是有趣的打篮球

吃谷类食品[40%,66.7%]产生误导在所有学生中，有75%吃谷类食品，高于66.7%。打篮球

不吃谷类食品[20%,33.3%]更为准确，尽管它的支持度与置信度都很低规则AB的置信度有一定的欺骗性，它只给出了A，B的条件概率估计，并没有度量A和B之间的相关性。2023/2/150数据挖掘6.5.2由关联分析到相关分析事件之间相关性的度量：corr打篮球不打篮球总和吃谷类食品200017503750不吃谷类食品10002501250总和3000200050002023/2/151数据挖掘挖掘大型数据库中的关联规则6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关分析6.6基于约束的关联挖掘6.7小结2023/2/152数据挖掘6.6基于约束的关联挖掘自动找到数据库中的所有模式—不现实！模式数目可能非常大，但大部分是不需要的数据挖掘应该是一个交互式过程用户使用数据挖掘查询语言或图形用户界面指导挖掘过程基于约束的挖掘用户：给出约束或指明需要挖掘什么系统优化：利用约束进行有效挖掘—基于约束的挖掘2023/2/153数据挖掘6.6基于约束的关联挖掘知识类型约束：

指定要挖掘的知识类型，如分类模型，关联规则，等等数据约束指定与任务相关的数据集维/层约束指定所用的维或概念分层结构中的层规则约束指定要挖掘的规则形式，如规则前件或后件中谓词的个数兴趣度约束指定规则兴趣度阈值或统计度量，如支持度阈值与置信度阈值2023/2/154数据挖掘6.6.1关联规则的元规则制导挖掘元规则使得用户可以说明他们感兴趣的规则的语法形式例子：元规则：与元规则匹配的规则：2023/2/155数据挖掘6.6.2用附加的规则约束制导的挖掘规则约束反单调的单调的简洁的可转变的不可转变的2023/2/156数据挖掘反单调约束反单调性若项集S不满足约束，那么它的所有超集都不满足约束求和(S.价格)v

是反单调的求和(S.价格)v

不是反单调的例子：约束C：求和(S.价格)15是反单调的项集ab

不满足Cab的任何超集也不满足CTID事务10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,g事务数据库(min_sup=2)项价格a40b10c20d10e30f30g20h102023/2/157数据挖掘单调约束单调性若项集S满足约束，则它的任意超集都满足约束求和(S.价格)v

是单调的最小(S.价格)

v是单调的例子：约束C：求和(S.价格)15项集ab

满足C