屬性選擇

屬性的感覺(jué)就是最大限度的增加樣本的純度，并且不要產(chǎn)生產(chǎn)生樣本數(shù)少的分枝。

屬性選擇標(biāo)準(zhǔn)有信息增益（Information Gain）和Gini系數(shù)
信息增益作為標(biāo)準(zhǔn)時(shí)，選擇信息增益大的作為分裂點(diǎn)
Gini是一種不純度函數(shù)，衡量數(shù)據(jù)關(guān)于類(lèi)別的純度，數(shù)據(jù)均勻分布于各個(gè)類(lèi)別時(shí)，不純度就很大

大小規(guī)模合適的樹(shù)

1. 樹(shù)停止生長(zhǎng)的條件（最小劃分實(shí)例數(shù)，劃分閾值，最大樹(shù)深度）
2. 對(duì)完全生長(zhǎng)的樹(shù)進(jìn)行剪枝（評(píng)估子樹(shù)，如去掉性能更好，則進(jìn)行剪枝）

ID3

思想：選信息增益大的屬性建立分支，遞歸選取知道子樹(shù)只包含一個(gè)類(lèi)別的數(shù)據(jù)

自頂向下的貪婪的搜索算法，構(gòu)造出與訓(xùn)練數(shù)據(jù)一致的決策樹(shù)
用信息增益作為屬性選擇的標(biāo)準(zhǔn)，使劃分后的數(shù)據(jù)集的信息熵最小

ID3的問(wèn)題

• 只能處理屬性數(shù)據(jù)，無(wú)法處理連續(xù)型數(shù)據(jù)
• 屬性的每個(gè)取值都會(huì)產(chǎn)生一個(gè)對(duì)應(yīng)分支，會(huì)有許多小的子集，過(guò)小的子集會(huì)導(dǎo)致統(tǒng)計(jì)特征不充分，使算法停止
• 信息增益在類(lèi)別值多的屬性上計(jì)算結(jié)果，大于類(lèi)別值少的屬性，導(dǎo)致算法天生偏向選擇分支多的屬性，會(huì)導(dǎo)致過(guò)度擬合

C4.5

• 能處理連續(xù)性和離散型屬性
• 能處理有缺失值的數(shù)據(jù)
• 信息增益作為決策樹(shù)屬性選擇標(biāo)準(zhǔn)
• 對(duì)生成樹(shù)進(jìn)行剪枝處理
• 決策樹(shù)到規(guī)則自動(dòng)生成

不同于ID3

• C4.5不是直接衡量信息增益，是用的信息增益率來(lái)衡量屬性的

• ID3中的信息增益是根據(jù)所屬類(lèi)別（y）來(lái)計(jì)算的，C4.5以信息增益率為標(biāo)準(zhǔn)，引入分裂信息的概念，考慮了獲取增益的代價(jià)，克服了ID3偏心多屬性特征的缺點(diǎn)

• 分裂信息用來(lái)衡量屬性分裂數(shù)據(jù)的廣度和均勻，公式如下

Paste_Image.png

屬性值越多，分布越平均的分裂信息越大，對(duì)應(yīng)的信息增益率則越小

對(duì)于連續(xù)值的求解

Paste_Image.png

處理缺失值，這個(gè)ID3也沒(méi)有

• 直接拋棄
• 平均數(shù)或者眾數(shù)
• C4.5中用概率的方法，為每個(gè)可能的賦值都設(shè)置一個(gè)概率

剪枝

不用預(yù)剪枝是因?yàn)轭A(yù)剪枝對(duì)不同數(shù)據(jù)的表現(xiàn)很不一樣

后剪枝方法

• 從葉節(jié)點(diǎn)開(kāi)始，檢查每個(gè)非葉節(jié)點(diǎn)
• 如果以某個(gè)葉節(jié)點(diǎn)（或其子節(jié)點(diǎn)中使用頻率最高的子節(jié)點(diǎn)），替換該非葉節(jié)點(diǎn)
• 整個(gè)決策樹(shù)的誤差率降低就剪去改節(jié)點(diǎn)

預(yù)剪枝方法

• 限制樹(shù)的最大深度
• 限制葉節(jié)點(diǎn)最小記錄數(shù)

C4.5后剪枝

針對(duì)每個(gè)節(jié)點(diǎn)，以其中的類(lèi)別眾數(shù)作為預(yù)測(cè)類(lèi)別
利用每個(gè)節(jié)點(diǎn)的錯(cuò)誤率，根據(jù)假設(shè)正態(tài)分布對(duì)真實(shí)誤差進(jìn)行估計(jì)

悲觀誤差剪枝

CART樹(shù)

改進(jìn)ID3的3個(gè)方面

• 不純度計(jì)算用GINI指數(shù)，取最小最為分裂點(diǎn)，就是差異損失最大的點(diǎn)（Gini父-Gini子最大的）
• 特征雙化（towing），二元分類(lèi)樹(shù)
• 輸出為離散時(shí)為分類(lèi)樹(shù)，為連續(xù)時(shí)為回歸樹(shù)

特征雙化

構(gòu)建二叉樹(shù)，雙化時(shí)盡量時(shí)2個(gè)類(lèi)別的輸出差異性的和，保持最小，就是純度最大。

具體操作就是窮舉法，對(duì)每對(duì)都計(jì)算Gini系數(shù)（帶全局的權(quán)重），然后選擇Gini系數(shù)最大的呢一組，這種感覺(jué)就是選最不純的一組，用你的下限去和別的屬性競(jìng)爭(zhēng)，以達(dá)到全局的最優(yōu)