机器学习树回归

线性回归需要拟合所有的数据才能生成模型，但是，当数据拥有众多的特征以及特征之间的关系十分复杂时，不能使用全局线性模型进行拟合，此时就可以使用树回归。树回归是通过构建树，来对连续性数值型（回归）数据进行预测。

CART（Classification And Regression Trees，分类回归树）是一种树构建算法。该算法既可以用于分类还可以用于回归。

CART和ID3算法的区别

决策树其在划分子集的时候使用的方法是信息增益（我们也叫ID3方法），其方法只针对标称型（离散型）数据有效，很难用于回归；对于多个特征，数据就会被切为多份，切分过后的特征在后面的过程中不再起作用。CART（分类回归树）算法可以解决掉ID3的问题，该算法可用于分类和回归。CART算法使用二元切分来处理连续性变量，回归树用到的方法划分树节点是采用计算总方差，而且叶节点代表的是回归树的叶节点是一个常数值（平均值）。

方差公式：

回归树划分结点停止条件：

（1）不同剩余特征值的数目如果为1，则说明就一个不同大小的值了，不需要继续切分了。

（2）切分数据集后效果提升不够大，小于自定义误差参数值，就不应该进行切分操作而直接创建叶节点。

（3）切分后的子集大小如果小于用户定义的参数，也不应该切分了。

代码：

from numpy import *



# 切分数据，feature：待切分的特征，value:切分的特征值
def BinSplitDataSet(dataset, feature, value):
    mat0 = dataset[nonzero(dataset[:, feature] > value)[0], :]
    mat1 = dataset[nonzero(dataset[:, feature] <= value)[0], :]
    return mat0, mat1


# 负责生成叶节点，在回归树中，叶节点的模型也就是目标变量的平均值
def regLeaf(dataSet):
    return mean(dataSet[:, -1])#损失函数均方误差，平均值损失 最小


# 计算目标变量的平均误差
def regErr(dataSet):
    # var()是均方差函数，用均方差乘上样本个数即为总方差
    return var(dataSet[:, -1]) * shape(dataSet)[0]


def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    # tols与toln是用户指定的参数，用于控住函数的停止时机
    # tols是容许的误差下降值，toln是切分的最小样本数
    tols = ops[0];
    tolN = ops[1]
    # 如果只剩下一种标签，则退出
    if len(set(dataSet[:, -1].T.tolist()[0])) == 1:
        return None, leafType(dataSet)
    #统计数据集的行和列
    m, n = shape(dataSet)
    # 得到数据集的总方差
    S = errType(dataSet)
    # 初始化最好的划分特征
    bestS = inf;
    bestIndex = 0;
    bestValue = 0;
    # 对于每个特征
    for featIndex in range(n - 1):
        # 对于每个特征值
        for splitValue in set(dataSet[:, featIndex].T.A.tolist()[0]):
            # 划分为两个数据集
            mat0, mat1 = BinSplitDataSet(dataSet, featIndex, splitValue)
            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue
            # 计算总方差
            newS = errType(mat0) + errType(mat1)
            if newS < bestS:
                bestIndex = featIndex
                bestValue = splitValue
                bestS = newS
    #如果小于容许的误差下降值则返回空，不划分
    if (S - bestS) < tols:
        return None, leafType(dataSet)
    mat0, mat1 = BinSplitDataSet(dataSet, bestIndex, bestValue)
    # 如果小于最小划分样本数同样返回空，不划分
    # if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):
    #     return None, leafType(dataSet)
    if(shape(dataSet)[0]<tolN):
        return None, leafType(dataSet)
    return bestIndex, bestValue


# 利用CART算法建立回归树
#
def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 2)):
    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
    # 递归的停止条件，如果不可再分，则终止
    if feat == None: return val
    retTree = {}
    # 定义根节点，及其对应的特征值
    retTree['spInd'] = feat
    retTree['spVal'] = val
    lSet, rSet = BinSplitDataSet(dataSet, feat, val)
    # 递归建立左子树与右子树
    retTree['left'] = createTree(lSet, leafType, errType, ops)
    retTree['right'] = createTree(rSet, leafType, errType, ops)
    return retTree


datasets=mat([[10,120,30,60],[12,130,35,65],[14,140,40,70],[16,150,45,75],[18,160,50,80],[20,170,60,85],[25,180,70,90]])
myTree = createTree(datasets)
print(myTree)

运行截图如下：可以根据如图画出树的形状。