基于单向频繁模式树的频繁项集挖掘算法

摘要

频繁项集挖掘是关联规则挖掘的关键步骤。FP-Growth算法是一种有效的频繁项集挖掘算法,它以自底向上的方式探索频繁模式树FP-tree,由FP-tree产生频繁项集。但是由于需要递归生成大量的条件FP-tree,其时间复杂度和空间复杂度都较高。针对这一问题,设计了一种基于单向频繁模式树的频繁项集挖掘算法UFIM。此算法首先构造一种单向频繁模式树UFP-tree结构,然后在UFP-tree上引入被约束子树,并对指向不同端点和指向相同端点的被约束子树分别采用递归和非递归的方法来挖掘频繁项集。非递归的方法判断端点的支持度计数是否小于最小支持度计数,若小于最小支持度计数则该棵被约束子树无频繁项集,否则其频繁项集是除根节点外的节点的排列组合。在mushroom数据集上的实验结果表明,UFIM算法的运行速度高于同类算法。