基于FP-tree的快速构建算法

计算机应用 ›› 2011, Vol. 31 ›› Issue (02): 438-440.

基于FP-tree的快速构建算法

陈治平¹,谭义红²,李学勇³,栾悉道³

1. 长沙学院
2. 湖南长沙学院信息与计算科学系
3. 长沙学院信息与计算科学系

收稿日期:2010-07-20 修回日期:2010-09-19 发布日期:2011-02-01 出版日期:2011-02-01
通讯作者: 陈治平

Fast construction algorithm based on FP-tree

Received:2010-07-20 Revised:2010-09-19 Online:2011-02-01 Published:2011-02-01
Contact: CHEN Zhi-Ping

摘要/Abstract

摘要： 数据库的访问频度是影响关联规则挖掘性能的关键因素之一。通过研究FP-tree算法，提出了一种基于FP-tree的快速构建算法，使FP-tree的构建过程仅需一次数据库扫描。该算法通过动态调整项头表中各项的顺序，同时动态修正FP-tree中项的出现顺序与项头表中各项出现顺序不一致的节点。最后，通过对项头表中非频繁项的剔除与FP-tree中对应项节点的清理，完成FP-tree的构建过程。实验结果证明了该算法的有效性。

关键词: 关联规则, 项头表, 频繁项

Abstract: Access frequency of database is one of the key factors to affect association rule mining performance. With the analysis of FP-tree, a fast construction algorithm based on FP-tree was proposed in this paper to scan database only one time. It dynamically adjusted not only the order of items in Item Entry Table (IET), but also the order of nodes in FP-tree whose order was not consistent with the order of nodes in IET. Finally, it removed the un-frequent items in the IET with related nodes in FP-tree, and completed the construction of FP-tree. The experimental results validate the efficiency of the new algorithm.

Key words: association rule, Item Entry Table (IET), frequent item

陈治平谭义红李学勇栾悉道. 基于FP-tree的快速构建算法[J]. 计算机应用, 2011, 31(02): 438-440.

[1]	王淳颖, 张驯, 赵金雄, 袁晖, 李方军, 赵博, 朱小琴, 杨凡, 吕世超. 基于多源告警的攻击事件分析[J]. 计算机应用, 2020, 40(1): 123-128.
[2]	于永斌, 戚敏惠, 尼玛扎西, 王琳. 基于阈值自适应忆阻器Hopfield神经网络的关联规则挖掘算法[J]. 计算机应用, 2019, 39(3): 728-733.
[3]	杜媛, 张世伟. 基于重构的改进自然排序树算法[J]. 计算机应用, 2019, 39(2): 441-445.
[4]	陈柳, 冯山. 正负关联规则两级置信度阈值设置方法[J]. 计算机应用, 2018, 38(5): 1315-1319.
[5]	肖文, 胡娟. 基于数据集稀疏度的频繁项集挖掘算法性能分析[J]. 计算机应用, 2018, 38(4): 995-1000.
[6]	尹远, 张昌, 文凯, 郑云俊. 基于DiffNodeset结构的最大频繁项集挖掘算法[J]. 计算机应用, 2018, 38(12): 3438-3443.
[7]	顾军华, 武君艳, 许馨匀, 谢志坚, 张素琪. 基于Spark的并行FP-Growth算法优化及实现[J]. 计算机应用, 2018, 38(11): 3069-3074.
[8]	王帅, 杨秋辉, 曾嘉彦, 万莹, 樊哲宁, 张光兰. 加权增量关联规则挖掘在通信告警预测中的应用[J]. 计算机应用, 2018, 38(10): 2875-2880.
[9]	李校林, 杜托, 刘彪. 基于B-list的快速频繁模式挖掘算法[J]. 计算机应用, 2017, 37(8): 2357-2361.
[10]	谭征, 刘惊雷, 余航. 基于最大团的条件偏好挖掘[J]. 计算机应用, 2017, 37(11): 3107-3114.
[11]	王涛, 覃锡忠, 贾振红, 牛红梅, 曹传玲. 基于相似度和信任度的关联规则微博好友推荐[J]. 计算机应用, 2016, 36(8): 2262-2267.
[12]	徐开勇, 龚雪容, 成茂才. 基于改进Apriori算法的审计日志关联规则挖掘[J]. 计算机应用, 2016, 36(7): 1847-1851.
[13]	王鑫, 刘方爱. 改进的多数据流协同频繁项集挖掘算法[J]. 计算机应用, 2016, 36(7): 1988-1992.
[14]	徐永秀, 刘旭敏, 徐维祥. 基于间隔链表改进的频繁项集挖掘算法[J]. 计算机应用, 2016, 36(4): 997-1001.
[15]	王乐, 常艳芬, 王水. 基于模式增长的不确定数据的频繁模式挖掘算法[J]. 计算机应用, 2015, 35(7): 1921-1926.