一、决策树
决策树（decision tree）是一种基本的分类与回归方法，本篇主要讨论用于分类的决策树。
1.决策树模型
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶节点（leaf node）。内部结点表示一个特征或属性，叶节点表示一个类。
下图为一个决策树的示意图，图中圆和方框分别表示内部结点和叶节点。
2.特征选择
如何选择特征？即需要确定选择特征的准则。如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有更好的分类，那么就更应该选择这个特征。
2.1 熵
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个有限的离散随机变量，其概率分布为
egin{align}
otag
P(X=x_{i})=p_{i}, i=1,2,...,n
end{align}
则随机变量X的熵定义为
egin{align}
otag
H(X)=-sum_{i=1}^{n}p_{i} extrm{log}p_{i}
end{align}
上式中，对数以2为底或以e为底。如有0概率，定义0log0=0。由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记作H(p)，即
egin{align}
otag
H(p)=-sum_{i=1}^{n}p_{i} extrm{log}p_{i}
end{align}
熵越大，随机变量的不确定性就越大。
2.2 条件熵
条件熵（conditional entropy）H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。
设有随机变量(X,Y)，其联合概率分布为
egin{align}
otag
P(X=x_{i},Y=y_{j})=p_{ij},i=1,2,...,n; j=1,2,...,m
end{align}
随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
egin{align}
otag
H(Y|X)=sum_{i=1}^{n}p_{i}H(Y|X=x_{i})
end{align}
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。
2.3 信息增益
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
egin{align}
otag
g(D,A)=H(D)-H(D|A)
end{align}
信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。
对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。
2.4 信息增益比
在训练数据集的经验熵大的时候，信息增益值会偏大，反之，信息增益值会偏小。使用信息增益比（information gain ratio）可以对这一问题进行校正。
特征A对训练数据集D的信息增益比定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比：
egin{align}
otag
g_{R}(D,A)=frac{g(D,A))}{H(D)}
end{align}
2.5 基尼指数
假设有K个类，样本点属于第k类的概率为Pk，则概率分布的基尼指数定义为
egin{align}
otag
Gini(p)=sum_{k=1}{K}p_{k}(1-p_{k})=1-sum_{k=1}{K}p_{k}^{2}
end{align}
对于给定的样本集合D，其基尼指数为
egin{align}
otag
Gini(D)=1-sum_{k=1}^{K}left ( frac{|C_{k}|}{|D|}
ight )^{2}
end{align}
如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即
egin{align}
otag
D_{1}= lbrace(x,y)in D|A(x)=a
brace,D_{2}=D-D_{1}
end{align}
则在特征A的条件下，集合D的基尼指数定义 为
egin{align}
otag
Gini(D,A)=frac{|D_{1}|}{|D|}Gini(D_{1})+frac{|D_{2}|}{|D|}Gini(D_{2})
end{align}
基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大。
3.树的生成
3.1 ID3
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。
具体方法是：
- 从根结点（root node）开始，对结点计算所有可能特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；
- 再对子结点递归地调用以上方法，构建决策树
- 直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树。
3.2 C4.5
C4.5算法对ID3算法进行了改进，使用信息增益比来选择特征。
3.3 CART
CART（classification and regression tree）决策树使用基尼指数来选择特征。
CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支的取值为“是”，右分支的取值为“否”。这样的决策树等价于递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法由以下两步组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
4.树的剪枝
在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning），剪枝是决策树学习算法对付过拟合的主要手段。
剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化模型。
决策树剪枝的基本策略有预剪枝（prepruning）和后剪枝（post-pruning）。
- 预剪枝是指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。
- 后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
二、随机森林
1.简介
随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于集成学习（Ensemble Learning）方法。
集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。
2.原理
2.1 算法流程
- 训练总样本数为N，有放回地从N个训练集中随机抽取n个作为此单颗树的训练样本；
- 训练样例的输入特征的个数为M，从M个输入特征里随机选择m个输入特征，m<<M，建立决策树；
- 每棵树都尽可能地生长，不需要剪枝。
2.2 结果判定
- 目标特征为数字类型：取t个决策树的平均值作为分类结果。
- 目标特征为类别类型：少数服从多数，取单棵树分类结果最多的那个类别作为整个随机森林的分类结果。
3.优点
- 在当前所有算法中，具有极好的准确率
- 能够有效地运行在大数据集上
- 能够处理具有高维特征的输入样本，而且不需要降维
- 能够评估各个特征在分类问题上的重要性
- 对于缺省值问题也能够获得很好得结果
三、python实现
利用scikit-learn模块来实现决策树和随机森林，代码如下。
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
# 实例化数据集
dc = load_breast_cancer()
# 划分训练集和测试集
x_train, x_test, y_train, y_test = train_test_split(dc.data,dc.target,test_size=0.25)
# 决策树进行预测
dt = DecisionTreeClassifier()
dt.fit(x_train, y_train)
print("决策树预测准确率为：", dt.score(x_test, y_test))
# 随机森林进行预测
rf = RandomForestClassifier(n_estimators=120, n_jobs=2)
rf.fit(x_train, y_train)
print("随机森林预测准确率为：", rf.score(x_test,y_test))
输出结果如下。
心满意足享受每一点快乐，是走向幸福的唯一途径。——《樱桃小丸子》