機器學習實戰-決策樹(ID3)

//====================================================

決策樹的構造：

構造決策樹時，需要解決的第一個問題是，目前資料集上那個特征在劃分資料是起決定性作用。為了找到決定性特征，我們必須使用某種度量來評估每個特征。完成評估之後，找到決定性特征，使用該特征劃分資料，原始的資料集就被劃分為幾個資料子集。這個子集會釋出在第一個決策點的所有分支。如果某個分支下的資料屬于同一類型，則目前已經準确劃分資料分類。如果資料子集内的資料不屬于同一類型，則需要重複劃分資料子集的過程。劃分資料的方法跟劃分原始資料的方法相同。

本文使用ID3算法劃分資料集，每次劃分時隻取一個特征屬性，如果資料集有多個特征，如何選取決定性特征？在采用量化的方法判斷如何劃分資料。

資訊增益：

劃分資料集的最大原則是：将無序的資料變得更加有序。一種方法是使用資訊論度量資訊。

在劃分資料集之前之後資訊發生的變化稱為資訊增益。可以計算每個特征值劃分資料集獲得的資訊增益，獲得的資訊增益最高的特征就是最好的選擇。

計算資訊增益：

集合資訊的度量方式稱為香農熵或者熵，定義為資訊的期望值。

資訊（xi）的定義：如果待分類的事務可能劃分在多個分類之中，則符号xi的資訊定義為l(xi)=-log2

p(xi),其中p(xi)是選擇該分類的機率

計算熵，計算所有分類所有可能值包含的資訊期望值：H=-Σp(xi)*log2 p(xi)

python計算熵的代碼如下：

//=====================================================

劃分資料集代碼：

dataSet為待劃分的資料集

axis為劃分資料的特征

value為劃分資料的特征的值

結果為傳回劃分好資料的特征

選擇最好的資料集劃分方式：

dataSet每行的最後一個元素為該行特征的标簽

//===============================================

構造決策樹，原理：得倒原始資料，基于最好的屬性值劃分資料集，由于特征值可能對于兩個，是以可能存在大于兩個分支的資料劃分。第一次劃分之後，在資料将被向下傳遞到樹分支的下一個節點，在這個節點上我們再次劃分資料。是以可以采用遞歸的方法劃分資料。

遞歸的結束條件：程式周遊完所有的特征或者每個分支下所有的資料都屬于同一分類。但是遞歸結束後，某個節點的資料不一定都屬于同一分類。此時我們需決定該節點的分類。這種情況下我們通常采用多票表決的方法。

代碼如下：

構造決策樹的代碼：

//=============================================

構造完決策樹，我們就可以使用決策樹執行分類。

分類的代碼如下：

//==============================================

使用python中的Matplotlib庫繪制決策樹樹形圖。

繪制的效果如下：

//====================================

總的代碼：http://pan.baidu.com/s/1bnla1HH