基于数据流的关联规则算法研究与实现

摘要

随着网络的迅速发展和普及，分布式计算的研究在90年代后达到了高潮，目前，在Internet网上分布式计算已非常流行。分布式计算研究主要集中在分布式操作系统研究和分布式计算环境研究两个方面。在过去的20多年间出现了大量的分布式计算技术，如中间件技术、网格技术、移动Agent技术、P2P技术以及最近推出的WebService技术等。每一种技术都在特定的范围内得到了广泛的应用。但是，随着无线网络容量、带宽的增大，移动设备的快速发展和应用，开始提出了移动分布式的计算环境。移动挖掘正是在此基础上提出的。　　移动挖掘的最大特点是面向数据流。移动设备资源有限以及数据流的高速、无限、随时间变化的特性给移动挖掘带来了挑战。因而，本文作如下研究，以解决在移动平台上的关联规则挖掘的问题。　　1.充分利用FP-树的紧密性，在此基础上利用滑动窗口的近似策略，解决数据流高速性，无限性等特点，提出一个基于整个数据流历史频繁计数的数据流频繁模式算法DSM-FP1。　　2.研究FP-Growth频繁模式生成过程，发掘内在并行性，提出一　　个适合在移动分布式平台应用的数据流频繁模式挖掘算法DSM-FP2，充分利用移动计算平台上分散的计算能力；　　3.在理论分析和实例分析的基础上，设计实现算法，再次通过实验验证所提出的两个算法的正确性和扩展性。与传统的关联规则算法相比较，在保持正确性的基础上，提高性能，稳定性和扩展性。　　本文的研究意义在于通过对传统算法的改进，设计出适合移动环境的算法，对数据流挖掘进行有益的探索。

目录

文摘

英文文摘

华南理工大学学位论文原创性声明及学位论文版权使用授权书

第一章绪论

1.1课题背景

1.2当前研究状况

1.2.1适应输入数据率

1.2.2数据抽象方法

1.2.3近似算法

1.2.4 AOG算法(Algorithm Output Granularity)

1.3频繁模式算法

1.4研究内容与本文结构

1.5小结

第二章数据流与数据流管理系统

2.1数据流的特点

2.2数据流管理系统抽象参考模型

2.3 DSMS与DBMS的区别

2.4数据流查询

2.4.1数据模型

2.4.2连续查询的语义

2.5小结

第三章关联规则算法

3.1关联规则的概念

3.1.1基本概念及问题描述

3.1.2关联规则的分类

3.2层次迭代算法

3.3不产生候选项目集的算法

3.3.1FP树简介

3.3.2FP树的构造

3.3.3用FP-tree来挖掘频繁模式

3.3.4FP-树的完整性和紧密性

3.4小结

第四章基于数据流的数据挖掘算法

4.1数据流模型

4.2基于滑动窗口近似挖掘算法DSM-FP1

4.2.1定义

4.2.2 DSM-FP1算法流程

4.2.3 DSM-FP1中挖掘频繁项集举例

4.3分布式频繁项集挖掘算法DSM-FP2

4.3.1算法概述

4.3.2 DSM-FP2的算法流程

4.3.3局部FP-tree生成子过程

4.3.4 FP-tree合并子过程

4.3.5分布式挖掘子过程

4.4小结

第五章算法实验

5.1实验数据的生成方法

5.2实验环境

5.3算法DSM-FP1的实验

5.3.1算法DSM-FP1的稳定性评测

5.3.2算法DSM-FP1的正确性评测

5.4算法DSM-FP2的实验

5.4.1算法的扩展性的评测

5.4.2算法DSM-FP2与传统FP-tree算法的比较

5.5小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢