程式師世界 >> 數據庫知識 >> SqlServer數據庫 >> 關於SqlServer >> 經典ID3算法

經典ID3算法

編輯：關於SqlServer

1．背景知識：
       決策樹是對數據進行分類，以此達到預測的目的。該決策樹方法先根據訓練集數據形成決策樹，如果該樹不能對所有對象給出正確的分類，那麼選擇一些例外加入到訓練集數據中，重復該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結構。
       決策樹由決策結點、分支和葉子組成。決策樹中最上面的結點為根結點，每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或決策，通常對應於待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。沿決策樹從上到下遍歷的過程中，在每個結點都會遇到一個測試，對每個結點上問題的不同的測試輸出導致不同的分支，最後會到達一個葉子結點，這個過程就是利用決策樹進行分類的過程，利用若干個變量來判斷所屬的類別。
2．ID3算法：
    ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎，以信息熵和信息增益度為衡量標准，從而實現對數據的歸納分類。以下是一些信息論的基本概念：
     定義1：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為Log2(n)e$NM mLX&C(H
定義2：若有n個消息，其給定概率分布為P=(p1,p2…pn)，則由該分布傳遞的信息量稱為P的熵，記為Bc+y^1Vt
I(p)=-(i=1 to n求和)piLog2(pi)。
     定義3：若一個記錄集合T根據類別屬性的值被分成互相獨立的類C1C2..Ck，則識別T的一個元素所屬哪個類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)-l0a%i+^%~;f.K
定義4：若我們先根據非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個元素類的信息量可通過確定Ti的加權平均值來得到，即Info(Ti)的加權平均值為：_6xW,FL#?7z
Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti)) ^E _OOt Y
定義5：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值後需確定的T一個元素的信息量，信息增益度公式為：7K:{S;wy'Hnwp7Lz1I
Gain(X, T)=Info(T)-Info(X, T)
     為方便理解，在此舉例說明算法過程，具體算法其實很簡單，呵呵： xc2G }gg
某市高中一年級（共六個班）學生上學期期末考試成績數據庫。其中學生考試成績屬性有：學籍號、語文、數學、英語、物理、化學，如下表所示，本例子的目的是利用決策樹技術研究學生物理成績的及格與否可以由哪些屬性決定
學號語文數學英語物理化學
1 76 71 68 71 81.k5?

sx"J{)v1m%m
2 71 65 63 72 741I!c"V)zA
3 60 81 67 87 80
4 67 84 71 61 78
5 64 76 72 64 72
6 73 80 66 58 67(sV2ptI7H)Z
7 62 81 78 52 79
8 74 78 47 60 56@2Vm w3bw
9 62 68 63 74 67)v(i{?X7n f
10 72 73 73 49 60
…… …… …… …… …… ……

第一步：對數據進行規范化處理。7A/YLl:[
將上表中的數據規范化，用0表示成績小於60分，1表示成績大於或等於60分，得到下表：c5X1OX"A'sw6u
學號語文數學英語物理

化學
1 76 71 68 71 81
2 71 65 63 72 74s7GT0`;O&of:R
3 60 81 67 87 80
4 67 84 71 61 78x u0Xn9PDe2h
5 64 76 72 64 72
6 73 80 66   58 67
7 62 81 78 52 79%IxsW#m:IQp!m"z
8 74 78 47 60 56
9 62 68 63 74 67
10 72 73 73 49 60^6vr Jk if&h#gw
…… …… …… …… …… ……
第二步：選取訓練實例集。
從所有學生中進行抽樣，將抽樣數據作為訓練集，共計有161條記錄。經統計，在這161條記錄的訓練集中單科成績及格人數和不及格人數如下表所示：J.gqkl9{ly*i_,

P^B
語文數學英語物理化學

及格 82 57 34 32 39!n s*zM!T{CW

不及格 79 104 127    129 1223NS$B%M1Az iij
第三步：利用信息增益度選取最能區別訓練集中實例的屬性。W(\!H"`{O
首先計算課程物理所含有的信息量。由表4可知物理及格人數P=32，不及格人數N=129，則可得到：
Info(T)=I(32, 129)=-[(32/161)Log2(32/161)+(129/161)Log2(129/161)]=0.7195
然後計算當課程物理及格和不及格時，課程語文所包含的總信息量。經統計，語文和物理有如下表所示的統計數據：
)B6Eos7B/mC#U
成績搭配人數FV1Y)c'~ m&T G
語文成績=1且物理成績=1 28
語文成績=1且物理成績=0 54
語文成績=0且物理成績=1 4]:j8z(K/D1t5]
語文成績=0且物理成績=0 75.`5kO$xm.w Q?
可得到：
Info(X,T) = )=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))=(82/161)I(28,54)+(79/161)I(4,75)=0.6136
最後可得到語文的信息增益度為： V Zy;XK\&_B @
Gain(X,T)=Info(T)-Info(X,T)=0.7195-0.6136=0.1059
同理可得其他課程的信息增益度，結果如下表所示：C_*D{8L_0m(g

                         數學英語化學
G Gain 0.2136 0.095  0.1701/Wc4|nR
#~A+oA;P
由此可以看出所有課程當中數學是最能區別訓練集中決定物理成績與否的課程P ]fQO#\
第四步：創建一個樹結點，並創建該結點的子鏈，每個子鏈代表所選屬性的一個唯一值。使用子鏈的值進一步細化子類。當出現以下兩種情形之一時可以停止分類：1.一個結點上的數據都是屬於同一類別；2.沒有屬性可以再對屬性進行分割。
根據各個課程的信息增益度，應該選擇數學作為所建決策樹的根結點。由於數學的屬性值只有兩個：1（及格）和0（不及格），所以在數學下可以建立兩個分支。經統計，數學不及格且物理不及格的人數為100，其准確率為100/104=96.2%。因此對數學不及格這個分之停止分割。又經統計，數學及格的57人中有26人物理及格，31人物理不及格，所以應對數學及格這個分支進行分割。從上表可知，應該選取化學作為分割結點進行細化。分割後經統計顯示，數學和化學都及格的學生中，有26人物理及格，6人物理不及格，准確率為 26/32=81.3%；數學及格但化學不及格的學生中，有22人物理不及格，3人物理及格，准確率為 22/25=88%。由此可構建出數據的決策樹，如下所示

                                            數學
                         （及格）             （不及格）
                      化學                               物理不及格（104/4） k9I:c)L`;J
      （及格）（不及格）)J#Eo$r9tqs K;D
物理及格（32/6）    物理不及格（25/3）
h S
注：括號內為分支條件（不知道怎麼上傳圖片，實際是一棵樹，呵呵）

第五步：將其它成績作為檢驗集。並用來檢驗所生成的決策樹的准確度。
由該決策樹可以得出下列規則：u2LK^8L
(1)IF學生的數學成績不及格 n;D2~QXZn
THEN其物理成績通常也不及格。
准確度=(104-4)/104=96.2％
覆蓋率=104/161=64.6％
(2)IF學生的數學及格且化學成績不及格， ^Pq;m%oZ
THEN物理成績不及格。

9O#{$JB ZH"m4e){;e;I
准確度=(32-6)/32=81.3％ %^*i:`}eRQ
覆蓋率=32/161=20％ (PR+\!Y"]]+D
(3)IF學生的數學成績及格且化學成績及格
THEN其物理成績及格 @J$|Tobm
准確度=(25-3)/25=88％ 3yj#[u9\?%Pj
覆蓋率=25/161=16％
我們也可這樣描述：學生數學的學習程度將直接影響著其對物理的學習效果。化學的學習對物理的學習也有一定的影響。因此高中教師在進行物理教學時。應考慮學生的數學基礎。數學程度較好而物理程度一般的學生應更重視化學的學習N N8f4t!~n