《機器學習by周志華》學習筆記-決策樹-01

本書中的「決策樹」有時指學習方法，有時指學得的樹。

1、基本流程

1.1、概念

基本流程，亦稱「判定樹」

決策樹(decision tree)，是一種常見的機器學習方法。以二分類任務為例，我們希望從給定訓練數據集學得一個模型，用以對新樣例進行分離。

以二分類任務為例，可看作對「當前樣本屬于正類嗎」這個問題的「決策」或「判定」過程。

1.2、目的

是為了產生一棵泛化能力強，即處理未見示例能力強的決策樹。

1.3、基本流程

顧名思義，決策樹是基于樹結構來進行決策的，這恰是人類在面臨決策問題時一種很自然的處理機制。

例如，我們要對「這是好瓜嗎」這樣的問題進行決策時，通常會進行一系列的子判斷或自決策，例如：

他是什么顏色？>>青綠色
它的根蒂是什么形態？>>蜷縮
它敲起來是什么聲音？>>**
這是好瓜嗎？>>好瓜

如下圖所示：

顯然，決策過程的最終結論對應了我們所希望的判定結果。例如：「是」或「不是」好瓜。

每個判定問題都是對某個屬性的「測試」。例如：他是什么顏色？、它的根蒂是什么形態？

每個「測試結果」或是「導出最終結論」或是「導出進一步的判斷問題」，其考慮范圍是在上次決策結果的限定范圍之內。例如：他是什么顏色？>>青綠色>>>它的根蒂是什么形態？

一般的，一顆決策樹包含：

一個根節點：包含樣本全集
若干個內部節點：對應一個屬性測試
若干個葉節點：對應決策結果

每個結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；從「根節點」到「每個葉節點」的路徑對應了一個判定測試序列。

其基本流程遵循簡單且直觀的「分而治之(divide-and-conquer)」策略。如下所示：

輸入

訓練集 $D=\left \{ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m}) \right \}$
離散屬性集 $A=\left \{ A_{1},A_{2},...A_{n} \right \}$
每個屬性對應屬性值的樣本個數為 $a_{i}^{1},a_{i}^{2},...,a_{i}^{V}$ ,其中最大樣本個數用 $a_{i}^{max}$ 表示

過程

創建函數 $TreeGenerate(D,A_{i})$ ；
創建節點 $node$ ；
$if$ （D中樣本全屬于同一類別 $A_{i}$ ）
         $then$ （ $node=A_{i}$ 且為葉節點）
         $return$ 情形（1）
$end if$
$if$ （ $A=\varnothing$ 或任意樣本類別個數 $a_{i}^{j}=a_{i}^{max}$ ）
         $then$ （ $node$ 為葉節點且標記為 $D$ 中樣本數量最多的類 $a_{i}^{max}$ ）
         $return$ 情形（2）
$end if$
從 $A$ 中選擇最優劃分屬性 $A_{i}$ //最優劃分屬性將在下面「2、劃分選擇」說明
$for$ （ $A_{i}$ 的每一個屬性值用 $A_{i}^{v}$ 表示）
   $do$ （為 $node$ 生成分支，令 $D_{i}^{v}$ 表示 $D$ 中在 $A_{i}$ 上取值為 $A_{i}^{v}$ 的樣本子集）
   $if$ （ $D_{i}^{v}=\varnothing$ ）
           $then$ （分支節點=葉節點，類別為 $D$ 中樣本數量最多的類 $a_{i}^{max}$ ）
                         $return$ 情形（3）
                         $else$ （分支節點= $TreeGenerate(D_{i}^{v},A\setminus \left \{ A_{i}^{v} \right \})$ ）
                 $end if$
$end for$

輸出

以node為根節點的一棵決策樹

顯然，決策樹的生成是一個遞歸過程。

在決策樹基本算法中，有3種情形會導致遞歸返回：

情形（1）：當前結點包含的樣本屬于同一類別，無需劃分。
情形（2）：當前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分。
情形（3）：當前結點包含的樣本集合為空，不能劃分。

在（2）情形下，我們把當前結點標記為葉節點，并將其類別設定為該結點所含樣本最多的類別；

在（3）情形下，同樣吧當前結點標記為葉節點，但將其類別設定為其父節點所含樣本最多的類別。

注意這兩種情形的處理實質不同：

情形（2）是在利用當前結點的后驗分布。
情形（3）是把父節點的樣本分布作為當前結點的先驗分布。

2、劃分選擇

從上面的決策樹「輸入-過程-輸出」的環節中我們可以知道，其中最重要也是需要研究的部分就是——最優劃分屬性。

本章主要的內容則是介紹了讓「劃分選擇」最優的方法：

隨著劃分過程不斷進行，我們希望決策樹的分支節點所包含的樣本盡可能屬于同一類別。即節點的「純度（Purity）」越來越高。

下面我們會介紹一些度量樣本集合「純度（Purity）」比較常用的指標，通過這些指標可以增加樣本「純度」，從而使「劃分選擇」更優。

2.1、信息增益

2.1.1、信息熵(Information Entropy)

「信息熵」是度量樣本「純度」最常用的一種指標。

假設當前樣本集： $D=\left \{ \left ( x_{1},y_{1} \right ), \left ( x_{2},y_{2} \right ),..., \left ( x_{m},y_{m} \right ) \right \}$ 的類別集合用Y表示：

$Y=\left \{ Y_{1},Y_{2},...,Y_{k} \right \}$

其中第 $Y_{j}(Y_{j}\in Y)$ 類樣本個數為 $y_{j}(1\leq y_{j}\leq m)$ 且 $\sum_{j=1}^{k}y_{j}=m$ ，其所占比例用 $P_{j}(j=1,2,...,k)$ 表示，則：

$P_{j}=\frac{y_{j}}{m}$

其離散屬性集合用A表示：

$A=\left \{ A_{1},A_{2},...,A_{n} \right \}$ ，其中任意離散屬性用 $A_{i}(A_{i}\in A)$

則樣本集D的「信息熵」定義為：

$Ent(D)=-\sum_{j=1}^{k}P_{j}\times log_{2}^{P_{j}}$

由于 $0< P_{j}\leq 1$ 且 $\sum_{j=1}^{k}P_{j}=1$ 所以：

$0< Ent(D)\leq \sum_{j=1}^{k}log_{2}^{P_{j}}$ ， $Ent(D)$ 越小，樣本D的「純度」越高。

2.1.2、信息增益(Information Gain)

假設離散屬性 $A_{i}$ 有V個可能的取值，分別用 $\left \{ A_i^{1},A_i^{2},...,A_i^{V} \right \}$ 表示。若使用 $A_{i}$ 來對樣本集D進行劃分，則會產生V個分支節點。其中第v個分支節點 $A_i^{v}$ 包含了D中所有在屬性 $A_{i}$ 上取值為 $A_i^{v}$ 的樣本，該樣本集合記為 $D_{i}^{v}$ （數據為i類別v值的樣本集合）且其對應的樣本數用 $a_{i}^{v}$ 表示，則樣本集合 $D_{i}^{v}$ 的信息熵：

$Ent(D_{i}^{v})=-\sum_{j=1}^{k}P_{j}\times log_{2}^{P_{j}}$

考慮到不同分支節點所包含的樣本數 $a_{i}^{v}$ 不同，給分支結點賦予權重的規則定為：樣本數越多的分支節點，影響越大。即 $a_{i}^{v}$ 越大，影響越大。所以權重表示為：

$g=\frac{\left | D_{i}^{v} \right |}{\left | D \right |}=\frac{a_{i}^{v}}{m}$

則用屬性 $A_{i}$ 對樣本D進行劃分所獲得的「信息增益(Information Gain)」為：

$Gain(D,A_{i})=Ent(D)-\sum_{v=1}^{V}\frac{|D_{i}^{v}|}{|D|}Ent(D_{i}^{v})$

一般來說，信息增益 $Gain(D,A_{i})$ 越大，則意味著使用屬性 $A_{i}$ 來進行劃分數據集D獲的的「純度」越大。因此我們可以用信息增益來進行決策樹的「劃分屬性選擇」。也就是上面算法的屬性選擇。

$f(A_{i})=\underset{A_{i}\in A}{argmax}Gain(D,A_{i})$

上個式子就是求集合 $A=\left \{ A_{1},A_{2},...,A_{n} \right \}$ 中所有類別的「信息增益」最大的屬性公式。

較為著名的就是ID3（Iterative Dichotomiser，迭代二分器）決策樹學習算法就是以「信息增益」為準則來選擇劃分屬性。

案例：給出數據集D如下表（綠色文字是好瓜Y1，紅色文字是壞瓜Y2）

西瓜數據集D
編號色澤(A1) 根蒂(A2) 敲聲(A3) 紋理(A4) 臍部(A5) 觸感(A6) 是否好瓜(Y)
x1 青綠 $A_{1}^{1}$ 蜷縮 $A_{2}^{1}$ 渾濁 $A_{3}^{1}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 是Y1
x2 烏黑 $A_{1}^{2}$ 蜷縮 $A_{2}^{1}$ 沉悶 $A_{3}^{2}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 是Y1
x3 烏黑 $A_{1}^{2}$ 蜷縮 $A_{2}^{1}$ 渾濁 $A_{3}^{1}$

西瓜數據集D
編號	色澤(A1)	根蒂(A2)	敲聲(A3)	紋理(A4)	臍部(A5)	觸感(A6)	是否好瓜(Y)
x1	青綠 $A_{1}^{1}$	蜷縮 $A_{2}^{1}$	渾濁 $A_{3}^{1}$	清晰 $A_{4}^{1}$	凹陷 $A_{5}^{1}$	硬滑 $A_{6}^{1}$	是Y1
x2	烏黑 $A_{1}^{2}$	蜷縮 $A_{2}^{1}$	沉悶 $A_{3}^{2}$	清晰 $A_{4}^{1}$	凹陷 $A_{5}^{1}$	硬滑 $A_{6}^{1}$	是Y1
x3	烏黑 $A_{1}^{2}$	蜷縮 $A_{2}^{1}$	渾濁 $A_{3}^{1}$

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/10009.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/10009.shtml
英文地址，請注明出處：http://en.pswp.cn/web/10009.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！