基于Hadoop平臺的隨機(jī)森林算法研究及圖像分類系統(tǒng)實(shí)現(xiàn)

1、基于基于HadoopHadoop平臺的隨機(jī)森林算法研究及平臺的隨機(jī)森林算法研究及圖像分類系統(tǒng)實(shí)現(xiàn)圖像分類系統(tǒng)實(shí)現(xiàn)背景知識Hadoop簡介圖像并行化處理DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果背景知識u 圖像分類圖像分類 圖像分類是計(jì)算機(jī)視覺、模式識別與機(jī)器學(xué)習(xí)領(lǐng)域非?；钴S的研究方向。圖像分類技術(shù)在很多領(lǐng)域得到廣泛應(yīng)用，包括人臉識別、行人檢測、智能視頻分析、行人跟蹤等，交通領(lǐng)域的交通場景物體識別、車輛計(jì)數(shù)、逆行檢測、車牌檢測與識別，以及互聯(lián)網(wǎng)領(lǐng)域的基于內(nèi)容的圖像檢索、相冊自動歸類等。可以說，圖像分類已經(jīng)應(yīng)用于人們?nèi)粘Ｉ畹姆椒矫婷?/p>

2、，改變了人類生活方式。 場景分類物體分類背景知識Hadoop簡介圖像并行化處理DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果Hadoop簡介u Hadoop Hadoop是一個開源的、可靠的、可擴(kuò)展的分布式并行計(jì)算框架，主要由分布式文件系統(tǒng)HDFS和MapReduce并行計(jì)算框架組成。 隨著圖像數(shù)據(jù)量不斷增長，海量的圖像數(shù)據(jù)處理是一個十分耗時(shí)的過程。Hadoop平臺有著優(yōu)秀的海量數(shù)據(jù)處理性能。將大規(guī)模的數(shù)據(jù)處理過程移植到Hadoop平臺上是一個很有意義的課題。Hadoop結(jié)構(gòu)示意MapReduce作業(yè)運(yùn)行背景知識Hadoop簡介圖像并

3、行化處理DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果HIPIu HIPI HIPI是Hadoop圖片處理的框架，它提供了用于在分布式計(jì)算環(huán)境中執(zhí)行圖片處理任務(wù)的API。通過把客戶端上的多張圖片合并成一個大的HIB文件,同時(shí)生成一個頭文件，記錄每張圖片的位移，然后把這些大的文件上傳到HDFS中。切割時(shí)，根據(jù)頭文件中記錄的位移，對HIB文件進(jìn)行切割，將得到的每個分塊提交給map任務(wù)進(jìn)行處理l 改進(jìn)：針對于圖像分類場景，在合并文件時(shí)同時(shí)將圖像的類別信息寫入到頭文件中，切割時(shí)再傳給圖像圖像并行化處理流程背景知識Hadoop簡介圖像并行化處理

4、DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果DenseSIFT算法 uDenseSIFT算法算法 是一種密集采樣算法，建立在SIFT算法的基礎(chǔ)之上。不同于一般的SIFT采樣過程，它首先將圖像劃分成為大小相同的區(qū)塊，在每一個區(qū)塊內(nèi)提取出一個128維的SIFT描述子。DenseSIFT算法 Li Fei-Fei 等人證明采用這種SIFT采樣方式，更適合于圖像分類的場景，它善于對均勻的圖像區(qū)域進(jìn)行處理，比如天空、水面、路面等。 整個過程在Map函數(shù)里進(jìn)行，也就是實(shí)現(xiàn)了對圖像特征的分布式提取。DenseSIFT算法背景知識Hadoop簡介圖

5、像并行化處理DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果BoVW模型 類比一篇文章由許多文字(textual words)組合而成，我們也可以將一張圖片看成由許多視覺單詞(visual words)組合而成，視覺單詞由圖像中不同區(qū)域提取出的特征點(diǎn)構(gòu)成。關(guān)鍵步驟1. 計(jì)算圖片特征區(qū)域的視覺詞匯(即SIFT描述子)2. 利用Kmeans算法將相似的視覺詞匯進(jìn)行聚類，構(gòu)造一個含有K個詞匯的詞典3. 再利用視覺詞典(visual vocabulary)將特征描述子映射為視覺單詞4. 統(tǒng)計(jì)每個視覺單詞在圖像中出現(xiàn)的頻率，生成視覺單詞直方圖流程

6、構(gòu)建Spatial Pyramid在利用BoVW模型表征圖像時(shí)，完全丟失了特征點(diǎn)的位置信息，構(gòu)造空間金字塔模型可以彌補(bǔ)這個缺陷。構(gòu)建過程：圖像分成若干個塊，分別統(tǒng)計(jì)每一個子塊的特征，最后將所有塊的特征拼接起來，形成完整的特征。劃分區(qū)塊的大小與賦予的權(quán)值大小成反比。構(gòu)建Spatial Pyramid構(gòu)建Spatial Pyramid 每一張圖片經(jīng)過BoVW詞袋模型的表示，成為一個300維的向量，再經(jīng)過構(gòu)建空間金字塔這一步之后，（4*4+2*2+1）*300 = 6300，每幅圖像被表示成為一個6300維向量，在此基礎(chǔ)之上，下一步將進(jìn)行隨機(jī)森林分類器的構(gòu)建。背景知識Hadoop簡介圖像并行化處理D

7、enseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果決策樹u決策樹 決策樹的結(jié)構(gòu)類似數(shù)據(jù)結(jié)構(gòu)中的樹模型,它是利用樹形圖來表示處理問題邏輯結(jié)果的一種方法。決策樹作為一種經(jīng)典的機(jī)器學(xué)習(xí)模型,常見的實(shí)現(xiàn)形式有:ID3、CART、C4.5等。決策樹中每一個非葉子節(jié)點(diǎn)代表一個決策節(jié)點(diǎn),利用某一個特征,按照某一規(guī)則可以對其進(jìn)行劃分,直到滿足終止條件。如果一個節(jié)點(diǎn)僅含有一類樣木,則停止劃分并將其作為葉子節(jié)點(diǎn)。對于決策樹來說,從根節(jié)點(diǎn)到每一個葉子節(jié)點(diǎn)的每一條路徑,代表的是一條劃分規(guī)則。決策樹實(shí)例隨機(jī)森林u 隨機(jī)森林 隨機(jī)森林是含有多棵決策樹的分類器,相較于決

8、策樹而言,隨機(jī)森林的性能的要高出其許多。得益于它的兩個隨機(jī)性：訓(xùn)練集抽取的隨機(jī)性和節(jié)點(diǎn)分裂的候選特征子集抽取的隨機(jī)性?；诸惼髦g的差異性,對于集成方法的性能至關(guān)重要,兩個隨機(jī)性保證了構(gòu)成隨機(jī)森林的決策樹之間的差異性,也使得隨機(jī)森林具有很好的分類效果。隨機(jī)森林模型隨機(jī)森林并行化基于Hadoop平臺，實(shí)現(xiàn)隨機(jī)森林算法的雙重并行化l 改進(jìn)：1. 建樹過程的并行化2. 節(jié)點(diǎn)分裂時(shí)，最佳分裂屬性選擇過程的并行化建樹過程的并行化 傳統(tǒng)的隨機(jī)森林算法中是采用串行的構(gòu)建方式，一個決策樹分類器構(gòu)建完成之后才進(jìn)行第二個決策樹分類器的構(gòu)建，依次類推。各個決策樹構(gòu)建過程相互獨(dú)立，為構(gòu)建決策樹分類器的并行化提供了理論

9、支持。 并行的過程是，首先獨(dú)立地通過Bagging抽取用于構(gòu)建每個決策樹分類器的訓(xùn)練樣本，然后每個決策樹分類器并行的的生長，它們都是用自己的隨機(jī)特征子空間去進(jìn)行分裂。節(jié)點(diǎn)分裂最優(yōu)屬性選擇并行化 在構(gòu)建決策樹的過程中，需要得到每個節(jié)點(diǎn)的分最優(yōu)分裂屬性。傳統(tǒng)的方式是遍歷候選屬性集中所有的屬性，計(jì)算每個屬性對應(yīng)的信息增益，時(shí)間復(fù)雜度較高。可以進(jìn)一步的并行化。 將候選屬性集分割成若干個子集，并行化的進(jìn)行每個子集中最優(yōu)分裂屬性的選取，最后reduce每個子集的結(jié)果，得出全局最優(yōu)分裂屬性。訓(xùn)練圖像Split0提取特征(DenseSIFT)Kmeans構(gòu)建詞典詞袋模型向量空間金字塔輸入向量Bagging(T

10、reeID,Dataset)Bagging(TreeID,Dataset)Bagging(TreeID,Dataset)Random Forest分類器Split1Splitn提取特征(DenseSIFT)提取特征(DenseSIFT)背景知識Hadoop簡介圖像并行化處理DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類器實(shí)驗(yàn)結(jié)果分類準(zhǔn)確率Kappa系數(shù)大小大小單機(jī)單機(jī)1臺臺2臺臺3臺臺4臺臺5臺臺1.61G運(yùn)行時(shí)間2m20s2122m35s35332s91325s5522s23322s787加速比0.904.375.66.366.363.21G

11、運(yùn)行時(shí)間4m33s3204m52s1341m0s29941s24636s65432s243加速比0.934.556.667.588.538.03G運(yùn)行時(shí)間11m8s16912m31s902m19s1631m41s1631m31s361m27s712加速比0.894.806.617.347.6716.07G運(yùn)行時(shí)間22m15s9024m24s624m29s3343m5s9192m6s7162m10s55加速比0.914.967.2110.5910.2632.14G運(yùn)行時(shí)間44m24s8448m30s78m38s8976m3s6585m28s6484m6s593加速比0.925.147.338.1210.8加速比總結(jié) 1. 基于MapReduce并行化的隨機(jī)森林算法在執(zhí)行時(shí)間上要比單機(jī)版的隨機(jī)森林少。但在一個節(jié)點(diǎn)的情況下，加速比小于1，這是由于從節(jié)點(diǎn)本身的Tas