论文部分内容阅读
经过近十几年的研究,数据挖掘技术已经相当成熟。作为数据挖掘研究中的基础任务,频繁模式挖掘一直是一个热点问题,得到了广泛而深入的研究。然而,随着网络、电信和传感器技术的发展,出现了一种新的流数据模型。数据流是大量的、连续的、无限的、快速变化的数据元素的序列。一般无法将数据流中的数据全部保存起来,对数据流中的数据一经处理除非刻意保存,否则就无法再次访问或再次访问的代价很大。为了从数据流中发现知识和模式,必须开发单遍扫描的、联机的、多层的和多维的流处理和分析方法。数据流挖掘是近年来数据挖掘领域的一个热点,大量数据流应用的产生促使数据流挖掘算法相继被提出。频繁模式挖掘是数据流挖掘中的重要研究内容,被广泛应用于关联规则发现、冰山查询、分类和聚类等问题。由于数据流本身的特点,数据流上的频繁模式挖掘只能对数据扫描一次,因此对频繁模式挖掘算法在时间和空间上都提出了更高的要求。许多现有的算法需要多次扫描整个数据集,因此在数据流频繁模式挖掘中的应用受到限制。与传统的频繁模式挖掘不同,为了挖掘数据流中的频繁模式,一般允许结果存在一个足够小的误差,以适应数据流的无限性并提高挖掘的效率。本文综述了数据流频繁模式挖掘研究的现状,分析了两个经典的算法Lossy Counting和FP-stream,两者都能够挖掘数据流中的频繁模式的完全集,但又具有各自的特点。Lossy Counting算法可以将候选项集存储在外存,使算法具有较好的空间效率,但算法只能给出整个流上的频繁模式,不能区分历史数据的不同影响。而FP-stream算法利用倾斜时间窗框架存储每个模式在多个时间粒度下的频数,因而具有较好的动态性,但算法在支持度较低时占用大量内存。本文在分析已有算法的基础上,提出了结合倾斜时间窗的TWCT树结构,可以保存不同时间粒度下的频繁模式的完全集,并设计了其顺序更新和删除算法,使其能够存储在外存,从而有效地降低算法的内存空间需求。结合TWCT树结构特点,提出了数据流上的频繁模式挖掘算法TWCT-Stream,其模式生长的TWCT-Growth算法按字典顺序生成频繁模式,以配合TWCT结构的顺序更新。实验证实算法的内存需求低于FP-stream等同类算法。本文结合滑动窗口模型提出了兼有水平数据格式和垂直数据格式两者特点的VDT-SW结构,该结构便于处理滑动窗口的数据更新,可以结合使用多种频繁模式挖掘算法。利用该结构特点,针对即时查询问题,提出了一个时间复杂度低的快速项集计数查询算法VDT-SW-Query。将基于VDT-SW结构的数据流频繁模式挖掘应用于电信数据分析领域,设计了一个数据流处理系统模型,通过对投诉记录的挖掘,为电信网络运行与维护工作提供有价值的信息。数据流的频繁模式挖掘已经成为当前数据挖掘领域中的一个研究热点。本文最后结合所做工作对进一步的研究进行了展望。