《第5章基于数据仓库的决策支持系统(4)解析课件.ppt》由会员分享，可在线阅读，更多相关《第5章基于数据仓库的决策支持系统(4)解析课件.ppt（31页珍藏版）》请在三一办公上搜索。
1、1,第5章,基于数据仓库的决策支持系统(4),5.5数据挖掘的决策支持,5.5.3 关联规则的挖掘及其应用基本原理Apriori算法3.实例,关联规则（Association Rule）挖掘是发现大量数据库中项集之间的关联关系。从大量商业事务中发现有趣的关联关系，可以帮助许多商业决策的制定，如分类设计、交叉购物等。Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题。,1关联规则的挖掘原理,关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式。例1：在购买铁锤的顾客当中，有70的人同时购买了铁钉。,例2：年龄在40 岁以上，工作在A区的投
2、保人当中，有45的人曾经向保险公司索赔过。可以看出来，A区可能污染比较严重，环境比较差，索赔率也相对比较高。,（1）基本原理,设I=i1,i2,im是项（Item）的集合。记D为事务（Transaction）的集合，事务T是项的集合，并且TI。设A是I中一个项集，如果AT，称事务T包含A。定义1：关联规则是形如AB的蕴涵式，这里AI，BI，并且AB=。,定义2：规则的支持度。规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)，即：其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。,定义3：规则的可信度规则AB具有可信度C，表示C是包
3、含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即：其中 表示数据库中包含项集A的事务个数。,定义4：阈值。在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度（min_sup）和最小可信度（min_conf）。定义5：项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。如果项集满足最小支持度，则它称之为频繁项集（Frequent Itemset）。,定义6：关联规则。同时满足最小支持度（min_sup）和最小可信度（min_conf）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。,（2）关联规则挖掘过
4、程,关联规则的挖掘一般分为两个过程：1）找出所有的频繁项集：找出支持度大于最小支持度的项集，即频繁项集。2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。,（3）关联规则的兴趣度,例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:,设定minsupp=0.2,minconf=0.6,得到如下的关联规则：买牛奶 买咖啡 s=0.2 c=0.8即80的人买了牛奶就会买咖啡。同时得到结论：90的人肯定会买咖啡。关联规则：买咖啡 不买牛奶 s=0.7 c=0.78支持度和可信度分别为0.7和0.78，更具有商业销售的指导意义。,定义7：兴趣度：公
5、式反映了项集A与项集B的相关程度。若 即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。,一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；兴趣度I不小于0。,所有可能的关联规则,讨论I1I2I3I6共4条规则：由于I1、I21，规则才有价值。兴趣度也称为作用度（Lift）,表示关联规则AB的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。,概括地说：可信度是对关联规则地准确度
6、的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度（作用度）越大，说明项集B受项集A的影响越大。,2.Apriori算法,Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（Frequent Itemset）。使用第1步找到的频繁集产生规则。,Apriori 使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。
7、首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。,1）Apriori 性质,性质：频繁项集的所有非空子集都必须也是频繁的。如果项集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-
8、项集的集合，取自所有事务中的单项元素。,2）“K-项集”产生“K+1-项集”,如 L1=A，BC2=AB=A，B，且|AB|=2L2=A，B，A，CC3=A，BA，C=A，B，C，|ABC|=3,3.实例,1)在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第1列。2)假定最小事务支持计数为2（即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。3)为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。4)扫描D中事务，计算C2中每个候选项
9、集的支持度计数，如图中的第4列。5)确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。见图第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，它由具有最小支持度的C3中候选3项集组成，见图第8列。8）按公式产生候选4项集的集合C4，产生结果A,B,C,E
10、,这个项集被剪去，因为它的子集B,C,E不是频繁的。这样L4=。此算法终止。L3是最大的频繁项集，即：A,B,C和A,B,E。,具体产生过程用图表示,候选集与频繁项集的产生,产生关联规则,根据前面提到的可信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“S LS”。注：LS表示在项集L中除去S子集的项集。,频繁项集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,
