基于并行计算的Apriori算法的优化与Java实现开题报告

1. 研究目的与意义

如今计算机信息技术已经发展和研究已经深入到一定层面，移动互联网和传统互联网以及社交应用的不断崛起让数据呈现出几何化激增状态。近两年来，以智能手机、平板电脑为代表的移动设备所产生的数据量暴增，我们被金融数据、科学数据、医疗数据、统计数据和销售数据所淹没，迎来了大数据时代。大数据技术的发展首次将不同行业的用户、运营商、服务商以及生态链前端提供商融入到一个大环境中，推动了人民上网、消费、娱乐、社交等习惯的快速转变，无论是公共服务领域，还是生产者消费者市场，正在与大数据产生紧密的联系。

面对如此庞大的数据量，一种可以从海量相关数据集中挖掘与用户切实相关的高效率到数据挖掘技术便显得尤为迫切。数据挖掘是一个寻找隐含的潜在有用的知识的过程，关联规则是数据挖掘中重要的研究内容之一。关联规则算法是用于描述事物之间潜在的相关性，它用于搜索事物项集之间的显示或者隐式关系，有助于分析管理和决策。经典的以广度优先遍历为主的Aprioni 算法和以深度优先遍历为主的FP-Growth算法，经过多年的发展已经成为一个较成熟的研究领域。然而，这些传统的关联规则算法已经无法满足大数据时代的需求，所以，如何对这些算法进行优化以使其符合当今时代的特点成为迫在眉睫的问题。

2. 研究内容和预期目标

前文已经述及，当今时代是一个大数据时代，传统串行关联规则算法已经无法承载数据的爆炸式增长，从而表现出了众多的缺陷与不足。而本次毕业设计拟对经典的apriori算法进行改进与优化，以提高它在处理大数据时的效率和性能。apriori算法是关联规则挖掘中的十分经典的算法，该算法采用迭代方法,通过连接步和剪枝步并反复扫描数据集,逐层搜索候选项集得到频繁项集.但是apriori算法有其自身的瓶颈:

(1) 算法在统计关联规则的过程中，产生的候选项太多，因此算法效率十分的低下，假设频繁一项集有一百个，那么产生的候选项集将达到数千亿的量级。

(2) 先验性算法在计算过程中需要反复的遍历输入数据，扫描事务数据是一个十分浪费资源的操作，同时也会存在十分巨大的时间浪费。

3. 国内外研究现状

自从agrawal等人于1993年提出了关联规则挖掘概念，1994年又提出了经典的apriori算法到现在，关联规则挖掘已经被众多科学家经过广泛而深入的研究,也取得了显著的发展。关联规则挖掘主要经历了以下好几个阶段：基于原始购物单数据研究，这也是著名的利用关联规则改进营销策略的成功案例；随着需求的不断增加，关联规则拥有许多扩展形式，如多维关联规则、量化关联规则、多层关联规则等；同时，关联规则一般性问题比如规则的兴趣度和度量以及规则的有效性和兴趣度也得到了深入研究。

关联规则算法研究的现状主要分为以下几个类别:

(1)经典串行算法: apriori算法是一种限制候选集的逐层迭代算法，在两个地方存在性能瓶颈，一是需要多次扫描数据库，二是虽然可以限制候选项集，但是当数据量较大时，候选集的数据量依然会非常大，特别是候选2项集；fp-growth 算法不产生候选项集的挖掘算法；eclat算法：一种基于垂直数据格式的算法。

4. 计划与进度安排

从关联规则算法的研究现状和研究趋势出发，基于传统串行算法无法承载当今数据时代的爆炸式增长，以及无法完美融合现行大数据计算引擎的缺陷与不足。本次设计着力于将经典关联规则apriori算法建立在云计算分布式平台上，从而提高apriori算法处理海量数据时的执行效率。主要工作计划为:

(1)本次设计首先需要知道关联规则挖掘技术的相关概念和背景知识，并了解相关关联规则算法的研究现状。其次还要明确大数据研究以及当今流行云平台的发展状况，以及对基于各平台的关联规则算法该如何优化。此外，还必须明确分布式计算引擎下关联规则算法的研究与优化的意义所在。

(2)在此之后，本次设计需要对传统关联规则算法apriori 进行深入解析，并对其中存在的缺陷做深入研究，从而将算法需要多次扫描数据库、计数时间过长以及产生庞大的候选集等缺点进行改进。

5. 参考文献

[1]衣梦涵,王慧颖.基于蚁群算法的关联规则挖掘[j].统计与决策,2019,35(17):79-81.

[2]刘莉萍,章新友,牛晓录,郭永坤,丁亮.基于spark的并行关联规则挖掘算法研究综述[j].计算机工程与应用,2019,55(09):1-9.