cookieOptions = {...}; .人工智慧之 Ada Boost 算法 - 3S Market「全球智慧科技應用」市場資訊網

3S MARKET


智慧城市展智慧安控專區 ——

讓您建立「解決方案產業鏈合作夥伴」

並直通應用場域

2018年7月23日 星期一

Ensembles (4): AdaBoost





來源AI 优化生活


Hunt、Marin、和 Stone於1966年研製了一個概念學習系統CLS, 可以學習單個概念,並用此學到的概念分類新的實例。John Ross Quinlan(雪梨大學)於1983年研製了ID3算法




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

ID3算法是以資訊論為基礎,以資訊熵資訊增益度為衡量標準,從而實現對數據的歸納分類




ID3算法概念:
ID3(Iterative Dichotomiser 3),即更新版二叉樹3代,該算法是一種貪心算法,用來構造決策樹【請參加人工智慧(23)】。ID3算法起源於概念學習系統(CLS),以資訊的下降速度,為選取測試屬性的標準,即在每個節點選取,還尚未被用來劃分的,具有最高資訊增益的屬性,作為劃分標準,然後繼續這個過程,直到生成的決策樹能完美分類訓練樣例。




ID3算法核心:
ID3算法核心是「資訊」。ID3算法透過計算,每個屬性的資訊增益,認為資訊增益高的是好屬性,每次劃分選取資訊增益最高的屬性為劃分標準,重覆這個過程,直至生成一個能完美分類訓練樣例的決策樹。




ID3算法本質:
在資訊論中,期望資訊越小,那麼資訊增益就越大,從而純度就越高。ID3算法本質是以資訊增益,來度量屬性的選擇,選擇分裂後,資訊增益最大的屬性進行分裂。該算法採用自頂向下的貪婪搜索遍歷可能的決策空間。

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




ID3算法步驟:
計算各屬性的資訊增益,找出最大者為根節點 
1)先驗熵:沒有接收到其他屬性時的平均不確定性;

2)後驗熵:接收到輸出符號 Vj 時關於信源的不確定性 ;

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

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

5)對剩餘屬性重複上述步驟。





ID3算法計算每個屬性的資訊增益,並選取具有最高增益的屬性,作為給定集合的測試屬性。對被選取的測試屬性,創建一個節點,並以該節點的屬性標記,對該屬性的每個值創建一個分支據此劃分樣本。

具體算法流程如下:


ID3優點:
1)算法結構簡單;

2)算法清晰易懂;

3)非常靈活方便;

4)不存在無解的危險;

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

ID3缺點:
1)處理大型數據速度較慢,經常出現內存不足;

2)不能處理連續型數據,只能通過離散化,將連續性數據轉化為離散型數據;

3)不可以並行,不可以處理數值型數據;

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

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

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

ID3應用場景:
決策樹ID3算法是一個很有實用價值的示例學習算法,它的基礎理論清晰,算法比較簡單,學習能力較強,適於處理大規模的學習問題,是數據挖掘和知識發現領域中的,一個很好的範例,為後來各學者提出優化算法,奠定了理論基礎。ID3算法特別在機器學習知識發現數據挖掘等領域,得到了極大發展。




結語:
ID3算法是基本的決策樹構建算法,作為決策樹經典的建構算法,具有算法結構簡單、理論清晰易懂、學習能力較強和靈活方便的特點。

但也存在著不能處理連續型數據,不適用於增量數據集,處理大型數據速度較慢,可能會出現過擬合等缺點。

ID3算法在世界上廣為流傳,得到極大的關注。ID3算法特別在機器學習知識發現數據挖掘等領域得到了極大發展。



0 意見: