決策樹

1.概述

決策樹由節(jié)點(diǎn)和有向邊組成绘闷，節(jié)點(diǎn)有兩種類型橡庞，內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩杂≌幔~節(jié)點(diǎn)表示一個(gè)類扒最。

enter description here

在用決策樹分類時(shí)，先從根節(jié)點(diǎn)出發(fā)华嘹，對(duì)實(shí)例中的某一特征進(jìn)行測(cè)試吧趣，根據(jù)測(cè)試結(jié)果將實(shí)例分配到其子節(jié)點(diǎn)。這樣以后，每一個(gè)子節(jié)點(diǎn)對(duì)應(yīng)該特征的一個(gè)取值再菊。這樣不斷遞歸下去對(duì)實(shí)例進(jìn)行測(cè)試和分類爪喘，直至達(dá)到葉節(jié)點(diǎn)，最后將實(shí)例分到葉節(jié)點(diǎn)中纠拔。
其主要優(yōu)點(diǎn)有：1.分類速度快秉剑， 2.具有可讀性。
學(xué)習(xí)時(shí)稠诲，利用訓(xùn)練數(shù)據(jù)侦鹏，根據(jù)損失函數(shù)最小化的原則建立決策樹模型。預(yù)測(cè)時(shí)臀叙，對(duì)新數(shù)據(jù)集略水，利用決策樹模型進(jìn)行分類。
主要步驟：1.特征選擇劝萤， 2.決策樹的生成渊涝， 3.決策樹的剪枝。
決策樹的生成只考慮局部最優(yōu)床嫌，容易過(guò)擬合跨释。決策樹的修剪則考慮全局最優(yōu)。

2 ID3算法

2.1 數(shù)學(xué)原理

數(shù)學(xué)原理部分看博客：
http://www.cnblogs.com/pinard/p/6050306.html

2.2 算法思路

輸入的是m個(gè)樣本厌处，樣本輸出集合為D鳖谈，每個(gè)樣本有n個(gè)離散特征，特征集合即為A阔涉，輸出為決策樹T缆娃。
算法的過(guò)程為：

1)初始化信息增益的閾值?
2）判斷樣本是否為同一類輸出Di，如果是則返回單節(jié)點(diǎn)樹T瑰排。標(biāo)記類別為Di

3. 判斷特征是否為空贯要，如果是則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別凶伙。
   4）計(jì)算A中的各個(gè)特征（一共n個(gè)）對(duì)輸出D的信息增益郭毕，選擇信息增益最大的特征Ag
4. 如果Ag的信息增益小于閾值?它碎，則返回單節(jié)點(diǎn)樹T函荣，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別。
   6）否則扳肛，按特征Ag的不同取值A(chǔ)gi將對(duì)應(yīng)的樣本輸出D分成不同的類別Di傻挂。每個(gè)類別產(chǎn)生一個(gè)子節(jié)點(diǎn)。對(duì)應(yīng)特征值為Agi挖息。返回增加了節(jié)點(diǎn)的數(shù)T金拒。
   7）對(duì)于所有的子節(jié)點(diǎn)，令D=Di,A=A?{Ag}遞歸調(diào)用2-6步，得到子樹Ti并返回绪抛。

2.3 ID3算法的不足

1. 沒有考慮連續(xù)特征资铡，比如長(zhǎng)度、密度等連續(xù)值無(wú)法再ID3中運(yùn)用
2. ID3采用信息增益大的特征優(yōu)先建立決策樹的節(jié)點(diǎn)幢码。很快就被人發(fā)現(xiàn)笤休，在相同條件下，取值比較多的特征比取值少的特征信息增益大症副。比如一個(gè)變量有2個(gè)值店雅，各為1/2，另一個(gè)變量為3個(gè)值贞铣，各為1/3闹啦，其實(shí)他們都是完全不確定的變量，但是取3個(gè)值的比取2個(gè)值的信息增益大辕坝。
3. ID3未考慮缺失值
4. 未考慮過(guò)擬合問(wèn)題

3 C4.5算法

3.1 數(shù)學(xué)原理

和上面那個(gè)算法一樣窍奋，可以參考這個(gè)教程
http://www.cnblogs.com/pinard/p/6050306.html

3.2 C4.5的特點(diǎn)

該算法和ID3的算法思路基本一致，但它有效的解決了上述四個(gè)問(wèn)題酱畅。
首先费变，對(duì)于第一個(gè)問(wèn)題：不能處理連續(xù)特征。C4.5的思路是將連續(xù)的特征離散化圣贸。比如m個(gè)樣本的連續(xù)特征A有m個(gè)挚歧，從小到大排列為a1,a2,...,am,則C4.5取相鄰兩樣本值的平均數(shù)，一共取得m-1個(gè)劃分點(diǎn)吁峻。對(duì)于這m-1個(gè)點(diǎn)滑负，分別計(jì)算以該點(diǎn)作為二元分類點(diǎn)時(shí)的信息增益。選擇信息增益最大的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)用含。比如取到的增益最大的點(diǎn)為at,則小于at的值為類別1矮慕，大于at的值為類別2，這樣我們就做到了連續(xù)特征的離散化啄骇。要注意的是痴鳄，與離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為連續(xù)屬性缸夹，則該屬性后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過(guò)程痪寻。

對(duì)于第二個(gè)問(wèn)題，信息增益作為標(biāo)準(zhǔn)容易偏向于取值較多的特征虽惭。這里引入了信息增益比橡类。

enter description here

其中n為特征A的類別數(shù)， Di為特征A的第i個(gè)取值對(duì)應(yīng)的樣本個(gè)數(shù)芽唇。D為樣本個(gè)數(shù)顾画。
特征數(shù)越多的特征對(duì)應(yīng)的特征熵越大，它作為分母，可以校正信息增益容易偏向于取值較多的特征的問(wèn)題研侣。

對(duì)于第三個(gè)問(wèn)題谱邪，缺失值處理的問(wèn)題，主要需要解決的是兩個(gè)問(wèn)題庶诡，一是在樣本某些特征缺失的情況下選擇劃分的屬性虾标，二是選定了劃分屬性，對(duì)于在該屬性上缺失特征的樣本的處理灌砖。

對(duì)于第一個(gè)子問(wèn)題璧函，對(duì)于某一個(gè)有缺失特征值的特征A。C4.5的思路是將數(shù)據(jù)分成兩部分基显，對(duì)每個(gè)樣本設(shè)置一個(gè)權(quán)重（初始可以都為1）蘸吓，然后劃分?jǐn)?shù)據(jù)，一部分是有特征值A(chǔ)的數(shù)據(jù)D1撩幽，另一部分是沒有特征A的數(shù)據(jù)D2. 然后對(duì)于沒有缺失特征A的數(shù)據(jù)集D1來(lái)和對(duì)應(yīng)的A特征的各個(gè)特征值一起計(jì)算加權(quán)重后的信息增益比库继，最后乘上一個(gè)系數(shù)，這個(gè)系數(shù)是無(wú)特征A缺失的樣本加權(quán)后所占加權(quán)總樣本的比例窜醉。

對(duì)于第二個(gè)子問(wèn)題宪萄，可以將缺失特征的樣本同時(shí)劃分入所有的子節(jié)點(diǎn)，不過(guò)將該樣本的權(quán)重按各個(gè)子節(jié)點(diǎn)樣本的數(shù)量比例來(lái)分配榨惰。比如缺失特征A的樣本a之前權(quán)重為1拜英，特征A有3個(gè)特征值A(chǔ)1,A2,A3。 3個(gè)特征值對(duì)應(yīng)的無(wú)缺失A特征的樣本個(gè)數(shù)為2,3,4.則a同時(shí)劃分入A1琅催，A2居凶，A3。對(duì)應(yīng)權(quán)重調(diào)節(jié)為2/9,3/9, 4/9藤抡。

對(duì)于第4個(gè)問(wèn)題侠碧，C4.5引入了正則化系數(shù)進(jìn)行初步的剪枝。

3.3 C4.5算法的不足

1.因?yàn)闆Q策樹算法特別容易過(guò)擬合缠黍，所以對(duì)于生成的決策數(shù)一定要進(jìn)行剪枝
2.C4.5生成的是多叉樹弄兜，一個(gè)父節(jié)點(diǎn)可以對(duì)于多個(gè)子節(jié)點(diǎn)，這樣的結(jié)構(gòu)會(huì)比二叉樹的效率低瓷式。
3.C4.5只能用于分類
4.C4.5由于使用了熵模型替饿，里面有大量的耗時(shí)的對(duì)數(shù)運(yùn)算,如果是連續(xù)值還有大量的排序運(yùn)算。

4 CART算法

4.1 算法原理

http://www.cnblogs.com/pinard/p/6053344.html

在這里CART算法選擇了基尼系數(shù)作為特征選擇的標(biāo)準(zhǔn)蒿往，基尼系數(shù)代表了模型的不純度盛垦，基尼系數(shù)越小湿弦，則不純度越低瓤漏，特征越好。
相對(duì)于熵模型的表達(dá)式，基尼系數(shù)的計(jì)算為二次運(yùn)算蔬充，比對(duì)數(shù)運(yùn)算要簡(jiǎn)單一些蝶俱，并且為了簡(jiǎn)化運(yùn)算，CART算法每次僅對(duì)某個(gè)特征值的值進(jìn)行二分類饥漫，這樣建立起來(lái)的就是一棵二叉樹榨呆，并且可以簡(jiǎn)化運(yùn)算。

4.2 CART對(duì)于連續(xù)值和離散值處理的改進(jìn)

對(duì)于CART分類樹連續(xù)值的處理問(wèn)題庸队，其思想和C4.5是相同的积蜻，都是將連續(xù)的特征離散化。唯一的區(qū)別在于在選擇劃分點(diǎn)時(shí)的度量方式不同彻消，C4.5使用的是信息增益比竿拆，則CART分類樹使用的是基尼系數(shù)。

對(duì)于離散值的處理采用的思路是不停的二分離散特征宾尚”瘢回憶下ID3或者C4.5，如果某個(gè)特征A被選取建立決策樹節(jié)點(diǎn)煌贴，如果它有A1,A2,A3三種類別御板，我們會(huì)在決策樹上一下建立一個(gè)三叉的節(jié)點(diǎn)。這樣導(dǎo)致決策樹是多叉樹牛郑。但是CART分類樹使用的方法不同怠肋，他采用的是不停的二分，還是這個(gè)例子淹朋，CART分類樹會(huì)考慮把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三種情況灶似，找到基尼系數(shù)最小的組合，比如{A2}和{A1,A3},然后建立二叉樹節(jié)點(diǎn)瑞你，一個(gè)節(jié)點(diǎn)是A2對(duì)應(yīng)的樣本酪惭，另一個(gè)節(jié)點(diǎn)是{A1,A3}對(duì)應(yīng)的節(jié)點(diǎn)。同時(shí)者甲，由于這次沒有把特征A的取值完全分開春感，后面我們還有機(jī)會(huì)在子節(jié)點(diǎn)繼續(xù)選擇到特征A來(lái)劃分A1和A3。這和ID3或者C4.5不同虏缸，在ID3或者C4.5的一棵子樹中鲫懒，離散特征只會(huì)參與一次節(jié)點(diǎn)的建立。

4.3 分類樹的生成

算法輸入是訓(xùn)練集D刽辙，基尼系數(shù)的閾值窥岩，樣本個(gè)數(shù)閾值。
輸出是決策樹T宰缤。
我們的算法從根節(jié)點(diǎn)開始颂翼，用訓(xùn)練集遞歸的建立CART樹晃洒。

1. 對(duì)于當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)集為D，如果樣本個(gè)數(shù)小于閾值或者沒有特征朦乏，則返回決策子樹球及，當(dāng)前節(jié)點(diǎn)停止遞歸。
2. 計(jì)算樣本集D的基尼系數(shù)呻疹，如果基尼系數(shù)小于閾值吃引，則返回決策樹子樹，當(dāng)前節(jié)點(diǎn)停止遞歸刽锤。
3. 計(jì)算當(dāng)前節(jié)點(diǎn)現(xiàn)有的各個(gè)特征的各個(gè)特征值對(duì)數(shù)據(jù)集D的基尼系數(shù)镊尺，對(duì)于離散值和連續(xù)值的處理方法和基尼系數(shù)的計(jì)算見第二節(jié)。缺失值的處理方法和上篇的C4.5算法里描述的相同并思。
4. 在計(jì)算出來(lái)的各個(gè)特征的各個(gè)特征值對(duì)數(shù)據(jù)集D的基尼系數(shù)中鹅心，選擇基尼系數(shù)最小的特征A和對(duì)應(yīng)的特征值a。根據(jù)這個(gè)最優(yōu)特征和最優(yōu)特征值纺荧，把數(shù)據(jù)集劃分成兩部分D1和D2旭愧，同時(shí)建立當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)，做節(jié)點(diǎn)的數(shù)據(jù)集D為D1宙暇，右節(jié)點(diǎn)的數(shù)據(jù)集D為D2.
5. 對(duì)左右的子節(jié)點(diǎn)遞歸的調(diào)用1-4步输枯，生成決策樹。

對(duì)于生成的決策樹做預(yù)測(cè)的時(shí)候占贫，假如測(cè)試集里的樣本A落到了某個(gè)葉子節(jié)點(diǎn)桃熄，而節(jié)點(diǎn)里有多個(gè)訓(xùn)練樣本。則對(duì)于A的類別預(yù)測(cè)采用的是這個(gè)葉子節(jié)點(diǎn)里概率最大的類別型奥。

4.4 回歸樹的生成

ART回歸樹和CART分類樹的建立算法大部分是類似的瞳收，所以這里我們只討論CART回歸樹和CART分類樹的建立算法不同的地方。

首先厢汹，我們要明白螟深，什么是回歸樹，什么是分類樹烫葬。兩者的區(qū)別在于樣本輸出界弧，如果樣本輸出是離散值，那么這是一顆分類樹搭综。如果果樣本輸出是連續(xù)值垢箕，那么那么這是一顆回歸樹。

除了概念的不同兑巾，CART回歸樹和CART分類樹的建立和預(yù)測(cè)的區(qū)別主要有下面兩點(diǎn)：

1)連續(xù)值的處理方法不同

2)決策樹建立后做預(yù)測(cè)的方式不同条获。

對(duì)于連續(xù)值的處理，我們知道CART分類樹采用的是用基尼系數(shù)的大小來(lái)度量特征的各個(gè)劃分點(diǎn)的優(yōu)劣情況蒋歌。這比較適合分類模型帅掘，但是對(duì)于回歸模型委煤，我們使用了常見的和方差的度量方式，CART回歸樹的度量目標(biāo)是锄开，對(duì)于任意劃分特征A素标，對(duì)應(yīng)的任意劃分點(diǎn)s兩邊劃分成的數(shù)據(jù)集D1和D2称诗，求出使D1和D2各自集合的均方差最小萍悴，同時(shí)D1和D2的均方差之和最小所對(duì)應(yīng)的特征和特征值劃分點(diǎn)。表達(dá)式為：

enter description here

其中寓免，c1為D1數(shù)據(jù)集的樣本輸出均值癣诱，c2為D2數(shù)據(jù)集的樣本輸出均值。
對(duì)于決策樹建立后做預(yù)測(cè)的方式袜香，上面講到了CART分類樹采用葉子節(jié)點(diǎn)里概率最大的類別作為當(dāng)前節(jié)點(diǎn)的預(yù)測(cè)類別撕予。而回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數(shù)來(lái)預(yù)測(cè)輸出結(jié)果蜈首。

4.5 CART算法的剪枝

參考博客http://www.cnblogs.com/pinard/p/6053344.html

4.6 CART算法小結(jié)

enter description here

5 決策樹中的剪枝

5.1 預(yù)剪枝

預(yù)剪枝主要是再節(jié)點(diǎn)進(jìn)行擴(kuò)展之前实抡，先計(jì)算當(dāng)前的劃分是否能帶來(lái)模型泛化能力的提升，若不能欢策，則停止生長(zhǎng)吆寨。
停止樹生長(zhǎng)的方法：

1)當(dāng)樹到達(dá)一定深度的時(shí)候，停止書的生長(zhǎng)
2)當(dāng)?shù)竭_(dá)當(dāng)前節(jié)點(diǎn)的樣本數(shù)量小于某個(gè)閾值時(shí)踩寇，停止樹的生長(zhǎng)
3)計(jì)算每次分裂對(duì)測(cè)試集準(zhǔn)確度提升啄清。當(dāng)小于某個(gè)閾值時(shí)，不再生長(zhǎng)

這種方法思想簡(jiǎn)單俺孙、算法簡(jiǎn)單辣卒、效率高，適于處理大規(guī)模數(shù)據(jù)睛榄。但如何準(zhǔn)確地估計(jì)何時(shí)停止樹的生長(zhǎng)（即上述方法中的深度或閾值）荣茫，針對(duì)不同問(wèn)題會(huì)有很大差別，需要一定經(jīng)驗(yàn)判斷场靴。且預(yù)剪枝存在一定局限性计露，有欠擬合的風(fēng)險(xiǎn)，雖然當(dāng)前的劃分會(huì)導(dǎo)致測(cè)試集準(zhǔn)確率降低憎乙，但在之后的劃分中票罐，準(zhǔn)確率可能會(huì)有顯著上升。

5.2后剪枝

后剪枝的核心思想是讓算法生成一棵完全生長(zhǎng)的決策樹泞边，然后從最
底層向上計(jì)算是否剪枝该押。剪枝過(guò)程將子樹刪除，用一個(gè)葉子結(jié)點(diǎn)替代阵谚，該結(jié)點(diǎn)的類別同樣按照多數(shù)投票的原則進(jìn)行判斷蚕礼。同樣地烟具，后剪枝也可以通過(guò)在測(cè)試集上的準(zhǔn)確率進(jìn)行判斷，如果剪枝過(guò)后準(zhǔn)確率有所提升奠蹬，則進(jìn)行剪枝朝聋。相比于預(yù)剪枝，后剪枝方法通扯谠辏可以得到泛化能力更強(qiáng)的決策樹冀痕，但時(shí)間開銷會(huì)更大。

常見的后剪枝方法包括錯(cuò)誤率降低剪枝（Reduced Error Pruning狸演，
REP）言蛇、悲觀剪枝（Pessimistic Error Pruning，PEP）宵距、代價(jià)復(fù)雜度剪枝（Cost ComplexityPruning腊尚，CCP）、最小誤差剪枝（Minimum Error Pruning满哪，MEP）婿斥、CVP（Critical Value Pruning）、OPP（Optimal
Pruning）等方法哨鸭，這些剪枝方法各有利弊民宿，關(guān)注不同的優(yōu)化角度，下面選取著名的CART剪枝方法CCP進(jìn)行介紹兔跌。

代價(jià)復(fù)雜剪枝主要包含以下兩個(gè)步驟勘高。
（1）從完整決策樹T0開始，生成一個(gè)子樹序列{T0,T1,T2,...,Tn}坟桅，
其中Ti +1由Ti生成华望，Tn為樹的根結(jié)點(diǎn)。
（2）在子樹序列中仅乓，根據(jù)真實(shí)誤差選擇最佳的決策樹赖舟。

對(duì)于步驟(1)主要以以下方式進(jìn)行計(jì)算：

誤差增加率公式

其中α代表誤差增加率，R(t)代表剪枝后的誤差夸楣，R(T)代表剪枝前的樹的誤差宾抓，|L(T)|代表葉子節(jié)點(diǎn)個(gè)數(shù)。
下面舉個(gè)例子來(lái)說(shuō)明：
女孩需要對(duì)80個(gè)人進(jìn)行見或不見的分類豫喧。假設(shè)根據(jù)某種規(guī)則石洗，已經(jīng)得到了一棵CART決策樹T 0 ，如圖1所示紧显。

圖1

此時(shí)共5個(gè)內(nèi)部結(jié)點(diǎn)可供考慮讲衫，其中

enter description here

可見α(t3)最小，因此對(duì)t3進(jìn)行剪枝孵班，得到新的子樹T1涉兽，如圖2所示招驴。

圖2

而后繼續(xù)計(jì)算所有結(jié)點(diǎn)對(duì)應(yīng)的誤差增加率，分別為α(t1)=3枷畏，α(t2)=3别厘，α(t4)=4。因此對(duì)t1進(jìn)行剪枝拥诡，得到T2触趴，如圖3所示。此時(shí)α(t0)=6.5袋倔，α(t2)=3雕蔽，選擇t2進(jìn)行剪枝折柠，得到T3宾娜。于是只剩下一個(gè)內(nèi)部結(jié)點(diǎn)，即根結(jié)點(diǎn)扇售，得到T4 前塔。

圖3

在步驟(2)中:
我們需要從子樹序列中選出真實(shí)誤差最小的決策
樹。CCP給出了兩種常用的方法：
一種是基于獨(dú)立剪枝數(shù)據(jù)集承冰，該方法與REP類似华弓，但由于其只能從子樹序列{T0,T1,T2,...,Tn}中選擇最佳決策樹，而非像REP能在所有可能的子樹中尋找最優(yōu)解困乒，因此性能上會(huì)有一定不足寂屏。
另一種是基于k折交叉驗(yàn)證，將數(shù)據(jù)集分成k份娜搂，前k?1份用于生成決策樹迁霎，最后一份用于選擇最優(yōu)的剪枝樹。重復(fù)進(jìn)行N次百宇，再?gòu)倪@N個(gè)子樹中選擇最優(yōu)的子樹考廉。

6 決策樹算法小結(jié)

決策樹算法作為一個(gè)大類別的分類回歸算法的優(yōu)缺點(diǎn)。這部分總結(jié)于scikit-learn的英文文檔携御。
決策樹算法的優(yōu)點(diǎn)：

1）簡(jiǎn)單直觀昌粤，生成決策樹很直觀。
2）基本不需要預(yù)處理啄刹，不需要提前歸一化涮坐，處理缺失值。
3）使用決策樹預(yù)測(cè)的代價(jià)是O(log2m)誓军。 m為樣本數(shù)袱讹。
4）既可以處理離散值也可以處理連續(xù)值。很多算法只是專注于離散值或者連續(xù)值谭企。
5）可以處理多維度輸出的分類問(wèn)題廓译。
6）相比于神經(jīng)網(wǎng)絡(luò)之類的黑盒分類模型评肆，決策樹在邏輯上可以得到很好的解釋
7）可以交叉驗(yàn)證的剪枝來(lái)選擇模型，從而提高泛化能力非区。
8） 對(duì)于異常點(diǎn)的容錯(cuò)能力好瓜挽，健壯性高。

決策樹算法的缺點(diǎn)

1）決策樹算法非常容易過(guò)擬合征绸，導(dǎo)致泛化能力不強(qiáng)久橙。可以通過(guò)設(shè)置節(jié)點(diǎn)最少樣本數(shù)量和限制決策樹深度來(lái)改進(jìn)管怠。
2）決策樹會(huì)因?yàn)闃颖景l(fā)生一點(diǎn)點(diǎn)的改動(dòng)淆衷，就會(huì)導(dǎo)致樹結(jié)構(gòu)的劇烈改變。這個(gè)可以通過(guò)集成學(xué)習(xí)之類的方法解決渤弛。
3）尋找最優(yōu)的決策樹是一個(gè)NP難的問(wèn)題祝拯，我們一般是通過(guò)啟發(fā)式方法，容易陷入局部最優(yōu)她肯〖淹罚可以通過(guò)集成學(xué)習(xí)之類的方法來(lái)改善。
4）有些比較復(fù)雜的關(guān)系晴氨，決策樹很難學(xué)習(xí)康嘉，比如異或。這個(gè)就沒有辦法了籽前，一般這種關(guān)系可以換神經(jīng)網(wǎng)絡(luò)分類方法來(lái)解決亭珍。
5）如果某些特征的樣本比例過(guò)大，生成決策樹容易偏向于這些特征枝哄。這個(gè)可以通過(guò)調(diào)節(jié)樣本權(quán)重來(lái)改善肄梨。

7 統(tǒng)計(jì)學(xué)習(xí)方法相關(guān)習(xí)題答案

可以參考這個(gè)博客https://blog.csdn.net/familyshizhouna/article/details/72551841

這里擺下5.2題的答案和代碼

enter description here

分類圖

enter description here

代碼實(shí)現(xiàn)

# 生成最小二乘回歸樹
import numpy as np
y = np.array([4.5, 4.75, 4.91, 5.34, 5.80, 7.05, 7.90, 8.23, 8.70, 9.00])
def CART(start, end, y):
    # 如果數(shù)組長(zhǎng)度不大于1則繼續(xù)進(jìn)行
    if (end - start) > 1:
        result = []          # 創(chuàng)建數(shù)組用來(lái)存儲(chǔ)每次的結(jié)果
        for i in range(start, end+1,1):
            c1 = [np.mean(y[start:i+1])]     # 算第一部分的平均值
            c2 = [np.mean(y[i+1:end+1])]    # 算第二部分的平均值
            y1 = y[start:i+1]                
            y2 = y[i+1:end+1]
            result.append((sum((y1 - c1)**2) + sum((y2 - c2)**2)))
        index = np.argmin(result) + start
        print(index, '******', np.mean(y[start:index+1]), '******', np.mean(y[index+1:end+1]))
        # 遞歸生成左右子樹
        CART(start, index, y)
        CART(index+1, end, y)
    else:
        return None        

結(jié)果

enter description here

8 sklearn中運(yùn)用決策樹

# 導(dǎo)入包
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

# 導(dǎo)入數(shù)據(jù)集
data = pd.read_csv('Social_Network_Ads.csv')
pd.head()

查看數(shù)據(jù)集

# 劃分?jǐn)?shù)據(jù)集，并將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集
X = data.iloc[:,[2,3]].values()
y = data.iloc[:,-1].values

from skearn.model_selection import train_test_split
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size = 0.25, random_state = 0)

# 進(jìn)行特征縮放
from skleran.processing import StandardScaler
sc = StandardScaler()
X_train = sc.fit_transform(X_train)
X_test = sc.transform(X_test)

# 對(duì)測(cè)試數(shù)據(jù)集進(jìn)行擬合分類,并且輸出對(duì)測(cè)試集的結(jié)果
from skleran.tree import DecisionTreeClassfier
clf = DecisionTreeClassifer
clf.fit(X_train, y_train)

y_pred = clf.predict(X_test)

# 建立混淆矩陣
# 混淆矩陣被用于在分類問(wèn)題上對(duì)準(zhǔn)確率的一種評(píng)估形式膘格，我們經(jīng)常通過(guò)
# 觀察混淆矩陣的對(duì)角線來(lái)評(píng)估出模型的分類效果峭范，最理想的結(jié)果就是所有的數(shù)據(jù)都在對(duì)角線上，那么說(shuō)明分類精度最高
from sklearn.metrics import confusion_matrix
cm = confusion_matrix(y_test, y_pred)

# 將訓(xùn)練數(shù)據(jù)集可視化
from matplotlib.colors import ListedColormap
X_set, y_set = X_train, y_train
X1, X2 = np.meshgrid(np.arange(start = X_set[:, 0].min() - 1 ,stop = X_set[:,0].max() + 1,step = 0.01),np.arange(strat = X_set[:,1].min() - 1,X_set[:,1].max() + 1,step = 0.01))
plt.contourf(X1, X2, clf.predict(np.array([X1.ravel(),X2.ravel()]).T).reshape(X1.shape),alpha = 0.75, cmap = ListedColormap(('red','gree')))
### 畫出散點(diǎn)圖
for i, j in range(np.unique(y_set)):
    plt.scatter(X_set[y_set == j, 0], X_set[y_set == j, 1],
    c = ListColormap(('red', 'green'))(i), label = j)
plt.title('Decision Tree Classification (Training set)')
plt.xlabel('Age')
plt.ylabel('Estimated Salary')
plt.legend()
plt.show()

enter description here

# 將測(cè)試數(shù)據(jù)集可視化
X_set2, y_set2 = X_test, Y_test
T1, T2 = np.meshgrid(np.arange(start = X_set2[:,0].min()-1, stop=X_set2[:,0].max()+1,step = 0.01),
                     np.arange(start = X_set2[:,1].min()-1, stop=X_set2[:,1].max()+1,step = 0.01))
plt.contourf(T1,T2,clf.predict(np.array([T1.ravel(),T2.ravel()]).T).reshape(T1.shape),
            alpha = 0.75, cmap = ListedColormap(('red', 'green')))
plt.xlim(T1.min(), T1.max())
plt.ylim(T2.min(), T2.max())
for i, j in enumerate(np.unique(y_set2)):
    plt.scatter(X_set2[y_set2 == j, 0], X_set2[y_set2 == j, 1],
               c = ListedColormap(('red', 'green'))(i), label = j)
plt.title('Decision Tree Classification (Test set)')
plt.xlabel('Age')
plt.ylabel('Estimated Salary')
plt.legend()
plt.show()

enter description here