1．背景知識：
? ?? ?決策樹是對數(shù)據(jù)進行分類，以此達到預測的目的。該決策樹方法先根據(jù)訓練集數(shù)據(jù)形成決策樹，如果該樹不能對所有對象給出正確的分類，那么選擇一些例外加入到
訓練集數(shù)據(jù)中，重復該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結(jié)構(gòu)。
? ?? ?決策樹由決策結(jié)點、分支和葉子組成。決策樹中最上面的結(jié)點為根結(jié)點，每個分支是一個新的決策結(jié)點，或者是樹的葉子。每個決策結(jié)點代表一個問題或決策，通常對應于待分類對象的屬性。每一個葉子結(jié)點代表一種可能的分類結(jié)果。沿決策樹從上到下遍歷的過程中，在每個結(jié)點都會遇到一個測試，對每個結(jié)點上問題的不同的測試輸出導致不同的分支，最后會到達一個葉子結(jié)點，這個過程就是利用決策樹進行分類的過程，利用若干個變量來判斷所屬的類別。
2．ID3算法：
? ? ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。以下是一些信息論的基本概念：
? ? 定義1：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為Log2(n)
? ? 定義2：若有n個消息，其給定概率分布為P=(p1,p2…pn)，則由該分布傳遞的信息量稱為P的熵，記為
? ? I(p)=-(i=1 to n求和)piLog2(pi)。
? ? 定義3：若一個記錄集合T根據(jù)類別屬性的值被分成互相獨立的類C1C2..Ck，則識別T的一個元素所屬哪個類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)
? ? 定義4：若我們先根據(jù)非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個元素類的信息量可通過確定Ti的加權(quán)平均值來得到，即Info(Ti)的加權(quán)平均值為：
? ? Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))
? ? 定義5：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量，信息增益度公式為：
? ? Gain(X, T)=Info(T)-Info(X, T)
? ? 為方便理解，在此舉例說明算法過程，具體算法其實很簡單，呵呵：
? ? 某市高中一年級（共六個班）學生上學期期末考試成績數(shù)據(jù)庫。其中學生考試成績屬性有 ：學籍號、語文、數(shù)學 、英語 、物理 、化學，如下表所示，本例子的目的是利用決策樹技術(shù)研究學生物理成績的及格與否可以由哪些屬性決定
學號? ? ? ? 語文? ? ? ? 數(shù)學? ? ? ? 英語? ? ? ? 物理? ? ? ? 化學
1? ? ? ? 76? ? ? ? 71? ? ? ? 68? ? ? ? 71? ? ? ? 81
2? ? ? ? 71? ? ? ? 65? ? ? ? 63? ? ? ? 72? ? ? ? 74
3? ? ? ? 60? ? ? ? 81? ? ? ? 67? ? ? ? 87? ? ? ? 80
4? ? ? ? 67? ? ? ? 84? ? ? ? 71? ? ? ? 61? ? ? ? 78
5? ? ? ? 64? ? ? ? 76? ? ? ? 72? ? ? ? 64? ? ? ? 72
6? ? ? ? 73? ? ? ? 80? ? ? ? 66? ? ? ? 58? ? ? ? 67
7? ? ? ? 62? ? ? ? 81? ? ? ? 78? ? ? ? 52? ? ? ? 79
8? ? ? ? 74? ? ? ? 78? ? ? ? 47? ? ? ? 60? ? ? ? 56
9? ? ? ? 62? ? ? ? 68? ? ? ? 63? ? ? ? 74? ? ? ? 67
10? ? ? ? 72? ? ? ? 73? ? ? ? 73? ? ? ? 49? ? ? ? 60
……? ? ? ? ……? ? ? ? ……? ? ? ? ……? ? ? ? ……? ? ? ? ……
第一步：對數(shù)據(jù)進行規(guī)范化處理。
將上表中的數(shù)據(jù)規(guī)范化，用0表示成績小于60分，1表示成績大于或等于60分，得到下表：
學號? ? ? ? 語文? ? ? ? 數(shù)學? ? ? ? 英語? ? ? ? 物理? ? ? ? 化學
1? ? ? ? 76? ? ? ? 71? ? ? ? 68? ? ? ? 71? ? ? ? 81
2? ? ? ? 71? ? ? ? 65? ? ? ? 63? ? ? ? 72? ? ? ? 74
3? ? ? ? 60? ? ? ? 81? ? ? ? 67? ? ? ? 87? ? ? ? 80
4? ? ? ? 67? ? ? ? 84? ? ? ? 71? ? ? ? 61? ? ? ? 78
5? ? ? ? 64? ? ? ? 76? ? ? ? 72? ? ? ? 64? ? ? ? 72
6? ? ? ? 73? ? ? ? 80? ? ? ? 66? ? ? ? 58? ? ? ? 67
7? ? ? ? 62? ? ? ? 81? ? ? ? 78? ? ? ? 52? ? ? ? 79
8? ? ? ? 74? ? ? ? 78? ? ? ? 47? ? ? ? 60? ? ? ? 56
9? ? ? ? 62? ? ? ? 68? ? ? ? 63? ? ? ? 74? ? ? ? 67
10? ? ? ? 72? ? ? ? 73? ? ? ? 73? ? ? ? 49? ? ? ? 60
……? ? ? ? ……? ? ? ? ……? ? ? ? ……? ? ? ? ……? ? ? ? ……
第二步：選取訓練實例集。
從所有學生中進行抽樣，將抽樣數(shù)據(jù)作為訓練集，共計有161條記錄。經(jīng)統(tǒng)計，在這161條記錄的訓練集中單科成績及格人數(shù)和不及格人數(shù)如下表所示：
? ? ? ? 語文? ? ? ? 數(shù)學? ? ? ? 英語? ? ? ? 物理? ? ? ? 化學
及格? ? ? ? 82? ? ? ? 57? ? ? ? 34? ? ? ? 32? ? ? ? 39
不及格? ? ? ? 79? ? ? ? 104? ? ? ? 127? ? ? ? 129? ? ? ? 122
第三步：利用信息增益度選取最能區(qū)別訓練集中實例的屬性。
首先計算課程物理所含有的信息量。由表4可知物理及格人數(shù)P=32，不及格人數(shù)N=129，則可得到：
Info(T)=I(32, 129)=-[(32/161)Log2(32/161)+(129/161)Log2(129/161)]=0.7195
然后計算當課程物理及格和不及格時，課程語文所包含的總信息量。經(jīng)統(tǒng)計，語文和物理有如下表所示的統(tǒng)計數(shù)據(jù)：
成績搭配? ? ? ? 人數(shù)
語文成績=1且物理成績=1? ? ? ? 28
語文成績=1且物理成績=0? ? ? ? 54
語文成績=0且物理成績=1? ? ? ? 4
語文成績=0且物理成績=0? ? ? ? 75
可得到：
Info(X,T) = )=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))=(82/161)I(28,54)+(79/161)I(4,75)=0.6136
最后可得到語文的信息增益度為：
Gain(X,T)=Info(T)-Info(X,T)=0.7195-0.6136=0.1059
同理可得其他課程的信息增益度，結(jié)果如下表所示：
? ? ? ? 數(shù)學? ? ? ? 英語? ? ? ? 化學
Gain? ? ? ? 0.2136? ? ? ? 0.095? ? ? ? 0.1701
由此可以看出所有課程當中數(shù)學是最能區(qū)別訓練集中決定物理成績與否的課程
第四步：創(chuàng)建一個樹結(jié)點，并創(chuàng)建該結(jié)點的子鏈，每個子鏈代表所選屬性的一個唯一值。使用子鏈的值進一步細化子類。當出現(xiàn)以下兩種情形之一時可以停止分類：1.一個結(jié)點上的數(shù)據(jù)都是屬于同一類別；2.沒有屬性可以再對屬性進行分割。
根據(jù)各個課程的信息增益度，應該選擇數(shù)學作為所建決策樹的根結(jié)點。由于數(shù)學的屬性值只有兩個：1（及格）和0（不及格），所以在數(shù)學下可以建立兩個分支。經(jīng)統(tǒng)計，數(shù)學不及格且物理不及格的人數(shù)為100，其準確率為100/104=96.2%。因此對數(shù)學不及格這個分之停止分割。又經(jīng)統(tǒng)計，數(shù)學及格的57人中有26人物理及格，31人物理不及格，所以應對數(shù)學及格這個分支進行分割。從上表可知，應該選取化學作為分割結(jié)點進行細化。分割后經(jīng)統(tǒng)計顯示，數(shù)學和化學都及格的學生中，有26人物理及格，6人物理不及格，準確率為 26/32=81.3%；數(shù)學及格但化學不及格的學生中，有22人物理不及格，3人物理及格，準確率為 22/25=88%。由此可構(gòu)建出數(shù)據(jù)的決策樹，如下所示
? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???數(shù)學
? ?? ?? ?? ?? ?? ?? ?? ? （及格）? ?? ?? ?? ?? ? （不及格）
? ?? ?? ?? ?? ?? ?? ?化學? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???物理不及格（104/4）
? ?? ???（及格）? ? （不及格）
物理及格（32/6）? ?? ? 物理不及格（25/3）
注：括號內(nèi)為分支條件（不知道怎么上傳圖片，實際是一棵樹，呵呵）
第五步：將其它成績作為檢驗集 。并用來檢驗所生成的決策樹的準確度。
由該決策樹可以得出下列規(guī)則：
(1)IF學生的數(shù)學成績不及格
THEN其物理成績通常也不及格。
準確度=(104-4)/104=96.2％
覆蓋率=104/161=64.6％
(2)IF學生的數(shù)學及格且化學成績不及格 ，
THEN物理成績不及格。
準確度=(32-6)/32=81.3％
覆蓋率=32/161=20％
(3)IF學生的數(shù)學成績及格且化學成績及格
THEN其物理成績及格
準確度=(25-3)/25=88％
覆蓋率=25/161=16％
我們也可這樣描述：學生數(shù)學的學習程度將直接影響著其對物理的學習效果。化學的學習對物理的學習也有一定的影響。因此高中教師在進行物理教學時。應考慮學生的數(shù)學基礎。數(shù)學程度較好而物理程度一般的學生應更重視化學的學習
注：例子摘自《決策樹技術(shù)在學生考試成績數(shù)據(jù)庫應用》一文
凡是有該標志的文章，都是該blog博主Caoer（草兒）原創(chuàng)，凡是索引、收藏
、轉(zhuǎn)載請注明來處和原文作者。非常感謝。