Decision Trees 决策树
Created: Apr 14, 2020 5:28 PM
什么是决策树？
决策树以树的结构形式来构建分类或者回归模型。树的决策从根（开始）到叶节点。决策树易于过度拟合，可以使用剪枝来简化模型。
假如我们要编写一个APP 推荐引擎，我们的任务是根据现有的数据，向人们推荐他们最有可能下载的APP，左边的表格是六个人的数据，性别、职业、和他们下载的APP。
我们可以建立下图右边的这样一棵树，先建立一个职业节点，如果是学生那么就推荐Pokemon Go，如果是工作，再创建一个性别的节点，女生推荐whatapp，男生推荐snapchat
另外一个例子是根据考生成绩和平时的成绩来判断学生是否被录取，我们可以用同样的方法来建立一棵树。
树构建算法 Tree construction algorithms
- ID3 用于分类
- C4.5 同于分类
- C5.0 与C4.5相比，内存更少，构建的规则集更小，同时更加准确。
- CART （Classification and Regression Trees）可以用于分类和回归
共同点：都是贪心算法，自上而下(Top-down approach)
区别：属性选择度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)
Entropy 熵
熵是一个物理学概念，如果系统中的粒子有许多可能移动的位置，则系统具有很高的熵，如果系统是刚性，粒子活动低，则系统具有较低的熵。
例如，处于固态、液态、和气态的水具有不同的熵，冰中的分子必须保留在晶格中刚性系统，因此冰的熵低。 水中的分子具有更多的运动位置，因此液态水具有中等
熵。 水蒸气中的分子几乎可以到达所需的任何位置，因此水蒸气具有很高的熵
当一个桶中有m个红球，n个蓝球，我们使用放回抽样是上图的熵是：
Information Gain 信息增益
对于推荐APP的例子，我们现在建立决策树，我们计算信息增益，并选择最大的信息增益。
1、计算类别信息增益为1.46，示的是所有样本中各种类别出现的不确定性之和
2、按性别区分的信息增益
其中1/2指的是按年龄分F占总的样本比例
InformationGain = Entropy - EntropyGender = 1.46-0.92=0.54
3、按职业区分的信息增益
InformationGain = Entropy - EntropyGender = 1.46-0.46=1
职业的信息增益大于性别的信息增益，所以选择职业作为第一个节点
ID3算法
- 树以训练样本的单个结点开始（步骤1）。
- 如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2 和3）。否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的特征（步骤6）。该特征成为该结点的“判定”特征（步骤7）。在算法的该版本中，所有的特征都是分类的，即离散值。连续属性必须离散化。
- 对判定特征的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个特征出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。
- 递归划分步骤仅当下列条件之一成立停止：
(a) 给定结点的所有样本属于同一类（步骤2 和3）。
(b) 没有剩余特征可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。即将给定的结点转换成树叶，并用样本中的多数所在的类标记它。
(c) 分枝test_attribute = a i 没有样本（步骤11）。在这种情况下，以样本中的多数类创建一个树叶（步骤12）
超参数
- 最大深度
- 每次拆分的最小样本数
- 最大特征数
sklearn实现决策树
# Import statements
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
import pandas as pd
import numpy as np
# Read the data.
data = np.asarray(pd.read_csv('data.csv', header=None))
# Assign the features to the variable X, and the labels to the variable y.
X = data[:,0:2]
y = data[:,2]
# 1. Build a decision tree model
# TODO: Create the decision tree model and assign it to the variable model.
model = DecisionTreeClassifier()
# 2. Fit the model to the data
# TODO: Fit the model.
model.fit(X,y)
# 3. Predict using the model
# TODO: Make predictions. Store them in the variable y_pred.
y_pred = model.predict(X)
# 4. Calculate the accuracy of the model
# TODO: Calculate the accuracy and assign it to the variable acc.
acc = accuracy_score(y, y_pred)C4.5算法
由于信息增益偏向于具有大量值的特征，而不是具有少数量值的特征，这些“超级特征”很容易被选为根，从而形成一个很宽大的树，导致表现不佳。我们可以通过使用另一种特征选择方法，即信息增益比，来惩罚具有大量值的特征。
信息增益比是本质是信息增益乘以一个惩罚参数1/SplitInfo(A)，当特征取值较少时SplitInfo(A)较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
缺点：信息增益比偏向取值较少的特征
1、计算SplitInfo(A)
通过计算上边两个特征性别和职业的信息增益率，我们选择信息增益率最大的特征Occupation职业###
CART算法
CART算法是基于基尼系数：样本被选中的概率 * 样本被分错的概率来选择特征
pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)
1、计算性别的Gini系数
2、计算职业的Gini系数
通过计算上边两个特征性别和职业的基尼系数，我们选择Gini系数最小的特征Occupation职业
熵和互信息
平均互信息：已知特征Y的信息而使得对标签X的信息的不确定性减少的程度。
剪枝
一种策略是通过提前停止树的生长来防止树变得非常复杂，有一个问题难以选择合适的阈值。另外一种策略是先构建一颗完整的树，然后将其修剪回更简单的形式，删除不重要的分支，修剪后用叶子节点替换子树。
决策树的优势
- 易于理解和解释
决策树是“白盒”模型。决策树能够产生“可理解的”规则。树木也可以可视化。相反，在黑匣子模型中（例如，在神经网络，随机森林中），通常很难用简单的术语来解释为什么做出预测。
- 建立决策树需要很少的数据准备
决策树可以处理合理数量的缺失值； 决策树对异常值也不敏感。 相比之下，其他算法通常需要对数据进行规范化，需要创建伪变量并删除空白值。
- 决策树能够处理连续变量和分类变量。
其他技术通常专用于分析仅具有一种变量类型的数据集。能够处理多输出问题。
- 隐式执行功能选择
例如，决策树（例如CART）具有内置的机制来执行特征选择。决策树清楚地表明了哪些字段对于预测或分类最重要
决策树的缺点
- 易于过拟合
很可能构建过于发杂的树，导致模型表现不佳
- 在数据不平衡的情况下创建偏倚树，建议在拟合之前平衡数据集
- 不稳定
因为数据中的细微变化可能会导致生成完全不同的树。通过在集成中使用决策树可以缓解此问题。随机森林可以通过对许多树木进行平均预测来限制这种不稳定性。
- 决策树使用的贪婪方法不能保证最佳解决方案贪婪算法无法在每个节点上做出局部最优决策，因此无法保证返回全局最优决策树。这可以通过训练多棵树来缓解，其中通过替换随机抽取特征和样本
参考：[https://www.cnblogs.com/muzixi/p/6566803.html]