精华内容
下载资源
问答
  • 决策树Cart算法源码

    2015-06-20 23:44:17
    这是我从网上找到的一份决策树Cart算法代码,其中在确定分枝时采用的是熵不纯度确定的方法,代码可以运行.声明这份代码不是我原创的,是从某个网页上下载下来的,不过原作者的代码中许多变量没有作详细注释,我在阅读...
  • 决策树决策算法之ID3算法 ID3算法决策树各个节点上应用信息增益准则选择特征,每一次都选择是的信息增益最大的特征进行分裂,递归的构建决策树 具体计算可以参考 决策常用算法数学计算过程 ID3代码实现 import ...

    决策树决策算法之ID3算法

    ID3算法

    在决策树各个节点上应用信息增益准则选择特征,每一次都选择是的信息增益最大的特征进行分裂,递归的构建决策树
    具体计算可以参考
    决策常用算法数学计算过程

    ID3代码实现

    import numpy as  np
    import math
    a=[[2,3],[4,],[3,2]]   #  原数据     参考上面链接里面的计算数据
    x=np.sum(a[0])+np.sum(a[1])+np.sum(a[2])
    # ID3算法计算 
    def Id3():
        result_arr=[]
        for i in a:
    
            c=0
            for j in range(len(i)):
                p=i[j]/np.sum(i)
                pi=p*math.log(p,2)
                c+=pi
            result_arr.append(c)
        return result_arr
    
    def arr_(result_arr):
        d=0
        for k in range(len(result_arr)):
            h=-(np.sum(a[k])/x)*result_arr[k]
            d+=h
        return round(d,3)
    
    id3=arr_(Id3())
    

    C4.5算法 对ID3算法的改进

    ID3算法 使用的是信息增益来判断,取值的时候会选择信息增益大的特征,也就是取值多的那些特征,容易过拟合 ,且只能够处理分类变量,不能够处理缺失值,
    C4.5算法 是采用的悲观剪枝的方式 比较节点前后的分类错误率来进行判断剪枝
    这弥补了ID3算法的偏向性 但由于是递归判断节点的错误率 也导致效率低下,避免过拟合,对缺失值可以处理
    具体计算可以参考
    决策常用算法数学计算过程

    C4.5算法代码实现

    #  计算原始的信息熵
    def start_h():
        a=y/x
        a_p=a*(math.log(y,2)-math.log(x,2))
        b=((x-y)/x)
        b_p=b*(math.log(x-y,2)-math.log(x,2))
        p=-a_p-b_p
        return round(p,4)
    #  C4.5算法   计算信息熵
    def  c4_5(d):
        d=0
        for i in a:
            p=np.sum(i)/x
    
            d+=-p*(math.log(np.sum(i),2)-math.log(np.sum(x),2))
        return  d
    c4_5(d)
    id3=arr_(Id3())   # id3算法处理后的信息熵   
    w=start_h()-id3   #  计算信息增益
    z=w/c4_5(d)       #  计算信息增益率
    

    CART算法 gini指数计算

    gini指数反应数据的离散程度 越大表示越混乱

    具体计算可以参考
    决策常用算法数学计算过程

    CART算法代码实现

    #CART算法  gini 指数计算
    def  gini(a):
        arr=[]
        for i in a:
            c=1
            for j in range(len(i)):
                c-=(i[j]/np.sum(i))**2
            arr.append(c)
        return arr
    
    cart=arr_(gini(a))
    
    
    展开全文
  • 机器学习:决策树cart算法构建回归树
    机器学习:决策树cart算法的回归树、模型树以及回归树与模型树的结果对比

    1、写在前面

    继本人的博文:决策树cart算法在分类与回归的应用(上),本文重点是cart算法在对数据集回归(预测)的实现,将构建的回归树结果与模型树进行比较,cart算法在构建回归树时,依据最小剩余方差法来进行最优标准划分的,当然回归树也是一个二叉树。这里有个本人认为的一个重点就是:cart算法在构建分类树与回归树时,是不删除已经选择过的特征属性的,而ID3、以及C4.5算法一旦第一次选择了该属性,就将剩余的记录去掉这个属性,然后再继续构建子树。这也是本人阅读了多篇博客的理解,而对于cart算法的回归树,博主写的很详细,本文也是在阅读此博主后,将个人的理解记录下来。

    2、cart回归树python实现:

    构建过程,本人就简单叙述下:1、最小剩余方差的计算过程中,充分利用python的set集合特点,将去重后的属性下的属性值放入集合中,然后遍历每个属性特征值计算分类后的方差,这样在遍历了每个属性下的属性值以及所有属性后,将计算的方差最小值对应的属性以及属性值返回,这样就得到了当前的最优划分。2、根据最优化分,将数据集记录划分为左右子树,这里注意不需要将划分后的记录删除已经作为划分了的特征属性。3、判断是否继续划分,即节点是否有必要进行分裂,若训练集数量很多,本人认为采取卡方检验是个很好的方法,但是本文代码实现的数据集记录就十几个,故在此就将是否继续分裂的标准定为了没有特征属性进行划分了,或者所有标签属性值一样,又或者记录数小于一设定阈值。4、回到第一步,对划分的左右数据记录进行最优划分标准求解。
    以下是cart回归树python代码的实现,回归树与模型树的构建方法都给出了相应的注释,数据集链接数据,密码:nrby:
    from numpy import *
    
    def loadDataSet(fileName):
        '''
        读取一个一tab键为分隔符的文件,然后将每行的内容保存成一组浮点数
        '''
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float,curLine))
            dataMat.append(fltLine)
        return dataMat
    
    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):
        '''负责生成叶节点'''
        #当chooseBestSplit()函数确定不再对数据进行切分时,将调用本函数来得到叶节点的模型。
        #在回归树中,该模型其实就是目标变量的均值。
        return mean(dataSet[:,-1])
    
    def regErr(dataSet):
        '''
        误差估计函数,该函数在给定的数据上计算目标变量的平方误差,这里直接调用均方差函数
        '''
        return var(dataSet[:,-1]) * shape(dataSet)[0]#返回总方差
    
    def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
        '''
        树构建函数
        leafType:建立叶节点的函数
        errType:误差计算函数
        ops:包含树构建所需其他参数的元组
        '''
        #选择最优的划分特征
        #如果满足停止条件,将返回None和某类模型的值
        #若构建的是回归树,该模型是一个常数;如果是模型树,其模型是一个线性方程
        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
    
    def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
        '''
        用最佳方式切分数据集和生成相应的叶节点
        '''
        #ops为用户指定参数,用于控制函数的停止时机
        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 splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):
                mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
                if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue
                newS = errType(mat0) + errType(mat1)
                if newS < bestS:
                    bestIndex = featIndex
                    bestValue = splitVal
                    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)
        #提前终止条件都不满足,返回切分特征和特征值
        return bestIndex,bestValue
    
    #剪枝
    def isTree(obj):
        '''判断输入变量是否是一棵树'''
        return (type(obj).__name__=='dict')
    
    def prune(tree, testData):
        '''回归树剪枝函数'''
        if shape(testData)[0] == 0: return getMean(tree) #无测试数据则返回树的平均值
        if (isTree(tree['right']) or isTree(tree['left'])):#
            lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
        if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)
        if isTree(tree['right']): tree['right'] =  prune(tree['right'], rSet)
        #如果两个分支已经不再是子树,合并它们
        #具体做法是对合并前后的误差进行比较。如果合并后的误差比不合并的误差小就进行合并操作,反之则不合并直接返回
        if not isTree(tree['left']) and not isTree(tree['right']):
            lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
            errorNoMerge = sum(power(lSet[:,-1] - tree['left'],2)) +\
                sum(power(rSet[:,-1] - tree['right'],2))
            treeMean = (tree['left']+tree['right'])/2.0
            errorMerge = sum(power(testData[:,-1] - treeMean,2))
            if errorMerge < errorNoMerge:
                print("merging")
                return treeMean
            else: return tree
    
    def getMean(tree):
        '''从上往下遍历树直到叶节点为止,计算它们的平均值'''
        if isTree(tree['right']): tree['right'] = getMean(tree['right'])
        if isTree(tree['left']): tree['left'] = getMean(tree['left'])
        return (tree['left']+tree['right'])/2.0
    
    #构建模型树
    def linearSolve(dataSet):
        '''将数据集格式化成目标变量Y和自变量X,X、Y用于执行简单线性回归'''
        m,n = shape(dataSet)
        X = mat(ones((m,n))); Y = mat(ones((m,1)))
        X[:,1:n] = dataSet[:,0:n-1]; Y = dataSet[:,-1]#默认最后一列为Y
        xTx = X.T*X
        #若矩阵的逆不存在,抛异常
        if linalg.det(xTx) == 0.0:
            raise NameError('This matrix is singular, cannot do inverse,\n\
            try increasing the second value of ops')
        ws = xTx.I * (X.T * Y)#回归系数
        return ws,X,Y
    
    def modelLeaf(dataSet):
        '''负责生成叶节点模型'''
        ws,X,Y = linearSolve(dataSet)
        return ws
    
    def modelErr(dataSet):
        '''误差计算函数'''
        ws,X,Y = linearSolve(dataSet)
        yHat = X * ws
        return sum(power(Y - yHat,2))
    
    #模型树与回归树比较
    def regTreeEval(model, inDat):
        #为了和modeTreeEval()保持一致,保留两个输入参数
        return float(model)
    
    def createForeCast(tree, testData, modelEval=regTreeEval):
        # 多次调用treeForeCast()函数,以向量形式返回预测值,在整个测试集进行预测非常有用
        m=len(testData)
        yHat = mat(zeros((m,1)))
        for i in range(m):
            yHat[i,0] = treeForeCast(tree, mat(testData[i]), modelEval)
        return yHat
    
    def treeForeCast(tree, inData, modelEval=regTreeEval):
        '''
        # 在给定树结构的情况下,对于单个数据点,该函数会给出一个预测值。
        # modeEval是对叶节点进行预测的函数引用,指定树的类型,以便在叶节点上调用合适的模型。
        # 此函数自顶向下遍历整棵树,直到命中叶节点为止,一旦到达叶节点,它就会在输入数据上
        # 调用modelEval()函数,该函数的默认值为regTreeEval()
        '''
        if not isTree(tree): return modelEval(tree, inData)
        if inData[tree['spInd']] > tree['spVal']:
            if isTree(tree['left']): return treeForeCast(tree['left'], inData, modelEval)
            else: return modelEval(tree['left'], inData)
        else:
            if isTree(tree['right']): return treeForeCast(tree['right'], inData, modelEval)
            else: return modelEval(tree['right'], inData)
    
    
    def modelTreeEval(model, inDat):
        #对输入数据进行格式化处理,在原数据矩阵上增加第0列,元素的值都是1
        n = shape(inDat)[1]
        X = mat(ones((1,n+1)))
        X[:,1:n+1]=inDat
        return float(X*model)
    
    if __name__=="__main__":
       trainData=mat(loadDataSet('trainDataset.txt'))
       testData=mat(loadDataSet('testDataset.txt'))
       Mytree=createTree(trainData,ops=(1,20))
       print(Mytree)
       yHat=createForeCast(Mytree,testData[:,0])
       print(corrcoef(yHat,testData[:,-1],rowvar=0)[0,1])#预测的结果与真实结果的相似性
       #创建模型树
       modelTree=createTree(trainData,modelLeaf,modelErr,ops=(1,20))
       yHat = createForeCast(modelTree,testData[:,0],modelTreeEval)
       print(corrcoef(yHat, testData[:, -1], rowvar=0)[0, 1])  # 模型树预测的结果与真实结果的相似性
    
    
    注意:在此处模型树构建过程与cart的回归树基本一致,区别在于在叶子节点处:回归树将叶子结点的记录求得方差值作为结果,而模型树求得是线性回归的系数作为叶子结点。

    3、运行结果图

    其中字典结构是最终生成的cart回归树;第二行是回归树预测的结果与真实结果的相似性,第三行是模型树与真实结果的相似性。

    4、写在最后

    有时间将介绍下使用Tkinter绘制GUI并结合Matplotlib实现交互式绘图,将数据信息以易于人们理解的方式呈现,便于观察对数据的具体分析。一起学习,一起进步。



    展开全文
  • 前面,小编和大家一起学习了关于决策树C5.0算法进行决策树分析,今天,继续学习使用CART算法进行决策树分析。 首先,我们了解一下CART算法与C5.0算法的区别: C5.0算法只能处理分类型目标变量,CART算法既能处理...

    在这里插入图片描述
    前面,小编和大家一起学习了关于决策树C5.0算法进行决策树分析,今天,继续学习使用CART算法进行决策树分析。

    首先,我们了解一下CART算法与C5.0算法的区别:

    • 目标变量类型:C5.0算法只能处理分类型目标变量,CART算法既能处理分类型,也能处理连续型目标变量生成分类树;
    • 衡量指标不同:在决策树生长阶段,CART算法分别采用基尼系数(分类树)以及方差(回归树)作为树生长的衡量指标;
    • 修剪方法不同:C5.0基于悲观误差估计进行剪枝,而CART算法是根据最小代价复杂度剪枝;
    • 树形结构不同:CART决策树是一种二叉树结构,无论变量的水平有多少种,最后只会生成两个分支。C5.0决策树则能生成多叉树。

    1. CART算法实现决策树分析

    CART决策树节点
    在这里插入图片描述
    案例:Demo数据文件“bankloan.sav”。(违约风险分析,识别每名客户属于违约组还是非违约组)

    数据流
    在这里插入图片描述
    类型节点中进行角色设定
    在这里插入图片描述

    2. 数据准备

    2.1 利用选择节点,删除缺失值

    剔除数据中的缺失数据。
    在这里插入图片描述

    2.2 利用分区节点,对数据进行分区

    C&R树节点还会从训练集中抽取样本作为检验集,所以选择80%作为训练集,20%作为测试集。
    在这里插入图片描述

    3. 建模设置

    3.1 构建选项卡

    3.11 目标选项

    在这里插入图片描述

    3.12 基本选项

    在这里插入图片描述

    3.13 中止规则选项

    在这里插入图片描述

    3.14 成本和先验选项

    在这里插入图片描述

    3.15 高级选项

    在这里插入图片描述

    4. 模型结果

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    可以看出,CART算法生成的决策树比C5.0的更加简洁。

    展开全文
  • 1.CART生成 CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右...CART算法由以下两步组成: 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大; 决...

    1.CART生成

    CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。

    CART算法由以下两步组成:

    1. 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大;
    2. 决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时损失函数最小作为剪枝的标准。

    CART决策树的生成就是递归地构建二叉决策树的过程。CART决策树既可以用于分类也可以用于回归。本文我们仅讨论用于分类的CART。对分类树而言,CART用Gini系数最小化准则来进行特征选择,生成二叉树。 CART生成算法如下:

    根据训练数据集,从根结点开始,递归地对每个结点进行以下操作,构建二叉决策树:

    算法停止计算的条件是结点中的样本个数小于预定阈值,或样本集的Gini系数小于预定阈值(样本基本属于同一类),或者没有更多特征。

    2.一个具体的例子

    首先对数据集非类标号属性{是否有房,婚姻状况,年收入}分别计算它们的Gini系数增益,取Gini系数增益值最大的属性作为决策树的根节点属性。根节点的Gini系数 

     

    当根据是否有房来进行划分时,Gini系数增益计算过程为 

    若按婚姻状况属性来划分,属性婚姻状况有三个可能的取值{married,single,divorced},分别计算划分后的

    • {married} | {single,divorced}
    • {single} | {married,divorced}
    • {divorced} | {single,married}

     的Gini系数增益。 
    当分组为{married} | {single,divorced}时,SlSl表示婚姻状况取值为married的分组,SrSr表示婚姻状况取值为single或者divorced的分组 

     

    当分组为{single} | {married,divorced}时, 

     

     

     

    当分组为{divorced} | {single,married}时, 

     
     

     

     对比计算结果,根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果,也就是{married} | {single,divorced}。

     最后考虑年收入属性,我们发现它是一个连续的数值类型。我们在前面的文章里已经专门介绍过如何应对这种类型的数据划分了。对此还不是很清楚的朋友可以参考之前的文章,这里不再赘述。

     对于年收入属性为数值型属性,首先需要对数据按升序排序,然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时,我们算得其中间值为65。倘若以中间值65作为分割点。

     

    其他值的计算同理可得,我们不再逐一给出计算过程,仅列出结果如下(最终我们取其中使得增益最大化的那个二分准则来作为构建二叉树的准则): 

     

     

     

    最大化增益等价于最小化子女结点的不纯性度量(Gini系数)的加权平均值,之前的表里我们列出的是Gini系数的加权平均值,现在的表里给出的是Gini系数增益。现在我们希望最大化Gini系数的增益。根据计算知道,三个属性划分根节点的增益最大的有两个:年收入属性和婚姻状况,他们的增益都为0.12。此时,选取首先出现的属性作为第一次划分

     接下来,采用同样的方法,分别计算剩下属性,其中根节点的Gini系数为(此时是否拖欠贷款的各有3个records) 

    与前面的计算过程类似,对于是否有房属性,可得 

     

    对于年收入属性则有:

    最后我们构建的CART如下图所示:

     

     

     

    最后我们总结一下,CART和C4.5的主要区别:

    • C4.5采用信息增益率来作为分支特征的选择标准,而CART则采用Gini系数;
    • C4.5不一定是二叉树,但CART一定是二叉树。

     

    3.关于过拟合以及剪枝

    决策树很容易发生过拟合,也就是由于对train数据集适应得太好,反而在test数据集上表现得不好。这个时候我们要么是

     通过阈值控制终止条件避免树形结构分支过细,要么就是通过对已经形成的决策树进行剪枝来避免过拟合。另外一个克服过拟合的手段就是基于Bootstrap的思想建立随机森林(Random Forest)。关于剪枝的内容可以参考文献【2】以了解更多。

    参考文献
    【1】Wu, X., Kumar, V., Quinlan, J.R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G.J., Ng, A., Liu, B., Philip, S.Y. and Zhou, Z.H., 2008. Top 10 algorithms in data mining. Knowledge and information systems, 14(1), pp.1-37. (http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf
    【2】李航,统计学习方法,清华大学出版社


    4.代码实现

    import numpy as np
    
    
    # 定义树结构,采用的二叉树,左子树:条件为true,右子树:条件为false
    # leftBranch:左子树结点
    # rightBranch:右子树结点
    # col:信息增益最大时对应的列索引
    # value:最优列索引下,划分数据类型的值
    # results:分类结果
    # summary:信息增益最大时样本信息
    # data:信息增益最大时数据集
    class Tree:
        def __init__(self, leftBranch=None, rightBranch=None, col=-1, value=None, results=None, summary=None, data=None):
            self.leftBranch = leftBranch
            self.rightBranch = rightBranch
            self.col = col
            self.value = value
            self.results = results
            self.summary = summary
            self.data = data
    
        def __str__(self):
            print(u"列号:%d" % self.col)
            print(u"列划分值:%s" % self.value)
            print(u"样本信息:%s" % self.summary)
            return ""
    
    
    # 划分数据集
    def splitDataSet(dataSet, value, column):
        leftList = []
        rightList = []
        # 判断value是否是数值型
        if (isinstance(value, int) or isinstance(value, float)):
            # 遍历每一行数据
            for rowData in dataSet:
                # 如果某一行指定列值>=value,则将该行数据保存在leftList中,否则保存在rightList中
                if (rowData[column] >= value):
                    leftList.append(rowData)
                else:
                    rightList.append(rowData)
        # value为标称型
        else:
            # 遍历每一行数据
            for rowData in dataSet:
                # 如果某一行指定列值==value,则将该行数据保存在leftList中,否则保存在rightList中
                if (rowData[column] == value):
                    leftList.append(rowData)
                else:
                    rightList.append(rowData)
        return leftList, rightList
    
    
    # 统计标签类每个样本个数
    '''
    该函数是计算gini值的辅助函数,假设输入的dataSet为为['A', 'B', 'C', 'A', 'A', 'D'],
    则输出为['A':3,' B':1, 'C':1, 'D':1],这样分类统计dataSet中每个类别的数量
    '''
    
    
    def calculateDiffCount(dataSet):
        results = {}
        for data in dataSet:
            # data[-1] 是数据集最后一列,也就是标签类
            if data[-1] not in results:
                results.setdefault(data[-1], 1)
            else:
                results[data[-1]] += 1
        return results
    
    
    # 基尼指数公式实现
    def gini(dataSet):
        # 计算gini的值(Calculate GINI)
        # 数据所有行
        length = len(dataSet)
        # 标签列合并后的数据集
        results = calculateDiffCount(dataSet)
        imp = 0.0
        for i in results:
            imp += results[i] / length * results[i] / length
        return 1 - imp
    
    
    # 生成决策树
    '''算法步骤'''
    '''根据训练数据集,从根结点开始,递归地对每个结点进行以下操作,构建二叉决策树:
    1 设结点的训练数据集为D,计算现有特征对该数据集的信息增益。此时,对每一个特征A,对其可能取的
      每个值a,根据样本点对A >=a 的测试为“是”或“否”将D分割成D1和D2两部分,利用基尼指数计算信息增益。
    2 在所有可能的特征A以及它们所有可能的切分点a中,选择信息增益最大的特征及其对应的切分点作为最优特征
      与最优切分点,依据最优特征与最优切分点,从现结点生成两个子结点,将训练数据集依特征分配到两个子结点中去。
    3 对两个子结点递归地调用1,2,直至满足停止条件。
    4 生成CART决策树。
    '''''''''''''''''''''
    
    
    # evaluationFunc= gini :采用的是基尼指数来衡量信息关注度
    def buildDecisionTree(dataSet, evaluationFunc=gini):
        # 计算基础数据集的基尼指数
        baseGain = evaluationFunc(dataSet)
        # 计算每一行的长度(也就是列总数)
        columnLength = len(dataSet[0])
        # 计算数据项总数
        rowLength = len(dataSet)
        # 初始化
        bestGain = 0.0  # 信息增益最大值
        bestValue = None  # 信息增益最大时的列索引,以及划分数据集的样本值
        bestSet = None  # 信息增益最大,听过样本值划分数据集后的数据子集
        # 标签列除外(最后一列),遍历每一列数据
        for col in range(columnLength - 1):
            # 获取指定列数据
            colSet = [example[col] for example in dataSet]
            # 获取指定列样本唯一值
            uniqueColSet = set(colSet)
            # 遍历指定列样本集
            for value in uniqueColSet:
                # 分割数据集
                leftDataSet, rightDataSet = splitDataSet(dataSet, value, col)
                # 计算子数据集概率,python3 "/"除号结果为小数
                prop = len(leftDataSet) / rowLength
                # 计算信息增益
                infoGain = baseGain - prop * evaluationFunc(leftDataSet) - (1 - prop) * evaluationFunc(rightDataSet)
                # 找出信息增益最大时的列索引,value,数据子集
                if (infoGain > bestGain):
                    bestGain = infoGain
                    bestValue = (col, value)
                    bestSet = (leftDataSet, rightDataSet)
        # 结点信息
        #    nodeDescription = {'impurity:%.3f'%baseGain,'sample:%d'%rowLength}
        nodeDescription = {'impurity': '%.3f' % baseGain, 'sample': '%d' % rowLength}
        # 数据行标签类别不一致,可以继续分类
        # 递归必须有终止条件
        if bestGain > 0:
            # 递归,生成左子树结点,右子树结点
            leftBranch = buildDecisionTree(bestSet[0], evaluationFunc)
            rightBranch = buildDecisionTree(bestSet[1], evaluationFunc)
            # print(Tree(leftBranch=leftBranch, rightBranch=rightBranch, col=bestValue[0]
            #             , value=bestValue[1], summary=nodeDescription, data=bestSet))
            return Tree(leftBranch=leftBranch, rightBranch=rightBranch, col=bestValue[0]
                        , value=bestValue[1], summary=nodeDescription, data=bestSet)
        else:
            # 数据行标签类别都相同,分类终止
            return Tree(results=calculateDiffCount(dataSet), summary=nodeDescription, data=dataSet)
    
    
    # def createTree(dataSet, evaluationFunc=gini):
    #     # 递归建立决策树, 当gain=0,时停止回归
    #     # 计算基础数据集的基尼指数
    #     baseGain = evaluationFunc(dataSet)
    #     # 计算每一行的长度(也就是列总数)
    #     columnLength = len(dataSet[0])
    #     # 计算数据项总数
    #     rowLength = len(dataSet)
    #     # 初始化
    #     bestGain = 0.0  # 信息增益最大值
    #     bestValue = None  # 信息增益最大时的列索引,以及划分数据集的样本值
    #     bestSet = None  # 信息增益最大,听过样本值划分数据集后的数据子集
    #     # 标签列除外(最后一列),遍历每一列数据
    #     for col in range(columnLength - 1):
    #         # 获取指定列数据
    #         colSet = [example[col] for example in dataSet]
    #         # 获取指定列样本唯一值
    #         uniqueColSet = set(colSet)
    #         # 遍历指定列样本集
    #         for value in uniqueColSet:
    #             # 分割数据集
    #             leftDataSet, rightDataSet = splitDataSet(dataSet, value, col)
    #             # 计算子数据集概率,python3 "/"除号结果为小数
    #             prop = len(leftDataSet) / rowLength
    #             # 计算信息增益
    #             infoGain = baseGain - prop * evaluationFunc(leftDataSet) - (1 - prop) * evaluationFunc(rightDataSet)
    #             # 找出信息增益最大时的列索引,value,数据子集
    #             if (infoGain > bestGain):
    #                 bestGain = infoGain
    #                 bestValue = (col, value)
    #                 bestSet = (leftDataSet, rightDataSet)
    #
    #     impurity = u'%.3f' % baseGain
    #     sample = '%d' % rowLength
    #
    #     if bestGain > 0:
    #         bestFeatLabel = u'serial:%s\nimpurity:%s\nsample:%s' % (bestValue[0], impurity, sample)
    #         myTree = {bestFeatLabel: {}}
    #         myTree[bestFeatLabel][bestValue[1]] = createTree(bestSet[0], evaluationFunc)
    #         myTree[bestFeatLabel]['no'] = createTree(bestSet[1], evaluationFunc)
    #         return myTree
    #     else:  # 递归需要返回值
    #         bestFeatValue = u'%s\nimpurity:%s\nsample:%s' % (str(calculateDiffCount(dataSet)), impurity, sample)
    #         return bestFeatValue
    
    
    # 分类测试:
    '''根据给定测试数据遍历二叉树,找到符合条件的叶子结点'''
    '''例如测试数据为[5.9,3,4.2,1.75],按照训练数据生成的决策树分类的顺序为
       第2列对应测试数据4.2 =>与决策树根结点(2)的value(3)比较,>=3则遍历左子树,否则遍历右子树,
       叶子结点就是结果'''
    
    
    def classify(data, tree):
        # 判断是否是叶子结点,是就返回叶子结点相关信息,否就继续遍历
        if tree.results != None:
            return u"%s\n%s" % (tree.results, tree.summary)
        else:
            branch = None
            v = data[tree.col]
            # 数值型数据
            if isinstance(v, int) or isinstance(v, float):
                if v >= tree.value:
                    branch = tree.leftBranch
                else:
                    branch = tree.rightBranch
            else:  # 标称型数据
                if v == tree.value:
                    branch = tree.leftBranch
                else:
                    branch = tree.rightBranch
            return classify(data, branch)
    
    
    def loadCSV(fileName):
        def convertTypes(s):
            s = s.strip()
            try:
                return float(s) if '.' in s else int(s)
            except ValueError:
                return s
    
        data = np.loadtxt(fileName, dtype='str', delimiter=',')
        data = data[1:, :]
        dataSet = ([[convertTypes(item) for item in row] for row in data])
        return dataSet
    
    
    # 多数表决器
    # 列中相同值数量最多为结果
    # def majorityCnt(classList):
    #     import operator
    #     classCounts = {}
    #     for value in classList:
    #         if (value not in classCounts.keys()):
    #             classCounts[value] = 0
    #         classCounts[value] += 1
    #     sortedClassCount = sorted(classCounts.items(), key=operator.itemgetter(1), reverse=True)
    #     return sortedClassCount[0][0]
    
    
    # 剪枝算法(前序遍历方式:根=>左子树=>右子树)
    '''算法步骤
    1. 从二叉树的根结点出发,递归调用剪枝算法,直至左、右结点都是叶子结点
    2. 计算父节点(子结点为叶子结点)的信息增益infoGain
    3. 如果infoGain < miniGain,则选取样本多的叶子结点来取代父节点
    4. 循环1,2,3,直至遍历完整棵树
    '''''''''
    # def prune(tree, miniGain, evaluationFunc=gini):
    #     print(u"当前结点信息:")
    #     print(str(tree))
    #     # 如果当前结点的左子树不是叶子结点,遍历左子树
    #     if (tree.leftBranch.results == None):
    #         print(u"左子树结点信息:")
    #         print(str(tree.leftBranch))
    #         prune(tree.leftBranch, miniGain, evaluationFunc)
    #     # 如果当前结点的右子树不是叶子结点,遍历右子树
    #     if (tree.rightBranch.results == None):
    #         print(u"右子树结点信息:")
    #         print(str(tree.rightBranch))
    #         prune(tree.rightBranch, miniGain, evaluationFunc)
    #     # 左子树和右子树都是叶子结点
    #     if (tree.leftBranch.results != None and tree.rightBranch.results != None):
    #         # 计算左叶子结点数据长度
    #         leftLen = len(tree.leftBranch.data)
    #         # 计算右叶子结点数据长度
    #         rightLen = len(tree.rightBranch.data)
    #         # 计算左叶子结点概率
    #         leftProp = leftLen / (leftLen + rightLen)
    #         # 计算该结点的信息增益(子类是叶子结点)
    #         infoGain = (evaluationFunc(tree.leftBranch.data + tree.rightBranch.data) -
    #                     leftProp * evaluationFunc(tree.leftBranch.data) - (1 - leftProp) * evaluationFunc(
    #                     tree.rightBranch.data))
    #         # 信息增益 < 给定阈值,则说明叶子结点与其父结点特征差别不大,可以剪枝
    #         if (infoGain < miniGain):
    #             # 合并左右叶子结点数据
    #             dataSet = tree.leftBranch.data + tree.rightBranch.data
    #             # 获取标签列
    #             classLabels = [example[-1] for example in dataSet]
    #             # 找到样本最多的标签值
    #             keyLabel = majorityCnt(classLabels)
    #             # 判断标签值是左右叶子结点哪一个
    #             if keyLabel in tree.leftBranch.results:
    #                 # 左叶子结点取代父结点
    #                 tree.data = tree.leftBranch.data
    #                 tree.results = tree.leftBranch.results
    #                 tree.summary = tree.leftBranch.summary
    #             else:
    #                 # 右叶子结点取代父结点
    #                 tree.data = tree.rightBranch.data
    #                 tree.results = tree.rightBranch.results
    #                 tree.summary = tree.rightBranch.summary
    #             tree.leftBranch = None
    #             tree.rightBranch = None
    
    
    def printTree(myTree):
        print("当前结点信息:")
        print(myTree)
        # 如果当前结点的左子树不是叶子结点,遍历左子树
        if (myTree.leftBranch.results == None):
            print("左子树结点信息:")
            print(myTree.leftBranch)
            printTree(myTree.leftBranch)
        # 如果当前结点的右子树不是叶子结点,遍历右子树
        if (myTree.rightBranch.results == None):
            print("右子树结点信息:")
            print(myTree.rightBranch)
            printTree(myTree.rightBranch)
    
    
    if __name__ == '__main__':
        dataSet = loadCSV("D:\\mlInAction\\irisData.csv")
        # print(dataSet)
        myTree = buildDecisionTree(dataSet, evaluationFunc=gini)
        printTree(myTree)
        testData = [5.9, 3, 4.2, 1.75]
        result = classify(testData,myTree)
        print("预测结果为:")
        print(result)

    5.输出结果

    当前结点信息:
    列号:2
    列划分值:3
    样本信息:{'impurity': '0.667', 'sample': '150'}
    
    左子树结点信息:
    列号:3
    列划分值:1.8
    样本信息:{'impurity': '0.500', 'sample': '100'}
    
    当前结点信息:
    列号:3
    列划分值:1.8
    样本信息:{'impurity': '0.500', 'sample': '100'}
    
    左子树结点信息:
    列号:2
    列划分值:4.9
    样本信息:{'impurity': '0.043', 'sample': '46'}
    
    当前结点信息:
    列号:2
    列划分值:4.9
    样本信息:{'impurity': '0.043', 'sample': '46'}
    
    右子树结点信息:
    列号:0
    列划分值:6
    样本信息:{'impurity': '0.444', 'sample': '3'}
    
    当前结点信息:
    列号:0
    列划分值:6
    样本信息:{'impurity': '0.444', 'sample': '3'}
    
    右子树结点信息:
    列号:2
    列划分值:5
    样本信息:{'impurity': '0.168', 'sample': '54'}
    
    当前结点信息:
    列号:2
    列划分值:5
    样本信息:{'impurity': '0.168', 'sample': '54'}
    
    左子树结点信息:
    列号:3
    列划分值:1.6
    样本信息:{'impurity': '0.444', 'sample': '6'}
    
    当前结点信息:
    列号:3
    列划分值:1.6
    样本信息:{'impurity': '0.444', 'sample': '6'}
    
    左子树结点信息:
    列号:0
    列划分值:7.2
    样本信息:{'impurity': '0.444', 'sample': '3'}
    
    当前结点信息:
    列号:0
    列划分值:7.2
    样本信息:{'impurity': '0.444', 'sample': '3'}
    
    右子树结点信息:
    列号:3
    列划分值:1.7
    样本信息:{'impurity': '0.041', 'sample': '48'}
    
    当前结点信息:
    列号:3
    列划分值:1.7
    样本信息:{'impurity': '0.041', 'sample': '48'}
    
    预测结果为:
    {'virginica': 1}
    {'impurity': '0.000', 'sample': '1'}

    https://www.cnblogs.com/further-further-further/p/9482885.html

    https://baimafujinji.blog.csdn.net/article/details/53269040

    转载于:https://www.cnblogs.com/xinmomoyan/p/10768611.html

    展开全文
  • 和之前介绍的ID3和C4.5一样,CART算法同样是决策树模型的一种经典的实现。决策树这个模型一共有三种实现方式,前面我们已经介绍了ID3和C4.5两种,今天刚好补齐这最后一种。 算法特点 CART称为分类回归树,从名字上...
  • 决策树CART分类算法

    2020-04-21 15:40:25
    决策树算法可以用作分类回归,两者差异在于构造树时节点分裂规则的不同。分类算法用Gini系数分裂,回归则是计算方差。 决策树分类: 假设存在数据集(X, Y),Y包含0和1两中标签 Num X0 ...
  • 决策树CART算法

    千次阅读 2016-03-16 19:43:17
    本文转自... 在之前介绍过决策树的ID3算法实现,今天主要来介绍决策树的另一种实现,即CART算法。   Contents    1. CART算法的认识  2. CART算法的原理  3. CART算法的实现
  • 决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树,分类树是从ID3算法开始,改进成C4.5,随后又出现了cart算法cart算法可以生成分类树,也可以生成回归树,每个决策树之所以...
  • 使用matlab实现决策树cart算法(基于fitctree函数)

    万次阅读 多人点赞 2018-04-08 10:57:55
    使用的是matlab自带的fitctree函数...数据直接用的matlab里自带的举例用数据,所以代码直接复制到maltab里即可运行。 大家有更好的想法或疑问欢迎留言交流。 %% Created by Indiffer %数据预处理 load ionosphere;...
  • 决策树-CART算法

    2016-09-14 16:53:49
    原文出自:ACdreamers-决策树CART算法 在之前介绍过决策树的ID3算法实现,今天主要来介绍决策树的另一种实现,即CART算法。   Contents    1. CART算法的认识  2. CART算法的原理 ...
  • 决策树CART 算法

    2020-09-10 11:05:58
    我们可以把决策树分为 ID3 算法、C4.5 算法CART 算法。今天我来带你学习 CART 算法CART 算法,英文全称叫做 Classification And Regression Tree,中文叫做分类回归树。ID3 和 C4.5 算法可以生成二叉树或多叉树...
  • CART算法的数学详细计算步骤,以及CART算法生成决策树的过程,可以详见:【机器学习】【决策树CART算法,用样本集一步一步详解如何求:基尼指数,最优特征,最优切分点本章仅提供CART算法的python实现代码,以...
  • 决策树CART算法实践

    2019-11-17 14:41:35
    上篇为 决策树的基本原理篇,本文主要是聊下CART算法,因为在上文提到的决策树算法中,CART算法在三种决策树算法中应用的最多,CART算法优点: 分类规则清晰,结果容易理解 计算量小,速度快 可以处理异常值,...
  • 本文是周志华老师的《机器学习》一书中第4章...本文主要是不进行剪枝的CART决策树的实现,预剪枝与后剪枝的CART决策树实现分别可见Python编程实现预剪枝的CART决策树和Python编程实现后剪枝的CART决策树。如果发现文...
  • 先生成数据,再调用cart算法,生成决策树。 #生成模板数据 dataSet,labels=createSet(url) #复制标签 测试决策树时,原有标签对象不可用 labels_tmp=labels[:] #用决策树 desicionTree = createTree(dataSet,...
  • 决策树Cart算法

    2017-11-09 10:07:00
    Contents 1. CART算法的认识 ...Classification And Regression Tree,即分类回归树算法,简称CART算法,它是决策树的一种实现,通 常决策树主要有三种实现,分别是ID3算法,CART算法和C4.5算法。...
  • 1. 前言本文主要讲解CART决策树代码实现的细节,对于想了解决策树原理的同学建议可以去观看台大林轩田教授的视频,他对于决策树以及接下来要利用决策树生成的随机森林算法都讲解的非常好,下面附上链接。...
  • CART决策树算法

    2020-09-04 10:45:07
    内容整理参考文档决策树——CART算法及其后的参考文章。 CART(classification and regression tree)分类与回归树,既可用于分类,也可用于回归。 CART分类树生成 CART分类树算法使用基尼系数来选择特征。基尼系数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,802
精华内容 2,320
关键字:

决策树cart算法代码