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

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

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

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

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

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

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

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

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

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

10、reeID,Dataset)Bagging(TreeID,Dataset)Bagging(TreeID,Dataset)Random Forest分類(lèi)器Split1Splitn提取特征(DenseSIFT)提取特征(DenseSIFT)背景知識(shí)Hadoop簡(jiǎn)介圖像并行化處理DenseSIFT算法提取特征BoVW模型和空間金字塔表示圖像構(gòu)建Random Forest分類(lèi)器實(shí)驗(yàn)結(jié)果分類(lèi)準(zhǔn)確率Kappa系數(shù)大小大小單機(jī)單機(jī)1臺(tái)臺(tái)2臺(tái)臺(tái)3臺(tái)臺(tái)4臺(tái)臺(tái)5臺(tái)臺(tái)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ī)森林少。但在一個(gè)節(jié)點(diǎn)的情況下，加速比小于1，這是由于從節(jié)點(diǎn)本身的Tas