在流滑动窗体上挖掘Top-K高效用项集的有效算法

摘要

数据流上的频繁项集挖掘是数据挖掘的一个重要话题,并在现实生活中应用广泛。可是这个问题存在两个限制：（1）项在数据流中的权重没有被考虑;（2）项在每条事务中的数量没有被考虑。因此,研究人员提出了＂数据流上的高效用项集挖掘＂的研究问题。在这一问题中,项的权重及项在事务中的数量被考虑,数据流上的高效用项集挖掘是指在数据流中挖掘所有效用值不小于用户指定最小效用阈值的项集。对用户而言,由于不了解数据流中数据的统计特性,很难设置一个合适的最小效用阈值,如果最小效用阈值设置过高,则挖掘算法返回高效用项集的数量过少,使得用户无法准确分析;如果最小效用阈值设置过低,则挖掘算法返回太多的高效用项集,使得用户需要对结果集二次分析,为此研究人员提出了＂数据流上的Top-K高效用项集挖掘＂的研究问题。数据流上的Top-K高效用项集挖掘是指在数据流中寻找前k个具有最高效用值的项集,通过设置k值取代最小效用阈值,可有效地控制算法的输出规模,对用户而言更直观。与静态数据相比,数据流具有如下特点：快速的数据到达速率、数据流的尺寸未知和不能访问以前到达数据的特点,因此很难将整个数据流放入内存中处理,通常研究人员采用流滑动窗体模型。流滑动窗体是由固定数量的、最近到达的批数据组成,每个批数据包含一组事务集。现有的挖掘流滑动窗体上Top-K高效用项集的研究方法通常包含两个阶段：（1）采用高估技术高估项集在流滑动窗体中的效用,将高估效用不小于由阈值提升技术获得的最小效用阈值的项集选定为Top-K高效用项集候选项集;（2）通过扫描流滑动窗体内的批数据,计算第一阶段生成的候选项集的真实效用。可是,这个方法存在两个问题：（1）第一阶段生成的候选项集通常数量巨大,需要大量的存储空间;（2）计算第一阶段生成的候选项集的真实效用是非常耗时的。因此,本文提出一个在挖掘过程中不生成候选项集的流滑动窗体上Top-K高效用项集挖掘算法TK-HIS,TK-HIS采用提出的HUILTree和效用数据库存储流滑动窗体中的项集及其在窗体事务中的效用,在HUIL-Tree和效用数据库的构建过程中提出两个阈值提升策略提升初始值为0的最小效用阈值,在挖掘过程中TK-HIS维护前k个具有最高效用值的项集,使用模式增长的方法生成搜索空间中的项集,对每一个项集通过效用数据库直接计算其在流滑动窗体中的效用。研究在稀疏数据流上进行了大量的实验评估TK-HIS的性能,并与当前最好的流滑动窗体Top-K高效用项集挖掘算法T-HUDS进行比较,实验结果表明在稀疏数据流上TK-HIS显著优于T-HUDS：运行时间最快可提升一个数量级。