[1]蒋东洁,李玲娟.基于单向频繁模式树的频繁项集挖掘算法[J].计算机技术与发展,2019,29(10):175-180.[doi:10. 3969 / j. issn. 1673-629X. 2019. 10. 034]
　JIANG Dong-jie,LI Ling-juan.Frequent Itemset Mining Algorithm Based on UFP-tree[J].,2019,29(10):175-180.[doi:10. 3969 / j. issn. 1673-629X. 2019. 10. 034]
点击复制

基于单向频繁模式树的频繁项集挖掘算法()
分享到：

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

卷:
29
期数:
2019年10期
页码:
175-180
栏目:
智能、算法、系统工程
出版日期:
2019-10-10

文章信息/Info

Title:
Frequent Itemset Mining Algorithm Based on UFP-tree
文章编号:
1673-629X(2019)10-0175-06
作者:
蒋东洁; 李玲娟
南京邮电大学 计算机学院,江苏 南京 210023
Author(s):
JIANG Dong-jie; LI Ling-juan
School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
关键词:
数据挖掘; 频繁项集; 单向频繁模式树; 被约束子树
Keywords:
data mining; frequent itemset; UFP-tree; constrained sub-tree
分类号:
TP301.6
DOI:
10. 3969 / j. issn. 1673-629X. 2019. 10. 034
摘要:
频繁项集挖掘是关联规则挖掘的关键步骤。 FP-Growth 算法是一种有效的频繁项集挖掘算法,它以自底向上的方式探索频繁模式树 FP-tree,由 FP-tree 产生频繁项集。 但是由于需要递归生成大量的条件 FP-tree,其时间复杂度和空间复杂度都较高。 针对这一问题,设计了一种基于单向频繁模式树的频繁项集挖掘算法 UFIM。 此算法首先构造一种单向频繁模式树 UFP-tree 结构,然后在 UFP-tree 上引入被约束子树,并对指向不同端点和指向相同端点的被约束子树分别采用递归和非递归的方法来挖掘频繁项集。 非递归的方法判断端点的支持度计数是否小于最小支持度计数,若小于最小支持度计数则该棵被约束子树无频繁项集,否则其频繁项集是除根节点外的节点的排列组合。 在 mushroom 数据集上的实验结果表明,UFIM 算法的运行速度高于同类算法。
Abstract:
Mining frequent itemset is a key step in mining association rules. The FP-Growth algorithm is an efficient frequent itemset mining algorithm which explores the frequent pattern tree (FP-tree) by a bottom-up way,and generates frequent items by mining the FP-tree. However,its time complexity and space complexity are high because of needing to recursively generate a large number of conditional FP-tree. Aiming at this problem,we design a frequent itemset mining algorithm named UFIM based on unidirectional frequent pattern tree. This algorithm first constructs a unidirectional frequent pattern tree (UFP-tree) structure,then introduces a constrained sub-tree on the constructed UFP-tree; divides the constrained sub-tree into two cases:pointing to different endpoints and pointing to the same endpoints,and respectively uses recursive method and non-recursive method to mine frequent itemset. The non-recursive method determines whether the endpoint’s support count is smaller than the minimum support count. If it is smaller,the restricted sub-tree does not have frequent itemset, otherwise the frequent itemset of the restricted subtree is a node arrangement combination of the nodes besides root node. The experiment of mining frequent item set on the mushroom dataset shows that the running speed of the UFIM algorithm is higher than similar algorithms.

相似文献/References:

[1]项响琴 汪彩梅.基于聚类高维空间算法的离群数据挖掘技术研究[J].计算机技术与发展,2010,(01):120.
　XIANG Xiang-qin,WANG Cai-mei.Study of Outlier Data Mining Based on CLIQUE Algorithm[J].,2010,(10):120.
[2]吉同路 柏永飞 王立松.住宅与房地产电子政务中数据挖掘的应用研究[J].计算机技术与发展,2010,(01):235.
　JI Tong-lu,BAI Yong-fei,WANG Li-song.Study and Application of Data Mining in E-government of House and Real Estate Industry[J].,2010,(10):235.
[3]杨静 张楠男 李建 刘延明 梁美红.决策树算法的研究与应用[J].计算机技术与发展,2010,(02):114.
　YANG Jing,ZHANG Nan-nan,LI Jian,et al.Research and Application of Decision Tree Algorithm[J].,2010,(10):114.
[4]赵裕啸 倪志伟 王园园 伍章俊.SQL Server 2005数据挖掘技术在证券客户忠诚度的应用[J].计算机技术与发展,2010,(02):229.
　ZHAO Yu-xiao,NI Zhi-wei,WANG Yuan-yuan,et al.Application of Data Mining Technology of SQL Server 2005 in Customer Loyalty Model in Securities Industry[J].,2010,(10):229.
[5]吴楠 胡学钢.基于聚类分区的序列模式挖掘算法研究[J].计算机技术与发展,2010,(06):109.
　WU Nan,HU Xue-gang.Research on Clustering Partition-Based Approach of Sequential Pattern Mining[J].,2010,(10):109.
[6]吴青 傅秀芬.水平分布数据库的正负关联规则挖掘[J].计算机技术与发展,2010,(06):113.
　WU Qing,FU Xiu-fen.Positive and Negative Association Rules Mining on Horizontally Partitioned Database[J].,2010,(10):113.
[7]孙名松 邸明星 王湛昱.多决策树算法在P2P网络流量检测中的应用[J].计算机技术与发展,2010,(06):126.
　SUN Ming-song,DI Ming-xing,WANG Zhan-yu.Application of Decision Tree Algorithm in Traffic Detection of P2P Network[J].,2010,(10):126.
[8]孟魁杰 董莹 赵宗涛.一种基于数据挖掘的无人飞行器故障分析方法[J].计算机技术与发展,2010,(06):225.
　MENG Kui-jie,DONG Ying,ZHAO Zong-tao.A Fault Analysis Method Based on Data Mining for Unmanned Aerial Vehicle[J].,2010,(10):225.
[9]文拯 梁建武 陈英.关联规则算法的研究[J].计算机技术与发展,2009,(05):56.
　WEN Zheng,LIANG Jian-wu,CHEN Ying.Research of Association Rules Algorithm[J].,2009,(10):56.
[10]王晓宇 秦锋 程泽凯 邹洪侠.关联规则挖掘技术的研究与应用[J].计算机技术与发展,2009,(05):220.
　WANG Xiao-yu,QIN Feng,CHENG Ze-kai,et al.Investigation and Application of Association Rules Mining[J].,2009,(10):220.
[11]李雷 丁亚丽 罗红旗.基于规则约束制导的入侵检测研究[J].计算机技术与发展,2010,(03):143.
　LI Lei,DING Ya-li,LUO Hong-qi.Intrusion Detection Technology Research Based on Homing - Constraint Rule[J].,2010,(10):143.
[12]张笑达 徐立臻.一种改进的基于矩阵的频繁项集挖掘算法[J].计算机技术与发展,2010,(04):93.
　ZHANG Xiao-da,XU Li-zhen.An Advanced Frequent Itemsets Mining Algorithm Based on Matrix[J].,2010,(10):93.
[13]王爱平 王占凤 陶嗣干 燕飞飞.数据挖掘中常用关联规则挖掘算法[J].计算机技术与发展,2010,(04):105.
　WANG Ai-ping,WANG Zhan-feng,TAO Si-gan,et al.Common Algorithms of Association Rules Mining in Data Mining[J].,2010,(10):105.
[14]张广路 雷景生 吴兴惠.一种改进的Apriori关联规则挖掘算法（英文）[J].计算机技术与发展,2010,(06):84.
　ZHANG Guang-lu,LEI Jing-sheng,WU Xing-hui.An Improved Apriori Algorithm for Mining Association Rules[J].,2010,(10):84.
[15]王伟 高亮 吴涛.基于遗传算法的长频繁项集挖掘方法[J].计算机技术与发展,2008,(04):19.
　WANG Wei,GAO Liang,WU Tao.A Method of Mining Long Frequent Itemset Based on Genetic Algorithm[J].,2008,(10):19.
[16]吴春阳 何友全.数据挖掘技术及其在旅游线路规划系统的应用[J].计算机技术与发展,2008,(09):235.
　WU Chun-yang,HE You-quan.Application of Association Rule in Data Mining for Tour Planning[J].,2008,(10):235.
[17]荣秋生 颜君彪.网格下最大频繁项集挖掘算法的实现[J].计算机技术与发展,2007,(01):98.
　RONG Qiu-sheng,YAN Jun-biao.Implementation of Maximal Frequent Itemset Data Mining Based on Grid[J].,2007,(10):98.
[18]冯洁 陶宏才.典型关联规则挖掘算法的分析与比较[J].计算机技术与发展,2007,(03):121.
　FENG Jie,TAO Hong-cai.Analysis and Comparison of Representative Algorithms for Mining Association Rules[J].,2007,(10):121.
[19]胡吉明 鲜学丰.挖掘关联规则中Apriori算法的研究与改进[J].计算机技术与发展,2006,(04):99.
　HU Ji-ming,XIAN Xue-feng.Research and Improvement on Apriori＇s Algorithm in Mining with Association Rules[J].,2006,(10):99.
[20]陈玉婷 王斌 刘博 宋斌[] 李颉[].关联规则挖掘算法介绍[J].计算机技术与发展,2006,(05):21.
　CHEN Yu-ting,WANG Bin,LIU Bo,et al.Introduction of Mining Association Rules Algorithm[J].,2006,(10):21.

更新日期/Last Update: 2019-10-10