基于Hadoop平台的随机森林算法研究及图像分类系统实现

1、基于基于HadoopHadoop平台的随机森林算法研究及平台的随机森林算法研究及图像分类系统实现图像分类系统实现背景知识Hadoop简介图像并行化处理DenseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果背景知识u 图像分类图像分类 图像分类是计算机视觉、模式识别与机器学习领域非常活跃的研究方向。图像分类技术在很多领域得到广泛应用，包括人脸识别、行人检测、智能视频分析、行人跟踪等，交通领域的交通场景物体识别、车辆计数、逆行检测、车牌检测与识别，以及互联网领域的基于内容的图像检索、相册自动归类等。可以说，图像分类已经应用于人们日常生活的方方面面

2、，改变了人类生活方式。 场景分类物体分类背景知识Hadoop简介图像并行化处理DenseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果Hadoop简介u Hadoop Hadoop是一个开源的、可靠的、可扩展的分布式并行计算框架，主要由分布式文件系统HDFS和MapReduce并行计算框架组成。 随着图像数据量不断增长，海量的图像数据处理是一个十分耗时的过程。Hadoop平台有着优秀的海量数据处理性能。将大规模的数据处理过程移植到Hadoop平台上是一个很有意义的课题。Hadoop结构示意MapReduce作业运行背景知识Hadoop简介图像并

3、行化处理DenseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果HIPIu HIPI HIPI是Hadoop图片处理的框架，它提供了用于在分布式计算环境中执行图片处理任务的API。通过把客户端上的多张图片合并成一个大的HIB文件,同时生成一个头文件，记录每张图片的位移，然后把这些大的文件上传到HDFS中。切割时，根据头文件中记录的位移，对HIB文件进行切割，将得到的每个分块提交给map任务进行处理l 改进：针对于图像分类场景，在合并文件时同时将图像的类别信息写入到头文件中，切割时再传给图像图像并行化处理流程背景知识Hadoop简介图像并行化处理

4、DenseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果DenseSIFT算法 uDenseSIFT算法算法 是一种密集采样算法，建立在SIFT算法的基础之上。不同于一般的SIFT采样过程，它首先将图像划分成为大小相同的区块，在每一个区块内提取出一个128维的SIFT描述子。DenseSIFT算法 Li Fei-Fei 等人证明采用这种SIFT采样方式，更适合于图像分类的场景，它善于对均匀的图像区域进行处理，比如天空、水面、路面等。 整个过程在Map函数里进行，也就是实现了对图像特征的分布式提取。DenseSIFT算法背景知识Hadoop简介图

5、像并行化处理DenseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果BoVW模型 类比一篇文章由许多文字(textual words)组合而成，我们也可以将一张图片看成由许多视觉单词(visual words)组合而成，视觉单词由图像中不同区域提取出的特征点构成。关键步骤1. 计算图片特征区域的视觉词汇(即SIFT描述子)2. 利用Kmeans算法将相似的视觉词汇进行聚类，构造一个含有K个词汇的词典3. 再利用视觉词典(visual vocabulary)将特征描述子映射为视觉单词4. 统计每个视觉单词在图像中出现的频率，生成视觉单词直方图流程

6、构建Spatial Pyramid在利用BoVW模型表征图像时，完全丢失了特征点的位置信息，构造空间金字塔模型可以弥补这个缺陷。构建过程：图像分成若干个块，分别统计每一个子块的特征，最后将所有块的特征拼接起来，形成完整的特征。划分区块的大小与赋予的权值大小成反比。构建Spatial Pyramid构建Spatial Pyramid 每一张图片经过BoVW词袋模型的表示，成为一个300维的向量，再经过构建空间金字塔这一步之后，（4*4+2*2+1）*300 = 6300，每幅图像被表示成为一个6300维向量，在此基础之上，下一步将进行随机森林分类器的构建。背景知识Hadoop简介图像并行化处理D

7、enseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果决策树u决策树 决策树的结构类似数据结构中的树模型,它是利用树形图来表示处理问题逻辑结果的一种方法。决策树作为一种经典的机器学习模型,常见的实现形式有:ID3、CART、C4.5等。决策树中每一个非叶子节点代表一个决策节点,利用某一个特征,按照某一规则可以对其进行划分,直到满足终止条件。如果一个节点仅含有一类样木,则停止划分并将其作为叶子节点。对于决策树来说,从根节点到每一个叶子节点的每一条路径,代表的是一条划分规则。决策树实例随机森林u 随机森林 随机森林是含有多棵决策树的分类器,相较于决

8、策树而言,随机森林的性能的要高出其许多。得益于它的两个随机性：训练集抽取的随机性和节点分裂的候选特征子集抽取的随机性。基分类器之间的差异性,对于集成方法的性能至关重要,两个随机性保证了构成随机森林的决策树之间的差异性,也使得随机森林具有很好的分类效果。随机森林模型随机森林并行化基于Hadoop平台，实现随机森林算法的双重并行化l 改进：1. 建树过程的并行化2. 节点分裂时，最佳分裂属性选择过程的并行化建树过程的并行化 传统的随机森林算法中是采用串行的构建方式，一个决策树分类器构建完成之后才进行第二个决策树分类器的构建，依次类推。各个决策树构建过程相互独立，为构建决策树分类器的并行化提供了理论

9、支持。 并行的过程是，首先独立地通过Bagging抽取用于构建每个决策树分类器的训练样本，然后每个决策树分类器并行的的生长，它们都是用自己的随机特征子空间去进行分裂。节点分裂最优属性选择并行化 在构建决策树的过程中，需要得到每个节点的分最优分裂属性。传统的方式是遍历候选属性集中所有的属性，计算每个属性对应的信息增益，时间复杂度较高。可以进一步的并行化。 将候选属性集分割成若干个子集，并行化的进行每个子集中最优分裂属性的选取，最后reduce每个子集的结果，得出全局最优分裂属性。训练图像Split0提取特征(DenseSIFT)Kmeans构建词典词袋模型向量空间金字塔输入向量Bagging(T

10、reeID,Dataset)Bagging(TreeID,Dataset)Bagging(TreeID,Dataset)Random Forest分类器Split1Splitn提取特征(DenseSIFT)提取特征(DenseSIFT)背景知识Hadoop简介图像并行化处理DenseSIFT算法提取特征BoVW模型和空间金字塔表示图像构建Random Forest分类器实验结果分类准确率Kappa系数大小大小单机单机1台台2台台3台台4台台5台台1.61G运行时间2m20s2122m35s35332s91325s5522s23322s787加速比0.904.375.66.366.363.21G

11、运行时间4m33s3204m52s1341m0s29941s24636s65432s243加速比0.934.556.667.588.538.03G运行时间11m8s16912m31s902m19s1631m41s1631m31s361m27s712加速比0.894.806.617.347.6716.07G运行时间22m15s9024m24s624m29s3343m5s9192m6s7162m10s55加速比0.914.967.2110.5910.2632.14G运行时间44m24s8448m30s78m38s8976m3s6585m28s6484m6s593加速比0.925.147.338.1210.8加速比总结 1. 基于MapReduce并行化的随机森林算法在执行时间上要比单机版的随机森林少。但在一个节点的情况下，加速比小于1，这是由于从节点本身的Tas