Spark MLlib中決策樹算法不同特征選擇標(biāo)準(zhǔn)比較

杜小芳，陳毅紅

(1.西華師范大學(xué) 計算機學(xué)院，四川 南充 637002；2.物聯(lián)網(wǎng)感知與大數(shù)據(jù)分析南充市重點實驗室，四川 南充 637002)

0 引言

Apache Spark是一個開源分布式數(shù)據(jù)處理平臺，使用分布式內(nèi)存抽象來高效地處理海量數(shù)據(jù).Spark MLlib[1]是Spark的組件之一，其中包含了許多機器學(xué)習(xí)算法，如決策樹[2]、k-meas、隨機森林、SVM和協(xié)同過濾等.決策樹算法根據(jù)應(yīng)用環(huán)境不同大致可以分為兩大類，一類是模糊決策樹算法[3]，這類算法將模糊集理論和決策樹算法相結(jié)合并將其應(yīng)用到模糊領(lǐng)域中.Chang R L P等人提出了FDT算法，該算法證明了模糊決策樹算法在分類方面表現(xiàn)良好.另一類是清晰決策樹算法[4],此類算法的特征分裂標(biāo)準(zhǔn)使用信息熵或者基尼指數(shù)，如ID3[5]、C4.5[6]和CART[7]，該類算法被廣泛應(yīng)用于醫(yī)療安全、入侵檢測和食品衛(wèi)生等領(lǐng)域.在大數(shù)據(jù)時代，大部分研究領(lǐng)域使分類精度保持在可以接受的范圍內(nèi)主要追求模型訓(xùn)練效率，但某些對精度要求較高的領(lǐng)域會更傾向于追求分類精度而不是效率.因此本文通過對比Spark-MLlib 中分類決策樹實現(xiàn)的兩種方法，來研究面對不同規(guī)模數(shù)據(jù)，在保持訓(xùn)練效率的情況下，哪種算法的模型分類精度更高.

1 基礎(chǔ)概念

1.1 決策樹

決策樹是一種樹形結(jié)構(gòu)，如圖1所示，由根節(jié)點、父節(jié)點、子節(jié)點、葉節(jié)點構(gòu)成.在理想狀態(tài)下，每個葉節(jié)點都表示一個無法再繼續(xù)切分的數(shù)據(jù)集合，即葉子節(jié)點只表示眾多分類中的一類.但在現(xiàn)實世界中，每次分割后不可能得到那么純的數(shù)據(jù).因此，決策樹算法也是一種貪心策略，力求在每一次子節(jié)點完成分裂后，其中的數(shù)據(jù)比上一次更純.決策樹的構(gòu)建首先從根節(jié)點開始，把訓(xùn)練數(shù)據(jù)集S除目標(biāo)屬性外的各屬性列看作根節(jié)點.然后，遍歷每個屬性的所有分裂方式，選取其中信息熵值或基尼值最小的分裂點作為待分裂點.列出所有屬性列的待分裂點，再進(jìn)行比較，選出其中信息增益最大或者基尼指數(shù)最小的待分裂點.最后以其所在的屬性作為當(dāng)前樹深度的樹節(jié)點來劃分?jǐn)?shù)據(jù)集.更新數(shù)據(jù)并重復(fù)上述步驟，直到當(dāng)前節(jié)點中的實例數(shù)小于某個閾值時停止.

1.2 Spark MLlib

Spark是目前大數(shù)據(jù)領(lǐng)域中常用的分布式處理框架，以有向無環(huán)圖(DAG)和彈性分布式數(shù)據(jù)集(RDD)為核心.MLlib是Spark中提供機器學(xué)習(xí)算法的庫，并利用Spark自身特性為這些算法提供了分布式實現(xiàn).首先把數(shù)據(jù)以RDD的形式表示，然后在分布式數(shù)據(jù)集上調(diào)用各種算法.機器學(xué)習(xí)的模型訓(xùn)練過程一般為：接受RDD中的LabeledPoint數(shù)據(jù)作為輸入，調(diào)用相應(yīng)的算法生成模型，利用生成的模型進(jìn)行預(yù)測.在Spark MLlib中，決策樹被認(rèn)為是不采取特征抽樣的隨機森林中只包含一顆樹的特殊情況.所以訓(xùn)練決策樹也就是訓(xùn)練隨機森林模型，最后從隨機森林中抽出一棵樹.

圖1 決策樹

2 算法相關(guān)數(shù)學(xué)原理

信息墑和基尼值都是衡量樣本集合純度的指標(biāo)，假設(shè)當(dāng)前有訓(xùn)練數(shù)據(jù)集S，S中第k類樣本所占比例為pk(k=1,2,...,x)，則數(shù)據(jù)集S的信息熵和基尼指數(shù)分別定義為：

(1)

(2)

對于同一個二元分裂，熵和基尼系數(shù)的關(guān)系如圖2所示.

圖2 熵和基尼系數(shù)的關(guān)系

2.1 ID3算法

ID3算法使用信息增益來劃分訓(xùn)練數(shù)據(jù)集.首先根據(jù)信息熵來選擇最佳特征，信息熵的值越小，則樣本集的純度越高，然后根據(jù)信息增益最大原則來選擇最優(yōu)切分點.ID3算法只能處理離散屬性，所以對于連續(xù)屬性，Spark MLlib會對其進(jìn)行箱化處理，把連續(xù)屬性離散化.該算法建立的樹模型是多類樹，并且在特征選擇時會偏向?qū)傩灾递^多的特征，其后的C4.5算法通過使用信息增益比來彌補了該缺陷.但Spark Mllib中決策樹API默認(rèn)使用的是ID3算法，因此本文在訓(xùn)練決策樹模型時，使用的是信息增益來作為分裂準(zhǔn)則.樣本集S的信息增益定義為：

(3)

其中a表示離散屬性并且有V個可能取值{a1,a2,…,aV}

2.2 CART算法

CART算法訓(xùn)練的模型是二叉分類回歸樹，在本文中用作分類模型.該算法使用基尼指數(shù)來劃分訓(xùn)練數(shù)據(jù)集，在選擇最優(yōu)特征和最佳分裂點時，根據(jù)基尼指數(shù)值最小原則來選擇.樣本集S的基尼指數(shù)定義為：

(4)

其中v(0

3 實驗

3.1 環(huán)境準(zhǔn)備

本文實驗在虛擬機Ubuntu5.4中搭建的Spark偽分布式環(huán)境中進(jìn)行，該環(huán)境由一個主節(jié)點和兩個從節(jié)點組成，每個節(jié)點的配置為8核Intel(R) Core(TM)@ 3.00GHz和4GB內(nèi)存.實驗環(huán)境所采用的軟件版本為：Hadoop 2.6.4、Spark 1.6.0和Scala 2.10.4，實驗所用數(shù)據(jù)來自UCI機器學(xué)習(xí)庫[8]并作做了數(shù)據(jù)清洗及標(biāo)準(zhǔn)化處理，如表1所示.

表1 數(shù)據(jù)集

3.2 實驗結(jié)果

本實驗進(jìn)行時，規(guī)定了樹的最大深度為8，最大箱化數(shù)為32.實驗結(jié)果表明使用gini和entropy兩種方法訓(xùn)練模型的時間差距很小，都保持了訓(xùn)練效率.原因在于雖然使用gini訓(xùn)練模型時不像entropy需要做對數(shù)運算，理論上使用gini的訓(xùn)練效率應(yīng)高于使用entropy.但由于Spark自身特性，其擁有強大高速的計算處理能力，在樹模型訓(xùn)練過程中是否有對數(shù)運算對其而言，差距幾乎可以忽略不計.表2記錄了使用基尼指數(shù)和信息熵兩種分裂標(biāo)準(zhǔn)訓(xùn)練決策樹模型時，兩種方法在8個數(shù)據(jù)集上的平均分類精度.從表中所示數(shù)據(jù)來看，對于小數(shù)據(jù)集，使用基尼指數(shù)來劃分訓(xùn)練數(shù)據(jù)集得到的模型其分類精度和使用信息熵訓(xùn)練所得模型的分類精度的差距不大.隨著數(shù)據(jù)規(guī)模增大，使用信息熵作為劃分準(zhǔn)則其模型分類精度高于使用基尼指數(shù)訓(xùn)練的模型的分類精度，提高了約0.2.

表2 平均分類精度

圖3 平均分類精度

我們使用數(shù)據(jù)集Machine Stoppage來驗證使用ID3和CART兩種算法在不同樹深度時的分類精度，實驗結(jié)果如圖3所示.在保持訓(xùn)練效率的情況下，隨著樹深度的不斷增加，使用ID3算法的分類精度始終高于CART算法的分類精度.

4 總結(jié)

本文通過實驗來對比Spark MLlib中決策樹算法的兩種實現(xiàn)方式，實驗結(jié)果表明：在保持訓(xùn)練效率的情況下，隨著數(shù)據(jù)規(guī)模增大，使用信息熵劃分訓(xùn)練數(shù)據(jù)集所得模型的分類精度高于使用基尼系數(shù).這對于某些對精度要求較高的領(lǐng)域來說，在進(jìn)行大規(guī)模數(shù)據(jù)分析建立樹模型時，此實驗結(jié)果可以為其提供參數(shù)選擇參考，減少其工作量.