数据流中基于FP-Tree的频繁项集挖掘算法研究

摘要

对国内外数据流频繁项集挖掘研究情况分析可知，以往的挖掘算法还存在诸多问题。简单的频繁项集挖掘由于没有采用合理的约束思想，挖掘出的频繁项集相当庞大；增量挖掘方法大部分是处理数据流中新到数据的插入，很少涉及过期数据的删除；单纯的频繁项集挖掘忽略了挖掘结果的时间特性。本文针对这些问题，将研究重点放在基于 FP-Tree概要数据结构的数据流频繁项集挖掘算法的研究上，解决这些问题对研究电子商务、商业智能以及市场决策等领域具有重要的意义。
　　本文首先设计了一种数据流中当前频繁闭项集挖掘算法 HCFI，根据滑动窗口模型，有效的限制了过期数据对挖掘结果的影响。该算法采用闭项集增长策略，仅从当前滑动窗口的数据流中挖掘闭项集，增强了挖掘结果的实时性。该算法在处理时间和内存消耗上优于算法CFI-Stream。
　　其次，提出了数据流滑动窗口上的最大频繁项集挖掘方法 SW-MFI。该算法解决了在挖掘结果不要求项集支持度计数的条件下，获取精确频繁项集结果的问题。该算法较算法DSM-MFI具有较好的时间和空间效率。
　　最后，设计了一种数据流中基于约束的频繁项集挖掘算法ConFI-SW。该算法把滑动窗口中的挖掘过程分为两部分：窗口的维护和基于约束的频繁项集挖掘。算法的时间效率和空间效率较以往算法都有所提高。
　　本文使用C语言对上述算法进行实现，使用现实数据集BMS-WebView-1和BMS-WebView-2进行基于滑动窗口的数据流中频繁闭项集和最大频繁项集挖掘，通过对不同处理结果的对比分析，所提出的算法在解决各自的问题上是有效的。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 数据流挖掘技术

1.2 数据流中频繁项集挖掘技术

1.3 课题研究内容

1.4 本文的结构内容安排

第2章 数据流中基于滑动窗口的频繁闭项集挖掘

2.1 引言

2.2 滑动窗模式的产生过程

2.3 挖掘任务分离的思想

2.4 问题定义

2.5 频繁闭项集挖掘算法的设计

2.6 算法分析与实例

2.7 本章小结

第3章 数据流中基于PB-tree的当前最大频繁项集挖掘算法

3.1 引言

3.2 问题定义

3.3 FP-Tree的设计过程

3.4 SW-MFI算法设计

3.5 实例

3.6 算法分析

3.7 本章小结

第4章 数据流中基于约束的频繁项集挖掘

4.1 引言

4.2 问题定义与描述

4.3 基于约束的频繁项集挖掘算法ConFI-SW的设计

4.4 实例

4.5 算法分析

4.6 本章小结

第5章 算法实现及实验分析

5.1 数据集的来源

5.2 HCFI算法实验

5.3 SW-MFI算法的实验

5.4 ConFI-SW算法的测试

5.5 本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介