決策樹分類

樹狀結構，可以很好的對數據進行分類；

• 決策樹的根節點到葉節點的每一條路徑構建一條規則；
• 具有互斥且完備的特點，即每一個樣本均被且只能被一條路徑所覆蓋；
• 只要提供的數據量足夠龐大真實，通過數據挖掘模式，就可以構造決策樹。
  

Hunt算法

設$D_t$是與節點相關聯的訓練記錄集
算法步驟:

1. 如果$D_t$中所有記錄都屬于同一個類$y_t$,則t是葉節點，用$y_t$標記。
2. 如果$D_t$中包含屬于多個類的記錄,則選擇一個屬性測試條件，將記錄劃分成較小的子集
3. 對于測試條件的每個輸出，創建一個子結點，并根據測試結果將$D_t$中的記錄分布到子結點中。然后，對于每個子結點，遞歸地調用該算法。

Hunt算法采用貪心策略構建決策樹

• 在選擇劃分數據的屬性時，采取一系列局部最優決策來構造決策樹。

決策樹歸納的設計問題

• 如何分裂訓練記錄？
  • 怎樣為不同類型的屬性指定測試條件？
  • 怎樣評估每種測試條件？
• 如何停止分裂過程？

怎樣為不同類型的屬性指定測試條件？

• 依賴于屬性的類型

  • 標稱
  • 序數
  • 連續

• 依賴于劃分的路數

  • 多路劃分
  • 二元劃分

怎樣選擇最佳劃分？
選擇最佳劃分的度量通常是根據劃分后子節點純性的程度。
純性的程度越高，類分布就越傾斜，劃分結果越好。

信息增益

熵的定義如下：
$$\mathrm{Entropy}(S)=?\sum _{i=1}^c{p}_i\log \left(p_i\right)$$
信息增益定義如下：
$$\mathrm{Gain}(S,A)=\mathrm{Entropy}(S)?\sum _{v\in A}\frac{\left|S_v\right|}{|S|}\mathrm{Entropy}\left(S_v\right)$$

信息增益表示的是：得知特征X的信息而使得分類Y的信息的不確定性減少的程度，如果某個特征的信息增益比較大，就表示該特征對結果的影響較大。

舉例說明:

增益比率

信息增益問題：取值比較多的特征比取值少的特征信息增益大
解決方案：使用增益率，K越大，SplitINFO越大，增益率被平衡
$$GainRATI{O}_{split}=\frac{{\text{?GAIN?}}_{\text{split?}}}{\text{?SplitINFO}}$$
$$SplitINFO=?\sum _{n=1}^k\frac{n_i}{n}\log \frac{n_i}{n}$$

增益率準則對可取值數目較少的屬性有偏好，因此C4.5算法并不是直接選擇增益率最大的屬性作為分支標準，而是先從侯選屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的屬性。

基尼指數

連續數據

• 二元劃分：$（A<v）or（A\ge v）$
  • 考慮所有的劃分點，選擇一個最優劃分點v
• 多路劃分：$v_i\le A<v_{i+1}（i=1,\dots ,k）$
  

總結

1. 決策樹是一種構建分類（回歸）模型的非參數方法
2. 不需要昂貴的的計算代價
3. 決策樹相對容易解釋
4. 決策樹是學習離散值函數的典型代表
5. 決策數對于噪聲的干擾具有相當好的魯棒性
6. 冗余屬性不會對決策樹的準確率造成不利影響
7. 數據碎片問題：隨著樹的生長，可能導致葉結點記錄數太少，對于葉結點代表的類，不能做出具有統計意義的判決
8. 子樹可能在決策樹中重復多次，使決策樹過于復雜
9. 決策樹無法學習特征之間的線性關系，難以完成特征構造