ID3算法java實作
1 ID3算法概述
1.1 資訊熵
熵是無序性(或不确定性)的度量名額。假如事件A的全機率劃分是(A1,A2,...,An)，每部分發生的機率是(p1,p2,...,pn)，那資訊熵定義為：
通常以2為底數。是以資訊熵的機關是bit。
1.2 決策樹
決策樹是以執行個體為基礎的歸納學習算法。它從一組無次序、無規則的元組中推理出決策樹表示形式的分類規則。
它採用自頂向下的遞歸方式，在決策樹的内部結點進行屬性值的比較。并依據不同的屬性值從該結點向下分支。葉結點是要學習劃分的類。從根到葉結點的一條路徑就相應着一條合取規則，整個決策樹就相應着一組析取表達式規則。
1.3 ID3算法
ID3算法的核心是：在決策樹各級結點上選擇屬性時，用資訊增益(information gain)作為屬性的選擇标準。以使得在每個非葉結點進行測試時，能獲得關于被測試記錄最大的類别資訊。
其詳細方法是：檢測全部的屬性，選擇資訊增益最大的屬性産生決策樹結點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調用該方法建立決策樹結點的分支，直到全部子集僅包括同一類别的資料為止。最後得到一棵決策樹。它能夠用來對新的樣本進行分類。
2 取樣實驗
樣本資料：
outlook
temperature
humidity
windy
play
sunny
hot
high
FALSE
no
sunny
hot
high
TRUE
no
overcast
hot
high
FALSE
yes
rainy
mild
high
FALSE
yes
rainy
cool
normal
FALSE
yes
rainy
cool
normal
TRUE
no
overcast
cool
normal
TRUE
yes
sunny
mild
high
FALSE
no
sunny
cool
normal
FALSE
yes
rainy
mild
normal
FALSE
yes
sunny
mild
normal
TRUE
yes
overcast
mild
high
TRUE
yes
overcast
hot
normal
FALSE
yes
rainy
mild
high
TRUE
No
統計資料：(便于計算熵值)
outlook
temperature
humidity
windy
play
yes
no
yes
no
yes
no
yes
no
yes
no
sunny
2
3
hot
2
2
high
3
4
FALSE
6
2
9
5
overcast
4
mild
4
2
normal
6
1
TRUR
3
3
rainy
3
2
cool
3
1
2.1 Outlook為sunny時：
temperature
humidity
windy
play
hot
high
FALSE
no
hot
high
TRUE
no
mild
high
FALSE
no
cool
normal
FALSE
yes
mild
normal
TRUE
yes
temperature
humidity
windy
play
yes
no
yes
no
yes
no
yes
no
hot
2
high
3
FALSE
1
2
2
3
mild
1
1
normal
2
TRUR
1
1
cool
1
2.1.1 humidity為high時：
temperature
windy
play
hot
FALSE
no
hot
TRUE
no
mild
FALSE
no
另外一種情況，是以的樣本都屬于同一類别，用相應的類别屬性no來标記
2.1.2 humidity為normal時：
temperature
windy
play
cool
FALSE
yes
mild
TRUE
yes
另外一種情況，是以的樣本都屬于同一類别。用相應的類别屬性yes來标記
2.2 Outlook為overcast時：
temperature
humidity
windy
play
hot
high
FALSE
yes
cool
normal
TRUE
yes
mild
high
TRUE
yes
hot
normal
FALSE
yes
另外一種情況，是以的樣本都屬于同一類别，用相應的類别屬性yes來标記
2.3 Outlook為rainy時：
temperature
humidity
windy
play
mild
high
FALSE
yes
cool
normal
FALSE
yes
cool
normal
TRUE
no
mild
normal
FALSE
yes
mild
high
TRUE
no
temperature
humidity
windy
play
yes
no
yes
no
yes
no
yes
no
mild
2
1
high
1
1
FALSE
3
3
2
cool
1
1
normal
2
1
TRUR
2
2.3.1 temperature為milk時：
humidity
windy
play
high
FALSE
yes
normal
FALSE
yes
high
TRUE
no
humidity
windy
play
yes
no
yes
no
yes
no
high
1
1
FALSE
2
2
1
normal
1
TRUR
1
2.3.1.1 windy為false時：
humidity
play
high
yes
normal
yes
另外一種情況。是以的樣本都屬于同一類别，用相應的類别屬性yes來标記
2.3.1.2 windy為true時：
humidity
play
high
no
另外一種情況。是以的樣本都屬于同一類别。用相應的類别屬性no來标記
2.3.2 temperature為cool時：
temperature
humidity
windy
play
cool
normal
FALSE
yes
cool
normal
TRUE
yes
另外一種情況，是以的樣本都屬于同一類别，用相應的類别屬性yes來标記
經計算得到的決策樹：
3 ID3算法Java實作
ID3算法實作包含四個類的設計：
一、 決策樹節點類(TreeNode類)，包含類屬性：name(節點屬性名稱)。rule(節點屬性值域，也就是相應決策樹的分裂規則)。child(節點下的孩子節點)，datas(目前決策下相應的樣本元組)，candidateAttr(目前決策下剩餘的分類屬性)。
二、 最大資訊增益節點計算類(Gain類)：包含屬性值：D(目前決策層次下的樣本資料)，attrList(目前決策層次下的剩餘分類屬性)；包含方法：統計屬性取值方法，統計屬性不同取值計數方法。計算先驗熵和條件熵的方法，篩選指定屬性索引在指定值上的樣本元組方法，通過先驗熵減後驗熵計算出最大資訊增益值屬性的方法。
詳細方法在程式中都已經凝視，在這裡僅僅是依據需求給出方法的大緻功能。
三、決策樹建立類(DecisionTree類)：包含方法：計算目前樣本中分類屬性的取值及其計數，并由此計算出多數類。決策樹節點遞歸建構構成，詳細實作思想同課上講授内容，在此不在重述，借助的類是增益值計算類。
四、 ID3算法測試類(TestDecisionTree類)：借助于上面決策樹建立類。決策樹節點之間連接配接已經建立完成，以下将以上第二部分的樣本資料作為測試資料。而且實作遞歸列印方法。輸出決策樹詳細内容。