決策樹(shù)簡(jiǎn)介胡作梁1433275決策樹(shù)簡(jiǎn)介胡作梁1433275目錄頁(yè)CONTENTSPAGE1.何為決策樹(shù)2.決策樹(shù)的發(fā)展3.決策樹(shù)分類4.決策樹(shù)適用目錄頁(yè)CONTENTSPAGE1.何為決策樹(shù)2.決策樹(shù)的發(fā)何為決策樹(shù)何為決策樹(shù)什么是決策樹(shù)？通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例；葉子節(jié)點(diǎn)即為實(shí)例所屬的分類；樹(shù)上每個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值。決策樹(shù)（DecisionTree），又稱為判定樹(shù)，是數(shù)據(jù)挖掘技術(shù)中的一種重要的分類方法，它是一種以樹(shù)結(jié)構(gòu)（包括二叉樹(shù)和多叉樹(shù)）形式來(lái)表達(dá)的預(yù)測(cè)分析模型。什么是決策樹(shù)？通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例決策樹(shù)的發(fā)展決策樹(shù)的發(fā)展決策樹(shù)的發(fā)展決策樹(shù)方法是一種比較通用的分類函數(shù)逼近法，它是一種常用于預(yù)測(cè)模型的算法，通過(guò)將大量數(shù)據(jù)有目的分類，找到一些有潛在價(jià)值的信息。決策樹(shù)的起源是CLS（ConceptLearningSystem），CLS是由Hunt、Marin和Stone為了研究人類概念模型而得來(lái)的，于1966年提出，該模型為很多決策樹(shù)算法的發(fā)展奠定了很好的基礎(chǔ)。1984年，L.Breiman等人提出了CART（ClassificationandRegressionTree）算法。決策樹(shù)的發(fā)展決策樹(shù)方法是一種比較通用的分類函數(shù)逼近法，它是一決策樹(shù)的發(fā)展1986年，J.R.Quinlan提出了ID3算法。1993年，J.R.Quinlan又提出了C4.5算法，克服了ID3算法的一些不足。1996年，M.Mehta和R.Agrawal等人提出了一種高速可伸縮的有監(jiān)督的尋找學(xué)習(xí)分類方法SLIQ（SupervisedLearningInQuest）。同年，J.Shafer和R.Agrawal等人提出可伸縮并行歸納決策樹(shù)分類方法SPRINT(ScalablePaRallelizableInductionofDecisionTrees)1998年，R.Rastogi等人提出一種將建樹(shù)和修剪相結(jié)合的分類算法PUBLIC(ADecisionTreethatIntegratesBuildingandPruning)決策樹(shù)的發(fā)展1986年，J.R.Quinlan提出了ID3算決策樹(shù)的分類決策樹(shù)的分類ID3ID3算法選用最大信息增益的屬性作為決策樹(shù)分裂屬性。在算法實(shí)際應(yīng)用中，這種方法偏向于選擇多值屬性，但屬性取值數(shù)目的多少與屬性的匹配并無(wú)真正關(guān)聯(lián)。這樣在使用ID3算法構(gòu)建時(shí)，若出現(xiàn)各屬性值取值數(shù)分布偏差大的情況，分類精度會(huì)大打折扣。ID3算法本身并未給出處理連續(xù)數(shù)據(jù)的方法。ID3算法不能處理帶有缺失值的數(shù)據(jù)集，故在進(jìn)行算法挖掘之前需要對(duì)數(shù)據(jù)集中的缺失值進(jìn)行預(yù)處理。ID3ID3算法選用最大信息增益的屬性作為決策樹(shù)分裂屬性。在C4.5C4.5算法同樣是由J.R.Quinlan提出，它在ID3算法的基礎(chǔ)上演變而來(lái)。C4.5算法除了擁有前述的ID3算法基本功能外，在其算法中還加入了連續(xù)值處理、屬性空缺處理等方法?？偨Y(jié)來(lái)說(shuō)，C4.5算法在以下幾個(gè)方面做出了改進(jìn)：信息增益比例計(jì)算公式如下：1）使用信息增益比例而非信息增益作為分裂標(biāo)準(zhǔn)。在上式中，

稱為分裂信息，它反映了屬性分裂數(shù)據(jù)的延展度與平衡性，計(jì)算公式如下：C4.5C4.5算法同樣是由J.R.Quinlan提出，C4.52）處理含有帶缺失值屬性的樣本C4.5算法在處理缺失數(shù)據(jù)時(shí)最常用的方法是，將這些值并入最常見(jiàn)的某一類中或是以最常用的值代替之。C4.5算法處理連續(xù)值屬性過(guò)程3）處理連續(xù)值屬性以每個(gè)數(shù)據(jù)作為閾值劃分?jǐn)?shù)據(jù)集，代價(jià)是否過(guò)大？C4.52）處理含有帶缺失值屬性的樣本C4.5算法在處理C4.54）規(guī)則的產(chǎn)生決策樹(shù)每條根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑都對(duì)應(yīng)一個(gè)分類規(guī)則，可將所有這些路徑綜合轉(zhuǎn)換為一個(gè)規(guī)則集。規(guī)則集存儲(chǔ)于一個(gè)二維數(shù)組中，每一行代表決策樹(shù)的一個(gè)規(guī)則。交互驗(yàn)證是一種模型的評(píng)估方法。在訓(xùn)練開(kāi)始之前，預(yù)留一部分?jǐn)?shù)據(jù)，而在訓(xùn)練之后，使用這部分?jǐn)?shù)據(jù)對(duì)學(xué)習(xí)的結(jié)果進(jìn)行驗(yàn)證的方法叫做交互驗(yàn)證。交互驗(yàn)證最簡(jiǎn)單的方法是兩分法，將數(shù)據(jù)集劃分為兩個(gè)獨(dú)立子集，一個(gè)稱為訓(xùn)練集，一個(gè)稱為測(cè)試集。另一種方法是K次折疊交互驗(yàn)證，將數(shù)據(jù)集劃分為K個(gè)子集，留取一個(gè)作為測(cè)試集，其余K-1個(gè)作為訓(xùn)練集，最后還對(duì)數(shù)據(jù)子集的錯(cuò)誤數(shù)計(jì)算平均值。5）交互驗(yàn)證（CrossValidation）從上面的改進(jìn)描述可以看到，C4.5相較ID3有了許多提高，縱然如此，C4.5仍然存在一定的不足之處。它在測(cè)試屬性的判斷和樣本集分割方面仍舊存在一定的偏向性，同時(shí)C4.5生成的決策樹(shù)還稱不上簡(jiǎn)潔，特別是對(duì)于數(shù)據(jù)屬性及其取值較多的情況。因此，人們還在不斷改進(jìn)現(xiàn)有算法和提出新的算法。C4.54）規(guī)則的產(chǎn)生決策樹(shù)每條根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑都對(duì)應(yīng)CARE&SLIQCART（ClassificationAndRegressionTree）算法該決策樹(shù)算法模型采用的是二叉樹(shù)形式，利用二分遞歸將數(shù)據(jù)空間不斷劃分為不同子集。同樣的，每一個(gè)葉節(jié)點(diǎn)都有著與之相關(guān)的分類規(guī)則，對(duì)應(yīng)了不同的數(shù)據(jù)集劃分。為了減小CART決策樹(shù)的深度，在決策樹(shù)某一分支節(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)集大多數(shù)為一類時(shí)，即將該分支設(shè)為葉節(jié)點(diǎn)。CART算法采用GINI系數(shù)作為屬性分裂的標(biāo)準(zhǔn)。在計(jì)算機(jī)大量普及的今天，雖然內(nèi)存和CPU越來(lái)越大，越來(lái)越快，但終究會(huì)有許多數(shù)據(jù)在處理的時(shí)候無(wú)法全部放入內(nèi)存計(jì)算。在眾多決策樹(shù)算法中，大部分算法需要在決策樹(shù)生成與分類時(shí)將數(shù)據(jù)集全部放入主存，這在數(shù)據(jù)集規(guī)模較小情況下沒(méi)有問(wèn)題，但是一旦數(shù)據(jù)規(guī)模超出主存限制，這些算法就無(wú)能為力了。SLIQ（SupervisedLearningInQuest）算法為了解決上述問(wèn)題，提出了一些改進(jìn)，并且它能保證分類精度不變。在SLIQ決策樹(shù)的生成過(guò)程中可以應(yīng)用其他算法，其精度也與這些算法一直，不過(guò)對(duì)于大數(shù)量級(jí)的數(shù)據(jù)，SLIQ效率大大提高，生成的模型也較為精簡(jiǎn)。除此之外，由于SLIQ破除了主存的限制，則其對(duì)訓(xùn)練數(shù)據(jù)量和屬性量都沒(méi)有限制了。SLIQ（SupervisedLearningInQuest）算法CARE&SLIQCART（ClassificationSPRINT&PUBLIC

由于SLIQ仍存在對(duì)主存容量的限制，J.Shafter等人提出了SPRINT（ScalablePaRallelizableINductionofdecisionTrees）算法，其在SLIQ的基礎(chǔ)上又做出了進(jìn)一步的改進(jìn)。該算法真正意義上破除了主存限制，使得決策樹(shù)處理的數(shù)據(jù)規(guī)模達(dá)到了前所未有的境界。與此同時(shí)，并行算法的引入也使得SPRINT算法具有更好的伸縮性。SPRINT主要改進(jìn)了SLIQ的數(shù)據(jù)結(jié)構(gòu)，合并SLIQ中的類表與屬性表，將這些數(shù)據(jù)結(jié)構(gòu)均放于輔存之中。這樣就使得算法在遍歷屬性列表尋找最優(yōu)分裂時(shí)，只需使用輔存中的合并數(shù)據(jù)表。最后，SPRINT采用的生成樹(shù)策略是深度優(yōu)先規(guī)則。并行算法就是用多臺(tái)處理機(jī)聯(lián)合求解問(wèn)題的方法和步驟，其執(zhí)行過(guò)程是將給定的問(wèn)題首先分解成若干個(gè)盡量相互獨(dú)立的子問(wèn)題，然后使用多臺(tái)計(jì)算機(jī)同時(shí)求解它，從而最終求得原問(wèn)題的解。SPRINT算法在上述介紹的決策樹(shù)算法中，所有算法均是先通過(guò)一定的規(guī)則建立決策樹(shù)，然后在進(jìn)行決策樹(shù)剪枝，從而達(dá)到生成最終決策樹(shù)的目的。而PUBLIC（ADecisionTreethatIntegratesBuildingandPruning）算法則是典型的預(yù)剪枝決策樹(shù)算法。作為預(yù)剪枝技術(shù)生成的決策樹(shù)與后剪枝決策樹(shù)是一致的，PUBLIC算法采用Gini系數(shù)作為分裂標(biāo)準(zhǔn)，可以說(shuō)是CART算法的一種有效改進(jìn)。PUBLIC算法SPRINT&PUBLIC由于SLIQ仍存在對(duì)主存容決策樹(shù)的適用決策樹(shù)的適用C5.0&CHAID1234SUGGESTION一、C5.0算法

（執(zhí)行效率和內(nèi)存使用改進(jìn)、適用大數(shù)據(jù)集）1）面對(duì)數(shù)據(jù)遺漏和輸入字段很多的問(wèn)題時(shí)非常穩(wěn)?。?）通常不需要很長(zhǎng)的訓(xùn)練次數(shù)進(jìn)行估計(jì)；3）比一些其他類型的模型易于理解，模型推出的規(guī)則有非常直觀的解釋；4）允許進(jìn)行多次多于兩個(gè)子組的分割。目標(biāo)字段必須為分類字段。C4.5是在ID3算法的基礎(chǔ)上將連續(xù)屬性離散化，C5.0是在C4.5的基礎(chǔ)上在內(nèi)存和執(zhí)行效率進(jìn)行了改進(jìn)。二、CHAID(卡方自動(dòng)交互檢測(cè))（可用于多元分類，從統(tǒng)計(jì)角度來(lái)分裂變量）1）可產(chǎn)生多分枝的決策樹(shù)；2）目標(biāo)變量可以定距或定類；3）從統(tǒng)計(jì)顯著性角度確定分支變量和分割值，進(jìn)而優(yōu)化樹(shù)的分枝過(guò)程；4）建立在因果關(guān)系探討中，依據(jù)目標(biāo)變量實(shí)現(xiàn)對(duì)輸入變量眾多水平劃分。C5.0&CHAID1234SUGGESTION一、C三、classificationandregressiontree(C&RT)（對(duì)二元分類比較有效）1）可自動(dòng)忽略對(duì)目標(biāo)變量沒(méi)有貢獻(xiàn)的屬性變量，也為判斷屬性變量的重要性，減少變量數(shù)據(jù)提供參考；2）在面對(duì)諸如存在缺失值、變量數(shù)多等問(wèn)題時(shí)C&RT顯得非常穩(wěn)健（robust）；3）估計(jì)模型通常不用花費(fèi)很長(zhǎng)的訓(xùn)練時(shí)間；4）推理過(guò)程完全依據(jù)屬性變量的取值特點(diǎn)（與C5.0不同，C&RT的輸出字段既可以是數(shù)值型，也可以是分類型）5）比其他模型更易于理解——從模型中得到的規(guī)則能得到非常直觀的解釋，決策推理過(guò)程可以表示成IF…THEN的形式；6）目標(biāo)是定類變量為分類樹(shù)，若目標(biāo)變量是定距變量，則為回歸樹(shù)；7）通過(guò)檢測(cè)輸入字段，通過(guò)度量各個(gè)劃分產(chǎn)生的異質(zhì)性的減小程度，找到最佳的一個(gè)劃分；8）非常靈活，可以允許有部分錯(cuò)分成本，還可指定先驗(yàn)概率分布，可使用自動(dòng)的成本復(fù)雜性剪枝來(lái)得到歸納性更強(qiáng)的樹(shù)。C&RT三、classificationandregressio四、QUEST（quickunbiasedefficientstatisticaltree）（也用于二分類，運(yùn)算過(guò)程比CR&T更簡(jiǎn)單有效，但不支持使用連續(xù)的輸出變量）QUEST節(jié)點(diǎn)可提供用于構(gòu)建決策樹(shù)的二元分類法，此方法的設(shè)計(jì)目的是減少大型C&R決策樹(shù)分析所需的處理時(shí)間，同時(shí)減小分類樹(shù)方法中常見(jiàn)的偏向類別較多預(yù)測(cè)變量的趨勢(shì)。預(yù)測(cè)變量字段可以是數(shù)字范圍的，但目標(biāo)字段必須是分類的。QUEST四、QUEST（quickunbiasedefficie1）決策樹(shù)與其他技術(shù)相結(jié)合在數(shù)據(jù)挖掘技術(shù)中，從數(shù)據(jù)集的預(yù)處理到最終輸出需要的知識(shí)，要用到很多方面的技術(shù)，所以決策樹(shù)也需要與其他技術(shù)相結(jié)合，才能有創(chuàng)新，才能有發(fā)展?，F(xiàn)在已經(jīng)有人將決策樹(shù)和模糊集合理論、遺傳算法、神經(jīng)網(wǎng)絡(luò)等技術(shù)結(jié)合起來(lái)研究，都不同程度的提高了決策樹(shù)的效率和精度。2）決策樹(shù)分類的準(zhǔn)確率決策樹(shù)分類的準(zhǔn)確率也是研究的重點(diǎn)，因?yàn)樗桥袛鄾Q策樹(shù)算法優(yōu)劣的標(biāo)準(zhǔn)之一，比如多變量決策樹(shù)技術(shù)，它減少了決策樹(shù)的規(guī)模，它的最終目的是為了提高決策樹(shù)的精度。未來(lái)的發(fā)展1）決策樹(shù)與其他技術(shù)相結(jié)合在數(shù)據(jù)挖掘技術(shù)中，從數(shù)據(jù)集的預(yù)處理實(shí)際中數(shù)據(jù)集往往存在大量的缺失數(shù)據(jù)、噪聲數(shù)據(jù)等等。當(dāng)然，最簡(jiǎn)單的方法就是直接將這樣的數(shù)據(jù)刪除，但是這樣必然會(huì)導(dǎo)致分類結(jié)果不準(zhǔn)確。目前的方法就是用出現(xiàn)頻率最高的值替代缺失值。4）決策樹(shù)算法的增量學(xué)習(xí)目前很多決策樹(shù)算法都不具備增量學(xué)習(xí)的功能，對(duì)于新的訓(xùn)練樣本需要重新建樹(shù)，這樣會(huì)花費(fèi)大量的時(shí)間，大大降低了效率。3）數(shù)據(jù)集的預(yù)處理未來(lái)的發(fā)展實(shí)際中數(shù)據(jù)集往往存在大量的缺失數(shù)據(jù)、噪聲數(shù)據(jù)等等。當(dāng)然，最簡(jiǎn)21謝謝21謝謝決策樹(shù)簡(jiǎn)介胡作梁1433275決策樹(shù)簡(jiǎn)介胡作梁1433275目錄頁(yè)CONTENTSPAGE1.何為決策樹(shù)2.決策樹(shù)的發(fā)展3.決策樹(shù)分類4.決策樹(shù)適用目錄頁(yè)CONTENTSPAGE1.何為決策樹(shù)2.決策樹(shù)的發(fā)何為決策樹(shù)何為決策樹(shù)什么是決策樹(shù)？通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例；葉子節(jié)點(diǎn)即為實(shí)例所屬的分類；樹(shù)上每個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值。決策樹(shù)（DecisionTree），又稱為判定樹(shù)，是數(shù)據(jù)挖掘技術(shù)中的一種重要的分類方法，它是一種以樹(shù)結(jié)構(gòu)（包括二叉樹(shù)和多叉樹(shù)）形式來(lái)表達(dá)的預(yù)測(cè)分析模型。什么是決策樹(shù)？通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例決策樹(shù)的發(fā)展決策樹(shù)的發(fā)展決策樹(shù)的發(fā)展決策樹(shù)方法是一種比較通用的分類函數(shù)逼近法，它是一種常用于預(yù)測(cè)模型的算法，通過(guò)將大量數(shù)據(jù)有目的分類，找到一些有潛在價(jià)值的信息。決策樹(shù)的起源是CLS（ConceptLearningSystem），CLS是由Hunt、Marin和Stone為了研究人類概念模型而得來(lái)的，于1966年提出，該模型為很多決策樹(shù)算法的發(fā)展奠定了很好的基礎(chǔ)。1984年，L.Breiman等人提出了CART（ClassificationandRegressionTree）算法。決策樹(shù)的發(fā)展決策樹(shù)方法是一種比較通用的分類函數(shù)逼近法，它是一決策樹(shù)的發(fā)展1986年，J.R.Quinlan提出了ID3算法。1993年，J.R.Quinlan又提出了C4.5算法，克服了ID3算法的一些不足。1996年，M.Mehta和R.Agrawal等人提出了一種高速可伸縮的有監(jiān)督的尋找學(xué)習(xí)分類方法SLIQ（SupervisedLearningInQuest）。同年，J.Shafer和R.Agrawal等人提出可伸縮并行歸納決策樹(shù)分類方法SPRINT(ScalablePaRallelizableInductionofDecisionTrees)1998年，R.Rastogi等人提出一種將建樹(shù)和修剪相結(jié)合的分類算法PUBLIC(ADecisionTreethatIntegratesBuildingandPruning)決策樹(shù)的發(fā)展1986年，J.R.Quinlan提出了ID3算決策樹(shù)的分類決策樹(shù)的分類ID3ID3算法選用最大信息增益的屬性作為決策樹(shù)分裂屬性。在算法實(shí)際應(yīng)用中，這種方法偏向于選擇多值屬性，但屬性取值數(shù)目的多少與屬性的匹配并無(wú)真正關(guān)聯(lián)。這樣在使用ID3算法構(gòu)建時(shí)，若出現(xiàn)各屬性值取值數(shù)分布偏差大的情況，分類精度會(huì)大打折扣。ID3算法本身并未給出處理連續(xù)數(shù)據(jù)的方法。ID3算法不能處理帶有缺失值的數(shù)據(jù)集，故在進(jìn)行算法挖掘之前需要對(duì)數(shù)據(jù)集中的缺失值進(jìn)行預(yù)處理。ID3ID3算法選用最大信息增益的屬性作為決策樹(shù)分裂屬性。在C4.5C4.5算法同樣是由J.R.Quinlan提出，它在ID3算法的基礎(chǔ)上演變而來(lái)。C4.5算法除了擁有前述的ID3算法基本功能外，在其算法中還加入了連續(xù)值處理、屬性空缺處理等方法。總結(jié)來(lái)說(shuō)，C4.5算法在以下幾個(gè)方面做出了改進(jìn)：信息增益比例計(jì)算公式如下：1）使用信息增益比例而非信息增益作為分裂標(biāo)準(zhǔn)。在上式中，

稱為分裂信息，它反映了屬性分裂數(shù)據(jù)的延展度與平衡性，計(jì)算公式如下：C4.5C4.5算法同樣是由J.R.Quinlan提出，C4.52）處理含有帶缺失值屬性的樣本C4.5算法在處理缺失數(shù)據(jù)時(shí)最常用的方法是，將這些值并入最常見(jiàn)的某一類中或是以最常用的值代替之。C4.5算法處理連續(xù)值屬性過(guò)程3）處理連續(xù)值屬性以每個(gè)數(shù)據(jù)作為閾值劃分?jǐn)?shù)據(jù)集，代價(jià)是否過(guò)大？C4.52）處理含有帶缺失值屬性的樣本C4.5算法在處理C4.54）規(guī)則的產(chǎn)生決策樹(shù)每條根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑都對(duì)應(yīng)一個(gè)分類規(guī)則，可將所有這些路徑綜合轉(zhuǎn)換為一個(gè)規(guī)則集。規(guī)則集存儲(chǔ)于一個(gè)二維數(shù)組中，每一行代表決策樹(shù)的一個(gè)規(guī)則。交互驗(yàn)證是一種模型的評(píng)估方法。在訓(xùn)練開(kāi)始之前，預(yù)留一部分?jǐn)?shù)據(jù)，而在訓(xùn)練之后，使用這部分?jǐn)?shù)據(jù)對(duì)學(xué)習(xí)的結(jié)果進(jìn)行驗(yàn)證的方法叫做交互驗(yàn)證。交互驗(yàn)證最簡(jiǎn)單的方法是兩分法，將數(shù)據(jù)集劃分為兩個(gè)獨(dú)立子集，一個(gè)稱為訓(xùn)練集，一個(gè)稱為測(cè)試集。另一種方法是K次折疊交互驗(yàn)證，將數(shù)據(jù)集劃分為K個(gè)子集，留取一個(gè)作為測(cè)試集，其余K-1個(gè)作為訓(xùn)練集，最后還對(duì)數(shù)據(jù)子集的錯(cuò)誤數(shù)計(jì)算平均值。5）交互驗(yàn)證（CrossValidation）從上面的改進(jìn)描述可以看到，C4.5相較ID3有了許多提高，縱然如此，C4.5仍然存在一定的不足之處。它在測(cè)試屬性的判斷和樣本集分割方面仍舊存在一定的偏向性，同時(shí)C4.5生成的決策樹(shù)還稱不上簡(jiǎn)潔，特別是對(duì)于數(shù)據(jù)屬性及其取值較多的情況。因此，人們還在不斷改進(jìn)現(xiàn)有算法和提出新的算法。C4.54）規(guī)則的產(chǎn)生決策樹(shù)每條根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑都對(duì)應(yīng)CARE&SLIQCART（ClassificationAndRegressionTree）算法該決策樹(shù)算法模型采用的是二叉樹(shù)形式，利用二分遞歸將數(shù)據(jù)空間不斷劃分為不同子集。同樣的，每一個(gè)葉節(jié)點(diǎn)都有著與之相關(guān)的分類規(guī)則，對(duì)應(yīng)了不同的數(shù)據(jù)集劃分。為了減小CART決策樹(shù)的深度，在決策樹(shù)某一分支節(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)集大多數(shù)為一類時(shí)，即將該分支設(shè)為葉節(jié)點(diǎn)。CART算法采用GINI系數(shù)作為屬性分裂的標(biāo)準(zhǔn)。在計(jì)算機(jī)大量普及的今天，雖然內(nèi)存和CPU越來(lái)越大，越來(lái)越快，但終究會(huì)有許多數(shù)據(jù)在處理的時(shí)候無(wú)法全部放入內(nèi)存計(jì)算。在眾多決策樹(shù)算法中，大部分算法需要在決策樹(shù)生成與分類時(shí)將數(shù)據(jù)集全部放入主存，這在數(shù)據(jù)集規(guī)模較小情況下沒(méi)有問(wèn)題，但是一旦數(shù)據(jù)規(guī)模超出主存限制，這些算法就無(wú)能為力了。SLIQ（SupervisedLearningInQuest）算法為了解決上述問(wèn)題，提出了一些改進(jìn)，并且它能保證分類精度不變。在SLIQ決策樹(shù)的生成過(guò)程中可以應(yīng)用其他算法，其精度也與這些算法一直，不過(guò)對(duì)于大數(shù)量級(jí)的數(shù)據(jù)，SLIQ效率大大提高，生成的模型也較為精簡(jiǎn)。除此之外，由于SLIQ破除了主存的限制，則其對(duì)訓(xùn)練數(shù)據(jù)量和屬性量都沒(méi)有限制了。SLIQ（SupervisedLearningInQuest）算法CARE&SLIQCART（ClassificationSPRINT&PUBLIC

由于SLIQ仍存在對(duì)主存容量的限制，J.Shafter等人提出了SPRINT（ScalablePaRallelizableINductionofdecisionTrees）算法，其在SLIQ的基礎(chǔ)上又做出了進(jìn)一步的改進(jìn)。該算法真正意義上破除了主存限制，使得決策樹(shù)處理的數(shù)據(jù)規(guī)模達(dá)到了前所未有的境界。與此同時(shí)，并行算法的引入也使得SPRINT算法具有更好的伸縮性。SPRINT主要改進(jìn)了SLIQ的數(shù)據(jù)結(jié)構(gòu)，合并SLIQ中的類表與屬性表，將這些數(shù)據(jù)結(jié)構(gòu)均放于輔存之中。這樣就使得算法在遍歷屬性列表尋找最優(yōu)分裂時(shí)，只需使用輔存中的合并數(shù)據(jù)表。最后，SPRINT采用的生成樹(shù)策略是深度優(yōu)先規(guī)則。并行算法就是用多臺(tái)處理機(jī)聯(lián)合求解問(wèn)題的方法和步驟，其執(zhí)行過(guò)程是將給定的問(wèn)題首先分解成若干個(gè)盡量相互獨(dú)立的子問(wèn)題，然后使用多臺(tái)計(jì)算機(jī)同時(shí)求解它，從而最終求得原問(wèn)題的解。SPRINT算法在上述介紹的決策樹(shù)算法中，所有算法均是先通過(guò)一定的規(guī)則建立決策樹(shù)，然后在進(jìn)行決策樹(shù)剪枝，從而達(dá)到生成最終決策樹(shù)的目的。而PUBLIC（ADecisionTreethatIntegratesBuildingandPruning）算法則是典型的預(yù)剪枝決策樹(shù)算法。作為預(yù)剪枝技術(shù)生成的決策樹(shù)與后剪枝決策樹(shù)是一致的，PUBLIC算法采用Gini系數(shù)作為分裂標(biāo)準(zhǔn)，可以說(shuō)是CART算法的一種有效改進(jìn)。PUBLIC算法SPRINT&PUBLIC由于SLIQ仍存在對(duì)主存容決策樹(shù)的適用決策樹(shù)的適用C5.0&CHAID1234SUGGESTION一、C5.0算法

（執(zhí)行效率和內(nèi)存使用改進(jìn)、適用大數(shù)據(jù)集）1）面對(duì)數(shù)據(jù)遺漏和輸入字段很多的問(wèn)題時(shí)非常穩(wěn)?。?）通常不需要很長(zhǎng)的訓(xùn)練次數(shù)進(jìn)行估計(jì)；3）比一些其他類型的模型易于理解，模型推出的規(guī)則有非常直觀的解釋；4）允許進(jìn)行多次多于兩個(gè)子組的分割。目標(biāo)字段必須為分類字段。C4.5是在ID3算法的基礎(chǔ)上將連續(xù)屬性離散化，C5.0是在C4.5的基礎(chǔ)上在內(nèi)存和執(zhí)行效率進(jìn)行了改進(jìn)。二、CHAID(卡方自動(dòng)交互檢測(cè))（可用于多元分類，從統(tǒng)計(jì)角度來(lái)分裂變量）1）可產(chǎn)生多分枝的決策樹(shù)；2）目標(biāo)變量可以定距或定類；3）從統(tǒng)計(jì)顯著性角度確定分支變量和分割值，進(jìn)而優(yōu)化樹(shù)的分枝過(guò)程；4）建立在因果關(guān)系探討中，依據(jù)目標(biāo)變量實(shí)現(xiàn)對(duì)輸入變量眾多水平劃分。C5.0&CHAID1234SUGGESTION一、C三、classificationandregressiontree(C&RT)（對(duì)二元分類比較有效）1）可自動(dòng)忽略對(duì)目標(biāo)變量沒(méi)有貢獻(xiàn)的屬性變量，也為判斷屬性變量的重要性，減少變量數(shù)據(jù)提供參考；2）在面對(duì)諸如存在缺失值、變量數(shù)多等問(wèn)題時(shí)C&RT顯得非常穩(wěn)?。╮obust）；3）估計(jì)模型通常不用花費(fèi)很長(zhǎng)的訓(xùn)