基本流程
決策樹是一種常用的機(jī)器學(xué)習(xí)方法轮傍，過程類似于樹狀結(jié)構(gòu)每一層通過對(duì)屬性進(jìn)行決策來進(jìn)行分類暂雹。
結(jié)構(gòu)主要有：根節(jié)點(diǎn)（初始的所有數(shù)據(jù)集），內(nèi)部節(jié)點(diǎn)（初步?jīng)Q策結(jié)果）创夜，葉節(jié)點(diǎn)（最終決策結(jié)果）杭跪，路徑（判定決策過程）。
決策樹學(xué)習(xí)基本算法：
輸入：訓(xùn)練集D,屬性集A={a1,a2,...,ad}
過程：函數(shù)TreeGenerate(D,A)
生成節(jié)點(diǎn)node:
if D中樣本全屬于統(tǒng)一類別C then
將node標(biāo)記為C類葉節(jié)點(diǎn);return
end if
if A=空集 or D中樣本在A上取值相同 then
將node標(biāo)記為葉節(jié)點(diǎn)，類別標(biāo)記為D中最多的類;return
end if
從A中選擇最優(yōu)劃分屬性a*;
for a* 的每一個(gè)取值a*v do
為node生成一個(gè)分支;另Dv表示D在a*上取值為a*v的樣本子集;
if Dv為空 then
將分支節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)涧尿，類別標(biāo)記為D中最多的類;return
else
以TreeGenerate(Dv,A\{a*})為分支節(jié)點(diǎn)
end if
end for
輸出：以node為根節(jié)點(diǎn)的一顆決策樹
這個(gè)是一個(gè)遞歸過程系奉，其中有三種情況導(dǎo)致遞歸返回：
- 當(dāng)前節(jié)點(diǎn)所有樣本屬于同一類，不用再劃分
- 當(dāng)前節(jié)點(diǎn)屬性集空姑廉，不能再劃分（當(dāng)前節(jié)點(diǎn)的后驗(yàn)分布）
- 當(dāng)前節(jié)點(diǎn)樣本集為空缺亮，不能再劃分（將父節(jié)點(diǎn)的分布當(dāng)成當(dāng)前節(jié)點(diǎn)的先驗(yàn)分布）
劃分選擇
什么樣的劃分屬性是最優(yōu)的？劃分后的結(jié)點(diǎn)中樣本的純度因該是比劃分前高的桥言。因此萌踱，引入了信息熵即度量樣本集合純度的指標(biāo)，樣本集合的信息熵定義為：
其中為第
類樣本所占的比例号阿。信息熵的值越小并鸵，
的純度越高。
當(dāng)根據(jù)某一屬性扔涧，對(duì)
進(jìn)行劃分后园担，形成的多個(gè)子結(jié)點(diǎn)的信息熵就是
。為了比較前后的信息熵變化枯夜，定義信息增益：
其中為每個(gè)分支點(diǎn)的權(quán)重弯汰。信息增益越大，就表明通過屬性
劃分得到的子結(jié)點(diǎn)的純度提升越大卤档。
同時(shí)注意到一個(gè)問題蝙泼，信息增益作為度量的時(shí)候，對(duì)于取值數(shù)目多的屬性具有偏愛性劝枣，比如樣本序號(hào)（1汤踏，2，3舔腾，4溪胶，5），如果作為一種劃分屬性稳诚，得到的結(jié)果純度達(dá)到哗脖，但是卻不具有對(duì)新樣本的預(yù)測(cè)能力。因此引入增益率:
其中：
但是扳还，增益率對(duì)于取值數(shù)目少的屬性具有偏愛性才避，因此長使用一種啟發(fā)式：先挑選信息增益高于平均水平的屬性，然后在選取增益率最高的屬性氨距。
CART決策樹是一種著名的決策樹學(xué)習(xí)算法桑逝，分類和回歸任務(wù)都可用。它使用“基尼指數(shù)”來選擇劃分屬性俏让。D的基尼值度量為：
指從D中隨機(jī)抽取兩個(gè)樣本不同類的概率楞遏，越小茬暇，D的純度越高。
屬性的基尼指數(shù)定義為：
使得劃分后基尼指數(shù)最小的屬性為最優(yōu)屬性寡喝。
剪枝處理
剪枝指對(duì)決策樹進(jìn)行枝干的修剪糙俗，為了應(yīng)對(duì)過擬合現(xiàn)象。分為以下兩種：
- 預(yù)剪枝
預(yù)剪枝是在決策樹形成的過程中预鬓，根據(jù)結(jié)點(diǎn)劃分是否提升決策樹整體的泛化性能來決定巧骚。這種方法計(jì)算量比較小，但是因?yàn)槠湄澙诽匦陨好螅赡軐?dǎo)致欠擬合（一些后續(xù)劃分提升泛化性能的枝网缝，會(huì)因?yàn)槌跏紕澐植荒芴嵘夯阅芏髿ⅲ?/li> - 后剪枝
后剪枝是在決策樹形成后，自下而上蟋定，根據(jù)非葉結(jié)點(diǎn)替換為葉節(jié)點(diǎn)是否提高決策樹泛化性能來決定是否替換粉臊。這種方法計(jì)算量比較大，但是不會(huì)欠擬合驶兜，而且多數(shù)情況比預(yù)剪枝的泛化性能要強(qiáng)扼仲。
連續(xù)與缺失值
- 連續(xù)值處理
對(duì)于給定的數(shù)據(jù)集D，連續(xù)屬性抄淑，并不能像離散指那樣直接按照取值進(jìn)行劃分屠凶。因此，將連續(xù)屬性的所有取值進(jìn)行肆资，從小到大的排序矗愧，然后
之間任意的取值劃分效果相同，所以候選劃分點(diǎn)集合為：
然后就可以按照離散屬性值一樣來考察這些劃分點(diǎn)郑原，選取最優(yōu)劃分點(diǎn)唉韭。例如：
注意，與離散值不同的是犯犁，連續(xù)屬性在劃分后的后代結(jié)點(diǎn)還可繼續(xù)劃分属愤。 - 缺失值處理
給定數(shù)據(jù)集，缺失屬性
酸役，
表示屬性
表示
表示
問題主要是在存在屬性值缺失的情況下贱呐，選擇劃分屬性，并且進(jìn)行劃分入桂。先要進(jìn)行準(zhǔn)備工作：
首先吼句，每個(gè)樣本初始化權(quán)重（取值1），然后定義：
根據(jù)這些式子就可以將信息增益推廣：
其中：
劃分的過程中事格，樣本在屬性逢捺。
多變量決策樹
多變量決策樹在劃分的時(shí)候不再是針對(duì)一個(gè)屬性谁鳍，而是針對(duì)多個(gè)屬性的組合。
我們把每個(gè)屬性看做一個(gè)坐標(biāo)軸劫瞳，個(gè)屬性的樣本就對(duì)應(yīng)了
維空間中的一個(gè)點(diǎn)倘潜，分類就相當(dāng)與尋找一個(gè)邊界將點(diǎn)劃分開。決策樹的劃分有個(gè)特點(diǎn)就是志于，形成的劃分界面是多段與坐標(biāo)軸平行的線段組成（單每層單屬性劃分）涮因。每一段對(duì)應(yīng)了某個(gè)屬性的取值，解釋性強(qiáng)伺绽，但是運(yùn)算量比較大养泡。因此想要通過平滑的斜線來代替這些線段，這樣可以簡化模型奈应，同時(shí)達(dá)到分類效果澜掩，即每次劃分采用多屬性的組合：
其中為屬性
的權(quán)重，
代表線性分類器杖挣，
和
都可以在該結(jié)點(diǎn)對(duì)應(yīng)樣本集和屬性集上學(xué)得肩榕。
