Ensembles (4): AdaBoost
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 comments:
張貼留言