數據挖掘入門系列教程(三點五)之決策樹

  • 2020 年 3 月 14 日
  • 筆記

數據挖掘入門系列教程(三點五)之決策樹

本來還是想像以前一樣,繼續學習《 Python數據挖掘入門與實踐 》的第三章「決策樹」,但是這本書上來就直接給我懟了一大串代碼,對於決策樹基本上沒有什麼介紹,可直接把我給弄懵逼了,主要我只聽過決策樹還沒有認真的了解過它。

這一章節主要是對決策樹做一個介紹,在下一個章節,將使用決策樹來進行預測分類 。

決策樹(Decision Tree)介紹

Decision Tree是一類較為常見的機器學習的方法。它既可以作為分類算法,也可以作為回歸算法。

如何來介紹決策樹,這裡舉一個例子:在大學,你找女朋友的時候,心目中順序應該是這樣的(僅僅是舉一個例子):

  • Q:性別要求?
  • A:不是女的不要。
  • Q:年齡要求?
  • A:大於我3歲的不要
  • Q:專業要求?
  • A:非CS不要
  • ……

為了更好的表示上面的這一些問題,我們可以將其畫成一張樹狀圖如下所示:

上面的這棵樹就是我們找女朋友的決策過程,圓角矩形代表了判斷條件,橢圓形代表了決策結果。通過性別,年齡,專業這幾個屬性,最終我們得出了最終的決策。而這棵樹也就被稱之為決策樹。

大家通過上圖會發現有3個東西:

  • 根節點:包含樣本的全集
  • 內部節點:對應特徵屬性測試
  • 葉節點:代表決策的結果

在一棵決策樹中,包含了一個根節點,多個內部節點(判斷條件) 和若干個葉子節點。先說葉子節點,在決策樹中,葉子節點對應了決策結果,決策結果可以有多種類型(圖中是yes和no,也可以為1,2,3)。內部節點和根節點對應的都是屬性測試,只不過先後順序不同。

總的來說,決策樹體現的是一種「分而治之」的思想,

那麼這裡就有一個問題,誰來當根節點?誰又來當中間的節點?先後順序又是怎樣的?(這裡先不說算法流程,從簡單開始說起,然後再說算法流程)

結點的選擇

首先我們需要明白根節點和中間節點是不同的,一個是統領全局的開始包含所有的樣本。一個是負責局部的決策,並且隨着決策樹的不斷的進行決策,所包含的樣本逐漸屬於同一個類別,即節點的「純度」越來越高。

那麼,我們如何來尋找合適根節點(也就是屬性)呢?靠感覺?靠感覺當然不行,我們需要一個具體的數值來決定,很幸運,香農幫助我們做到了。

「信息熵」(information entropy):可以度量樣本集合中的「純度」。 在信息世界,熵越高,表示蘊含越多的信息,熵越低,則信息越少。 而根節點需要包含所以的樣本,則根結點的熵最大

信息熵(Information Entropy)

設樣本集合為(D),第(k)類樣本所佔比例為(p_k(k = 1,2,3,……n)),則集合(D)的信息熵為:

[ Ent(D) = – sum_{k=1}^{n}p_klog_2p_k\ Ent(D)越大,則D的純度越小,也就是說集合D越混亂。 ]

現在,我們已經知道一個集合(D)中的信息熵是多少,那麼我們如何來進行劃分呢?首先,我們需要明確一個劃分的標準(也就是目標),我們當然希望劃分之後,劃分之後的集合的熵越來越小,也就是劃分後的集合越來越純,這裡我們引入信息增益這個概念。

信息增益(information gain)

下面是西瓜書中對信息增益的定義:

假設離散屬性(a)(V)個可能的取值({a^1,a^2,a^3……a^V}),若以屬性(a)對樣本進行劃分,則有V個分支,其中第(v)個分支包含了(D)中在屬性(a)上取值為(a^v)的樣本,記為(D^v)。我們可以計算出(D^v)的信息熵,然後考慮到不同分支結點的樣本數不同,給分支結點賦予權重(frac{|D^v|}{|D|}),樣本數愈多,則影響力越大,則可以計算出屬性(a)對樣本集(D)進行劃分的「信息增益」:

[ Gain(D,a) = Ent(D) – sum_{v=1}^Vfrac{|D^v|}{|D|}Ent(D^v) ]

一般來說,信息增益越大,則代表劃分後的集合越「純」,也就是說使用(a)屬性來劃分的效果最好,那麼我們就可以使用(a)屬性來進行劃分。ID3算法就是使用信息增益來作為標準劃分屬性的。

決策樹生成算法流程

下面是來自《西瓜書》的決策樹生成算法流程:

決策樹生成是一個遞歸的過程,在下面3中情況中,遞歸會返回:

  • 當前結點包含的樣本全屬於同一類別,無需劃分
  • 當前屬性集為空,或是所有樣本在所有屬性上取值相同,無法劃分
  • 當前結點包含的樣本集合為空,不能劃分

算法可能不是那麼的形象好理解,下面將以實際的例子來展示。

在最上面上面的找女朋友的例子並不是特別的好,屬性太少。這裡以西瓜書中的?來進行舉例。這個屬性還是挺多的。

在上圖中,屬性的集合是{色澤,根蒂,敲聲,紋理,臍部,觸感}(目前不考慮編號這個屬性),分類的集合是{是,否},一共有17個樣本。

首先讓我們來及計算集合(D)的熵值。在集合(D)中,好瓜(是)占(p_1 = frac{8}{17}),壞瓜(否)占(p_1 = frac{9}{17}),所以集合(D)的熵為:
[ Ent(D) = -sum_{k=1}^2p_klog_2p_k = -(frac{8}{17}log_2frac{8}{17} + frac{9}{17}log_2frac{9}{17}) = 0.998 ]

以色澤作為劃分標準,可以得到3個子集:
[ D^1(色澤=青綠) = {1,4,6,10,13,17} \ 在D^1中p_1 = frac{3}{6},p_2=frac{3}{6}\ D^2(色澤=烏黑) = {2,3,7,8,9,15}\ 在D^2中p_1 = frac{4}{6},p_2=frac{2}{6}\ D^3(色澤=淺白) = {5,11,12,14,16}\ 在D^2中p_1 = frac{1}{5},p_2=frac{4}{5} \ 其中集合中的數字代表表格中的編號 ]

我們可以獲得(D^1,D^2,D^3)的信息熵:

[ Ent(D^1)=-(frac{3}{6}log_2frac{3}{6}+frac{3}{6}log_2frac{3}{6}) = 1.00 \ Ent(D^2)=-(frac{4}{6}log_2frac{4}{6}+frac{2}{6}log_2frac{2}{6}) = 0.918 \ Ent(D^3)=-(frac{1}{5}log_2frac{1}{5}+frac{4}{5}log_2frac{4}{5}) = 0.722 \ ]

因此色澤的信息增益為:

[ begin{equation} begin{aligned} Gain(D,色澤) &= Ent(D) – sum_{v=1}^3frac{|D^v|}{|D|}Ent(D^v)\ &= 0.99 – (frac{6}{17}times 1.00 + frac{6}{17}times0.918 +frac{5}{17}times0.722) \ &= 0.109 end{aligned} end{equation} ]
同理可以得到:
[ begin{equation} begin{split} & Gain(D,根蒂) = 0.143;Gain(D,敲聲) = 0.141;\ & Gain(D,紋理) = 0.381;Gain(D,臍部) = 0.289; \ & Gain(D,觸感) = 0.006;Gain(D,色澤)=0.109; end{split} end{equation} ]
通過計算可以得到,紋理的信息增益最大,因此他被選為劃分的屬性如下圖:

然後以紋理是「清晰為例」,該集合(D^1={1,2,3,4,5,6,8,10,15}),可用的屬性集合為{ 色澤,根蒂,敲聲,臍部, 觸感}。因此,基於(D^1)又可以計算出各個屬性的信息增益:

[ begin{equation} begin{split} & Gain(D^1,色澤) = 0.043;Gain(D^1,根蒂) = 0.458;\ &Gain(D^1,敲聲) = 0.331; Gain(D^1,觸感) = 0.458;\ &Gain(D^1,臍部)=0.458; end{split} end{equation} ]

因此我們可以在「根蒂」,「觸感」,「臍部」中任意選擇其中一個作為劃分屬性。最終得到以下的決策樹:

通過上面的這些步驟,我們就得到了一顆關於西瓜的好壞的決策樹。ID3算法就是用信息增益作為劃分標準。

上面的例子來自西瓜書,以及計算的結果也來自西瓜書。

增益率(Gain Ratio)

在這裡有一個問題,(Gain(D,屬性))越大,就一定能夠作為劃分標準嗎?假如它是一個無用的屬性呢?比如上圖中編號這個屬性,如果在上面我們選擇編號作為根節點,那麼第一次劃分就能夠得到17個集合,每一個集合只有1個樣本,(Gain(D,編號))必定能夠達到最大值。但是我們知道,編號這個屬性在這裡是毫無作用的。如果將這個問題進行泛化,如果一個屬性在分類中起到的作用給很小(也就是它對分類的影響很小),那麼我們應該怎麼考慮呢?

這裡我們可以使用增益率來作為劃分的標準,定義如下
[ begin{equation} begin{split} &Gain_ratio(D,a) = frac{Gain(D,a)}{IV(a)} \ &其中\ &IV(a) = -sum_{v=1}^Vfrac{D^v}{D}log_2frac{D^v}{D} end{split} end{equation} ]

(IV(a))稱之為屬性(a)固有值(intrinsic value),屬性(a)的可能取值越多(劃分的(D^v)的集合越多),(IV(a))就會越大。若像編號一樣進行劃分(每一個劃分的集合中只有一個樣本),隨着編號的增多,(IV(a))的取值如下圖:

其中著名的C4.5算法就是使用增益率來劃分屬性。

除了這種解決方案,還有一種解決方法,基尼指數作為劃分標準,CART決策樹使用這種方法。

基尼指數(Gini Index)

前面我們使用信息熵來表示集合的純度,這裡我們使用基尼值來表示:

設樣本集合為(D),第(k)類樣本所佔比例為(p_k(k = 1,2,3,……n))
[ begin{equation} begin{aligned} Gini(D) &= sum_{k=1}^{|n|}sum_{k'neq k}p_kp_{k'}\ &=1 – sum_{k=1}^{|n|}p_k^2 end{aligned} end{equation} ]

(Gini(D)) 反映了從數據集中隨機抽取兩個樣本,其類別標記不一致的概率。因此, $Gini(D) $越大,則數據集越複雜,純度越低。

同樣,屬性(a)的基尼指數定義為:

[ Gini_index(D,a) = sum_{v=1}^Vfrac{D^v}{D}Gini({D^v}) ]

因此,在我們選擇合適的屬性進行劃分的時候,選擇劃分後基尼指數較小的屬性作為劃分標準即可。

這個時候我們再來看一看這幅圖,應該就看的懂了吧。

剪枝(pruning)處理

首先,我們先說一下剪枝的目的——防止「過擬合」。在決策樹的學習過程中,為了保證正確性,會不斷的進行劃分,這樣可能會導致對於訓練樣本能夠達到一個很好的準確性,但是對於測試集可能就不是很好了,這樣的模型不具備泛化性。下面來舉一個例子:

我們有如下的數據集:

坐標軸的上的每一個點代表一個樣本,有(x,y)兩種屬性,其中,藍色的點代表類0,橙色的點代表類1。

當我們使用決策樹進行訓練後,模型對於數據的識別區域如下,在粉紅色區域,其認為裏面的點為類0,藍色的區域為類1:

大家可能發現一個問題,那就是這個區域劃分的太「細緻」了。因為數據是有噪音(noise)的,這樣劃分明顯是不合理的。這裡大家可以看一看決策樹的圖片:

那麼如何來緩解這種問題呢?其中有一種方法就是去掉一些分支(剪枝)來降低過擬合的風險。

剪枝有兩種方案:

  • 預剪枝(prepruning)
  • 後剪枝(post-pruning)

預剪枝

預剪枝是指在決策樹生成過程中,對每個結點在劃分前先進行估計,若當前結點的劃分不能帶來決策樹泛化性能提升,則停止劃分並將當前結點標記為葉結點。

用通俗的話來說,就是如果進行劃分能夠帶來更好的結果就進行劃分,否則不進行劃分。首先,我們定義一個訓練集和一個驗證集如下:(西瓜書中間的例子)

上面一部分是訓練集,下面一部分是測試集。然後讓我們來對訓練集(記住是訓練集)進行劃分,劃分的規則與上面的一樣。

下面的這幅圖是未剪枝的情況。

那麼,剪枝是如何進行的呢?

首先,我們先判斷「臍部」,如果我們不對「臍部」進行劃分,也就是說這棵決策樹是這樣的:

只有一個好瓜的判斷結果(根據上面的算法流程圖,node節點直接就是葉子節點,其類別由樣本中最多的決定【這裡既可以是好瓜也可以是壞瓜,因為數量一樣】)

這樣下來,也就是說無論你什麼瓜過來我都判斷它是好瓜。使用驗證集進行驗證,驗證的精準度為:(frac{3}{7} times100% = 42.9%)。如果進行劃分呢?

下圖便是進行劃分的情況,其中被紅色圓圈框出來的部分表示驗證正確。

如果只劃分「臍部」這個屬性,我們可以通過其來劃分好瓜和壞瓜,通過驗證機去測試,我們可以得到劃分後的準確性為:(frac{5}{7}times100%=71.4% > 42.9%),所以選擇劃分。

下面便是進行前剪枝後的劃分結果,使用驗證集進行驗證,精度為(71.4%)

儘管該方案可以降低過擬合的風險,並在一定程度上能夠降低算法的複雜度,但也會帶來欠擬合的風險。因為會出現另外一種情況:有可能當前劃分不能提升泛化能力,但是在此基礎上的後續的劃分也許可以導致性能顯著提高。

後剪枝

後剪枝則是先從訓練集生成一棵完整的決策樹,然後自底向上地對非葉結點進行考察,若將該結點對應的子樹替換為葉結點能帶來決策樹泛化性能提升,則將該子樹替換為葉結點.

後剪枝和前剪枝的不同在於後剪枝是在生成決策樹後再進行剪枝。順序是由下到上

我們繼續來看這幅圖:

通過驗證集,我們易得到該決策樹的識別率為(42.9%)

讓我們重新看一下數據吧,數據集和驗證集如下:

現在讓我們來進行剪枝吧!!首先先看節點⑥,節點6中包含編號為({7(好瓜),15(壞瓜)})的訓練樣本,因此我們將節點⑥變成葉節點並標記為「好瓜(壞瓜也ok)」。如下所示:

在這種情況下,驗證集中序號為({4,8,11,12})驗證正確,精度調高到(frac{4}{7} times 100%= 57.1%),因此可以進行剪枝。

考慮結點⑤,包含編號為({6,7,15}),將其變成葉節點(標記為「好瓜」),使用驗證集去驗證,其精度仍為(57.1%),沒有提高,進行考慮。同理可得到下面的這副圖片:

最終,該決策樹的精度為(71.4%)

比較預剪枝和後剪枝,後剪枝保留的分支更多,同時後剪枝的欠擬合的風險很小,泛化性能往往優於預剪枝決策樹,但是顯而易見,訓練的時間要比預剪枝大得多。

隨機森林(Random Forest | RF)

什麼是隨機森林呢?隨機森林是一個包含多個決策樹的分類器,由很多決策樹構成,不同的決策樹之間沒有關聯。當我們進行分類任務時,森林中的每一棵決策樹都會分別對樣本進行判斷和分類,每個決策樹會得到一個自己的分類結果,決策樹的分類結果中哪一個分類最多,那麼隨機森林就會把這個結果當做最終的結果。 (emm,少樹服從多樹)。好像很簡單的樣子,但是這裡有一個問題,那就是隨機森林中有多個決策樹,那麼,我們如何用已有的數據集去構建這麼多的決策樹呢?

首先我們要明白,決策樹是不同的,那麼訓練決策樹所需要的數據也不同。那麼具體該如何選擇呢?既然是隨機森林,那麼它肯定是隨機的!!它的隨機有兩層含義:

  • 樣本隨機:Bagging算法
  • 屬性隨機

樣本隨機

樣本隨機使用的是Bagging算法(Bootstrap aggregating,引導聚集算法)又稱之為裝袋算法。算法的流程如下:

給定一個訓練集大小為(n)的訓練集(D),Bagging算法從中間隨機的、有放回的選出(m)個大小為(n')的子集(D_i)作為新的訓練集。

ps:通過以上這種取樣得到的集合(D_i)中間可能會有重複的元素(因為是有放回的抽取元素)

屬性隨機

若樣本有(M)個屬性時,隨機從這(M)個屬性中選取出(m)個屬性(無放回),滿足條件(m < M)

ps:在這種情況下,(m)個屬性中是沒有重複的屬性的。

隨機森林的優缺點

通過上面的樣本隨機和屬性隨機,我們就可以構建出很多棵不同的決策樹了,然後組成一個森林,裏面住着熊大和熊二,在一起快樂的生活。

優缺點的整理來自這裡,基本上所有的文章都是這個說法,不同的在於文字的多少罷了!

優點

  1. 它可以出來很高維度(特徵很多)的數據,並且不用降維,無需做特徵選擇
  2. 它可以判斷特徵的重要程度
  3. 可以判斷出不同特徵之間的相互影響
  4. 不容易過擬合
  5. 訓練速度比較快,容易做成並行方法
  6. 實現起來比較簡單
  7. 對於不平衡的數據集來說,它可以平衡誤差。
  8. 如果有很大一部分的特徵遺失,仍可以維持準確度。

缺點

  1. 隨機森林已經被證明在某些噪音較大的分類或回歸問題上會過擬合。
  2. 對於有不同取值的屬性的數據,取值劃分較多的屬性會對隨機森林產生更大的影響,所以隨機森林在這種數據上產出的屬性權值是不可信的

總結

決策樹的概念就暫時介紹到這裡了,儘管內容有點多,但是還是挺好理解的,很類似於人類的思考方式。在下一篇的博客中,將使用scikit-learn工具包,基於決策樹來對數據進行分類。決策樹還有很多知識和算法,但是至少我們得掌握基本的概念。

參考

  1. 《西瓜書》決策樹——第四章
  2. 維基百科:隨機森林 Bagging算法