0
0

【人工智能与机器学习】决策树ID3及其python实现

文章目录

1 决策树算法

决策树（Decision Tree)是一类常见的机器学习方法，是一种非常常用的分类方法，它是一种监督学习。常见的决策树算法有ID3，C4.5、C5.0和CART（classification and regression tree），CART的分类效果一般要优于其他决策树。

决策树是基于树状结构来进行决策的，一般地，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。

每个内部节点表示一个属性上的判断
每个分支代表一个判断结果的输出
每个叶节点代表一种分类结果。
根节点包含样本全集
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略。

本文主要介绍ID3算法，ID3算法的核心是根据信息增益来选择进行划分的特征，然后递归地构建决策树。

1.1 特征选择

特征选择也即选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。 随着划分过程不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

1.2 熵（entropy）

熵表示事务不确定性的程度，也就是信息量的大小（一般说信息量大，就是指这个时候背后的不确定因素太多），熵的公式如下：

其中， p(xi)是分类 xi 出现的概率，n是分类的数目。可以看出，熵的大小只和变量的概率分布有关。
对于在X的条件下Y的条件熵，是指在X的信息之后，Y这个变量的信息量（不确定性）的大小，计算公式如下：

例如，当只有A类和B类的时候，p(A)=p(B)=0.5，熵的大小为：

当只有A类或只有B类时，

所以当Entropy最大为1的时候，是分类效果最差的状态，当它最小为0的时候，是完全分类的状态。因为熵等于零是理想状态，一般实际情况下，熵介于0和1之间 。

熵的不断最小化，实际上就是提高分类正确率的过程。

1.3 信息增益

信息增益：在划分数据集之前之后信息发生的变化，计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

定义属性A对数据集D的信息增益为infoGain(D|A)，它等于D本身的熵，减去 给定A的条件下D的条件熵，即：

信息增益的意义：引入属性A后，原来数据集D的不确定性减少了多少。

计算每个属性引入后的信息增益，选择给D带来的信息增益最大的属性，即为最优划分属性。一般，信息增益越大，则意味着使用属性A来进行划分所得到的的“纯度提升”越大。

2 ID3算法的python实现

以西瓜数据集为例
·watermalon.csv·文件内容如下：

读取文件数据

  1. import numpy as np
  2. import pandas as pd
  3. import math
  4. data = pd.read_csv('work/watermalon.csv')
  5. data


计算熵

  1. definfo(x,y):if x != y and x !=0:# 计算当前情况的熵return-(x/y)*math.log2(x/y)-((y-x)/y)*math.log2((y-x)/y)if x == y or x ==0:# 纯度最大，熵值为0return0
  2. info_D = info(8,17)
  3. info_D

结果为：
0.9975025463691153

计算信息增益

  1. # 计算每种情况的熵
  2. seze_black_entropy =-(4/6)*math.log2(4/6)-(2/6)*math.log2(2/6)
  3. seze_green_entropy =-(3/6)*math.log2(3/6)*2
  4. seze_white_entropy =-(1/5)*math.log2(1/5)-(4/5)*math.log2(4/5)# 计算色泽特征色信息熵
  5. seze_entropy =(6/17)*seze_black_entropy+(6/17)*seze_green_entropy+(5/17)*seze_white_entropy
  6. print(seze_entropy)# 计算信息增益
  7. info_D - seze_entropy

结果为：
0.10812516526536531

查看每种根蒂中好坏瓜情况的分布情况

  1. data.根蒂.value_counts()# 查看每种根蒂中好坏瓜情况的分布情况print(data[data.根蒂=='蜷缩'])print(data[data.根蒂=='稍蜷'])print(data[data.根蒂=='硬挺'])

  1. gendi_entropy =(8/17)*info(5,8)+(7/17)*info(3,7)+(2/17)*info(0,2)
  2. gain_col = info_D - gendi_entropy
  3. gain_col

根蒂的信息增益为：0.142674959566793

查看每种敲声中好坏瓜情况的分布情况

  1. data.敲声.value_counts()# 查看每种敲声中好坏瓜情况的分布情况print(data[data.敲声=='浊响'])print(data[data.敲声=='沉闷'])print(data[data.敲声=='清脆'])
  2. qiaosheng_entropy =(10/17)*info(6,10)+(5/17)*info(2,5)+(2/17)*info(0,2)
  3. info_gain = info_D - qiaosheng_entropy
  4. info_gain


查看每种纹理中好坏瓜情况的分布情况

  1. data.纹理.value_counts()# 查看每种纹理中好坏瓜情况的分布情况print(data[data.纹理=="清晰"])print(data[data.纹理=="稍糊"])print(data[data.纹理=="模糊"])
  2. wenli_entropy =(9/17)*info(7,9)+(5/17)*info(1,5)+(3/17)*info(0,3)
  3. info_gain = info_D - wenli_entropy
  4. info_gain


同理查看其他列的分布情况，这里不做演示

绘制可视化树

  1. import matplotlib.pylab as plt
  2. import matplotlib
  4. # 能够显示中文
  5. matplotlib.rcParams['font.sans-serif']=['SimHei']
  6. matplotlib.rcParams['font.serif']=['SimHei']# 分叉节点，也就是决策节点
  7. decisionNode =dict(boxstyle="sawtooth", fc="0.8")# 叶子节点
  8. leafNode =dict(boxstyle="round4", fc="0.8")# 箭头样式
  9. arrow_args =dict(arrowstyle="<-")defplotNode(nodeTxt, centerPt, parentPt, nodeType):"""
  10.     绘制一个节点
  11.     :param nodeTxt: 描述该节点的文本信息
  12.     :param centerPt: 文本的坐标
  13.     :param parentPt: 点的坐标，这里也是指父节点的坐标
  14.     :param nodeType: 节点类型,分为叶子节点和决策节点
  15.     :return:
  16.     """
  17.     createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
  18.                             xytext=centerPt, textcoords='axes fraction',
  19.                             va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)defgetNumLeafs(myTree):"""
  20.     获取叶节点的数目
  21.     :param myTree:
  22.     :return:
  23.     """# 统计叶子节点的总数
  24.     numLeafs =0# 得到当前第一个key，也就是根节点
  25.     firstStr =list(myTree.keys())[0]# 得到第一个key对应的内容
  26.     secondDict = myTree[firstStr]# 递归遍历叶子节点for key in secondDict.keys():# 如果key对应的是一个字典，就递归调用iftype(secondDict[key]).__name__ =='dict':
  27.             numLeafs += getNumLeafs(secondDict[key])# 不是的话，说明此时是一个叶子节点else:
  28.             numLeafs +=1return numLeafs
  30. defgetTreeDepth(myTree):"""
  31.     得到数的深度层数
  32.     :param myTree:
  33.     :return:
  34.     """# 用来保存最大层数
  35.     maxDepth =0# 得到根节点
  36.     firstStr =list(myTree.keys())[0]# 得到key对应的内容
  37.     secondDic = myTree[firstStr]# 遍历所有子节点for key in secondDic.keys():# 如果该节点是字典，就递归调用iftype(secondDic[key]).__name__ =='dict':# 子节点的深度加1
  38.             thisDepth =1+ getTreeDepth(secondDic[key])# 说明此时是叶子节点else:
  39.             thisDepth =1# 替换最大层数if thisDepth > maxDepth:
  40.             maxDepth = thisDepth
  42.     return maxDepth
  44. defplotMidText(cntrPt, parentPt, txtString):"""
  45.     计算出父节点和子节点的中间位置，填充信息
  46.     :param cntrPt: 子节点坐标
  47.     :param parentPt: 父节点坐标
  48.     :param txtString: 填充的文本信息
  49.     :return:
  50.     """# 计算x轴的中间位置
  51.     xMid =(parentPt[0]-cntrPt[0])/2.0+ cntrPt[0]# 计算y轴的中间位置
  52.     yMid =(parentPt[1]-cntrPt[1])/2.0+ cntrPt[1]# 进行绘制
  53.     createPlot.ax1.text(xMid, yMid, txtString)defplotTree(myTree, parentPt, nodeTxt):"""
  54.     绘制出树的所有节点，递归绘制
  55.     :param myTree: 树
  56.     :param parentPt: 父节点的坐标
  57.     :param nodeTxt: 节点的文本信息
  58.     :return:
  59.     """# 计算叶子节点数
  60.     numLeafs = getNumLeafs(myTree=myTree)# 计算树的深度
  61.     depth = getTreeDepth(myTree=myTree)# 得到根节点的信息内容
  62.     firstStr =list(myTree.keys())[0]# 计算出当前根节点在所有子节点的中间坐标,也就是当前x轴的偏移量加上计算出来的根节点的中心位置作为x轴（比如说第一次：初始的x偏移量为：-1/2W,计算出来的根节点中心位置为：(1+W)/2W，相加得到：1/2），当前y轴偏移量作为y轴
  63.     cntrPt =(plotTree.xOff +(1.0+float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)# 绘制该节点与父节点的联系
  64.     plotMidText(cntrPt, parentPt, nodeTxt)# 绘制该节点
  65.     plotNode(firstStr, cntrPt, parentPt, decisionNode)# 得到当前根节点对应的子树
  66.     secondDict = myTree[firstStr]# 计算出新的y轴偏移量，向下移动1/D，也就是下一层的绘制y轴
  67.     plotTree.yOff = plotTree.yOff -1.0/plotTree.totalD
  69.     # 循环遍历所有的keyfor key in secondDict.keys():# 如果当前的key是字典的话，代表还有子树，则递归遍历ifisinstance(secondDict[key],dict):
  70.             plotTree(secondDict[key], cntrPt,str(key))else:# 计算新的x轴偏移量，也就是下个叶子绘制的x轴坐标向右移动了1/W
  71.             plotTree.xOff = plotTree.xOff +1.0/plotTree.totalW
  72.             # 打开注释可以观察叶子节点的坐标变化# print((plotTree.xOff, plotTree.yOff), secondDict[key])# 绘制叶子节点
  73.             plotNode(secondDict[key],(plotTree.xOff, plotTree.yOff), cntrPt, leafNode)# 绘制叶子节点和父节点的中间连线内容
  74.             plotMidText((plotTree.xOff, plotTree.yOff), cntrPt,str(key))# 返回递归之前，需要将y轴的偏移量增加，向上移动1/D，也就是返回去绘制上一层的y轴
  75.     plotTree.yOff = plotTree.yOff +1.0/plotTree.totalD
  77. defcreatePlot(inTree):"""
  78.     需要绘制的决策树
  79.     :param inTree: 决策树字典
  80.     :return:
  81.     """# 创建一个图像
  82.     fig = plt.figure(1, facecolor='white')
  83.     fig.clf()
  84.     axprops =dict(xticks=[], yticks=[])
  85.     createPlot.ax1 = plt.subplot(111, frameon=False,**axprops)# 计算出决策树的总宽度
  86.     plotTree.totalW =float(getNumLeafs(inTree))# 计算出决策树的总深度
  87.     plotTree.totalD =float(getTreeDepth(inTree))# 初始的x轴偏移量，也就是-1/2W，每次向右移动1/W，也就是第一个叶子节点绘制的x坐标为：1/2W，第二个：3/2W，第三个：5/2W，最后一个：(W-1)/2W
  88.     plotTree.xOff =-0.5/plotTree.totalW
  89.     # 初始的y轴偏移量，每次向下或者向上移动1/D
  90.     plotTree.yOff =1.0# 调用函数进行绘制节点图像
  91.     plotTree(inTree,(0.5,1.0),'')# 绘制
  92.     plt.show()if __name__ =='__main__':
  93.     createPlot(mytree)

总结

决策树ID3是一种经典的机器学习算法，用于解决分类问题。它通过在特征空间中构建树形结构来进行决策，并以信息增益作为划分标准。ID3算法的关键在于选择最佳的属性进行划分，以最大化信息增益。通过Python实现ID3算法，我们可以构建出一棵高效而准确的决策树模型，用于分类预测和决策分析。

参考
https://zhuanlan.zhihu.com/p/133846252
https://cuijiahua.com/blog/2017/11/ml_2_decision_tree_1.html
https://blog.csdn.net/tauvan/article/details/121028351

标签： 人工智能 机器学习 决策树
本文转载自: https://blog.csdn.net/apple_52030329/article/details/131501100
版权归原作者 日常脱发的小迈 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【人工智能与机器学习】决策树ID3及其python实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？