第5章基于数据仓库的决策支持系统4解析课件

第5章基于数据仓库的决策支持系统

(4)1第5章基于数据仓库的决策支持系统15.5数据挖掘的决策支持5.5.3关联规则的挖掘及其应用基本原理Apriori算法3.实例5.5数据挖掘的决策支持5.5.3关联规则的挖掘及其应用2关联规则（AssociationRule）挖掘是发现大量数据库中项集之间的关联关系。从大量商业事务中发现有趣的关联关系，可以帮助许多商业决策的制定，如分类设计、交叉购物等。Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题。

关联规则（AssociationRule）挖掘是发现大量数31．关联规则的挖掘原理

关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式。例1：在购买铁锤的顾客当中，有70％的人同时购买了铁钉。

1．关联规则的挖掘原理关联规则是发现交易数据库中不同4

例2：年龄在40岁以上，工作在A区的投保人当中，有45％的人曾经向保险公司索赔过。可以看出来，A区可能污染比较严重，环境比较差，索赔率也相对比较高。例2：年龄在40岁以上，工作在A区的投保人当中，5（1）

基本原理设I={i1,i2,…,im}是项（Item）的集合。记D为事务（Transaction）的集合，事务T是项的集合，并且TI。设A是I中一个项集，如果AT，称事务T包含A。定义1：关联规则是形如AB的蕴涵式，这里AI，BI，并且AB=。（1）基本原理设I={i1,i2,…,im}是项（Item6定义2：规则的支持度。规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)，即：

其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。定义2：规则的支持度。7定义3：规则的可信度规则AB具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即：

其中表示数据库中包含项集A的事务个数。定义3：规则的可信度8定义4：阈值。在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度（min_sup）和最小可信度（min_conf）。定义5：项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。如果项集满足最小支持度，则它称之为频繁项集（FrequentItemset）。定义4：阈值。9定义6：关联规则。同时满足最小支持度（min_sup）和最小可信度（min_conf）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。定义6：关联规则。10（2）关联规则挖掘过程关联规则的挖掘一般分为两个过程：

1）找出所有的频繁项集：找出支持度大于最小支持度的项集，即频繁项集。

2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。（2）关联规则挖掘过程关联规则的挖掘一般分为两个过程：11（3）关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:

买咖啡不买咖啡合计买牛奶20525不买牛奶70575合计9010100（3）关联规则的兴趣度例子：讨论不购买商品与购买商品的关系12设定minsupp=0.2,minconf=0.6,得到如下的关联规则：

买牛奶→买咖啡s=0.2c=0.8即80％的人买了牛奶就会买咖啡。同时得到结论：90％的人肯定会买咖啡。关联规则：

买咖啡→不买牛奶s=0.7c=0.78支持度和可信度分别为0.7和0.78，更具有商业销售的指导意义。设定minsupp=0.2,minconf=0.6,得到13定义7：兴趣度：

公式反映了项集A与项集B的相关程度。若即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。定义7：兴趣度：14一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；兴趣度I不小于0。一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际15所有可能的关联规则

RulesSCI1买牛奶→买咖啡0.20.80.892买咖啡→买牛奶0.20.220.893买牛奶→不买咖啡0.050.224不买咖啡→买牛奶0.050.525不买牛奶→买咖啡0.70.931.0376买咖啡→不买牛奶0.70.781.0377不买牛奶→不买咖啡0.050.0670.678不买咖啡→不买牛奶0.050.20.87所有可能的关联规则1买牛奶→买咖啡0.20.80.816讨论I1﹑I2﹑I3﹑I6共4条规则：由于I1、I2<1，在实际中它的价值不大；I3、I6>1，规则才有价值。兴趣度也称为作用度（Lift）,表示关联规则A→B的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。

讨论I1﹑I2﹑I3﹑I6共4条规则：17概括地说：可信度是对关联规则地准确度的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度（作用度）越大，说明项集B受项集A的影响越大。概括地说：18

2.

Apriori算法Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（FrequentItemset）。使用第1步找到的频繁集产生规则。2.Apriori算法Apriori是挖掘关联规则的一19Apriori使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。Apriori使用一种称作逐层搜索的迭代方法，“K-项集”20

1）Apriori性质性质：频繁项集的所有非空子集都必须也是频繁的。如果项集B不满足最小支持度阈值min-sup，则B不是频繁的，即P（B）<min-sup。如果项A添加到B，则结果项集（即BA）不可能比B更频繁出现。因此，BA也不是频繁的，即P（BA）<min-sup。1）Apriori性质性质：频繁项集的所有非空子集都必须21设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1。有公式：

CK+1=LKLK={XY，其中X，YLK，|XY|=K+1}其中C1是1-项集的集合，取自所有事务中的单项元素。

2）“K-项集”产生“K+1-项集”

设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK22如

L1={{A}，{B}} C2={A}{B}={A，B}，且|AB|=2 L2={{A，B}，{A，C}} C3={A，B}{A，C}={A，B，C}，|ABC|=3如L1={{A}，{B}}233.实例事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C3.实例事务ID事务的项目集T1A,B,ET2B,DT3B,241)

在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第1列。2)

假定最小事务支持计数为2（即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。3)

为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。4)

扫描D中事务，计算C2中每个候选项集的支持度计数，如图中的第4列。5)

确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。见图第5列。1)在算法的第一次迭代，每个项都是候选1-项集的集合C1的256)

候选3-项集的集合C3的产生，得到候选集：C3={{A，B，C}，{A，B，E}，{A，C，E}，{B，C，D}，{B，C，E}，{B，D，E}}按Apriori性质，频繁项集的所有子集必须是频繁的。由于{A，D}，{C，D}，{C，E}，{D，E}不是频繁项集，故C3中后4个候选不可能是频繁的，在C3中删除它们。见图第6列。扫描D中事务，对C3中的候选项集计算支持度计数，见图第7列。7)

确定L3，它由具有最小支持度的C3中候选3－项集组成，见图第8列。8）按公式产生候选4－项集的集合C4，产生结果{A,B,C,E},这个项集被剪去，因为它的子集｛B,C,E｝不是频繁的。这样L4=Ф。此算法终止。L3是最大的频繁项集，即：｛A,B,C｝和｛A,B,E｝。6)候选3-项集的集合C3的产生，得到候选集：26具体产生过程用图表示

具体产生过程用图表示27候选集与频繁项集的产生

项集支持度计数A,B 4 A,C 4 A,E 2 B,C 4 B,D 2 B,E 2 项集A,B，C A,B，E C3候选集L2频繁2-项集计算支持度项集支持度计数

A,B,C 2 A,B,E 2 项集支持度计数 A,B,C 2 A,B,E 2 C3候选集L3频繁3-项集候选集与频繁项集的产生项集支持度计数A,B 4 项集C3候28产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“S→L－S”。注：L－S表示在项集L中除去S子集的项集。产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：29频繁项集L={A，B，E}，可以由L产生哪些关联规则？L的非空子集S有：{A,B},{A,E},{B,E},{A},{B},{E}。可得到关联规则如下：A∧B→Econf=2/4=50%A∧E→Bconf=2/2=100%B∧E→Aconf=2/2==100%A→B∧Econf=2/6=33%B→A∧Econf=2/7=29%E→A∧Bconf=2/2=100%假设最小可信度为60％，则最终输出的关联规则为：A∧E→B100%B∧E→A100%E→A∧B100%对于频繁项集{A，B，C}，同样可得其它关联规则。频繁项集L={A，B，E}，可以由L产生哪些关联规则？30习题

42、44习题31

第5章基于数据仓库的决策支持系统

(4)32第5章基于数据仓库的决策支持系统15.5数据挖掘的决策支持5.5.3关联规则的挖掘及其应用基本原理Apriori算法3.实例5.5数据挖掘的决策支持5.5.3关联规则的挖掘及其应用33关联规则（AssociationRule）挖掘是发现大量数据库中项集之间的关联关系。从大量商业事务中发现有趣的关联关系，可以帮助许多商业决策的制定，如分类设计、交叉购物等。Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题。

关联规则（AssociationRule）挖掘是发现大量数341．关联规则的挖掘原理

关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式。例1：在购买铁锤的顾客当中，有70％的人同时购买了铁钉。

1．关联规则的挖掘原理关联规则是发现交易数据库中不同35

例2：年龄在40岁以上，工作在A区的投保人当中，有45％的人曾经向保险公司索赔过。可以看出来，A区可能污染比较严重，环境比较差，索赔率也相对比较高。例2：年龄在40岁以上，工作在A区的投保人当中，36（1）

基本原理设I={i1,i2,…,im}是项（Item）的集合。记D为事务（Transaction）的集合，事务T是项的集合，并且TI。设A是I中一个项集，如果AT，称事务T包含A。定义1：关联规则是形如AB的蕴涵式，这里AI，BI，并且AB=。（1）基本原理设I={i1,i2,…,im}是项（Item37定义2：规则的支持度。规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)，即：

其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。定义2：规则的支持度。38定义3：规则的可信度规则AB具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即：

其中表示数据库中包含项集A的事务个数。定义3：规则的可信度39定义4：阈值。在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度（min_sup）和最小可信度（min_conf）。定义5：项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。如果项集满足最小支持度，则它称之为频繁项集（FrequentItemset）。定义4：阈值。40定义6：关联规则。同时满足最小支持度（min_sup）和最小可信度（min_conf）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。定义6：关联规则。41（2）关联规则挖掘过程关联规则的挖掘一般分为两个过程：

1）找出所有的频繁项集：找出支持度大于最小支持度的项集，即频繁项集。

2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。（2）关联规则挖掘过程关联规则的挖掘一般分为两个过程：42（3）关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:

买咖啡不买咖啡合计买牛奶20525不买牛奶70575合计9010100（3）关联规则的兴趣度例子：讨论不购买商品与购买商品的关系43设定minsupp=0.2,minconf=0.6,得到如下的关联规则：

买牛奶→买咖啡s=0.2c=0.8即80％的人买了牛奶就会买咖啡。同时得到结论：90％的人肯定会买咖啡。关联规则：

买咖啡→不买牛奶s=0.7c=0.78支持度和可信度分别为0.7和0.78，更具有商业销售的指导意义。设定minsupp=0.2,minconf=0.6,得到44定义7：兴趣度：

公式反映了项集A与项集B的相关程度。若即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。定义7：兴趣度：45一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；兴趣度I不小于0。一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际46所有可能的关联规则

RulesSCI1买牛奶→买咖啡0.20.80.892买咖啡→买牛奶0.20.220.893买牛奶→不买咖啡0.050.224不买咖啡→买牛奶0.050.525不买牛奶→买咖啡0.70.931.0376买咖啡→不买牛奶0.70.781.0377不买牛奶→不买咖啡0.050.0670.678不买咖啡→不买牛奶0.050.20.87所有可能的关联规则1买牛奶→买咖啡0.20.80.847讨论I1﹑I2﹑I3﹑I6共4条规则：由于I1、I2<1，在实际中它的价值不大；I3、I6>1，规则才有价值。兴趣度也称为作用度（Lift）,表示关联规则A→B的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。

讨论I1﹑I2﹑I3﹑I6共4条规则：48概括地说：可信度是对关联规则地准确度的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度（作用度）越大，说明项集B受项集A的影响越大。概括地说：49

2.

Apriori算法Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（FrequentItemset）。使用第1步找到的频繁集产生规则。2.Apriori算法Apriori是挖掘关联规则的一50Apriori使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。Apriori使用一种称作逐层搜索的迭代方法，“K-项集”51

1）Apriori性质性质：频繁项集的所有非空子集都必须也是频繁的。如果项集B不满足最小支持度阈值min-sup，则B不是频繁的，即P（B）<min-sup。如果项A添加到B，则结果项集（即BA）不可能比B更频繁出现。因此，BA也不是频繁的，即P（BA）<min-sup。1）Apriori性质性质：频繁项集的所有非空子集都必须52设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1。有公式：

CK+1=LKLK={XY，其中X，YLK，|XY|=K+1}其中C1是1-项集的集合，取自所有事务中的单项元素。

2）“K-项集”产生“K+1-项集”

设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK53如

L1={{A}，{B}} C2={A}{B}={A，B}，且|AB|=2 L2={{A，B}，{A，C}} C3={A，B}{A，C}={A，B，C}，|ABC|=3如L1={{A}，{B}}543.实例事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C3.实例事务ID事务的项目集T1A,B,ET2B,DT3B,551)

在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第1列。2)

假定最小事务支持计数为2（即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。3)

为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。4)

扫描D中事务，计算C2中每个候选项集的支持度计数，如图中的第4列。5)

确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。见图第5列。1)在算法的第一次迭代，每个项都是候选1-项集的集合C1的566)

候选3-项集的集合C3的产生，得到候选集：C3={{A，B，C}，{A，B，E}，{A，C，E}，{B，C，D}，{B，C，E}，{B，D，E}}按Apriori性质，频繁项集的所有子集必须是频繁的。由于{A，D}，{C，D}，{C，E}，{D，E}不是频繁项集，故C3中后4个候选不可能是频繁的，在C3中