简单易学的机器学习算法—分类回归树CART

分类回归树（Classification and Regression Tree，CART）是一种典型的决策树算法，CART算法不仅可以应用于分类问题，而且可以用于回归问题。
一、树回归的概念
    对于一般的线性回归，其拟合的模型是基于全部的数据集。这种全局的数据建模对于一些复杂的数据来说，其建模的难度也会很大。其后，我们有了局部加权线性回归，其只利用数据点周围的局部数据进行建模，这样就简化了建模的难度，提高了模型的准确性。树回归也是一种局部建模的方法，其通过构建决策点将数据切分，在切分后的局部数据集上做回归操作。
    在博文“简单易学的机器学习算法——决策树之ID3算法”中介绍了ID3算法的思想，ID3算法主要是用来处理离散性的问题，然而对于连续型的问题，ID3算法就无能无力了。其次ID3算法的分支也属于多分支，即通过一个特征可以分出很多的子数据集。分类回归树(Classification and Regression Tree, CART)是一种树构建算法，这种算法既可以处理离散型的问题，也可以处理连续型的问题。在处理连续型问题时，主要通过使用二元切分来处理连续型变量，即特征值大于某个给定的值就走左子树，或者就走右子树。
二、回归树的分类
    在构建回归树时，主要有两种不同的树：
回归树(Regression Tree)，其每个叶节点是单个值
模型树(Model Tree)，其每个叶节点是一个线性方程
三、基于CART算法的回归树
    在进行树的左右子树划分时，有一个很重要的量，即给定的值，特征值大于这个给定的值的属于一个子树，小于这个给定的值的属于另一个子树。这个给定的值的选取的原则是使得划分后的子树中的“混乱程度”降低。如何定义这个混乱程度是设计CART算法的一个关键的地方。在ID3算法中我们使用的信息熵和信息增益的概念。信息熵就代表了数据集的紊乱程度。对于连续型的问题，我们可以使用方差的概念来表达混乱程度，方差越大，越紊乱。所以我们要找到使得切分之后的方差最小的划分方式。数据分析师培训
四、实验仿真
    对于数据集1，数据集2，我们分别使用CART算法构建回归树

(数据集1)

(数据集2)
从图上我们可以看出可以将数据集划分成两个子树，即左右子树，并分别在左右子树上做线性回归。同样的道理，下图可以划分为5个子树。
结果为：

(数据集1的结果)

(数据集2的结果)
MATLAB代码：
主程序
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
%% CART  
 
clear all  
clc  
 
% 导入数据集  
%dataSet = load('ex00.txt');  
dataSet = load('ex0.txt');  
 
% 画图1  
% plot(dataSet(:,1),dataSet(:,2),'.');  
% axis([-0.2,1.2,-1.0,2.0]);  
 
% 画图2  
% plot(dataSet(:,2),dataSet(:,3),'.');  
% axis([-0.2,1.2,-1.0,5.0]);  
 
 
createTree(dataSet,1,4);  

构建子树
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ retTree ] = createTree( dataSet,tolS,tolN )  
    [feat,val] = chooseBestSplit(dataSet, tolS, tolN);  
      
    disp(['feat:', num2str(feat)]);  
    disp(['value:', num2str(val)]);  
    if feat == 0  
        return;  
    end  
      
    [lSet,rSet] = binSplitDataSet(dataSet, feat, val);  
    disp('left:');  
    createTree( lSet,tolS,tolN );  
    disp('right:');  
    createTree( rSet,tolS,tolN );  
end  

最佳划分
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ Index, Value ] = chooseBestSplit( dataSet, tolS, tolN )  
% 参数中tolS是容许的误差下降值，tolN是切分的最小样本数  
    m = size(dataSet);%数据集的大小  
    if length(unique(dataSet(:,m(:,2)))) == 1%仅剩下一种时  
        Index = 0;  
        Value = regLeaf(dataSet(:,m(:,2)));  
        return;  
    end  
    S = regErr(dataSet);%误差  
    bestS = inf;%初始化,无穷大  
    bestIndex = 0;  
    bestValue = 0;  
      
    %找到最佳的位置和最优的值  
    for j = 1:(m(:,2)-1)%得到列  
        b = unique(dataSet(:,j));%得到特征所在的列  
        lenCharacter = length(b);  
        for i = 1:lenCharacter  
            temp = b(i,:);  
            [mat0,mat1] = binSplitDataSet(dataSet, j ,temp);  
            m0 = size(mat0);  
            m1 = size(mat1);  
            if m0(:,1) < tolN || m1(:,1) < tolN  
                continue;  
            end  
            newS = regErr(mat0) + regErr(mat1);  
            if newS < bestS  
                bestS = newS;  
                bestIndex = j;  
                bestValue = temp;  
            end  
        end  
    end  
      
    if (S-bestS) < tolS  
        Index = 0;  
        Value = regLeaf(dataSet(:,m(:,2)));  
        return;  
    end  
      
    %划分  
    [mat0, mat1] = binSplitDataSet(dataSet, bestIndex ,bestValue);  
    m0 = size(mat0);  
    m1 = size(mat1);  
    if m0(:,1) < tolN || m1(:,1) < tolN  
        Index = 0;  
        Value = regLeaf(dataSet(:,m(:,2)));  
        return;  
    end  
    Index = bestIndex;  
    Value = bestValue;  
end  

划分
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
%% 将数据集划分为两个部分  
function [ dataSet_1, dataSet_2 ] = binSplitDataSet( dataSet, feature, value )  
    [m,n] = size(dataSet);%计算数据集的大小  
    DataTemp = dataSet(:,feature)';%变成行  
      
    %计算行中标签列的元素大于value的行  
    index_1 = [];%空的矩阵  
    index_2 = [];  
      
    for i = 1:m  
        if DataTemp(1,i) > value  
            index_1 = [index_1,i];  
        else  
            index_2 = [index_2,i];  
        end  
    end  
    [m_1,n_1] = size(index_1);%这里要取列数  
    [m_2,n_2] = size(index_2);  
      
    if n_1>0 && n_2>0  
        for j = 1:n_1  
            dataSet_1(j,:) = dataSet(index_1(1,j),:);  
        end  
      
        for j = 1:n_2  
            dataSet_2(j,:) = dataSet(index_2(1,j),:);  
        end  
    elseif n_1 == 0  
            dataSet_1 = [];  
            dataSet_2 = dataSet;  
    elseif n_2 == 0  
            dataSet_2 = [];  
            dataSet_1 = dataSet;  
    end  
end  
%% 将数据集划分为两个部分  
function [ dataSet_1, dataSet_2 ] = binSplitDataSet( dataSet, feature, value )  
    [m,n] = size(dataSet);%计算数据集的大小  
    DataTemp = dataSet(:,feature)';%变成行  
      
    %计算行中标签列的元素大于value的行  
    index_1 = [];%空的矩阵  
    index_2 = [];  
      
    for i = 1:m  
        if DataTemp(1,i) > value  
            index_1 = [index_1,i];  
        else  
            index_2 = [index_2,i];  
        end  
    end  
    [m_1,n_1] = size(index_1);%这里要取列数  
    [m_2,n_2] = size(index_2);  
      
    if n_1>0 && n_2>0  
        for j = 1:n_1  
            dataSet_1(j,:) = dataSet(index_1(1,j),:);  
        end  
      
        for j = 1:n_2  
            dataSet_2(j,:) = dataSet(index_2(1,j),:);  
        end  
    elseif n_1 == 0  
            dataSet_1 = [];  
            dataSet_2 = dataSet;  
    elseif n_2 == 0  
            dataSet_2 = [];  
            dataSet_1 = dataSet;  
    end  
end  

偏差
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ error ] = regErr( dataSet )  
    m = size(dataSet);%求得dataSet的大小  
      
    dataVar = var(dataSet(:,m(:,2)));  
      
    error = dataVar * (m(:,1)-1);  
end  

叶节点
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ leaf ] = regLeaf( dataSet )  
    m = size(dataSet);  
    leaf = mean(dataSet(:,m(:,2)));  
end