主要内容:决策树算法+CART(回归树)

  \  

CART(classification and regression tree) 故英文名思意:分类和回归树.
CART算法包含决策树生成和决策树剪枝两部分
CART决策生成树部分主要分为生成回归树和生成分类树
本篇主要讲生成回归树
  \  
  \  

构建一棵可以对输入样本进行很好预测,并输出预测值的二叉决策回归树

  \  
  \  

• 把一个样本放入节点
  比较自身与节点的特征,选择一个分支: ‘下去’
  循环 ‘下去’ , 直到叶子节点为止
  当一个测试样本a落入某叶子时, 该叶子的c值作为该样本a的预测值输出
  (某叶子的c值是该树在训练时候, 训练集划分到该叶子的所有样本的输出值的平均值)
  (每个节点都有一个特征选择,如:长头发向左分支,短头发向右分支,该选择是决策树生成的时候遗留的)

  \  
  \  

• 算法一开始将所有训练样本丢到根节点
  然后通过某准则将它们切成两份,分别丢入左节点与右节点
  然后对每个节点按照该准则继续切分,直到某个情况发生,停止切分,直接生成叶子节点
  (某情况是指:例如节点内样本数不能低于10个,树的层数不超过11层…参数设置的问题啊)

  \  
  \  

• 算法这样做滴:
  我们针对一个节点D, 定义一个误差函数J 它可以计算该节点内所有样本的的总误差J(D)
  然后取节点内某特征m与该特征的某个取值n,
  再按照每个样本的的 m ≤ n 与 m > n m \le n与m>n m≤n与m>n,将样本集切成两份 D 1 , D 2 D_1,D_2 D1​,D2​
  J ( D 1 ) + J ( D 2 ) J(D_1)+J(D_2) J(D1​)+J(D2​)的值,即此切法的总误差P
  所以: 我们只需要遍历节点内的所有特征,并在该特征内再遍历所有可能取值,取得一大堆总误差P
  最后取最小的总误差 P m i n P_{min} Pmin​所对应的特征与取值,进行切分就好

  \  
  \  

• 算法说:单个节点所有样本的预测值与平均值之差的平方的和(总方差)作为该叶子节点误差

• 即 : 单 个 节 点 误 差 = ∑ i = 1 节 点 样 本 总 数 ( y i − y ˉ ) 2 即:单个节点误差=\sum^{节点样本总数}_{i=1}(y_i-\bar y)^2 即:单个节点误差=∑i=1节点样本总数​(yi​−yˉ​)2

  \  

• 这个式子可以很好表达我们对误差的定义,
• 同时每个叶子内部所有样本输出值y的总方差越小,其平均值c的代表性就越高
  (在样本容量相同的情况下，方差越大，说明数据的波动越大，越不稳定)

  \  
  \  

  \  
  \  

  \  
  \