分类回归树算法 -- CART

机器学习 算法

树回归

建模原理

决策树是不断将数据切分成小数据集，直到所有目标变量完全相同，或者数据不能再切分为止。决策树是一种贪心算法，在给定时间内作出最佳选择，并不关心能否达到全局最优。

树回归

优点：可以对复杂进而非线性的数据建模
缺点：结果不易理解
适用数据类型：数值型和标称型数据

CART算法使用二元切分来处理连续型变量。对CART稍作修改就可以处理回归问题。

算法

构建算法:

• 找到最佳的待切分特征：
  
  • 如果该节点不能再分，将该节点存为叶节点
  • 执行二元切分
  • 在左子树构建本方法
  • 在右子树构建本方法

回归

回归树假设叶节点是常数值，这种策略认为数据中的复杂关系可以用树结构来概括。

连续型数值的混乱度计算

计算均值，计算每个点到均值的绝对值或者平方。类似总方差。

切分函数

• 对每个特征：
  
  • 对每个特征值：
    
    • 将数据集切分成两份
    • 计算切分的误差
    • 如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新
• 返回最佳切分的特征和阀值

剪枝

通过降低决策树的复杂度来避免过拟合的过程称为剪枝。

预剪枝

预剪枝通过算法中的参数min_sample_num, min_delta_error来进行控制

后剪枝

后剪枝方法将数据集分成测试集和训练集。首先指定参数，使得构建出来的树足够大、足够复杂，便于剪枝。接下来从上而下找到叶节点，用测试集判断将这些叶节点合并能否降低测试误差，如果是就合并。

• 基于已有的树切分测试数据：
  
  • 如果存在任一子集是一棵树，则在该子集递归剪枝过程
  • 计算将当前两个叶节点合并后的误差
  • 计算不合并的误差
  • 如果合并会降低误差的话，就将叶节点合并

模型树

除了可以把叶节点设置为常数值外，还可以将叶节点设置为分段线性函数(piecewise linear)，所谓的分段线性是指模型由多个线性片段组成。

叶节点产生为函数

def model_leaf(dataset):
    ws, x, y = linesolve(dataset)
    return ws
def model_error(dataset):
    ws, x, y = linesolve(dataset)
    yhat = x*ws
    return sum(power(y - yhat, 2)

指标

回归判断哪个模型好：用y与预测y计算相关性进行判断， corrcoef

Python实现

Github: https://github.com/spiritwiki/codes/tree/master/decidetree_cart
coding.net：https://coding.net/u/spiritwiki/p/codes/git/tree/master/decidetree_cart