天天看點

cart算法_決策樹之CART算法

cart算法_決策樹之CART算法

CART對連續型屬性處理方式和C4.5一樣,隻不過使用GINI值作為屬性劃分的依據,而C4.5是采用增益率作為依據。

對于離散型屬性,C4.5是理論上有多少個離散值就分裂成多少個節點。但CART算法生成的是一顆二叉樹,每一次分裂隻會産生兩個節點。

以打籃球案例中的“天氣”屬性為例,C4.5算法分裂成了小雨、晴天、陰天三個節點。如果是CART算法的話,會把屬性值分為不同的組,{小雨}、{晴天、陰天},{晴天}、{小雨、陰天},{陰天}{晴天、小雨},分别計算三組的基尼指數,然後選取基尼指數最小的值作為節點。

cart算法_決策樹之CART算法
cart算法_決策樹之CART算法
cart算法_決策樹之CART算法

通過計算,我們發現{小雨}、{晴天、陰天}的劃分方法,基尼指數最小,是以如果我們以天氣屬性作為劃分,那麼就選擇{小雨}、{晴天、陰天}的分類

基尼指數的計算方法,由于沒有使用對數,是以運算會比對數運算要快。

  • 基尼值公式:

資料集D的純度可以用基尼值來度量,Gini(D)越小,資料集D的純度越高

cart算法_決策樹之CART算法
  • 基尼指數公式:

資料集D,選擇屬性a劃分後的基尼指數

cart算法_決策樹之CART算法

比如資料集D,屬性a的值把D分為D1、D2兩個部分,那麼在屬性a的條件下,D的基尼指數表達式為:

cart算法_決策樹之CART算法