DMStar组-基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘project答辩PPTV5.0.ppt 24页

'基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘DMStar小组杨柳杨华峰宋旋婷任智红梁志溢贺冠文 主要内容Apriori算法FP-Growth算法Eclat算法234频繁模式挖掘实现概述1算法对比评价62 频繁模式挖掘实现概述实现了Apriori、FP-Growth及Eclat三种频繁模式挖掘算法对Mushroom、Accidents、T10I4D100K三个数据集做频繁模式挖掘实验，设定不同的阈值，对比不同算法挖掘频繁模式的时间 Apriori算法描述Apriori算法特点1、k-1项集连接规律：若有两个k-1项集，每个项集保证有序，如果两个k-1项集的前k-2个项相同，而最后一个项不同，则证明它们是可连接的，可连接生成k项集。2、反单调性。如果一个项集是频繁的，那么它的所有子集都是频繁的。即若一个项集的子集不是频繁项集，则该项集肯定也不是频繁项集。 Apriori算法流程1.扫描数据库，生成候选1项集和频繁1项集。2.从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。2.1频繁k-1项集两两组合，判定是否可以连接，若能则连接生成k项集。2.2对k项集中的每个项集检测其子集是否频繁，舍弃掉子集不是频繁项集即不在频繁k-1项集中的项集。2.3扫描数据库，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。3.若当前k项集中只有一个项集时循环结束。 Apriori主要函数说明Map,Integer>genNextKItem(Map,Integer>preMap)由频繁K-1项集生成频繁K项集booleanisNeedCut(Map,Integer>preMap,Setset)由于单调性，必须保证k项集的所有k-1项子集都是频繁的，否则就该剪切该k项集List>getSubSets(Setset)获取k项集set的所有k-1项子集privateMap,Integer>assertFP(Map,Integer>allKItem)遍历事物数据库，求支持度，确保为频繁项集booleanisCanLink(String[]strA1,String[]strA2)检测两个频繁K项集是否可以连接，连接条件是只有最后一个项不同MapfindFP1Items(List>dataTrans)生成频繁1项集6 Apriori算法挖掘结果硬件环境：IntelCore2DuoCPUT57502GHZ,2G内存实验结果F:/DataMiningSample/FPmining/Mushroom.datthreshold:0.25共用时：54015ms共有5545项频繁模式F:/DataMiningSample/FPmining/Mushroom.datthreshold:0.2共用时：991610ms共有53663项频繁模式F:/DataMiningSample/FPmining/Mushroom.datthreshold:0.15结论：对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确，但是算法速度很慢，对大数据量如T10I4D100K低阈值挖掘时间太长解决办法：改用C++写FP-Growth算法做频繁模式挖掘！Sec.18.2 FP-Growth算法FP-Growth算法流程Step1读取数据库，构造频繁1项集及FP-tree Step2遍历FP-tree的头表，对于每个频繁项x，累积项x的所有前缀路径形成x的条件模式库CPBFP-Growth算法 Step3对CPB上每一条路径的节点更新计数为x的计数，根据CPB构造条件FP-treeStep4从条件FP-tree中找到所有长路径，对该路径上的节点找出所有组合方式，然后合并计数Step5将Step4中的频繁项集与x合并，得到包含x的频繁项集Step2-5循环，直到遍历头表中的所有项FP-Growth算法 FP-Growth算法的实现由于时间紧迫，基于芬兰教授BartGoethals的开源代码实现 FP-Growth算法挖掘结果Mushroom.dat挖掘时间 FP-Growth算法挖掘结果Accidents.dat挖掘时间 FP-Growth算法挖掘结果T10I4D100K.dat挖掘时间 Eclat算法算法思想：由频繁k项集求交集，生成候选k+1项集。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代，直到项集归一。算法过程：1.一次扫描数据库，获得初始数据。包括频繁1项集，数据库包含的所有items，事务总数（行）transNum，最小支持度minsup=limitValue*trans。2.二次扫描数据库，获得频繁2项集。3.按照Eclat算法，对频繁2项集迭代求交集，做裁剪，直到项集归一。 主要数据结构：ClassItemSet{intitem=k;//频繁k项集intminsup;BitSetitems;//存放k项BitSettrans;//所谓TidSet}ClassHeadNode{longitems;//每一分块所包含的ItemSet个数，如果items=1，没有ItemSet合并ItemSetfirst;//指向分块第一个ItemSetItemSetlast;//指向分块第最后一个ItemSet}ArrayListarray：长度为数据库所包含的项数。以mushroom为例array.length=119。 ClassHashNode{BitSetbs;//临时存放频繁k+1项集itemset.itemsHashNodenext;}ClassHashHeadNode{HashNodefirst;//指向第一个HashNode}HashHeadNode[]hashTable 实现要点：1.将求频繁项集问题分块求解。以mushroom为例，所有的有序频繁项集可以分成118类。例如：1391323253436384052545963677685869093981071131块：2项：{1,3}，{1,9}，{1,13}，……3项：{1,3,9}，{1,3,13}，{1,3,23}…………..2块：3块：2项：{3,9}，{3,13}，……3项：{3,9,13}，{3,9,23}，…….…….........118块：2项：{118,119}ArrayListarray中每个HeadNode指向相应的块，每块由ItemSet链表记录。优点：提高运算速度，每次求频繁k项集，只是分块计算，块与块之间不用计算。 2.生成频繁2项集2次扫描数据库，生成频繁2项集。充分利用数据库中数据的有序性，利用2维数组TreeSet[][]a生成有序的频繁2项集。a中每一行代表相应的一块。例如：候选2项集{1,3}，事务(行)号为1，那么a[1][3].add(1)。再扫描一遍做裁剪，将事务数小于minsup的项集删除，同时生成初始的ArrayListarray (2)裁剪将支持度小于minsup的候选项集删除。注意：在算法运行过程中会产生大量的ItemSet对象，java垃圾回收机制不能及时清除所有无用对象，很容易造成内存溢出。可以做一点改进。在自连接过程中，将每次无用的所有k-1项频繁项集收集到一起，生成k+1频繁项集时，先从收集的空间中分配。如果不够，再创建新的ItemSet对象。但是，如果k+1频繁项个数远远大于k-1频繁项个数，这种方法不能从根本上解决问题。 结果：1.只生成数据库mushroom的频繁模式，其中阈值为0.05情况，由于内存溢出没有生成。Mushroom阈值0.10.150.20.25模式数目57451398575536635545时间(s)24.5315.6724.6563.515 注:(1)所有频繁模式数目，也包括频繁1项集(2)minsup=limitValue*transNum，minsup有可能不是整数，如果对其下取整会得到上面的数据，如果上取整得到的数据会比上面所列的数据小。 QA&Thanks'