淘先锋技术网

首页 1 2 3 4 5 6 7

机器学习算法第十篇

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


  \  

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 mnm>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(yiyˉ)2

  \  

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

  \  
  \  

  \  
  \  

  \  
  \