核心划分点选择 输出值确定。一、概述决策树是一种基本的分类与回归方法本文叙述的是回归部分。回归决策树主要指CART(classification and regression tree)算法内部结点特征的取值为“是”和“否” 为二叉树结构。所谓回归就是根据特征向量来决定对应的输出值。回归树就是将特征空间划分成若干单元每一个划分单元有一个特定的输出。因为每个结点都是“是”和“否”的判断所以划分的边界是平行于坐标轴的。对于测试数据我们只要按照特征将其归到某个单元便得到对应的输出值。【例】左边为对二维平面划分的决策树右边为对应的划分示意图其中c1,c2,c3,c4,c5是对应每个划分单元的输出。如现在对一个新的向量(6,6)决定它对应的输出。第一维分量6介于5和8之间第二维分量6小于8根据此决策树很容易判断(6,6)所在的划分单元其对应的输出值为c3.划分的过程也就是建立树的过程每划分一次随即确定划分单元对应的输出也就多了一个结点。当根据停止条件划分终止的时候最终每个单元的输出也就确定了也就是叶结点。二、回归树建立既然要划分切分点怎么找输出值又怎么确定这两个问题也就是回归决策树的核心。[切分点选择最小二乘法]; [输出值单元内均值].1.原理假设X和Y分别为输入和输出变量并且Y是连续变量给定训练数据集为 D{(x1,y1),(x2,y2),...,(xN,yN)} 其中为输入实例(特征向量)n为特征个数i1,2,...,N, N为样本容量。对特征空间的划分采用启发式方法每次划分逐一考察当前集合中所有特征的所有取值根据平方误差最小化准则选择其中最优的一个作为切分点。如对训练集中第j个特征变量和它的取值s作为切分变量和切分点并定义两个区域和为找出最优的 j 和 s 对下式求解(1.1)也就是找出使要划分的两个区域平方误差和最小的 j 和 s .其中 c1 , c2 为划分后两个区域内固定的输出值方括号内的两个min意为使用的是最优的 c1 和 c2 也就是使各自区域内平方误差最小的c1和 c2 易知这两个最优的输出值就是各自对应区域内Y的均值所以上式可写为现证明一维空间中样本均值是最优的输出值平方误差最小找到最优的切分点(j,s)后依次将输入空间划分为两个区域接着对每个区域重复上述划分过程直到满足停止条件为止。这样就生成了一棵回归树这样的回归树通常称为最小二乘回归树。2. 算法叙述输入训练数据集D输出回归树f(x).在训练数据集所在的输入空间中递归地将每个区域划分为两个子区域并决定每个子区域上的输出值构建二叉决策树(1) 选择最优切分变量j与切分点s求解遍历变量 j 对固定的切分变量 j 扫描切分点 s 选择使上式达到最小值的对 (j,s) .(2) 用选定的对 (j,s) 划分区域并决定相应的输出值(3) 继续对两个子区域调用步骤(1),(2)直至满足停止条件.(4) 将输入空间划分为M个区域 R1,R2,...,RM 生成决策树三、示例下表为训练数据集特征向量只有一维根据此数据表建立回归决策树。 (1) 选择最优切分变量j与最优切分点s在本数据集中只有一个特征变量最优切分变量自然是x。接下来考虑9个切分点 {1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5} 切分变量两个相邻取值区间 [ai,ai1) 内任一点均可根据式(1.2)计算每个待切分点的损失函数值损失函数为同式(1.2)a. 计算子区域输出值同理得到其他各切分点的子区域输出值列表如下b. 计算损失函数值找到最优切分点当s1.5时同理计算得到其他各切分点的损失函数值列表如下易知取s6.5时损失函数值最小。因此第一个划分点为(jx,s6.5).(2) 用选定的对(j,s)划分区域并决定相应的输出值划分区域为 R1{1,2,3,4,5,6} R2{7,8,9,10}对应输出值 c16.24 c28.91(3) 调用步骤(1),(2)继续划分对 R1 取切分点 {1.5,2.5,3.5,4.5,5.5} 计算得到单元输出值为损失函数值为L(3.5)最小取s3.5为划分点。后面同理。(4) 生成回归树假设两次划分后即停止则最终生成的回归树为四、Python实现对第三部分例子的python实现及与线性回归对比。(来自https://github.com/KARL13YAN/learning/blob/master/regression%20tree.py)import numpy as np import matplotlib.pyplot as plt from sklearn.tree import DecisionTreeRegressor from sklearn import linear_model # Data set x np.array(list(range(1, 11))).reshape(-1, 1) y np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05]).ravel() # Fit regression model model1 DecisionTreeRegressor(max_depth1) model2 DecisionTreeRegressor(max_depth3) model3 linear_model.LinearRegression() model1.fit(x, y) model2.fit(x, y) model3.fit(x, y) # Predict X_test np.arange(0.0, 10.0, 0.01)[:, np.newaxis] y_1 model1.predict(X_test) y_2 model2.predict(X_test) y_3 model3.predict(X_test) # Plot the results plt.figure() plt.scatter(x, y, s20, edgecolorblack, cdarkorange, labeldata) plt.plot(X_test, y_1, colorcornflowerblue, labelmax_depth1, linewidth2) plt.plot(X_test, y_2, coloryellowgreen, labelmax_depth3, linewidth2) plt.plot(X_test, y_3, colorred, labelliner regression, linewidth2) plt.xlabel(data) plt.ylabel(target) plt.title(Decision Tree Regression) plt.legend() plt.show()
