论文部分内容阅读
数据流是近年出现的一个新的应用类型,具有连续、无限、高速等特点。典型的数据流包括:无线传感器网络应用环境中由传感器传回的各种监测数据、股票交易所的股票价格信息、网络监测系统与道路交通监测系统的监测数据、电信部门的通话记录数据,以及网站的日志信息等。数据流的出现对传统的数据管理和挖掘技术提出了巨大的挑战。传统的数据挖掘技术往往对静态数据集合做多遍扫描,其时间和空间复杂度均较高,难以直接应用到数据流环境中。本文对数据流上的频繁项集挖掘问题做了深入研究,主要研究内容和创新性成果概述如下:
本文首先对频繁项集挖掘问题做了一个全面的综述。综述部分先对静态数据集上的频繁项集挖掘的概念、分类、经典算法等相关研究做全面的介绍,然后分析了在数据流上进行频繁项集挖掘面临的问题和挑战、以及研究现状。
频繁元素可以看作仅有一个元素的频繁项集,是某些频繁项集挖掘算法的基础组成部分,在实际生活中也有很多应用。针对数据流上的频繁元素挖掘问题,本文提出了一个简单而高效的算法,挖掘数据流滑动窗口上的频繁元素;算法既可以定期返回满足∈-近似要求的频繁元素,也可以响应用户在任意时间提交的请求,返回满足误差要求的结果。
针对数据流上的频繁项集挖掘问题,本文提出了BFI-Stream算法,挖掘数据流滑动窗口上的所有频繁项集,返回精确结果。该算法使用前缀树数据结构,并且在创建和更新过程中裁剪了一部分非频繁节点,因此算法的空间和时间复杂度都较低。BFI-Stream算法可以在任意时刻处理用户的请求,并且挖掘过程无须额外计算,只须对树进行遍历即可,因此能实时返回频繁项集结果集。
接着,本文针对现有的在数据流上挖掘频繁项集的算法存在维护过多非频繁项集而导致使用空间过大的问题,提出了一种乐观裁剪方法,大大降低了算法的空间复杂度。文中先对实际数据集分析了项集的频率分布情况,提出了乐观裁剪方法,裁剪大部分非频繁项集;然后分别对BFI-Stream和Moment算法应用乐观裁剪方法,提出了新的OPFI-Stream和OP-Moment算法,实验结果表明乐观裁剪方法不仅大大降低了内存使用量,还提高了算法的更新效率。
再次,本文针对用户指定最小支持度和允许误差的近似查询,提出了在数据流滑动窗口上挖掘频繁项集的近似算法AFI-Stream,返回满足误差要求的结果。AFI-Stream仅仅维护频繁项集,不维护非频繁项集,因此能大大减少算法使用的内存;算法同时也能监测到一部分非频繁项集变为频繁项集的情况,从而将其添加到树中。
为了满足在数据流上挖掘频繁项集研究的需要,本文设计并开发了一个数据流频繁项集挖掘原型系统STREAMMINER,进行相关算法的评测和研究。STREAMMINER提供了良好的可扩展性与可配置性,支持对新增数据流模拟器和频繁项集挖掘算法等的测试与分析。
本文提出了几个在数据流上挖掘频繁项集的算法,能很好的适应数据流动态环境的需求,具有较高的理论价值和良好的应用前景;数据流挖掘原型系统可以作为在数据流上进行挖掘和监控的测试平台,为进一步对数据流挖掘进行研究提供了较好的基础平台。