機器學習(5)之決策樹ID3及Python實現

微信公眾號

關鍵字全網搜索最新排名

【機器學習演算法】：排名第一

【機器學習】：排名第二

【Python】：排名第三

【演算法】：排名第四

ID3是什麼？

ID3演算法是決策樹的一種，基於

奧卡姆剃刀原理

用盡量用較少的東西做更多的事

Iterative Dichotomiser 3)，

迭代二叉樹3代

演算法的基礎就是上面提到的奧卡姆剃刀原理，越是小型的決策樹越優於大的決策樹，儘管如此，也不總

是生成最小的樹型結構，而是一個啟發式演算法。

在資訊理論中，期望信息越小，那麼信息增益就越大，從而純度就越高。

ID3演算法的核心思想就是以信息增益來度量屬性的選擇，選擇分裂後信息增益最大的屬性進行分裂。該演算法採用自頂向下的貪婪搜索遍歷可能的決策空間。

在1948年，香農引入了

信息熵

一個系統越

有序，信息熵越低，反之越是混亂，它的信息熵越高。

所以信息熵可以被認為是系統有序化程度的一個度量。

信息增益是針對一個一個特徵而言的，就是看一個特徵，系統有它和沒有它時的信息量各是多少，兩者

的差值就是這個特徵給系統帶來的信息量，即信息增益。

計算公式如下

Python實現

源代碼下載請

加入

機器學習交流2群（634808033）

後台回復關鍵詞：「20170711」

這裡採用的是從UCI上獲得的一個名為

agaricus-lepiota

準確率達到了99.63%

代碼在實現決策樹節點的分枝時是用遞歸實現的。其中，遞歸的終止條件有兩種：一是無法通過分枝產生信息增益，這樣自然就不必再分枝了，二是節點本身分得的樣本數達到了下限值minNumOfInstances，這種情況不再進行分枝的目的是為了避免造成過度擬合的問題。

main.py

pre_processing.py

decision_tree.py

參考：

1. 周志華《機器學習》

2. ACdreamers的博客：http://blog.csdn.net/acdreamers/article/details/44661149

3. stridehuan的博客：http://blog.csdn.net/u012822866/article/details/42419471

招募 志願者

廣告、商業合作

請加QQ：357062955@qq.com

喜歡，別忘關注~

幫助你在AI領域更好的發展，期待與你相遇！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！