前言：人工智能機器學習有關算法內容，請參見公眾號“科技優(yōu)化生活”之前相關文章。人工智能之機器學習主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點探討一下ID3算法。
Hunt、Marin、和 Stone于1966年研制了一個概念學習系統(tǒng)CLS， 可以學習單個概念，并用此學到的概念分類新的實例。John Ross Quinlan（悉尼大學）于1983年研制了ID3算法。
ID3算法是決策樹的一種，它是基于奧卡姆剃刀原理的，即用盡量用較少的東西做更多的事。
ID3算法是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現對數據的歸納分類。
ID3算法概念：
ID3（Iterative Dichotomiser 3），即迭代二叉樹3代，該算法是一種貪心算法，用來構造決策樹【請參加人工智能（23）】。ID3算法起源于概念學習系統(tǒng)（CLS），以信息熵的下降速度為選取測試屬性的標準，即在每個節(jié)點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標準，然后繼續(xù)這個過程，直到生成的決策樹能完美分類訓練樣例。
ID3算法核心：
ID3算法核心是“信息熵”。ID3算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標準，重復這個過程，直至生成一個能完美分類訓練樣例的決策樹。
ID3算法本質：
在信息論中，期望信息越小，那么信息增益就越大，從而純度就越高。ID3算法本質是以信息增益來度量屬性的選擇，選擇分裂后信息增益最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策空間。
在決策樹的每一個非葉子結點劃分之前，先計算每一個屬性所帶來的信息增益，選擇最大信息增益的屬性來劃分，因為信息增益越大，區(qū)分樣本的能力就越強，越具有代表性，很顯然這是一種自頂向下的貪心策略。
ID3算法步驟：
計算各屬性的信息增益，找出最大者為根節(jié)點 1）先驗熵：沒有接收到其他屬性時的平均不確定性；
2）后驗熵：接收到輸出符號Vj時關于信源的不確定性 ；
3）條件熵：對后驗熵在輸出符號集V中求期望，接收到全部符號后對信源的不確定性 ；
4）信息增益：先驗熵與條件熵的差，是信宿端所獲得信息量；
5）對剩余屬性重復上述步驟。
ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創(chuàng)建一個節(jié)點，并以該節(jié)點的屬性標記，對該屬性的每個值創(chuàng)建一個分支據此劃分樣本。
具體算法流程如下：
ID3優(yōu)點：
1） 算法結構簡單；
2） 算法清晰易懂；
3） 非常靈活方便；
4） 不存在無解的危險；
5） 可以利用全部訓練例的統(tǒng)計性質進行決策，從而抵抗噪音。
ID3缺點：
1） 處理大型數據速度較慢，經常出現內存不足；
2） 不能處理連續(xù)型數據，只能通過離散化將連續(xù)性數據轉化為離散型數據；
3） 不可以并行，不可以處理數值型數據；
4） 只適用于非增量數據集，不適用于增量數據集，可能會收斂到局部最優(yōu)解而非全局最優(yōu)解，最佳分離屬性容易選擇屬性值多一些的屬性；
5） 沒有對決策樹進行剪枝處理，很可能會出現過擬合的問題。
注： ID3（并行）和ID3（number）解決了缺點3）的2個問題。
ID3應用場景：
決策樹ID3算法是一個很有實用價值的示例學習算法，它的基礎理論清晰，算法比較簡單，學習能力較強，適于處理大規(guī)模的學習問題，是數據挖掘和知識發(fā)現領域中的一個很好的范例，為后來各學者提出優(yōu)化算法奠定了理論基礎。ID3算法特別在機器學習、知識發(fā)現和數據挖掘等領域得到了極大發(fā)展。
結語：
ID3算法是基本的決策樹構建算法，作為決策樹經典的構建算法，具有算法結構簡單、理論清晰易懂、學習能力較強和靈活方便的特點。但也存在著不能處理連續(xù)型數據，不適用于增量數據集，處理大型數據速度較慢，可能會出現過擬合等缺點。ID3算法在世界上廣為流傳，得到極大的關注。ID3算法特別在機器學習、知識發(fā)現和數據挖掘等領域得到了極大發(fā)展。
（免責聲明：本網站內容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網站出現的信息，均僅供參考。本網站將盡力確保所提供信息的準確性及可靠性，但不保證有關資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責。本網站對有關資料所引致的錯誤、不確或遺漏，概不負任何法律責任。
任何單位或個人認為本網站中的網頁或鏈接內容可能涉嫌侵犯其知識產權或存在不實內容時，應及時向本網站提出書面權利通知或不實情況說明，并提供身份證明、權屬證明及詳細侵權或不實情況證明。本網站在收到上述法律文件后，將會依法盡快聯(lián)系相關文章源頭核實，溝通刪除相關內容或斷開相關鏈接。 ）
