曹蒙蒙 郭朝有

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

1 引言

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

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

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

2 Hadoop簡介

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

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

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

3 隨機(jī)森林算法

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

3.1 決策樹

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

熵的計(jì)算公式如（1）所示：

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

增益的計(jì)算公式如（2）所示：

3.2 隨機(jī)森林算法工作原理

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

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

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

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

圖2 隨機(jī)森林算法形成流程圖

4.1 生成描述性文件

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

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

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

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

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

4.3 評(píng)估隨機(jī)森林模型

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

5 實(shí)驗(yàn)及結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境搭建及部署

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

1）硬件環(huán)境

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

圖3 隨機(jī)森林模型評(píng)估流程圖

2）軟件環(huán)境

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

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

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

表2 實(shí)驗(yàn)環(huán)境硬件配置

表3 實(shí)驗(yàn)環(huán)境軟件配置

5.2 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

5.3 實(shí)驗(yàn)過程

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顯示了生成描述性文件的運(yùn)行結(jié)果。

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

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

4）用測試集評(píng)估隨機(jī)森林模型

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

5.4 結(jié)果分析

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

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

圖6 3棵決策樹形成的隨機(jī)森林模型評(píng)估結(jié)果運(yùn)行信息

圖7 5棵決策樹形成的隨機(jī)森林模型評(píng)估結(jié)果運(yùn)行信息

圖8 10棵決策樹形成的隨機(jī)森林模型評(píng)估結(jié)果運(yùn)行信息

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

6 結(jié)語

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

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