決策樹：決策樹是一種簡單的機器學習方法，它是對被觀測資料進行分類的一種相當直覺的方法，決策樹在經過訓練之後，看起來就像是以樹狀形式排列的一系列if-then語句，一旦我們有了決策樹，根據決策樹進行決策的過程就非常的簡單，隻有沿着樹的路徑一直向下，正确的回答每一個問題，就會得到最終的答案。随機森林是在建立多棵決策樹，然後按照不同決策樹的結果選擇輸出屬性最多的那個作為最後的結果。
一、幾個重要概念
1、基尼不純度（Gini Impurity）：
基尼不純度是一種度量集合有多純的方法，如果集合裡面的值都是一個數的話，則基尼不純度的值為0，随着混合的東西越多，則基尼不純度值越高。公式為
def giniimpurity(l):
total = len(l)
counts = {}
for item in l:
counts.setdefault(item,0)
counts[item]+= 1
imp = 0
for j in l:
f1 = float(counts[j])/total
for k in l:
if j==k:continue
f2 = float(counts[k])/total
imp += f1 * f2
return imp
#x = [1,1,1]
#print giniimpurity(x)
2、熵（Entropy）：
在資訊論中，熵代表的是集合的無序程度，即我們所處的目前集合的混雜程度。可以看成我們從集合中随機抽取一個元素的意外程度，如果說集合中的所有元素都是A,那麼當我們從中抽取A元素的時候是絕對不出現意外的，此時的熵為0。熵的計算公式為：
def entropy(l):
from math import log
log2 = lambda x: log(x)/log(2)
total = len(l)
counts = {}
for item in l:
counts.setdefault(item,0)
counts[item] += 1
ent = 0
for i in counts:
p = float(counts[i])/total
ent -= p * log2(p)
return ent
#x = [1,1,1,2,3]
#print entropy(x)
熵和基尼不純度之間的主要差別在于，熵達到峰值的過程相對要慢一些，是以，熵對于混亂集合的“判罰”往往要更重一些。由于人們對于熵的使用更為普遍，以下都用熵作為度量标準。
3、資訊增益：
已經有了熵或者基尼不純度作為衡量訓練樣本集合的純度标準，由此，我們可以定義屬性分類訓練資料的效率度量标準。這個标準被稱為“資訊增益（information gain）”。假設我們選用熵來作為度量标準，一個屬性的資訊增益就是由于使用了這個屬性對樣本進行分割，進而導緻的期望的熵值降低（分類更為純淨）。其定義公式如下：
V(A)是屬性A的值域
S是樣本集合
S（v）是S中屬性A值等于v的樣本的集合
二、ID3算法
ID3算法用于決策樹建立的過程：
（1）對于目前的所有樣本集合，計算每個屬性的資訊增益
（2）選擇資訊增益最大的屬性（假設為Ai）
（3）把在Ai出取值相同的樣本對于同一個子集，Ai有幾個屬性，就合成幾個子集
（4）重複以上的三個過程，直到結束（熵值為0或者一個門檻值）
ID3算法使用的是自頂向下的貪婪搜尋便利可能的決策樹空間構造，屬于局部最優，不一定全局最優。
三、C4.5算法
C4.5是另一種決策樹構造算法，它是上文ID3的一個改進。主要的差别如下：
（1）用資訊增益率代替資訊增益來選擇屬性，ID3選擇屬性用的是子樹的資訊增益，而C4.5用的是資訊增益率。
（2）在樹的構造過程中進行剪枝，比較不容易overfiting
（3）對非離散值也可以進行處理
（4）能夠對不完整的資料進行處理
在對于資訊增益和資訊增益率的比較上，july用了一個很好的例子來說明：一般來說率就是用來取平衡用的，就像方差起的作用差不多，比如有兩個跑步的人，一個起點是10m/s的人、其10s後為20m/s；另一個人起速是1m/s、其1s後為2m/s。如果緊緊算內插補點那麼兩個差距就很大了，如果使用速度增加率(加速度，即都是為1m/s^2)來衡量，2個人就是一樣的加速度。是以，C4.5克服了ID3用資訊增益選擇屬性時偏向選擇取值多的屬性的不足。
資訊增益率的定義：
分裂資訊度量被定義為(分裂資訊用來衡量屬性分裂資料的廣度和均勻)：
四、CART算法（Classification And Regression Tree）
CART也是決策樹的一種生成算法，主要的差别在于CART的決策是二叉樹的，它同樣可以處理離散值，但是，隻能選擇其中一種來把資料分成兩個部分。
對于其中有多重輸出結果的屬性，是如何選擇它的拆分方法的？根據集體智慧程式設計的方法，對于屬性A的所有取值儲存下來，分别計算他們的資訊增益，然後選擇資訊增益最高的value進行拆分。
Reference：
《集體智慧程式設計》
《資料挖掘——實用機器學習》
http://blog.csdn.net/v_july_v/article/details/7577684