问题一: 机器学习的基本流程( 七 ) _机器学习

■ 后剪枝
后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝.剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断.同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝.相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大.
常见的后剪枝方法包括错误率降低剪枝（ Error ，REP）、悲观剪枝（ Error ，PEP）、代价复杂度剪枝（Cost，CCP）、最小误差剪枝（ Error ，MEP）、CVP（ Value ）、OPP（）等方法.
下面通过决策树一回归举例
核心: 划分点选择 + 输出值确定.
一、概述
决策树是一种基本的分类与回归方法, 本文叙述的是回归部分.回归决策树主要指 CART ( andtree)算法, 内部结点特征的取值为 “是”和“否”, 为二叉树结构.
所谓回归, 就是根据特征向量来决定对应的输出值.回归树就是将特征空间划分成若干单元, 每一个划分单元有一个特定的输出.因为每个结点都是“是”和“否”的判断, 所以划分的边界是平行于坐标轴的.对于测试数据, 我们只要按照特征将其归到某个单元, 便得到对应的输出值.
【例】左边为对二维平面划分的决策树, 右边为对应的划分示意图, 其中c 1 , c 2 , c 3 , c 4 , c 5 c_{1}, c_{2}, c_{3}, c_{4}, c_{5} c1?,c2?,c3?,c4?,c5? 是对应每个划分单元的输出.
比如现在对一个新的向量( 6 , 6 ) (6,6) (6,6) 决定它对应的输出.第一维分量 6 介于 5 和 8 之间, 第二维分量 6 小于 8 , 根据此决策树很容易判断( 6 , 6 ) (6,6) (6,6) 所在的划分单元, 其对应的输出值为c 3 c_{3} c3?.
划分的过程也就是建立树的过程, 每划分一次, 随即确定划分单元对应的输出, 也就多了一个结点.当根据停止条件划分终止的时候, 最终每个单元的输出也就确定了, 也就是叶结点.
二、回归树建立
既然要划分, 切分点怎么找? 输出值又怎么确定? 这两个问题也就是回归决策树的核心.
[切分点选择: 最小二乘法]; [输出值: 单元内均值].
1. 原理
假设X \{X} X 和Y \{Y} Y 分别为输入和输出变量, 并且Y \{Y} Y 是连续变量, 给定训练数据集为D = \{D}= D={ ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } \left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\} {(x1?,y1?),(x2?,y2?),…,(xN?,yN?)}, 其中x i = ( x i ( 1 ) , x i ( 2 ) , … , x i ( n ) ) x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right) xi?=(xi(1)?,xi(2)?,…,xi(n)?) 为输入实例(特征向量),n \{n} n 为特征个数,i = 1 , 2 , … , N , N \{i}=1,2, \ldots, \{N}, \{N} i=1,2,…,N,N 为样本容量.
对特征空间的划分采用启发式方法, 每次划分逐一考察当前集合中所有特征的所有取值, 根据平方误差最小化准则选择其中最优的一个作为切分点.如对训练集中第j j j 个特征变量x ( j ) x^{(j)} x(j) 和它的取值s s s, 作为切分变量和切分点, 并定义两个区域R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\} R1?(j,s)={x∣x(j)≤s} 和R 2 ( j , s ) = R_{2}(j, s)= R2?(j,s)={ x ∣ x ( j ) > s } \left\{x \mid x^{(j)}>s\right\} {x∣x(j)>s}, 为找出最优的j \{j} j 和s \{s} s, 对下式求解
min ? j , s [ min ? c 1 ∑ x i ∈ R 1 ( j , s ) ( y i ? c 1 ) 2 + min ? c 2 ∑ x i ∈ R 2 ( j , s ) ( y i ? c 2 ) 2 ] \min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right] j,smin????c1?min?xi?∈R1?(j,s)∑?(yi??c1?)2+c2?min?xi?∈R2?(j,s)∑?(yi??c2?)2???
也就是找出使要划分的两个区域平方误差和最小的j j j 和s s s.