基于邻接矩阵的fp-tree构造算法

《基于邻接矩阵的fp-tree构造算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用2011，47（7）153基于邻接矩阵的FP-tree构造算法刘应东1，冷明伟2，陈晓云3LIUYingdong1，LENGMingwei2，CHENXiaoyun31.兰州交通大学交通运输学院，兰州7300702.上饶师范学院数学与计算机系，江西上饶3340003.兰州大学信息科学与工程学院，兰州7300001.SchoolofTrafficandTransportation，LanzhouJiaotongUnivers

2、ity，Lanzhou730070，China2.DepartmentofMathematicsandComputer，ShangraoNormalUniversity，Shangrao，Jiangxi334000，China3.SchoolofInformationScienceandEngineering，LanzhouUniversity，Lanzhou730000，ChinaLIUYingdong，LENGMingwei，CHENXiaoyun.ConstructionalgorithmofFP-

3、treebasedonadjacencymatrix.Comput-erEngineeringandApplications，2011，47（7）：153-155.Abstract：AconstructionalgorithmofFP-treebasedonadjacencymatrixisproposed.Anadjacencymatrixaboutsupportcountof2-frequentitemsetsisconstructedbyscanningdatabase.Usingtheadjace

4、ncymatrix，FP-treeisestablishedafteritemsetsarefilteredandrestructured.Forthenumbersofbranches，nodesanddepthsarereducedgreatly，thestoragespaceisfarlessandergodictimeisshortermuch.Theconstructionalgorithmistestedandverifiedusingstandarddatasets.There-sultsh

5、owsthenewconstructionstrategycanimproveefficiencyoffrequentitemminingandensurevalidityoftheresultscomparedwithothersalgorithms.Keywords：datamining；frequentitemsets；FP-treealgorithm；adjacencymatrix摘要：提出了一种基于邻接矩阵的FP-tree构造方法。首先通过扫描数据库建立2-项集支持数的邻接矩阵，通过邻接矩阵对项

6、进行过滤和新方式排序，然后再利用邻接矩阵构造FP-tree，使得FP-tree的分支、节点数和深度大幅度地减少，从而使存储空间减少、遍历时间缩短。最后使用标准数据集进行验证测试并和其他算法的比较，实验结果表明，该算法在保证结果的同时有效地提高频繁项集挖掘的效率。关键词：数据挖掘；频繁项集；FP-tree算法；邻接矩阵DOI：10.3778/j.issn.1002-8331.2011.07.044文章编号：1002-8331（2011）07-0153-03文献标识码：A中图分类号：TP301针对Aprior

7、i算法[1]的固有缺陷，J.Han等提出了不产生候少，占用内存减少，并提高了挖掘效率。选挖掘频繁项集的方法FP-tree频集算法[2]。对于FP-tree算法其优点是不需要产生候选项集，在内存能满足要求的情况下1问题的描述只需两次扫描数据库，与Apriori-类算法相比，具有较快的挖掘频繁项集的概念[3]可描述如下：给定项集I={il，i2，…，im}，速度。但如果大项集的数量很多，并且如果由原数据库得到事务数据库D={T1，T2，…，Tn}，其中每个事务T（iÎ[1，2，…，i的FP-tree的分支很多

8、且分支长度很长时，该算法需要构造出n]）包含事务ID号TID和一个I中项的子集。I的子集也是项数量巨大的条件FP-tree，不仅费时而且占用大量的空间，挖掘集或模式，根据定义，项集X的支持度计数sup_coun（tX）是D效率不高，而且递归算法本身效率也较低。所以在挖掘大型中包含项集的事务数；X的支持度：support=sup_coun（tX）/

9、D

10、，数据库时，占用内存大，运行速度慢。因此在利用FP-tree数据其中

11、D

12、是