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