一. 什么是决策树
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。
如图即为最简单的决策树
二.决策树名词
1.根节点：最顶部的那个节点
2.叶子节点：每条路径最末尾的那个节点，也就是最外层的节点
3.非叶子节点：一些条件的节点，下面会有更多分支，也叫做分支节点
4.分支：也就是分叉
三.决策树的判断-信息熵
先看一下信息熵的公式：
其中：𝑝(𝑥𝑖)代表随机事件𝑥𝑖的概率。
首先了解一下信息量：信息量是对信息的度量，就跟时间的度量是秒一样，当我们考虑一个离散的随机变量 x 的时候，当我们观察到的这个变量的一个具体值的时候，我们接收到了多少信息呢？
多少信息用信息量来衡量，我们接受到的信息量跟具体发生的事件有关。
信息的大小跟随机事件的概率有关。越小概率的事情发生了产生的信息量越大，如孝感发生的地震了；越大概率的事情发生了产生的信息量越小，如太阳从东边升起来了（肯定发生嘛， 没什么信息量）。这很好理解！
因此一个具体事件的信息量应该是随着其发生概率而递减的，且不能为负。
因此我们就得到信息量的公式为：
信息量度量的是一个具体事件发生了所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望
转换一下：
四.决策树与实践
我们以小明起床为例：
我们随机抽了一年中14天小明的赖床情况
可以发现，数据中有三个属性会影响到最终的结果，分别是，季节，时间是否过8点，风力情况
在计算每一个属性的信息熵之前，我们需要先根据历史数据，计算没有任何属性影响下的赖床信息熵。从数据我们可以知道，12天中，有赖床为8天，不赖床为4天。则
p(赖床) = 8 / 12
p(不赖床) = 4 / 12.
信息熵为：
H(赖床) =-(p(赖床) * log(p(赖床)) + p(不赖床) * log(p(不赖床)))
= -((8/12)*log(8/12)+(6/12)*log(6/12)
=0.918
接下来就可以来计算每个属性的信息熵了，这里有三个属性，即季节，是否过早上8点，风力情况，我们需要计算三个属性的每个属性在不同情况下，赖床和不赖床的概率，以及熵值。
我们以风力情况为例：
风力情况为 breeze 时，有 4 / 5 的概率会赖床，而 1 / 5 的概率不会赖床
熵为 entropy(breeze) =0.722
风力情况为 no wind 时
熵值为 entropy(no wind) = 0.811
风力情况为 gale 时，熵值为 entropy(gale) = 0.918
总的风力熵值为：
5/12 * 0.722 + 4/12 * 0.811 + 3/12 * 0.918 = 0.801
显然通过计算我们发现，在风力分类的情况下，赖床的熵值降低了，说明什么呢？
说明我们的信息混乱程度降低了
以同样的计算方式，我们可以求出另外两个属性的信息熵：
H(季节) = 0.56
H(是否过 8 点) = 0.748
显然通过发现
0.56<0.748<0.801
季节<是否过8点<风力
很明显，信息增益最大的是季节这个属性
通过遍历既可以算出不同属性的增益情况
即可以得到如下决策树图
四.过拟合和欠拟合
剪枝，即减少树的高度就是为了解决过拟合
从而降低噪音对数据分类的影响
而剪枝又分两种方法，预剪枝干，和后剪枝。这两种方法其实还是蛮好理解的，一种是自顶向下，一种是自底向上。我们分别来看看。
预剪枝
预剪枝其实你可以想象成是一种自顶向下的方法。在构建过程中，我们会设定一个高度，当达构建的树达到那个高度的时候呢，我们就停止建立决策树，这就是预剪枝的基本原理。
后剪枝
后剪枝呢，其实就是一种自底向上的方法。它会先任由决策树构建完成，构建完成后呢，就会从底部开始，判断哪些枝干是应该剪掉的。
注意到预剪枝和后剪枝的最大区别没有，预剪枝是提前停止，而后剪枝是让决策树构建完成的，所以从性能上说，预剪枝是会更块一些，后剪枝呢则可以更加精确。
决策树优缺点
优点:
(1)速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词.
(2)准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则.
(3)可以处理连续和种类字段
(4)不需要任何领域知识和参数假设
(5)适合高维数据
缺点:
(1)对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征
(2)容易过拟合
(3)忽略属性之间的相关性
五.决策树的实际应用
DecisionTreeClassifier(criterion="gini",
splitter="best",
max_depth=None,
min_samples_split=2,
min_samples_leaf=1,
min_weight_fraction_leaf=0.,
max_features=None,
random_state=None,
max_leaf_nodes=None,
min_impurity_decrease=0.,
min_impurity_split=None,
class_weight=None,
presort=False)
参数含义：
1.criterion:string, optional (default="gini")
(1).criterion='gini',分裂节点时评价准则是Gini指数。
(2).criterion='entropy',分裂节点时的评价指标是信息增益。
2.max_depth:int or None, optional (default=None)。指定树的最大深度。
如果为None，表示树的深度不限。直到所有的叶子节点都是纯净的，即叶子节点
中所有的样本点都属于同一个类别。或者每个叶子节点包含的样本数小于min_samples_split。
3.splitter:string, optional (default="best")。指定分裂节点时的策略。
(1).splitter='best',表示选择最优的分裂策略。
(2).splitter='random',表示选择最好的随机切分策略。
4.min_samples_split:int, float, optional (default=2)。表示分裂一个内部节点需要的做少样本数。
(1).如果为整数，则min_samples_split就是最少样本数。
(2).如果为浮点数(0到1之间)，则每次分裂最少样本数为ceil(min_samples_split * n_samples)
5.min_samples_leaf: int, float, optional (default=1)。指定每个叶子节点需要的最少样本数。
(1).如果为整数，则min_samples_split就是最少样本数。
(2).如果为浮点数(0到1之间)，则每个叶子节点最少样本数为ceil(min_samples_leaf * n_samples)
6.min_weight_fraction_leaf:float, optional (default=0.)
指定叶子节点中样本的最小权重。
7.max_features:int, float, string or None, optional (default=None).
搜寻最佳划分的时候考虑的特征数量。
(1).如果为整数，每次分裂只考虑max_features个特征。
(2).如果为浮点数(0到1之间)，每次切分只考虑int(max_features * n_features)个特征。
(3).如果为'auto'或者'sqrt',则每次切分只考虑sqrt(n_features)个特征
(4).如果为'log2',则每次切分只考虑log2(n_features)个特征。
(5).如果为None,则每次切分考虑n_features个特征。
(6).如果已经考虑了max_features个特征，但还是没有找到一个有效的切分，那么还会继续寻找
下一个特征，直到找到一个有效的切分为止。
8.random_state:int, RandomState instance or None, optional (default=None)
(1).如果为整数，则它指定了随机数生成器的种子。
(2).如果为RandomState实例，则指定了随机数生成器。
(3).如果为None，则使用默认的随机数生成器。
9.max_leaf_nodes: int or None, optional (default=None)。指定了叶子节点的最大数量。
(1).如果为None,叶子节点数量不限。
(2).如果为整数，则max_depth被忽略。
10.min_impurity_decrease:float, optional (default=0.)
如果节点的分裂导致不纯度的减少(分裂后样本比分裂前更加纯净)大于或等于min_impurity_decrease，则分裂该节点。
加权不纯度的减少量计算公式为：
min_impurity_decrease=N_t / N * (impurity - N_t_R / N_t * right_impurity
- N_t_L / N_t * left_impurity)
其中N是样本的总数，N_t是当前节点的样本数，N_t_L是分裂后左子节点的样本数，
N_t_R是分裂后右子节点的样本数。impurity指当前节点的基尼指数，right_impurity指
分裂后右子节点的基尼指数。left_impurity指分裂后左子节点的基尼指数。
11.min_impurity_split:float
树生长过程中早停止的阈值。如果当前节点的不纯度高于阈值，节点将分裂，否则它是叶子节点。
这个参数已经被弃用。用min_impurity_decrease代替了min_impurity_split。
12.class_weight:dict, list of dicts, "balanced" or None, default=None
类别权重的形式为{class_label: weight}
(1).如果没有给出每个类别的权重，则每个类别的权重都为1。
(2).如果class_weight='balanced'，则分类的权重与样本中每个类别出现的频率成反比。
计算公式为：n_samples / (n_classes * np.bincount(y))
(3).如果sample_weight提供了样本权重(由fit方法提供)，则这些权重都会乘以sample_weight。
13.presort:bool, optional (default=False)
指定是否需要提前排序数据从而加速训练中寻找最优切分的过程。设置为True时，对于大数据集
会减慢总体的训练过程；但是对于一个小数据集或者设定了最大深度的情况下，会加速训练过程。
通常来说，较为重要的参数有：
criterion：用以设置用信息熵还是基尼系数计算。
splitter：指定分支模式
max_depth：最大深度，防止过拟合
min_samples_leaf：限定每个节点分枝后子节点至少有多少个数据，否则就不分枝
5.1 准备数据及读取
数据就是上次说到的赖床特征，
季节 | 时间已过 8 点 | 风力情况 | 要不要赖床
将它存储成 csv 文件
spring,no,breeze,yes
winter,no,no wind,yes
autumn,yes,breeze,yes
winter,no,no wind,yes
summer,no,breeze,yes
winter,yes,breeze,yes
winter,no,gale,yes
winter,no,no wind,yes
spring,yes,no wind,no
summer,yes,gale,no
summer,no,gale,no
autumn,yes,breeze,no
import pandas as pd
from sklearn.feature_extraction import DictVectorizer
from sklearn import tree
from sklearn.model_selection import train_test_split
#pandas 读取 csv 文件，header = None 表示不将首行作为列
data = pd.read_csv('data/laic.csv',header =None)
#指定列
data.columns = ['season','after 8','wind','lay bed']
#sparse=False意思是不产生稀疏矩阵
vec=DictVectorizer(sparse=False)
#先用 pandas 对每行生成字典，然后进行向量化
feature = data[['season','after 8','wind']]
X_train = vec.fit_transform(feature.to_dict(orient='record'))
#打印各个变量
print('show feature\n',feature)
print('show vector\n',X_train)
print('show vector name\n',vec.get_feature_names())
show feature
season after 8 wind
0 spring no breeze
1 winter no no wind
2 autumn yes breeze
3 winter no no wind
4 summer no breeze
5 winter yes breeze
6 winter no gale
7 winter no no wind
8 spring yes no wind
9 summer yes gale
10 summer no gale
11 autumn yes breeze
show vector
[[1. 0. 0. 1. 0. 0. 1. 0. 0.]
[1. 0. 0. 0. 0. 1. 0. 0. 1.]
[0. 1. 1. 0. 0. 0. 1. 0. 0.]
[1. 0. 0. 0. 0. 1. 0. 0. 1.]
[1. 0. 0. 0. 1. 0. 1. 0. 0.]
[0. 1. 0. 0. 0. 1. 1. 0. 0.]
[1. 0. 0. 0. 0. 1. 0. 1. 0.]
[1. 0. 0. 0. 0. 1. 0. 0. 1.]
[0. 1. 0. 1. 0. 0. 0. 0. 1.]
[0. 1. 0. 0. 1. 0. 0. 1. 0.]
[1. 0. 0. 0. 1. 0. 0. 1. 0.]
[0. 1. 1. 0. 0. 0. 1. 0. 0.]]
show vector name
['after 8=no', 'after 8=yes', 'season=autumn', 'season=spring', 'season=summer', 'season=winter', 'wind=breeze', 'wind=gale', 'wind=no wind']
通过DictVectorizer，我们就能够把字符型的数据，转化成0 1的矩阵，方便后面进行运算。额外说一句，这种转换方式其实就是one-hot编码。
5.2决策树训练
#划分成训练集，交叉集，验证集，不过这里我们数据量不够大，没必要
#train_x, test_x, train_y, test_y = train_test_split(X_train, Y_train, test_size = 0.3)
#训练决策树
clf = tree.DecisionTreeClassifier(criterion='gini')
clf.fit(X_train,Y_train)
#保存成 dot 文件，后面可以用 dot out.dot -T pdf -o out.pdf 转换成图片
with open("out.dot", 'w') as f :
f = tree.export_graphviz(clf, out_file = f,
feature_names = vec.get_feature_names())
最后差不多就这个样子了
参考：
https://www.cnblogs.com/listenfwind/p/11310924.html
