论文部分内容阅读
关联规则一直是数据挖掘领域中一个研究热点,被广泛的应用于各个领域。随着web2.0时代的到来,特别是以用户为主导产生互联网内容的社交网络的兴起,数据积累呈现出指数级的增长趋势。在面对海量的数据集时高效地使用关联规则是数据挖掘的重要任务。本文对FP-Growth算法的并行化进行了研究,在己有PFP算法基础上,设计了一种新的并行FP-Growth算法。之所以要并行化,是因为要在面对大规模数据处理时,传统的FP-Growth算法是基于单机的内存消耗算法,因此会出现内存不足或者执行时间过长等问题。现有的并行FP-Growth算法已经解决了如划分数据库事务集这一问题,可以保证划分后的事务集彼此之间相独立,但单节点在FP-tree挖掘过程中还是存在迭代次数过多,效率低下的问题,并且主节点向子节点划分数据集时也没有考虑负载均衡。因此,实现高效率并且负载均衡的并行FP-Growth算法是本文要解决的问题。本文在PFP这种原有的基于MapReduce的并行FP-Growth算法之上运用剪枝策略,通过合并FP-tree中满足条件的非频繁路径从而减少了其部分分支的迭代次数,加快了挖掘效率。另外,在主节点向子节点分配计算数据集时使用负载均衡策略,首先由Flist进行各频繁项的负载估计,然后通过负载均衡算法将频繁项分组得至Glist。通过这两种策略的结合,本文设计了一种新的并行FP-Growth算法,并设计实验证明该算法相对原算法在执行效率上的提升。本文将并行FP-Growth算法应用在微博好友推荐上,设计了一种基于关联则的微博好友推荐算法。以往的社交网络好友推荐往往是基于用户之间的共同好友,但是微博除了具有社交网络的属性外,更加注重的是新鲜事的传播,因此具有潜在好友关系的用户不仅会关注相同的人,更加会关注相同的事(以用户对微博的转发或者评论体现)。本文将这两点结合,利用新浪微博的开放API接口获取用户之间的关注数据和用户对微博的关注数据,将这里的“关注”看成一条交易,用户看成交易项,所有交易的集合看作交易数据库。在此基础上进行并行FP-Growth算法,提取出产生的频繁二项集,按频度由高到低取前N个用户作为推荐好友,实验表明该算法在推荐的准确率和召回率上优于基于共同好友的Friend-of-friend算法。