翟 悦 王 璨 孙建言

(大连科技学院信息科学系 辽宁 大连 116052)

0 引 言

频繁项集挖掘是数据挖掘研究中最为突出的任务之一，也是数据挖掘中最为耗时的部分，一旦挖掘出所有的频繁项集，关联规则即可通过简单的数学计算得到，可以说频繁项集挖掘算法的效率直接影响着整个数据挖掘的效率，因此十分有必要深入研究频繁项集挖掘算法。传统数据频繁项集挖掘算法主要分为两类: 一类是以Apriori算法为代表的产生候选频繁项集的挖掘算法，Apriori类算法具有需要重复扫描数据库及产生大量候选项集等缺陷；另一类是FP-growth为代表的采用分而治之策略挖掘频繁项集算法，该种采用频繁模式增长类的算法将数据压缩到FP-tree，需要递归构建条件FP-tree，时间性能无法保证。

尽管近年来研究者提出诸多改进的频繁项集挖掘算法，但当事务数据库非常稠密,并且最小支持度设定非常低时, 频繁项集数量会随着其长度呈指数型增长，频繁项集挖掘时间复杂度仍然存在下降空间。因此，Deng等[3-4]提出了基于PPC-tree结构的挖掘算法PrePost，利用一种新的数据结构N-List，通过N-List的交集运算求得项集支持度，它在频繁项集挖掘中有很高的效率。Song等[2]提出的包含因子概念提高了频繁项集的挖掘速度。

本文提出一种借鉴包含因子概念融入PrePost算法，结合两种策略的优势，给出HNSFI算法。该算法利用哈希表存储N-List数据结构所表示的项集，N-List表示的项集与FP-tree相比拥有较高的压缩率，哈希表存储利用空间换时间的方法进一步降低N-List相交运算的时间复杂度，并可根据性质快速计算项集的支持度，同时结合项集的包含因子概念省略某些情况下N-List相交运算过程。……