決策樹(shù)的一些基礎(chǔ)概念（根節(jié)點(diǎn)，內(nèi)部結(jié)點(diǎn)，葉子結(jié)點(diǎn)等），結(jié)合數(shù)據(jù)結(jié)構(gòu)的二叉樹(shù)/非二叉樹(shù)其實(shí)很好理解。

純度

這個(gè)好像還是第一次看到。決策樹(shù)在選擇最優(yōu)的劃分屬性時(shí)，希望分支節(jié)點(diǎn)包含盡可能多的同一類(lèi)別的樣本，這個(gè)就是指結(jié)點(diǎn)的“純度”盡可能高。

劃分方法對(duì)比

ID3（信息增益）

使用信息熵來(lái)度量樣本集合的純度；

• 信息熵定義：

  
  
  image1.png

• 信息增益：

  
  
  image2.png

信息增益越大，代表著使用此屬性a劃分的子集不確定性越小，而“純度”越大。

• 缺點(diǎn)：對(duì)可取值較多的屬性有偏好。

C4.5（增益率）

為了減少I(mǎi)D3（信息增益）算法的偏好問(wèn)題，C4.5算法提出了用增益率來(lái)選擇最優(yōu)劃分屬性。

• 增益率定義：

  
  
  圖片發(fā)自簡(jiǎn)書(shū)App

• 缺點(diǎn)：對(duì)可取值較少的屬性有偏好。

注意：C4.5使用時(shí)，先從候選的劃分屬性中選出信息增益高與平均水平的屬性，再?gòu)闹羞x擇增益率最高的。

CART（基尼指數(shù)）

數(shù)據(jù)集D的純度可用基尼值度量：

圖片發(fā)自簡(jiǎn)書(shū)App

Gini(D)反映了從D中隨機(jī)抽取兩個(gè)樣本，類(lèi)別標(biāo)記不一致的概率。因此，Gini(D)越小，代表著D的純度越高。
屬性a的基尼指數(shù)定義：

圖片發(fā)自簡(jiǎn)書(shū)App

因此，在候選屬性中選擇哪個(gè)使得劃分后，基尼指數(shù)最小的屬性作為劃分屬性。