基于位存储Tid的Eclat算法CPU并行化与分布式研究

摘要

在关联规则挖掘算法中频繁项目集挖掘(Frequent itemset mining，FIM)是十分重要的一步。典型的关联规则挖掘算法有Apriori算法、DHP算法、Toivoen算法、Eclat算法和FP-Growth算法等等。这些基于串型的传统关联规则算法在处理小数据和海量数据时在内存消耗和挖掘效率两方面均存在瓶颈，本文针对当前的应用场景及需求，从CPU并行化及分布式化两个方面对Eclat算法进行研究及改进。
　　Eclat是基于垂直Tid（事务标识）列表的关联规则挖掘算法。本文分析了Eclat算法和相关改进算法的频繁项目集生成原理，在其基础上提出了一种基于位存储结构的CPU并行化Eclat算法（Bit Parallel Eclat，简称BPEclat），BPEclat算法中各个项目的事务Tid使用二进制位进行存储，同时采用并行化的挖掘模式，将挖掘任务分配到各个线程，最大限度发挥CPU的运算性能，实验证明BPEclat算法在提高了频繁项目集挖掘效率的同时也极大降低内存的消耗。
　　为使算法适用于海量数据环境下的关联规则挖掘，将BPEclat算法与Spark框架进行深度融合，进一步提出了一种基于Spark大数据处理平台的BPEelat算法（Bit Parallel Eclat based on Spark，简称SBPEclat）。SBPEclat算法充分利用了Spark框架在迭代计算和处理大数据方面的优势，同时为平衡算法挖掘过程中计算节点间的负载，算法中使用了负载均衡策略对等价类分组进行了优化，对SBPEclat算法进行的多组实验表明，基于Spark平台的BPEclat算法-SBPEclat算法对海量数据进行频繁项目集挖掘时性能表现优异。

目录

声明

摘要

第一章 绪论

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．3 本文主要研究内容

1．4 本文结构安排

1．5 本章小结

第二章 相关理论与平台

2．1 关联规则概述

2．1．1 关联规则基本概念

2．1．2 关联规则定理

2．1．3 关联规则挖掘过程

2．1．4 关联规则分类

2．2 关联规则相关算法简介

2．2．1 基于水平数据格式的Apriori系列算法

2．2．2 基于垂直数据格式的Eclat系列算法

2．2．3 基于树形数据格式的FP-Growth系列算法

2．3 Eclat算法详解

2．3．1 Eclat算法介绍

2．3．2 Eclat算法实例描述

2．4 分布式平台简介

2．4．1 Hadoop平台简介

2．4．2 Spark平台简介

2．5 本章小结

第三章 基于位存储Tid的CPU并行化Eclat算法-BPEclat算法

3．1．1 内存消耗问题

3．1．2 挖掘效率问题

3．2．1 BPEclat算法改进策略

3．3 BPEclat算法实现策略

3．3．1 位垂直Tid列表的数据结构

3．3．2 位垂直Tid列表的生成

3．3．3 候选项目的支持度计数

3．3．4 多线程挖掘任务分配

3．4 算法整体流程图

3．5 本章小结

第四章 基于Spark平台的BPEcalt算法-SBPEcalt算法

4．1 基于Spark框架的分布式化与原理

4．1．1 并行思想概述

4．1．2 数据分区策略

4．2 SBPEclat算法实现策略

4．3 算法整体流程图

4．3 本章小结

第五章 算法实现与实验结果分析

5．1．2 实验结果对比与分析

5．2 SBPEclat算法实现与实验结果分析

5．2．1 实验环境与实验数据

5．2．2 实验结果对比与分析

5．3 本章小结

总结与展望

参考文献

致谢