決策樹的算法比較簡單
主要分為以下部分：
一、決策樹基本機率以及計算（ID3）
1、決策樹定義
決策樹(Decision Tree),又稱為判定樹, 是一種以樹結構(包括二叉樹和多叉樹)形式表達的預測分析模型。比如我們會問‘今天出去玩嗎’，那麼室外的溫度，天氣都會影響我們做決策的過程，如果‘溫度适中’，我們就再看‘天氣如何’。
決策樹學習的目地：産生一顆泛化能力強，處理未見示例強的決策樹
2、決策樹優缺點
決策樹學習的優點：速度快，準确率高，對中間缺失值不敏感
決策樹學習的缺點：對于各類别樣本數量不一緻的資料, 資訊增益偏向于那些更多數值的特征，容易過拟合，忽略屬性之間的相關性
3、需要掌握熵和資訊增益兩個概念和計算公式
熵：對樣本集合純度的一種度量，k指的是樣本類别個數
以表4.1為例：樣本類别個數為2，即好瓜和壞瓜，好瓜8個機率為8/17，壞瓜9個機率為9/17。
那麼可以計算根節點的熵為H=Ent(D)：
資訊增益：
1、假定離散屬性a有V個取值{a1，…aV}， 比如表4.1中，第一個屬性色澤有3個取值，分别是青綠、烏黑、淺白，v=3。
2、若使用a色澤對樣本集D進行劃分，會産生V（3）個分支，其中第v個包含了D中在a屬性上取值為av的所有樣本，記為Dv。比如D1（色澤=青綠），D2（色澤=烏黑），D3（色澤=淺白）
3、再根據不同分支結點包含的樣本數不同來給與權重：|Dv|/|D|，比如屬性（色澤）=6/17
資訊增益公式：
以色澤為例，計算3個分支的資訊熵：
計算（屬性=色澤）的資訊增益：
類似地：我們計算其他屬性的資訊增益：
Gain（D，根蒂）=0.143
Gain（D，敲聲）=0.141
Gain（D，根蒂）=0.381
Gain（D，根蒂）=0.289
Gain（D，根蒂）=0.006
其中紋理的資訊增益最大，把紋理選為屬性劃分：
依照上述步驟再分類對紋理的三個屬性進行劃分，得到最後的劃分結果。
這是我自己根據書上步驟寫的程式：
import math
import pandas as pd
import operator
import numpy as np
def data():
dataSet = [
['青綠', '蜷縮', '濁響', '清晰', '凹陷', '硬滑', '好瓜'],
['烏黑', '蜷縮', '沉悶', '清晰', '凹陷', '硬滑', '好瓜'],
['烏黑', '蜷縮', '濁響', '清晰', '凹陷', '硬滑', '好瓜'],
['青綠', '蜷縮', '沉悶', '清晰', '凹陷', '硬滑', '好瓜'],
['淺白', '蜷縮', '濁響', '清晰', '凹陷', '硬滑', '好瓜'],
['青綠', '稍蜷', '濁響', '清晰', '稍凹', '軟粘', '好瓜'],
['烏黑', '稍蜷', '濁響', '稍糊', '稍凹', '軟粘', '好瓜'],
['烏黑', '稍蜷', '濁響', '清晰', '稍凹', '硬滑', '好瓜'],
# ----------------------------------------------------
['烏黑', '稍蜷', '沉悶', '稍糊', '稍凹', '硬滑', '壞瓜'],
['青綠', '硬挺', '清脆', '清晰', '平坦', '軟粘', '壞瓜'],
['淺白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '壞瓜'],
['淺白', '蜷縮', '濁響', '模糊', '平坦', '軟粘', '壞瓜'],
['青綠', '稍蜷', '濁響', '稍糊', '凹陷', '硬滑', '壞瓜'],
['淺白', '稍蜷', '沉悶', '稍糊', '凹陷', '硬滑', '壞瓜'],
['烏黑', '稍蜷', '濁響', '清晰', '稍凹', '軟粘', '壞瓜'],
['淺白', '蜷縮', '濁響', '模糊', '平坦', '硬滑', '壞瓜'],
['青綠', '蜷縮', '沉悶', '稍糊', '稍凹', '硬滑', '壞瓜']
]
# 特征值清單
labels = ['色澤', '根蒂', '敲擊', '紋理', '臍部', '觸感']
return dataSet,labels
###################################################################################
#資訊熵
def Ent(df):
dic={}
EntD=0
#df = pd.DataFrame(dataset)
datalabel = df[df.shape[1] - 1] #擷取最後一列的資料
for i in set(datalabel): #統計好瓜和壞瓜個數
dic[i]=sum(datalabel==i)
for i in dic.values(): #計算資訊熵
EntD -=(i/len(df))*math.log(i/len(df),2)
return EntD
###################################################################################
#去除标簽那一列的資料
def remove(df,i):
dicall = []
#df=pd.DataFrame(dataset)
lei=set(df[i]) #屬性類别
for yangben in lei: #擷取去除标簽那列的資料
aa=df[(df[i]==yangben)]
aa=np.array(aa.drop([i], axis=1)).tolist() #删除标簽列，轉化為list儲存
aa=pd.DataFrame(aa) #重新轉化為dataframe格式
dicall.append(aa)
return dicall,lei
###################################################################################
#計算資訊增益
def Gain(dataset,labels):
dic={}
for i in range(len(labels)): #周遊每個标簽
ENtall = Ent(dataset) #得到資訊熵
dataset1,shuxing=remove(dataset,i)
for j in range(len(shuxing)): #計算每個屬性每個類别的資訊熵
size=Ent(dataset1[j])
ENtall-= (len(dataset1[j])/len(dataset))*size #得到資訊增益
dic[i] = ENtall #将屬性和資訊增益存在字典中
largelabels = sorted(dic.items(),key=operator.itemgetter(1), reverse=True) #将資訊增益排序
return largelabels[0][0] # 傳回最大的資訊增益
###########################################################################
#傳回最後類别中比較多的那一類[好瓜，好瓜，壞瓜]，傳回好瓜
def largedata(dataset):
dic = {}
setnum=set(dataset[dataset.shape[1]-1])
for i in setnum:
dic[i]=sum(dataset[dataset.shape[1]-1]==i)
aa=sorted(dic.items(),key=operator.itemgetter(1),reverse=True)
return aa[0][0]
######################################################################
#生成決策樹
def TreeGenerate1(dataset, labels):
df=pd.DataFrame(dataset)
if len(df)==1 : #第一個傳回條件
return np.array(df[len(df.ix[0])-1]).tolist()[0]
labelset=set(df[len(labels)])
if len(labels) == 0 or len(labelset) == 1: #第二個傳回條件
return largedata(dataset)
dic={}
dicall=[]
bestlabel=Gain(df,labels) #擷取最好标簽
dataset1,shu=remove(df,bestlabel) #去除最好标簽的資料集和屬性類别
#pdb.set_trace()
linedata1 = labels[:bestlabel]
linedata1.extend(labels[bestlabel + 1:]) #在清單中删除最好标簽
#pdb.set_trace()
for i,aa in enumerate(shu): #周遊屬性類别
dic1 = {}
dic1[aa]=TreeGenerate1(dataset1[i], linedata1) #生成字典dic1={清晰：？，模糊：？，稍糊：？}
dicall.append(dic1)
dic[labels[bestlabel]]=dicall #再将上邊的字典放入大字典中{紋理：dic1}
return dic
########################################################################
dataset, labels = data()
regr_1=TreeGenerate1(dataset, labels )
print(regr_1)
程式結果：
{'紋理': [{'清晰': {'根蒂': [{'稍蜷': {'色澤': [{'青綠': '好瓜'}, {'烏黑': {'觸感': [{'軟粘': '壞瓜'}, {'硬滑': '好瓜'}]}}]}}, {'硬挺': '壞瓜'}, {'蜷縮': '好瓜'}]}}, {'稍糊': {'觸感': [{'軟粘': '好瓜'}, {'硬滑': '壞瓜'}]}}, {'模糊': '壞瓜'}]}
程式講解：
以下是整個程式的流程圖：
二、資訊增益率
著名的C4.5算法就提出不使用資訊增益，而使用資訊增益率來劃分最優屬性。資訊增益率的出現是因為資訊增益不夠好，資訊增益對可取值數目較多的屬性有所偏好，這樣會造成決策樹分支多，深度淺。舉例：比如表4.1中，将編号也劃為屬性。那麼編号中有17個取值。Ent(Di)=0,Gain（編号）=0.998。這時候就會變成：
可見由編号作為劃分條件雖然可以直接判斷西瓜的好壞，但是這樣的分支屬性太多，并不一定是最好的。
資訊增益率公式：
Gain(D,a)我們通過第一節已經求出來了，資訊增益率就是用資訊增益除以IV（a）。v就是屬性的類别數目，比如色澤（青綠，烏黑，淺白）v=3。
得到IV（色澤）=1.580（v=3）
增益率準則對屬性類别較少的屬性（觸感V=2）有所偏好，是以C4.5不直接使用增益率最大的候選劃分屬性，而是先選出資訊增益高于平均值的屬性，再從中選擇增益率最高的一個。
三、CART基尼指數
資料集D的純度可以用基尼值來度量
表4.1中，以屬性色澤為例
基尼系數越小，屬性越優。
Gini 指數的計算不需要對數運算，更加高效；
Gini 指數更偏向于連續屬性，熵更偏向于離散屬性。
四、決策樹的過拟合
決策樹的對訓練資料集有很好的分類能力，但是對未知的測試書籍未必有很好的分類能力，泛化能力弱，容易發生過拟合。剪枝是處理過拟合問題的重要手段。剪枝分為預剪枝和後剪枝。
随機森林是一種比較好的處理決策樹過拟合的方法。
1、随機森林來源
Bagging政策
（從樣本中重采樣（有重複）選出n個樣本。
在所有屬性上對n個樣本建立分類器（ID3、C4.5、CART、SVM、logistic回歸））
重複以上m次，得到m個分類器
根據這m個分類器的結果，決定資料屬于哪一類
2、随機森林在Bagging基礎上做了修改
随機森林政策
（從資料集中用Bootstrap采樣選出n個樣本；
從所有屬性中随機選出k個屬性，選擇最佳分割屬性作為節點建立CART決策樹）
重複以上步驟m次，就得到m棵CART決策樹
這m個決策樹就是随機森林，通過投票表決結果
3、随機森林/Bagging/決策樹的關系
- 随機森林和Bagging可以使用決策樹為基本分類器
- 也可以使用SVM、Logistic回歸等其他分類器，習慣上，這些分類器組成總的“分類器”，仍然叫随機森林
想要了解關于內建學習-boosting算法，随機森林，bagging算法的，可以點這裡