现实世界中最强大的机器学习算法。训练实例可以表示为键值对，且分类目标具有离散的输出值时，特别适合决策树学习。
几乎不需要数据预处理，根本不需要特征缩放或居中
决策树（Decision Tree，DT）是树模型系列的根基模型，后续的随机森林（RF）、提升树（Boosting Tree）、梯度提升树（GBDT）、XGBoost都是在其基础上演化而来，是机器学习基础模型。

信息论基础

定长编码与变长编码

定长编码(Block Codes)：将猫、狗、鱼、鸟四种信息编码为：00 01 10 11 。

变长编码(Variable Codes)：考虑到不同的信息出现的频率不同，有的出现频率高，有的出现频率底，为了节约整体编码长度。将出现频率高的字符使用短编码，出现频率低的字符使用长编码。编码为：0 , 10 , 110 , 111 假设这四条信息的频率分布为：$\frac{1}{2}$, $\frac{1}{4}$,$\frac{1}{8}$,$\frac{1}{8}$。
那么对于定长编码，每个字的平均编码长度为：

$$ L(x) = 2 \times \frac{1}{2} + 2 \times \frac{1}{4} + 2 \times \frac{1}{8} + 2 \times \frac{1}{8} =2 $$

变长编码的平均编码长度为：

$$ L(x) = 1 \times \frac{1}{2} + 2 \times \frac{1}{4} + 3 \times \frac{1}{8} + 3 \times \frac{1}{8} =1.75 $$

无损编码

问题：按上面的变长编码的码表，有信息代号：001110 ，有多种解释。
引入无损编码的概念：使压缩的数据能够无损的复原为原始数据
无损编码需要的特点有：

非奇异：$x_1 \not= x_2 \Rightarrow C(x_1) \not= C(x_2) $
可扩展：$C(x_1,...,x_n) = C(x_1)...C(x_n) $
唯一可译：$x_i ^n \not= x_j ^m \Rightarrow C(x_i^n) \not= C(x_j^m) $

这还不够，仍然没有解决信息重复的问题。
引入前缀编码方案：
即任意符号的编码都不是其他编码的前缀：

$$ x_1 \not= x_2 \Rightarrow C(x_1) \not= Prefix(C(x_2)) $$

基于前缀编码，C(x)是：

x	1	2	3	4
C(x)	0	10	110	111

这样就没有歧义了。

最优编码

限定：源符号有限且已知的编码。

code

经数学求解，得最优编码长度为：$log_r \frac{1}{p_i}$

以上内容参考了csdn博客，博客链接见文末。

信息熵

熵（entropy）的概念起源于热力学，表示分子混乱的程度，后来这个概念被推广至各领域，现在熵的概念有多种解释，这里仅介绍信息论的解释。
熵的减少通常称为信息增益（information gain），即信息不确定度的减少。决策树可以看作是将无序的数据变得更加有序的过程。
信息增益公式：

$$ Gain(D,A) = H(D) - H(D|A) $$

H(D) : 熵（D的不确定性）
H(D|A) ：条件熵（在A的条件下，D的不确定度）

给定C个分类，对于属性a来说，如果在所有例子中，它都拥有值v，那么它的熵E可以定义为：

$$ E(a=v) = \sum_{i=1}^{C}-p_i log_2 p_i $$

其中$p_i$是在第$i$类中属性$a$取值为v的概率。
假设在传输信息时，每条信息都是来自于集合 { a, b, c, d, e, f, g, h } 的一个字符，该集合存在8个不同的对象，为了表示这8个不同的对象，需要用3位二进制，即 { 000 , 010 , 100 , 001 , 110 , 101 , 011 , 111 } 。这样每条信息所需要的平均位数就是3，有：

$$E= \sum_{i=1}^{8} \frac{1}{8} log_2 \frac{1}{8} =3$$

没有其他任何信息的情况下，通常假定所有信息发生的可能性都相同$\frac{1}{8}$如果信息发生的频率不同，那么较短的位串就用来表示最频繁发生的那些信息，这就是上文介绍的编码与最优编码问题。
信息增益定义：

$$ Gain(T,A)=E(T) - \sum_{j=1}^{v} \frac{ \vert T_j \vert }{ \vert T \vert} E(T_j) $$

其中，$T$是训练例子集合，$T_j$是属性A取值为j的训练例子集合，为$T$的一个子集

示例

信息增益比

信息增益比(information gain radio)，也称信息增益率。

$$ Gain_{Ratio} (D,A) = \frac{Gain(D,A)}{H_A (d)} \\ 其中 H_A(D) = - \sum_{i=1}^{n} \frac{ \vert D_i \vert }{ \vert D \vert } log_2\frac{ \vert D_i \vert }{ \vert D \vert } ，n是特征值A的取值个数 $$

基尼系数

基尼系数（Gini index）表示随机取样的两个样本不一致的概率。基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。
分类问题中，假设有M个类别，第k类的概率为$p_k$ 基尼系数的公式为：

$$ Gini(p) = \sum_{k=1}^{M} p_k (1-p_k) = 1- \sum_{k=1}^{M}p_k^2 $$

决策树原理

关于决策树

决策树算法的历史

第一个决策算法（E.B.Hunt）：CLS
使决策树受到关注，成为机器学习主流技术的算法（J.R.Quinlan）：ID3
最常用的决策树算法（J.R.Quinlan）：C4.5
既可以分类可以用于回归任务的决策树算法：CART（Classfication and regression tree），从统计建模的角度出发考虑问题，前面都是用过信息论角度去考虑
基于决策树的最强大算法之一：Random Forest

3种典型决策树算法：ID3、C4.5、CART

ID3算法（Quinlan，1986，Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。
ID3决策树的特征选择标准是信息增益，但偏向于取值较多的特征。

介绍

伪代码

C4.5决策树的特征选择标准是信息增益比，但偏向于取值较少的特征。ID3和C4.5算法生成的决策树是多叉树，只能处理分类不能处理回归。

CART决策树

CART决策树,分类与回归树（Classification and regression tree，CART）,也称为“增长树”。
（1）CART是一棵二叉树；
（2）CART既能是分类树，又能是回归树，由目标任务决定；
（3）当CART是分类树时，采用基尼不纯度 (GINI) 作为结点分裂的依据；当CART是回归树时，采用MSE(均方误差)作为结点分裂的依据。

ID3中使用了信息增益选择特征，增益大优先选择。C4.5中，采用信息增益率选择特征，减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数选择特征，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）相反。

首先使用单个特征k和阈值$t_k$（例如，“花瓣长度”≤2.45cm”）将训练集分为两个子集。如何选择k和$t_k$它搜索产生最纯子集（按其大小加权）的一对（k，$t_k$）?

有最小化成本函数：

$$ J(k,t_k) = \frac{m_{left}}{m}G_{left} + \frac{m_{right}}{m}G_right $$

其中：

$$ \begin{cases} G_{left/right} 是左右子集的不纯度 \\ m_{left/right} 是左右子集的实例数量（样本数量） \end{cases} $$

不幸的是，寻找最优树是一个已知的 NP完全问题。时间复杂度$o(exp(m))$，即使是很小的数据集，也很棘手。

回归

$$ J(k,t_k) = \frac{m_{left}}{m}MSE_{left} + \frac{m_{right}}{m}MSE_right $$

其中：

$$ \begin{cases} MSE_{node} = \sum_{i \in node }( \hat{y}_{node} - y^{(i)})^2 \\ \hat{y}_{node} = \frac{\sum_{i \in node } y^{(i)}}{m_{node}} \end{cases} $$

演化

程序实现

先看一个简单的：

python


from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier , plot_tree
X, y = load_iris(return_X_y=True)
tree_clf = DecisionTreeClassifier()
tree_clf.fit(X,y)
plot_tree(tree_clf)

看看函数原型
class sklearn.tree.DecisionTreeClassifier(*, criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, class_weight=None, ccp_alpha=0.0)
重点参数：
参数 criterion {“gini”, “entropy”, “log_loss”}, default=”gini”
当criterion取值为“gini”时采用基尼不纯度（Gini impurity）算法构造决策树，当criterion取值为 “entropy” 时采用信息增益（ information gain）算法构造决策树。默认采用基尼不纯度测量。

参数 splitter {“best”, “random”}, default=”best”
此参数决定了在每个节点上拆分策略的选择。支持的策略是“best” 选择“最佳拆分策略”， “random” 选择“最佳随机拆分策略”。

参数 max_depth int, default=None
树的最大深度。如果取值为None,则将所有节点展开，直到所有的叶子都是纯净的或者直到所有叶子都包含少于min_samples_split个样本。
减小max_depth可使模型正则化，从而降低过拟合的风险。
其他参数：min_samples_split（分裂前节点必须有的最小样本数）、min_samples_leaf（叶节点必须有的最小样本数量）、min_weight_fraction_leaf（与min_samples_leaf一样，但表现为加权实例总数的占比）、max_leaf_nodes（最大叶节点数量），以及max_features（分裂每个节点评估的最大特征数量）。增大超参数min_ 或减小max_ 将使模型正则化。

Scikit-Learn使用分类和回归树（Classification and Regression Tree，CART）算法来训练决策树（也称为“增长树”）。

决策树回归

CART算法的工作原理与以前的方法大致相同，不同之处在于，它不再尝试以最小化不纯度的方式来拆分训练集，而是以最小化MSE 的方式来拆分训练集。
就像分类任务一样，决策树在处理回归任务时容易过拟合。 class sklearn.tree.DecisionTreeRegressor(*, criterion='mse', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, presort='deprecated', ccp_alpha=0.0)

官方例程：