大數(shù)據(jù)環(huán)境下決策樹(shù)的研究

鄧曉林，陳毅紅，王登輝

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

0 引言

近年來(lái)，IT技術(shù)、網(wǎng)絡(luò)、可穿戴設(shè)備的迅速發(fā)展，為互聯(lián)網(wǎng)網(wǎng)民在社交媒體、物聯(lián)網(wǎng)、各種應(yīng)用程序的使用打下了良好的基礎(chǔ).網(wǎng)民可以隨時(shí)隨地流暢地使用各種應(yīng)用程序，這給生活帶來(lái)了方方面面的便利，但便利的同時(shí)，網(wǎng)絡(luò)數(shù)據(jù)量每天以TB、PB級(jí)增加，引起了數(shù)據(jù)量的暴漲.數(shù)據(jù)量的暴漲，使互聯(lián)網(wǎng)進(jìn)入了大數(shù)據(jù)時(shí)代.各行各業(yè)的應(yīng)用程序?qū)?shù)據(jù)進(jìn)行實(shí)時(shí)存儲(chǔ)與響應(yīng)，表明大數(shù)據(jù)具有實(shí)時(shí)性、多樣性（音頻、視頻、文本、圖片、語(yǔ)音等）、異構(gòu)性、數(shù)據(jù)關(guān)系復(fù)雜性、信息量少的特點(diǎn).基于大數(shù)據(jù)集的這些特點(diǎn)，怎樣快、穩(wěn)、準(zhǔn)、有效地進(jìn)行分析與預(yù)測(cè)，是現(xiàn)在大數(shù)據(jù)和人工智能研究的重要領(lǐng)域.

在大數(shù)據(jù)時(shí)代最根本的挑戰(zhàn)是在海量的數(shù)據(jù)中分析出有價(jià)值的信息為下一步行動(dòng)提供參考.在大多數(shù)情況下，大數(shù)據(jù)的分析過(guò)程必須非常高效且接近實(shí)時(shí)，因?yàn)橛脩艨扇淌艿臅r(shí)間非常短已近似實(shí)時(shí).為了實(shí)現(xiàn)大數(shù)據(jù)的快速響應(yīng)和實(shí)時(shí)分類(lèi)，需要使用到高效的數(shù)據(jù)分析算法和高效的應(yīng)用平臺(tái).

目前分類(lèi)算法可以分為有監(jiān)督和無(wú)監(jiān)督.無(wú)監(jiān)督學(xué)習(xí)算法是通過(guò)算法把不知道分類(lèi)標(biāo)簽的樣本，把相似的樣本歸為一類(lèi).監(jiān)督學(xué)習(xí)算法是先訓(xùn)練帶有屬性標(biāo)簽的樣本，再預(yù)測(cè)不具有屬性標(biāo)簽樣本的分類(lèi)情況.監(jiān)督學(xué)習(xí)算法中常用的有決策樹(shù)、KNN等，其中最具代表性的是決策樹(shù)，因?yàn)楹?jiǎn)單易學(xué)、準(zhǔn)確率高等特點(diǎn)備受關(guān)注.決策樹(shù)根據(jù)屬性標(biāo)簽是否確定，分為清晰決策樹(shù)和模糊決策樹(shù).清晰決策樹(shù)代表標(biāo)簽是明確，最典型是ID3、C4.5、CART、SLIQ和SPRINT.為了適應(yīng)不確定、模糊環(huán)境，衍生了模糊決策樹(shù)，具有代表性的是模糊ID3算法.傳統(tǒng)決策樹(shù)只能應(yīng)用于中小型數(shù)據(jù)集，具有一定局限性，所以有必要基于大數(shù)據(jù)分布式平臺(tái)對(duì)決策樹(shù)進(jìn)行深入研究.Hadoop和Spark的分布式并行化平臺(tái)，可以支持大數(shù)據(jù)集的運(yùn)算與處理，尤其是分布式集群方式，提高了算法的計(jì)算效率，為大數(shù)據(jù)的實(shí)時(shí)分析和預(yù)測(cè)提供了可能性.本文結(jié)構(gòu)主要從以下三個(gè)方面進(jìn)行深入分析：首先系統(tǒng)介紹決策樹(shù)及各類(lèi)決策樹(shù)算法原理；其次，分析Hadoop和Spark平臺(tái)下的分布式并行運(yùn)算機(jī)制；最后從分布式?jīng)Q策樹(shù)算法優(yōu)化、平臺(tái)并行機(jī)制方面深入分析大數(shù)據(jù)平臺(tái)Hadoop和Spark下的分布式?jīng)Q策樹(shù)的現(xiàn)狀，為未來(lái)大數(shù)據(jù)平臺(tái)下分布式?jīng)Q策樹(shù)研究提供方向.

1 決策樹(shù)基礎(chǔ)算法

1.1 清晰決策樹(shù)

決策樹(shù)是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域里非常有用的工具.它于1982年被提出，不僅應(yīng)用領(lǐng)域廣泛，比如被應(yīng)用于醫(yī)療衛(wèi)生［1］、故障預(yù)測(cè)［2］、入侵檢測(cè)［3］、目標(biāo)追蹤［4］、食品安全［5］等領(lǐng)域，而且易于理解和使用.決策樹(shù)根據(jù)分類(lèi)是否明確分為清晰決策樹(shù)和模糊決策樹(shù)［6］.決策樹(shù)通過(guò)訓(xùn)練數(shù)據(jù)集進(jìn)行學(xué)習(xí)，得出一棵自頂向下的樹(shù)模型，再將測(cè)試數(shù)據(jù)應(yīng)用于這棵樹(shù)模型得出預(yù)測(cè)分類(lèi)結(jié)果［7］.這是一個(gè)包含根節(jié)點(diǎn)、中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)的二叉樹(shù)模型，每個(gè)節(jié)點(diǎn)根據(jù)每個(gè)屬性的分裂標(biāo)準(zhǔn)進(jìn)行判斷和選擇，葉子節(jié)點(diǎn)是樣本的最終分類(lèi)類(lèi)別，如圖1.從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)完全可以解釋數(shù)據(jù)分類(lèi)，所以決策樹(shù)最具解釋性.

圖1 二叉決策樹(shù)

清晰決策樹(shù)的屬性值和分類(lèi)值都是確定的.通常一顆決策樹(shù)的構(gòu)建需要幾個(gè)步驟：數(shù)據(jù)準(zhǔn)備，即將整個(gè)數(shù)據(jù)集基于一定規(guī)則劃分成兩個(gè)子數(shù)據(jù)集；其次由其中一個(gè)子數(shù)據(jù)集，構(gòu)建出一顆決策樹(shù)，再將另一個(gè)子數(shù)據(jù)集應(yīng)用于已構(gòu)建的決策樹(shù)預(yù)測(cè)分類(lèi)結(jié)果；最后根據(jù)生成的分類(lèi)結(jié)果與數(shù)據(jù)集的原有分類(lèi)結(jié)果進(jìn)行比較，計(jì)算出所構(gòu)建決策樹(shù)的分類(lèi)精度.構(gòu)建決策樹(shù)時(shí)最重要的環(huán)節(jié)是對(duì)屬性分裂節(jié)點(diǎn)的選擇.目前主要的分裂節(jié)點(diǎn)標(biāo)準(zhǔn)有信息增益、信息增益率和Gini指數(shù).根據(jù)節(jié)點(diǎn)不同的分裂標(biāo)準(zhǔn)可以構(gòu)建不同決策樹(shù).目前也針對(duì)已有的這些決策樹(shù)提出了各種不同優(yōu)化算法.

1.1.1 信息增益

Quinlan提出了一種以信息增益作為特征分裂準(zhǔn)則構(gòu)建樹(shù)模型的ID3［8］算法.ID3的核心是基于香農(nóng)公式中的信息熵.在構(gòu)建ID3決策樹(shù)時(shí)，首先需要計(jì)算各個(gè)屬性的信息熵，再計(jì)算各個(gè)屬性的信息增益，把信息增益最高的屬性作為節(jié)點(diǎn)分裂的標(biāo)準(zhǔn).假設(shè)樣本數(shù)據(jù)集X，這些樣本有m個(gè)不同標(biāo)簽類(lèi)別Ci（i=1，2，3，…，m），則目標(biāo)類(lèi)別熵為：

條件熵為：

當(dāng)屬性x在標(biāo)簽確定條件下的條件熵，屬性x的信息增益為：

ID3算法理論清晰，使用簡(jiǎn)單，但也存在一些缺點(diǎn)，比如：邏輯表達(dá)能力差、計(jì)算量大、分類(lèi)偏向?qū)傩灾刀嗟臉颖镜?針對(duì)這些缺陷，提出了一些優(yōu)化的ID3決策樹(shù)算法.ID3根據(jù)信息增益構(gòu)建樹(shù)，僅僅考慮單層節(jié)點(diǎn)，當(dāng)出現(xiàn)較多節(jié)點(diǎn)時(shí)，邏輯表達(dá)能力較差.針對(duì)ID3表達(dá)能力差問(wèn)題，提出MID3［9］，該算法提出需考慮兩層節(jié)點(diǎn)的信息增益包括當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)之后的一個(gè)節(jié)點(diǎn)［9］.MID3［9］算法的優(yōu)化只考慮了離散型屬性，還需要進(jìn)一步針對(duì)連續(xù)型屬性進(jìn)行驗(yàn)證.ID3與K-Means方法結(jié)合，解決了K類(lèi)均值的K的取值問(wèn)題［10］.針對(duì)ID3不能處理離散屬性，并且構(gòu)建決策樹(shù)時(shí)常偏向多值屬性的問(wèn)題提出了一些改進(jìn)算法：AR-KOS算法［11］、熵值計(jì)算中引入權(quán)重值［12］、信息增益率［13］.

1.1.2 信息增益率

C4.5［14］是一種以信息增益率作為特征分裂標(biāo)準(zhǔn)的決策樹(shù)，是ID3的一種進(jìn)化.C4.5算法可以處理數(shù)字型屬性，也能處理分類(lèi)型屬性，同時(shí)還解決了屬性缺省值問(wèn)題.

數(shù)據(jù)集S，特征屬性A，則屬性分裂信息公式為：

Si代表特征屬性分割后的子數(shù)據(jù)集，則信息增益率公式為：

C4.5算法存在一些缺點(diǎn)：數(shù)字型屬性離散化時(shí)比較耗時(shí)、整個(gè)數(shù)據(jù)集信息增益率計(jì)算量大、節(jié)點(diǎn)分裂后數(shù)據(jù)量減小呈碎片化后導(dǎo)致過(guò)擬合.針對(duì)C4.5這些缺陷提出了一些優(yōu)化方法.

劉鵬［15］等針對(duì)決策樹(shù)的空支與無(wú)意義支導(dǎo)致的過(guò)擬合問(wèn)題，提出在離散屬性上使用修正的信息增益的R-C4.5決策樹(shù)模型.實(shí)驗(yàn)結(jié)果表明R-C4.5模型一定程度上解決了過(guò)擬合問(wèn)題，提高了準(zhǔn)確率.周劍峰［16］等提出采用數(shù)學(xué)公式里的等價(jià)無(wú)窮小理論代替基于對(duì)數(shù)運(yùn)算的信息增益率的改進(jìn)C4.5算法.實(shí)驗(yàn)表明該方式降低了計(jì)算量，加快了生成決策樹(shù)速度，提高了效率，但其中的優(yōu)化熵代替平均信息熵進(jìn)行計(jì)算的方式并沒(méi)有明顯提高預(yù)測(cè)分類(lèi)的精度.針對(duì)通過(guò)對(duì)數(shù)運(yùn)算方式計(jì)算信息增益率耗時(shí)比較長(zhǎng)問(wèn)題，引用麥克勞公式和泰勒公式思想，使用簡(jiǎn)單運(yùn)算替換對(duì)數(shù)計(jì)算方式，提高了效率，也保證了預(yù)測(cè)分類(lèi)的準(zhǔn)確率［17］.對(duì)連續(xù)屬性離散化時(shí)采用Fayyad和Irani的邊界定理，解決離散化比較耗時(shí)問(wèn)題；離散化后節(jié)點(diǎn)分裂標(biāo)準(zhǔn)采用Gini指標(biāo)，并通過(guò)再帶入估計(jì)算法，解決了決策樹(shù)過(guò)擬合問(wèn)題，實(shí)驗(yàn)結(jié)果表明該優(yōu)化在模型復(fù)雜度上有所下降［18］.

1.1.3 Gini指數(shù)

Gini指數(shù)代表屬性分類(lèi)不確定性，其值越小，代表不確定越低，即作為選擇最優(yōu)特征的標(biāo)準(zhǔn).將Gini指數(shù)替換了原來(lái)的熵值計(jì)算，解決了對(duì)數(shù)復(fù)雜的計(jì)算，使運(yùn)算變?yōu)楹?jiǎn)單的加減乘除，大大提高了計(jì)算效率.基于Gini指數(shù)作為屬性分裂標(biāo)準(zhǔn)的決策樹(shù)有CART、SLIQ和SPRINT.Gini公式如下（6），Pi代表了樣本屬于i類(lèi)別的概率，樣本被錯(cuò)分的概率為1-Pi.

CART［19］算法是一種分類(lèi)回歸二叉決策樹(shù)，即當(dāng)使用某個(gè)特征進(jìn)行樣本劃分，只能劃分為兩個(gè)集合：等于給定樣本特征的集合、不等于給定樣本特征的集合.其中S為樣本數(shù)據(jù)集，S1和S2為子樣本集：

針對(duì)CART算法不能處理遞增式數(shù)據(jù)，引入了遞增式學(xué)習(xí)里的測(cè)試函數(shù)提升思想，從實(shí)驗(yàn)表明確實(shí)證明了其準(zhǔn)確性和有效性，但該算法也有些局限性，需要對(duì)參數(shù)不斷進(jìn)行設(shè)置嘗試，不具有普遍推廣性［20］.對(duì)連續(xù)屬性劃分區(qū)域計(jì)算分裂值的離散化方式降低了計(jì)算頻次.改進(jìn)后的CART算法針對(duì)連續(xù)屬性的離散化采用了Fayyad邊界定理［21］，實(shí)驗(yàn)表明該方法改進(jìn)在準(zhǔn)確率方面得到大大提升［22］.為了降低CART決策樹(shù)誤判率，通過(guò)剪枝改進(jìn)了CART決策樹(shù)，分別有CCP剪枝和AIC剪枝算法.實(shí)驗(yàn)表明通過(guò)AIC剪枝不僅提高了準(zhǔn)確率而且具有良好的擴(kuò)展性［23］.

傳統(tǒng)決策樹(shù)在處理大數(shù)據(jù)時(shí)，可能會(huì)出現(xiàn)精度下降或者性能下降的問(wèn)題，IBM提出了基于內(nèi)存讀取的SLIQ［24］算法，它也是一種基于Gini指數(shù)作為屬性分裂標(biāo)準(zhǔn)的決策樹(shù).該算法是一種快速、可伸縮并且能處理大數(shù)據(jù)的算法.SLIQ是以屬性表、內(nèi)表和直方圖作為其數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)預(yù)處理階段需要屬性值進(jìn)行預(yù)排序，構(gòu)建決策樹(shù)時(shí)結(jié)合寬度優(yōu)先增長(zhǎng)策略，最后剪枝時(shí)采用最小描述長(zhǎng)度原則（MDLP），實(shí)驗(yàn)表明這種方式提高了效率［24］.但SLIQ算法存儲(chǔ)類(lèi)表的內(nèi)存有限，也就決定了單機(jī)環(huán)境下是不適合處理大數(shù)據(jù)集的.

SPRINT［25］也是以Gini指數(shù)作為屬性分裂標(biāo)準(zhǔn)，是基于SLIQ算法優(yōu)化而來(lái)的一種算法.由于單機(jī)內(nèi)存有限，它去掉了SLIQ的數(shù)據(jù)結(jié)構(gòu)中的類(lèi)別列表結(jié)構(gòu)，節(jié)約了內(nèi)存.針對(duì)SPRINT算法在尋找最佳分割點(diǎn)時(shí)涉及計(jì)算量極大問(wèn)題，學(xué)術(shù)界提出了一些優(yōu)化方法.劉友軍等［26］提出將數(shù)值型區(qū)間分割為純區(qū)間和非純區(qū)間，純區(qū)間即已確定分類(lèi)的進(jìn)行規(guī)約，不純區(qū)間即需要精確計(jì)算，明顯減少了計(jì)算量也得到了相應(yīng)的準(zhǔn)確率，但不足之處就是對(duì)所劃分區(qū)間進(jìn)行整體性的掃描需要消耗相當(dāng)一部分時(shí)間.彭程等［27］提出根據(jù)如果連續(xù)屬性表中確定分割點(diǎn)v的兩個(gè)元祖的類(lèi)別相同，至少存在另一個(gè)分割點(diǎn)的V1求得最小分割點(diǎn)，但這種方式只是通過(guò)減少分割點(diǎn)數(shù)目而達(dá)到提高效率目的.

1.2 模糊決策樹(shù)

模糊決策樹(shù)結(jié)合了模糊集理論，適應(yīng)了不確定性的環(huán)境，增強(qiáng)了決策樹(shù)的應(yīng)用性，也是清晰決策樹(shù)的一種推廣.在模糊決策樹(shù)中最經(jīng)典的是基于ID3的模糊決策樹(shù).模糊決策樹(shù)最開(kāi)始是通過(guò)ID3與模糊集理論結(jié)合，應(yīng)用到分析石油中的氣體來(lái)分析電勢(shì)變壓器，取得一定效果［28］.模糊決策樹(shù)構(gòu)建時(shí)，首先通過(guò)隸屬函數(shù)對(duì)屬性進(jìn)行模糊化，再對(duì)模糊化的屬性計(jì)算模糊信息熵和模糊信息增益，選取模糊信息增益最大值作為模糊決策樹(shù)節(jié)點(diǎn)分裂標(biāo)準(zhǔn).目前主要是三角形、梯形和高斯隸屬函數(shù)，最典型的是三角隸屬函數(shù)，公式如下：

在三角隸屬度函數(shù)時(shí)，需要將數(shù)據(jù)集（x）劃分為幾個(gè)數(shù)據(jù)區(qū)域，a、b、c分別為數(shù)據(jù)集邊界，參數(shù)b為最高點(diǎn)，參數(shù)a、c為三角形的下方的左右兩個(gè)點(diǎn).

1.2.1 模糊ID3決策樹(shù)

模糊ID3決策樹(shù)是把ID3算法應(yīng)用到了模糊環(huán)境的融合模型，比如：吉林豐滿水電數(shù)字仿真系統(tǒng)的考核系統(tǒng)，既分析處理了大數(shù)據(jù)問(wèn)題，又解決了不確定性數(shù)據(jù)的問(wèn)題［29］.

模糊ID3需要使用模糊屬性和模糊標(biāo)簽屬性，所以在數(shù)據(jù)預(yù)處理階段需要對(duì)屬性進(jìn)行模糊化.針對(duì)模糊化時(shí)有可能會(huì)損失有用信息，翟俊海［30］等提出了一種結(jié)合模糊粗糙集技術(shù)的模糊決策樹(shù)歸納算法（RFDT），它直接處理不需要模糊化，仍然把Kosko模糊熵作為終止條件，沒(méi)有信息丟失.RFDT算法的模糊熵定義為：

F是定義在論域U上的模糊集，其中Fc是F的模糊補(bǔ)集.這一方法是否對(duì)連續(xù)型屬性有相關(guān)影響后續(xù)還待驗(yàn)證.針對(duì)模糊決策樹(shù)在進(jìn)行數(shù)據(jù)模糊化可能丟失有用信息提出了容差粗糙模糊集（TRFDT）［31］，它可以直接利用連續(xù)型屬性和模糊值的模糊決策表生成模糊決策樹(shù)，也是利用了Kosko模糊熵作為終止條件，仿真結(jié)果表明該算法不僅學(xué)習(xí)速度快，而且收斂性和泛化能力都比較強(qiáng)，但也只是理論上得到證實(shí)，具體實(shí)際應(yīng)用還需要進(jìn)一步驗(yàn)證.

在處理不均衡數(shù)據(jù)時(shí)，采用猶豫模糊集理論結(jié)合模糊ID3算法，因?yàn)樵谀：镫`屬度只能取一個(gè)值，但在真實(shí)案例處理時(shí)隸屬度可能取多個(gè)值.針對(duì)這一情況采用猶豫模糊集，構(gòu)建決策樹(shù)時(shí)，首先對(duì)數(shù)據(jù)集進(jìn)行模糊化，其次計(jì)算隸屬度，再計(jì)算出模糊熵、模糊信息增益和猶豫模糊信息增益，但該方法在處理二分類(lèi)性能良好，但是沒(méi)有對(duì)多分類(lèi)問(wèn)題進(jìn)行驗(yàn)證［32］.

1.2.2 其他模糊決策樹(shù)

與模糊ID3算法相比使用分類(lèi)歧義來(lái)選擇模糊決策樹(shù)的根節(jié)點(diǎn)處的拆分屬性，并使用信息增益來(lái)選擇其他樹(shù)節(jié)點(diǎn)中的拆分屬性，實(shí)驗(yàn)結(jié)果表明該方法具有更高效率［33］.Chandra等［34］提出模糊SLIQ決策樹(shù)算法FS-DT，通過(guò)構(gòu)造模糊二進(jìn)制決策樹(shù)，決策樹(shù)的規(guī)模變小，在效率上提高了74%，但是在精確率上提高的比較少，因?yàn)椴眉袅瞬糠种虚g節(jié)點(diǎn).

2 大數(shù)據(jù)平臺(tái)

2.1 Hadoop分布式計(jì)算框架

大數(shù)據(jù)時(shí)代背景下需要對(duì)大數(shù)據(jù)集進(jìn)行實(shí)時(shí)存儲(chǔ)與響應(yīng)，包含文件存儲(chǔ)和計(jì)算兩個(gè)部分.Hadoop［35］是一個(gè)生態(tài)圈，它主要包含的組件Common、Hive、HDFS、YARN、MapReduce等.Hadoop集群采用主從（Master／Slave）模式，其中Master（即NameNode）節(jié)點(diǎn)在集群中只有一個(gè)，而Slave（即DataNode）節(jié)點(diǎn)在集群中可以有多個(gè).分布式文件管理系統(tǒng)（HDFS）和分布式計(jì)算框架（MapReduce）有效地解決了大數(shù)據(jù)的實(shí)時(shí)存儲(chǔ)與計(jì)算問(wèn)題.

分布式文件管理系統(tǒng)（HDFS）采用主從集群模式，其中NameNode主要是管理分布式文件管理系統(tǒng)，DataNode節(jié)點(diǎn)主要是對(duì)文件進(jìn)行存儲(chǔ)與分析.數(shù)據(jù)從HDFS系統(tǒng)讀取到NameNode節(jié)點(diǎn)后，需要對(duì)數(shù)據(jù)進(jìn)行分塊，并將不同分塊分配到不同的DataNode節(jié)點(diǎn)，通過(guò)這種方式，一個(gè)大數(shù)據(jù)文件就會(huì)被分成多個(gè)小數(shù)據(jù)文件存儲(chǔ)在不同機(jī)器，從而達(dá)到分布式文件的存儲(chǔ).

MapReduce［36］是Hadoop分布式集群計(jì)算框架的核心，它最早由Google公司提出并實(shí)現(xiàn).MapReduce封裝了對(duì)用戶來(lái)說(shuō)比較復(fù)雜的細(xì)節(jié)，用戶調(diào)用接口即可應(yīng)用，所以編碼和部署會(huì)變得簡(jiǎn)單高效.MapReduce包含Map和Reduce兩部分，用戶只需要處理好Map和Reduce階段即可實(shí)現(xiàn)對(duì)海量數(shù)據(jù)的并行處理［37］.當(dāng)數(shù)據(jù)被分成多個(gè)小塊并分配到不同節(jié)點(diǎn)時(shí)，只需要讀取當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)執(zhí)行Map和Reduce任務(wù)，當(dāng)所有節(jié)點(diǎn)的計(jì)算完成后，再對(duì)所有節(jié)點(diǎn)進(jìn)行聚合并輸出結(jié)果.整個(gè)MapReduce過(guò)程的執(zhí)行都是并行、單獨(dú)的運(yùn)行，以此實(shí)現(xiàn)了分布式計(jì)算，提高了效率.

Hadoop平臺(tái)基于MapReduce框架具有很強(qiáng)的分布式可操作性，但將所有的操作都抽象為Map和Reduce任務(wù)，具有一定的局限性，為后面Spark的提出奠定了基礎(chǔ).

2.2 Spark分布式計(jì)算框架

Spark［38］是Hadoop的進(jìn)化版本，繼承了Hadoop的優(yōu)點(diǎn)，也優(yōu)化了MapReduce缺陷，比如Hadoop頻繁進(jìn)行讀取I／O、節(jié)點(diǎn)通信等.Spark是基于內(nèi)存進(jìn)行計(jì)算，隨時(shí)讀取，降低延遲，提高效率，也減少了磁盤(pán)開(kāi)銷(xiāo).Spark的核心是基于RDD彈性數(shù)據(jù)集進(jìn)行操作，而DAG有向無(wú)環(huán)圖則記錄了RDD數(shù)據(jù)集的來(lái)龍去脈，若RDD數(shù)據(jù)丟失或出錯(cuò)，可以根據(jù)DAG圖重建RDD，無(wú)需重頭開(kāi)始，提高了容錯(cuò)性.Spark不僅有Hadoop里面的Map和Reduce操作，還有Transformation和Action操作.Transformation主要是對(duì)Spark里特有的RDD彈性數(shù)據(jù)集之間進(jìn)行變換操作，而Action則是操作RDD得到一個(gè)數(shù)據(jù)結(jié)果，具有較高的通用性.

在Spark分布式計(jì)算框架上，RDD是核心，而且整個(gè)框架的并行性是通過(guò)RDD實(shí)現(xiàn)分布式的.在Spark平臺(tái)上，首先RDD讀取數(shù)據(jù)集，根據(jù)按行分區(qū)規(guī)則對(duì)數(shù)據(jù)集進(jìn)行分區(qū)，每個(gè)分區(qū)包含一定量的子數(shù)據(jù)集，最后將每個(gè)分區(qū)分布到集群節(jié)點(diǎn)，由此可見(jiàn)每個(gè)分區(qū)是獨(dú)立、并行運(yùn)行的，從而實(shí)現(xiàn)集群的并行計(jì)算，如圖2.

圖2 Spark的分布式并行圖

3 基于大數(shù)據(jù)平臺(tái)的決策樹(shù)

決策樹(shù)因其預(yù)測(cè)分類(lèi)準(zhǔn)確率高、參數(shù)少、易理解的特點(diǎn)在數(shù)據(jù)挖掘領(lǐng)域占據(jù)重要位置.傳統(tǒng)決策樹(shù)的實(shí)現(xiàn)是在單機(jī)上對(duì)屬性進(jìn)行反復(fù)迭代的計(jì)算過(guò)程，但單機(jī)無(wú)論在計(jì)算能力還是存儲(chǔ)能力上都比較局限，所以傳統(tǒng)決策樹(shù)已不能適應(yīng)當(dāng)今大數(shù)據(jù)集環(huán)境，繼而發(fā)展了并行決策樹(shù).并行決策樹(shù)是在單機(jī)基礎(chǔ)上使用串行的方式實(shí)現(xiàn).這種方式主要是依賴(lài)于消息傳遞，底層的代碼實(shí)現(xiàn)復(fù)雜又困難，更重要的是只能處理計(jì)算密集型問(wèn)題，不能處理數(shù)據(jù)密集型問(wèn)題，依然不能完全適應(yīng)大數(shù)據(jù)環(huán)境.Spark和Hadoop兩大主流大數(shù)據(jù)運(yùn)行平臺(tái)是通過(guò)將任務(wù)和數(shù)據(jù)進(jìn)行分塊，并將不同分塊分配到不同節(jié)點(diǎn)執(zhí)行計(jì)算任務(wù)，最后將不同結(jié)果進(jìn)行統(tǒng)計(jì)，實(shí)現(xiàn)預(yù)測(cè)分類(lèi)，整個(gè)過(guò)程即為并行分布式處理.Hadoop和Spark的這種并行分布式處理為單機(jī)并行決策樹(shù)的發(fā)展提供了契機(jī)，繼而提出了分布式?jīng)Q策樹(shù).Hadoop平臺(tái)的MapReduce和Spark的MLlib都封裝了很多API，編碼時(shí)可以直接使用，既便于管理也提高了實(shí)現(xiàn)代碼的效率.

3.1 基于Hadoop平臺(tái)的分布式?jīng)Q策樹(shù)

3.1.1 清晰分布式?jīng)Q策樹(shù)

分布式并行清晰決策樹(shù)主要是基于ID3、C4.5、CART、SPRINT等基礎(chǔ)算法的分布式，從而提高算法在大數(shù)據(jù)集上的準(zhǔn)確率和效率，但仍然還需考慮決策樹(shù)算法本身的計(jì)算復(fù)雜性、駐留內(nèi)存等特點(diǎn)進(jìn)行優(yōu)化后再實(shí)行分布式.在Hadoop的并行機(jī)制中核心是MapReduce框架，Map對(duì)數(shù)據(jù)進(jìn)行處理，經(jīng)過(guò)Shuffle后將Map階段合成的數(shù)據(jù)再經(jīng)Reduce階段進(jìn)行整合.Map是根據(jù)分區(qū)獨(dú)立并行而Reduce也是分區(qū)獨(dú)立運(yùn)行，提高了效率.

針對(duì)ID3偏向多值取向問(wèn)題，陸秋［39］等提出使用屬性相似度作為屬性選擇標(biāo)準(zhǔn)進(jìn)行優(yōu)化.屬性相似度越大，表明決策屬性與條件屬性越相似，即可作為最優(yōu)屬性分割點(diǎn).優(yōu)化后的ID3算法，通過(guò)Hadoop的Map和Reduce的并行實(shí)現(xiàn)，具體實(shí)現(xiàn)過(guò)程如下：

a.首先需要對(duì)讀取的數(shù)據(jù)集進(jìn)行分塊，并將分塊的元數(shù)據(jù)分配到不同的DataNode，而DataNode之間是獨(dú)立的，以并行的方式進(jìn)行計(jì)算處理.

b.Hadoop將為分配到每個(gè)節(jié)點(diǎn)的數(shù)據(jù)分片創(chuàng)建map任務(wù)，并以＜key，value＞形式作為輸出結(jié)果.

c.在shuffle階段對(duì)map輸出結(jié)果進(jìn)行歸并操作即對(duì)具有相同key的value進(jìn)行歸并處理，輸出＜key，value＿list（）＞.

d.Reduce任務(wù)，則是將shuffle后的＜key，value＿list（）＞形式數(shù)據(jù)進(jìn)行計(jì)算處理，最后輸出的結(jié)果就存到HDFS文件系統(tǒng).

在整個(gè)過(guò)程中不同的Map任務(wù)和Reduce任務(wù)之間不進(jìn)行通信與數(shù)據(jù)交換，即具有獨(dú)立性.基于這樣的機(jī)制，可以實(shí)現(xiàn)分布式并行模式，如圖3.實(shí)驗(yàn)將分布式ID3決策樹(shù)與非分布式?jīng)Q策樹(shù)在精確度、加速比和可擴(kuò)展性三個(gè)指標(biāo)上進(jìn)行比較分析，得出分布式ID3決策樹(shù)在這三個(gè)指標(biāo)上都有較好的表現(xiàn).

圖3 MapReduce框架下分布式?jīng)Q策樹(shù)計(jì)算圖

張晶星［40］等提出一種基于Hadoop平臺(tái)的C4.5的不確定概率誤差剪枝算法（C4.5-IEP），該算法解決了駐留內(nèi)存和剪枝問(wèn)題.首先，為了比較不同剪枝算法在處理嘈雜數(shù)據(jù)上的能力，分別在單機(jī)下對(duì)經(jīng)典的悲觀剪枝算法（PEP）、條件誤差剪枝算法（CEP）和不確定概率誤差剪枝算法（C4.5-IEP）進(jìn)行對(duì)比實(shí)驗(yàn)［40］，實(shí)驗(yàn)結(jié)果表明IEP比另外兩種算法在規(guī)模上稍小，但在三個(gè)算法準(zhǔn)確率都不理想的情況下，IEP有明顯優(yōu)勢(shì)；將C4.5-IEP應(yīng)用于MapReduce框架下進(jìn)行分布式行實(shí)驗(yàn)，并通過(guò)加速比、可擴(kuò)展性指標(biāo)進(jìn)行比較分析，表明分布式的C4.5-IEP在處理大數(shù)據(jù)集上性能有了明顯的提升［40］.黃剛［41］等將SPRINT算法應(yīng)用于Hadoop大數(shù)據(jù)計(jì)算平臺(tái)，實(shí)驗(yàn)結(jié)果從執(zhí)行效率和準(zhǔn)確率兩個(gè)指標(biāo)進(jìn)行對(duì)比分析，得出分布式SPRINT決策樹(shù)比單機(jī)下的SPRINT更有優(yōu)勢(shì).楊長(zhǎng)春［42］等提出并行SLIQ算法，由于SLIQ算法需要逐一遍歷屬性計(jì)算伸縮性指標(biāo)進(jìn)行節(jié)點(diǎn)分裂太耗時(shí).為了實(shí)現(xiàn)并行化SLIQ，首先將所有的類(lèi)表復(fù)制到每個(gè)節(jié)點(diǎn)的內(nèi)存；在樹(shù)構(gòu)建階段主要是尋找最佳分裂點(diǎn)、并根據(jù)分裂點(diǎn)創(chuàng)建新節(jié)點(diǎn)，所以需要記錄每個(gè)樣本的類(lèi)表、直方圖，根據(jù)直方圖計(jì)算Gini值，為了比較分割節(jié)點(diǎn)兩側(cè)的值，引入一個(gè)哈希表進(jìn)行存儲(chǔ)兩側(cè)數(shù)據(jù)，為并行性提高依據(jù).仿真實(shí)驗(yàn)表明并行化SLIQ具有可行性.Shivaraju［43］等提出一種基于屬性劃分的并行決策樹(shù).首先將整個(gè)數(shù)據(jù)集按照一定規(guī)則劃分為構(gòu)建決策樹(shù)的訓(xùn)練集和測(cè)試決策樹(shù)模型的測(cè)試集，再對(duì)這兩個(gè)數(shù)據(jù)集的屬性分區(qū)，每個(gè)分區(qū)至少兩列屬性，保持測(cè)試集分區(qū)數(shù)與訓(xùn)練集的分區(qū)數(shù)一致.在訓(xùn)練集上，根據(jù)每個(gè)分區(qū)生成一顆訓(xùn)練樹(shù)；根據(jù)測(cè)試集的分區(qū)結(jié)合訓(xùn)練樹(shù)生成測(cè)試樹(shù)，在生成的測(cè)試樹(shù)上，使用加權(quán)投票法，生成最終的預(yù)測(cè)分類(lèi)結(jié)果，并在Reduce階段統(tǒng)計(jì)正確率.但是實(shí)驗(yàn)只使用了小數(shù)據(jù)集，并未在大數(shù)據(jù)集上進(jìn)行驗(yàn)證.Yuan［44］等為了解決C4.5算法中信息增益率計(jì)算比較耗時(shí)問(wèn)題，提出了麥克勞林公式進(jìn)行計(jì)算信息增益，通過(guò)改進(jìn)的C4.5與傳統(tǒng)C4.5在Hadoop平臺(tái)上進(jìn)行對(duì)比實(shí)驗(yàn)，分析了他們的時(shí)間復(fù)雜度和準(zhǔn)確率，實(shí)驗(yàn)結(jié)果表明改進(jìn)C4.5具有更高的準(zhǔn)確率和效率.

3.1.2 分布式模糊決策樹(shù)

目前基于Hadoop平臺(tái)的模糊決策樹(shù)研究相對(duì)少一些.Mu［45］提出并行融合模糊規(guī)則分類(lèi)，通過(guò)Map-Reduce（MR-FFRCS）顯示如何從數(shù)據(jù)中并行提取模糊規(guī)則并以整體學(xué)習(xí)的方式評(píng)估模糊規(guī)則.然后以MRFFRCS為基礎(chǔ)模塊，我們提出了基于并行模糊規(guī)則庫(kù)的決策樹(shù)（MR-FRBDT），以改進(jìn)原始FRDT算法，從實(shí)驗(yàn)結(jié)果上看，既提高了性能，并避免了內(nèi)存限制.

3.2 基于Spark平臺(tái)的分布式?jīng)Q策樹(shù)

Spark分布式平臺(tái)是基于內(nèi)存計(jì)算，即將數(shù)據(jù)集緩存到內(nèi)存，隨時(shí)讀取，減少了磁盤(pán)操作，提升了效率.但決策樹(shù)算法移植到Spark平臺(tái)，不僅僅是算法在平臺(tái)的實(shí)現(xiàn)，還需要對(duì)原算法重新進(jìn)行設(shè)計(jì)以適應(yīng)分布式處理.Spark MLlib（機(jī)器學(xué)習(xí)庫(kù)）中已實(shí)現(xiàn)了分布式?jīng)Q策樹(shù)，可以直接調(diào)用.在Spark興起后，也有不少學(xué)者將不同決策樹(shù)遷移到Spark平臺(tái)進(jìn)行研究，主要是通過(guò)平衡數(shù)據(jù)移動(dòng)、負(fù)載平衡和通信開(kāi)銷(xiāo)方面對(duì)基于Spark的分布式?jīng)Q策樹(shù)進(jìn)行優(yōu)化.

3.2.1 Spark分布式清晰決策樹(shù)

Desai［46］等提出對(duì)分布式?jīng)Q策樹(shù)進(jìn)行可擴(kuò)展性的研究.在第一版分布式?jīng)Q策樹(shù)［47］中，提出了決策樹(shù)基于Hadoop的DDT和基于Spark的ST的分布式實(shí)現(xiàn)，在分布式?jīng)Q策樹(shù)中影響的主要因素是樹(shù)的大小和準(zhǔn)確度.樹(shù)的大小與分區(qū)樹(shù)一致，即生成樹(shù)數(shù)等于分區(qū)數(shù).分區(qū)的大小影響樹(shù)的準(zhǔn)確度，如果分區(qū)數(shù)太多，每個(gè)分區(qū)的樣本數(shù)就偏小，即從小樣本中進(jìn)行學(xué)習(xí)，最后預(yù)測(cè)的準(zhǔn)確率受影響；如果分區(qū)數(shù)少，那每個(gè)分區(qū)的樣本偏多，有可能內(nèi)存無(wú)法完全加載，如果能加載即有更高的準(zhǔn)確度.由此可見(jiàn)，分區(qū)大小是另一個(gè)需要考慮的優(yōu)化參數(shù).

圖4 DDT生成圖

DDTv2是需要對(duì)之前的DDT和ST進(jìn)行優(yōu)化，需要在分區(qū)與準(zhǔn)確度之間進(jìn)行權(quán)衡，即在不損失精度的情況下，實(shí)現(xiàn)并行性.在DDTv2中實(shí)行“保持模型”，如圖5，每顆決策樹(shù)從兩個(gè)分區(qū)的數(shù)據(jù)集中進(jìn)行學(xué)習(xí)，訓(xùn)練的數(shù)據(jù)集增大了，所以提高了訓(xùn)練的準(zhǔn)確性，而每顆決策樹(shù)從兩個(gè)分區(qū)中進(jìn)行訓(xùn)練，則樹(shù)數(shù)是分區(qū)數(shù)一半.實(shí)驗(yàn)結(jié)果從樹(shù)規(guī)模、準(zhǔn)確率、葉子節(jié)點(diǎn)數(shù)目等指標(biāo)進(jìn)行分析，DDTv2的中間樹(shù)和葉數(shù)都更小，平均建模時(shí)間也更短，具有更高的精度.所以，DDTv2不僅能適應(yīng)大數(shù)據(jù)集，同時(shí)樹(shù)的規(guī)模明顯縮小，準(zhǔn)確率也有所提升.

圖5 DDTv2生成圖

Chen［48］等提出對(duì)隨機(jī)森林PRF進(jìn)行優(yōu)化，隨機(jī)森林算法中，所有決策樹(shù)同時(shí)訓(xùn)練，所以適合并行化.在效率方面通過(guò)數(shù)據(jù)并行和任務(wù)并行進(jìn)行優(yōu)化；在預(yù)測(cè)準(zhǔn)確度方面，并行化之前需要對(duì)大數(shù)據(jù)量、高維數(shù)據(jù)和噪聲數(shù)據(jù)進(jìn)行降維；最后根據(jù)生成的多顆決策樹(shù)采用加權(quán)投票法得出最終的決策樹(shù)分類(lèi)，通過(guò)這種方式提高預(yù)測(cè)準(zhǔn)確率.首先，選取數(shù)據(jù)集，從數(shù)據(jù)集S中采用bootstrap抽樣方式選擇K個(gè)訓(xùn)練集.其次，針對(duì)大數(shù)據(jù)高維、高噪聲特點(diǎn)，構(gòu)建決策樹(shù)時(shí)需要根據(jù)各個(gè)特征變量的重要性計(jì)算增益比，并按降序排序，選出前K個(gè)，也就是最重要的前K個(gè)（K＜＜M，k＜m）.從余下的M-k個(gè)特征變量選出m-k個(gè)變量.所以，數(shù)據(jù)集的維度就從M降到m了.這在特征變量的多樣性和準(zhǔn)確度下取得平衡，解決了分類(lèi)過(guò)度擬合問(wèn)題.

G（yij）為第j個(gè)特征變量的信息增益，GR（yij）為第j個(gè)特征變量的信息增益率.

對(duì)第j個(gè) 特征變量，對(duì)a取不同值時(shí)的重要性進(jìn)行計(jì)算.為了降低訓(xùn)練集的維度，根據(jù)變量的信息增益比來(lái)衡量每個(gè)特征變量的重要性，然后，選擇最重要的特征變量，刪除不重要的特征變量.

然后，用加權(quán)投票法，計(jì)算每顆決策樹(shù)hi的分類(lèi)精度CAi.

y是正確類(lèi)中的值，z是錯(cuò)誤類(lèi)中的值（z不等于y）.在數(shù)據(jù)并行化方面，PRF的構(gòu)建是基于多顆決策樹(shù)，而每顆樹(shù)的構(gòu)建依賴(lài)于特征的信息增益率的計(jì)算值，所以計(jì)算相當(dāng)龐大繁雜，因此采用了數(shù)據(jù)垂直劃分、數(shù)據(jù)多路復(fù)用技術(shù).數(shù)據(jù)垂直劃分通過(guò)將訓(xùn)練集劃分為多個(gè)特征子集，每個(gè)特征子集分配到Spark集群.而數(shù)據(jù)多路復(fù)用，則是數(shù)據(jù)抽樣過(guò)程中，通過(guò)記錄他們的索引到數(shù)據(jù)樣本索引（DSI）表里，再將DSI表和它對(duì)應(yīng)的特征集一起分配給所有的從節(jié)點(diǎn)，避免數(shù)據(jù)重復(fù)復(fù)制到不同節(jié)點(diǎn).基于Spark平臺(tái)方面，使用雙偶并行方式，訓(xùn)練過(guò)程中創(chuàng)建了DAG任務(wù)和相互依賴(lài)的RDD對(duì)象，最后在不同DAG上執(zhí)行不同任務(wù)調(diào)度.實(shí)驗(yàn)表明基于Spark計(jì)算平臺(tái)下的分布式PRF在準(zhǔn)確率、效率和可擴(kuò)展性方面都有較大的提高.

陸旭［49］等提出基于Spark的并行決策樹(shù)（SPDT），在數(shù)據(jù)預(yù)處理階段，由于連續(xù)屬性計(jì)算頻次太多，采用了Fayyad等的基于邊界點(diǎn)類(lèi)別判定的方法對(duì)連續(xù)屬性離散化，減少了計(jì)算頻次.在決策樹(shù)構(gòu)建階段：通過(guò)信息增益比的計(jì)算，解決了節(jié)點(diǎn)分裂偏向多值屬性問(wèn)題.Spark并行計(jì)算平臺(tái)本身是基于內(nèi)存進(jìn)行計(jì)算，并且構(gòu)成Spark集群的PC機(jī)都是普通機(jī)器，內(nèi)存有限，為了避免內(nèi)存不足，提出了數(shù)據(jù)壓縮方式來(lái)節(jié)約存儲(chǔ)空間.SPDT采用了數(shù)據(jù)的Bitset結(jié)構(gòu)的數(shù)據(jù)壓縮方式，特征的所有值由0或1代替，但會(huì)忽略重復(fù)值，所以將每個(gè)屬性列的取值與數(shù)量做了一個(gè)映射，確保取值正確.屬性的信息增益的計(jì)算是需要特征列屬性和目標(biāo)屬性的值進(jìn)行計(jì)算，如果還是按Spark的按行分區(qū)，需要頻繁從不同節(jié)點(diǎn)去獲取同列屬性的不同樣本取值，增加了網(wǎng)絡(luò)通信資源占用，降低了效率，為此，提出了垂直劃分即基于屬性列進(jìn)行存儲(chǔ)，將一列或多列的特征子集存儲(chǔ)在一個(gè)節(jié)點(diǎn)，便于計(jì)算.實(shí)驗(yàn)結(jié)果表明，并行決策樹(shù)比原來(lái)的MLDT和Yggdrasil的效率提高了，只是準(zhǔn)確率提高的較少，主要原因可能是數(shù)據(jù)壓縮后，取值不對(duì)應(yīng)問(wèn)題.

黃廷輝［50］等提出梯度優(yōu)化決策樹(shù)（GBDT）.傳統(tǒng)決策樹(shù)是一個(gè)分類(lèi)器進(jìn)行預(yù)測(cè)，為了提高準(zhǔn)確率，GBDT使用多個(gè)分類(lèi)器融合成一個(gè)分類(lèi)器進(jìn)行預(yù)測(cè)分類(lèi)，最后通過(guò)Boosting投票方式對(duì)多分類(lèi)器結(jié)果，使用少數(shù)服從多數(shù)原則確定最終分類(lèi)結(jié)果.GBDT是決策樹(shù)與Boosting相融合的一種決策樹(shù)應(yīng)用，即利用損失函數(shù)對(duì)前面決策樹(shù)的分類(lèi)錯(cuò)誤結(jié)果進(jìn)行訓(xùn)練.損失函數(shù)中采用了梯度下降值進(jìn)行優(yōu)化.對(duì)連續(xù)屬性的離散化采用了切分點(diǎn)抽樣方法，即在一定子特征策略上進(jìn)行抽樣，然后生成各個(gè)分區(qū)結(jié)果，最后聚合計(jì)算純度，取純度最低的點(diǎn)為切分點(diǎn).在特征數(shù)據(jù)的選取上，因?yàn)樘卣鞑凰愣?，分析交通的每個(gè)特征、每個(gè)特征的取值，控制了數(shù)據(jù)樣本的噪音，提高了準(zhǔn)確率.傳統(tǒng)決策樹(shù)是按深度、寬度進(jìn)行迭代，GBDT結(jié)合了Spark分布式原理通過(guò)逐層構(gòu)建，充分利用了平臺(tái)并行性，提高了效率.實(shí)驗(yàn)表明，基于Spark平臺(tái)的分布式GBDT對(duì)交通預(yù)測(cè)系統(tǒng)的實(shí)時(shí)性提供了強(qiáng)有力的技術(shù)支持.而梯度優(yōu)化決策樹(shù)在效率和準(zhǔn)確率上得到一個(gè)平衡，但決策樹(shù)并未進(jìn)行剪枝，所以存在過(guò)擬合問(wèn)題.在數(shù)據(jù)分析上，針對(duì)每個(gè)特征進(jìn)行分析，只能應(yīng)用于小數(shù)據(jù)集，并不能適應(yīng)于大數(shù)據(jù)集.王曉楠［51］提出根據(jù)CART算法整個(gè)樹(shù)的構(gòu)建過(guò)程：數(shù)據(jù)預(yù)處理、屬性選取、剪枝進(jìn)行整個(gè)過(guò)程實(shí)行并行化.實(shí)驗(yàn)分為兩部分：一部分基于CART算法改進(jìn)和一部分基于改進(jìn)的CART算法并行化到Spark平臺(tái)，從實(shí)驗(yàn)結(jié)果來(lái)看單獨(dú)的算法改進(jìn)在效率上得以提高，但是并行化后效率提升并不明顯，主要是因?yàn)橛?jì)算量大，也沒(méi)有對(duì)Spark平臺(tái)運(yùn)行進(jìn)行調(diào)優(yōu).

3.2.2 Spark分布式模糊決策樹(shù)

為了適應(yīng)大數(shù)據(jù)集的不確定環(huán)境，也有將模糊決策樹(shù)遷移到Spark平臺(tái)上進(jìn)行實(shí)現(xiàn)的研究.分布式模糊決策樹(shù)在模糊環(huán)境下具有重大意義，尤其是在醫(yī)學(xué)研究領(lǐng)域.構(gòu)建分布式模糊決策樹(shù)時(shí)，第一步是對(duì)數(shù)據(jù)的模糊化，但模糊化對(duì)整個(gè)模糊決策樹(shù)的構(gòu)成的性能有較大影響.模糊決策樹(shù)中存在模糊分區(qū)，提出比較八種不同模糊分區(qū)方法在準(zhǔn)確性和數(shù)據(jù)執(zhí)行效率上，PCR和NPCR優(yōu)于其他幾種方法［52］.Segatori［53］等基于Spark平臺(tái)首次對(duì)模糊決策樹(shù)的廣泛性研究，提出基于離散化算法的兩步數(shù)據(jù)生成算法.離散化時(shí)采用基于模糊分區(qū)的模糊熵.基于模糊信息熵的離散化會(huì)生成多個(gè)候選分裂點(diǎn)，再通過(guò)最小描述長(zhǎng)度原則對(duì)多個(gè)候選分裂點(diǎn)進(jìn)行判斷是接收還是拒絕，確定最終分裂點(diǎn)，這個(gè)點(diǎn)會(huì)生成最小化后的權(quán)重熵.這種新穎的分布式模糊離散器，是基于模糊信息熵為每個(gè)連續(xù)屬性生成強(qiáng)大的模糊分區(qū).通過(guò)比較基于Spark平臺(tái)的FDT（模糊決策樹(shù)）、Spark MLlib庫(kù)中的DDT（分布式?jīng)Q策樹(shù)）、MapReduce基于分布式模糊規(guī)則的分類(lèi)系統(tǒng)Chi-FRBCS-BigData算法、基于MapReduce的模糊二進(jìn)制決策樹(shù)（FBDT）和模糊多路決策樹(shù)（FMDT）在數(shù)據(jù)集的準(zhǔn)確性，復(fù)雜性和執(zhí)行時(shí)間三個(gè)指標(biāo)進(jìn)行分析，模糊二進(jìn)制決策樹(shù)在準(zhǔn)確性方面和統(tǒng)計(jì)上優(yōu)于FMDT，DDT和Chi-FRBCS-BigData.模型復(fù)雜性上得出FBDT和DDT使用的節(jié)點(diǎn)數(shù)比FMDT少.

4 結(jié)論

關(guān)于在大數(shù)據(jù)平臺(tái)下的分布式?jīng)Q策樹(shù)已有較多研究，相比而言，Spark是Hadoop的升級(jí)版本，發(fā)展的時(shí)間并不長(zhǎng)，所以針對(duì)Spark平臺(tái)下的研究稍微少一些.模糊決策樹(shù)在處理不確定性環(huán)境下有較大的實(shí)際意義，希望后面有更多關(guān)于大數(shù)據(jù)平臺(tái)下的模糊決策樹(shù)的研究.部分文獻(xiàn)針對(duì)屬性進(jìn)行了分析，但在小數(shù)據(jù)集上明顯提高了準(zhǔn)確率，但如何將屬性分析應(yīng)用到大數(shù)據(jù)集需要進(jìn)一步研究.針對(duì)各行各業(yè)產(chǎn)生的數(shù)據(jù)集也許有不同特征，比如是有序、無(wú)序、連續(xù)型或者離散型，分析數(shù)據(jù)集，對(duì)不同數(shù)據(jù)集的特征結(jié)合不同的優(yōu)化方式，再結(jié)合決策樹(shù)，也許能產(chǎn)生更高的準(zhǔn)確率.分布式?jīng)Q策樹(shù)評(píng)價(jià)指標(biāo)上，不能僅僅參考分類(lèi)準(zhǔn)確率、效率，而應(yīng)多角度進(jìn)行比較分析.在性能優(yōu)化方面，不僅是對(duì)算法的優(yōu)化，還要針對(duì)算法所應(yīng)用的平臺(tái)應(yīng)用時(shí)分區(qū)數(shù)、分區(qū)大小、節(jié)點(diǎn)參數(shù)等需要設(shè)置，但想要一個(gè)較好的配置，將耗費(fèi)大量時(shí)間，可以結(jié)合粒子群算法，通過(guò)多方面優(yōu)化，分布式?jīng)Q策樹(shù)將會(huì)有更好的表現(xiàn).