訂閱
糾錯
加入自媒體

人工智能之AdaBoost算法

前言:人工智能機器學習有關(guān)算法內(nèi)容,人工智能之機器學習主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下ID3算法。 

Hunt、Marin、和 Stone于1966年研制了一個概念學習系統(tǒng)CLS, 可以學習單個概念,并用此學到的概念分類新的實例。John Ross Quinlan(悉尼大學)于1983年研制了ID3算法。

ID3算法決策樹的一種,它是基于奧卡姆剃刀原理的,即用盡量用較少的東西做更多的事。

ID3算法是以信息論為基礎(chǔ),以信息熵信息增益度為衡量標準,從而實現(xiàn)對數(shù)據(jù)的歸納分類

ID3算法概念

ID3Iterative Dichotomiser 3,即迭代二叉樹3,該算法是一種貪心算法,用來構(gòu)造決策樹【請參加人工智能(23)】。ID3算法起源于概念學習系統(tǒng)(CLS),以信息熵的下降速度為選取測試屬性的標準,即在每個節(jié)點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標準,然后繼續(xù)這個過程,直到生成的決策樹能完美分類訓練樣例。

ID3算法核心

ID3算法核心是“信息熵”。ID3算法通過計算每個屬性的信息增益,認為信息增益高的是好屬性,每次劃分選取信息增益最高的屬性為劃分標準,重復這個過程,直至生成一個能完美分類訓練樣例的決策樹。

ID3算法本質(zhì)

在信息論中,期望信息越小,那么信息增益就越大,從而純度就越高。ID3算法本質(zhì)是以信息增益來度量屬性的選擇,選擇分裂后信息增益最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策空間。

在決策樹的每一個非葉子結(jié)點劃分之前,先計算每一個屬性所帶來的信息增益,選擇最大信息增益的屬性來劃分,因為信息增益越大,區(qū)分樣本的能力就越強,越具有代表性,很顯然這是一種自頂向下的貪心策略。

ID3算法步驟:

計算各屬性的信息增益,找出最大者為根節(jié)點
1)先驗熵:沒有接收到其他屬性時的平均不確定性;

2)后驗熵:接收到輸出符號Vj時關(guān)于信源的不確定性 ;

3)條件熵:對后驗熵在輸出符號集V中求期望,接收到全部符號后對信源的不確定性 ;

4)信息增益:先驗熵與條件熵的差,是信宿端所獲得信息量;

5)對剩余屬性重復上述步驟。

ID3算法計算每個屬性的信息增益,并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創(chuàng)建一個節(jié)點,并以該節(jié)點的屬性標記,對該屬性的每個值創(chuàng)建一個分支據(jù)此劃分樣本。

具體算法流程如下:

ID3優(yōu)點

1)   算法結(jié)構(gòu)簡單;

2)   算法清晰易懂;

3)   非常靈活方便;

4)   不存在無解的危險;

5)   可以利用全部訓練例的統(tǒng)計性質(zhì)進行決策,從而抵抗噪音。

ID3缺點:

1)    處理大型數(shù)據(jù)速度較慢,經(jīng)常出現(xiàn)內(nèi)存不足;

2)    不能處理連續(xù)型數(shù)據(jù),只能通過離散化將連續(xù)性數(shù)據(jù)轉(zhuǎn)化為離散型數(shù)據(jù);

3)    不可以并行,不可以處理數(shù)值型數(shù)據(jù);

4)    只適用于非增量數(shù)據(jù)集,不適用于增量數(shù)據(jù)集,可能會收斂到局部最優(yōu)解而非全局最優(yōu)解,最佳分離屬性容易選擇屬性值多一些的屬性;

5)    沒有對決策樹進行剪枝處理,很可能會出現(xiàn)過擬合的問題。

注: ID3(并行)和ID3(number)解決了缺點3)的2個問題。

ID3應用場景:

決策樹ID3算法是一個很有實用價值的示例學習算法,它的基礎(chǔ)理論清晰,算法比較簡單,學習能力較強,適于處理大規(guī)模的學習問題,是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)領(lǐng)域中的一個很好的范例,為后來各學者提出優(yōu)化算法奠定了理論基礎(chǔ)。ID3算法特別在機器學習、知識發(fā)現(xiàn)數(shù)據(jù)挖掘等領(lǐng)域得到了極大發(fā)展。

結(jié)語:

ID3算法是基本的決策樹構(gòu)建算法,作為決策樹經(jīng)典的構(gòu)建算法,具有算法結(jié)構(gòu)簡單、理論清晰易懂、學習能力較強和靈活方便的特點。但也存在著不能處理連續(xù)型數(shù)據(jù),不適用于增量數(shù)據(jù)集,處理大型數(shù)據(jù)速度較慢,可能會出現(xiàn)過擬合等缺點。ID3算法在世界上廣為流傳,得到極大的關(guān)注。ID3算法特別在機器學習、知識發(fā)現(xiàn)數(shù)據(jù)挖掘等領(lǐng)域得到了極大發(fā)展。

聲明: 本文由入駐維科號的作者撰寫,觀點僅代表作者本人,不代表OFweek立場。如有侵權(quán)或其他問題,請聯(lián)系舉報。

發(fā)表評論

0條評論,0人參與

請輸入評論內(nèi)容...

請輸入評論/評論長度6~500個字

您提交的評論過于頻繁,請輸入驗證碼繼續(xù)

暫無評論

暫無評論

人工智能 獵頭職位 更多
掃碼關(guān)注公眾號
OFweek人工智能網(wǎng)
獲取更多精彩內(nèi)容
文章糾錯
x
*文字標題:
*糾錯內(nèi)容:
聯(lián)系郵箱:
*驗 證 碼:

粵公網(wǎng)安備 44030502002758號