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

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

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

3. ID3算法分裂屬性的選擇——信息增益
??屬性的選擇是決策樹算法中的核心。是對決策樹的結(jié)構(gòu)、性能起到?jīng)Q定性的作用。ID3算法基于信息增益的分裂屬性選擇?；谛畔⒃鲆娴膶傩赃x擇是指以信息熵的下降速度作為選擇屬性的方法。它以的信息論為基礎(chǔ)，選擇具有最高信息增益的屬性作為當前節(jié)點的分裂屬性。選擇該屬性作為分裂屬性后，使得分裂后的樣本的信息量最大，不確定性最小，即熵最小。
??信息增益的定義為變化前后熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。
??信息：分類標簽xi 在樣本集 S 中出現(xiàn)的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。
??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標簽的個數(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)
??注：分裂屬性的選擇標準為：分裂前后信息增益越大越好，即分裂后的熵越小越好。

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

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

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