Hike News
Hike News

機器學習-演算法-決策樹(decision tree)

Introduction

程序設計中的條件分支結構就是if-then結構,最早的決策樹就是利用這類結構分割數據的一種分類學習方法

信息熵

在選擇64個數字中,誰會是終極密碼的信息量應該為6bit(二分法往下尋找)
且在開放某些信息的情況下,信息熵(代價)會比6bit少
準確的信息量應為:
$$
H = -(p1\log(p1) + p2\log(p2) + … + p64log(p64))
$$

  • H為信息熵單位為bit

公式

$$
H(X) = \sum P(x) \log(P(x))
$$

  • 當上面64個數字選取的機率相同時,對應的信息熵等於6bit
  • 信息熵越大,不確定性亦越大

決策樹

作為決策樹越前面的決策,通常是為了大幅的減少不確定性(大幅降低信息熵)
因此作為越前面的決策,它減少的信息熵一定會比接下來的決策大

常見的決策樹演算法

  • ID3 信息增益 (最大作為決策優先)
  • C4.5 信息增益比 (最大作為決策優先)
  • CART
    • 回歸樹:平方誤差 (最小作為決策優先)
    • 分類樹:基尼係數 (最小作為決策優先)
      • 在sklearn中決策樹演算法的默認原則
      • 相對信息增益而言 劃分更加仔細

信息增益

  • 為決策樹劃分的依據之一
  • 定義:當得知一個特徵條件X之後,使得類別Y信息的不確定性減少的程度(信息熵減少程度),程度越大則為越前面的決策

公式

特徵$A$對訓練數據集$D$的信息增益,記作 $g(D,A)$
定義為 集合$D$ 的信息熵為 $H(D)$ 與 給定特徵$A$的條件下 $D$的條件信息熵記作$H(D|A)$ 之差
$$
g(D,A) = H(D) - H(D|A)
$$

  • $H(D)$:初始信息熵大小
  • $H(D|A):條件熵的大小

sklearn決策樹API

  • 為一種estimator
  • 使用sklearn.tree.DecisionTreeClassifier(criterion="gini", max_depth=None, random_state=None)

    • criterion:預設是使用”gini”係數進行分類,選擇信息增益的熵作為分類依據則使用”entropy”
    • max_depth:樹的深度大小 (為超參數 可調優)
    • random_state:隨機數seed
  • 樹的結構可視化

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from sklearn.model_selection import train_test_split
from sklearn.feature_extraction import DictVectorizer
from sklearn.tree import DecisionTreeClassifier
import pandas as pd

datapath = "../Kaggle Dataset/Titanic/train.csv"

def Decision():
data = pd.read_csv(datapath)
X = data[["Pclass","Sex","Age"]]
Y = data["Survived"]

# 填補缺失值
X["Age"].fillna(X["Age"].mean(),inplace=True) # inplace是否直接替換

X_train,X_test,y_train,y_test = train_test_split(X,Y,test_size=0.25)

# 特徵為類別使用one-hot編碼
DV = DictVectorizer(sparse=False)

# DictVectorizer需使用字典形式,使用to_dict轉換為字典形式
X_train = DV.fit_transform(X_train.to_dict(orient="records")) # orient為records為一行行轉換
X_test = DV.transform(X_test.to_dict(orient="records"))

D_tree = DecisionTreeClassifier()
D_tree.fit(X_train,y_train)
score = D_tree.score(X_test,y_test)
print("score:",score)

if __name__ == '__main__':
Decision()

result

1
score: 0.8251121076233184

決策樹可視化

  • 使用sklearn.tree.export_graphviz()導出dot格式

export_graphviz

  • tree.export_graphviz(estimator, out_file=”./tree.dot”, feature_names=[“”,””])
    • estimator : 實例化的estimator物件
    • out_file : 輸出文件名
    • feature_names : 樹的劃分是按特徵進行劃分的,將他的get_featurenames貼上
      • [“Age”,”pclass=1st”,”pclass=2nd”,”pclass=3rd”,”sex=female”,”sex_male”]

工具graphviz可視化

  • brew install graphviz
  • 轉成圖片使用dot -Tpng tree.dot -o tree.png

優缺點

  • 優點:
    • 簡單的理解和解釋,樹木可視化
    • 數據的前處理很少,其他技術通常需要歸一化或標準化處理
  • 缺點:
    • 一開始學習決策樹演算法時,常常創建不能很好的分類數據過於複雜的樹被稱之為過擬合
    • 複雜的決策樹雖在訓練集中100%擬合,但在測試數據時往往表現不好
  • 改進:
    • 使用剪枝cart算法(在決策樹的API當中已實現),減少過擬合的情況發生
      • 在實例化決策樹DecisionTreeClassifier時有兩個參數為min_samples_splitmin_samples_leaf可控制分支數
        • min_samples_split
        • min_samples_leaf
    • 隨機森林

tips

  • 企業重要決策,由於決策樹很好的分析能力,在決策過程應用較多