決策樹(shù)(ID3,C4.5,CART)

決策樹(shù)

決策樹(shù)是一種基本的分類(lèi)和回歸方法.決策樹(shù)顧名思義,模型可以表示為樹(shù)型結(jié)構(gòu),可以認(rèn)為是if-then的集合,也可以認(rèn)為是定義在特征空間與類(lèi)空間上的條件概率分布.

[圖片上傳失敗...(image-472fde-1543139528029)]

決策樹(shù)的中間節(jié)點(diǎn)可以看做是對(duì)一種特征的判斷,也是符合上一次判斷特征某種取值的數(shù)據(jù)集,根節(jié)點(diǎn)代表所有數(shù)據(jù)集;葉子節(jié)點(diǎn)看做是判斷所屬的類(lèi)別.

決策樹(shù)學(xué)習(xí)通常包括3個(gè)步驟: 特征選擇. 決策樹(shù)生成和決策樹(shù)剪枝.

目前常用的決策樹(shù)算法有ID3, C4.5 和CART.

特征選擇

在數(shù)據(jù)集中的所有特征列表中,選擇分類(lèi)效果最好的特征,或者說(shuō)讓分類(lèi)效果盡可能的"純",通俗的說(shuō)就是讓劃分的每個(gè)結(jié)果的盡可能屬于同一個(gè)類(lèi)別,都是自己人. 那么, 分類(lèi)效果最好,或者說(shuō)純度,怎么定義? 用什么衡量特征的分類(lèi)效果呢? 不同的決策樹(shù)算法采用不同的衡量指標(biāo).比如說(shuō),ID3采用信息增益,C4.5采用信息增益比率,CART分類(lèi)回歸樹(shù)當(dāng)用于分類(lèi)時(shí),采用Gini指數(shù),用于回歸問(wèn)題時(shí)采用均方差差[計(jì)算劃分之前的均方差,劃分之后的均方差,再做差運(yùn)算]. 無(wú)論是哪種指標(biāo),本質(zhì)上,都是比較用特征劃分前后兩種狀態(tài)之間的差異變化,變化越明顯越好,而各種指標(biāo)是對(duì)這種差異變化的量化. 但是不同的指標(biāo)會(huì)有不同的傾向性,這種傾向性從指標(biāo)計(jì)算公式上可以發(fā)現(xiàn),而傾向性又會(huì)引出不同的問(wèn)題,進(jìn)而產(chǎn)生不同的優(yōu)化方法.

另一方面,最佳的特征的選擇,總是需要對(duì)所有特征進(jìn)行一次遍歷,分別計(jì)算每種特征的劃分效果,比較求最優(yōu)特征的最佳特征劃分值.

信息增益

計(jì)算信息增益之前,需要先引出信息熵的概念.熵是信息論中的一個(gè)非常重要的概念,信息熵的計(jì)算,對(duì)于一個(gè)數(shù)據(jù)集D,其中N中類(lèi)別的第k類(lèi)樣本所占比例為pk,則數(shù)據(jù)集D的信息熵:

Ent(D)= -\sum_{k=1}^{N}p_k log_2 p_k

從信息熵的計(jì)算公式可以知道,Ent(D)的取值范圍在[0, log_2n], 最小,或者說(shuō)節(jié)點(diǎn)最純時(shí)[都是同一個(gè)類(lèi)別],為0;最大,最混亂時(shí)[每種類(lèi)別比例都相等],為log_2n.

知道了信息熵的計(jì)算公式,那么劃分前,計(jì)算數(shù)據(jù)集的信息熵, 依據(jù)特征f的n種取值劃分后的n個(gè)節(jié)點(diǎn),分別計(jì)算信息熵,然后依據(jù)各個(gè)節(jié)點(diǎn)數(shù)據(jù)集的比率,加權(quán)平均,計(jì)算劃分后的總的信息熵,前后兩次做差,得到這次劃分的信息增益,用來(lái)衡量特征f的劃分效果如何.

信息增益:
信息增益表示得知特征f的信息而使得類(lèi)Y的信息的不確定性較少的程度.

Gain(D,f) = Ent(D) - \sum_{i=1}^{n} \frac{|D_i|}{|D|}Ent(D_i)

信息增益越大,特征劃分效果越好. 信息增益指標(biāo),趨向于選擇取值數(shù)目多的特征.[個(gè)人觀點(diǎn):特征取值越多,劃分到每個(gè)子節(jié)點(diǎn)的數(shù)據(jù)越少,一定程度上,純度越高,混亂程度越低,熵取值越小,進(jìn)而,信息增益越大.比如說(shuō),ID特征,因?yàn)镮D是唯一的,所有劃分到每個(gè)ID取值節(jié)點(diǎn)上也就一個(gè)數(shù)據(jù)點(diǎn),純度100%,熵為0.]

信息增益比率

GainRatio(D,f)=\frac{Gain(D,f)}{IV(f)}

其中,
IV(f) = -\sum_{v=1}^{V}\frac{|D_v|}{|D|}log_2\frac{|D_v|}{|D|}

D_v表示特征f取值為v的數(shù)據(jù)子集.

因?yàn)樾畔⒃鲆鏁?huì)傾向于選擇特征取值多的特征,所以,我們對(duì)多取值特征進(jìn)行懲罰,除以特征f的固有值[或者說(shuō)特征f的信息熵,f的信息熵越大,相應(yīng)f的取值情況越多,懲罰力度越大].

Gini指數(shù)

假設(shè)數(shù)據(jù)集D有K個(gè)類(lèi),樣本點(diǎn)屬于第k類(lèi)的概率為pk,則概率分布的基尼指數(shù)定義為:

Gini(D)=\sum_{k=1}^Kp_k(1-p_k) =1 - \sum_{k=1}^Kp_k^2

知道了gini指數(shù)的計(jì)算公式,計(jì)算劃分前的gini指數(shù),劃分后,計(jì)算各個(gè)節(jié)點(diǎn)的gini指數(shù)值,然后根據(jù)劃分后子節(jié)點(diǎn)的數(shù)據(jù)比例進(jìn)行加權(quán)求和,得到劃分后的總gini指數(shù),最后對(duì)兩次結(jié)果做差,得到特征f的劃分效果, 差值越大,分類(lèi)效果越好.

均方差MSE[和,不平均]

和分類(lèi)時(shí)相似,計(jì)算劃分前節(jié)點(diǎn)的均方差,劃分后計(jì)算子節(jié)點(diǎn)的均方差,依據(jù)數(shù)據(jù)比例加權(quán)平均,再計(jì)算兩次結(jié)果差值,差值越大越好.

MAE也可以用作特征選擇指標(biāo),和MSE類(lèi)似.

決策樹(shù)生成

決策樹(shù)本質(zhì)上也是一棵樹(shù),所以符合數(shù)據(jù)結(jié)構(gòu)中樹(shù)的一般性構(gòu)造過(guò)程,也就是遞歸.

既然是遞歸構(gòu)建過(guò)程,首先要明白的是遞歸終止條件,否則就會(huì)陷入死循環(huán).那么決策樹(shù)的終止條件是什么呢?決策樹(shù)中符合終止條件時(shí),停止繼續(xù)劃分,生成葉節(jié)點(diǎn).

如果是分類(lèi)樹(shù):

  1. 如果節(jié)點(diǎn)數(shù)據(jù)全是同一類(lèi)別,停止遞歸[沒(méi)有必要了,都是自己人];
  2. 如果特征列表為空,停止遞歸[在分類(lèi)問(wèn)題中,一般情況下,每種劃分特征只會(huì)用一次,用完就扔了---負(fù)心漢];
  3. 如果所有樣本在所有特征上取值都相同,停止遞歸[特征沒(méi)用,不具有區(qū)分度---所有特征上取值都相同,千篇一律]

如果是回歸樹(shù),回歸樹(shù)通常會(huì)設(shè)定自定義的參數(shù),比如均方差變化最小值,每個(gè)節(jié)點(diǎn)容忍的最小樣本數(shù),相應(yīng)的條件:

  1. 均方差變化太小[小于預(yù)定義的閾值];
  2. 劃分后節(jié)點(diǎn)的樣本量太少[小于預(yù)定義的閾值,比如只有2,3個(gè),小貓兩三只沒(méi)有必要繼續(xù)劃分了];
[終止條件]檢測(cè)數(shù)據(jù)集中的每個(gè)子項(xiàng)是否屬于同一分類(lèi),or 特征集為空：

    If so:  return  類(lèi)標(biāo)簽

    Else:
        尋找劃分?jǐn)?shù)據(jù)集的最好特征（--基于信息增益）
        劃分?jǐn)?shù)據(jù)集
        創(chuàng)建分支結(jié)點(diǎn)
            for    每個(gè)劃分的子集
                調(diào)用自己，并增加返回結(jié)果到分支結(jié)點(diǎn)中

        return    分支結(jié)點(diǎn)

上面?zhèn)未a中存在一個(gè)問(wèn)題, 類(lèi)標(biāo)簽怎么確定?
如果葉子節(jié)點(diǎn)都屬于同一類(lèi)別,那么給定所屬類(lèi)別即可;如果葉子節(jié)點(diǎn)數(shù)據(jù)屬于不同的類(lèi)別,大家進(jìn)行投票決定,服從多數(shù)人的利益[少數(shù)服從多數(shù)].

樹(shù)剪枝

因?yàn)樵跊Q策樹(shù)的構(gòu)建過(guò)程中,可能會(huì)存在過(guò)擬合現(xiàn)象,或者說(shuō)決策樹(shù)深度太深,太過(guò)于復(fù)雜;因此,我們可以對(duì)決策樹(shù)進(jìn)行剪枝處理.剪枝又分為預(yù)剪枝和后剪枝.

預(yù)剪枝是指在決策樹(shù)生成過(guò)程中,對(duì)每個(gè)節(jié)點(diǎn)在劃分前先進(jìn)行估計(jì),如果當(dāng)前的劃分不能帶來(lái)決策樹(shù)泛化性能的提升[泛化性能可以用錯(cuò)誤率,或者說(shuō)均方差衡量],則停止劃分將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn).

后剪枝過(guò)程是一個(gè)不斷嘗試的過(guò)程:找到葉子節(jié)點(diǎn),嘗試合并[將葉子節(jié)點(diǎn)的雙親變成葉子節(jié)點(diǎn)],比較合并前后的變化效果.變化效果需要定量分析,這個(gè)數(shù)據(jù)量指標(biāo)分類(lèi)問(wèn)題可以使用錯(cuò)誤率,回歸樹(shù)可以使用均方差, 而指標(biāo)的計(jì)算需要數(shù)據(jù),因此我們需要一定的測(cè)試數(shù)據(jù),然后使用測(cè)試數(shù)據(jù)在已經(jīng)生成的決策樹(shù)上進(jìn)行不斷測(cè)試,假如合并后比合并前效果好,分類(lèi)問(wèn)題上就是錯(cuò)誤率降低了,回歸問(wèn)題上均方差減少了,我們就進(jìn)行合并處理[或者說(shuō)是剪枝處理].

其他問(wèn)題

決策樹(shù)使用范圍,或者說(shuō)對(duì)數(shù)據(jù)集的要求: 標(biāo)稱數(shù)據(jù)或數(shù)值型數(shù)據(jù).本質(zhì)上,決策樹(shù)只適用于標(biāo)稱型數(shù)據(jù)[也就是離散數(shù)據(jù)],但如果是連續(xù)數(shù)據(jù)[在特征取值上連續(xù)],我們需要進(jìn)行離散處理.不同類(lèi)型的決策樹(shù)處理問(wèn)題不同,有的決策樹(shù)需要對(duì)數(shù)據(jù)進(jìn)行預(yù)先離散化處理;但有的決策樹(shù)本身可以處理連續(xù)數(shù)據(jù).

決策樹(shù)在生成過(guò)程中會(huì)遇到各種各樣的問(wèn)題.有數(shù)據(jù)集的問(wèn)題,也有決策樹(shù)本身的問(wèn)題,而決策樹(shù)本身也有自己的適用范圍,不可能適用于所有問(wèn)題[一招鮮吃遍天impossible].比如說(shuō):

  • 連續(xù)數(shù)據(jù): 離散化處理;
  • 空缺數(shù)據(jù): 如果在某個(gè)特征上數(shù)據(jù)存在空缺值,怎么處理? 我們可以先將取特征上非空的數(shù)據(jù)子集,當(dāng)做非空數(shù)據(jù)處理,然后將特征取值為空記錄按照子節(jié)點(diǎn)數(shù)據(jù)的比率劃分到所有子節(jié)點(diǎn)上.
  • etc.

具體問(wèn)題具體分析,依據(jù)不同的任務(wù),數(shù)據(jù)集的不同特點(diǎn)選擇適合的算法模型.

代碼實(shí)現(xiàn)

repository 歡迎fork,star.

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

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

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