在线挖掘数据流闭合频繁项集算法的研究

论文摘要

近年来，随着计算机存储和网络通信技术的快速发展，数据流逐渐出现在日常生活中的各个领域，比如大型商场的售货记录，环境温度的检测数据，交易所的股票价格信息等。人们需要对海量的动态数据进行实时连续的收集与分析，进而挖掘数据流上的频繁模式得到越来越多的关注。与传统静态数据库相比，数据流具有持续不断、高速运行、无限到达的特点。数据流中的数据随时间的推移不断更新，而用户通常只关注近期有价值的模式。本文研究的是数据流频繁项集挖掘的一个主要方面：数据流闭合频繁项集挖掘。它是针对数据流频繁项集挖掘中得到大量冗余的频繁项集，造成内存过多的消耗和挖掘速度的极大下降而提出的。闭合频繁项集包括了挖掘出的所有频繁项集的完全集，从而避免了冗余频繁项集的产生，可以大大节省存储空间，提高挖掘效率，但是又不会丢失任何有用信息。数据流快速无限的特点及其应用领域的不断扩增，使数据流的在线挖掘技术越来越具有挑战性。提出了一种新的CMNL-SW挖掘算法（Closed Map and Num List-SlidingWindow），它沿用Moment算法的滑动窗口技术和CFI-Stream算法只维持闭合项集信息的方法，但与之不同的是，CMNL-SW算法不需产生事务的子集，也不需搜索每个子集的超集。算法使用数据结构Closed Map存储挖掘到的闭合项集和Num List存储所有不同项的序号，通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口，使之能够根据用户任意指定的支持度阈值实时输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集Mushroom、Retail-chain以及人工合成数据集T40I10D100K的挖掘结果表明，提出的算法在时空效率上明显优于同类经典算法Moment和CFI-Stream，并且随着数据流上处理事务数的递增和快速改变有很好的稳定性。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题研究的背景
• 1.1.1 在线数据流挖掘技术的由来
• 1.1.2 挖掘闭合频繁项集的意义
• 1.2 课题国内外研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 论文的研究内容和组织结构
• 第2章 数据流模型及相关数据流挖掘技术
• 2.1 数据挖掘
• 2.1.1 数据挖掘的基本功能
• 2.1.2 数据挖掘的过程
• 2.2 数据流及数据流挖掘模型
• 2.2.1 数据流的特点
• 2.2.2 数据流挖掘模型
• 2.3 数据流挖掘相关技术和应用
• 2.3.1 滑动窗口技术
• 2.3.2 数据流挖掘的应用
• 2.4 数据挖掘中的频繁项集算法概述
• 2.4.1 频繁项集相关定义
• 2.4.2 挖掘静态数据库中频繁项集的算法及评析
• 2.5 数据流挖掘频繁项集算法概述
• 2.5.1 概要数据结构估测算法
• 2.5.2 使用滑动窗口技术的算法
• 2.5.3 采用衰落因子的算法
• 2.5.4 采用倾斜时间窗口策略的算法
• 2.6 本章小结
• 第3章 闭合频繁项集挖掘算法的研究
• 3.1 相关概念及定义
• 3.2 挖掘静态数据库中闭合频繁项集的算法演变
• 3.2.1 最早提出闭合项集思想的 Close 和 A-Close 算法
• 3.2.2 CHARM 算法
• 3.2.3 CLOSET 和 CLOSET+算法
• 3.3 基于滑动窗口挖掘数据流闭合频繁项集算法阐述
• 3.3.1 Moment 算法
• 3.3.2 CFI-Stream 算法
• 3.3.3 以往算法存在的问题
• 3.4 本章小结
• 第4章 一种新的在线挖掘算法 CMNL-SW
• 4.1 闭合项集的定义和性质
• 4.2 算法相关数据结构
• 4.3 维持算法的规则
• 4.4 添加新事务到滑动窗口
• 4.5 从滑动窗口删除旧事务
• 4.6 本章小结
• 第5章 实验结果及性能评估
• 5.1 实验环境和数据集
• 5.1.1 实验环境介绍
• 5.1.2 真实和模拟数据集
• 5.2 挖掘结果及分析
• 5.3 性能指标比较
• 5.3.1 性能指标
• 5.3.2 性能评估
• 5.4 算法的稳定性和扩展性
• 5.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢