请介绍一下基于MapReduce的遗传算法的原理 - 高飞网
7人看过

请介绍一下基于MapReduce的遗传算法的原理

2014-04-20 01:25:58

面向海量Web数据的数据挖掘方法或者算法必须是能进行并行处理的。在实际大型企业Web 站点中,URL 数常常达到几万甚至几十万,这将造成构造出的Web 访问矩阵过大,传统基于单机处理海量数据的能力成为发展的一个瓶颈。为了解决此问题,对常用数据挖掘算法C4.5SPRINT、关联规则、K-means 等进行改进,提出了许多基于传统挖掘算法的并行算法。其中,基于数据划分的方法是普遍采用一种并行处理的方法:首先将数据集合划分为适当的子块,然后在各个子块上用传统的挖掘算法(Aprior算法)进行处理,最后将各个子块上的结果进行合并。通过上文的表述,MapReduce已经实现了对数据的划分,但前提是数据上下文是松耦合的。

遗传算法是一种求解问题的高度并行的全局随机化搜索算法,在求解问题为非连续、多峰以及有噪声的情况下,能够以很大的概率收敛到最优解或满意解,具有较好的全局最优解求解能力。同时,由于遗传算法只需在初始群体的基础上进行遗传进化操作,不需要对数据库进行多次扫描,大大减少了数据的传输量,因此将遗传算法用于基于Hadoop 集群框架的用户浏览偏爱路径挖掘,在提高算法执行效率的同时还能减少数据的传输量[7-8]

融合了基于MapReduce的数据分割和遗传算法的新算法结合了数据分割技术的分布式处理和遗传算法的全局搜索最优解的优点。新算法的表述如下:

步骤1
数据分割处理。针对Web 数据的特点,对Web数据进行分割,比如对Web日志文件按用户和访问日期进行分割,并传输到不同的子节点上,同时获取用户定义的支持度S

步骤2
初始化群体。各子节点在Hadoop平台下利用Map Reduce 操作将数据集转化为满足用户定义支持度的偏爱子路径的1-项集形式,作为遗传算法的初始种群。

步骤3
适应度值计算。通过一条访问路径的频度衡量其是否是用户偏爱的访问路径,因此,适应度函数定义如下:


其中,S’为路径的访问频度。保留Fitness 大于1 的个体进入下一代。

步骤4
若当前进化代中所有个体的适应度值Fitness 等于1,表明群体经过遗传进化后得不到改善,转至步骤7,否则,继续。

步骤5
对该代进行选择、交叉操作。在遗传进化过程中,首先采取精英保留策略,保留遗传过程中的精英个体,让它们不参与交叉操作直接进入下一代。本文将第i 个个体的选择概率定义为:


其中,为第i 个个体的路径访问频度;
为群体中所有个体路径访问频度的平均值。

在保留的个体中,根据选择概率选取个体进行交叉操作,当代数为50 的倍数时,进行迁移操作,相邻2 个子群体间联姻,并将联姻后代中的最佳个体复制到相关的源种群中。

步骤6
将整个子代群体替代父代群体,形成新一代,然后转至步骤2

步骤7 当经过一定遗传代数后,k 值仍无变化,则退出进化,输出最终用户偏爱访问路径。

 

还没有评论!
23.20.129.162