【作者】 吴磊；

【导师】 程良伦；

【作者基本信息】 广东工业大学 ， 软件工程， 2019， 硕士

【摘要】 关联规则挖掘作为数据挖掘的一个重要分支,用于发现数据当中隐藏的联系,为决策提供支持,在web挖掘、推荐系统、故障诊断等诸多领域有着广泛的应用。关联规则挖掘最核心、最耗时的步骤是频繁模式的获取。目前国内外已经开展了大量的研究来加快频繁模式的挖掘速度,但是随着大数据时代的到来,数据量越来越大,目前的频繁模式挖掘算法仍然无法满足日益增长的对挖掘算法时效性的要求。如何提升大数据环境下的频繁模式挖掘效率仍然是目前数据挖掘领域面临的一个巨大挑战。为了提升频繁模式挖掘效率,本文开展了以下研究:(1)结合频繁模式挖掘算法当中经典的Apriori算法、FP-growth算法、ECLaT算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM(Interval Interaction and Transaction Mapping)。该算法只需扫描两次数据集,第一次扫描生成频繁1-项集,第二次扫描生成条件模式树,接着扫描条件模式树将频繁1-项集映射到区间当中,通过区间求交来进行模式增长,从而避免了递归生成条件模式树带来的开销。同时本文还通过引入Hash存储结构存储项集的区间、利用布隆过滤器对候选项集进行筛选、优化区间求交的方式来进一步提高算法的效率。(2)本文在IITM算法的基础之上提出基于大数据处理平台Spark的PIITM(Parrallel Interval Interaction and Transaction Mapping)算法,该算法通过将不同后缀的条件模式基划分到不同的节点上使得各个节点的数据相互独立,从而可以在各个节点并行地进行频繁项集挖掘。同时该算法在划分数据时综合考虑节点的负载能力、节点当中原有数据分布,使得划分后各个节点的负载尽可能均衡,并且尽量将数据划分到拥有其条件模式基最多的节点从而减少数据划分阶段需要进行的数据交换。结合Spark大数据处理引擎来进行分布式数据挖掘,使得该算法更加高效、易于扩容、能够容错。最后本文实现上述算法并和其它同类算法在多个真实数据集上进行挖掘效率对比。实验表明在多个真实数据集上,在不同的支持度下本文提出的IITM算法以及其并行化改进算法PIITM算法都有较高的执行效率。更多还原

【Abstract】 Association rule mining,an important branch of data mining,is applied to discover hidden connections in data to provide decision supports.It has been widely applied to many fields,such as web mining,recommender system and fault diagnosis.The most important and time-consuming step of association rule mining is the acquisition of frequent patterns.At present,a lot of research has been carried out to speed up the frequent pattern mining at home and abroad.However,in the age of the big data,the current frequent pattern mining algorithms cannot satisfy the growing requirements for the low time cost,while the amount of data becomes more and more larger.How to improve the efficiency of frequent pattern mining in big data environment is still a huge challenge in the field of data mining.In order to improve the efficiency of the frequent patterns mining algorithm,the following research is carried out:(1)Combining the classical Apriori algorithm,FP-growth algorithm and ECLaT algorithm,a frequent pattern mining algorithm based on Interval Interaction and Transaction Mapping(IITM)is proposed.Fitstly,the proposed algorithm just needs to scan the dataset twice.Frequent 1-itemsets are generated in the first scan,and a conditional pattern tree is generated in the second scan.Then,the intervals of all frequent 1-itemset are obtained by scaning the conditional pattern tree.Subsequently,the frequentpattern growth performed by the interval intersection can avoid the time cost of recursively generating conditional pattern trees.At the same time,a lot of measures are introduced to improve the efficiency of the algorithm,i.e.introducing Hash storage structure to sotre the intervals of the itemsets,useing the Bloom filter to filter out the non-frequent itemset and optimizing the interval intersection.(2)On the basis of the IITM algorithm,Parrallel Interval Interaction and Transaction Mapping(PIITM)algorithm is proposed,which is based on the big data processing platform Spark.The PIITM algorithm divides the conditional pattern bases of different suffixes into different machines(nodes)to make the data of each node independence.Therefore,the frequent item set mining is parallelly performed by the PIITM algorithm in each nodes.Meanwhile,the PIITM algorithm considers the load capacity of the nodes and the original data distributions among the nodes in dividing the data,which can balance the load of each nodes as much as possible.Also,the PIITM algorithm devides the data into the nodes with the most conditional pattern base as much as possible to reduce the unnecessary data exchange in the phase of data division.In order to make the PIITM algorithm more efficient,more extensible and fault-tolerant,the Spark big data processing engine is applied to distributed data mining.In the last of this paper,the performances of the two proposed methods and the orther up-to-date algorithms are evaluated on multiple real data sets.The experiments show that the IITM and PIITM algorithms attrive satisfy performace under different support degrees on multiple real data sets.更多还原