機器學(xué)習(xí)筆記（6）：決策樹

本文來自之前在Udacity上自學(xué)機器學(xué)習(xí)的系列筆記。這是第6篇，介紹了監(jiān)督學(xué)習(xí)中的決策樹模型。

決策樹

決策樹是監(jiān)督學(xué)習(xí)中的分類模型的一種。關(guān)于分類模型，我們先了解下面的的概念：

  • Instance：實例，表示輸入input
  • Concept：概念，表示輸出函數(shù)Function
  • Target concept：目標概念，即根據(jù)輸入，希望得到的輸出是什么
  • Sample：訓(xùn)練集Training set
  • Candidate：候選的輸出函數(shù)Function
  • Testing set：測試集Testing set

什么是決策樹？它就像一顆倒過來的樹形結(jié)構(gòu)一樣。比如，我們決定是否去餐廳A吃飯，我們會考慮多個因素，比如說肚子是否餓了、餐廳是否滿座、中餐還是西餐等。最后，我們可以依次對每一個因素的判斷，來得到結(jié)論。

image.png

所以，決策樹就是：

  1. 選擇數(shù)據(jù)集的一個特征，數(shù)據(jù)集作為初始的判斷節(jié)點（Nodes），根據(jù)對這個特征的判斷（Attributes），將數(shù)據(jù)集分為幾類子節(jié)點；
  2. 沿著不同的子數(shù)據(jù)集，再選擇數(shù)據(jù)集的一個特征，進行判斷并細分數(shù)據(jù)集；
  3. 重復(fù)步驟2，直到獲得滿足條件的數(shù)據(jù)集，即葉子節(jié)點的數(shù)據(jù)集中的數(shù)據(jù)大多都屬于同一類別了。

AND、OR、XOR
我們可以用“AND”，“OR”和“XOR”來加深理解。

  1. "AND"表示A和B同時為真時，C為真；否者為假；
  2. “OR”表示A或B為真時，C為真；否者為假；
  3. “XOR”表示A和B的結(jié)果不相同時，C為真，否則為假。

從而可以表示為：

image.png

上面是兩個節(jié)點的情況，這可以推廣到n個節(jié)點的情況。對于“AND”和“OR”，n個節(jié)點判斷的計算量是線性的n階運算；而“XOR”的計算量是指數(shù)級的2^n階運算。如果我們用真值表來表示n個節(jié)點的“XOR”決策樹的話，每個節(jié)點是二元的，那么一共有2^n種情況，而輸出則有2^{2^n}種，這個運算量是很大的。

模型
由上面的介紹，我們現(xiàn)在知道了，決策樹是一種樹狀結(jié)構(gòu)模型，可以解決分類的問題。

解決這類問題，可以通過特征選擇的方法。

算法
ID3：

  1. 選擇最優(yōu)的特征A；
  2. 賦予特征A到?jīng)Q策樹的節(jié)點；
  3. 對于特征A的每個值，創(chuàng)建節(jié)點的分支；
  4. 劃分訓(xùn)練集到?jīng)Q策樹的子節(jié)點；
  5. 如果子結(jié)點的數(shù)據(jù)得到完美地劃分，那么模型訓(xùn)練結(jié)束；否則繼續(xù)選擇其他特征進行迭代。

ID3算法的特征選取按照“信息增益”最大的特征進行。所謂“信息增益”，字面上意思就是，根據(jù)該特征來劃分數(shù)據(jù)可以降低數(shù)據(jù)集中的不確定性，即對每個劃分出來的子數(shù)據(jù)集，里面的樣本基本屬于同一類。

這個方法背后思想也是很樸素的。因為當(dāng)我們對一個不確定的問題進行思考時，會優(yōu)先根據(jù)問題的特征，以及特征可能存在的情況進行細分，并且這種細分可以將問題最大程度地確定清楚。

熵（Entropy）
在信息學(xué)中，用“熵”這個概念來表示信息的不確定性，或者說數(shù)據(jù)集的不純度。

假設(shè)一個數(shù)據(jù)集S的樣本中，包含了m個樣本，每個樣本有n個特征；一共有k個分類標簽。用p_i表示標簽集合的概率分布，那么整個數(shù)據(jù)集的熵定義為：
Entropy=\sum_{i}-(p_i)log_2(p_i)
如果Entropy越大，說明數(shù)據(jù)集的不純度越高，不確定性越大。

信息增益（Information Gain）
“信息增益”是可以降低這個數(shù)據(jù)集S不純度的定義。假設(shè)父節(jié)點經(jīng)過某特征A的劃分，根據(jù)這個特征的取值v，劃分為多個子節(jié)點S_v。那么可以得到：
Gain(S,A)=Entropy(S)-\sum_{v} \frac{ \left | S_v \right|}{ \left | S \right|} Entropy(S_v)

計算例子

Grade Bumpiness Speed limit Speed
steep bumpy yes slow
steep smooth yes slow
flat bumpy no fast
steep smooth no fast

上述表格的特征分別是公路的Grade, Bumpiness和Speed limit特征，然后駕駛速度Speed是相應(yīng)的輸出。

對于父節(jié)點（ssff），對應(yīng)有P_s=P_f=0.5，且
Entropy(ssff)=-0.5\times log_2(0.5)-0.5 \times log_2(0.5)=1.0
如果選擇Grade特征進行劃分數(shù)據(jù)集，可以劃分為（ssf）和（f）。
對于子節(jié)點（f），有P_s=0, P_f=1，且
Entropy(f)=-1\times log_2(1)=0
對于子節(jié)點（ssf），有P_s=\frac{2}{3}, P_f=\frac{1}{3}，且
Entropy(ssf)=-\frac{2}{3} \times log_2(\frac{2}{3}) - \frac{1}{3} \times log_2(\frac{1}{3})=0.9184
從而
\sum_{v} \frac{\left | S_v \right|}{\left | S \right|}Entropy(S_v)=\frac{3}{4} \times 0.9184 + \frac{1}{4} \times 0
綜上，可以得到特征Grade下的信息增益
Gain(S,Grade)=1- \frac{3}{4} \times0.9184 = 0.3112

同理，可以求得
Gain(S, Bumpiness)=0
Gain(S, Speed \, limit)=1
所以，Speed limit的信息增益最大，可以使用Speed limit作為最優(yōu)特征進行劃分數(shù)據(jù)集。

其他注意點

  1. 如果特征是連續(xù)值，例如年齡、體重、距離等，可以進行離散化處理，比如說年齡段在20到30的。

  2. 對于存在連續(xù)值的特征的決策樹，可能有必要重復(fù)某個特征的判斷，比如說年齡在20到30歲，如果判斷為F，那就還需要對年齡繼續(xù)判斷，到底是大于30歲，還是小于20歲。

  3. 如果所有數(shù)據(jù)集都得到正確地劃分，或者沒有更多的特征時，就可以停止決策樹。另外，沒有出現(xiàn)過擬合情況也是。

  4. 決策樹的優(yōu)點是它相對來說比較直觀和容易理解。但缺點就是容易過擬合，這是因為樹的分叉過細導(dǎo)致。特別是當(dāng)數(shù)據(jù)集包含大量特征的數(shù)據(jù)時。所以需要仔細地調(diào)整參數(shù)，避免過擬合。

具體scikit-learn可以參考：
https://scikit-learn.org/stable/modules/tree.html#tree

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容