第7章 关联规则挖掘

1、第七章第七章 关联规则的挖掘关联规则的挖掘一、关联规则挖掘的含义一、关联规则挖掘的含义 关联规则用于表示关联规则用于表示OLTPOLTP数据库中诸多属性（项集）之间数据库中诸多属性（项集）之间的关联程度。而关联规则挖掘（的关联程度。而关联规则挖掘（ Association Rules MiningAssociation Rules Mining）则是利用数据库中的大量数据通过关联算法寻找属性间的相关则是利用数据库中的大量数据通过关联算法寻找属性间的相关性。性。 例：例：( (超级市场超级市场) )在购买商品在购买商品A A的客户中有的客户中有90%90%的人会同时购的人会同时购买商品买商品B

2、B，则可用关联规则表示为：，则可用关联规则表示为：BA支持度支持度(Support) 同时购买同时购买A A和和B B的客户人数占总客户数的百分比称为规则的的客户人数占总客户数的百分比称为规则的支持度。支持度。)()(supBAPBAport置信度置信度(Confidence) 同时购买同时购买A和和B的客户人数占购买的客户人数占购买A的客户人数的百分比称的客户人数的百分比称为规则的置信度。为规则的置信度。)()()|()(APBAPABPBAconfidence 由于在实际应用中，概率由于在实际应用中，概率P一般是无法事先给出的，一般是无法事先给出的，所以常以频度代替所以常以频度代替购买购买

3、A的顾客的顾客购买购买B的顾客的顾客同时购买同时购买A和和B的顾客（的顾客（A B） 如果不考虑关联规则的支持度和如果不考虑关联规则的支持度和置置信度信度，那么在事务数那么在事务数据库中存在无穷多的关联规则。事实上据库中存在无穷多的关联规则。事实上，人们一般只对满足人们一般只对满足一定的支持度和可信度的关联规则感兴趣。一定的支持度和可信度的关联规则感兴趣。 为了发现出有意义的关联规则为了发现出有意义的关联规则，需要给定两个阈值需要给定两个阈值：最最小支持度和最小小支持度和最小置置信度。信度。关联规则挖掘的实质是在数据集合关联规则挖掘的实质是在数据集合中寻找满足用户给定的最小支持度和最小置信度的

4、规则。中寻找满足用户给定的最小支持度和最小置信度的规则。 例：交易情况如下表，例：交易情况如下表，要求最小支持度为要求最小支持度为50%, 50%, 最小可信度为最小可信度为 50%, 50%, 则可得到：则可得到：A A C (50%, 66.6%) C (50%, 66.6%)C C A (50%, 100%) A (50%, 100%)ID号号购买的商品购买的商品001A，B，C002A，C003A，D004B，E，F二、关联规则挖掘算法二、关联规则挖掘算法： The Apriori Algorithm Agrawal等人提出等人提出1 1、术语、术语项集项集：在数据库中出现的属性值的集

5、合。在数据库中出现的属性值的集合。频繁项集频繁项集：满足最小支持度要求的项集。满足最小支持度要求的项集。 关联规则一定是在满足用户的最小支持度要求的频关联规则一定是在满足用户的最小支持度要求的频繁项集中产生的，因此，关联规则挖掘也就是在数据库中繁项集中产生的，因此，关联规则挖掘也就是在数据库中寻找频繁项集的过程。寻找频繁项集的过程。K_K_项集：项集：包含包含K K个项的项集。个项的项集。交易号交易号购买的商品购买的商品001A，B，C002A，C003A，D004B，E，F例：例：项集：项集：A，B，C，D，E，F，.1_项集：项集：A，B，C，.，F2_项集：项集：A，B，A，C.如要求最

6、小支持度为如要求最小支持度为50%，则：，则：频繁项集：频繁项集：A，B，C，A，C频繁项集的任何子集也一定是频繁的！频繁项集的任何子集也一定是频繁的！2、关联规则分类、关联规则分类1）根据规则中所处理的）根据规则中所处理的值类型值类型布尔关联规则：规则考虑的关联项是否存在布尔关联规则：规则考虑的关联项是否存在量化关联规则：规则描述的是量化的项或属性间的规则量化关联规则：规则描述的是量化的项或属性间的规则(2) )buys(x,)42K.50K(x,)30.39(x,背投高清晰电视收入年龄(1) )128Kbuys(x,)Sony(x,记忆棒的数码相机Sonybuys2）根据规则中所涉及的）根

7、据规则中所涉及的数据维数据维(1)是单维的，涉及是单维的，涉及buys; (2)多维，涉及年龄、收入和多维，涉及年龄、收入和buys3）根据规则中所涉及的）根据规则中所涉及的抽象层抽象层)buys()30.39age(x,)buys()30.39age(x,计算机台式机商品位于不同层，计算机的抽象层高，称为商品位于不同层，计算机的抽象层高，称为多层关联规则多层关联规则3 3、 AprioriApriori算法算法符号定义：符号定义： Lk:k项项频繁频繁集的集合；集的集合； Ck：k项集的候补集合项集的候补集合步骤：步骤：连接连接: 用用 Lk-1自连接得到自连接得到Ck，（，（k2) 注注

8、设设l1,l2是有是有两个有两个有k-1个有序项的项集，个有序项的项集，lji代表代表k-1个项的第个项的第i项项(j=1,2; i=1,2,k-1)。l1和和l2是可连接的是可连接的l1Xl2，需满足：需满足： l11=l21 ,l12=l22，.，l1k-2=l2k-2， l1k-1 l2k-1，产生的项是：产生的项是： l11l12.l1k-2l1k-1l2k-1(lji是有序的）是有序的）*注：注：C2= 由由1_项集两两组合生成项集两两组合生成 ，共，共C2m(m为为1_项集合的项数）项集合的项数）修剪修剪: 一个一个k-项集，如果它的一个项集，如果它的一个k-1项子集不是频繁的，那

9、它本项子集不是频繁的，那它本身也不可能是频繁的。身也不可能是频繁的。例：例：l1=A,B,C ， l2=A,B,D，l3=A,C,F则：则：l1 X l2=A,B,C,D l1 X l3，l2 X l3均为空均为空为什么为什么l1 X l3不生成不生成A,B,C,F?A，B，C ，A，B，F4、伪代码、伪代码:min_support为最小支持度为最小支持度L1= 找频繁找频繁1_项集；项集；for (k = 2; Lk !=; k+) Ck= 由由 Lk-1生成候补集合；生成候补集合； for each t Ck 计算计算t在数据集合中出现的次数；在数据集合中出现的次数； if (出现计数小于

10、出现计数小于min_support) 从从Ck中剔除；中剔除； Lk = Ck； return k Lk;5、关联规则挖掘例，（要求最小支持数为、关联规则挖掘例，（要求最小支持数为2）TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库数据库 D扫描扫描 Ditemset sup.1223334153C1itemsetsup1 211 321 512 322 53C23 52itemset1 21 31 52 32 53 5C2扫描扫描 DC3itemset2 3 5扫描扫描 DL3itemset sup2 3 52itemset sup.12233

11、353L1itemset sup1 322 322 533 52L26、可以产生哪些规则、可以产生哪些规则 前面的例子中，得到一个频繁集前面的例子中，得到一个频繁集 2，3，5，非空真子集有，非空真子集有2，3，5，2，3，2，5，3，5itemset sup.12233353L1itemset sup1 322 322 533 52L3itemset sup2 3 52L2规则：规则：2 3 3 5 53 3 2 2 5 55 5 2 2 3 32 2 3 3 5 52 2 5 5 3 33 3 5 5 2 2置信度：置信度：2/3=66%（2，3，5频度频度/2频度）频度）2/3=66%（

12、2，3，5频度频度/3频度）频度）2/3=66%（2，3，5频度频度/5频度）频度）2/2=100%（2，3，5频度频度/2，3频度）频度）2/3=66%（2，3，5频度频度/2，5频度）频度）2/2=100% （2，3，5频度频度/3，5频度）频度）支持度支持度 ：2/4=50%7、Apriori 够快了吗够快了吗? 性能瓶颈性能瓶颈AprioriApriori算法的核心算法的核心: :用频繁的用频繁的( (k-k-1)_1)_项集生成项集生成候选候选的频繁的频繁 k k_ _项集项集用数据库扫描和模式匹配计算候选集的支持度用数据库扫描和模式匹配计算候选集的支持度AprioriApriori

13、 的瓶颈的瓶颈: : 候选集生成候选集生成巨大的候选集巨大的候选集: :10104 4 个频繁个频繁1 1_ _项集要生成项集要生成 10107 7 个候选个候选 2_2_项集项集要找尺寸为要找尺寸为100100的频繁模式，如的频繁模式，如 a a1 1, a, a2 2, , , a, a100100, , 你必须先产生你必须先产生2 2100 100 10 103030 个候选集（个候选集（1_1_项集）项集）多次扫描数据库多次扫描数据库： 如果最长的模式是如果最长的模式是n n的话，则需要的话，则需要n n次数据库扫描次数据库扫描为提高为提高AprioriApriori算法的性能，有许多

14、改进的算法。算法的性能，有许多改进的算法。8、如何在概念分层有效地挖掘多层关联规则、如何在概念分层有效地挖掘多层关联规则 一般采用自顶向下策略，由概念层一般采用自顶向下策略，由概念层1开始向下，到较低的开始向下，到较低的更特定的概念层，对每个概念层的频繁集累加计数，直到不更特定的概念层，对每个概念层的频繁集累加计数，直到不能再找到频繁项集。能再找到频繁项集。计算机计算机支持度支持度=10%台式机台式机支持度支持度=6%笔记本笔记本支持度支持度=4%层层1: minsup=5%层层2: minsup=5%非频繁非频繁 问题：问题：因为较低层次抽象的项不大可能像较高层次抽象的项因为较低层次抽象的项

15、不大可能像较高层次抽象的项出现得那么频繁。如果最小支持度阀值设置的太高，可能丢出现得那么频繁。如果最小支持度阀值设置的太高，可能丢掉出现在较低抽象层次中有意义的关联规则。如果阀值设置掉出现在较低抽象层次中有意义的关联规则。如果阀值设置太底，可能会出现在较高抽象层的无兴趣的关联规则。太底，可能会出现在较高抽象层的无兴趣的关联规则。对于所有层使用一致的最小支持度对于所有层使用一致的最小支持度8、如何在概念分层有效地挖掘多层关联规则、如何在概念分层有效地挖掘多层关联规则 一般采用自顶向下策略，由概念层一般采用自顶向下策略，由概念层1开始向下，到较低的开始向下，到较低的更特定的概念层，对每个概念层的频

16、繁集累加计数，直到不更特定的概念层，对每个概念层的频繁集累加计数，直到不能再找到频繁项集。能再找到频繁项集。对于所有层使用一致的最小支持度对于所有层使用一致的最小支持度在较低层使用递减的最小支持度在较低层使用递减的最小支持度计算机计算机支持度支持度=10%台式机台式机支持度支持度=6%笔记本笔记本支持度支持度=4%层层1: minsup=5%层层2: minsup=3%9、冗余的多层关联规则处理、冗余的多层关联规则处理 买笔记本买笔记本买打印机买打印机 支持度支持度=8%,=8%,置信度置信度=70% (1)=70% (1) 买买IBM笔记本笔记本买打印机买打印机 支持度支持度=2%,=2%,

17、置信度置信度=72% (2)=72% (2)规则规则2有用吗？它提供了新颖的信息吗？有用吗？它提供了新颖的信息吗？ 如果后一个具有较小一般性的规则，它不提供新的信息，应如果后一个具有较小一般性的规则，它不提供新的信息，应当删除它！当删除它！ 如果一个规则的祖先，它的支持度和置信度都接近于该规如果一个规则的祖先，它的支持度和置信度都接近于该规则的则的“期望期望”值，这个规则是冗余的。值，这个规则是冗余的。 从（从（1）的）的置信度置信度=70%=70%推断：推断： 买笔记本买笔记本同时买打印机的交易数同时买打印机的交易数/ /买笔记本交易数买笔记本交易数=70% IBM笔记本属于笔记本，因此笔记

18、本属于笔记本，因此置信度也应该在置信度也应该在70%70%左右。由左右。由（2)2)实际为实际为72%72%，基本无差异。，基本无差异。9、冗余的多层关联规则处理、冗余的多层关联规则处理 买笔记本买笔记本买打印机买打印机 支持度支持度=8%,=8%,置信度置信度=70% (1)=70% (1) 买买IBM笔记本笔记本买打印机买打印机 支持度支持度=2%,=2%,置信度置信度=72% (2)=72% (2)规则规则2有用吗？它提供了新颖的信息吗？有用吗？它提供了新颖的信息吗？ 如果后一个具有较小一般性的规则，它不提供新的信息，应如果后一个具有较小一般性的规则，它不提供新的信息，应当删除它！当删除

19、它！ 如果一个规则的祖先，它的支持度和置信度都接近于该规如果一个规则的祖先，它的支持度和置信度都接近于该规则的则的“期望期望”值，这个规则是冗余的。值，这个规则是冗余的。 从（从（1）的）的支持度支持度=8%=8%推断：推断： 买笔记本买笔记本同时买打印机的交易数同时买打印机的交易数/ /总交易数总交易数=8%，假定从，假定从数据集中还发现，数据集中还发现，IBM笔记本在占整个笔记本销量的笔记本在占整个笔记本销量的25%。 则：买则：买IBM笔记本的支持度应该为笔记本的支持度应该为8%*25%=2%， 由（由（2)2)实际为实际为2%2%，两者相同。，两者相同。结论：规则（结论：规则（2）不是

20、有趣的，因为它不提供有趣的信息。）不是有趣的，因为它不提供有趣的信息。10、关联规则的相关分析、关联规则的相关分析 强关联规则不一定有趣强关联规则不一定有趣%66%,40) ,() ,(置信度支持度影碟机计算机游戏xbuysxbuys 其实，规则是误导，因为购买影碟机的可能性是其实，规则是误导，因为购买影碟机的可能性是75%，比，比66%还大。事实是：计算机游戏和影碟机是负相关的。还大。事实是：计算机游戏和影碟机是负相关的。 A和和B的相关性：的相关性：)()()(BpApBApcorrABcorrAB: 1，正相关，每一个出现蕴涵另一个出现，正相关，每一个出现蕴涵另一个出现 例：在例：在10000个交易中，个交易中，6000个顾客交易包含计算机游戏，个顾客交易包含计算机游戏，7500个顾客交易包含影碟机，个顾客交易包含影碟机，4000个交易包