频繁模式发现并行算法的应用研究开题报告

一、研究的基本内容

1. 学习并掌握频繁模式发现算法。

2. 充分了解并掌握Hadoop分布式并行计算框架。

3. 结合MapReduce分布式编程模型设计实现频繁模式发现并行算法。

4. 根据手工设计的数据集验证并行算法的正确性，以及sogou实验室提供的大数据集验证算法的效率。

二、 研究的目标

通过改进Aproiri算法，较少键/值对的产生，提高算法挖掘频繁项集的加速比，从而提高Aproiri算法的执行效率。

三、拟采用的技术方案以及措施

1) 进行技术调研以及搜集相关资料，细化研究内容，深入进行可行性分析。

2) 掌握相关基本理论、算法，熟悉相应的工具、平台的使用。包括Linux操作系统Ubuntu，MapReduce原理和运行机制以及Hadoop云计算平台的搭建；算法频繁模式发现算法，多阶段算法；掌握涉及的工具包括Java开发语言和Eclipse开发平台。

3) 针对研究内容，从以下几个方面开展工作：

1. 搭建基于Hadoop的完全分布式平台

① 配置2台机器，Master和Slave，修改各个机器的hosts和hostname。

② 安装并配置SSH服务器，实现各个机器上执行指令的无密码登录。

③ 对Hadoop进行配置。

④ 启动Hadoop并运行Hadoop实例，并运行实例，测试平台可用性。

2. 基于Hadoop的MapReduce任务设计

在结构化程序设计中，循环由2个部分组成，循环条件和循环体，循环条件用来控制循环次数，循环体负责迭代执行。这里沿用这种思路，将需要迭代执行的MapReduce任务设计成循环体，另外再设计一个外部“驱动”程序，配置循环条件，循环调用MapReduce任务，实现MapReduce任务的迭代调用。

3. 基于MapReduce的并行Aproiri算法实现

Apriori算法的并行改进:

① 把数据库分成规模相当的M个数据子集，把数据子集发送到M个站点。

② 每个站点扫描它的数据子集，产生一个局部候选K项集，每个候选项集的支持度计数为1。

③ 利用hash函数把M个站点的候选k项集总相同的项集和它的支持度计数发送到R个站点。

④ 站点把相同项集的计数累加起来，产生最后的实际支持度，与最小支持度计数比较，确定局部频繁k项集的集合。

⑤ 把R个站点的输出合并即产生全局频繁k项集的集合。改进的Apriori算法的优势是查找k频繁项集和k 1频繁项集的过程是完全独立的。他们之间没有联系，这是一个循环的过程。k值从1开始递增，知道找出所有的频繁项集。也可以设定k的值，知识查找k频繁项集，或者从1频繁项集到k频繁项集之间的所有频繁项集。

改进的Apriori算法的MapReduce实现：

① MapReduce库将事物数据库进行水平划分，分成M个规模相当的数据子集。

② 对M歌数据子集进行格式化，产生key,value对，具体格式化为Tid,list，Tid表示事物数据库中的事物标识符，list为事物数据库中的事物对应的列表值。

③ Map函数的任务是对输入的数据子集的每个记录Tid,list进行扫描，产生一个局部候选k项集的集合，每个候选k项集的支持度计数为1。Map函数生成并输出中间key,value对，这里定义为itemsets,1对，itemsets表示候选k项集。

④ 当事物数据库很大，划分后的每个数据子集中事物对应的列表很相近时，Map函数产生的中间key值得重复数据会占很大的比重。例如每个Map函数产生成千上万个这样的记录I,1。所有这些记录将通过网络被发送到指定的Reduce函数。这无疑耗费了宝贵的网络资源，增加了延迟，降低了I/O性能。所以在每台执行map任务的机器上增加一个可选的Combiner函数，Combiner函数首先在本地将Map函数输出进行一次合并输出itemsets,supsup表示itemsets在数据子集中的支持度计数，然后利用分区函数hash（key）mod R将Combiner函数产生的中间键值对分成R个不同的分区，将每个分区分配到指定的Reduce函数。

⑤ 被分配了Reduce任务的工作站的读取Combiner函数提交的数据itemsets,sup，由于许多不同的候选k项集会映射到相同的Reduce函数，因此对键值itemsets进行排序使得具有相同候选k项集的数据聚合在一起，形成itemsets,list(sup)。工作站点遍历排序后的中间数据，将itemsets,list(sup)传递给Reduce函数，然后Reduce函数把相同候选k项集itemsets的支持度计数累加起来，就得到此候选k项集在整个事物数据库中的实际支持度计数，然后和最小支持度比较，确定局部频繁k项集的集合。

⑥ 把比较之后的R各Reduce函数的输出的项集合并就得到最终的频繁K项集的集合。

⑦ k值从数值1开始递增，直到成的k频繁项集为空，至此，已找出所有的频繁项集。

4. 验证Aproiri改进算法效率实验的设计

① 实验环境

在 Linux 环境建立 Hadoop 集群环境，共 4 个节点，每个节点的处理器为 Pentium( R) 双核 CPU E5400 2.70GHz，2GB 内存。操作系统均采用 Ubuntu 10．10，JDK 版本为 Sun JDK 1.6.0_24，Hadoop 为0.20.2 稳定版本．。4个节点均作为从节点，并把其中一个节点同时作为主节点。

② 实验数据集

使用 webdocs 和 accidents 作为实验数据集， Webdocs有1.4 GB，共 1692082 条事务，5267656个不同的项，其中最长的事务有714772项。Accidents有33.9 MB，共340184条记录，有572不同的属性值，平均每条记录45个属性。

③ 记录并分析实验

Hadoop 分布式文件系统( HDFS) 默认的块大小是64 MB，因此 1．4 GB 大小的 Webdocs 数据集被分布在不同的节点上，体现了数据分割存放的特点。而33.9MB大小的Accidents数据集全部存放于某个节点上。将Webdocs数据集输入，根据输出结果画出坐标图，横轴代表集群节点数，纵轴代表加速比，支持度定为0.1。观察是否随着集群节点数的增加，算法的加速比随之提高。

以Accidents为实验数据，支持度设为 0.2，采用传统Aproiri算法和改进的Aproiri算法分别挖掘频繁项集。将 Map 的输入分片大小更改为9 MB，使原数据集划分为4 小部分，开启4 个 Map 任务， 充分利用 4 个节点的计算资源。比较两种算法执行的时间消耗，其结果应该是改进后的算法时间消耗远小于普通算法。