一种基于有效修剪的最大频繁项集挖掘算法

《一种基于有效修剪的最大频繁项集挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一种基于有效修剪的最大频繁项集挖掘算法陈鹏吕卫锋(北京航空航天大学计算机学院，北京100083)摘要：对关联挖掘中的最大频繁项集挖掘问题进行了研究，提出了一种基于项集格修剪机制的最大频繁项集挖掘算法．采用项集格生成树的数据结构，将最大频繁项集挖掘过程转化为对项集格生成树进行深度优先搜索获取所有最大频繁节点的过程．其中提高算法效率的一个重要措施是在遍历项集格生成树的过程中对生成树进行修剪．给出了项集格生成树的三个性质，并在此基础上提出了直接超集修剪、间接超集修剪与事务集等价修剪三种修剪机制，尽可能忽略非频繁节点及其所生成的扩展节点以减少遍历的节点数目．试验结果表明，三种修剪机制都

2、能够有效地减少搜索空间，其中事务集等价修剪机制的效果最好，算法的性能与输入数据集的稠密程度相关．关键词：数据挖掘；关联规则；关联挖掘；格中图分类号：TP311文献标识码：A文章编号：1001-5965(2006)02-0218-06MaximalfrequentitemsetsminingalgorithmbasedoneffectivepruningmechanismsChenPengLtiWeifeng(SchoolofComputerScienceandTechnology,BeijingUniversityofAeronauticsandAstronautics,Bei

3、jing100083,China)Abstract:Themaximalfrequentitemsetsminingproblemwasstudiedandanalgorithmbasedonpruningitem-setlatticeeffectivelywasproposed.Theitemsetlatticetreedatastructurewasadoptedtotranslatemaximalfrequentitemsetsminingintotheprocessofdepth-firstsearchingthe.itemsetlatticetree.Oneofthe

4、keymeasurestopromoteperformanceofthealgorithmistoprunetheitemsetlatticetreewhiletraversingit.Threepropertiesofitemsetlatticetreeweregivenandthreepruningmechanisms,directsupersetpruning,indirectsupersetpruningandtransactionsetsequivalencepruning,wereproposedbasedonthemrespectivelytoprunethein

5、frequentnodesandtheirexten-sionnodestoreducethenumberofnodeswhiletraversingtheitemsetlatticetree.Testresultsindicatethatallthethreepruningmechanismscanreducethesearchspaceeffectivelyandthetransactionsetsequivalencepruninghasthebesteffectonperformanceofthealgorithm.Testresultsalsoindicatethat

6、performanceofthealgorithmisrelatedtodensenessofthedatasets.Keywords:datamining;associationrule;associationmining;lattice