基于倾斜时间窗口的频繁项集挖掘算法研究

当今的信息社会的中,人们每天都要处理各种各样的信息和数据。随着信息的爆炸式增长,许多应用中需要处理的数据规模也越来越大,这些数据以快速的、大量的、按时间顺序连续到达,这种数据模式就是数据流。由于数据流的流动性和无限性的特点,原有频繁项集挖掘算法已很难完成基于数据流上的挖掘任务。这些挑战吸引了许多人对数据流中频繁项集挖掘进行了大量研究。现在,数据流中频繁项集挖掘已成为数据挖掘中的热点之一。 FP-stream算法可以实现在线挖掘多时间粒度的频繁项集。作为一个经典的挖掘算法,FP-stream算法具有较好的时间效率。但它的不足之处在于:算法使用FP-growth算法来生成频繁项集和计算支持数,需要很大的内存开销和时间开销;整个挖掘过程中,所有的历史信息数据都存于内存中,随着时间的推移内存空间将急剧的膨胀。所以,内存开销巨大是FP-stream算法最大的缺点。 针对上述问题,本文将在原算法的基础之上,采用一种新的数据结构(LR-Trie树及树结点)来存储频繁项集及其对应的倾斜时间窗口。同时引入了垂直的二进制向量表示法存储事务数据以提高时空效率。由于构造了新的树结点结构,可以方便地完成LR-Trie树的线性存储和结点查询。另外将LR-Trie树分割为若干子树并以文件的形式存储,在内存中建立项和文件的索引表,按需调入文件,极大地减少了内存消耗。实验表明,改进后的算法在不明显降低原算法时间效率的前提下,提高了内存空间利用率。该算法适用于对时间要求不高,但对内存空间要求较高的应用。