首页 > 编程语言 >机器学习——编程实现从零构造训练集的决策树

机器学习——编程实现从零构造训练集的决策树

时间：2024-03-18 14:02:44浏览次数：28  
标签：node 结点 attr self 编程 构造 cal class 决策树

自己搭建一棵决策树【长文预警】

忙了一个周末就写到了“构建决策树”这一步，还没有考虑划分测试集、验证集、“缺失值、连续值”，预剪枝、后剪枝的部分，后面再补吧（挖坑）

目录

1、信息

1）基本算法过程

2）信息熵和信息增益的计算方式

2、做点假设，简化运算

3、拆解算法过程

0）结点类

1）同类样本判断

2）数据集能否再拆解

3）选取最优属性

步骤1

步骤2：

步骤3：

步骤4： 

 步骤5：

4）构造新结点

4、完整的结点类代码

5、完整的构造树的过程

6、建树

1）准备数据集

2）建树

7、绘图查看树的结构

1）绘图代码

2）结果

3）预测

完整的代码指路

DrawPixel/decisionTree.ipynb at main · ndsoi/DrawPixel (github.com)

1、信息

1）基本算法过程

2）信息熵和信息增益的计算方式

2、做点假设，简化运算

 ① 为了选择最优的属性进行划分，我们需要计算信息增益，而计算信息增益需要用到信息：

        1、选取的属性attr有多少种取值？

                (用西瓜分类的例子，考虑属性”纹理“，就有3种取值——”清晰“、”稍糊“和”模糊“）

        2、每种取值有哪些数据?这些数据中有多少是A类别的，又有多少是B类别的..？

                比如对原始数据集考虑”纹理=清晰“的数据，那么有7个是好瓜，有2个是坏瓜

② 计算完信息增益之后，我们选信息增益最大的属性，按照这个属性划分数据集，生成子结点

注意这里的划分数据集，事实上我们在完成①.2问题的时候就已经“划分了”一次数据集，只是我们没有记录下来，类似这样的“冗余”计算有很多，为了尽量减少“重复”计算，我重规划算法的步骤如下：

1、设总共有class_num个类别，假设我们初始化结点node的时候就知道了这个数据集的如下信息：

数据集        self.data

属性集        self.attr

该数据集内样本数量最多的类别        self.max

该数据集内每个类别的样本数量        self.cal_class 是一个列表，每一个元素是|Dv|

2、基于假设1： 

计算Ent(D)：

def Ent(D,cal_class):
  sum = len(D) # 样本总数
  # 求占比
  re = 0
  for k in cal_class:
    pk_class = k/sum
    if pk_class != 0:
      re -= pk_class* math.log(pk_class,2)
  return re

3、拆解算法过程

0）结点类

class Node():
  def __init__(self,D,A,max,cal_class,class_num):
    self.data = D
    self.attr = A
    self.class_num = class_num
    self.cal_class = cal_class

    self.max = max
    self.label = 0 # 0表示非叶结点 1表示叶结点
    self.Class = 0 # 默认一个
    self.flag = "init"

1）同类样本判断

若要判断D中的样本是否同属于一个类别：只需要判断self.max的数量是否等于class_num

  def isSameClass(self):
    if self.cal_class[self.max] == len(self.data):
      return True
    return False

2）数据集能否再拆解

若D中样本不属于同一类，那么接下来要看D中的样本是否还能再分解：

def isNoAttr(self):
    # 属性集为空
    if self.attr == None or self.attr==[]:
      return True,[]
    # 存储取值不同的属性
    self.Attr_Div = []
    for a in self.attr:
      a1 = self.data[0][a]
      for d in self.data:
        if d[a] != a1:
          self.Attr_Div.append(a)
          break
    # 无可分的属性
    if self.Attr_Div == []:
      return True,[]

    return False,self.Attr_Div

3）选取最优属性

从2）中获取了当前node数据集进一步可以分解的属性范围(self.Attr_Div),对于self.Attr_Div中的每一个attr，我们需要做的事情还有：

1. 找出属性attr的所有取值

2. 按照attr的不同取值将self.data划分成互斥的子集Dv_{attr=a1},Dv_{attr_{a_2}}...Dv_{a_n} 简称为Dv

3. 计算|Dv|和 Ent(Dv) 

4. 计算出attr的Gain

5. 重复步骤2-4 计算出所有attr的Gain， 选出Gain最大的attr

步骤1

# 属性attr的取值大全
def attrAllvalue(D,attr):
  Allvalue = {}
  for d in D:
    Allvalue[d[attr]] = 0
  return Allvalue

步骤2：

def divDataByattr(D,attr):
  # 建立一个字典，key是attr的取值，已初始化数值为0
  re = attrAllvalue(D,attr)
  n = len(re) # 要划分出n个子数据集
  SubDataSets = {}
  for key,value in re.items():
    SubDataSets[key] = []
  for d in D:
    SubDataSets[d[attr]].append(d)
  return SubDataSets

divDataByattr获得形如： {'清晰':[数据1,数据2],'模糊':[数据3],'稍糊':[数据4]} 的字典

步骤3：

为了计算Ent(Dv)我们需要获得Dv的cal_class，下列函数计算了数据集子集Dv的max和cal_class

# 获取maxnumClass
def calMaxClass(D,class_num):
  # 统计数据集D中各类样本的数目
  cal_class = [0 for i in range(class_num)]
  max = 0
  for d in D:
    cal_class[d['Class']]+=1
    if cal_class[d['Class']] > cal_class[max]:
      max = d['Class']
  return max,cal_class

步骤4： 

确定一个attr，划分出子集的集合,遍历子集集合，然后调用Ent函数，组合计算（加粗部分就是Gain函数所做的事情）

# 信息增益
def Gain(D,attr,class_info):
  max,cal_class = calMaxClass(D,class_num)
  EntD = Ent(D,cal_class)
  SubDataSets = divDataByattr(D,attr)
  EntDv = 0
  for value,Dv in SubDataSets.items():
    # cal_class
    max,cal_class=calMaxClass(Dv,class_num)
    class_info.append([max,cal_class])
    EntDv +=len(Dv)/len(D)*Ent(Dv,cal_class)
  Gain_D_attr = EntD-EntDv
  return Gain_D_attr

补充：这里的class_info就是记录下每一个Dv的max和cal_class，用于后续传参给node 初始化

 步骤5：

def choseAttr(D,attrSet):
  compar = 0

  Gain_D = {}
  for attr in attrSet:
    SubDataSets = divDataByattr(D,attr)
    EntDv = 0
    # 补充上Dv额外的参数
    class_info = []
    Gain_D_attr = Gain(D,attr,class_info)
    # 记录数据集D用属性attr做划分时所有的已知信息，包括gain，数据子集，数据子集的class_num和max类
    Gain_D[attr] = {'gain':Gain_D_attr,'Dv':SubDataSets,'Dv_info':class_info}

  # 找gain最高的attr
  target = attrSet[0]
  for attr in attrSet:
    if Gain_D[attr]['gain'] > compar:
      compar = Gain_D[attr]['gain']
      target = attr

  return target,Gain_D

4）构造新结点

在完成3）的步骤5后，应该为选定的attr划分的子集生成新结点，新结点

# 选取最优属性
  attr,info = node.bestAttr()
  # 获取划分好的数据集
  SubDataSets = info[attr]['Dv']
  SubInfo = info[attr]['Dv_info']


  # 生成子node
  Attr = copy.deepcopy(Attr_Div)
  Attr.remove(attr)
  st = 0
  for value,subds in SubDataSets.items():
    # 因为假设是离散属性，所以新的self.attr必然要去掉已经选出的attr
    subnodeAttr = copy.deepcopy(Attr)
    # 获取已经算好的Dv的max和cal_class
    submax = SubInfo[st][0]
    subcal_class = SubInfo[st][1]
    st+=1

    # 生成新结点
    subnode = Node(subds,subnodeAttr,submax,subcal_class,class_num)
    subnode.setflag(attr)
    # 新结点还要继续加入tree进行讨论
    tree.put(subnode)

    # 父结点记录子结点的指引
    node.addsubDs(subnode,value)

4、完整的结点类代码

# 说明：
# 设数据集是[{},{},{},...,{}]的格式
# {}的格式是{'attr1':'value1,'attr2':'value2',..,'label':'class'}
# label是结点node：表明其为叶节点还是非叶节点
# Class 是当node为叶结点时，该集合的类别
#
# 类别的数量
class_num = 2
class Node():
  def __init__(self,D,A,max,cal_class,class_num):
    self.data = D
    self.attr = A
    self.class_num = class_num
    self.cal_class = cal_class

    self.max = max
    self.label = 0 # 0表示非叶结点 1表示叶结点
    self.Class = 0 # 默认一个
    self.flag = "init"

  def isSameClass(self):
    if self.cal_class[self.max] == len(self.data):
      return True
    return False

  def isNoAttr(self):
    # 属性集为空
    if self.attr == None or self.attr==[]:
      return True,[]
    # 存储取值不同的属性
    self.Attr_Div = []
    for a in self.attr:
      a1 = self.data[0][a]
      for d in self.data:
        if d[a] != a1:
          self.Attr_Div.append(a)
          break
    # 无可分的属性
    if self.Attr_Div == []:
      return True,[]

    return False,self.Attr_Div



  # 计算选取最优划分属性
  def bestAttr(self):
    # 指向划分的子结点
    self.subDs = {}
    self.bestattr,self.Gain_D = choseAttr(self.data,self.Attr_Div)
    return self.bestattr,self.Gain_D

  def setflag(self,attr):
    self.flag = attr


  # 设置subDs
  def addsubDs(self,node,value):
    self.subDs[value] = node

5、完整的构造树的过程

import copy
import queue

def do_tree(tree):
  node = tree.get()
  print(node.data)

  # 判断D中的类别是不是都是一类
  re = node.isSameClass()

  if re:
    print("当前node都属于同一类别")
    # 如果D中的数据都属于同一个类别
    node.Class = node.max
    node.label = 1 # 标记为叶子结点
    return

  # D中的数据并不属于同一个类别
  # 判断属性是否可分
  boolre,Attr_Div = node.isNoAttr()
  print(f"Attr_Div={Attr_Div}")
  # D中的属性不可再分
  if boolre == True:
    print("当前类别属性不可再分")
    node.label = 1
    node.Class = node.max
    return

  # 选取最优属性
  attr,info = node.bestAttr()
  # 获取划分好的数据集
  SubDataSets = info[attr]['Dv']
  SubInfo = info[attr]['Dv_info']


  # 生成子node
  Attr = copy.deepcopy(Attr_Div)
  Attr.remove(attr)
  st = 0
  for value,subds in SubDataSets.items():
    # 因为假设是离散属性，所以新的self.attr必然要去掉已经选出的attr
    subnodeAttr = copy.deepcopy(Attr)
    # 获取已经算好的Dv的max和cal_class
    submax = SubInfo[st][0]
    subcal_class = SubInfo[st][1]
    st+=1

    # 生成新结点
    subnode = Node(subds,subnodeAttr,submax,subcal_class,class_num)
    subnode.setflag(attr)
    # 新结点还要继续加入tree进行讨论
    tree.put(subnode)

    # 父结点记录子结点的指引
    node.addsubDs(subnode,value)

def TreeGenerate(D,A):
  # 计算初始数据集的max和cal_class
  max,cal_class = calMaxClass(D,class_num)
  # 生成根结点
  node = Node(D,A,max,cal_class,class_num)

  tree = queue.Queue()
  tree.put(node)
  while tree.empty() == False:
    do_tree(tree)
  return node

6、建树

1）准备数据集


dataSet = [
        # 1
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        # 2
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        # 3
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        # 4
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        # 5
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        # 6
        ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
        # 7
        ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
        # 8
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],

        # ----------------------------------------------------
        # 9
        ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
        # 10
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
        # 11
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
        # 12
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
        # 13
        ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
        # 14
        ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
        # 15
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
        # 16
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
        # 17
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
    ]
Attr = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']

# 硬编码类别
class_dict = {'坏瓜':0,'好瓜':1}

# 将数据合并格式
D = []
for i in range(len(dataSet)):
  d = {}
  for j in range(len(Attr)):
    d[Attr[j]] = dataSet[i][j]
  d['Class'] = class_dict[dataSet[i][-1]]
  D.append(d)

print(D)

2）建树

root = TreeGenerate(D,Attr)

7、绘图查看树的结构

1）绘图代码

只是打印每层的结点，通过分支数目得知父子结点的关系

cur = root
# 表示区分的属性

q = queue.Queue()
q.put(cur)
while q.empty()==False:
  # 这层的宽度
  width = q.qsize()
  for i in range(width):
    # 用/**/包住一个node
    print(" /*",end="")
    cur = q.get()
    if cur.label == 1:
      # 叶子结点
      print(f"叶子：{cur.Class,cur.flag,cur.data[0][cur.flag]}",end="")
    else:
      l = len(cur.subDs)
      print(f"被分类依据：{cur.flag}",end="")
      if cur.flag != "init":
        print(f"值:{cur.data[0][cur.flag]}",end="  ")
      print(f",分支：{l}个",end="")

      for key,nod in cur.subDs.items():
        q.put(nod)

    print("*/ ",end="")
  print("")

2）结果

手绘还原：

3）预测

投入一个样本，返回好瓜/坏瓜判断

def predict(data,root):
  cur = root
  while cur.label != 1:
    attr = cur.bestattr
    cur = cur.subDs[data[attr]]
  return cur.Class

for d in D:
  pd_label = predict(d,root)
  if pd_label == 0:
    print("坏瓜")
  else:
    print("好瓜")

结果打印8行好瓜，9行坏瓜

标签：node,结点,attr,self,编程,构造,cal,class,决策树
From： https://blog.csdn.net/m0_60402183/article/details/136788897

相关文章

  • c语言编程题
    1.密码破译要将"China"译成密码，译码规律是：用原来字母后面的第4个字母代替原来的字母。例如，字母"A"后面第4个字母是"E"．"E"代替"A"。因此，"China"应译为"Glmre"。请编一程序，用赋初值的方法使cl、c2、c3、c4、c5五个变量的值分别为，’C’、’h’、’i’、’n’、’a’，经过运算，使c1、......
  • Node+Vue毕设少儿编程教育系统（程序+mysql+Express）
    本系统（程序+源码）带文档lw万字以上 文末可获取本课题的源码和程序系统程序文件列表系统的选题背景和意义选题背景：在当今信息化社会，编程教育逐渐成为儿童素质教育的重要组成部分。越来越多的家长认识到从小培养孩子的计算机思维和编程能力对其未来学习和职业发展的重要性......
  • C++中的this指针、访问控制和构造函数
    C++中的this指针、访问控制和构造函数this指针在C++中，this指针是一个特殊的指针，它指向当前对象的地址。每个非静态成员函数（包括成员函数模板）都有一个this指针作为其隐含参数，这意味着在成员函数内部，this可以用来引用调用该成员函数的对象。this指针是自动传递给成员函数的，......
  • 整块代码自动生成、智能括号匹配……CodeGeeX编程提效，功能再升级！
    CodeGeeX插件功能持续打磨，希望成为开发者更高效的智能编程工具，提高开发速度和代码质量。今天介绍VSCode中最新的v2.4.0版本插件新功能，让你在编写代码时更加得心应手。一、新增block代码块生成的设置CodeGeeX插件中，以往针对代码生成的行数，只有Automatic和Linebyline两种模式。......
  • 在LabVIEW中编程运行可执行程序
    以下文字来自于https://knowledge.ni.com/KnowledgeArticleDetails?id=kA03q000000YGhVCAW&l=en-US翻译来自于ChatGPT3.5 在LabVIEW中，您可以使用SystemExecVI来编程调用可执行文件（*.exe）或应用程序。SystemExecVI接受一个字符串输入，在Windows命令提示符中执行该字符串；要启......
  • C#异步编程：原理与实践
    一、引言在现代应用程序开发中，尤其是在涉及I/O操作（如网络请求、文件读写等）时，异步编程成为了提高性能和用户体验的关键技术。C#作为.NET框架下的主流开发语言，提供了强大的异步编程支持，通过async/await关键字，可以让开发者以同步的方式编写异步代码，极大地简化了异步编程的复杂性。本......
  • Android第一行代码——快速入门 Kotlin 编程（2.5 面向对象编程）
    目录2.5    面向对象编程2.5.1    类与对象2.5.2    继承与构造函数2.5.3    接口2.5.4    数据类与单列类2.5    面向对象编程        和很多现代高级语言一样，Kotlin也是面向对象的，因此理解什么是面向对......
  • 架构知识-编程语言的演进
    架构学习-编程语言的演进前言什么是冯·诺伊曼结构中央处理器存储器输入输出设备汇编语言编程范式的进化1、过程式2、函数式3、面向对象参考架构学习-编程语言的演进前言这里开始来尝试了解下架构层面的知识。什么是冯·诺伊曼结构冯·诺伊曼结构（英语：V......
  • 新书速览|轻松学C++编程：案例教学
    零负担学习C++语言的语法，轻松上手C++面向对象程序设计本书简介The19thAsianGames《轻松学C++编程：案例教学》从初学者的角度循序渐进地从C++语言的基础语法到高级语法进行讲解。全书使用生动的实例和图示，介绍C++面向对象程序设计的基础知识；进而通过案例详解类的高级应......
  • 注入js编程应该知道的一些基础知识，以防混淆造成的错误
    假设我现在用的是chrome extension的方式注入javascript来控制网页，例如有一个元素，原始的网页制作者已经给他注册了各种事件，但是我想得到当这个元素发生改变时，会触发一个我自己能控制的事件，有没有什么办法？要在不干扰原有网页事件的前提下，为元素添加自定义事件处理程序，你可以使用M......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99