关联规则并行采掘算法的研究

摘要

目前传统的关联规则采掘技术大多采用串行算法,例如Level-wise算法、non-level-wise算法以及不产生候选项目集的算法,其中R.Agrawal等人提出的Apriori算法是处理事务数据库中大项目集较为有效的算法.随着分布式数据库的发展,提出了采掘关联规则更有效的并行算法,如Level-wise并行模式,DMA并行模式等,明显地提高了采掘效率.其中pSPADE算法是一种广泛应用于大型数据库上快速采掘频繁序列的有效并行算法,它将搜索空间分成了更小的基于后缀的类,可在每个处理器上独立地处理,实现了数据的本地性最大化和同步的最小化.该文通过对pSPADE算法的研究,发现算法执行中,处理器将所有的类和它的中间id列表存于主存,导致了大量的内存开销.当处理更大的数据集时,容易产生内存不足而溢出.该文根据搜索算法内存管理的思想,提出了一种内存扩展方案来解决这一问题.在内存不足和获得足够内存两种情况下,把部分类写入磁盘,释放了内存空间,缓解了内存的压力.在程序需要时,再将写入磁盘的类加入共享队列作为多余的类处理.该文通过对这种方案的分析,指出了它的优缺点和适用范围.

目录

文摘

英文文摘

第一章引言

1.1数据采掘的产生

1.2数据采掘的定义

1.3数据采掘技术

1.3.1数据采掘技术分类

1.3.2数据采掘技术应用

1.4关联规则采掘技术

1.4.1关联规则的串行采掘技术

1.4.2关联规则的并行采掘技术

1.5 pSPADE并行采掘算法

1.6本文的主要工作

1.7论文的组织

第二章关联规则采掘问题

2.1问题的产生

2.2问题的定义

2.3关联规则采掘问题的分解

2.3.1根据频繁项目集产生强规则

2.3.2关联规则采掘的基本模型

2.4关联规则采掘算法

2.4.1 level-wise算法

2.4.2 Non-level-wise算法

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

2.5关联规则采掘技术的研究方向

2.5.1关联规则的兴趣度

2.5.2关联规则采掘算法的交互性

2.5.3关联规则并行采掘算法

2.6小结

第三章关联规则的并行采掘算法

3.1问题的提出

3.2关联规则并行采掘的基本概念

3.3并行采掘算法的基本内容

3.3.1 Level-Wise算法的并行模式

3.3.2其它并行模式

3.4并行算法总结

3.5小结

第四章pSPADE并行采掘算法

4.1序列模式采掘的概念

4.2序列模式采掘技术

4.2.1串行采掘算法

4.2.2并行采掘算法

4.3 pSPADE并行算法

4.3.1 SGI Origin 2000

4.3.2 pSPADE算法的设计和实现

4.4实验结论

4.4.1并行性能

4.4.2可扩展性

4.5小结

第五章改进的pSPADE方案

5.1问题的产生

5.2内存扩展方案

5.2.1搜索算法内存管理

5.2.2 pSPADE内存扩展方案

5.3方案分析

5.4小结

第六章总结和展望

研究生期间发表论文

参考文献

致谢