决策树

思想：程序设计中分支结构if-then结构

信息熵

信息的单位：比特

$H = -(P1logP1 + P2logP2 + ... + PnlogPn)$H=−(P1logP1+P2logP2+...+PnlogPn)

信息和消除不确定性相联系
信息熵越大，不确定性越大，获取信息付出的代价越大

信息熵公式

$H(X) =- \sum _{x \in X} P(x)logP(x)$H(X)=−x∈X∑​P(x)logP(x)

信息增益

决策树的划分依据之一

信息增益：
得知一个特征A的信息而使得集合D的信息不确定性减少的程度

$g(D, A) = H(D) - H(D|A)$g(D,A)=H(D)−H(D∣A)

$H(D)$H(D) ：集合D的信息熵
$H(D|A)$H(D∣A)： 特征A给定条件下集合D的信息条件熵

信息熵计算

$H(D) =- \sum _{k=1}^{K} \frac{|C_{k}|} {|D|}log\frac{|C_{k}|}{|D|}$H(D)=−k=1∑K​∣D∣∣Ck​∣​log∣D∣∣Ck​∣​

条件熵计算
$H(D|A) = \sum _{i=1}^{n} \frac{|D_i|} {|D|}H(D_i) = - \sum _{i=1}^{n} \frac{|D_i|} {|D|} \sum _{k=1}^{K} \frac{|C_{ik}|}{|D_i|} log\frac{|C_{ik}|}{|D_i|}$H(D∣A)=i=1∑n​∣D∣∣Di​∣​H(Di​)=−i=1∑n​∣D∣∣Di​∣​k=1∑K​∣Di​∣∣Cik​∣​log∣Di​∣∣Cik​∣​

$C_{k}$Ck​ 表示属于某类别的样本数

计算举例

1、数据

ID  年龄  房子   类别
1   青年   无     否
2   青年   无     否
3   青年   有     是
4   青年   无     否
5   中年   有     否
6   中年   有     否
7   中年   有     是
8   老年   无     是
9   老年   有     否
10  老年   无     否

2、计算

# 经验熵：
H(D) = -(4/10log(4/10) + 6/10log(6/10)) = 0.97

# 年龄条件熵：
H(D|年龄) = 1/3H(青年) +  1/3H(中年) +  1/3H(老年)

H(青年) = -(1/4log(1/4) + 3/4log(3/4)) = 0.81
H(中年) = -(1/3log(1/3) + 2/3log(2/3)) = 0.92
H(老年) = -(2/3log(2/3) + 1/3log(1/3)) = 0.92

H(D|年龄) = 1/3 * 0.81 + 1/3 * 0.92 + 1/3 * 0.92 = 0.88

# 年龄信息增益：
g(D, 年龄) = H(D) - H(D|年龄) = 0.97 - 0.88 = 0.09

# 房子条件熵
H(D|房子) = 1/2H(有) +  1/2H(无)

H(有) = -(2/5log(2/5) + 3/5log(3/5)) = 0.97
H(无) = -(1/5log(1/5) + 4/5log(4/5)) = 0.72

H(D|房子) = 1/2 * 0.97 + 1/2 * 0.72 = 0.84

# 房子信息增益
g(D, 房子) = H(D) - H(D|房子) = 0.97 - 0.84 = 0.13

# 信息增益比较
g(D, 房子) > g(D, 年龄)

常见决策树使用的算法

ID3 信息增益最大准则
C4.5 信息增益比最大准则
CART
回归树：平方误差最小
分类树：基尼系数最小的准侧（划分更加仔细） sklean中默认划分原则

graphviz

决策树结构保存查看
1、安装graphviz

brew install graphviz

dot 转换为 png

$ dot -Tpng tree.doc -o tree.png

2、python接口

pip install graphviz

文档：https://graphviz.readthedocs.io/en/stable/index.html

代码示例

泰坦尼克数据集下载
https://www.kaggle.com/c/titanic/data

import pandas as pd
from graphviz import render
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_graphviz

# 读取数据
train = pd.read_csv("source/train.csv")

# 选取数据集和目标集
data = train[["Pclass", "Sex", "Age"]]
target = train["Survived"]

# 关闭警告
pd.set_option('mode.chained_assignment', None)

# 缺失值处理
data["Age"].fillna(data["Age"].mean(), inplace=True)

# 处理分类数据 数值替换为文本
data["Pclass"].replace(1, "low", inplace=True)
data["Pclass"].replace(2, "middle", inplace=True)
data["Pclass"].replace(3, "high", inplace=True)

# 拆分数据集成训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(
    data, target, test_size=0.25)

# 特征工程，类别-> One-Hot编码
dct = DictVectorizer(sparse=False)
X_train = dct.fit_transform(X_train.to_dict(orient="records"))
X_test = dct.transform(X_test.to_dict(orient="records"))
print(dct.get_feature_names())
# ['Age', 'Pclass=high', 'Pclass=low', 'Pclass=middle', 'Sex=female', 'Sex=male']

# 决策树进行预测
decision = DecisionTreeClassifier(max_depth=5)
decision.fit(X_train, y_train)
print(decision.score(X_test, y_test))
# 0.80

# 导出决策树
filename = "tree.dot"
feature_names = ['年龄', '高层', '中层', '底层', '女性', '男性']
export_graphviz(decision, filename, feature_names=feature_names)

# 渲染保存决策树
render("dot", "png", filename)