[1]赵阳,白凡. 基于FP-tree的支持度计数优化策略[J].计算机技术与发展,2017,27(10):30-33.
　ZHAO Yang,BAI Fan. Support Count Optimization Method Based on FP-tree[J].,2017,27(10):30-33.
点击复制

 基于FP-tree的支持度计数优化策略()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
27
期数:
2017年10期
页码:
30-33
栏目:
智能、算法、系统工程
出版日期:
2017-10-10

文章信息/Info

Title:
 Support Count Optimization Method Based on FP-tree
文章编号:
1673-629X（2017)10-0030-04
作者:
 赵阳; 白凡
 江南计算技术研究所
Author(s):
 ZHAO Yang; BAI Fan
关键词:
 ; 关联规则挖掘; FP-tree; 最大频繁项集; 支持度计数; 搜索剪枝
Keywords:
 ; association rules mining; FP-tree; maximum frequent itemsets; support count; search prune
分类号:
TP311
文献标志码:
A
摘要:
 关联规则挖掘过程中,频繁项集的挖掘是最关键的步骤.最大频繁项集是最常用的频繁项集简化表示.基于FP-tree的最大频繁项集挖掘算法多数都需要自底向上地搜索FP-tree来计算项集的支持度.而已有的支持度计算方法在计算当前项集的支持度时没有考虑已完成的支持度计算过程所获得的信息,因而造成了不必要的开销.针对该问题,提出了基于FP-tree的支持度计数优化策略(Support Count Optimization Method on FP-tree,SCOM),在付出很小的额外空间代价的条件下,充分利用已完成的支持度计数过程中获取的路径对项集的支持信息和项集之间的关系进行搜索剪枝,并设计实验将该策略应用到DMFIA算法上.实验结果表明,应用该策略的最大频繁项集挖掘算法DMFIA获得了较大的性能提升.SCOM对基于FP-tree的支持度计数进行优化,因此能够应用到所有利用FP-tree进行支持度计数的算法之中.
Abstract:
 In the association rules mining,mining frequent itemsets is the most critical step. Maximum frequent itemsets is the most com-mon simplified representation of frequent itemsets. Maximum frequent itemsets mining algorithms based on FP-tree are most needed to search the FP-tree bottom-up to count the support of the itemsets,but they have not considered the information obtained by completed support counting while counting the current itemset,resulting in unnecessary overhead. To solve it,Support Count Optimization Method on FP-tree,called SCOM for short,is proposed. With a small additional space cost,it can make full use of the information that whether a path supports a itemset and the relation between the itemsets to prune the search. Experimental results show that the maximum frequent itemsets mining algorithm applied obtains a performance boost with SCOM which optimizes the support count based on FP-tree,so it can be applied to all algorithms that use FP-tree to count support.

相似文献/References:

[1]何中胜 庄燕滨.基于Apriori＆Fp—growth的频繁项集发现算法[J].计算机技术与发展,2008,(07):45.
　HE Zhong-sheng,ZHUANG Yan-bin.Algorithm of Mining Frequent Itemset Based on Apriori and Fp - growth[J].,2008,(10):45.
[2]李志云 周国祥.一种基于MFP树的快速关联规则挖掘算法[J].计算机技术与发展,2007,(06):94.
　LI Zhi-yun,ZHOU Guo-xiang.A Fast Association Rule Mining Algorithm Based on MFP Tree[J].,2007,(10):94.
[3]楼巍 刘捷 严利民.协同进化算法在关联规则挖掘中的应用[J].计算机技术与发展,2012,(11):13.
　LOU Wei,LIU Jie,YAN Li-min.Applied Research on Association Rules Mining with Co-evolution Algorithm[J].,2012,(10):13.
[4]张志宏,吴庆波,邵立松,等.基于飞腾平台TOE协议栈的设计与实现[J].计算机技术与发展,2014,24(07):1.
　ZHANG Zhi-hong,WU Qing-bo,SHAO Li-song,et al. Design and Implementation of TCP/IP Offload Engine Protocol Stack Based on FT Platform[J].,2014,24(10):1.
[5]梁文快,李毅. 改进的基因表达算法对航班优化排序问题研究[J].计算机技术与发展,2014,24(07):5.
　LIANG Wen-kuai,LI Yi. Research on Optimization of Flight Scheduling Problem Based on Improved Gene Expression Algorithm[J].,2014,24(10):5.
[6]黄静,王枫,谢志新,等. EAST文档管理系统的设计与实现[J].计算机技术与发展,2014,24(07):13.
　HUANG Jing,WANG Feng,XIE Zhi-xin,et al. Design and Implementation of EAST Document Management System[J].,2014,24(10):13.
[7]侯善江[],张代远[][][]. 基于样条权函数神经网络P2P流量识别方法[J].计算机技术与发展,2014,24(07):21.
　HOU Shan-jiang[],ZHANG Dai-yuan[][][]. P2P Traffic Identification Based on Spline Weight Function Neural Network[J].,2014,24(10):21.
[8]李璨,耿国华,李康,等. 一种基于三维模型的文物碎片线图生成方法[J].计算机技术与发展,2014,24(07):25.
　LI Can,GENG Guo-hua,LI Kang,et al. A Method of Obtaining Cultural Debris’ s Line Chart Based on Three-dimensional Model[J].,2014,24(10):25.
[9]翁鹤,皮德常. 混沌RBF神经网络异常检测算法[J].计算机技术与发展,2014,24(07):29.
　WENG He,PI De-chang. Chaotic RBF Neural Network Anomaly Detection Algorithm[J].,2014,24(10):29.
[10]刘茜[],荆晓远[],李文倩[],等. 基于流形学习的正交稀疏保留投影[J].计算机技术与发展,2014,24(07):34.
　LIU Qian[],JING Xiao-yuan[,LI Wen-qian[],et al. Orthogonal Sparsity Preserving Projections Based on Manifold Learning[J].,2014,24(10):34.
[11]赵阳,吴廖丹. 一种自底向上的最大频繁项集挖掘方法[J].计算机技术与发展,2017,27(08):57.
　ZHAO Yang,WU Liao-dan. A Bottom-up Method for Mining Maximum Frequent Itemsets[J].,2017,27(10):57.

更新日期/Last Update: 2017-11-23