你好,游客 登录
背景:
阅读新闻

CART之回归树python代码实现

[日期:2018-04-20] 来源:  作者: [字体: ]

一、CART ( Classification And Regression Tree) 分类回归树

1、基尼指数:

在分类问题中,假设有 个类,样本点属于第 类的概率为 ,则概率分布的基尼指数定义为:

在CART 分类问题中,基尼指数作为特征选择的依据:选择基尼指数最小的特征及切分点做为最优特征和最优切分点。

2、在回归问题中,特征选择及最佳划分特征值的依据是:划分后样本的均方差之和最小!

二、算法分析:

CART 主要包括特征选择、回归树的生成、剪枝三部分

数据特征停止划分的条件:
1、当前数据集中的标签相同,返回当前的标签
2、划分前后的总方差差距很小,数据不划分,返回的属性为空,返回的最佳划分值为当前所有标签的均值。
3、划分后的左右两个数据集的样本数量较小,返回的属性为空,返回的最佳划分值为当前所有标签的均值。

若满足上述三个特征停止划分的条件,则返回的最佳特征为空,返回的最佳划分特征值会作为叶子结点。

注:CART是一棵二叉树。 在生成CART回归树过程中,一个特征可能会被使用不止一次,所以,不存在当前属性集为空的情况;

1、特征选择(依据:总方差最小)

输入:数据集、op = [m,n]
输出:最佳特征、最佳划分特征值

m表示剪枝前总方差与剪枝后总方差差值的最小值; n: 数据集划分为左右两个子数据集后,子数据集中的样本的最少数量;

1、判断数据集中所有的样本标签是否相同,是:返回当前标签;
2、遍历所有的样本特征,遍历每一个特征的特征值。计算出每一个特征值下的数据总方差,找出使总方差最小的特征、特征值
3、比较划分前和划分后的总方差大小;若划分后总方差减少较小,则返回的最佳特征为空,返回的最佳划分特征值会为当前数据集标签的平均值。
4、比较划分后的左右分支数据集样本中的数量,若某一分支数据集中样本少于指定数量op[1],则返回的最佳特征为空,
返回的最佳划分特征值会为当前数据集标签的平均值。
5、否则,返回使总方差最小的特征、特征值

二、回归树的生成函数 createTree
输入:数据集
输出:生成回归树
1、得到当前数据集的最佳划分特征、最佳划分特征值
2、若返回的最佳特征为空,则返回最佳划分特征值(作为叶子节点)
3、声明一个字典,用于保存当前的最佳划分特征、最佳划分特征值
4、执行二元切分;根据最佳划分特征、最佳划分特征值,将当前的数据划分为两部分
5、在左子树中调用createTree 函数, 在右子树调用createTree 函数。
6、返回树。

注:在生成的回归树模型中,划分特征、特征值、左节点、右节点均有相应的关键词对应。

三、(后)剪枝:(CART 树一定是二叉树,所以,如果发生剪枝,肯定是将两个叶子节点合并)

输入:树、测试集
输出:树

1、判断测试集是否为空,是:对树进行塌陷处理
2、判断树的左右分支是否为树结构,是:根据树当前的特征值、划分值将测试集分为Lset、Rset两个集合;
3、判断树的左分支是否是树结构:是:在该子集递归调用剪枝过程;
4、判断树的右分支是否是树结构:是:在该子集递归调用剪枝过程;
5、判断当前树结构的两个节点是否为叶子节点:
是:
a、根据当前树结构,测试集划分为Lset,Rset两部分;
b、计算没有合并时的总方差NoMergeError,即:测试集在Lset 和 Rset 的总方差之和;
c、合并后,取叶子节点值为原左右叶子结点的均值。求取测试集在该节点处的总方差MergeError,;
d、比较合并前后总方差的大小;若NoMergeError > MergeError,返回合并后的节点;否则,返回原来的树结构;
否:
返回树结构。

代码实现:数据集

#-*- coding:utf-8 -*-
from numpy import *
import numpy as np
# 三大步骤:
'''1、特征的选择:标准:总方差最小2、回归树的生成:停止划分的标准3、剪枝:'''

# 导入数据集
def loadData(filaName):
    dataSet = []
    fr = open(filaName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        theLine = map(float, curLine)                # map all elements to float()
        dataSet.append(theLine)
    return dataSet

# 特征选择:输入: 输出:最佳特征、最佳划分值
'''1、选择标准遍历所有的特征Fi:遍历每个特征的所有特征值Zi;找到Zi,划分后总的方差最小停止划分的条件:1、当前数据集中的标签相同,返回当前的标签2、划分前后的总方差差距很小,数据不划分,返回的属性为空,返回的最佳划分值为当前所有标签的均值。3、划分后的左右两个数据集的样本数量较小,返回的属性为空,返回的最佳划分值为当前所有标签的均值。当划分的数据集满足上述条件之一,返回的最佳划分值作为叶子节点;当划分后的数据集不满足上述要求时,找到最佳划分的属性,及最佳划分特征值'''

# 计算总的方差
def GetAllVar(dataSet):
    return var(dataSet[:,-1])*shape(dataSet)[0]

# 根据给定的特征、特征值划分数据集
def dataSplit(dataSet,feature,featNumber):
    dataL =  dataSet[nonzero(dataSet[:,feature] > featNumber)[0],:]
    dataR = dataSet[nonzero(dataSet[:,feature] <= featNumber)[0],:]
    return dataL,dataR

# 特征划分
def choseBestFeature(dataSet,op = [1,4]):          # 三个停止条件可否当作是三个预剪枝操作
    if len(set(dataSet[:,-1].T.tolist()[0]))==1:    # 停止条件 1
        regLeaf = mean(dataSet[:,-1])       
        return None,regLeaf                  # 返回标签的均值作为叶子节点
    Serror = GetAllVar(dataSet)
    BestFeature = -1; BestNumber = 0; lowError = inf
    m,n = shape(dataSet) # m 个样本, n -1 个特征
    for i in range(n-1):    # 遍历每一个特征值
        for j in set(dataSet[:,i].T.tolist()[0]):
            dataL,dataR = dataSplit(dataSet,i,j)
            if shape(dataR)[0]<op[1] or shape(dataL)[0]<op[1]: continue  # 如果所给的划分后的数据集中样本数目甚少,则直接跳出
            tempError = GetAllVar(dataL) + GetAllVar(dataR)
            if tempError < lowError:
                lowError = tempError; BestFeature = i; BestNumber = j
    if Serror - lowError < op[0]:              # 停止条件 2 如果所给的数据划分前后的差别不大,则停止划分
        return None,mean(dataSet[:,-1])       
    dataL, dataR = dataSplit(dataSet, BestFeature, BestNumber)
    if shape(dataR)[0] < op[1] or shape(dataL)[0] < op[1]:        # 停止条件 3
        return None, mean(dataSet[:, -1])
    return BestFeature,BestNumber


# 决策树生成
def createTree(dataSet,op=[1,4]):
    bestFeat,bestNumber = choseBestFeature(dataSet,op)
    if bestFeat==None: return bestNumber
    regTree = {}
    regTree['spInd'] = bestFeat
    regTree['spVal'] = bestNumber
    dataL,dataR = dataSplit(dataSet,bestFeat,bestNumber)
    regTree['left'] = createTree(dataL,op)
    regTree['right'] = createTree(dataR,op)
    return  regTree

# 后剪枝操作
# 用于判断所给的节点是否是叶子节点
def isTree(Tree):
    return (type(Tree).__name__=='dict' )

# 计算两个叶子节点的均值
def getMean(Tree):
    if isTree(Tree['left']): Tree['left'] = getMean(Tree['left'])
    if isTree(Tree['right']):Tree['right'] = getMean(Tree['right'])
    return (Tree['left']+ Tree['right'])/2.0

# 后剪枝
def pruneTree(Tree,testData):
    if shape(testData)[0]==0: return getMean(Tree)
    if isTree(Tree['left'])or isTree(Tree['right']):
        dataL,dataR = dataSplit(testData,Tree['spInd'],Tree['spVal'])
    if isTree(Tree['left']):
        Tree['left'] = pruneTree(Tree['left'],dataL)
    if isTree(Tree['right']):
        Tree['right'] = pruneTree(Tree['right'],dataR)
    if not isTree(Tree['left']) and not isTree(Tree['right']):
        dataL,dataR = dataSplit(testData,Tree['spInd'],Tree['spVal'])
        errorNoMerge = sum(power(dataL[:,-1] - Tree['left'],2)) + sum(power(dataR[:,-1] - Tree['right'],2))
        leafMean = getMean(Tree)
        errorMerge = sum(power(testData[:,-1]-  leafMean,2))
        if errorNoMerge > errorMerge:
            print"the leaf merge"
            return leafMean
        else:
            return Tree
    else:
        return Tree

# 预测
def forecastSample(Tree,testData):
    if not isTree(Tree): return float(tree)
    # print"选择的特征是:" ,Tree['spInd']
    # print"测试数据的特征值是:" ,testData[Tree['spInd']]
    if testData[0,Tree['spInd']]>Tree['spVal']:
        if isTree(Tree['left']):
            return forecastSample(Tree['left'],testData)
        else:
            return float(Tree['left'])
    else:
        if isTree(Tree['right']):
            return forecastSample(Tree['right'],testData)
        else:
            return float(Tree['right'])

def TreeForecast(Tree,testData):
    m = shape(testData)[0]
    y_hat = mat(zeros((m,1)))
    for i in range(m):
        y_hat[i,0] = forecastSample(Tree,testData[i])
    return y_hat

if __name__=="__main__":
    print "hello world"
    dataMat = loadData("ex2.txt")
    dataMat = mat(dataMat)
    op = [1,6]    # 参数1:剪枝前总方差与剪枝后总方差差值的最小值;参数2:将数据集划分为两个子数据集后,子数据集中的样本的最少数量;
    theCreateTree =  createTree(dataMat,op)
  # 测试数据
    dataMat2 = loadData("ex2test.txt")
    dataMat2 = mat(dataMat2)
    #thePruneTree = pruneTree(theCreateTree, dataMat2)
    #print"剪枝后的后树:\n",thePruneTree
    y = dataMat2[:, -1]
    y_hat = TreeForecast(theCreateTree,dataMat2)
    print corrcoef(y_hat,y,rowvar=0)[0,1]              # 用预测值与真实值计算相关系数

收藏 推荐 打印 | 录入:Cstor | 阅读:
相关新闻      
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款