Python 決策樹的生成算法介紹

劃分?jǐn)?shù)據(jù)集的最大原則是：使無序的數(shù)據(jù)變的有序。如果一個訓(xùn)練數(shù)據(jù)中有20個特征，那么選取哪個做劃分依據(jù)?這就必須采用量化的方法來判斷，量化劃分方法有多重，其中一項就是“信息論度量信息分類”?；谛畔⒄摰臎Q策樹算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來。

決策樹的生成算法由很多變形，這里簡單說一下幾種經(jīng)典的實現(xiàn)算法：ID3算法，C4.5算法和CART算法。這些算法的主要區(qū)別在于分類結(jié)點(diǎn)熵特征選擇的選取標(biāo)準(zhǔn)不同，下面了解一下算法的具體實現(xiàn)過程。

一：ID3算法

ID3算法所采用的度量標(biāo)準(zhǔn)就是我們前面提到的“信息增益”。當(dāng)屬性a的信息增益最大時，則意味著用a屬性劃分，其所獲得的“純度”提升最大，我們所要做的，就是找到信息增益最大的屬性。

ID3算法的核心是在決策樹的各個節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則進(jìn)行特征選擇，具體的做法是：

從根節(jié)點(diǎn)上開始，對結(jié)點(diǎn)計算所有可能特征的信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，并由該特征的不同取值構(gòu)建子節(jié)點(diǎn);

對于子節(jié)點(diǎn)遞歸的調(diào)用以上方法，構(gòu)建決策樹;

直到所有特征的信息增益均很小或者沒有特征可選擇的時候為止。

ID3算法具體的算法過程如下：

輸入的是m個樣本，樣本輸出集合為D，每個樣本有n個離散特征，特征集合為A，輸出為決策樹T。

1，初始化信息增益的閾值€

2，判斷樣本是否為同一類輸出Di，如果是則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為Di

3，判斷特征是否為空，如果是則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本值紅輸出類別D實例數(shù)最多的類別

4，計算A中的各個特征(一共n個)對輸出D的信息增益，選擇信息增益最大的特征Ag

5，如果Ag的信息增益小于閾值€，則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本中輸出類別D實例樹最多的類別

6，否則，按特征Ag的不同取值A(chǔ)gi將對應(yīng)的樣本輸出D分成不同的類別Di，每個類別產(chǎn)生一個子節(jié)點(diǎn)。對應(yīng)特征為Agi，返回增加了節(jié)點(diǎn)的數(shù)T

7，對于所有的子節(jié)點(diǎn)，令D=Di，A=A-{Ag}遞歸調(diào)用2~6步，得到子樹Ti并返回

ID3算法存在的缺點(diǎn)：

1.ID3算法在選擇根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中的分支屬性時，采用信息增益作為評價標(biāo)準(zhǔn)。信息增益的缺點(diǎn)是傾向于選擇取值較多是屬性，在有些情況下這類屬性可能不會提供太多有價值的信息。

2.ID3算法只能對描述屬性為離散型屬性的數(shù)據(jù)集構(gòu)造決策樹。

3.ID3算法對于缺失值的情況沒做考慮。

4.沒有考慮過擬合的問題。

以上內(nèi)容為大家介紹了Python決策樹的生成算法介紹，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。