杨青侠 何明祥 邱冬冬 聂宝军

山东科技大学信息科学与工程学院，山东 青岛 266000

基于FP-Tree的挖掘最大频繁项目集的新算法

杨青侠 何明祥 邱冬冬 聂宝军

山东科技大学信息科学与工程学院，山东 青岛 266000

引言

关联规则是由Agrawal等人首先提出的一个重要的数据挖掘研究课题[1]。而挖掘频繁项目集是关联规则挖掘的关键技术。在此基础上Agrawal等人于1993年首次提出为布尔关联规则挖掘频繁项集的Apriori算法。虽然，Apriori算法是数据挖掘中最重要的算法之一。但是它也存在着不足。Apriori算法为了挖掘频繁项目集，必须产生所有的候选项目集，候选项目集的数量很庞大。并且为了得到候选项目集的支持度，算法必须重复的扫描数据库来确定候选项目集的支持度。计算候选项目集的支持度是最耗时的工作。所以减小成本的最好手段就是降低候选项目集的数目和减少数据库的扫描次数。FP-Tree[2]存储结构就是为了解决这两个问题而被提出的。FP-Tree的构造只扫描两次数据库。第一次数据库扫描和Apriori相同，它导出频繁项（1-项集）的集合和支持度计数（频率）。第二次数据库扫描用于构建FP-Tree和保存重要信息。

最大频繁项目集中包含了所有的频繁项目集信息。所以对频繁项目集的挖掘就转化为对最大频繁项目集挖掘的问题。目前挖掘最大频繁项目集的算法有Max-Miner[3]，Pincer-Search[4]，DMFI[5]及DMFIA[6]等算法。其中DMFIA基于FP-Tree存储结构，虽然克服了先前的挖掘算法的不足，但仍然生产了过多的候选项目集。本文在研究大量算法的基础上，提出了一种基于FP-Tree的新的挖掘算法FP-GDMA。……