数据挖掘FP与Apriori试验报告

1、数据挖掘买验 数据挖掘实验报告 - Apriori算法和FP增长算法挖掘频繁项集 问题描述: 一、数据库有5个事务如：表设min_sup=60%zmin_conf=80% TID 购买的商品 T100 M,O,N,K,E,Y T200 D,O,N,K,E,Y T300 M,A,K,E T400 M,U,C,K,Y T500 C,O,O,K,I,E 表 分别使用Apriori和FP增长算法找出所有频繁项集。并比较两种挖掘过程的效率。 列举所有与卜面元规则匹配的强关联规则(给出支持度s和置信度c),其中，X是代表 顾客的变量，itemi是表示项的变量(如“A”，B”)： V x transacti

2、on,buys(X, item!) A buys(X, item2) = buys(X, iteni3) s, c 问题分析： 1. 分别使用Apriori算法和FP算法逐步求的所有的频繁项集，记录各自使用的扫描事务的 总次数，用于探究各自的效率。 2. 对于问题二可以采取如卜步骤解决：首先找出所仔三项频繁项集，然后按照元规则匹配 出关联规则，最后利用支持度和置信度选出强关联规则。 解决方案: 1.采用Aporior算法挖掘所有频繁项集的步骤： 1) 扫描数据库，对每个候选计数，得频繁一项候选集C1如表1： 项集 支持度计数 A 1 C 2 D 1 E 4 0) 1 K 5 M 3 N 2 0

3、 3 数据挖掘买验 U 1 Y 3 数据挖掘买验 表1 2）由比较候选支持度计数与最小支持度计数（min_sup*5=3）得频繁一项集L1如表2 项集 支持度计数 E 4 的 5 M 3 0 3 Y 3 表2 3）连接（L1XL1）得频繁二项候选集C2如表3： 项集 k持度计数 E，K 4 E，M 2 E,0 3 E,Y 2 K,M 3 K,0 3 K,Y 3 M,0 1 M,Y 2 0，Y 2 表3 4）扫描数据咋由比较候选支持度计数与最小支持度计数得频繁二项集L2如表.4： 项集 k持度计数 E,K 4 E,。 3 K,M 3 K,0 3 K,Y 3 表4 5）重复步骤3）（此处可以不用扫

4、描数据库而是利用Aprioir剪枝进行选择）求的频繁三项 候选集C3如表5： 项集 支持度计数 E,K,0 3 E,K,M ) 2 E,K,Y 2 K,M,0 1 K,M,Y 2 K,O,Y 2 表5 6）使用Apriori剪枝可以去掉C3中的E,K,M,E,K,Y,K,M,O,K,M,Y,K,Y,O（因为这些项集中 存在数据挖掘买验 不属于L2中的子集），求的L3。数据挖掘买验 L3=E,K,0 即求的所有频繁项集LL L2, L3。 2.采用FP增长算法挖掘所有频繁项集得步骤： 1）扫描事务数据库，收集频繁一项集L和对应的支持度计数并按降序排列得表6： 项集 支持度计数 的 5 E 4 M

5、 3 Y 3 0 3 2）再次扫描事务数据库，构造FP树如图-1所示: 频繁模式信息的FP树图.1 3）通过创建条件模式基挖掘FP树: 项 条件模式基 条件FP树 频繁项集 Y K,E,M,Y:1,K,E,Y:1,K,M,Y:1 K,Y M K,E,M:2,K,M:1 K,M 0 K,E,M,Y:1,K,E,Y:1,K,E:1 K,O,E,O,K,E,O E K：5 (K：5 K,E 数据挖掘买验 即求的所有频繁项集。 效率分析：在Apriori算法中1） 2） 3） 4）步中分要扫描数据库多次而在FP增长算法中只 需要在1） 2）步骤中扫描数据库。因此FP增长算法的效率比Apriori算法效率高！ 由频繁三项集L3=K,E,0产生关联规则旦匹配元规则的关联规则任 KAE=0 Confidence=2/4 E Confidence=100%min_conf=80% 强关联规则 EAO= K Confidence=100%min_conf=80% 强关联规则 注：s=3