《统计学习方法》决策树 CART生成算法回归树 Python实现

左手的ㄟ右手 2022-06-09 00:51 217阅读 0赞

代码可在Github上下载:[代码下载][Link 1]  
先说明一下在看《统计学习方法》Cart回归树的时候懵懵的，也没又例子。然后发现《机器学习实战》P162有讲到这个，仔细看了一下。  
所以这下面是《机器学习实战》的代码，但书上没有什么原理，如果不太懂原理的话，会有点难以理解。而它的实现就是《统计学习方法》P69的算法5.5（最小二乘回归树的生成算法）。  
\#\#\#\#\#\#引用《统计学习方法》P69的算法5.5

> 输入：训练数据集 D；  
> 输出：回归树 f(x).  
> 在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：  
> (1) 选择最优切分变量 j 与切分点 s（比如选择切分向量第j维来划分，就根据这个s>特征值和<=特征值来划分成2个子集），求解  
>  m i n j , s \[ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 \] \\mathop \{min\}\_\{j,s\}\[\\mathop \{min\}\_\{c\_1\}\\sum\_\{x\_i\\in R\_1(j,s)\}(y\_i−c\_1)^2+\\mathop \{min\}\_\{c\_2\}\\sum\_\{x\_i\\in R\_2(j,s)\}(y\_i−c\_2)^2\] minj,s\[minc1∑xi∈R1(j,s)(yi−c1)2\+minc2∑xi∈R2(j,s)(yi−c2)2\]  
> 遍历变量 j，对固定的切分变量 j 扫描切分点 s  
> (2) 用选定的对 (j,s) 划分区域并决定相应的输出值：  
>  R 1 ( j , s ) = x ∣ x ( j ) ≤ s R\_1(j,s)=\{x|x^\{(j)\}≤s\} R1(j,s)=x∣x(j)≤s, R 2 ( j , s ) = x ∣ x ( j ) > s R\_2(j,s)=\{x|x^\{(j)\}>s\} R2(j,s)=x∣x(j)>s  
>  c ^ m = 1 N m ∑ x i ∈ R m ( j , s ) y i \\hat c\_m=\\frac \{1\}\{N\_m\}\\sum\_\{x\_i \\in R\_m(j,s)\}y\_i c^m=Nm1∑xi∈Rm(j,s)yi, x ∈ R m , m = 1 , 2 x\\in R\_m,m=1,2 x∈Rm,m=1,2  
> (3) 继续对两个子区域调用步骤(1),(2)，直至满足停止条件。  
> (4) 将输入空间分为 M 个区域 R1,R2,⋯,RM，生成决策树：  
>  f ( x ) = ∑ m = 1 M c ^ m I ( x ∈ R m ) f(x)=\\sum\_\{m=1\}^M\\hat c\_mI(x\\in R\_m) f(x)=∑m=1Mc^mI(x∈Rm)

好了，我们来看代码吧。

def loadDataSet(self, fileName):    #加载数据
            dataMat = []
            fr = open(fileName)
            for line in fr.readlines(): #遍历每一行
                curLine = line.strip().split('\t')
                fltLine = map(float, curLine)   #将里面的值映射成float,否则是字符串类型的
                dataMat.append(fltLine)
            return dataMat

这上面是从文件中加载数据集的代码，没太多可以说的，接着看。

def regLeaf(self, dataSet): #将均值作为叶子节点
            return np.mean(dataSet[:, -1]) #类别的均值

看下注释，其实就是对应上面的 c ^ m = 1 N m ∑ x i ∈ R m ( j , s ) y i \\hat c\_m=\\frac \{1\}\{N\_m\}\\sum\_\{x\_i \\in R\_m(j,s)\}y\_i c^m=Nm1∑xi∈Rm(j,s)yi, x ∈ R m , m = 1 , 2 x\\in R\_m,m=1,2 x∈Rm,m=1,2这个公式了。

def regErr(self, dataSet):#计算误差
            return np.var(dataSet[:, -1]) * np.shape(dataSet)[0] #方差乘以行数

你可以先看下[api:numpy.var][api_numpy.var]就知道了它是一个计算方差的。

> var = mean(abs(x - x.mean())\*\*2)

方差乘以行数不就是mean(abs(x - x.mean())\*\*2)然后行数，对应 m i n c 1 ∑ ( y i − c 1 ) 2 \\mathop \{min\}\_\{c\_1\} \\sum (y\_i - c\_1) ^2 minc1∑(yi−c1)2了么。  
所以这个函数对应着 m i n j , s \[ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 \] \\mathop \{min\}\_\{j,s\}\[\\mathop \{min\}\_\{c\_1\}\\sum\_\{x\_i\\in R\_1(j,s)\}(y\_i−c\_1)^2+\\mathop \{min\}\_\{c\_2\}\\sum\_\{x\_i\\in R\_2(j,s)\}(y\_i−c\_2)^2\] minj,s\[minc1∑xi∈R1(j,s)(yi−c1)2\+minc2∑xi∈R2(j,s)(yi−c2)2\].让我们乘胜逐北。

def createTree(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
            feat, val = self.chooseBestSplit(dataSet, leafType, errType, ops)
            if feat == None:    return val  #说明是叶节点，直接返回均值
            retTree = {}
            retTree['spInd'] = feat #记录是用哪个特征作为划分
            retTree['spVal'] = val  #记录是用哪个特征作为划分（以便于查找的时候，相等进入左树，不等进入右树）
            lSet, rSet = self.binSplitDataSet(dataSet, feat, val)   #按返回的特征来选择划分子集
            retTree['left'] = self.createTree(lSet, leafType, errType, ops) #用划分的2个子集的左子集，递归建树
            retTree['right'] = self.createTree(rSet, leafType, errType, ops)
            return retTree

这个就是建树的代码了，大体思想就是通过判断是否需要继续划分，如果不需要说明已经是叶节点了，返回叶节点的值；如果需要划分，则继续用递归的形式继续划分下去。继续看下如何选择最好的特征划分。

def chooseBestSplit(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
            tolS = ops[0] #容许的误差下降值
            tolN = ops[1]   #划分的最少样本数
            if len(set(dataSet[:, -1].T.tolist()[0])) == 1: #类标签的值都是一样的，说明没必要划分了，直接返回
                return None, leafType(dataSet)
            m, n = np.shape(dataSet)    #m是行数，n是列数
            S = errType(self, dataSet)    #计算总体误差
            bestS = np.inf  #np.inf是无穷大的意思，因为我们要找出最小的误差值，如果将这个值设得太小，遍历时很容易会将这个值当成最小的误差值了
            bestIndex = 0
            bestValue = 0
            for featIndex in range(n-1):    #遍历每一个维度
                for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]): #选出不同的特征值，进行划分,勘误：这里跟书上不一样，需修改
                    mat0, mat1 = self.binSplitDataSet(dataSet, featIndex, splitVal) #子集的划分
                    if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):    #划分的两个数据子集，只要有一个小于4，就说明没必要划分
                        continue
                    newS = errType(self, mat0) + errType(self, mat1)    #计算误差
                    if newS < bestS:    #更新最小误差值
                        bestIndex = featIndex
                        bestValue = splitVal
                        bestS = newS
            if (S - bestS) < tolS:  #检查新切分能否降低误差
                return None, leafType(self, dataSet)
            mat0, mat1 = self.binSplitDataSet(dataSet, bestIndex, bestValue)
            if (np.shape(mat0)[0] < tolN) or(np.shape(mat1)[0] < tolN): #检查是否需要划分（如果两个子集的任一方小于4则没必要划分）
                return None, leafType(self, dataSet)
            return bestIndex, bestValue

这段代码，说白了就是上面算法（1）的步骤：

>  \[ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 \] \[\\mathop \{min\}\_\{c\_1\}\\sum\_\{x\_i\\in R\_1(j,s)\}(y\_i−c\_1)^2+\\mathop \{min\}\_\{c\_2\}\\sum\_\{x\_i\\in R\_2(j,s)\}(y\_i−c\_2)^2\] \[minc1∑xi∈R1(j,s)(yi−c1)2\+minc2∑xi∈R2(j,s)(yi−c2)2\]

对应这个代码`newS = errType(self, mat0) + errType(self, mat1)`。  
上面`for featIndex in range(n-1):`以及里面的循环，  
`for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):`  
就是寻找最小的误差值了。  
然后这里有3个条件会被判定这个集合是作为叶子节点的（好不让他继续划分下去呀）。  
1、类标签的值都是一样的，说明没必要划分了，直接返回None， 叶子节点值。  
2、总体误差减去最小的误差如果小于容许的误差下降值（tolS=ops\[0\]），直接返回None， 叶子节点值。  
3、如果划分的两个子集，任一方小于4（tolN=ops\[1\]）个样本的话，直接返回None， 叶子节点值。  
好了，测试一下。

if __name__ == '__main__':
        regTree = RegressionTree()
        myMat = regTree.loadDataSet('ex0.txt')
        myMat = np.mat(myMat)
        print regTree.createTree(myMat)

你成功了吗?  
下面贴下完整的代码。

# --*-- coding:utf-8 --*--
    import numpy as np
    
    class RegressionTree:   #回归树
        def loadDataSet(self, fileName):    #加载数据
            dataMat = []
            fr = open(fileName)
            for line in fr.readlines(): #遍历每一行
                curLine = line.strip().split('\t')
                fltLine = map(float, curLine)   #将里面的值映射成float,否则是字符串类型的
                dataMat.append(fltLine)
            return dataMat
    
        def binSplitDataSet(self, dataSet, feature, value): #按某列的特征值来划分数据集
            mat0 = dataSet[np.nonzero(dataSet[:, feature] > value)[0], :]   #勘误：这里跟书上不一样，需修改
            mat1 = dataSet[np.nonzero(dataSet[:, feature] <= value)[0], :]  #np.nonzero(...)[0]返回一个列表
            return mat0, mat1
        def regLeaf(self, dataSet): #将均值作为叶子节点
            return np.mean(dataSet[:, -1])
    
        def regErr(self, dataSet):#计算误差
            return np.var(dataSet[:, -1]) * np.shape(dataSet)[0]    #方差乘以行数
    
        def createTree(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
            feat, val = self.chooseBestSplit(dataSet, leafType, errType, ops)
            if feat == None:    return val  #说明是叶节点，直接返回均值
            retTree = {}
            retTree['spInd'] = feat #记录是用哪个特征作为划分
            retTree['spVal'] = val  #记录是用哪个特征作为划分（以便于查找的时候，相等进入左树，不等进入右树）
            lSet, rSet = self.binSplitDataSet(dataSet, feat, val)   #按返回的特征来选择划分子集
            retTree['left'] = self.createTree(lSet, leafType, errType, ops) #用划分的2个子集的左子集，递归建树
            retTree['right'] = self.createTree(rSet, leafType, errType, ops)
            return retTree
    
        def chooseBestSplit(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
            tolS = ops[0] #容许的误差下降值
            tolN = ops[1]   #划分的最少样本数
            if len(set(dataSet[:, -1].T.tolist()[0])) == 1: #类标签的值都是一样的，说明没必要划分了，直接返回
                return None, leafType(dataSet)
            m, n = np.shape(dataSet)    #m是行数，n是列数
            S = errType(self, dataSet)    #计算总体误差
            bestS = np.inf  #np.inf是无穷大的意思，因为我们要找出最小的误差值，如果将这个值设得太小，遍历时很容易会将这个值当成最小的误差值了
            bestIndex = 0
            bestValue = 0
            for featIndex in range(n-1):    #遍历每一个维度
                for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]): #选出不同的特征值，进行划分,勘误：这里跟书上不一样，需修改
                    mat0, mat1 = self.binSplitDataSet(dataSet, featIndex, splitVal) #子集的划分
                    if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):    #划分的两个数据子集，只要有一个小于4，就说明没必要划分
                        continue
                    newS = errType(self, mat0) + errType(self, mat1)    #计算误差
                    if newS < bestS:    #更新最小误差值
                        bestIndex = featIndex
                        bestValue = splitVal
                        bestS = newS
            if (S - bestS) < tolS:  #检查新切分能否降低误差
                return None, leafType(self, dataSet)
            mat0, mat1 = self.binSplitDataSet(dataSet, bestIndex, bestValue)
            if (np.shape(mat0)[0] < tolN) or(np.shape(mat1)[0] < tolN): #检查是否需要划分（如果两个子集的任一方小于4则没必要划分）
                return None, leafType(self, dataSet)
            return bestIndex, bestValue

数据集文件"ex0.txt"以及回归树的完整代码见[机器学习Github][Github]

[Link 1]: https://github.com/FlameCharmander/MachineLearning
[api_numpy.var]: https://docs.scipy.org/doc/numpy/reference/generated/numpy.var.html
[Github]: https://github.com/FlameCharmander/MachineLearning/tree/master/decision_tree