决策树原理及Python代码实现

决策树原理及Python代码实现决策树其实就是按节点分类数据集的一种方法。在本文中,我将讨论数学上如何使用信息论划分数据集,并编写代码构建决策树。创建决策树进行分类的流程如下:(1)创建数据集(2)计算数据集的信息熵(3)遍历所有特征,选择信息熵最小的特征,即为最好的分类特征(4)根据上一步得到的分类特征分割数据集,并将该特征从列表中移除(5)执行递归函数,返回第三

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

2020.4.5添加:

哈哈,迟来的源码,我把它放到GitHub上了:包含详细注释的树模型源码;包括决策树和随机森林,欢迎取用,欢迎讨论,欢迎star;

我才发现CSDN的资源下载自动要求这么多积分,我之前上传的时候是限定0积分的。。

###################正文分割线######################

决策树其实就是按节点分类数据集的一种方法。在本文中,我将讨论数学上如何使用信息论划分数据集,并编写代码构建决策树(本文使用ID3算法构建决策树,ID3算法可以用来划分标称型数据集)。

创建决策树进行分类的流程如下:

(1)    创建数据集

(2)    计算数据集的信息熵

(3)    遍历所有特征,选择信息熵最小的特征,即为最好的分类特征

(4)    根据上一步得到的分类特征分割数据集,并将该特征从列表中移除

(5)    执行递归函数,返回第三步,不断分割数据集,直到分类结束

(6)    使用决策树执行分类,返回分类结果

 

首先,给出一个简单数据集:

决策树原理及Python代码实现

 

 数据解读:

在该数据集中包含五个海洋动物,有两个特征:(1)不浮出水面是否可以生存;(2)是否有脚蹼;这些动物被分成两类:鱼类和非鱼类。在我们构建决策树的过程中,对某个动物,只有两个特征都为“是”时,才将其判定为鱼类。

   在构建决策树时,我们需要解决的第一个问题是:当前数据集哪个特征在划分数据分类时起决定性作用,即我们要如何找出最优的分类特征。为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。完成数据划分后,原始数据集就被划分为几个数据子集,这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型,即数据已正确分类,无需进一步分割。如果数据子集内的数据不属于同个类型,则需要重复划分数据子集的过程。划分数据子集的算法和划分原始数据集的方法相同(因此可用递归函数继续划分子集),直到所有具有相同类型的数据都在一个数据子集内。

 

  构建决策树的伪代码函数createTree()如下所示:

检测数据集中的每个子集是否属于同一分类:

    If so return 类标签

    Else:

        寻找划分数据集的最好特征

        划分数据集

        创建分支节点

            For 每个划分的子集:

                调用函数createTree()并增加返回结果到分支节点中

        Return 分支节点

 

 

1)划分数据集的大原则是:将无序的数据变得更加有序。这里引入信息熵的概念。如果待分类的事务可能划分在多个分类之中,则符号xi的信息定义为:

决策树原理及Python代码实现

 

其中p(xi)是选择该分类的概率。

为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值,通过下面的公式得到:

决策树原理及Python代码实现

 

直观的理解:如果x属于某个分类的值越大(即数据越有序),H的值越小;极端情况下,p(xi)=1时,H=0,此时分类最准确。所以我们要使H的值尽可能小。

计算给定数据集的信息熵的代码如下:

'''计算数据集的信息熵 (信息熵即指类别标签的混乱程度,值越小越好)'''
def calcshan(dataSet):   
    lenDataSet=len(dataSet)
    p={}
    H=0.0
    for data in dataSet:
        currentLabel=data[-1]  #获取类别标签
        if currentLabel not in p.keys():  #若字典中不存在该类别标签,即创建
            p[currentLabel]=0
        p[currentLabel]+=1    #递增类别标签的值
    for key in p:
        px=float(p[key])/float(lenDataSet)  #计算某个标签的概率
        H-=px*log(px,2)  #计算信息熵
    return H

结果如下:

决策树原理及Python代码实现

 

(2)计算完信息熵后,我们便可以得到数据集的无序程度。我们将对每个特征划分数据集的结果计算一次信息熵,然后判断哪个特征划分数据集是最好的划分方式(根据信息熵判断,信息熵越小,说明划分效果越好)。

按照给定特征划分数据集的代码如下:

 

'''根据某一特征分类数据集'''
def spiltData(dataSet,axis,value):    #dataSet为要划分的数据集,axis为给定的特征,value为给定特征的具体值
    subDataSet=[]
    for data in dataSet:
        subData=[]
        if data[axis]==value:
            subData=data[:axis]  #取出data中第0到axis-1个数进subData;
            subData.extend(data[axis+1:])  #取出data中第axis+1到最后一个数进subData;这两行代码相当于把第axis个数从数据集中剔除掉
            subDataSet.append(subData) #此处要注意expend和append的区别
    return subDataSet

 

结果如下:

决策树原理及Python代码实现

 

(3)选择最好的数据集划分方式,代码如下:

 

'''遍历所有特征,选择信息熵最小的特征,即为最好的分类特征'''      
def chooseBestFeature(dataSet):  
    lenFeature=len(dataSet[0])-1    #计算特征维度时要把类别标签那一列去掉
    shanInit=calcshan(dataSet)      #计算原始数据集的信息熵
    feature=[]
    inValue=0.0
    bestFeature=0
    for i in range(lenFeature):
        shanCarry=0.0
        feature=[example[i] for example in dataSet]  #提取第i个特征的所有数据
        feature=set(feature)  #得到第i个特征所有的分类值,如'0'和'1'
        for feat in feature:  
            subData=spiltData(dataSet,i,feat)  #先对数据集按照分类值分类
            prob=float(len(subData))/float(len(dataSet))
            shanCarry+=prob*calcshan(subData)  #计算第i个特征的信息熵
        outValue=shanInit-shanCarry  #原始数据信息熵与循环中的信息熵的差
        if (outValue>inValue):
            inValue=outValue  #将信息熵与原始熵相减后的值赋给inValue,方便下一个循环的信息熵差值与其比较
            bestFeature=i
    return bestFeature

 

结果如下:

决策树原理及Python代码实现

 

(4)选择好最好的划分特征后,接下来,可以开始创建决策树了。其工作原理如下:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据。因此我们可以使用递归的原则处理数据集。递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类。

具体实现代码如下:

 

'''创建我们所要分类的决策树'''
def createTree(dataSet,label):    
    classList=[example[-1] for example in dataSet]   #classList是指当前数据集的类别标签
    if classList.count(classList[0])==len(classList): #计算classList中某个类别标签的数量,若只有一类,则数量与它的数据长度相等
        return classList[0]
    if len(dataSet[0])==1:   #当处理完所有特征而类别标签还不唯一时起作用
        return majorityCnt(classList)
    featBest=chooseBestFeature(dataSet)  #选择最好的分类特征
    feature=[example[featBest] for example in dataSet]  #接下来使用该分类特征进行分类
    featValue=set(feature)  #得到该特征所有的分类值,如'0'和'1'
    newLabel=label[featBest]
    del(label[featBest])
    Tree={newLabel:{}}  #创建一个多重字典,存储决策树分类结果
    for value in featValue:
        subLabel=label[:]
        Tree[newLabel][value]=createTree(spiltData(dataSet,featBest,value),subLabel) #递归函数使得Tree不断创建分支,直到分类结束
    return Tree

 

结果如下:

 

 决策树原理及Python代码实现

(5)依靠训练数据构造了决策树之后,我们可以将它用于实际数据的分类。在执行数据分类时,需要使用决策树以及用于构造树的标签向量。然后,程序比较测试数据与决策树上的数值,递归执行该过程直到进入叶子节点;最后将测试数据定义为叶子节点所属的类型。

具体实现代码如下:

 

'''使用决策树执行分类,返回分类结果'''
def classify(tree,label,testVec):       #tree为createTree()函数返回的决策树;label为特征的标签值;testVec为测试数据,即所有特征的具体值构成的向量
    firstFeat=tree.keys()[0]            #取出tree的第一个键
    secondDict=tree[firstFeat]          #取出tree第一个键的值,即tree的第二个字典(包含关系)
    labelIndex=label.index(firstFeat)   #得到第一个特征firstFeat在标签label中的索引
    for key in secondDict.keys():       #遍历第二个字典的键
        if testVec[labelIndex]==key:    #如果第一个特征的测试值与第二个字典的键相等时
            if type(secondDict[key]).__name__=='dict':  #如果第二个字典的值还是一个字典,说明分类还没结束,递归执行classify函数
                classLabel=classify(secondDict[key],label,testVec)  #递归函数中只有输入的第一个参数不同,不断向字典内层渗入
            else:
                classLabel=secondDict[key]  #最后将得到的分类值赋给classLabel输出
    return classLabel

 

结果如下:

决策树原理及Python代码实现

 

我们可以看到,只有测试数据的两个特征都为1时,才会输出‘yes’,判定为鱼类,结果符合我们的实际要求。

 

现在我们已经创建了使用决策树的分类器,但是每次使用分类器时,必须重新构造决策树,而且构造决策树是很耗时的任务。因此,为了节省计算时间,最好能够在每次执行分类时调用已经构造好的决策树。这里我们使用Python的pickle模块序列化对象。序列化对象可以在磁盘上保存对象,并在需要的时候读取出来。

使用pickle模块存储决策树代码如下:

 

'''使用pickle模块存储决策树'''
def storeTree(tree,filename):  
    import pickle
    fw=open(filename,'w')
    pickle.dump(tree,fw)
    fw.close()

'''打开文件取出决策树'''
def loadTree(filename):         
    import pickle
    fr=open(filename,'r')
    return pickle.load(fr)

 

结果如下:

决策树原理及Python代码实现

 

执行完storeTree()函数,我们的代码路径里就会多出一个dataTree.txt的文件,保存决策树内容,以后要使用决策树进行分类时,使用loadTree()函数直接调用即可。

参考书籍:

《机器学习实战》 Peter Harrington著  李锐,李鹏,曲亚东,王斌译

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195945.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 将oracle端口1521共享_oracle如何开放1521端口

    将oracle端口1521共享_oracle如何开放1521端口如何设置SharedSocket?在注册表:HKEY_LOCAL_MACHINESOFTWAREORACLEHOME0上新建一个字符串值:USE_SHARED_SOCKET=true.如果安装了多个目录,则每个类似的目录都要设置:HKEY_LOCAL_MACHINESOFTWAREORACLEHOMEx(x目录编号)设置后要求重新启动实例(只重启listener发现没有效果)Oracle客户端…

  • oracle修改数据库用户名密码,怎样修改oracle数据库的用户名密码[通俗易懂]

    oracle修改数据库用户名密码,怎样修改oracle数据库的用户名密码[通俗易懂]对于不经常使用数据库的同学们来说,忘记用户名密码是很常见的一件事。下面就让学习啦小编给大家说说怎样修改oracle数据库的用户名密码吧。修改oracle数据库用户名密码的方法进入cmd命令界面(快捷键是win+R)。修改管理员用户密码(一):在命令界面输入sqlplus“/assysdba”即可以管理员身份链接成功。修改管理员用户密码(二):在SQL命令界面输入alterusersyste…

  • Kubeadm 安装

    Kubeadm 安装

  • js数组删除指定数据方法「建议收藏」

    js数组删除指定数据方法「建议收藏」js数组中删除指定数据1,splice删除(配合indexOf()方法)2,filter删除3,Set删除

  • Windows AD域功能介绍、Windows AD域方案介绍

    Windows AD域功能介绍、Windows AD域方案介绍WindowsAD域功能介绍、WindowsAD域方案介绍功能一、AD域管理https://www.manageengine.cn/products/ad-manager/1、AD域管理通过批量创建和编辑用户帐户,指派管理权限等,简化WindowsAD域的管理。2、批量管理域用户使用CSV文件批量导入用户、编辑用户属性、重置密码、批量迁移用户和用户对象。3、批量创建域用…

  • 开发MT4指标和EA(自动交易系统)

    开发MT4指标和EA(自动交易系统)对外开发MT4指标和EA(自动交易系统)开发MT4指标或EA(自动交易系统)需按照标准格式,撰写如下内容文档。而后会评估价格和你联系.联系电子邮件,alantop@qq.com指标或EA的参数是否…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号