基于矩阵的数据流滑动窗口频繁项集挖掘算法研究

摘要

近年来，出现了一种与传统静态数据库不同的新型数据模式——数据流，在电子商务网络交易、股市交易、通话日志分析、传感器网络及计算机网络安全监控等许多领域都存在着广泛的应用。由于数据流具有连续性、无限性、实时性等特点，因而传统的静态数据挖掘技术不能满足处理和分析数据流这种新型数据的要求，因此数据流挖掘技术已成为当前研究的一个热点问题。
　　数据流频繁项集挖掘是关联规则挖掘的基础与核心。首先介绍了课题的研究背景以及国内外的研究现状，阐述了数据流频繁项集挖掘目前存在的一些问题，然后介绍了数据流挖掘相关的基本概念与理论。
　　针对现有的宽度优先频繁项集挖掘算法存在的需要多次连接，产生大量冗余项集等问题，本文提出了一种基于矩阵的数据流滑动窗口频繁项集挖掘算法TMFI。该算法采用事务矩阵来存储数据流中的事务信息，此矩阵即为一个滑动窗口，对滑动窗口中的数据进行更新时，采用直接覆盖的方法，这样能够减少数据的存储和更新时间，并减少窗口滑动的时间。在挖掘频繁项集时，采用二项集矩阵存储二项集的信息，并且没有采用经典的Apriori性质，而是采用了一种利用频繁k-项集扩展(k+1)-项集的思想，这样能够有效的避免冗余项集的产生，提高挖掘的效率。实验结果表明了算法稳定行、快速性、准确性。
　　频繁项集挖掘算法需要用户预先设定阈值，而阈值的设定关系到挖掘结果的好坏，为了避免用户设置不恰当的阈值，本文又提出了基于滑动窗口的top-k频繁项集挖掘算法TKFM。top-k频繁项集的挖掘不需要用户事先定义最小支持度阈值，而是根据用户的需要挖掘最频繁的k个项集，只需要用户指定一个k值即可。TKFM算法用滑动窗口对数据流进行逐条采样，并用事务矩阵存储事务的相关信息，用二项集矩阵存储top-k二项集的信息。利用k-项集扩展为(k+1)-项集的思想及事务矩阵和二项集矩阵的相关信息，来挖掘当前滑动窗口中的频繁项集。之后，把得到的频繁项集存储到数据字典Dictionary中，并且按支持度计数降序排列。在挖掘出新的频繁项集时，加入到Dictionary中，同时更新border-sup的值。最后输出Dictionary中的频繁项集。实验结果表明，该算法在挖掘的过程中避免了冗余项集的产生，在保证正确率的前提下，具有较高的时间效率。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 数据流频繁项集挖掘目前存在的一些问题

1．4 本文解决的主要问题

1．5 本文研究的目的和主要内容

1．6 本文的组织结构

第二章 数据挖掘相关基本概念与理论

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 本章小结

第三章 基于矩阵的数据流滑动窗口频繁项集挖掘算法

3．1 问题的提出及相关研究

3．2 算法描述

3．2．1 数据结构

3．2．2 滑动窗口初始阶段

3．2．3 滑动窗口滑动阶段

3．2．4 频繁项集产生阶段

3．3 实验结果及分析

3．3．1 算法的性能分析

3．3．2 算法的性能比较

3．4 本章小结

第四章 基于矩阵的数据流top-k频繁项集挖掘算法

4．1 引言

4．2 算法描述

4．2．1 数据结构

4．2．2 top-k频繁项集挖掘

4．3 实验结果及分析

4．4 本章小结

第五章 总结与展望

5．1 研究工作总结

5．2 未来工作展望

参考文献

发表论文情况

致谢