SOM算法在MapReduce框架上的实现.docx

目录
1 Hadoop MapReduce编程框架 1
Hadoop MapReduce编程框架的原理 1
Hadoop MapReduce编程框架的执行过程 1
2  SMO优化算法(Sequential minimal optimization) 2
SMO的基本思想 2
选择两个样例的搜索方法 4
SMO中拉格朗日乘子的启发式选择方法 9
3 SOM算法在MapReduce框架上的实现 10
1 Hadoop MapReduce编程框架
Hadoop MapReduce编程框架的原理
MapReduce是一种适用于大规模数据处理的编程模型。它将工作流程分为:map和reduce两个阶段,每个阶段都使用key/value对作为输入和输出,分别由进行任务分解的Map函数和对处理结果进行汇总的Reduce函数来实现。MapReduce将分布式处理的底层细节进行了封装,开发者只需要调用Map函数和Reduce函数即可编写分布式程序。因此,MapReduce己经成为云平台中主流的分布式数据处理模型。
Hadoop MapReduce是Google的Mapreduce的开源实现。主要有Map, Combine和Reduce三种操作组成:
Map操作主要完成对任务的分解功能,将原始数据按照设定的参数值分割成数据块,并将从数据块中读取出来的key/value进行map处理生成中间结果键值对,并以缓冲的方式写到磁盘。每个Map操作对应一个默认大小为100M的环形缓冲区,当缓冲内容达到指定大小时,后台线程开始将溢出内容写入磁盘。
Combine操作是可选的,该操作将Map操作的中间结果键值对进行合并,即将具有相同key值的key/value对合并为一个键值对。
Reduce操作将分解后的多任务的处理结果进行汇总,输出最终结果。
Hadoop MapReduce中的Map, Reduce函数需要遵循如下形式:
Map:(K1,V1) -> list(K2,V2)
Reduce:(K2,list(V2)) -> list(K3,V3)
通常来说,Map函数的输入键值对(K1,V1)的数据类型与输出键值对(K2,V2)的数据类型是不一致的,但是Reduce函数的输入数据类型与Map函数的输出数据类型必须是相同的。
Hadoop MapReduce编程框架的执行过程
Hadoop MapReduce框架采用master/slave的组织结构。集群由一个主控节点master和若干个slaves节点组成。
master节点也称为jobtacker,负责调度构成一个作业的所有任务,并监控各个任务的执行情况,这些任务被分配在集群中的slave节点上完成。slave节点也称为tasktracker,仅负责执行由master指派的任务即可。
一般来说,分布式文件系统(HDFS)与Hadoop MapReduce框架部署在同一个Hadoop集群上,也就是说存储节点与计算节点通常是相同的。这种配置允许Hadoop MapReduce框架在己经存放好数据的节点上高效地完成任务的执行和调度,同时有利于提高整个集群的网络带宽的使用率。
当调用Hadoop MapReduce框架完成分布式作业时,集群主要完成以下工作:
(1)分布式文件系统( HDFS)根据系统设置对原始数据文件进行分块处理,并将划分好的数据块部署在集群中,等待处理;
(2)主控节点master根据分块任务的多少和各个slave节点的空闲情况进行任务的指派;
(3)slave节点读取相关的数据块,并对其进行处理,产生的中间结果键值对(key/value)暂时缓冲在内存中;
(4)slave节点由执行map过程产生的中间结果被定时的写入到本地磁盘,并发送给master节点。master节点则将这些结果信息传送给执行reduce过程的工作节点;
(5)执行reduce过程的节点将各个中间结果按照关键字进行排序以及合并。在对有序的键值对进行处理之后得到最终输出结果并将结果输出到文件。
2  SMO优化算法(Sequential minimal optimization)
SMO的基本思想
SMO算法由Microsoft Research的John C. Platt在1998年提出,并成为最快的二次规划优化算法,特别针对线性SVM和数据稀疏时性能更优
首先回到SVM对偶函数最后的优化问题:
要解决的是在参数上求最大值W的问题,至于和都是已知数。C是预先设定的惩罚参数数。
我们需要一次选取两个参数做优化,比如和,此时可以由和其他参数表示出来。这样回带到W中,W就只是关于的函数了。