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

其中,c 1 , c 2 c_{1}, c_{2} c1?,c2? 为划分后两个区域内固定的输出值, 方括号内的两个min ? \min min 意为使用的是最优的c 1 c_{1} c1? 和c 2 c_{2} c2?, 也就是使各自区域内平方误差最小的c 1 c_{1} c1? 和c 2 c_{2} c2?, 易知这两个最优的输出值就是各自对应区域内Y Y Y 的均值, 所以上式可写为
min ? j , s [ ∑ x i ∈ R 1 ( j , s ) ( y i ? c 1 ^ ) 2 + ∑ x i ∈ R 2 ( j , s ) ( y i ? c 2 ^ ) 2 ] \min _{j, s}\left[\sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-\{c_{1}}\right)^{2}+\sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-\{c_{2}}\right)^{2}\right] j,smin????xi?∈R1?(j,s)∑?(yi??c1??)2+xi?∈R2?(j,s)∑?(yi??c2??)2???
其中C 1 ^ = 1 N 1 ∑ x i ∈ R 1 ( j , s ) y i , c 2 ^ = 1 N 2 ∑ x i ∈ R 2 ( j , s ) y i \{C_{1}}=\frac{1}{N_{1}} \sum_{x_{i} \in R_{1}(j, s)} y_{i}, \{c_{2}}=\frac{1}{N_{2}} \sum_{x_{i} \in R_{2}(j, s)} y_{i} C1??=N1?1?∑xi?∈R1?(j,s)?yi?,c2??=N2?1?∑xi?∈R2?(j,s)?yi?.
现证明一维空间中样本均值是最优的输出值 (平方误差最小):
给定一个随机数列{ x 1 , x 2 , … , x n } \left\{x_{1}, x_{2}, \ldots, x_{n}\right\} {x1?,x2?,…,xn?}, 设该空间中最优的输出值为a a a, 根据最小平方误差准则, 构造a a a 的函数如下:
F ( a ) = ( x 1 ? a ) 2 + ( x 2 ? a ) 2 + ? + ( x n ? a ) 2 \{F}(\{a})=\left(x_{1}-a\right)^{2}+\left(x_{2}-a\right)^{2}+\cdots+\left(x_{n}-a\right)^{2} F(a)=(x1??a)2+(x2??a)2+?+(xn??a)2
考察其单调性,
F ′ ( a ) = ? 2 ( x 1 ? a ) ? 2 ( x 2 ? a ) + ? ? 2 ( x n ? a ) = 2 n a ? 2 ∑ i = 1 n x i F^{\prime}(a)=-2\left(x_{1}-a\right)-2\left(x_{2}-a\right)+\cdots-2\left(x_{n}-a\right)=2 n a-2 \sum_{i=1}^{n} x_{i} F′(a)=?2(x1??a)?2(x2??a)+??2(xn??a)=2na?2i=1∑n?xi?
令F ′ ( a ) = 0 F^{\prime}(a)=0 F′(a)=0 得,a = 1 n ∑ i = 1 n x i a=\frac{1}{n} \sum_{i=1}^{n} x_{i} a=n1?∑i=1n?xi?
根据其单调性, 易知a ^ = 1 n ∑ i = 1 n x i \hat{a}=\frac{1}{n} \sum_{i=1}^{n} x_{i} a^=n1?∑i=1n?xi? 为最小值点.证毕.
找到最优的切分点( j , s ) (j, s) (j,s) 后, 依次将输入空间划分为两个区域, 接着对每个区域重复上述划分过程, 直到满足停止条件为止.这样就生成了一棵回归树, 这样的回归树通常称为最小二乘回归树.
2. 算法叙述
输入: 训练数据集 D;
输出: 回归树f ( x ) f(x) f(x).
在训练数据集所在的输入空间中, 递归地将每个区域划分为两个子区域并决定每个子区域上的输出值, 构建二叉决策树:
(1) 选择最优切分变量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, 对固定的切分变量j \{j} j 扫描切分点s \{s} s, 选择使上式达到最小值的对( j , s ) (j, s) (j,s).
(2) 用选定的对( j , s ) (j, s) (j,s) 划分区域并决定相应的输出值:
c m ^ = 1 N m ∑ x i ∈ R m ( j , s ) y i , x ∈ R m , m = 1 , 2 \{c_{m}}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}, \quad \{x} \in R_{m}, \{~m}=1,2 cm??=Nm?1?xi?∈Rm?(j,s)∑?yi?,x∈Rm?,m=1,2
其中,R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } , R 2 ( j , s ) = { x ∣ x ( j ) > s } R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\}, R_{2}(j, s)=\left\{x \mid x^{(j)}>s\right\} R1?(j,s)={x∣x(j)≤s},R2?(j,s)={x∣x(j)>s}.
(3) 继续对两个子区域调用步骤(1),(2), 直至满足停止条件.
(4) 将输入空间划分为M M M 个区域R 1 , R 1 , … , R M R_{1}, R_{1}, \ldots, R_{M} R1?,R1?,…,RM?, 生成决策树:
f ( x ) = ∑ m = 1 M c m ^ I ( x ∈ R m ) \{f}(\{x})=\sum_{m=1}^{M} \{c_{m}} I\left(x \in R_{m}\right) f(x)=m=1∑M?cm??I(x∈Rm?)