Hadoop平臺下Mahout隨機森林算法的分析與實現(xiàn)?

曹蒙蒙 郭朝有

（海軍工程大學(xué)動力工程學(xué)院 武漢 430033）

1 引言

隨著信息技術(shù)、物聯(lián)網(wǎng)及互聯(lián)網(wǎng)的快速發(fā)展，數(shù)據(jù)正在以空前的速度產(chǎn)生和被收集。目前，各個行業(yè)都存儲了海量的數(shù)據(jù)，如何從這些海量的數(shù)據(jù)中挖掘出有價值的信息是亟需解決的問題。分類方法可以有效地解決該問題，它通過對已知類別的數(shù)據(jù)集進行學(xué)習(xí)，從中找出分類規(guī)則，進而對新的數(shù)據(jù)集進行預(yù)測判斷。但海量數(shù)據(jù)的處理對傳統(tǒng)分類算法提出了新的要求。為了提高分類算法的準確率和減輕計算機的計算負載，采用大規(guī)模計算機集群對海量數(shù)據(jù)進行分布式處理是一種有效的方法。

Hadoop是Apache軟件基金會旗下的一個開源分布式計算平臺，其源于Google的云計算基礎(chǔ)架構(gòu)系統(tǒng)，核心組成是HDFS分布式文件系統(tǒng)架構(gòu)和MapReduce分布式處理機制，可用于實現(xiàn)大規(guī)模分布式計算和并行處理。Mahout是來自Apache的、開源的機器學(xué)習(xí)軟件庫，它基于MapReduce模式封裝了大量的適用于數(shù)據(jù)挖掘的經(jīng)典算法，其中的部分算法通過轉(zhuǎn)換可以直接在Hadoop框架上進行使用，從而大大降低了大數(shù)據(jù)應(yīng)用中并行數(shù)據(jù)挖掘產(chǎn)品的開發(fā)［1］。在大數(shù)據(jù)的處理上，目前Hadoop已經(jīng)成為搭建云計算平臺的主流，國外IBM的藍云、雅虎及英特爾的“云計劃”等，國內(nèi)阿里巴巴、百度等云平臺均是基于Hadoop基礎(chǔ)架構(gòu)實現(xiàn)的［2］。而Mahout算法庫的機器學(xué)習(xí)主要集中在三個領(lǐng)域，即協(xié)同過濾（推薦引擎）、聚類和分類。分類模塊作為其中一種重要的方法具體包括Logistic Regression（邏輯回歸）、Naive Bayesian（樸素貝葉斯）、Support Vector Machine（支持向量機）、Random Forests（隨機森林）和Hidden Markov Models（隱馬爾科夫模型）。目前Mahout分類算法在Hadoop平臺上的應(yīng)用包括：第一，基于Hadoop平臺的分類算法在某方面的具體應(yīng)用，如高一男等［3］基于Hadoop平臺，利用Mahout的貝葉斯算法通過對郵件進行特征提取以檢測是否為釣魚郵件，并通過真實郵件數(shù)據(jù)進行測試，取得較好效果；梁世磊［4］基于Hadoop平臺利用MapReduce并行計算模型分布式設(shè)計了隨機森林算法，提高了圖像的分類效率；滿蔚仕等［5］通過將傳統(tǒng)的網(wǎng)格法與粒子群算法結(jié)合，提出一種新型衛(wèi)星并行粒子群算法，相比于單機支持向量機（SVM），Hadoop平臺分布式SVM在分類準確率和計算速度上均有明顯提高。第二，在Hadoop、Spark等不同云計算平臺中比較Mahout中的分類算法的運行效率和效果，如郭成林［6］在Hadoop和Spark平臺分別實現(xiàn)了決策樹、貝葉斯等機器學(xué)習(xí)算法并對改進算法進行了試驗和比較分析。

綜上所述，基于Hadoop的云計算平臺已經(jīng)是大數(shù)據(jù)分析與應(yīng)用的重要基礎(chǔ)架構(gòu)，而將傳統(tǒng)的分類算法運用到以MapReduce為模式的并行計算編程框架上，能夠有效解決對海量數(shù)據(jù)處理的瓶頸問題。因此，本文在搭建Hadoop物理集群平臺的基礎(chǔ)上，對Mahout分類算法中的隨機森林算法進行深入分析與研究，最后通過實際數(shù)據(jù)分析傳統(tǒng)森林算法在分布式環(huán)境下的優(yōu)點與不足。

2 Hadoop簡介

Hadoop是一種典型的Master∕Slave架構(gòu)，由一個Master節(jié)點和多個Slave節(jié)點組成，Master節(jié)點負責(zé)Slave節(jié)點上的任務(wù)調(diào)度，是整個系統(tǒng)的控制和調(diào)度中心，Slave節(jié)點負責(zé)數(shù)據(jù)的存儲和具體任務(wù)的執(zhí)行。其核心組成是HDFS分布式文件系統(tǒng)和MapReduce分布式并行計算框架［7］。Hadoop基本架構(gòu)如圖1所示。

圖1 Hadoop基本架構(gòu)

由圖1可知，Master節(jié)點由NameNode和Job?Tracker組成，其中NameNode是HDFS的Master，主要負責(zé)Hadoop分布式文件系統(tǒng)元數(shù)據(jù)的管理工作，包括文件系統(tǒng)的名字空間（namespace）以及客戶端對文件的訪問；JobTracker是MapReduce的Master，主要任務(wù)是啟動、跟蹤和調(diào)度各個Task?Tracker的任務(wù)執(zhí)行。Slave節(jié)點由DataNode和TaskTracker組成，其中DataNode主要負責(zé)數(shù)據(jù)的存儲并對數(shù)據(jù)進行冗余備份；TaskTracker主要根據(jù)任務(wù)需求然后結(jié)合本地數(shù)據(jù)執(zhí)行Map和Reduce任務(wù)。

3 隨機森林算法

Leo Breiman［8］最早提出隨機森林算法（Ran?dom Forests，RF），它是集成學(xué)習(xí)Bagging算法的一個擴展。隨機森林是由多棵決策樹組成的組合分類器，分類時使用森林里的多棵決策樹同時對某一對象進行分類，結(jié)果遵循“以少服多”的原則，并且相同深度的每一棵決策樹和每一個節(jié)點都能獨立進行訓(xùn)練和分類，因此它的訓(xùn)練效率和分類效果非常高［9］。決策樹是隨機森林的組成部分，下面首先對決策樹進行簡單介紹。

3.1 決策樹

決策樹是一種有監(jiān)督的分類學(xué)習(xí)方法，通過對對象的各個特征屬性進行分類然后形成樹狀預(yù)測模型［10］。在建立決策樹的過程中，決策樹的屬性和類別之間的關(guān)系需要根據(jù)屬性度量值來決定，其中熵和信息增益是兩種重要的度量準則［11］。

熵的計算公式如（1）所示：

其中，Yt表示類別Y中的第代表類別Y的總記錄數(shù)，N為類別Y的總數(shù)目。

增益的計算公式如（2）所示：

3.2 隨機森林算法工作原理

隨機森林方法原理可以大致描述為從N個原始數(shù)據(jù)集中，采用bootstrap抽樣方式（即有放回抽樣）抽取N次，形成一組包含N個訓(xùn)練集的訓(xùn)練樣本；按照上述方式，重復(fù)T次，形成新的訓(xùn)練樣本集D；從訓(xùn)練樣本集D中選取m個特征屬性，并從中選擇最優(yōu)屬性以最佳的分裂方式形成決策樹；將T棵決策樹組合形成隨機森林，最后以“投票”的方式對測試集進行評估。隨機森林算法形成的流程圖如圖2所示。

4 Mahout中隨機森林算法的實現(xiàn)過程

在Mahout中，隨機森林算法的實現(xiàn)可由以下三個步驟完成［12］：第一，根據(jù)原始數(shù)據(jù)生成描述性

文件；第二，根據(jù)描述性文件、輸入數(shù)據(jù)及其他參數(shù)通過決策樹算法生成多棵決策樹，然后將這些決策樹轉(zhuǎn)換成隨機森林模型；第三，使用測試數(shù)據(jù)對上面生成的隨機森林模型進行評估，以檢驗生成模型的好壞。

圖2 隨機森林算法形成流程圖

4.1 生成描述性文件

描述性文件是對原始輸入數(shù)據(jù)數(shù)據(jù)屬性的集中概括，如每個特征屬性的數(shù)據(jù)格式、不參與建模的屬性列及輸出類別屬性列等。在Mahout中，用I（Ignore）表示不參與建模屬性列；用C（Categorical）表 示 離散的屬性列；用N（Numerical）表示連續(xù)的屬性列；用L（Label）表示輸出類別屬性列。下面用一個實例說明描述性文件的生成策略，具體見表1。

表1 隨機森林算法輸入數(shù)據(jù)訓(xùn)練集

首先對原始數(shù)據(jù)進行分析，由表1可以看出，第一列為行號，不參與建模；第二、三列為連續(xù)屬性的數(shù)據(jù)格式；第四列為離散屬性的數(shù)據(jù)格式；第五列為輸出類別。因此，描述性字符串為［I 2 N C L］，其中［2 N］即為［N N］。然后，將其存入描述性文件。

4.2 構(gòu)建隨機森林模型

隨機森林模型由多棵決策樹組合而成，形成隨機森林模型的過程如流程圖2所示。在構(gòu)建隨機森林的過程中，每生成一棵決策樹就會將其寫入文件，直至所有的樹都建立完成，這時所有的決策樹都存在同一個文件，然后再將這些樹封裝成一個鏈表，形成一個變量，即為隨機森林模型。

4.3 評估隨機森林模型

隨機森林模型建好之后的效果需要利用測試數(shù)據(jù)集進行測試，并根據(jù)分類的質(zhì)量進行評價。隨機森林模型評估過程描述如下：利用測試集對構(gòu)建的隨機森林模型進行評估，首先預(yù)設(shè)變量i為0；遍歷隨機森林中每棵決策樹對測試集的每條記錄進行分類，分類結(jié)果采用投票方式，選取分類次數(shù)重復(fù)最多的作為分類結(jié)果；將分類結(jié)果與原始數(shù)據(jù)集進行比較，如果分類正確則變量i循環(huán)增加，否則進行測試集中下一條記錄的分類，直至測試集中的N條記錄分類完畢；分類正確率由i∕N計算得出。隨機森林模型的評估的具體流程如圖3。

5 實驗及結(jié)果分析

5.1 實驗環(huán)境搭建及部署

本實驗環(huán)境基于物理機搭建了完全分布式的Hadoop集群，形成了以服務(wù)器為主節(jié)點，三臺PC機為從節(jié)點的主從架構(gòu)，集群環(huán)境部署如下：

1）硬件環(huán)境

實驗室共有服務(wù)器一臺，閑置電腦3臺?；谶@4臺機器搭建Hadoop完全分布式物理集群。其中服務(wù)器作為NameNode主節(jié)點，其余四臺機器作為DataNode從節(jié)點，各機器硬件配置信息如表2所示。

圖3 隨機森林模型評估流程圖

2）軟件環(huán)境

軟件環(huán)境具體配置如表3所示。

軟件環(huán)境配置說明：由于服務(wù)器和PC機的操作系統(tǒng)分別是64位和32位，因此上述各軟件版本有64位和32位之分。具體配置如下：在服務(wù)器 上 安 裝 VM?ware-worksta?

tion-full-12.0版本的虛擬機，并安裝Cen?tos-7 64位桌面版Linux操作系統(tǒng)，然后安裝對應(yīng)64位的JDK，即 JDK-8u144 64位，最后安裝Java開發(fā)工具Eclipse。在3臺PC機中任選2臺安裝VMware-work?station-full-10.0虛擬機，并安裝Centos-7 32位桌面版Linux操作系統(tǒng)，然后安裝對應(yīng)的32位JDK，即JDK-8u144 32位。在剩余一臺PC機上直接安裝Linux系統(tǒng)，即Cen?tos-7 32位桌面版操作系統(tǒng)和32位的JDK。

表2 實驗環(huán)境硬件配置

表3 實驗環(huán)境軟件配置

5.2 實驗數(shù)據(jù)分析

本次實驗原始數(shù)據(jù)集使用的是UCI公開數(shù)據(jù)庫中的banknote authentication數(shù)據(jù)集，它是利用小波變換工具對紙幣圖像進行鑒別，然后從圖片中進行特征提取的。該數(shù)據(jù)集共有1372條記錄，每條記錄含5列數(shù)據(jù)，其中前4列為樣本特征屬性，均為連續(xù)數(shù)值型數(shù)據(jù)格式，最后一列為樣本的類別標(biāo)簽即真鈔或偽造鈔票。該數(shù)據(jù)集的特征屬性分別為小波變換圖像的方差、小波變換圖像的偏度、小波變換圖像的峰度以及圖像熵。圖4為部分數(shù)據(jù)集的數(shù)據(jù)格式。

圖4 原始數(shù)據(jù)集部分數(shù)據(jù)

5.3 實驗過程

1）將數(shù)據(jù)集分為訓(xùn)練集和測試集

由于該數(shù)據(jù)集并沒有提供測試數(shù)據(jù)集，因此首先用Mahout提供的split方法將原始數(shù)據(jù)集分為訓(xùn)練集和測試集兩部分，其中，選擇原始數(shù)據(jù)集的20%作為測試集。

2）生成描述性文件

由圖4分析可知，描述性字符串為［4 N L］。［4 N］說明數(shù)據(jù)集前4列為連續(xù)數(shù)值型數(shù)據(jù)，L表明這一列為類別標(biāo)簽。圖5顯示了生成描述性文件的運行結(jié)果。

3）用訓(xùn)練集構(gòu)建隨機森林模型

在建樹的過程中，決策樹的個數(shù)不同，生成的隨機森林模型就不相同。本實驗分別選擇使用3棵、5棵和10棵決策樹形成隨機森林，并對生成的隨機森林模型進行比較分析。

4）用測試集評估隨機森林模型

用測試集去檢驗分別由3棵、5棵和10棵決策樹生成的隨機森林模型，結(jié)果如下。

5.4 結(jié)果分析

由圖5可知，描述性文件已經(jīng)生成且存入HDFS文件系統(tǒng)上了。從圖6、圖7和圖8可以看出測試集總記錄條數(shù)為274，即隨機從原始數(shù)據(jù)選擇20%作為測試集的數(shù)目，該結(jié)果與預(yù)先設(shè)置一致；從不同決策樹形成的隨機森林模型評估結(jié)果來看，3棵決策樹形成的隨機森林模型分類正確率為96.7153%，5棵決策樹形成的隨機森林模型分類正確率為98.5401%，而10棵決策樹形成的隨機森林模型分類正確率為98.1752%。由此可見，隨機森林模型的評估質(zhì)量非常高。此外，由該結(jié)果還能得出，隨機森林模型的評估效果并不是決策樹越多準確率就越高。

圖5 生成描述性文件運行結(jié)果信息

圖6 3棵決策樹形成的隨機森林模型評估結(jié)果運行信息

圖7 5棵決策樹形成的隨機森林模型評估結(jié)果運行信息

圖8 10棵決策樹形成的隨機森林模型評估結(jié)果運行信息

由以上三圖給出的混淆矩陣，可以得出，a、b分別表示分類結(jié)果，即a=0、b=1，代表真鈔和偽造鈔票；Classified as表示本應(yīng)該分到此類的數(shù)目，以圖6為例，分到a類的記錄條數(shù)應(yīng)該為149，但實際只分了144條記錄，即a類有5條記錄是被誤分了。因此，從混淆矩陣可以分析出哪些類別容易被誤分以及分錯的個數(shù)和其他信息等。

6 結(jié)語

本文基于Hadoop平臺實現(xiàn)了Mahout中的隨機森林算法，并利用banknote authentication數(shù)據(jù)集對生成的隨機森林模型進行效果評估。實驗結(jié)果表明，利用隨機森林算法對該數(shù)據(jù)集進行分類，準確率高達96%以上，說明了隨機森林模型分類精確度較高、性能較穩(wěn)定。此外，本實驗還選取了不同決策樹的個數(shù)以生成不同的隨機森林模型并分別進行驗證，結(jié)果表明隨機森林算法的魯棒性較高、分類效果較好。

但是，本文也存在一定的不足。從隨機森林模型的評估效果來看，分類準確率基本上都在96%以上，這與原始數(shù)據(jù)集的數(shù)據(jù)模式簡單、數(shù)據(jù)特征質(zhì)量高有一定的關(guān)系。因此，下一步，還將針對包含較多特征屬性及數(shù)據(jù)有一定缺失值的數(shù)據(jù)集展開針對性研究，以期對Mahout中的隨機森林算法的效果做出更進一步的評估。