决策树 |
您所在的位置:网站首页 › 决策树算法举例 › 决策树 |
核心:划分点选择 + 输出值确定。 一、概述决策树是一种基本的分类与回归方法,本文叙述的是回归部分。回归决策树主要指CART(classification and regression tree)算法,内部结点特征的取值为“是”和“否”, 为二叉树结构。 所谓回归,就是根据特征向量来决定对应的输出值。回归树就是将特征空间划分成若干单元,每一个划分单元有一个特定的输出。因为每个结点都是“是”和“否”的判断,所以划分的边界是平行于坐标轴的。对于测试数据,我们只要按照特征将其归到某个单元,便得到对应的输出值。 【例】左边为对二维平面划分的决策树,右边为对应的划分示意图,其中c1,c2,c3,c4,c5是对应每个划分单元的输出。 如现在对一个新的向量(6,6)决定它对应的输出。第一维分量6介于5和8之间,第二维分量6小于8,根据此决策树很容易判断(6,6)所在的划分单元,其对应的输出值为c3. 划分的过程也就是建立树的过程,每划分一次,随即确定划分单元对应的输出,也就多了一个结点。当根据停止条件划分终止的时候,最终每个单元的输出也就确定了,也就是叶结点。 二、回归树建立既然要划分,切分点怎么找?输出值又怎么确定?这两个问题也就是回归决策树的核心。 [切分点选择:最小二乘法]; [输出值:单元内均值]. 1.原理 假设X和Y分别为输入和输出变量,并且Y是连续变量,给定训练数据集为 对特征空间的划分采用启发式方法,每次划分逐一考察当前集合中所有特征的所有取值,根据平方误差最小化准则选择其中最优的一个作为切分点。如对训练集中第j个特征变量 也就是找出使要划分的两个区域平方误差和最小的 其中, 其中 现证明一维空间中样本均值是最优的输出值(平方误差最小): 给定一个随机数列 考察其单调性, 令 根据其单调性,易知 找到最优的切分点(j,s)后,依次将输入空间划分为两个区域,接着对每个区域重复上述划分过程,直到满足停止条件为止。这样就生成了一棵回归树,这样的回归树通常称为最小二乘回归树。 2. 算法叙述 输入:训练数据集 输出:回归树 在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树: (1) 选择最优切分变量j与切分点s,求解 遍历变量 (2) 用选定的对 其中, (3) 继续对两个子区域调用步骤(1),(2),直至满足停止条件. (4) 将输入空间划分为M个区域 其中 下表为训练数据集,特征向量只有一维,根据此数据表建立回归决策树。 x 1 2 3 4 5 6 7 8 9 10 y 5.56 5.7 5.91 6.4 6.8 7.05 8.9 8.7 9 9.05 (1) 选择最优切分变量j与最优切分点s: 在本数据集中,只有一个特征变量,最优切分变量自然是x。接下来考虑9个切分点 损失函数为(同式(1.2)) 其中 a. 计算子区域输出值 当s=1.5时,两个子区域 同理,得到其他各切分点的子区域输出值,列表如下 s 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 5.56 5.63 5.72 5.89 6.07 6.24 6.62 6.88 7.11 7.5 7.73 7.99 8.25 8.54 8.91 8.92 9.03 9.05 b. 计算损失函数值,找到最优切分点 当s=1.5时, 同理,计算得到其他各切分点的损失函数值,列表如下 s 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 L(s) 15.72 12.07 8.36 5.78 3.91 1.93 8.01 11.73 15.74 易知,取s=6.5时,损失函数值最小。因此,第一个划分点为(j=x,s=6.5). (2) 用选定的对 划分区域为: 对应输出值: (3) 调用步骤(1),(2),继续划分: 对 s 1.5 2.5 3.5 4.5 5.5 5.56 5.63 5.72 5.89 6.07 6.37 6.54 6.75 6.93 7.05 损失函数值为 s 1.5 2.5 3.5 4.5 5.5 L(s) 1.3087 0.754 0.2771 0.4368 1.0644 L(3.5)最小,取s=3.5为划分点。 后面同理。 (4) 生成回归树: 假设两次划分后即停止,则最终生成的回归树为: 对第三部分例子的python实现及与线性回归对比。 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_depth=1) model2 = DecisionTreeRegressor(max_depth=3) 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, s=20, edgecolor="black", c="darkorange", label="data") plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=1", linewidth=2) plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=3", linewidth=2) plt.plot(X_test, y_3, color='red', label='liner regression', linewidth=2) plt.xlabel("data") plt.ylabel("target") plt.title("Decision Tree Regression") plt.legend() plt.show()运行结果: pdf下载 参考 李航.《统计学习方法》.清华大学出版社.https://blog.csdn.net/weixin_40604987/article/details/79296427https://github.com/KARL13YAN/learning/blob/master/regression%20tree.py |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |