简单易学的机器学习算法——分类回归树CART
简单易学的机器学习算法——分类回归树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代码：
主程序
%% 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);构建子树
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最佳划分
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划分
%% 将数据集划分为两个部分
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偏差
function [ error ] = regErr( dataSet )
m = size(dataSet);%求得dataSet的大小
dataVar = var(dataSet(:,m(:,2)));
error = dataVar * (m(:,1)-1);
end叶节点
function [ leaf ] = regLeaf( dataSet )
m = size(dataSet);
leaf = mean(dataSet(:,m(:,2)));
end