基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘主要内容频繁模式挖掘实现概述Apriori算法描述Apriori算法流程Apriori主要函数说明Apriori算法挖掘结果FP-Growth算法Step2遍历FP-tree的头表，对于每个频繁项x，累积项x的所有前缀路径形成x的条件模式库CPBStep3对CPB上每一条路径的节点更新计数为x的计数，根据CPB构造条件FP-treeStep4从条件FP-tree中找到所有长路径，对该路径上的节点找出所有组合方式，然后合并计数Step5将Step4中的频繁项集与x合并，得到包含x的频繁项集FP-Growth算法的实现FP-Growth算法挖掘结果FP-Growth算法挖掘结果FP-Growth算法挖掘结果Eclat算法主要数据结构：ClassItemSet{intitem=k;//频繁k项集intminsup;BitSetitems;//存放k项BitSettrans;//所谓TidSet}ClassHeadNode{longitems;//每一分块所包含的ItemSet个数，如果items=1，没有ItemSet合并ItemSetfirst;//指向分块第一个ItemSetItemSetlast;//指向分块第最后一个ItemSet}ArrayList<HeadNode>array：长度为数据库所包含的项数。以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}ArrayList<HeadNode>array中每个HeadNode指向相应的块，每块由ItemSet链表记录。优点：提高运算速度，每次求频繁k项集，只是分块计算，块与块之间不用计算。2.生成频繁2项集2次扫描数据库，生成频繁2项集。充分利用数据库中数据的有序性，利用2维数组TreeSet[][]a生成有序的频繁2项集。a中每一行代表相应的一块。例如：候选2项集{1,3}，事务(行)号为1，那么a[1][3].add(1)。再扫描一遍做裁剪，将事务数小于minsup的项集删除，同时生成初始的ArrayList<HeadNode>array(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有可能不是整数，如果对其下取整会得到上面的数据，如果上取整得到的数据会比上面所列的数据小。