搜索
数据挖掘实验数据挖掘实验报告——Apriori算法和FP增长算法挖掘频繁项集问题描述：一、数据库有5个事务如：表-0。设min_sup=60%,min_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}表-0分别使用Apriori和FP增长算法找出所有频繁项集。并比较两种挖掘过程的效率。列举所有与下面元规则匹配的强关联规则（给出支持度s和置信度c），其中，X是代表顾客的变量，itemi是表示项的变量（如“A”，“B”）：∀x∈transaction,buys(X,item1)∧buys(X,item2)⟹buys(X,item3)[𝑠,𝑐]问题分析：1.分别使用Apriori算法和FP算法逐步求的所有的频繁项集，记录各自使用的扫描事务的总次数，用于探究各自的效率。2.对于问题二可以采取如下步骤解决：首先找出所有三项频繁项集，然后按照元规则匹配出关联规则，最后利用支持度和置信度选出强关联规则。解决方案：1.采用Aporior算法挖掘所有频繁项集的步骤：1)扫描数据库，对每个候选计数，得频繁一项候选集C1如表-1：项集支持度计数{A}1{C}2{D}1{E}4{I}1{K}5{M}3{N}2{O}3{U}1{Y}3数据挖掘实验表-12)由比较候选支持度计数与最小支持度计数（min_sup*5=3）得频繁一项集L1如表-2：项集支持度计数{E}4{K}5{M}3{O}3{Y}3表-23)连接（L1⋈L1）得频繁二项候选集C2如表-3：项集支持度计数{E,K}4{E,M}2{E,O}3{E,Y}2{K,M}3{K,O}3{K,Y}3{M,O}1{M,Y}2{O,Y}2表-34)扫描数据库由比较候选支持度计数与最小支持度计数得频繁二项集L2如表-4：项集支持度计数{E,K}4{E,O}3{K,M}3{K,O}3{K,Y}3表-45)重复步骤3）（此处可以不用扫描数据库而是利用Aprioir剪枝进行选择）求的频繁三项候选集C3如表-5：项集支持度计数{E,K,O}3{E,K,M}2{E,K,Y}2{K,M,O}1{K,M,Y}2{K,O,Y}2表-56)使用Apriori剪枝可以去掉C3中的{E,K,M},{E,K,Y},{K,M,O},{K,M,Y},{K,Y,O}(因为这些项集中存在不属于L2中的子集)，求的L3。数据挖掘实验L3=={E,K,O}即求的所有频繁项集L1，L2，L3。2.采用FP增长算法挖掘所有频繁项集得步骤：1)扫描事务数据库，收集频繁一项集L和对应的支持度计数并按降序排列得表-6：项集支持度计数{K}5{E}4{M}3{Y}3{O}32)再次扫描事务数据库，构造FP树如图-1所示：3)通过创建条件模式基挖掘FP树：项条件模式基条件FP树频繁项集Y{{K,E,M,Y:1},{K,E,Y:1},{K,M,Y:1}}K:3{K,Y}M{{K,E,M:2},{K,M:1}}K:3{K,M}O{{K,E,M,Y:1},{K,E,Y:1},{K,E:1}}K:3,E:3{K,O},{E,O},{K,E,O}E{K:5}{K:5}{K,E}即求的所有频繁项集。效率分析：在Apriori算法中1）2）3）4）步中需要扫描数据库多次。而在FP增长算法中只需要在1）2）步骤中扫描数据库。因此FP增长算法的效率比Apriori算法效率高！Null{}E：4频繁模式信息的FP树图-1数据挖掘实验由频繁三项集L3={K,E,O}产生关联规则且匹配元规则的关联规则有：K∧E⟹OConfidence=2/4min_conf=80%弱关联规则K∧O⟹EConfidence=100%min_conf=80%强关联规则E∧O⟹KConfidence=100%min_conf=80%强关联规则*注：s=3,c=1.实验总结：一、在构造FP增长树时不熟练，导致树的节点路劲与数据库中的事务不吻合。二、利用FP增长树挖掘频繁项集时，产生频繁项集与条件树的依赖关系不明确。报告人：***