基于改进FP树的项项正相关关联规则挖掘  

Between-Items Positive Correlated Association Rules Mining Based on Node Linked List FP-Tree

作　　者：刘上力[1] 杨清[1] 

机构地区：[1]湖南科技大学网络信息中心,湖南湘潭411201

出　　处：《计算机工程与科学》2011年第7期183-187,共5页Computer Engineering & Science

基　　金：湖南省自然科学基金资助项目(06JJ5132);湖南省教育厅重点科学研究项目(10A028);湖南省科技计划项目(2009JT3031)

摘　　要：兴趣度量在关联规则挖掘中常用来发现那些潜在的令人感兴趣的模式,基于FP树结构的FP-growth算法是目前较高效的关联规则挖掘算法之一,如果挖掘潜在的有价值的低支持度模式,这种算法效率较低。为此,本文提出一种新的兴趣度量—项项正相关兴趣度量,该量度具有良好的反单调性,所得到的模式中任意一项在事务中的出现均可提升模式中其余项出现的可能性。同时,提出一种改进的FP挖掘算法,该算法采用一种压缩的FP树结构,并利用非递归调用方法来减少挖掘中建立额外条件模式树的开销。更为重要的是,在频繁项集挖掘中引入项项正相关兴趣度量剪枝策略,有效过滤掉非正相关长模式和无效项集,扩大了可挖掘支持度阈值范围。实验结果表明,该算法是有效和可行的。Interestingness measures are intended for selecting patterns according to their potential interest to the user in association rules.The FP-growth algorithm based on the FP-tree structure is an efficient algorithm for mining association rules.This algorithm is not quite effective in the process of mining potentially valuable low-support patterns.To solve this problem,a novel type of interestingness measure called between-items positive correlation interestingness measure is presented.This measure has a good auti-monotone,and the presence of an item in one transaction increases the presence of every other item in the same pattern.This paper also proposes an improved FP mining algorithm which creates a compact FP structure by the node linked list and uses a non-recursive function to decrease the overhead of creating an extra data structure at each mining step.More importantly,this algorithm exploits an efficient pruning strategy which uses the interestingness measure to filter the non-positive correlated long model and invalid itemsets.The range of the support threshold is expanded.The experimental results indicate the given algorithm is efficient and feasible.

关 键 词：关联规则 兴趣度 项项正相关 剪枝 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]