01
簡介
ID3算法是一種貪心算法，最早由羅斯昆(J. Ross Quinlan)于1975年在悉尼大學提出，算法的核心是“資訊熵”。ID3算法通過計算每個屬性的資訊增益，認為資訊增益高的是好屬性，每次劃分選取資訊增益最高的屬性為劃分标準，重複這個過程，直至生成一個能完美分類訓練樣例的決策樹。
02
貪心算法
貪心算法是一種對某些求最優解問題的更簡單、更迅速的設計技術。貪心算法的特點是一步一步地進行，常以目前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪心算法采用自頂向下，以疊代的方法做出相繼的貪心選擇，每做一次貪心選擇，就将所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解。
03
決策樹
決策樹是對資料進行分類，以此達到預測的目的。該決策樹方法先根據訓練集資料形成決策樹，如果該樹不能對所有對象給出正确的分類，那麼選擇一些例外加入到訓練集資料中，重複該過程一直到形成正确的決策集。決策樹代表着決策集的樹形結構。
決策樹類似于流程圖的一個樹形結構。樹的最頂層是根結點。其中每個内部結點表示在一個屬性上的測試，每個分支代表一個屬性的輸出，每個葉子結點代表類或者類的分布。
決策樹的優缺點：
優點：直覺，便于了解，小規模資料集有效。
缺點：處理連續變量不好；類别較多時，錯誤增加的比較快(算法複雜度大)；可規模性一般。
04
資訊熵
1948年，香農提出了“資訊熵”的概念，描述了信源的不确定度，解決了對資訊的量化度量的問題。香農指出，任何資訊都存在備援，備援大小與資訊中每個符号(數字、字母或單詞)的出現機率或者說不确定性有關。即資訊的度量就等于不确定性的大小。通常，一個信源發送出什麼符号是不确定的，衡量它可以根據其出現的機率來度量。機率大，出現機會多，不确定性小；反之不确定性就大。比特(bit)來衡量資訊的多少，用P(Xi)表示一個某個符号出現的機率，那麼資訊熵H(X)的值就是：
變量的不确定性越大，熵也就越大，資訊熵的取值範圍是0到1之間。
05
ID3算法
ID3算法的核心是在決策樹各個節點上應用資訊增益準則選擇特征遞歸地建構決策樹。設有随機變量(X, Y)，其聯合機率分布為：
條件熵：
條件熵H(Y|X)表示在已知随機變量X的條件下，随機變量Y的不确定性。随機變量X給定的條件下随機變量Y的條件熵H(Y|X)，定義為X給定條件下Y的條件機率分布的熵對X的數學期望：
當熵和條件熵中的機率由資料估計得到時(如極大似然估計)，所對應的熵與條件熵分别稱為經驗熵和經驗條件熵。
資訊增益：
資訊增益表示由于得知特征A的資訊後的資料集D的分類不确定性減少的程度，定義為：
即集合D的經驗熵H(D)與特征A給定條件下D的經驗條件熵H(H|A)之差。選擇劃分後資訊增益大的作為劃分特征，說明使用該特征後劃分得到的子集純度越高，即不确定性越小。是以我們總是選擇目前使得資訊增益最大的特征來劃分資料集。
資料來源
https://baike.baidu.com/item/ID3算法/5522381?fr=aladdin
https://my.oschina.net/u/3470937/blog/3009396
https://shuwoom.com/?p=1452
https://baike.baidu.com/item/貪心算法/5411800?fr=aladdin
本期文案|芃
本期排版|芃
實用數學|超級實用的距離判别法
實用數學| 排隊論模型的簡介與建構
實用數學|第十期 最短路徑模型