決策樹是一種基本分類與回歸方法佑力。其不要優(yōu)點是模型具有可讀性式散,分類速度快。學(xué)習(xí)時打颤,利用訓(xùn)練數(shù)據(jù)暴拄,根據(jù)損失函數(shù)最小化的原則建立決策樹模型。預(yù)測時编饺,對新的數(shù)據(jù)乖篷,利用決策樹模型進行分類。決策樹學(xué)習(xí)通常包括3個步驟:特征選擇透且、決策樹的生成和決策樹的修建撕蔼。這些決策樹學(xué)習(xí)的思想主要來源Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法豁鲤, 以及Breiman等人在1984年提出的CART算法。
一鲸沮、決策樹模型與學(xué)習(xí)
1.決策樹模型
分類決策樹是一種描述對實例進行分類的樹形結(jié)構(gòu)琳骡。決策樹由結(jié)點(node)和有向邊(directed edge)組成。結(jié)點有兩種類型:內(nèi)部結(jié)點(internal node)和葉結(jié)點(leaf node),內(nèi)部結(jié)點表示一個特征或?qū)傩运夏纾~結(jié)點表示一個類楣号。
用決策樹分類,從根結(jié)點開始怒坯,對實例的某一特征進行測試炫狱,根據(jù)測試結(jié)果,將實例分配到其子結(jié)點:這時剔猿,每一個子結(jié)點對應(yīng)著該特征的一個取值视译。如此遞歸地對實例進行測試,直至達到葉結(jié)點艳馒。最后將實例分到葉結(jié)點的類中憎亚。
2.決策樹與if-then規(guī)則
可以將決策樹看成一個if-then規(guī)則员寇,將決策樹轉(zhuǎn)換成if-then規(guī)則的過程是這樣的:由決策樹的根結(jié)點到葉結(jié)點的每一條路徑構(gòu)建一條規(guī)則:路徑上與內(nèi)結(jié)點的特征對應(yīng)著規(guī)則的條件弄慰,而葉結(jié)點的類對應(yīng)著規(guī)則的結(jié)論。每一條實例都被一條路徑或一條規(guī)則所覆蓋蝶锋,而且僅被一條路徑或一條規(guī)則所覆蓋陆爽。這里所謂覆蓋是指實例的特征與路徑上的特征一致或?qū)嵗凉M足規(guī)則的條件。
3.決策樹學(xué)習(xí)
假設(shè)給定訓(xùn)練數(shù)據(jù)集
其中,為輸入實例(特征向量)扳缕,n為特征個數(shù)慌闭,
,N為樣本容量躯舔。決策樹學(xué)習(xí)的目標是根據(jù)給定訓(xùn)練集構(gòu)建一個決策樹模型驴剔,使它能夠?qū)嵗M行正確地分類。
決策樹學(xué)習(xí)本質(zhì)上是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則粥庄。與訓(xùn)練數(shù)據(jù)集不相矛盾的決策樹(即能對訓(xùn)練數(shù)據(jù)集進行正確分類的決策樹可能有多個)丧失,也有可能一個也沒有苔巨。我們需要的是與一個訓(xùn)練數(shù)據(jù)矛盾教小的決策樹波势,同時具有很好的泛化能力。
決策樹學(xué)習(xí)用損失函數(shù)表示這一目標刻伊,決策樹的損失函數(shù)通常是正則化的極大似然函數(shù)训堆,決策樹的學(xué)習(xí)策略是以損失函數(shù)的最小化描验。
當損失函數(shù)確定以后,學(xué)習(xí)問題就變成為在損失函數(shù)意義下選擇最優(yōu)決策樹的問題坑鱼,因為從所有可能的決策樹選取最優(yōu)決策樹是NP完全問題膘流,所以現(xiàn)實中決策樹問題算法通常采用啟發(fā)式方法,近似求解這一個最優(yōu)化問題, 得到的決策樹是次最優(yōu)的睡扬。
二盟蚣、特征選擇
特征選擇在于選擇對訓(xùn)練數(shù)據(jù)具有分類能力的特征,這樣可以提高決策樹的學(xué)習(xí)效率卖怜。如果利用一個特征進行分類的結(jié)果與隨機分類的結(jié)果沒有很大差別屎开,則稱這個特征沒有分類能力。經(jīng)驗上扔掉這樣的特征對決策樹學(xué)習(xí)的精度影響不大马靠。通常特征選擇的準則是信息增益或信息增益比奄抽。
1.信息增益
為了便于說明,先給出熵與條件熵的定義甩鳄。
在信息論中逞度,熵(entropy)是表示隨機變量不確定性的度量。設(shè)X是一個取有限個值的離散隨機變量妙啃,其概率分布為
則隨機變量X的熵定義為
(2.1)式中的對數(shù)以2為底或以e為底(自然對數(shù))档泽,這時熵的單位分別稱為比特(bit)或納特(nat)。由定義可知揖赴,熵只依賴于X的分布馆匿,而與X的取值無關(guān),所以也可以將X的熵記作H(p)燥滑,即
熵越大渐北,隨機變量的不確定性越大。從定義上可驗證
當隨機變量只取1,0是铭拧,即X的分布為
熵為
當p=0或p=1時赃蛛,H(P)最大,隨機變量完全沒有不確定性搀菩。當p=0.5時呕臂,H(p)=1,熵取最大,隨機變量不確定性最大肪跋。
設(shè)隨機變量(X,Y)歧蒋,其聯(lián)合概率分布為
條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性。隨機變量X給定的條件下隨機變量Y的條件熵(conditional entropy)H(Y|X)澎嚣,定義為X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望
這里疏尿,
當熵和條件概率由數(shù)據(jù)估計(特別是極大似然估計)得到時,所對應(yīng)的熵與條件熵分別為經(jīng)驗熵(empirical entropy)和經(jīng)驗條件熵(empirical conditional entropy)易桃。
信息增益(information gain)表示得知特征X的信息而使得類Y的信息的不確定性減少的程度褥琐。
信息增益特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A),定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差晤郑。
一般的敌呈,熵H(Y)與條件熵H(Y|X)之差稱為互信熵(mutual information)贸宏。決策樹學(xué)習(xí)中的信息增益等價于訓(xùn)練數(shù)據(jù)中類與特征的互信熵
.
決策樹學(xué)習(xí)應(yīng)用信息增益準則選擇特征,給定訓(xùn)練數(shù)據(jù)集D和特征A磕洪,經(jīng)驗熵H(D)表示對數(shù)據(jù)集D進行分類的不確定性吭练,而經(jīng)驗條件熵H(D|A)表示在特征A給定的條件下對數(shù)據(jù)集D進行分類的不確定性。那么它們的差析显,即信息增益鲫咽,就表示由于特征A而使得對數(shù)據(jù)集D分類的不確定性減少的程度。顯然谷异,對數(shù)據(jù)集D而言分尸,信息增益依賴于特征,不同的特征往往具有不同的信息增益歹嘹。信息增益大的特征具有更強的分類能力箩绍。
設(shè)訓(xùn)練數(shù)據(jù)集為D,|D|表示樣本容量尺上,即樣本個數(shù)材蛛。設(shè)有K個類,
表示屬于類
的樣本個數(shù)怎抛,
卑吭。設(shè)特征A有n個不同的取值
,根據(jù)特征A的取值將D劃分為n個子集抽诉,
陨簇,
表示樣本個數(shù)吐绵,
迹淌,記子集
中屬于類
的樣本集合為
,即
為$D_{ik}的樣本個數(shù)己单,于是信息增益算法如下
輸入:訓(xùn)練數(shù)據(jù)集D合特征A唉窃;
輸出:特征A對訓(xùn)練集D的信息增益g(D,A)
(1)計算數(shù)據(jù)集D的經(jīng)驗熵H(D)
(2)特征A對數(shù)據(jù)集D的經(jīng)驗條件熵
(3)計算信息增益
g(D,A)=H(D)-H(D|A)
2.信息增益比
信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征,存在偏向于選擇取值較多的特征的問題纹笼,使用信息增益比(information gain ratio)可以對這一問題進行校正纹份。這是特征選擇的另一準則。
信息增益比特征A對訓(xùn)練數(shù)據(jù)集D的信息增益比定義為其信息增益g(D,A)與訓(xùn)練數(shù)據(jù)集D關(guān)于特征A的值的熵
之比廷痘,即
其中蔓涧,,n是特征A取值的個數(shù)。
3.基尼指數(shù)
分類問題中笋额,假設(shè)有K個類元暴,樣本點屬于第k類的概率為,則概率分布的基尼指數(shù)定義為
對于二分類問題兄猩,若有黑人點屬于第1個類的概率是p茉盏,則概率分布的基尼指數(shù)為
對于給定的樣本集合D鉴未,其基尼指數(shù)為
其中,是屬于第k類的樣本子集鸠姨,K是類的個數(shù)
如果樣本集合D根據(jù)特征A是否取某一可能值被分割成
和
兩部分铜秆,則在特征A的條件下,集合D的基尼指數(shù)定義為
基尼指數(shù)表示集合D的不確定性讶迁,基尼指數(shù)
表示經(jīng)
分割后集合D的不確定性连茧。基尼指數(shù)越大巍糯,樣本集合的不確定性也就越大梅屉,這一點與熵相似。
三鳞贷、決策樹的生成
1.ID3算法
ID3算法的核心在決策樹各個結(jié)點上應(yīng)用信息增益準則選擇特征坯汤,遞歸地構(gòu)建決策樹。具體方法是:從根結(jié)點(root node)開始搀愧,對結(jié)點計算所有可能的特征的信息增益惰聂,選擇信息增益最大的特征作為結(jié)點的特征,由該特征的不同取值建立子結(jié)點咱筛,再對子結(jié)點遞歸地調(diào)用以上方法搓幌,構(gòu)建決策樹:直到所有的特征的信息增益均很小或沒有特征可以選擇為止。最后得到一棵決策樹迅箩。ID3相當于用極大似然法進行概率模型的選擇溉愁。
ID3算法
輸入:訓(xùn)練集D,特征集A閾值
輸出:決策樹
(1)若D中所有實例屬于同一類饲趋,則T為單結(jié)點樹拐揭,并將類
作為該結(jié)點的類標記,返回T
(2)若奕塑,則T為單結(jié)點樹堂污,并將D中實例樹最大的類
作為該結(jié)點的類標記,返回T
(3)否則龄砰,按ID3算法計算各特征對D的信息增益盟猖,選擇信息增益最大的特征
(4)如果的信息增益小于閾值
,則置T為單結(jié)點樹换棚,并將D中實例數(shù)最大的類
作為該結(jié)點的類標記式镐,返回T
(5)否則,對的每一個可能值
固蚤,依
將D分割為若干非空子集
娘汞,將
中的類
作為該結(jié)點的類標記,返回T
(6)對第i個子結(jié)點颇蜡,以為訓(xùn)練集价说,以
為特征集辆亏,遞歸地調(diào)用步(1)~步(5),得到子樹
鳖目,返回
2.C4.5算法
C4.5在生成的過程中扮叨,用信息增益比來選擇特征。
C4.5算法
輸入:訓(xùn)練集D领迈,特征集A閾值
輸出:決策樹
(1)若D中所有實例屬于同一類彻磁,則T為單結(jié)點樹,并將類
作為該結(jié)點的類標記狸捅,返回T
(2)若,則T為單結(jié)點樹尘喝,并將D中實例樹最大的類
作為該結(jié)點的類標記磁浇,返回T
(3)否則,按C4.5算法計算各特征對D的信息增益朽褪,選擇信息增益最大的特征
(4)如果的信息增益小于閾值
置吓,則置T為單結(jié)點樹,并將D中實例數(shù)最大的類
作為該結(jié)點的類標記缔赠,返回T
(5)否則衍锚,對的每一個可能值
,依
將D分割為若干非空子集
嗤堰,將
中的類
作為該結(jié)點的類標記戴质,返回T
(6)對第i個子結(jié)點,以為訓(xùn)練集踢匣,以
為特征集告匠,遞歸地調(diào)用步(1)~步(5),得到子樹
符糊,返回
3.CART算法
分類與回歸樹(classification and regression tree,CART)模型是由Breiman等在1984年提出凫海,是應(yīng)用廣泛的決策樹學(xué)習(xí)方法呛凶,CART同樣由特征選擇男娄、樹的生成及剪枝組成,既可以用于分類也可以用于回歸漾稀。
(1)回歸樹生成
假設(shè)X與Y分別為輸入和輸出變量模闲,并且Y是連續(xù)變量,給定訓(xùn)練數(shù)據(jù)集
一棵回歸樹對應(yīng)著輸入空寂(即特征空間)的一個劃分及在劃分的單位上的輸出值崭捍,假設(shè)已將輸入空間劃分為M個單元尸折,并且每個單元
上有一個固定的輸出值
,于是回歸樹表示為
當輸入空間的劃分確定時殷蛇,可以用平方誤差來表示回歸樹對于訓(xùn)練數(shù)據(jù)上的誤差实夹,用平方誤差最小的準則來求解每個單元上的最優(yōu)輸出值橄浓。易知,單元
上的
的最優(yōu)值
是
上的所有輸入實例
對應(yīng)的輸出
的均值亮航,即
最小二乘回歸樹
問題是怎么樣對輸入空間進行劃分荸实,這里采用啟發(fā)式方法,選擇第j個變量和他的取值s缴淋,作為 切分變量(splitting variable)和切分點(splitting point)准给,并定義兩個區(qū)域
然后尋找最優(yōu)切分變量j和切分點s,具體地求解
對固定輸入j可以劃分最優(yōu)切分點s
遍歷所有輸入變量重抖,找到最優(yōu)的切分變量j露氮,構(gòu)成一對(j,s)。依次將此輸入變量劃分成兩個區(qū)域钟沛。接著對每個區(qū)域重復(fù)上述劃分過程畔规,直到滿足停止條件為止,這樣就生成一棵回歸樹恨统。這樣的回歸樹通常稱為最小二乘回歸樹(least squares regression)
(2)分類樹
輸入:訓(xùn)練集D油讯,停止計算條件
輸出:CART決策樹
(1)設(shè)結(jié)點的訓(xùn)練數(shù)據(jù)集為D,計算現(xiàn)有特征對該數(shù)據(jù)集的基尼指數(shù)延欠。此時陌兑,對每一個特征A,對其可能取的每個值由捎,根據(jù)樣本點對
的測試為"是"或"否"兔综,將D分割成
兩部分,計算
此時的基尼指數(shù)
(2)在所有可能的特征A以及所有可能的切分點中狞玛,選擇基尼指數(shù)最小的特征及其對應(yīng)的切分點作為最優(yōu)特征與最優(yōu)切分點软驰。依最優(yōu)特征與最優(yōu)切分點,從現(xiàn)結(jié)點生成兩個子結(jié)點心肪,將訓(xùn)練數(shù)據(jù)集依特征分配到兩個子結(jié)點中去
(3)對兩個子結(jié)點遞歸調(diào)用(1),(2)锭亏,直至滿足停止條件
(4)生成CART決策樹
四、決策樹剪枝
決策樹生成算法遞歸地產(chǎn)生決策樹硬鞍,直到不能繼續(xù)下去為止慧瘤。這樣產(chǎn)生的樹往往對訓(xùn)練數(shù)據(jù)的分類很準確,但對未知的測試數(shù)據(jù)卻沒那么準確固该,即出現(xiàn)了過擬合現(xiàn)象锅减。過擬合的原因在于學(xué)習(xí)時過多的考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類,將訓(xùn)練數(shù)據(jù)中的噪音也學(xué)習(xí)了伐坏,從而構(gòu)建出過于復(fù)雜的決策樹怔匣。
在決策樹學(xué)習(xí)中將已生成的樹進行簡化的過程稱為減枝(pruning),具體地桦沉,剪枝從已生成的樹減掉一些子樹或葉結(jié)點每瞒,并將其根結(jié)點作為新的葉結(jié)點從而簡化分類樹模型金闽。
決策樹剪枝往往通過極小化決策樹整體的損失函數(shù)(loss function)或代價函數(shù)(cost function)來實現(xiàn),設(shè)樹T的葉結(jié)點個數(shù)為|T|剿骨,t是樹T的葉結(jié)點呐矾,該葉結(jié)點有個樣本,其中k類的樣本點有
個懦砂,
蜒犯,
為葉結(jié)點t上的經(jīng)驗熵,
為參數(shù)荞膘,則決策樹學(xué)習(xí)的損失函數(shù)可以定義為
其中經(jīng)驗熵為
在損失函數(shù)中罚随,將(4.1)右端的第1項記作
這時有
式(4.3),表示模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差羽资,即模型與訓(xùn)練數(shù)據(jù)的擬合程度淘菩,
表示模型復(fù)雜度,參數(shù)
控制兩者之間的影響屠升,較大的
促使選擇教簡單的模型(樹)潮改,較小的
促使選擇教復(fù)雜的模型(樹),
意味著只考慮模型與訓(xùn)練數(shù)據(jù)的擬合程度腹暖,不考慮模型的復(fù)雜度汇在。