决策树
同步更新在个人网站：http://www.wangpengcufe.com/machinelearning/pythonml-pythonml4/

一、决策树的原理

决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-then结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法 。

二、决策树的现实案例

相亲

相亲决策树

女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

银行是否发放贷款

行长：是否有自己的房子？
职员：有。
行长：可以考虑放贷。
职员：如果没有自己的房子呢？
行长：是否有稳定工作？
职员：有。
行长：可以考虑放贷。
职员：那如果没有呢？
行长：既没有自己的房子，也没有稳定工作，那咱还放啥贷款？
职员：懂了。

贷款决策树

预测足球队是否夺冠

预测决策树

三、信息论基础

信息熵：

假如我们竞猜32只足球队谁是冠军？我可以把球编上号，从1到32，然后提问：冠 军在1-16号吗？依次进行二分法询问，只需要五次，就可以知道结果。
32支球队，问询了5次，信息量定义为5比特，log32=5比特。比特就是表示信息的单位。
假如有64支球队的话，那么我们需要二分法问询6次，信息量就是6比特，log64=6比特。
问询了多少次，专业术语称之为信息熵，单位为比特。
公式为：

信息熵

信息熵的作用：
决策树生成的过程中，信息熵大的作为根节点，信息熵小的作为叶子节点，按照信息熵的从大到小原则，生成决策树。

条件熵：

条件熵H（D|A）表示在已知随机变量A的条件下随机变量D的不确定性。
公式为：

条件熵

通俗来讲就是，知道A情况下，D的信息量。

信息增益：

特征A对训练数据集D的信息增益g(D,A),定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差。
公式为：

信息增益

怎么理解信息增益呢？信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。简单讲，就是知道的增多，使得不知道的（不确定的）就减少。

四、 决策树API

sklearn.tree.DecisionTreeClassifier

class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)
决策树分类器
criterion:默认是’gini’系数，也可以选择信息增益的熵’entropy’
max_depth:树的深度大小
random_state:随机数种子

method:
dec.fit(X,y): 根据数据集(X,y)建立决策树分类器
dec.apply(X): 返回每个样本被预测为的叶子的索引。
dec.cost_complexity_pruning_path(X,y): 在最小成本复杂性修剪期间计算修剪路径。
dec.decision_path(X): 返回树中的决策路径
dec.get_depth(): 返回树的深度
dec.get_n_leaves(): 返回决策树的叶子节点
dec.get_params(): 返回评估器的参数
dec.predict(X): 预测X的类或回归值
dec.predict_log_proba(X): 预测X的类的log值
dec.predict_proba(X): 预测X分类的概率值
dec.score(X,y): 测试数据X和标签值y之间的平均准确率
dec.set_params(min_samples_split=3): 设置评估器的参数
X 表示训练集，y表示特征值

五、 决策树的生成与本地保存

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
li = load_iris()
dec = DecisionTreeClassifier()
# 根据训练集(X,y)建立决策树分类器
dec.fit(li.data,li.target)
# 预测X的类或回归值
dec.predict(li.data)
# 测试数据X和标签值y之间的平均准确率
dec.score(li.data,li.target)
# 保存树文件 tree.dot
tree.export_graphviz(dec,out_file='tree.dot')

tree.dot 保存结果:

digraph Tree {
node [shape=box] ;
0 [label="X[2] <= 2.45\ngini = 0.667\nsamples = 150\nvalue = [50, 50, 50]"] ;
1 [label="gini = 0.0\nsamples = 50\nvalue = [50, 0, 0]"] ;
.....

六、 决策树的优缺点

优点

• 简单的理解和解释，树木可视化。
• 需要很少的数据准备，其他技术通常需要数据归一化。

缺点

• 决策树学习者可以创建不能很好地推广数据的过于复杂的树，被称为过拟合。
• 决策树可能不稳定，因为数据的小变化可能会导致完全不同的树
  被生成。

改进

• 减枝cart算法
• 随机森林