1、1 第第5章章基于基于数据仓库的数据仓库的决策支持系统决策支持系统 (4)5.5数据挖掘的决策支持数据挖掘的决策支持5.5.3 关联规则的挖掘及其应用关联规则的挖掘及其应用1.基本原理基本原理2.Apriori算法算法3.实例实例n关联规则（关联规则（Association Rule）挖掘是发现大）挖掘是发现大量数据库中项集之间的关联关系。量数据库中项集之间的关联关系。n从大量商业事务中发现有趣的关联关系，可以从大量商业事务中发现有趣的关联关系，可以帮助许多商业决策的制定，如分类设计、交叉帮助许多商业决策的制定，如分类设计、交叉购物等。购物等。nAgrawal等人于等人于1993年首先提出了挖
2、掘顾客年首先提出了挖掘顾客交易数据库中项集间的关联规则问题交易数据库中项集间的关联规则问题。1关联规则的挖掘原理关联规则的挖掘原理 关联规则是发现交易数据库中不同商品关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买（项）之间的联系，这些规则找出顾客购买行为模式行为模式。例例1：在购买铁锤的顾客当中，有在购买铁锤的顾客当中，有70的人同时的人同时购买了铁钉。购买了铁钉。例例2：年龄在：年龄在40 岁以上，工作在岁以上，工作在A区的区的投保人当中，有投保人当中，有45的人曾经向保险公的人曾经向保险公司索赔过。司索赔过。可以看出来，可以看出来，A区可能污染比较严重，区可能污染
3、比较严重，环境比较差，索赔率也相对比较高。环境比较差，索赔率也相对比较高。（1）基本原理基本原理n设设I=i1,i2,im是项（是项（Item）的集合。）的集合。n记记D为事务（为事务（Transaction）的集合，）的集合，n事务事务T是项的集合，并且是项的集合，并且T I。n设设A是是I中一个项集，如果中一个项集，如果A T，称事务，称事务T包含包含A。定义定义1：关联规则是形如：关联规则是形如AB的蕴涵式，这里的蕴涵式，这里A I，B I，并且，并且A B=。定义定义2：规则的支持度。：规则的支持度。规则规则AB在数据库在数据库D中具有支持度中具有支持度S，表示，表示S是是D中事务同时
4、包含中事务同时包含AB的百分比，它是概率的百分比，它是概率P(AB)，即：，即：其中其中|D|表示事务数据库表示事务数据库D的个数，表示的个数，表示A、B两两个项集同时发生的事务个数。个项集同时发生的事务个数。|D|AB|P(AB)B)(A S定义定义3：规则的可信度：规则的可信度规则规则AB具有可信度具有可信度C，表示，表示C是包含是包含A项集的同项集的同时也包含时也包含B项集，相对于包含项集，相对于包含A项集的百分比，项集的百分比，这是条件概率这是条件概率P(B|A)，即：，即：其中其中 表示数据库中包含项集表示数据库中包含项集A的事务个数。的事务个数。|A|AB|)|()BA(ABPC|
5、A|定义定义4：阈值。：阈值。在事务数据库中找出有用的关联规则，需要由用户确在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：定两个阈值：最小支持度最小支持度（min_sup）和）和最小可信最小可信度度（min_conf）。）。定义定义5：项的集合称为项集（：项的集合称为项集（Itemset），包含），包含k个项个项的项集称之为的项集称之为k-项集。项集。如果项集满足最小支持度，则它称之为如果项集满足最小支持度，则它称之为频繁项集频繁项集（Frequent Itemset）。）。定义定义6：关联规则。：关联规则。同时满足最小支持度（同时满足最小支持度（min_sup）和最小可信）和最小
6、可信度（度（min_conf）的规则称之为关联规则，即）的规则称之为关联规则，即成立时，规则称之为成立时，规则称之为关联规则关联规则，也可以称为，也可以称为强关强关联规则联规则。(A B)min_sup(A B)min_confSC,（2）关联规则挖掘过程关联规则挖掘过程关联规则的挖掘一般分为两个过程：关联规则的挖掘一般分为两个过程：1）找出所有的频繁项集找出所有的频繁项集：找出支持度大：找出支持度大于最小支持度的项集，即频繁项集。于最小支持度的项集，即频繁项集。2）由频繁项集产生关联规则由频繁项集产生关联规则：根据定义，：根据定义，这些规则必须满足最小支持度和最小可这些规则必须满足最小支持度
7、和最小可信度。信度。（3）关联规则的兴趣度关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。例子：讨论不购买商品与购买商品的关系。设，交易集设，交易集D，经过对，经过对D的分析，得到表格的分析，得到表格:买咖啡买咖啡不买咖啡不买咖啡合计合计买牛奶买牛奶20205 52525不买牛奶不买牛奶70705 57575合计合计90901010100100设定设定minsupp=0.2,minconf=0.6,得到如下的得到如下的关联规则：关联规则：买牛奶买牛奶 买咖啡买咖啡 s=0.2 c=0.8即即80的人买了牛奶就会买咖啡。的人买了牛奶就会买咖啡。同时得到结论：同时得到结论：90的人肯定会买咖
8、啡。的人肯定会买咖啡。关联规则：关联规则：买咖啡买咖啡 不买牛奶不买牛奶 s=0.7 c=0.78支持度和可信度分别为支持度和可信度分别为0.7和和0.78，更具有商业销售，更具有商业销售的指导意义。的指导意义。定义定义7：兴趣度：兴趣度：公式反映了项集公式反映了项集A与项集与项集B的相关程度。的相关程度。若若 即即表示项集表示项集A出现和项集出现和项集B是相互独立的。是相互独立的。若若表示表示A出现和出现和B出现是负相关的。出现是负相关的。若若表示表示A出现和出现和B出现是正相关的。意味着出现是正相关的。意味着A的出现的出现蕴含蕴含B的出现。的出现。()()()()P ABI ABP A P
9、 B1 )BA(I)()()(BPAPABPI(A)1Bn一条规则的兴趣度越大于一条规则的兴趣度越大于1说明我们对这条规说明我们对这条规则越感兴趣（即其实际利用价值越大）；则越感兴趣（即其实际利用价值越大）；n一条规则的兴趣度越小于一条规则的兴趣度越小于1说明我们对这条规说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；利用价值越大）；n兴趣度兴趣度I不小于不小于0。所有可能的关联规则所有可能的关联规则 Rules Rules S SC CI I1 1 买牛奶买牛奶买咖啡买咖啡0.20.20.80.80.89 0.89 2 2买咖啡
10、买咖啡买牛奶买牛奶 0.20.20.220.220.89 0.89 3 3买牛奶买牛奶不买咖啡不买咖啡0.050.050.20.22 24 4不买咖啡不买咖啡买牛奶买牛奶0.050.050.50.52 25 5不买牛奶不买牛奶买咖啡买咖啡0.70.70.930.931.0371.0376 6买咖啡买咖啡不买牛奶不买牛奶0.70.70.780.781.0371.0377 7不买牛奶不买牛奶不买咖啡不买咖啡0.050.050.0670.0670.670.678 8不买咖啡不买咖啡不买牛奶不买牛奶0.050.050.20.20.870.87讨论讨论I1I2I3I6共共4条规则：条规则：由于由于I1、
11、I21，规则才有价值。，规则才有价值。兴趣度也称为作用度（兴趣度也称为作用度（Lift）,表示关联规则表示关联规则AB的的“提升提升”。如果作用度（兴趣度）不。如果作用度（兴趣度）不大于大于1，则此关联规则就没有意义了，则此关联规则就没有意义了。概括地说：概括地说：可信度可信度是对关联规则地准确度的衡量。是对关联规则地准确度的衡量。支持度支持度是对关联规则重要性的衡量。支持度说明了这条规是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则
12、实用的机会很小，因此也不重要。该关联规则实用的机会很小，因此也不重要。兴趣度兴趣度（作用度）描述了项集（作用度）描述了项集A对项集对项集B的影响力的大小。的影响力的大小。兴趣度（作用度）越大，说明项集兴趣度（作用度）越大，说明项集B受项集受项集A的影响越大。的影响越大。2.Apriori算法算法Apriori是挖掘关联规则的一个重要方法。是挖掘关联规则的一个重要方法。算法分为两个子问题：算法分为两个子问题：n找到所有支持度大于最小支持度的项集找到所有支持度大于最小支持度的项集（Itemset），这些项集称为），这些项集称为频繁集频繁集（Frequent Itemset）。）。n使用第使用第1步
13、找到的步找到的频繁集产生规则频繁集产生规则。nApriori 使用一种称作逐层搜索的迭代方法，使用一种称作逐层搜索的迭代方法，“K-项集项集”用于探索用于探索“K+1-项集项集”。n首先，找出频繁首先，找出频繁“1-项集项集”的集合。该集合记作的集合。该集合记作L1。L1用于找频繁用于找频繁“2-项集项集”的集合的集合L2，而，而L2用于找用于找L3，n如此下去，直到不能找到如此下去，直到不能找到“K-项集项集”。找每个。找每个LK需需要一次数据库扫描要一次数据库扫描。1）Apriori 性质性质性质：频繁项集的所有非空子集都必须也是频繁的。性质：频繁项集的所有非空子集都必须也是频繁的。如果项
14、集如果项集B不满足最小支持度阈值不满足最小支持度阈值min-sup，则，则B不不是频繁的，即是频繁的，即 P（B）min-sup。如果项如果项A添加到添加到B，则结果项集（即，则结果项集（即BA）不可能比）不可能比B更频繁出现。因此，更频繁出现。因此，BA也不是频繁的，即也不是频繁的，即 P（BA）min-sup。设设K-项集项集LK，K+1项集项集LK+1，产生，产生LK+1的候选集的候选集CK+1。有公式：。有公式：CK+1=LKLK=XY，其中，其中X，Y LK，|XY|=K+1其中其中C1是是1-项集的集合，取自所有事务中的单项项集的集合，取自所有事务中的单项元素。元素。2）“K-项集
15、项集”产生产生“K+1-项集项集”如如 L1=A，BC2=AB=A，B，且|AB|=2L2=A，B，A，CC3=A，BA，C=A，B，C，|ABC|=33.实例实例事务事务ID事务的项目集事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C1)在算法的第一次迭代，每个项都是候选在算法的第一次迭代，每个项都是候选1-项集的集合项集的集合C1的的成员。算法扫描所有的事务，对每个项的出现次数计数。见成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第图中第1列。列。2)假定最小事务支持计数为假定最小事务支持计数为2（即（即m
16、in-sup=2/9=22%），可以确定频繁），可以确定频繁1-项集的集合项集的集合L1。它由具有最小支持度的候选它由具有最小支持度的候选1-项集组成。见图中第项集组成。见图中第2列。列。3)为发现频繁为发现频繁2-项集的集合项集的集合L2，算法使用，算法使用L1*L1来产生候选集来产生候选集C2。见图中第。见图中第3列。列。4)扫描扫描D中事务，计算中事务，计算C2中每个候选项集的支持度计数，如中每个候选项集的支持度计数，如图中的第图中的第4列。列。5)确定频繁确定频繁2-项集的集合项集的集合L2，它由具有，它由具有最小支持度的最小支持度的C2中的候选中的候选2-项集组成。见图第项集组成。见
17、图第5列列。6)候选候选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，它由具有最小支持度的，它
18、由具有最小支持度的C3中候选中候选3项集组成，项集组成，见图第见图第8列。列。8）按公式产生候选按公式产生候选4项集的集合项集的集合C4，产生结果，产生结果A,B,C,E,这个项集被剪去，因为它的子集这个项集被剪去，因为它的子集B,C,E不是频繁的。这样不是频繁的。这样L4=。此算法终止。此算法终止。L3是最大的频是最大的频繁项集，即：繁项集，即：A,B,C和和A,B,E。具体产生过程用图表示具体产生过程用图表示 候选集与频繁项集的产生候选集与频繁项集的产生 项集支持度计数A,B4A,C4A,E2B,C4B,D2B,E2项集A,B，CA,B，EC3候选集L2频繁2-项集计算支持度项集 支持度计
19、数A,B,C2A,B,E2项集 支持度计数A,B,C2A,B,E2C3候选集L3频繁3-项集产生关联规则产生关联规则根据前面提到的可信度的定义，关联规则的产生根据前面提到的可信度的定义，关联规则的产生如下：如下：（1）对于每个频繁项集）对于每个频繁项集L，产生，产生L的所有非空子的所有非空子集；集；（2）对于）对于L的每个非空子集的每个非空子集S，如果，如果则输出规则则输出规则“S LS”。注：注：LS表示在项集表示在项集L中除去中除去S子集的项集子集的项集。confmin_SL 频繁项集频繁项集L=A，B，E，可以由，可以由L产生哪些关联规则？产生哪些关联规则？L的非空子集的非空子集S有：有：A,B,A,E,B,E,A,B,E。可得到关联规则如下：可得到关联规则如下：A B E conf=2/4=50%A E B conf=2/2=100%B E A conf=2/2=100%A B E conf=2/6=33%B A E conf=2/7=29%E A B conf=2/2=100%假设最小可信度为假设最小可信度为60，则最终输出的关联规则为：，则最终输出的关联规则为：A E B 100%B E A 100%E A B 100%对于频繁项集对于频繁项集A，B，C，同样可得其它关联规则。，同样可得其它关联规则。习题习题 42、44
