5关联规则及相关算法讲解

《5关联规则及相关算法讲解》由会员分享，可在线阅读，更多相关《5关联规则及相关算法讲解（79页珍藏版）》请在金锄头文库上搜索。

1、关联规则及相关算法,主要内容,关联规则概述 Apriori算法 CARMA算法 序列模式,关联规则概述,数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。 关联规则挖掘的一个典型例子是购物篮分析。 啤酒与尿布的故事,啤酒与尿布的故事,在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。 这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。,啤酒与尿布的故事,沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行

2、为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。 在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。,啤酒与尿布的故事,一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！ 经过大量实际调查和分析，揭示了一个隐藏在“尿布与啤酒”背后的美国人的一种行为模式： 在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。,关联可分为简单关联、时序关联、因果关联

3、。关联分析的目的是找出数据库中隐藏的关联，并以规则的形式表达出来，这就是关联规则。,基本概念,一个样本称为一个“事务” 每个事务由多个属性来确定，这里的属性我们称为“项” 多个项组成的集合称为“项集”,k-项集,由k个项构成的集合 牛奶、啤酒都是1-项集； 牛奶，果冻是2-项集； 啤酒，面包，牛奶是3-项集。 每个事务其实就是一个项集,关联规则的表示,X和Y是项集 X称为规则前项（或者前件，antecedent） Y称为规则后项（或者后件，consequent） 支持度s是数据库中包含 的事务占全部事务的百分比 置信度c是包含 的事务数与包含X的事务数的比值,频繁项集,用户预先定义最小支持度阈

4、值（min_sup）和最小置信度阈值（min_conf）。 如果某个项集的支持度大于等于设定的最小支持度阈值min_sup，称这个项集为“频繁项集”（也称为“大项集”，LargeItemsets），所有的“频繁k-项集”组成的集合通常记作Lk。,关联规则挖掘过程主要包含两个阶段 第一阶段先从数据集中找出所有的频繁项集，它们的支持度均大于等于最小支持度阈值min_sup 第二阶段由这些频繁项集产生关联规则，计算它们的置信度，然后保留那些置信度大于等于最小置信度阈值min_conf的关联规则。,关联规则挖掘算法,广度优先算法 Apriori：频繁项集的非单调性 AprioriTid： Aprior

5、iHybrid 深度优先算法 FP-growth Eclat H-Mine,Apriori算法是挖掘布尔关联规则频繁项集的算法 Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。 先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。,Apriori算法 (1),以表5-1为例 min_sup=0.22,频繁1-项集为 L1=牛奶，果冻，啤酒，面包，花生酱 频繁2-项集为 L2=牛奶,果冻,牛

6、奶,啤酒,牛奶,花生酱,果冻, 啤酒,果冻, 面包,果冻, 花生酱 频繁3-项集为 L3=牛奶,果冻,啤酒,牛奶,果冻,花生酱,2. 由频繁项集产生关联规则 由上一步得到的频繁项集集合 L2 和 L3 中的每一个频繁项集 l 都可以产生关联规则。 以下用 L3 中频繁项集 l = I1, I2, I5 进行说明。 L2 和 L3 中的其它频繁项集的关联规则同理可得。 l I1, I2, I5 的所有的非空子集为： I1, I2，I1, I5，I2, I5，I1，I2 和 I5,对于 l 的每个非空子集 s，计算 s l-s 的置信度并输出规则： I1I2 I5，confidence = 2/4

7、 = 50% I1I5 I2，confidence = 2/2 = 100% I2I5 I1，confidence = 2/2 = 100% I1 I2I5，confidence = 2/6 = 33% I2 I1I5，confidence = 2/7 = 29% I5 I1I2，confidence = 2/2 = 100% 如果最小置信度阈值为70%，则只有2、3 和最后一个规则可以输出，因为只有这些是强的。,在Clementine中应用Apriori算法,应用Apriori节点来对某超市的客户采购数据集进行购物篮分析。该数据集包含有21个属性（这些属性包括：COD、pasta、milk、

8、water、biscuits、coffee、brioches、yoghurt、frozen vegetables、tunny、beer、tomato、souce、coke、rice、juices、crackers、oil、frozen fish、ice cream、mozzarella、tinned meat。其中“COD”是记录编号，其它20个属性代表20种商品），共46243个记录。每个属性代表某种商品，其取值为“0”或者“1”，“0”表示没有购买该商品，“1”表示购买了该商品。,数据源,设置“类型”节点,设置“Apriori”节点,“Apriori”节点的高级选项,浏览模型,作业： 关联

9、规则的两个例子： http:/www.tipdm.org/information/index.jhtml,四、CARMA 算法, CARMA 算法原理 1. 算法组成 2. 算法中的符号定义 3. 算法的基本过程 实例说明 4. 用一个简单的例子说明算法原理。 CARMA 算法描述 5. 用自然语言描述算法的实现过程。,已有的一些关联规则挖掘算法在运行之前要求用户输入最小置信度和最小支持度。而对用户来讲，确定合适的最小置信度和最小支持度比较困难，需要运行算法多次判断最小置信度和最小支持度是否过高或过低。 Christian Hidber 1999年提出了在线挖掘关联规则的算法 CARMA (C

10、ontinuous Association Rule Mining Algorithm)，此算法在运行过程中给用户以反馈，用户可根据反馈信息随时调整最小支持度，如果用户对输出结果已感到满意，可随时终止算法的运行。,所谓在线算法是相对于批处理式算法而言， 有以下特点： 算法执行过程中即能不断产生部分计算结果，供用户参考； 在算法执行过程中，用户能根据产生的部分计算结果控制算法如何进行下去； 算法给出的结果必须是精确的。 在线挖掘关联规则的算法允许用户随时调整最小支持度(阈值)，以得出合理的结果，如果中间结果已经令人满意，用户也可以随时终止算法的执行。,在线算法相对于离线的批处理式的算法而言，可交

11、互性较好。CARMA 算法最多需要遍历交易集合两次，因为第二次遍历不一定需要进行完，如果满足某条件，算法可能在第二次遍历未结束时就终止。在第一次遍历过程中，算法逐步建立起一个潜在的数据项频集的集合 L，对 L 中的每一个数据项集，CARMA 计算其支持度的上界和下界。每处理一条交易之后，算法向用户输出根据当前集合 L 计算出的关联规则以及每条关联规则的支持度和置信度的上界和下界，用户可以根据输出信息调整最小支持度和最小置信度的数值。注意这种调整是随时发生的。如果用户对输出的中间结果满意，可提前结束算法运行。,1. 算法组成 第一步 找出所有频繁项集 第一阶段 Phase I 产生潜在频繁项集

12、V (支持栅格)。在该阶段中可以随时调整最小支持度。 第二阶段 Phase 对潜在频繁项集 V 进行删减得到最终的频繁项集。 第二步由频繁项集产生关联规则 与 Apriori 算法相应部分相同，在此不重复。, CARMA 算法原理,四、 CARMA 算法,在Clementine中应用CARMA算法,对某超市的交易数据进行关联分析，研究销售商品见的关联关系，目的是为超市货架的摆放提供科学的依据，对促销决策提供参考建议。 事务数据集为Clementine自带的Baskets1n数据集，存放在Clementine安装目录下的Demos文件夹中（.clementine12.0DemosBASKETS1

13、n），包含了1000个数据样本，每个样本包含了顾客的卡号、性别、年龄、收入、付款方式等一系列个人信息，以及其购买的各种食品清单，是一个Tabular格式的数据集。,这是一个超市数据库，有18个字段，1000条记录，该例子中数据字段包含如下：,实例研究购物篮分析,六、关联规则挖掘实践,读取文本数据 可以使用“变量文件节点”读取定界文本数据。可以从选项板中添加变量文件节点，方法是单击源选项卡找到此节点，或者使用收藏夹选项卡。 然后，双击新添加的节点以打开相应的对话框。,单击以“” 标记的按钮，浏览 Clementine 安装目录，打开demos 目录，选择文件 BASKETS1n。 选择从文件读取

14、字段名，并注意已载入对话框中的字段和值。,3. 添加表 在已载入数据文件中，可以浏览一下某些记录的值。其中一个方法就是构建一个包含“表节点”的流。 要将表节点添加到流中，可双击选项板中的表节点图标或将其拖放到工作区。,要查看表，单击工具栏上的绿色箭头按钮执行流，或者右键单击表节点，然后选择执行。,表节点可以临时连接流中的不同节点，以便查看这些节点处理后的中间结果。不用时可以删除表节点。,4. 字段处理 对于关联规则中的输入输出字段要求，可以用一个“类型节点”来处理 。 要将“类型节点”添加到流中，可双击选项板中的图标或将其拖放到工作区。,双击流中“类型节点”，然后进行设置。,点击“读取值”按钮

15、将各个字段类型实例化。,5. 构建模型 用前面方法把 “Apriori 节点”和 “Carma 节点” 加到流中。,设置 “Apriori 节点” 选项 (采用默认值)。 要产生关联规则，单击工具栏上的绿色箭头执行流，或单击节点“执行”按钮，可产生“Apriori 模型”。,设置 “Carma 节点” 选项 单击节点“执行”按钮，可产生“Carma 模型”,6. 浏览模型 执行“Apriori节点”时，生成的“Apriori模型”将被添加到窗口右上角的“模型”选项卡中。 右键单击此图标，然后从菜单中选择浏览。,“啤酒蔬菜罐头冻肉”87% “啤酒冻肉蔬菜罐头”86% “冻肉蔬菜罐头啤酒”84%,

16、全部显示 对于“CARMA模型”可以用同样操作，浏览模型内容。,模型的 7 项信息的含意 规则 ID (Rule ID) 规则编号。通过规则 ID，可以标识哪些规则要应用于某个给定的预测。通过规则 ID，还可以在以后合并附加的规则信息，如部署能力、产品信息或条件。 实例 ( Instances) 数据集中包含规则前项的事务数量的。 例如，规则为“冻肉蔬菜罐头啤酒”的实例数为 173，表示训练数据中有 173 个事务包含条件项集冻肉，蔬菜罐头。, 支持度 (Support) 规则条件(前项)支持度 即包含规则前项的事务数量在训练数据中的比例。 例如，规则“冻肉蔬菜罐头啤酒”的支持度为： (173/1000)100%=17.3% 规则支