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

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

一：ID3算法

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

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

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

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

直到所有特征的信息增益均很小或者沒有特征可選擇的時(shí)候?yàn)橹埂?/p>

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

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

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

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

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

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

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

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

7，對(duì)于所有的子節(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)中的分支屬性時(shí)，采用信息增益作為評(píng)價(jià)標(biāo)準(zhǔn)。信息增益的缺點(diǎn)是傾向于選擇取值較多是屬性，在有些情況下這類屬性可能不會(huì)提供太多有價(jià)值的信息。

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

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

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

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