流程

根結(jié)點(diǎn) 包含樣本全集

結(jié)點(diǎn) 對(duì)應(yīng)一個(gè)屬性測(cè)試

子結(jié)點(diǎn) 包含結(jié)點(diǎn)中屬性測(cè)試的結(jié)果

葉結(jié)點(diǎn) 對(duì)應(yīng)決策結(jié)果

決策樹(shù)需進(jìn)行學(xué)習(xí)過(guò)程和預(yù)測(cè)過(guò)程

學(xué)習(xí)過(guò)程：通過(guò)對(duì)訓(xùn)練樣本的分析來(lái)確定 劃分屬性(內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的屬性)

預(yù)測(cè)過(guò)程：從根結(jié)點(diǎn)開(kāi)始沟娱，沿著劃分屬性構(gòu)成的 判定順序列 進(jìn)行屬性值判別 直到葉結(jié)點(diǎn)

可用于回歸任務(wù)（只用得出預(yù)測(cè)值）的決策樹(shù)算法

三種停止條件

1桃漾、樣本為同一類別耸序，沒(méi)有需要?jiǎng)澐值膶傩粤?/p>

2袁梗、有屬性但是全部樣本屬性值一樣無(wú)需劃分

3、沒(méi)有樣本

學(xué)習(xí)過(guò)程

對(duì)劃分屬性(結(jié)點(diǎn))的選擇

信息增益

Y是類別

K類是指結(jié)果類別

P是每類別的占比

信息熵是所有 plog2p的總和

信息增益是 劃分前的信息熵 - 劃分后的信息熵（分支結(jié)點(diǎn)的信息熵 ：p變?yōu)槊糠N種屬性值內(nèi)類別占比 plog2p 再乘該屬性值集合占比的和）

信息增益最大（分支結(jié)點(diǎn)的信息熵最小惭每，每種類別的概率泄嵌觥）的屬性被選為劃分屬性（信息增益越大，則意味著使周屬性 α 來(lái)進(jìn)行劃分所獲得的"純 度提升"越大）

信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好台腥，為減少這種 偏好可能帶來(lái)的不利影響宏赘，著名的 C4.5 決策樹(shù)算法 [Quinlan， 1993J 不直接使 用信息增益黎侈，而是使用"增益率"

屬性信息熵(負(fù)數(shù)）越小的時(shí)候增益率越大? 因此增益率準(zhǔn)則對(duì)可取值數(shù)目較少的屬性有所偏

C4.5 算法并不是直接選擇增益率最大的候選劃分屬性察署，而是使用了一個(gè)啟發(fā)式先從候選劃分屬性中找出信息增益高于平均水平的屬性，再?gòu)?中選擇增益率最高的.

基尼指數(shù)

基尼值等于 正例比率和反例比率的積

反映了從數(shù)據(jù)集 D 中隨機(jī)抽取兩個(gè)樣本峻汉，其類別標(biāo)記 不一致的概率.（方差）越小贴汪，數(shù)據(jù)集的純度越高（類別標(biāo)記越一致，大部分為一類）

某屬性的基尼指數(shù)為 該屬性各值的基尼值的和 基尼指數(shù)最小的屬 性作為最優(yōu)劃分屬性（該屬性劃分下的結(jié)果會(huì)更趨于一致）

剪枝處理 （判斷是否需要該屬性測(cè)試）

剪枝 是決策樹(shù)學(xué)習(xí)算法對(duì)付"過(guò)擬合"(由于學(xué)習(xí)器把某種不具普遍性的特征納入判別正例的標(biāo)準(zhǔn)而導(dǎo)致分類錯(cuò)誤）的主要手段 通過(guò)主動(dòng) 去掉一些分支（判斷是否需要該屬性測(cè)試）來(lái)降低過(guò)擬合的風(fēng)險(xiǎn).

預(yù)剪枝

在決策樹(shù)生成過(guò)程中休吠，對(duì)每個(gè)結(jié)點(diǎn)（對(duì)應(yīng)一個(gè)屬性測(cè)試）在劃 分前先進(jìn)行估計(jì)扳埂，若當(dāng)前結(jié)點(diǎn)的劃分不能帶來(lái)決策樹(shù)泛化性能提升，則停止劃 分并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)（決策結(jié)果）（該屬性對(duì)結(jié)果的關(guān)聯(lián)性不大）

后剪枝

先從訓(xùn)練集生成一棵完整的決策樹(shù)瘤礁， 然后自底向上地對(duì)非葉結(jié)點(diǎn)進(jìn)行考察阳懂，若將該結(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)替換為葉結(jié)點(diǎn)能帶來(lái)決策樹(shù)泛化性能提升，則將該子樹(shù)替換為葉結(jié)點(diǎn).

判斷決策樹(shù)泛化性能是否提升

留出法（預(yù)留一部分?jǐn)?shù)據(jù)用作"驗(yàn)證集"以進(jìn)行性 能評(píng)估）

樣本屬性取值若為特殊值（連續(xù)值或者缺失值）

連續(xù)值處理

離散化技術(shù) 二分法

對(duì)所有樣本中該屬性的連續(xù)值排序后的每?jī)蓚€(gè)值的中位點(diǎn)作為候選劃分點(diǎn) 對(duì)這些候選劃分點(diǎn)計(jì)算其信息增益（以中位點(diǎn)的值作為分類標(biāo)準(zhǔn)) 選出信息增益最大的中位值 作為劃分點(diǎn)

每個(gè)屬性對(duì)應(yīng)一個(gè)坐標(biāo)軸，每個(gè)樣本都對(duì)應(yīng)該空間中的一個(gè)數(shù)據(jù)點(diǎn)岩调，分類樣本即對(duì)空間區(qū)域分塊巷燥。

二分法所學(xué)習(xí)出的決策樹(shù)所形成的分類邊界有一個(gè)明顯的特點(diǎn): 軸平行(axis-parallel) ，即它的分類邊界由若干個(gè)與坐標(biāo)軸平行的分段組成.（某屬性值是否大于某一值）

優(yōu)缺點(diǎn):具有好的解釋性号枕，但當(dāng)學(xué)習(xí)任務(wù)復(fù)雜時(shí)需要很多段劃分缰揪，開(kāi)銷大。

多變量決策樹(shù)

使用斜的劃分邊界葱淳，則能簡(jiǎn)化決策樹(shù)钝腺。每個(gè)結(jié)點(diǎn)是屬性的線性組合，而不只是對(duì)某個(gè)屬性赞厕。

缺失值處理

現(xiàn)實(shí)任務(wù)中常會(huì)遇到不完整樣本拍屑，即樣本的某些屬性值缺失。（某些樣本由于特殊原因無(wú)法得知某些屬性的值） 如果放棄不完整樣本進(jìn)行學(xué)習(xí)則是對(duì)數(shù)據(jù)信息極大的浪費(fèi)

我們需解決兩個(gè)問(wèn)題

(1) 如何在屬性值缺失的情況 F進(jìn)行劃分屬性選擇?

選擇出不缺失該屬性的樣本坑傅，對(duì)該樣本進(jìn)行該屬性的信息增益的計(jì)算

用這種方法計(jì)算所有屬性的信息增益并比較，選擇信息增益最大的作為劃分屬性喷斋。

(2) 給定劃分屬性?若樣本在該屬性上的值缺失唁毒，如何對(duì)樣本進(jìn)行劃分?

根據(jù)對(duì)應(yīng)的屬性值劃分完所有無(wú)缺失值的樣本后，將每個(gè)屬性值按照（子結(jié)點(diǎn)）包含的樣本比例放入所有子結(jié)點(diǎn)星爪。

選劃分點(diǎn)依據(jù)無(wú)缺失值樣本的信息增益浆西，其他樣本按概率放入子結(jié)點(diǎn)。

總結(jié)

信息增益用于對(duì)屬性的選擇

存在連續(xù)值時(shí)先假設(shè)后選擇 (先依次假設(shè)屬性的劃分點(diǎn) 計(jì)算信息增益 這些假設(shè)值中信息增益的最大值即為改屬性的信息增益 并對(duì)應(yīng)劃分點(diǎn) 結(jié)點(diǎn)即包含屬性一個(gè)劃分點(diǎn))

當(dāng)分類任務(wù)復(fù)雜時(shí)把針對(duì)單一屬性的結(jié)點(diǎn)替換成多個(gè)屬性（變量）的線性組合（多變量決策樹(shù)）

樣本有缺失值時(shí) 選擇屬性時(shí)不加入含該屬性缺失值的樣本 選完后將缺失值樣本按概率同時(shí)放入所有結(jié)點(diǎn)