決策樹之ID3算法及其Python實(shí)現(xiàn)

1. 決策樹背景知識
??決策樹是數(shù)據(jù)挖掘中最重要且最常用的方法之一，主要應(yīng)用于數(shù)據(jù)挖掘中的分類和預(yù)測。決策樹是知識的一種呈現(xiàn)方式，決策樹中從頂點(diǎn)到每個結(jié)點(diǎn)的路徑都是一條分類規(guī)則。決策樹算法最先基于信息論發(fā)展起來，經(jīng)過幾十年發(fā)展，目前常用的算法有：ID3、C4.5、CART算法等。

2. 決策樹一般構(gòu)建過程
??構(gòu)建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數(shù)據(jù)進(jìn)行切分細(xì)分的過程，每一次切分都會產(chǎn)生一個數(shù)據(jù)子集對應(yīng)的節(jié)點(diǎn)。從包含所有數(shù)據(jù)的根節(jié)點(diǎn)開始，根據(jù)選取分裂屬性的屬性值把訓(xùn)練集劃分成不同的數(shù)據(jù)子集，生成由每個訓(xùn)練數(shù)據(jù)子集對應(yīng)新的非葉子節(jié)點(diǎn)。對生成的非葉子節(jié)點(diǎn)再重復(fù)以上過程，直到滿足特定的終止條件，停止對數(shù)據(jù)子集劃分，生成數(shù)據(jù)子集對應(yīng)的葉子節(jié)點(diǎn)，即所需類別。測試集在決策樹構(gòu)建完成后檢驗(yàn)其性能。如果性能不達(dá)標(biāo)，我們需要對決策樹算法進(jìn)行改善，直到達(dá)到預(yù)期的性能指標(biāo)。
??注：分裂屬性的選取是決策樹生產(chǎn)過程中的關(guān)鍵，它決定了生成的決策樹的性能、結(jié)構(gòu)。分裂屬性選擇的評判標(biāo)準(zhǔn)是決策樹算法之間的根本區(qū)別。

3. ID3算法分裂屬性的選擇——信息增益
??屬性的選擇是決策樹算法中的核心。是對決策樹的結(jié)構(gòu)、性能起到?jīng)Q定性的作用。ID3算法基于信息增益的分裂屬性選擇。基于信息增益的屬性選擇是指以信息熵的下降速度作為選擇屬性的方法。它以的信息論為基礎(chǔ)，選擇具有最高信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的分裂屬性。選擇該屬性作為分裂屬性后，使得分裂后的樣本的信息量最大，不確定性最小，即熵最小。
??信息增益的定義為變化前后熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。
??信息：分類標(biāo)簽xi 在樣本集 S 中出現(xiàn)的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。
??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標(biāo)簽的個數(shù)。
??通過屬性A分裂之后樣本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集，|Sj| 表示第j個子樣本集中樣本數(shù)量，|S| 表示分裂之前數(shù)據(jù)集中樣本總數(shù)量。
??通過屬性A分裂之后樣本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??注：分裂屬性的選擇標(biāo)準(zhǔn)為：分裂前后信息增益越大越好，即分裂后的熵越小越好。

4. ID3算法
??ID3算法是一種基于信息增益屬性選擇的決策樹學(xué)習(xí)方法。核心思想是：通過計算屬性的信息增益來選擇決策樹各級節(jié)點(diǎn)上的分裂屬性，使得在每一個非葉子節(jié)點(diǎn)進(jìn)行測試時，獲得關(guān)于被測試樣本最大的類別信息。基本方法是：計算所有的屬性，選擇信息增益最大的屬性分裂產(chǎn)生決策樹節(jié)點(diǎn)，基于該屬性的不同屬性值建立各分支，再對各分支的子集遞歸調(diào)用該方法建立子節(jié)點(diǎn)的分支，直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹，可用來對新樣本數(shù)據(jù)進(jìn)行分類。

ID3算法流程：
(1) 創(chuàng)建一個初始節(jié)點(diǎn)。如果該節(jié)點(diǎn)中的樣本都在同一類別，則算法終止，把該節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)，并用該類別標(biāo)記。
(2) 否則，依據(jù)算法選取信息增益最大的屬性，該屬性作為該節(jié)點(diǎn)的分裂屬性。
(3) 對該分裂屬性中的每一個值，延伸相應(yīng)的一個分支，并依據(jù)屬性值劃分樣本。
(4) 使用同樣的過程，自頂向下的遞歸，直到滿足下面三個條件中的一個時就停止遞歸。
??A、待分裂節(jié)點(diǎn)的所有樣本同屬于一類。
??B、訓(xùn)練樣本集中所有樣本均完成分類。
??C、所有屬性均被作為分裂屬性執(zhí)行一次。若此時，葉子結(jié)點(diǎn)中仍有屬于不同類別的樣本時，選取葉子結(jié)點(diǎn)中包含樣本最多的類別，作為該葉子結(jié)點(diǎn)的分類。

ID3算法優(yōu)缺點(diǎn)分析
優(yōu)點(diǎn)：構(gòu)建決策樹的速度比較快，算法實(shí)現(xiàn)簡單，生成的規(guī)則容易理解。
缺點(diǎn)：在屬性選擇時，傾向于選擇那些擁有多個屬性值的屬性作為分裂屬性，而這些屬性不一定是最佳分裂屬性；不能處理屬性值連續(xù)的屬性；無修剪過程，無法對決策樹進(jìn)行優(yōu)化，生成的決策樹可能存在過度擬合的情況。