經典分類算法——決策樹算法(ID3)

機器學習 人工智能 科技 數據分析之路 2017-05-14

決策樹算法

決策樹方法最早產生於上世紀60年代,到70年代末。由J Ross Quinlan提出了ID3算法,此算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進,對於預測變量的缺值處理、剪枝技術、派生規則等方面作了較大改進,既適合於分類問題,又適合於迴歸問題。

經典分類算法——決策樹算法(ID3)

決策樹算法:顧名思義,以二分類問題為例,即利用自變量構造一顆二叉樹,將目標變量區分出來,所有決策樹算法的關鍵點如下:

1.分裂屬性的選擇。即選擇哪個自變量作為樹叉,也就是在n個自變量中,優先選擇哪個自變量進行分叉。而採用何種計算方式選擇樹叉,決定了決策樹算法的類型,即ID3、c4.5、CART三種決策樹算法選擇樹叉的方式是不一樣的,後文詳細描述。

2.樹剪枝。即在構建樹叉時,由於數據中的噪聲和離群點,許多分支反映的是訓練數據中的異常,而樹剪枝則是處理這種過分擬合的數據問題,常用的剪枝方法為先剪枝和後剪枝。

決策樹算法-ID3(一)

ID3算法大致思想描述:

對當前例子集合,計算屬性的信息增益; 選擇信息增益最大的屬性Ai(關於信息增益後面會有詳細敘述);把在Ai處取值相同的例子歸於同於子集,Ai取幾個值就得幾個子集;對依次對每種取值情況下的子集,遞歸調用建樹算法,即返回a; 若子集只含有單個屬性,則分支為葉子節點,判斷其屬性值並標上相應的符號,然後返回調用處。

下面用一個例子看一下:

經典分類算法——決策樹算法(ID3)

示例數據

計算過程:

經典分類算法——決策樹算法(ID3)

計算

ID3樹形狀

經典分類算法——決策樹算法(ID3)

決策樹

ID3算法的優缺點

ID3的優點

不存在無解的危險;可以利用全部訓練例的統計性質進行決策,從而抵抗噪音。

ID3的缺點

處理大型數據速度較慢,經常出現內存不足,不可以並行,不可以處理數值型數據;ID3(並行)和ID3(number)解決了後兩個問題。只適用於非增量數據集,不適用於增量數據集,可能會收斂到局部最優解而非全局最優解,最佳分離屬性容易選擇屬性值多一些的屬性。

最近會介紹一些數據分析經典算法,感興趣的同學關注一下一起學習哦!

相關推薦

推薦中...