標籤: 暫無標籤

ID3演算法是以資訊理論為基礎,以信息熵和信息增益度為衡量標準,從而實現對數據的歸納分類,由Quinlan首先提出的。

1 ID3演算法 -ID3演算法

  1、背景知識:

決策樹是對數據進行分類,以此達到預測的目的。該決策樹方法先根據訓練集數據形成決策樹,如果該樹不能對所有對象給出正確的分類,那麼選擇一些例外加入到訓練集數據中,重複該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結構。   

ID3演算法使用ID3演算法構造決策樹

決策樹由決策結點、分支和葉子組成。決策樹中最上面的結點為根結點,每個分支是一個新的決策結點,或者是樹的葉子。每個決策結點代表一個問題或決策,通常對應於待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。沿決策樹從上到下遍歷的過程中,在每個結點都會遇到一個測試,對每個結點上問題的不同的測試輸出導致不同的分支,最後會到達一個葉子結點,這個過程就是利用決策樹進行分類的過程,利用若干個變數來判斷所屬的類別。   

2.ID3演算法:

資訊理論的基本概念:

定義1:若存在n個相同概率的消息,則每個消息的概率p是1/n,一個消息傳遞的信息量為Log2(n)   

定義2:若有n個消息,其給定概率分佈為P=(p1,p2…pn),則由該分佈傳遞的信息量稱為P的熵,記為   

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|)   

定義4:若我們先根據非類別屬性X的值將T分成集合T1,T2…Tn,則確定T中一個元素類的信息量可通過確定Ti的加權平均值來得到,即Info(Ti)的加權平均值為:

Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))   

定義5:信息增益度是兩個信息量之間的差值,其中一個信息量是需確定T的一個元素的信息量,另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量,信息增益度公式為:

Gain(X, T)=Info(T)-Info(X, T)  

為方便理解,在此舉例說明演算法過程,具體演算法其實很簡單: 
某市高中一年級(共六個班)學生上學期期末考試成績資料庫。其中學生考試成績屬性有 :學籍號、語文、數學 、英語 、物理 、化學,如下表所示,本例子的目的是利用決策樹技術研究學生物理成績的及格與否可以由哪些屬性決定:
學號   語文   數學     英語    物理     化學
 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 
第一步:對數據進行規範化處理。
將上表中的數據規範化,用0表示成績小於60分,1表示成績大於或等於60分,得到下表:
學號   語文    數學  英語    物理     化學
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

第二步:選取訓練實例集。
從所有學生中進行抽樣,將抽樣數據作為訓練集,共計有161條記錄。經統計,在這161條記錄的訓練集中單科成績及格人數和不及格人數如下表所示: 
               語文        數學        英語        物理        化學

及格           82           57           34           32           39

不及格        79         104          127         129         122
第三步:利用信息增益度選取最能區別訓練集中實例的屬性。
首先計算課程物理所含有的信息量。由表4可知物理及格人數P=32,不及格人數N=129,則可得到:
 Info(T)=I(32, 129)=-[(32/161)Log2(32/161)+(129/161)Log2(129/161)]=0.7195
然後計算當課程物理及格和不及格時,課程語文所包含的總信息量。經統計,語文和物理有如下表所示的統計數據: 
成績搭配                                人數
語文成績=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
同理可得其他課程的信息增益度,結果如下表所示: 

                 數學        英語        化學 
 Gain        0.2136       0.095       0.1701 
由此可以看出所有課程當中數學是最能區別訓練集中決定物理成績與否的課程\
第四步:創建一個樹結點,並創建該結點的子鏈,每個子鏈代表所選屬性的一個唯一值。使用子鏈的值進一步細化子類。當出現以下兩種情形之一時可以停止分類:1.一個結點上的數據都是屬於同一類別;2.沒有屬性可以再對屬性進行分割。
根據各個課程的信息增益度,應該選擇數學作為所建決策樹的根結點。由於數學的屬性值只有兩個:1(及格)和0(不及格),所以在數學下可以建立兩個分支。經統計,數學不及格且物理不及格的人數為100,其準確率為100/104=96.2%。因此對數學不及格這個分之停止分割。又經統計,數學及格的57人中有26人物理及格,31人物理不及格,所以應對數學及格這個分支進行分割。從上表可知,應該選取化學作為分割結點進行細化。分割后經統計顯示,數學和化學都及格的學生中,有26人物理及格,6人物理不及格,準確率為 26/32=81.3%;數學及格但化學不及格的學生中,有22人物理不及格,3人物理及格,準確率為 22/25=88%。
第五步:將其它成績作為檢驗集 。並用來檢驗所生成的決策樹的準確度。
由該決策樹可以得出下列規則:
(1)IF

學生的數學成績不及格
THEN

其物理成績通常也不及格。 
準確度=(104-4)/104=96.2% 
覆蓋率=104/161=64.6% 
(2)IF

學生的數學及格且化學成績不及格
THEN

物理成績不及格。
準確度=(32-6)/32=81.3%
覆蓋率=32/161=20% 
(3)IF

學生的數學成績及格且化學成績及格 
THEN其物理成績及格
準確度=(25-3)/25=88% 
覆蓋率=25/161=16% 
我們也可這樣描述:學生數學的學習程度將直接影響著其對物理的學習效果。化學的學習對物理的學習也有一定的影響。因此高中教師在進行物理教學時。應考慮學生的數學基礎。數學程度較好而物理程度一般的學生應更重視化學的學習。
ID3演算法計算每個屬性的信息增益,並選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創建一個節點,並以該節點的屬性標記,對該屬性的每個值創建一個分支據此劃分樣本.

上一篇[手錶遊絲]    下一篇 [卡里巴水電站]

相關評論

同義詞:暫無同義詞