1．背景知識(shí)：
      決策樹是對(duì)數(shù)據(jù)進(jìn)行分類，以此達(dá)到預(yù)測(cè)的目的。該決策樹方法先根據(jù)訓(xùn)練集數(shù)據(jù)形成決策樹，如果該樹不能對(duì)所有對(duì)象給出正確的分類，那么選擇一些例外加入到訓(xùn)練集數(shù)據(jù)中，重復(fù)該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結(jié)構(gòu)。
      決策樹由決策結(jié)點(diǎn)、分支和葉子組成。決策樹中最上面的結(jié)點(diǎn)為根結(jié)點(diǎn)，每個(gè)分支是一個(gè)新的決策結(jié)點(diǎn)，或者是樹的葉子。每個(gè)決策結(jié)點(diǎn)代表一個(gè)問題或決策，通 常對(duì)應(yīng)于待分類對(duì)象的屬性。每一個(gè)葉子結(jié)點(diǎn)代表一種可能的分類結(jié)果。沿決策樹從上到下遍歷的過程中，在每個(gè)結(jié)點(diǎn)都會(huì)遇到一個(gè)測(cè)試，對(duì)每個(gè)結(jié)點(diǎn)上問題的不同 的測(cè)試輸出導(dǎo)致不同的分支，最后會(huì)到達(dá)一個(gè)葉子結(jié)點(diǎn)，這個(gè)過程就是利用決策樹進(jìn)行分類的過程，利用若干個(gè)變量來判斷所屬的類別。
2．ID3算法：
    ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的歸納分類。以下是一些信息論的基本概念：
    定義1：若存在n個(gè)相同概率的消息，則每個(gè)消息的概率p是1/n，一個(gè)消息傳遞的信息量為L(zhǎng)og2(n)
    定義2：若有n個(gè)消息，其給定概率分布為P=(p1,p2…pn)，則由該分布傳遞的信息量稱為P的熵，記為
    I(p)=-(i=1 to n求和)piLog2(pi)。
    定義3：若一個(gè)記錄集合T根據(jù)類別屬性的值被分成互相獨(dú)立的類C1C2..Ck，則識(shí)別T的一個(gè)元素所屬哪個(gè)類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)
    定義4：若我們先根據(jù)非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個(gè)元素類的信息量可通過確定Ti的加權(quán)平均值來得到，即Info(Ti)的加權(quán)平均值為：
    Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))
    定義5：信息增益度是兩個(gè)信息量之間的差值，其中一個(gè)信息量是需確定T的一個(gè)元素的信息量，另一個(gè)信息量是在已得到的屬性X的值后需確定的T一個(gè)元素的信息量，信息增益度公式為：
    Gain(X, T)=Info(T)-Info(X, T)
    為方便理解，在此舉例說明算法過程，具體算法其實(shí)很簡(jiǎn)單，呵呵：
    某市高中一年級(jí)（共六個(gè)班）學(xué)生上學(xué)期期末考試成績(jī)數(shù)據(jù)庫(kù)。其中學(xué)生考試成績(jī)屬性有 ：學(xué)籍號(hào)、語文、數(shù)學(xué) 、英語 、物理 、化學(xué)，如下表所示，本例子的目的是利用決策樹技術(shù)研究學(xué)生物理成績(jī)的及格與否可以由哪些屬性決定
學(xué)號(hào)        語文        數(shù)學(xué)        英語        物理        化學(xué)
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
……        ……        ……        ……        ……        ……
第一步：對(duì)數(shù)據(jù)進(jìn)行規(guī)范化處理。
將上表中的數(shù)據(jù)規(guī)范化，用0表示成績(jī)小于60分，1表示成績(jī)大于或等于60分，得到下表：
學(xué)號(hào)        語文        數(shù)學(xué)        英語        物理        化學(xué)
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
……        ……        ……        ……        ……        ……
第二步：選取訓(xùn)練實(shí)例集。
從所有學(xué)生中進(jìn)行抽樣，將抽樣數(shù)據(jù)作為訓(xùn)練集，共計(jì)有161條記錄。經(jīng)統(tǒng)計(jì)，在這161條記錄的訓(xùn)練集中單科成績(jī)及格人數(shù)和不及格人數(shù)如下表所示：
        語文        數(shù)學(xué)        英語        物理        化學(xué)
及格        82        57        34        32        39
不及格        79        104        127        129        122
第三步：利用信息增益度選取最能區(qū)別訓(xùn)練集中實(shí)例的屬性。
首先計(jì)算課程物理所含有的信息量。由表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ì)算當(dāng)課程物理及格和不及格時(shí)，課程語文所包含的總信息量。經(jīng)統(tǒng)計(jì)，語文和物理有如下表所示的統(tǒng)計(jì)數(shù)據(jù)：

成績(jī)搭配        人數(shù)
語文成績(jī)=1且物理成績(jī)=1        28
語文成績(jī)=1且物理成績(jī)=0        54
語文成績(jī)=0且物理成績(jī)=1        4
語文成績(jī)=0且物理成績(jī)=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ù)學(xué)        英語        化學(xué)
Gain        0.2136        0.095        0.1701

由此可以看出所有課程當(dāng)中數(shù)學(xué)是最能區(qū)別訓(xùn)練集中決定物理成績(jī)與否的課程
第四步：創(chuàng)建一個(gè)樹結(jié)點(diǎn)，并創(chuàng)建該結(jié)點(diǎn)的子鏈，每個(gè)子鏈代表所選屬性的一個(gè)唯一值。使用子鏈的值進(jìn)一步細(xì)化子類。當(dāng)出現(xiàn)以下兩種情形之一時(shí)可以停止分類：1.一個(gè)結(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一類別；2.沒有屬性可以再對(duì)屬性進(jìn)行分割。
根 據(jù)各個(gè)課程的信息增益度，應(yīng)該選擇數(shù)學(xué)作為所建決策樹的根結(jié)點(diǎn)。由于數(shù)學(xué)的屬性值只有兩個(gè)：1（及格）和0（不及格），所以在數(shù)學(xué)下可以建立兩個(gè)分支。經(jīng) 統(tǒng)計(jì)，數(shù)學(xué)不及格且物理不及格的人數(shù)為100，其準(zhǔn)確率為100/104=96.2%。因此對(duì)數(shù)學(xué)不及格這個(gè)分之停止分割。又經(jīng)統(tǒng)計(jì)，數(shù)學(xué)及格的57人中 有26人物理及格，31人物理不及格，所以應(yīng)對(duì)數(shù)學(xué)及格這個(gè)分支進(jìn)行分割。從上表可知，應(yīng)該選取化學(xué)作為分割結(jié)點(diǎn)進(jìn)行細(xì)化。分割后經(jīng)統(tǒng)計(jì)顯示，數(shù)學(xué)和化學(xué) 都及格的學(xué)生中，有26人物理及格，6人物理不及格，準(zhǔn)確率為 26/32=81.3%；數(shù)學(xué)及格但化學(xué)不及格的學(xué)生中，有22人物理不及格，3人物理及格，準(zhǔn)確率為 22/25=88%。由此可構(gòu)建出數(shù)據(jù)的決策樹，如下所示

                                            數(shù)學(xué)
                         （及格）                （不及格）
                     化學(xué)                                物理不及格（104/4）
        （及格）    （不及格）
物理及格（32/6）       物理不及格（25/3）

注：括號(hào)內(nèi)為分支條件（不知道怎么上傳圖片，實(shí)際是一棵樹，呵呵）

第五步：將其它成績(jī)作為檢驗(yàn)集 。并用來檢驗(yàn)所生成的決策樹的準(zhǔn)確度。
由該決策樹可以得出下列規(guī)則：
(1)IF學(xué)生的數(shù)學(xué)成績(jī)不及格
THEN其物理成績(jī)通常也不及格。
準(zhǔn)確度=(104-4)/104=96.2％
覆蓋率=104/161=64.6％
(2)IF學(xué)生的數(shù)學(xué)及格且化學(xué)成績(jī)不及格 ，
THEN物理成績(jī)不及格。
準(zhǔn)確度=(32-6)/32=81.3％
覆蓋率=32/161=20％
(3)IF學(xué)生的數(shù)學(xué)成績(jī)及格且化學(xué)成績(jī)及格
THEN其物理成績(jī)及格
準(zhǔn)確度=(25-3)/25=88％
覆蓋率=25/161=16％
我們也可這樣描述：學(xué)生數(shù)學(xué)的學(xué)習(xí)程度將直接影響著其對(duì)物理的學(xué)習(xí)效果?；瘜W(xué)的學(xué)習(xí)對(duì)物理的學(xué)習(xí)也有一定的影響。因此高中教師在進(jìn)行物理教學(xué)時(shí)。應(yīng)考慮學(xué)生的數(shù)學(xué)基礎(chǔ)。數(shù)學(xué)程度較好而物理程度一般的學(xué)生應(yīng)更重視化學(xué)的學(xué)習(xí)


注：例子摘自《決策樹技術(shù)在學(xué)生考試成績(jī)數(shù)據(jù)庫(kù)應(yīng)用》一文