英文网站导航 源码,建设一个简单的网站,免费域名注册平台有哪些,公司做网站是管理费用自己搭建一棵决策树【长文预警】
忙了一个周末就写到了“构建决策树”这一步#xff0c;还没有考虑划分测试集、验证集、“缺失值、连续值”#xff0c;预剪枝、后剪枝的部分#xff0c;后面再补吧#xff08;挖坑#xff09;
第二节内容#xff1a;验证集划分\k折交叉…自己搭建一棵决策树【长文预警】
忙了一个周末就写到了“构建决策树”这一步还没有考虑划分测试集、验证集、“缺失值、连续值”预剪枝、后剪枝的部分后面再补吧挖坑
第二节内容验证集划分\k折交叉检验 机器学习——编程从零实现决策树【二】-CSDN博客
目录
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 0for k in cal_class:pk_class k/sumif 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 Dself.attr Aself.class_num class_numself.cal_class cal_classself.max maxself.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 Truereturn False2数据集能否再拆解
若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
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]] 0return Allvalue
步骤2
def divDataByattr(D,attr):# 建立一个字典key是attr的取值已初始化数值为0re 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 0for d in D:cal_class[d[Class]]1if 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 0for value,Dv in SubDataSets.items():# cal_classmax,cal_classcalMaxClass(Dv,class_num)class_info.append([max,cal_class])EntDv len(Dv)/len(D)*Ent(Dv,cal_class)Gain_D_attr EntD-EntDvreturn Gain_D_attr
补充这里的class_info就是记录下每一个Dv的max和cal_class用于后续传参给node 初始化 步骤5
def choseAttr(D,attrSet):compar 0Gain_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最高的attrtarget attrSet[0]for attr in attrSet:if Gain_D[attr][gain] compar:compar Gain_D[attr][gain]target attrreturn target,Gain_D
4构造新结点
在完成3的步骤5后应该为选定的attr划分的子集生成新结点新结点
# 选取最优属性attr,info node.bestAttr()# 获取划分好的数据集SubDataSets info[attr][Dv]SubInfo info[attr][Dv_info]# 生成子nodeAttr copy.deepcopy(Attr_Div)Attr.remove(attr)st 0for value,subds in SubDataSets.items():# 因为假设是离散属性所以新的self.attr必然要去掉已经选出的attrsubnodeAttr copy.deepcopy(Attr)# 获取已经算好的Dv的max和cal_classsubmax SubInfo[st][0]subcal_class SubInfo[st][1]st1# 生成新结点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 Dself.attr Aself.class_num class_numself.cal_class cal_classself.max maxself.label 0 # 0表示非叶结点 1表示叶结点self.Class 0 # 默认一个self.flag initdef isSameClass(self):if self.cal_class[self.max] len(self.data):return Truereturn Falsedef 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_Ddef setflag(self,attr):self.flag attr# 设置subDsdef addsubDs(self,node,value):self.subDs[value] node
5、完整的构造树的过程
import copy
import queuedef do_tree(tree):node tree.get()print(node.data)# 判断D中的类别是不是都是一类re node.isSameClass()if re:print(当前node都属于同一类别)# 如果D中的数据都属于同一个类别node.Class node.maxnode.label 1 # 标记为叶子结点return# D中的数据并不属于同一个类别# 判断属性是否可分boolre,Attr_Div node.isNoAttr()print(fAttr_Div{Attr_Div})# D中的属性不可再分if boolre True:print(当前类别属性不可再分)node.label 1node.Class node.maxreturn# 选取最优属性attr,info node.bestAttr()# 获取划分好的数据集SubDataSets info[attr][Dv]SubInfo info[attr][Dv_info]# 生成子nodeAttr copy.deepcopy(Attr_Div)Attr.remove(attr)st 0for value,subds in SubDataSets.items():# 因为假设是离散属性所以新的self.attr必然要去掉已经选出的attrsubnodeAttr copy.deepcopy(Attr)# 获取已经算好的Dv的max和cal_classsubmax SubInfo[st][0]subcal_class SubInfo[st][1]st1# 生成新结点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_classmax,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):# 用/**/包住一个nodeprint( /*,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 rootwhile cur.label ! 1:attr cur.bestattrcur cur.subDs[data[attr]]return cur.Classfor d in D:pd_label predict(d,root)if pd_label 0:print(坏瓜)else:print(好瓜)结果打印8行好瓜9行坏瓜
