论文部分内容阅读
随着互联网、传感器等技术的发展,社会的信息化不断被推进,全球数据的生产速度也在飞快增长。众所周知,移动通信数据是承载着通信业务与互联网信息的大动脉,是网络信息时代发展的重要基础设施。因此,通信大数据的概念越发受到关注,数据价值信息的挖掘也逐渐成为研究热点。其中,数据集中项与项之间关联规则挖掘技术的分析和发现也是数据挖掘过程中的重要分支。同时,该项研究挖掘的规则中所蕴藏的潜在价值也是前所未知的。因此,如何高效、准确的完成通信大数据环境下的关联规则挖掘成为一个热门的研究主题。目前,虽然传统关联规则挖掘算法在大数据时代下的改进取得了一定的成果,然而,通信大数据环境下的数据类型多样、更新速度快等特点,使得此类算法的优化研究仍具有被无限探索潜力。此外,现有的改进算法在执行过程中的复杂度依然很高,难以将并行化计算嵌入到其大规模数据中。鉴于此,本文分别从所挖掘的数据类型和通信大数据的环境特征方面着手,通过对数据预处理和算法步骤的改进,针对算法执行结果的精确度以及算法执行的效率进行提升。本文主要工作如下:针对大规模高维数据在基于FP-growth算法的挖掘过程中存在数据特征捕捉不准确、结点负载不均衡、数据交互频繁以及频繁项集紧凑化程度低等问题,提出了基于MapReduce的并行挖掘算法PARDG-MR（the Parallel Association Rules Mining Algorithm by using Dimension Granulating based on MapReduce）。该算法首先根据数据特征,提出基于维度粒化算法DGA（the dimension granulated Algorithm,DGA）和负载均衡算法GPL（the algorithm of Grouping method based on prefix length,GPL）的DGPL策略（dimensional granulation and strategy of grouping method based on load estimation,DGPL）,从而完成对高维复杂数据特征属性的准确捕捉,并解决数据划分中结点负载不均衡问题;其次,提出基于PJPFP-Tree树的频繁项集并行挖掘策略PARM（Parallel Association Rules Mining Algorithm,PARM）,来实现频繁项集的并行化分组过程,提升算法的整体速率;最后,针对候选剪枝策略,提出基于剪枝前缀推论PPL（pruning prefix lemma）的整合结点剪枝算法PJPFP（Pruning JFP-growth Algorithm,PJPFP）,来提高频繁项集挖掘过程中的剪枝效率,增强频繁项集的紧凑化程度,进一步提升算法总体的挖掘效率。理论分析与实验结果共同表明,PARDG-MR算法不仅有效克服了高维数据在挖掘过程中的瓶颈,而且在内存消耗和挖掘效率上都有了极大的提高。针对基于MapReduce框架的Apriori关联规则挖掘算法产生候选项集较长、算法执行效率低等问题,以及大数据环境中数据快速更新造成增量处理等缺陷进行了研究,提出了一种基于项集动态加权的增量挖掘算法WDU-Apriori（weighted dynamic updating-Apriori）。首先该算法提出W-DPC（weighted dynamic passes combiner）机制作为其候选项集的结合方式,有效提高算法在大数据环境下的适应能力;其次对于新来的增量数据,设计了WBI（weighted border itemsets）策略,用于生成加权边界项集,以改进对于增量数据的挖掘效率;最后构建了CTP（calculate transform probability）方法,用于量化阈值边界项集变为频繁项集的可能性,这对先前的挖掘结果有了更高效的应用,降低节点负载的同时也解决了原始数据集扫描次数较多的问题。理论分析与实验结果共同表明,WDU-Apriori算法不仅有效提高了挖掘效率,平衡了每一个阶段的工作量,同时也有效降低了算法的时间复杂度。