一种基于节点交换的FP-tree构造算法

基于FP树的FP-Growth关联规则挖掘算法,不需要产生候选项集,是当前频繁项集挖掘算法中应用最为广泛的算法之一.针对该算法在对大型的数据库挖掘的时候,存在运行速度慢,占用资源多的问题,文中发现算法中FP树和条件FP树的构建是最占资源的阶段.为此,提出了一种基于改进的FP树的构造算法.该算法一方面通过节点交换的方式压缩树的规模,提高挖掘的效率;另一方面,利用节点支持度计数的差值作为阈值以限定节点交换的条件,避免了由于交换过于频繁,造成不必要的系统开销,并把这种基于节点交换FP树构造算法称为TFP树算法.经过实验验证和性能分析,结果表明新算法有效,执行时间少,效率高.

An FP-tree construction algorithm based on exchanging nodes

FP-tree based FP-growth algorithm on association rule, which needs not to generate candidate itemset, is one of the data mining approaches widely applied in frequent item-set excavation. However, it still has disadvantages such as low running speed and more occupied resources when mining is performed in large datasets. To these problems it is found that the construction of FP-tree or condition FP-tree is performed in a stage occupying the most resources. To overcome these drawbacks, this paper proposes an improved FP-tree construction algorithm. On the one hand, it adopts node exchanging to reduce the scale of the tree and improve the mining efficiency. On the other hand, node exchanging condition is limited by threshold which is the difference of counters on node supporting degrees, which avoids unnecessary system spending due to excessive frequent exchanging. In this paper the FP-tree construction approach based on node exchanging is called TFP-tree algorithm. Experiment validation and performance analysis demonstrate that with a short running time and a great efficiency, the new approach is powerful.