Decision tree(決策樹)
決策樹可以分為回歸樹或分類樹趣苏，決策樹容易o(hù)verfitting年柠。
常決策樹主要有三種實(shí)現(xiàn)凿歼，分別是ID3算法褪迟，CART算法和C4.5算法冗恨。
這邊我們用data science from scratch的例子來講講決策樹，首先我們有一組數(shù)據(jù)味赃，這是來應(yīng)徵者的應(yīng)徵資料(feature特徵)及面試後是否被錄用(label標(biāo)籤)掀抹。
我們想從過往數(shù)據(jù)經(jīng)由特徵將它正確分類到各種標(biāo)籤，未來依據(jù)特徵判斷是否錄用心俗，在決策樹中我們會(huì)建立決策路徑來表示樹的結(jié)構(gòu)傲武。
我們?nèi)绾谓Q策路徑呢?首先會(huì)先決定一個(gè)問題，例如""它們的應(yīng)徵職等是甚麼城榛，那就是分成3種Junior揪利、Mid、Senior""狠持，然後將資料依問題劃分成不同群組疟位，如果問完問題還沒不同群組中如果還有不同類別(錄用、不錄用)混再一起則再?zèng)Q定一個(gè)問題進(jìn)行切分喘垂，直到所有群組都能各自被分為標(biāo)籤(錄用甜刻、不錄用)為止。
樹中每個(gè)問題叫做決策節(jié)點(diǎn)(decision node)正勒、被已分類的標(biāo)籤叫做葉節(jié)點(diǎn)(leaf node)得院。
CART算法
CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程，對(duì)回歸樹用平方誤差最小化準(zhǔn)則章贞，對(duì)分類樹用基尼指數(shù)最小化準(zhǔn)則祥绞，進(jìn)行特徵選擇，生成二叉樹鸭限。
CART是一種二分遞歸分割技術(shù)蜕径，把當(dāng)前樣本劃分為兩個(gè)子樣本，使得生成的每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)分支里覆，因此CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹丧荐。
由於CART構(gòu)成的是一個(gè)二叉樹，它在每一步的決策時(shí)只能是「是」或者「否」喧枷，把數(shù)據(jù)分為兩部分虹统。
在CART算法中主要分為兩個(gè)步驟：
- 將樣本遞歸劃分進(jìn)行建樹
- 用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝
- 離散型變量如何進(jìn)行遞歸建立二叉樹弓坞？
選一個(gè)自變量，再選取的一個(gè)值车荔，把維空間劃分為兩部分渡冻，對(duì)非連續(xù)變量來說屬性值的取值只有兩個(gè)，即等於該值或不等於該值忧便。
ps. 如果特徵有多類別將割成多份各自分為"是某類"與"不是某類"族吻。貪婪演算法會(huì)選擇不純度或亂度最小的劃分
首先我們要知道如何衡量劃分好壞，我們可以使用entropy(熵)或Gini(不純度)珠增，不純度或亂度越低越好超歌。
Gini(不純度)：假設(shè)我們有K個(gè)類，樣本點(diǎn)屬於第k個(gè)類的概率為
計(jì)算資料的不純度蒂教，=第k類在所有樣本中的總數(shù)(
) ／ 所有樣本數(shù) (
)巍举。
資料(D)樣本數(shù)切分後為()樣本數(shù)與(
)樣本數(shù)，A表示某切分法(例如以職等切分)凝垛，我們將切分後資料各自計(jì)算不純度後再各自乘以他們資料在總資料的比例懊悯，最後加總起來的值就為切分不純度。
而我們就是要找到切分後不純度為最小的A(切分方法)梦皮。
我們用phd(是否為博士)做切分來計(jì)算炭分，先算D1(phd=yes)、D2(phd=no)
- 遞歸處理剑肯，將上面得到的兩部分按步驟(1)(2)重新選取一個(gè)屬性繼續(xù)劃分捧毛，直到把整個(gè)空間都劃分完。
- 連續(xù)型變量如何進(jìn)行遞歸建立二叉樹退子？
我們希望劃分後的數(shù)據(jù)集盡的值可能是集中的岖妄，接近訓(xùn)練樣本的y值(標(biāo)籤)，所以我們對(duì)切分後的兩個(gè)集合做的y與切分?jǐn)?shù)據(jù)的平均y值(c)做MSE寂祥，加總起來求最小值荐虐，平均值越集中l(wèi)oss越低。
- 遍歷變量
(特徵的中的一個(gè)連續(xù)值變量丸凭，例如身高)福扬，對(duì)固定的切分變量
，選擇使式子最小的(
)惜犀。
是被劃分的後輸入空間(劃分後的資料集合)
是
中對(duì)應(yīng)標(biāo)籤的平均值铛碑。
- 用選定的對(duì)(
CART回歸樹的生成是一個(gè)貪心選擇最優(yōu)分割點(diǎn)的過程莉御，這種貪心策略在一定程度上使得最開始生成的CART樹具有很多缺點(diǎn)撇吞，這表現(xiàn)在樹容易將噪聲也擬合進(jìn)去俗冻，出現(xiàn)過擬合，以及訓(xùn)練容易陷入局部最優(yōu)等牍颈。為此迄薄，需要在樹生成後進(jìn)行一定的處理，這就是剪枝的目的煮岁。
剪枝
實(shí)際使用CART樹時(shí)讥蔽，常常將訓(xùn)練數(shù)據(jù)分為訓(xùn)練集和剪枝的數(shù)據(jù)集
- 預(yù)剪枝(Pre-Pruning):
通過調(diào)整樹停止生長的策略，如提前終止樹生長（通過調(diào)整均方誤差下降的最小值實(shí)現(xiàn)）等可實(shí)現(xiàn)画机。 - 後剪枝(Post-Pruning):
將數(shù)據(jù)根據(jù)訓(xùn)練好的樹模型將數(shù)據(jù)集遞歸地分割到葉子結(jié)點(diǎn)冶伞，然後考慮減去葉子和不剪去葉子兩種情況下數(shù)據(jù)集的均方誤差值，如果剪枝使得該值變小色罚，則剪之碰缔，否則放棄账劲。遍歷所有結(jié)點(diǎn)戳护，剪去所有冗餘的枝條，就實(shí)現(xiàn)了後剪枝瀑焦。
