Archive

Posts Tagged ‘moner carlo’

MapReduce实现Monte Carlo特征选择的可行性概述

2011/04/04 发表评论

第一节:monte carlo特征选择过程

用monte carlo的思路来实现高维特征的选择,其实有点类似于随机森林的过程,但选择指标进行了改进,下面主要介绍一种自己在研究生阶段所用到的方法。

先看一张方法的框图:



方法不但考虑分类率,还考虑构成决策树各结点的基因对整体的重要性,因为当某个基因作为一棵决策树的分裂结点的属性时,如果其包含的信息量越多,那么对决策树分类率的作用也越大。因此定义某个变量(特征)的相对重要性指标为,具体定义为

从框图中可以看出,整个过程按照随机森林的思想对数据进行多次抽样分配。首先对原始数据进行c次重采样,把数据分成c组训练集和测试集;然后从特征中随机选择m个特征来构建决策树,在这过程中共随机选择了s次,而每次构建t棵决策树; 最后整个过程得到cst棵决策树,计算每个特征的相对重要性指标值RI后,排序后得到重要特征。

第二节:MapReduce原理概述

用书中天气预报的例子说明下MapReduce大致原理

假设我们需要处理一批有关天气的数据,其格式如下:

  • 按照ASCII码存储,每行一条记录
  • 每一行字符从0开始计数,第15个到第18个字符为年
  • 第25个到第29个字符为温度,其中第25位是符号+/-
0067011990999991950051507+0000

0043011990999991950051512+0022+

0043011990999991950051518-0011+

0043012650999991949032412+0111+

0043012650999991949032418+0078+

0067011990999991937051507+0001+

0043011990999991937051512-0002+

0043011990999991945051518+0001+

0043012650999991945032412+0002+

0043012650999991945032418+0078+

现在需要统计出每年的最高温度。

Map-Reduce主要包括两个步骤:Map和Reduce

每一步都有key-value对作为输入和输出:

  • map阶段的key-value对的格式是由输入的格式所决定的,如果是默认的TextInputFormat,则每行作为一个记录进程处理,其中key为此行的开头相对于文件的起始位置,value就是此行的字符文本
  • map阶段的输出的key-value对的格式必须同reduce阶段的输入key-value对的格式相对应

对于上面的例子,在map过程,输入的key-value对如下:

(0, 0067011990999991950051507+0000+) 

(33, 0043011990999991950051512+0022+)

(66, 0043011990999991950051518-0011+)

(99, 0043012650999991949032412+0111+)

(132, 0043012650999991949032418+0078+)

(165, 0067011990999991937051507+0001+)

(198, 0043011990999991937051512-0002+)

(231, 0043011990999991945051518+0001+)

(264, 0043012650999991945032412+0002+)

(297, 0043012650999991945032418+0078+)

在map过程中,通过对每一行字符串的解析,得到年-温度的key-value对作为输出:

(1950, 0) 

(1950, 22)

(1950, -11)

(1949, 111)

(1949, 78)

(1937, 1)

(1937, -2)

(1945, 1)

(1945, 2)

(1945, 78)

在reduce过程,将map过程中的输出,按照相同的key将value放到同一个列表中作为reduce的输入

(1950, [0, 22, –11]) 

(1949, [111, 78])

(1937, [1, -2])

(1945, [1, 2, 78])

在reduce过程中,在列表中选择出最大的温度,将年-最大温度的key-value作为输出:

(1950, 22) 

(1949, 111)

(1937, 1)

(1945, 78)

其逻辑过程可用如下图表示:

image

第三节:MapReduce实现monte carlo特征选择

mapreduce有两个主要特性:

MapReduce基本架构 Master-Slave 模型, Master负责任务(Task) 和 数据和运算的切分,和分发,分发到集群的各节点上; Slave 在这里叫 Worker,负责执行Master分发的任务;
Map Reduce 的运算过程是先分后合。
Map 意思直译为映射,不过理解为“分治”更容易懂。就是将数据和运算进行切分,并分发到集群节点上;
Reduce (本意是减少,所以初看名称时一直不理解减少为合意), 这里应该理解为该词的另一个意思,“归并”, 就是将分开执行的众多计算任务和数据进行合并,形成最终的输出结果。

而monte carlo的过程从结构上来说也是mater slave结果,如下图:

 

同样,它也是一个先分发计算,后合并得到结果的过程。

在这里k为每一个特征的编号,而v为每一次计算RI的值,简图如下:

在map阶段计算各个master上的特征的RI值;

shuffle过程归并每一个特征的RI值;

reduce过程计算每一个特征的总RI值,进行求和计算;

output阶段,这种背景下可以直接输出,而由于monte carlo算法的时间消耗点在map过程,因此可以使用1个reduce,然后直接将结果输出。

本人只是一个可行性分析,没有具体操作实现过,如有错误忘谅解。

by pierrelai