决策树一般分为三步：特征划分，树生成，树剪枝
基本概念(特征划分)
熵：表示随机变量的不确定性
- X是一个取有限个值的离散随机变量，其概率分布为$P(X=x_i)=p_i, i=1,2,..,n$
- 熵定义为$H(X)=-\sum_{i=1}^np_ilogp_i$
- 又定义可知，熵只依赖于X的分布，而与X的取值无关
条件熵
- 条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y 的不确定性，也就是给定随机变量X的条件下Y的条件熵
- 定义为：$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$
信息增益
- 表示得知特征X的信息而使得类Y的信息不确定性减少的程度
- 特征A对心里数据集D的信息增益定义为：$g(D,A)=H(D)-H(D|A)$
- 个人理解为不确定性的减少量
信息增益比
- 以信息增益作为划分数据集的特征，存在偏向于选择取值较多的特征的问题
- $g_R(D,A)=\frac{g(D,A)}{H_A(D)}$其中$H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{D}log_2\frac{|D_i|}{D}$,n是特征A取值的个数
树生成
就是根据特征选择来区分
- ID3:使用的信息增益进行特征划分
- C4.5:使用信息增益比进行特征的划分
树剪枝
- 生成树一般按照局部最优原则生成，容易过拟合
剪枝（pruning）是决策树学习算法对付”过拟合“的主要手段。
决策树剪枝的基本策略有”预剪枝“（prepruning）和”后剪枝“（post-pruning）
- 预剪枝是指在决策树生成过程中，对每个节点在划分前进行估计，若当前的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点
- 后剪枝是先从训练集生成一颗完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点
剪枝处理降低了”过拟合“风险，但也带来了”欠拟合“的风险。
- 一般情形下，后剪枝决策树欠拟合风险较小，泛化性能往往优于预剪枝决策树
- 但后剪枝训练开销比未剪枝决策树和预剪枝决策树都要大很多
CART(classification and regression tree)算法
- CART是在给定输入随机变量X的条件下输出随机变量Y 的条件概率分布的学习方法，分类回归树即可以用于分类，也可以用于回归
CART决策树的生成
- 回归树：使用平方误差最小化的准则进行特征选择
- 启发式方法(即随机选择第j个变量和它的取值进行划分),遍历特征和各个特征的取值
- 分类树：使用基尼指数(Gini index)(和熵类似)
- 假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)$
- 如果样本集合D根据特征A是否取某一可能值a被分割为$D_1和D_2$两部分，则在特征A的条件下，集合D的基尼指数定义为$Gini(D,A)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2)$
- 基尼指数Gini(D)表示集合D的不确定性
- 基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性，基尼指数越大，样本集合的不确定性也就越大，这个和熵比类似
CART决策树的剪枝
- 用验证数据集对已生成的数进行剪枝并选择最优子树，这时是用的损失函数最小作为剪枝的标准
小结
