簡單易學的機器學習算法—分類回歸樹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