機器學習－決策樹 Decision Tree

04-29

一、決策樹模型定義

1、分類決策樹模型是基於特徵對實例進行分類的樹形結構。

2、決策樹的損失函數通常是正則化的極大似然函數，決策樹學習的策略是以損失函數為目標函數的最小化。

3、遞歸選擇最優函數：

（1）選擇一個特徵，構建根節點，對數據集劃分。（第一個劃分的特徵怎麼選？）

（2）如果子集被正確分類，則停止，構建葉節點；

如果子集不能被正確分類，則繼續選擇最優特徵進行分割。。。

（3）如此遞歸下去，直到所有的子集都被分到葉節點。

4、決策樹的演算法包括三個部分：特徵選擇、樹的生成、樹的剪枝

常用的演算法：ID3、C4.5、CART

二、一些名詞的定義

1、熵（entropy）是隨機變數不確定性的度量，熵越大，隨機變數的不確定性越大。

隨機變數X的熵為：

$H(X)=-sum_{i=1}^{n}{p_{i}log p_{i}}$

2、條件熵（conditional entropy），H(Y|X) 表示在已知隨機變數X的條件下隨機變數Y的不確定性。定義為X給定條件下Y的條件概率分布的熵對X的數學期望：

$H(Y|X)=sum_{i=1}^{n}{p_{i}H(Y|X=x_{i})}$ ;

$p_{i}=P(X=x_{i})$

3、當熵和條件熵中的概率由數據估計（特別是極大似然估計，就是利用已知的樣本結果，反推最有可能（最大概率）導致這樣結果的參數值。）得到時，所對應的熵和條件熵分別稱為經驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）。

4、信息增益（information gain）表示得知特徵X的信息而使得類Y的信息不確定性減少的程度。

特徵A對訓練數據集D的信息增益 $g(D,A)$ ，定義：

$g(D,A)=H(D)-H(D|A)$

D的不確定性－在A條件下D的不確定性。差值越大，代表減少的不確定性越大。

信息增益越大的特徵具有更強的分類能力。

4、信息增益比（information gain ratio）為信息增益與數據集D的經驗熵之比。

$R(D,A)=frac{g(D,A)}{H(D)}$

三、演算法

ID3：

1、依次算出每個特徵下的數據信息增益，選擇最大的作為最優特徵。

2、如果數據在這個特徵下被完全劃分，則標記為葉節點，停止。

3、如果水沒有被完全劃分，在這個數據分類下，繼續計算不同特徵的信息增益，依次類推，直到數據被完全劃分。

C4.5:

以信息增益比為標準來劃分數據。

四、CART

1、定義

CART（classification and regression tree）是在給定輸入隨機變數X條件下，輸出隨機變數Y的條件概率分布。

決策樹的生成是遞歸地構建二叉決策樹的過程。對回歸樹（Y是連續變數）用平方誤差最小化準則，對分類樹用基尼指數（Gini index）最小化準則，進行特徵選擇，生成二叉樹。

2、Gini 基尼指數

$Gini(p)=sum_{k=1}^{K}{p_{k}(1-p_{k})}=1-sum_{k=1}^{K}{p_{k}^{2}}$

在特徵A的條件下，數據被分成D1，D2兩個部分，則集合D的基尼指數為：

$Gini(D,A)=frac{|D1|}{|D|}Gini(D1)+frac{|D2|}{|D|}Gini(D2)$

兩個基尼指數分別乘以數據個數的佔比。

基尼指數表示集合D的不確定性，基尼指數越大，樣本集合的不確定性也就越大。

3、演算法：

CART構建二叉樹。

首先計算所有特徵分類下的基尼指數，選擇最小的作為最優特徵，此點作為最優切分點。

一步一步跟ID3的步驟一樣，只不過以基尼指數作為標準，且選擇最小的基尼指數。

未完待續。。。

參考文獻：《統計學習方法》