ID3算法是一種貪心算法，用來構造決策樹。ID3算法起源於概念學習系統（CLS），以信息熵的下降速度為選取測試屬性的標準，即在每個節點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標準，然後繼續這個過程，直到生成的決策樹能完美分類訓練樣例。
基本介紹
- 中文名：ID3算法
- 提出者：Quinlan
- 大學：悉尼大學
- 解釋：建立了概念學習系統(CLS)算法
背景知識,ID3算法,
背景知識
ID3算法最早是由羅斯昆（J. Ross Quinlan）於1975年在悉尼大學提出的一種分類預測算法，算法的核心是“信息熵”。ID3算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標準，重複這個過程，直至生成一個能完美分類訓練樣例的決策樹。
決策樹是對數據進行分類，以此達到預測的目的。該決策樹方法先根據訓練集數據形成決策樹，如果該樹不能對所有對象給出正確的分類，那么選擇一些例外加入到訓練集數據中，重複該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結構。
決策樹由決策結點、分支和葉子組成。決策樹中最上面的結點為根結點，每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或決策，通常對應於待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。沿決策樹從上到下遍歷的過程中，在每個結點都會遇到一個測試，對每個結點上問題的不同的測試輸出導致不同的分支，最後會到達一個葉子結點，這個過程就是利用決策樹進行分類的過程，利用若干個變數來判斷所屬的類別。
ID3算法
定義1：若存在n個相同機率的訊息，則每個訊息的機率p是1/n，一個訊息傳遞的信息量為-Log2(1/n)
定義2：若有n個訊息，其給定機率分布為P=(p1,p2…pn)，則由該分布傳遞的信息量稱為P的熵，記為
。
定義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)
數據描述
所使用的樣本數據有一定的要求,ID3是:
描述-屬性-值相同的屬性必須描述每個例子和有固定數量的價值觀。
預定義類-實例的屬性必須已經定義的,也就是說,他們不是學習的ID3。
離散類-類必須是尖銳的鮮明。連續類分解成模糊範疇(如金屬被“努力,很困難的,靈活的,溫柔的,很軟”都是不可信的。
足夠的例子——因為歸納概括用於(即不可查明)必須選擇足夠多的測試用例來區分有效模式並消除特殊巧合因素的影響。
屬性選擇
ID3決定哪些屬性如何是最好的。一個統計特性,被稱為信息增益,使用熵得到給定屬性衡量培訓例子帶入目標類分開。信息增益最高的信息(信息是最有益的分類)被選擇。為了明確增益,我們首先從資訊理論借用一個定義，叫做熵。每個屬性都有一個熵。
