一棵決策樹(shù)包含一個(gè)根結(jié)點(diǎn)、若干個(gè)內(nèi)部結(jié)點(diǎn)和若干個(gè)葉結(jié)點(diǎn)；葉結(jié)點(diǎn)對(duì)應(yīng)于決策結(jié)果，其他每個(gè)結(jié)點(diǎn)則對(duì)應(yīng)一個(gè)屬性測(cè)試；每個(gè)結(jié)點(diǎn)包含的樣本結(jié)合根據(jù)屬性測(cè)試的結(jié)果被劃分到子結(jié)點(diǎn)中；根結(jié)點(diǎn)包含樣本全集，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的每個(gè)葉結(jié)點(diǎn)的路徑對(duì)應(yīng)一個(gè)判定測(cè)試序列。決策樹(shù)學(xué)習(xí)的目的是為了產(chǎn)生一棵泛化能力強(qiáng)，也就是能夠處理未見(jiàn)實(shí)例的決策樹(shù)。

信息熵是度量樣本集合純度最常用的一種指標(biāo)。假設(shè)樣本集合D中第k類(lèi)樣本所占的比重為pk，那么信息熵的計(jì)算則為下面的計(jì)算方式

當(dāng)這個(gè)Ent(D)的值越小，說(shuō)明樣本集合D的純度就越高

有了信息熵，當(dāng)我選擇用樣本的某一個(gè)屬性a來(lái)劃分樣本集合D時(shí)，就可以得出用屬性a對(duì)樣本D進(jìn)行劃分所帶來(lái)的“信息增益”

一般來(lái)講，信息增益越大，說(shuō)明如果用屬性a來(lái)劃分樣本集合D，那么純度會(huì)提升，因?yàn)槲覀兎謩e對(duì)樣本的所有屬性計(jì)算增益情況，選擇最大的來(lái)作為決策樹(shù)的一個(gè)結(jié)點(diǎn)，或者可以說(shuō)那些信息增益大的屬性往往離根結(jié)點(diǎn)越近，因?yàn)槲覀儠?huì)優(yōu)先用能區(qū)分度大的也就是信息增益大的屬性來(lái)進(jìn)行劃分。當(dāng)一個(gè)屬性已經(jīng)作為劃分的依據(jù)，在下面就不在參與競(jìng)選了，我們剛才說(shuō)過(guò)根結(jié)點(diǎn)代表全部樣本，而經(jīng)過(guò)根結(jié)點(diǎn)下面屬性各個(gè)取值后樣本又可以按照相應(yīng)屬性值進(jìn)行劃分，并且在當(dāng)前的樣本下利用剩下的屬性再次計(jì)算信息增益來(lái)進(jìn)一步選擇劃分的結(jié)點(diǎn)，ID3決策樹(shù)就是這樣建立起來(lái)的。

C4.5決策樹(shù)的提出完全是為了解決ID3決策樹(shù)的一個(gè)缺點(diǎn)，當(dāng)一個(gè)屬性的可取值數(shù)目較多時(shí)，那么可能在這個(gè)屬性對(duì)應(yīng)的可取值下的樣本只有一個(gè)或者是很少個(gè)，那么這個(gè)時(shí)候它的信息增益是非常高的，這個(gè)時(shí)候純度很高，ID3決策樹(shù)會(huì)認(rèn)為這個(gè)屬性很適合劃分，但是較多取值的屬性來(lái)進(jìn)行劃分帶來(lái)的問(wèn)題是它的泛化能力比較弱，不能夠?qū)π聵颖具M(jìn)行有效的預(yù)測(cè)。

而C4.5決策樹(shù)則不直接使用信息增益來(lái)作為劃分樣本的主要依據(jù)，而提出了另外一個(gè)概念，增益率

但是同樣的這個(gè)增益率對(duì)可取值數(shù)目較少的屬性有所偏好，因此C4.5決策樹(shù)先從候選劃分屬性中找出信息增益高于平均水平的屬性，在從中選擇增益率最高的。

CART決策樹(shù)的全稱(chēng)為Classification and Regression Tree,可以應(yīng)用于分類(lèi)和回歸。

采用基尼系數(shù)來(lái)劃分屬性

基尼值

基尼系數(shù)

因此在候選屬性中選擇基尼系數(shù)最小的屬性作為最優(yōu)劃分屬性。