05_決策樹算法_台中搬家公司

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

擁有後台管理系統的網站,將擁有強大的資料管理與更新功能,幫助您隨時新增網站的內容並節省網站開發的成本。

  今天是2020年2月7日星期五。分享一個箴言:世界上只有一種英雄主義,那就是認識生活的真相后依然愛它。

  好了,開始今天的內容,決策樹算法。書中針對該算法,洋洋洒洒講了很多內容,對初學者不太友好,我初讀本章內容時,頭大的很。但等到學完,頭腦里有了框架之後,該算法的學習就清楚了很多,所以稍後會寫一下該算法的脈絡主線,帶着框架去完成該算法的搭建,這樣學習要輕鬆點。另外,在記錄這個學習過程前,我一般會在網上多看幾篇相關內容,發現各個內容各有所長,相應的,大家也要各取所需。

  脈絡主線:(1)總起講基本決策樹模型,闡述決策樹基本思路;(2)以ID3、C4.5為例分講三步驟:特徵選擇、決策樹生成、決策樹剪枝;(3)最後以經典CART算法結束決策樹的學習,該算法應用決策樹基本思路,細品起來還是挺不一樣的。

 GitHub:https://github.com/wangzycloud/statistical-learning-method

 決策樹算法

引入

  決策樹算法是一種呈樹形結構的基本分類與回歸方法,本內容主要討論用於分類的決策樹,基於特徵對實例進行分類。像書中提到的,決策樹算法可以認為是if-then規則的集合,即根據特徵的不同取值進行分支選擇;也可以認為是定義在特徵空間與類空間上的條件概率分佈,即通過構建決策樹將特徵空間劃分成不同子空間,恭弘=叶 恭弘節點上的子空間對應條件概率最大的類,分類時將‘特徵符合’的實例點強行分到該空間對應的類上(認為順着根節點到恭弘=叶 恭弘節點,在符合各內部節點特徵的條件下,實例點是該類的條件概率最大)。

  學習時,該算法利用訓練數據集,根據損失函數最小化的原則建立決策樹模型;預測時,對新的數據,利用決策樹模型進行分類。決策樹的學習,通常由三個步驟構成:特徵選擇、決策樹的生成、決策樹剪枝。接下來按照提到的脈絡主線,記錄決策樹模型基本思路、三大步驟(ID3、C4.5)、CART算法。

決策樹模型

  先來看一下定義:

  用圓框表示內部節點,用方框表示恭弘=叶 恭弘節點,有了樹形結構,它是怎麼分類的呢?這裏我們用判斷來診人員是否需要輸液的例子:

  內部節點表示特徵,用決策樹進行分類,就是從根節點開始,對實例的某一特徵進行測試。根據測試結果,選擇合適的分支,將實例分配到該分支對應的子節點上,這時每一個子節點對應着該特徵的一個取值。遞歸的對實例進行測試,直至到達恭弘=叶 恭弘節點,最後將實例分配到恭弘=叶 恭弘節點對應的類中。看一下圖中的例子,對於新的來診人員,從我們的生活經驗上,醫生一般會讓我們先測試一下體溫,如果體溫過高的話,基本上是需要打個退燒針了;測完體溫后,醫生會進行聽診,然後看咽喉是否發炎,了解下咳嗽情況。也就是說,判斷完體溫特徵后,再判斷下一個特徵乾咳是否嚴重,每個特徵判斷完畢,就可以根據不同的分支結果,確定患者是否需要輸液了。

  對決策樹的理解,書中有兩個解釋。

  首先第一個,決策樹與if-then規則,也就是與選擇分支結構的關係。從判斷來診人員是否需要輸液的例子上,我們可以看到決策樹模型分類的過程,就是從根節點到恭弘=叶 恭弘節點的一條路徑。路徑上內部節點的特徵對應着選擇分支的判別條件,子節點對應着條件的不同分支,恭弘=叶 恭弘節點的類對應着判別的結果。另外,構成分類決策的所有路徑,也就是選擇分支的所有條件,具有一個重要的性質:互斥且完備。每個實例從根節點判別開始,到恭弘=叶 恭弘節點得到分類結果結束,都有屬於自己的一條路徑,有且僅有一條路徑,並且該決策樹能把訓練集所有實例判別。

  第二個是從條件概率分佈的角度,也就是在給定特徵條件下類的條件概率來理解決策樹算法。書中指出,這一條件概率分佈定義在特徵空間的一個劃分上。在我的理解中,這句話要拆開來看,(1)求誰的概率,在哪個條件上?(2)特徵空間是怎樣劃分的?

  第一點很明確,求恭弘=叶 恭弘節點類別的概率,條件是各項已知的特徵。在輸液例子中,要求的類別:是否需要輸液;特徵有兩個:體溫情況、乾咳程度。要求恭弘=叶 恭弘節點的條件概率就是求分別在給定體溫高燒、體溫正常乾咳嚴重、體溫正常乾咳正常條件下,是否需要輸液的概率。對於第二點,說起特徵空間的劃分,很容易想到我們之前接觸到的kd樹算法,它就是對特徵空間進行劃分,輪流從不同維度取中位數對特徵空間進行劃分。在決策樹算法中,輸液的這個例子,如果將各個特徵,看成不同維度(幾個特徵,幾個維度坐標軸),進行特徵選擇的過程,不就是將特徵空間逐步劃分成小單元的過程。簡單講,將特徵數目看成維度數目,將特徵值取值的數目看成該維度坐標軸的切分點。從根節點到恭弘=叶 恭弘節點的路徑,不就是在特徵空間中從原點行走到某個小空間單元的過程(決策樹中的一條路徑對應於劃分的一個單元)。

  再返回去看第一點在給定特徵下的條件概率,也就是根據在不同特徵上的取值,將特徵空間劃分成了小單元。該條件概率就是在各個恭弘=叶 恭弘子節點小單元的條件下(條件也就是決策樹中從根節點到恭弘=叶 恭弘子節點,每層特徵取固定的值),將每個單元定義成某個類別的概率。另外,各恭弘=叶 恭弘子節點(單元)上的條件概率往往偏向於一個類,即屬於某一類的概率較大。比如說,體溫高燒這條路徑對應的恭弘=叶 恭弘子節點,需要輸液的條件概率要遠遠大於體溫高燒不需要輸液的條件概率;‘體溫正常乾咳正常’這路徑對應的恭弘=叶 恭弘子節點,不需要輸液的條件概率遠遠大於‘體溫正常乾咳正常’需要輸液的概率。

決策樹學習

  從上一部分的分析中,可以看出,決策樹學習本質上就是從訓練數據集中,通過特徵選擇歸納出一組分類規則。另外,樹形結構每層選擇‘作為根節點的特徵’不同,構造出來的決策樹也就不同。同時能對訓練集進行正確分類的決策樹可能有多個,也可能一個沒有。我們的目標是通過損失函數,學習到一個對訓練數據集更好分類前提下,能夠對新數據有很好泛化能力的決策樹模型。

  這裏提到了一個最優特徵的概念,表示特徵之間的重要性是不一樣的,構建決策需要從最重要的特徵開始考慮,下一層選擇次優的特徵,下下次選擇次次優的特徵。這是有實際意義的,以是否輸液為例,對於醫生來講,判斷一個感冒病人是否需要輸液,“體溫是不是高”這個特徵表現,要遠比“乾咳嚴不嚴重”的特徵表現,更能決定是不是需要輸液。一旦體溫很高,這直接決定了需要輸液,“判斷”這個過程的不確定性,直接降了下來(體溫高燒->需要輸液);而如果先判斷“乾咳嚴不嚴重”,這個特徵表現不能全然斷定需要輸液。還要繼續用“體溫高不高”這個特徵再測試一下才能確定。這個“判斷”過程的不確定性,是逐步降下來(乾咳正常->體溫高燒->需要輸液)。

  通過上述方法構建的決策樹,可能對訓練數據集有很好的分類能力,但是對未知的測試數據卻未必有很好的分類能力,有可能發生過擬合現象。直觀點來說,決策樹構建的越細密,訓練集特徵空間切分也就越微小越明確,有可能鄰近個幾個小空間都屬於一類。完全沒必要切分這麼細,樹形越複雜越容易出現過擬合。這就需要我們對已生成的樹進行自下而上的剪枝,將樹變的更簡單,從而具有更好的泛化能力。具體來講就是去掉過細的恭弘=叶 恭弘節點,使其退回到父節點,讓父節點成為新的恭弘=叶 恭弘子節點。當然,如果特徵的數量較多,在構建決策樹的開始,就可以對特徵進行選擇,只留下對數據集有很好分類能力的特徵。

  通過上述決策樹學習算法的描述,可以發現生成決策樹的過程,是一個細分特徵空間,對實例點進行局部選擇的過程。盡可能讓每個實例從原點到達特徵空間的某一個具有確定類別的區域,且該區域能夠對實例做出正確的判斷;如果樹形過大過細過複雜,就意味着決策樹能夠對當前訓練數據集有非常非常好的判斷(都是長路徑)。一旦來新數據(需要新路徑進行分類),找不到分類規則就不能判斷,因此需要將樹形消減,去掉過細的恭弘=叶 恭弘節點,讓最優的特徵發揮作用。從主要特徵上對新數據判斷(短的路徑),將樹形修減到合適的程度也就是考慮全局最優。

特徵選擇

  在決策樹學習的過程描述里,提到了一個“最優特徵”的概念,也就是實例點在特徵選擇分支的條件判斷中,從根節點到恭弘=叶 恭弘節點,“特徵判斷”有一個先後順序,看一下判斷患者是否需要輸液的例子,先判斷體溫?還是先判斷乾咳?一般經驗下,肯定是先判斷是不是出現高燒,也就是判斷體溫這個特徵比判斷乾咳的特徵優先級高。

  特徵選擇就是決定用哪個特徵來劃分特徵空間,關鍵在於選取對訓練數據具有分類能力的特徵,這樣可以提高決策樹學習的效率。如果利用一個特徵進行分類的結果與隨機分類的結果沒有很大差別,則稱這個特徵是沒有分類能力的。經驗上丟掉這樣的特徵對決策樹學習的精度影響不大,通常特徵進行選擇的準則是信息增益或信息增益比。這裏我們使用書上的例5.1。

  通過該圖解,可以看到選擇不同的特徵作為根節點,可以得到不同的決策樹;某特徵的不同取值,成為子節點的不同分支。

  至於信息增益這個概念,我在剛開始接觸這本書的時候,理解起來困難還是蠻大的,概率沒怎麼學,熵、條件熵也不知道是啥。看到“熵”這個字,腦子里全是高中物理里的“熵”,也就是體系混亂程度的度量,本書裡邊用“熵”表示隨機變量不確定性的度量,這兩個定義好像表達的是一個意思。擲出硬幣后,在空中翻轉是一個旋轉不定的過程(動能勢能不斷的轉換),這中間正面朝上是個說不準的事情,不確定性非常高,一會正一會反;硬幣正面朝上落在桌子上了,靜止不動(相對平衡的體系狀態),正面朝上就是一個確定的事情。然後先看“信息增益”的作用是什麼,再去理解“信息增益”是個啥。

  在我的理解里,“信息增益”是讓“熵”減小的能力度量單位。也就是某個東西能讓目標整體的不確定性減小,就是指通過特徵A的劃分讓分類目標的不確定性減小的能力度量單位。比如說,判斷體溫高燒要比判斷是否乾咳更能決定是否需要輸液,即體溫特徵比乾咳特徵在是否輸液這個分類目標上,具有更好的讓不確定性減少的能力。簡而言之,信息增益就是得知特徵X而使得類Y的信息不確定性減少的程度

  先來看一下熵與條件熵的定義。

  之前提到,高中物理裡邊的熵是體系的混亂程度,反映到信息論與概率統計中,不正好就是隨機變量取值的不確定性。由公式5.1,可以看到離散隨機變量X的熵與該隨機變量具體取什麼值沒有關係,只與它取值的概率分佈有關。看一下擲硬幣這種二分類的例子。

  類似於擲硬幣的過程,只有正反面兩種結果,P(正面)≈P(反面),如圖5.4所示,p=0.5時,擲硬幣的結果最不確定(這個時候的熵最大),是正是反都有可能,但是哪一面最有可能呢?誰也說不上,因為正反面的概率一分為二,都是50%的概率。如果改變一下硬幣的形狀,變成類似圓台的形狀,讓面積大的一側是反面,面積小的一側是正面(同時把高拉長)。這時再擲硬幣,誰都知道面積大的面會朝下(90%),這是很確定的事情,反面朝上的概率很小(10%),這個時候再去猜測哪個面會朝上,大家肯定都會說是正面,因為正反面的概率差別很大,這件事情的確定性大(這個時候熵比較小)。

  顧名思義,條件熵反映的是隨機變量Y在給定隨機變量X條件下的不確定性。這裏公式5.5有待證明,但在公式的直觀表示上(公式右端,每個條件下Y的熵乘以條件出現的概率再加和),可以看出H(Y|X)的求法。Y在Xi的條件下,要把所有Xi、Y聯合出現的概率求出條件熵(Y|Xi熵),乘以該Xi條件下Y|Xi熵的概率,最後加和。

  當熵和條件熵中的概率由訓練數據集通過極大似然估計得到時,對應的熵和條件熵分別稱為經驗熵、經驗條件熵。如果有0概率,令0log0=0。

  熵是不確定性的衡量,信息增益是讓不確定性減少的程度,在決策樹中,也就是得知特徵X的信息從而使得類Y的信息的不確定性減少的程度,具體定義如下。

  這裏假設存在訓練數據集D,D中數據共有K個類別Ck,k=1,2,3,…,K,其中:

    |D|表示樣本容量,即樣本個數;

    |Ck|表示屬於Ck這個類別的樣本個數;

  設特徵A有n個不同的取值{a1,a2,…,an},根據A的取值將數據集D劃分成n個子集D1,D2…Dn,其中:

    |Di|表示子集Di樣本容量,即子集Di的樣本個數;

  根據假設,有以下等式成立:

    

  記子集Di中屬於類Ck的樣本的集合為Dik,即Dik=Di∩Ck,其中:

    |Dik|表示Dik樣本容量,即集合Dik的樣本個數;

  匯總如下:

    

  於是得到信息增益算法5.1如下:

  例5.2是根據表5.1貸款申請樣本數據表計算最優特徵的過程。注意到,根據算法5.1,首先計算整個集合D對於分類問題的檢驗熵,也就是得到當前數據判斷類別的不確定性。其次,逐個計算每個特徵條件下,對數據集D的檢驗條件熵。最後分別計算各個特徵的信息增益,並進行比較,選擇信息增益最大的特徵作為最優特徵。

  在算法5.1部分,各個熵的計算直接給出了計算公式,從公式的直觀形式上,通過各事件出現的頻率來估計概率,好像是極大似然估計得到的公式,但是書中並沒有提及公式來源。

  要知道,信息增益是ID3算法中進行最優特徵選擇的準則,在接下來的決策樹生成部分,會詳細寫一下ID3算法。與ID3算法同時學習的是C4.5算法,自然而然,C4.5算法是ID3算法的改進,改進的地方很簡單,就是將特徵選擇的準則由信息增益改為了信息增益比。先來看一下信息增益比的計算方式,再分析優點。

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

還在煩惱搬家費用要多少哪?台中大展搬家線上試算搬家費用,從此不再擔心「物品怎麼計費」、「多少車才能裝完」

  從公式5.10中可以看到,信息增益比多了一個分母。分母是數據集D關於每個特徵取值的熵。也就是對某個特徵計算完信息增益后,要比上數據集D關於該特徵取值劃分成對應子類的熵。

  C4.5作為ID3算法的改進,要想了解信息增益比的優點,可以先了解信息增益的缺點。用信息增益作為劃分訓練數據集的特徵,存在偏向於選擇取值較多的特徵的問題。這一點怎麼理解呢?在公式5.8中可以發現,如果某個特徵取值較多,該取值的實例數目所佔的比例大,導致該特徵的條件經驗熵高,因此該特徵的信息增益值大。其實就是相當於,取該值的特徵非常多,該特徵成為了去往恭弘=叶 恭弘節點的必經路徑,形成了往這裏劃分一定能行這種邏輯,劃分后必然降低不確定性,但是該特徵不一定具有很好的特徵選擇能力。

  使用信息增益比就可以對這個問題進行改進,注意到公式5.10中HA(D)的描述,針對特徵A的取值計算數據集D的熵,這個熵與H(D)的區別在於子集劃分規則不同。H(D)是關於類別Y的熵,HA(D)是關於特徵A子集的熵。這裡有待深入學習,沒有解釋為什麼可以校正。

決策樹的生成

  本節內容從ID3算法入手,學習一下決策樹的生成,上文提到ID3算法的核心是在決策樹各個節點上應用信息增益準則選擇特徵,遞歸的構建決策樹。具體方法是:從根節點開始,對節點計算所有可能的特徵的信息增益,選擇信息增益最大的特徵作為節點的特徵,由該特徵的不同取值建立子節點;再對子節點遞歸的調用以上方法,構建決策樹;直到所有特徵的信息增益均很小或者沒有特徵可以選擇為止。

  要知道ID3算法只有樹的生成,沒有剪枝過程,因此生成的決策樹容易發生過擬合。算法如下:ID3 相當於用極大似然法進行概率模型的選擇,怎麼理解?(不理解…@_@)

  算法流程圖:

  具體示例:

  C4.5的生成算法與ID3算法相似,特徵選擇改進為信息增益比。

決策樹剪枝

  前文提到,如果構建的決策樹非常細密,樹形非常複雜,會容易發生過擬合現象。這樣的樹往往對訓練數據的分類很準確,但對未知的測試數據進行分類的時候,卻沒有那麼準確。原因在於學習時過多的考慮如何提高對訓練數據的正確分類,從而構建出了複雜的決策樹。因此,是否可以考慮決策樹的複雜度,對已生成的決策樹進行簡化。

  簡化的過程稱為剪枝,從已生成的決策樹上剪掉一些子樹或者恭弘=叶 恭弘節點,並將其根節點或父節點作為新的恭弘=叶 恭弘節點,從而簡化決策樹模型。書中提到,決策樹的剪枝往往通過極小化決策樹整體的損失函數來實現。書中只是描述了公式及算法,並沒有闡述為什麼這樣做可以,這裏提出一個不成熟的觀點和理解。

  首先明確熵是不確定性的度量。構建決策樹的過程,是將整個特徵空間劃分為不同的小區域,通過一系列的特徵判斷,訓練集中的各個數據有了明確的安放位置,特徵空間內井井有條。生成決策樹,就是能夠最快的將不同數據劃分到相應恭弘=叶 恭弘節點的子空間中,且該子空間內的數據盡可能屬於同一類。決策的過程,就是在給定某個特徵的條件下,數據集D分類的不確定性減少;那麼對應到恭弘=叶 恭弘節點,給定恭弘=叶 恭弘節點特徵路徑的條件下,數據集D分類的熵應盡可能小。也就是說恭弘=叶 恭弘節點對應的數據,應該盡可能的一致,大家都屬於一個類最好了(算法5.2如果信息增益小於閾值,將實例數最大的類作為節點類標記,也就是恭弘=叶 恭弘節點對應的數據不一定屬於同一個類)。

  現在考慮這棵決策樹在訓練集上構建的好不好,是不是就可以通過恭弘=叶 恭弘節點的不確定性程度來反映。如果每個恭弘=叶 恭弘節點都是一類,也就是在恭弘=叶 恭弘節點特徵路徑的條件下,數據集D內的數據確定是屬於某個類,不確定性為零,就說這棵決策樹構建的非常好,但相應的,樹形會非常複雜。如果每個恭弘=叶 恭弘節點中數據不屬於同一個類,也就是在恭弘=叶 恭弘節點特徵路徑的條件下,數據集D內的數據不能完全確定屬於這個類,不確定性大,就不能說這是一棵好的決策樹,相應的樹形會比較簡潔。可以發現,恭弘=叶 恭弘節點的熵和樹形的複雜程度成反比關係,是不是可以利用該關係,設計一個損失函數,讓決策樹的分類能力和樹形的複雜程度做一個平衡。看一下書中的計算公式以及剪枝算法。

  設樹T的恭弘=叶 恭弘節點個數為|T|,t是樹T的恭弘=叶 恭弘節點,該恭弘=叶 恭弘節點上有Nt個樣本點,其中k類的樣本點數為Ntk個,k=1,2…K,Ht(T)為恭弘=叶 恭弘節點t上的經驗熵,α≥0為參數,則決策樹學習的損失函數可以定義為:

  公式5.11右端第一項,每個恭弘=叶 恭弘節點的經驗熵多乘了一個係數(該節點的樣本個數),暫時看不出意義在哪裡。在公式5.13上,該係數消去了一個分母,看不出別的門道來,貌似也沒有把計算變簡單,畢竟log后仍然求分數(小數過小是不是會導致溢出?log里的小數沒有溢出問題,不知道是不是這個原因)。

  在公式5.14中,可以看到C(T)表示模型對訓練數據的預測誤差,即模型與訓練數據的擬合程度,也就是觀點裡邊該決策樹是否將數據集很好分類的能力。|T|表示模型複雜度,α控制兩者之間的影響,相當於權重因子(數值大,則該項被優化的力度大)。較大的α促使選擇較簡單的決策樹,較小的α促使選擇較複雜的決策樹,α=0意味着只考慮模型與訓練數據的擬合程度,不考慮模型的複雜度(正則化項)。

  可以看出,決策樹生成只考慮了通過提高信息增益或者信息增益比對訓練數據進行更好的擬合,而決策樹剪枝通過優化損失函數還考慮了減小模型複雜度。圖5.6是決策樹剪枝過程的示意圖,看一下剪枝算法:

CART算法

  CART算法是分類與回歸樹(classification and regression tree)的簡稱,同樣由特徵選擇、樹的生成和剪枝組成,既可以用於分類也可以用於回歸。與ID3、C4.5算法構建決策樹不同的是,CART假設決策樹是二叉樹,內部節點特徵取值為“是”和“否”,左分支是取值為“是”的分支,右分支是取值為“否”的分支,這樣的決策樹等價於遞歸的二分每個特徵,將輸入空間即特徵空間劃分成有限個單元。該算法同樣是給定輸入變量X條件下輸出隨機變量Y的條件概率分佈的學習方法,在劃分后的每個單元上確定預測的概率分佈,也就是在輸入給定的條件下輸出的條件概率分佈。

  這裏需要注意理解“遞歸的二分每個特徵”,ID3算法構建決策樹時,我們沒有強調是一棵二叉樹。因為每個特徵的取值,不固定只有兩個取值,我們根據該特徵的取值,劃分為不同子樹,幾個取值幾個子樹。現在“遞歸的二分每個特徵”要構建一棵二叉樹,是不是和多個取值的特徵發生矛盾呢?沒矛盾的話怎麼處理呢?比如體溫有三個取值:高溫、正常、低溫,遞歸的二分每個特徵是指細分每個特徵的取值。之前體溫特徵內部節點的判別結果有三個分支,現在內部節點判別條件變為是否高溫、是否正常、是否低溫,相應內部節點的判別結果分成兩個分支。具體做法仍然是生成和剪枝兩個部分。

CART-分類樹的生成

  類似於ID算法的生成過程,CART分類樹使用基尼指數來選擇最優特徵,同時決定該特徵的最優二值切分點。先看一下基尼指數的定義:

  可以看到公式5.23計算方式是公式5.22在二分類問題下的特殊情況,公式5.24使用頻率估計概率,得到樣本集合D下判別K類的基尼指數。類似於條件熵,在已知某特徵取值下的表示為:

  基尼指數Gini(D)表示集合D的不確定性,基尼指數Gini(D,A)表示經A=a分割後集合的不確定性。與熵類似,基尼指數的值越大,樣本集合的不確定性也就越大。CART生成算法:

  算法流程圖:

  計算例子:

CART-回歸樹的生成

  顧名思義,回歸樹是決策樹算法在回歸問題上的應用。

  我們先來思考一下,回歸問題應該和分類問題有什麼差異,再看接下來的內容。

  第一個問題,回歸樹模型是什麼樣子的。之前提到的決策樹模型,都是關於分類問題,通過特徵選擇對特徵空間進行劃分,被劃分到決策樹恭弘=叶 恭弘子節點對應子空間上的實例,屬於同一類別;我們知道回歸問題輸出變量應為連續值,是不是就意味着回歸問題里,類別數目非常非常多,多到像連續值的排列一樣。子空間劃分成的各個小單元,標記不再是類別,而是一系列數值。

  第二個問題,對什麼進行選擇,從而劃分特徵空間。分類樹中,各個數據基本上都是非數值型的,存在很多特徵分量,我們根據各個特徵的取值概率,找最優的特徵作為切分數據集的標準;在回歸問題中,輸入一般為數值型數據,決策樹模型需要找到切分點,回歸問題中怎麼處理呢?

  第三個問題,切分點選擇的準則是什麼。分類樹中,我們通過信息增益或者信息增益比來選擇最優特徵作為子樹節點的切分點;在回歸樹中,要通過什麼準則對什麼進行選擇,從而劃分特徵空間?

  帶着這三個問題,我們看一下回歸樹模型及算法。

  這裏可以幫助解決第一個問題,公式5.16反映了回歸樹模型的基本模式。決策樹建樹的過程,對應了特徵空間的劃分,劃分成的每個子空間,能夠安放具有相同特徵的數據實例,給他們具體的類別標記。在回歸問題上,劃分后的子空間單元同樣可以用來表示回歸模型的輸出值。詳細看一下公式5.16,指示函數部分表示,屬於Rm類時,該值為1,用回歸樹模型進行預測時,屬於該子空間的實例,賦予輸出值為Cm。注意該公式的求和函數部分,輸入數據x遍歷每個子空間單元,遍歷到所屬的子空間后,得到輸出值Cm,遍歷其它子空間時不得值(因為指示函數條件不滿足時,值為0),f(x)=0+0+…+Cm+…+0=Cm。

  該部分提出了平方誤差的計算思路,用於衡量訓練數據的預測誤差很好理解;用於求解每個單元上的最優輸出值,類似於分類樹中選擇實例數量最多的類,目的在於找到該單元所代表的最優值。為什麼均值會是最優值?原因就在於平方誤差函數,取均值時,與其它值做差,方差最小。

  這裏可以幫助解決第二、三個問題,採取什麼準則對什麼進行選擇。書中描述為,選取合適的變量(第幾個實例)作為切分變量,其值為切分點。也就是說用第n個變量的值來劃分特徵空間,並且採用平方誤差來作為切分點的選擇標準。公式5.19很好理解,首先明確該公式希望找到最優的切分變量和最優切分點,此時誤差值最小;中括號里分成了兩部分,也就是切分點s兩側的情況;我們要使總誤差值最小,就要使中括號中s左右兩側的誤差都保持最小;先看左側部分(R1),我們要找到合適的輸出值c1使該項誤差最小;實際上,左側部分最合適的c1就是左側部分所有yi的均值;右側同理。

  公式5.20表示的過程,我們很難直接計算出來,但我們可以採用遍歷的笨方法,把所有的輸入變量遍歷一遍,去找最優的切分變量j。在遍歷過程中,每個變量依次將特徵空間劃分為兩個區域,對每個區域重複上述劃分過程,直到滿足停止條件未知。也就是下邊的最小二乘回歸樹生成算法。

CART剪枝

  該部分一個大公式,需要深入學習下~開學后整起。

代碼效果

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※推薦台中搬家公司優質服務,可到府估價

台中搬鋼琴,台中金庫搬運,中部廢棄物處理,南投縣搬家公司,好幫手搬家,西屯區搬家