定義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。
離散類-類必須是尖銳的鮮明。連續類分解成模糊範疇(如金屬被“努力,很困難的,靈活的,溫柔的,很軟”都是不可信的。
足夠的例子——因為歸納概括用於(即不可查明)必須選擇足夠多的測試用例來區分有效模式並消除特殊巧合因素的影響。
屬性選擇
ID3決定哪些屬性如何是最好的。壹個統計特性,被稱為信息增益,使用熵得到給定屬性衡量培訓例子帶入目標類分開。信息增益最高的信息(信息是最有益的分類)被選擇。為了明確增益,我們首先從信息論借用壹個定義，叫做熵。每個屬性都有壹個熵。