首先从两幅图中导入什么是决策树。
是否学习的决定过程
决策树是模仿树的结构进行决策的,例如在上图中,就“是否学习”的问题进行决策时,通常伴随着一系列的子决策。 首先,是否有“对象”,如果有,是否需要“陪伴对象”,经过一次次子的决策后得到最终的决策。 是不是学习。
通常,一个决策树包含根节点、几个内部节点和几个叶节点。 如下图所示,与是否学习的决定过程相对应,“女票”为根节点,“与她交往”为“任务”,“吃鸡”为内部节点,最底层为叶节点。
决策树节点图
决策树算法的第一种常用机器学习方法在分类任务中经常使用,从给定的训练数据集学习用于分类新例子的模型。 决策树需要两个数据。
培训数据:用于建立决策树,即决策机制
测试数据:验证构建的决策树的错误率
决策树学习算法的伪代码如下所示:
决策树学习算法伪代码
这里用具体的小例子说明决策树算法
数据是一组简单判别生物是否为鱼类的数据集,通过分析以下数据建立决策树:
序列号
不上浮能否生存
有蹼吗
属于鱼类
1
是
是
是
2
是
是
是
3
是
不
不
4
不
是
不
5
不
不
不
第一步是数据处理
defdataset(:
数据=[ 1,1,' yes']、[ 1,1,' yes']、[ 1,0,' no']、[ 0,1,' no']、[ 0,0,' no']#数据集
labels=['no surfacing ',' flipper']
返回数据,标签
defsplitdata (数据、原始、标签) : #按特定属性划分数据集
Dataset=[]
for data in dataset:
if data[row]==label:
reducedata=data[:row]
reducedata.extend (data [ row 1: ]
dataset.append (冗馀数据) ) ) ) ) )。
返回数据集
伪代码的第8行是决策树建模的重要一步,那么如何选择最佳的划分属性呢? 希望随着分割过程的进行,决策树分支节点中包含的样本尽可能属于同一类别,即节点纯度越来越高。 一般的方法是利用信息增益。
在介绍信息增益之前,引入信息熵这一概念
信息熵
信息熵
ent(d )是信息熵,其中pk是样本集合d中第k类样本所占的比例,ent(d )的值越小,表示该样本集合d的纯度越高。
信息增益
信息增益
假设属性a具有v个可能值,当由a划分样本集时,产生v个分支节点,并且Dv是包括在第v个分支中的样本。 上述公式可以计算通过利用属性a分割样本组d而获得的信息增益。 信息增益越大,用属性a分类样品的纯度越高。 因此,选择信息增益最大的属性进行分割。 具体代码实现如下
defshannonent (数据) : #信息熵的计算
lens=len (数据集)
count={}
for data in dataset:
key=data[-1]
count[key]=count.get(key,0 ) 1
Ent=0
for key in count:
prob=count[key]/lens
ent-=prob*log(prob,2 ) ) ) ) ) ) ) ) )。
返回事件
选择defchoosefeature(dataset ) : #最佳分区属性
lens=len (数据set [0]-1
bestfeature=-1
输入=Shannon ent (dataset )
bestInfo=0
forIinrange(lens ) :
eaturelist=set ([ example [ I ] forexampleindataset ]
新企业=0
for j in featurelist:
数据=split data (数据,I,j ) )。
prob=len (数据)/len (数据) )。
新企业--=prob * Shannon ent (数据) ) )。
infoGain=entropy Newentropy
信息基础设施(if ) :
bestInfo=infoGain
bestfeature=i
返回基本功能
开始构建和测试决策树。
efcreatetree (数据,标签) :
class list=[ example [-1 ] forexampleindataset ]
与ifclasslist.count(classlist[0] )==len (class list ) : #类别相同的停止分类
返回类列表[0]
bestfeature=choose feature (dataset ) () ) ) ) ) )。
最佳标签=labels [ best feature ]
my tree={最佳标签: { } }
戴尔(labels [ bestfeature ]
获取tags=set ([ example [ bestfeature ] forexampleindataset ] )列表中包含的所有属性
for tag in tags:
my tree [ best label ] [ tag ]=creat tree (分割数据(dataset,bestfeature,tag ),labels ) ) )。
返回我的树
打印(创建树(数据,标签) )打印树结构
ef classify (数据、标签、测试) : #测试
first=list(data.keys () () ) )0) ) ) ) ) )。
second=data[first] # {0: 'no ',1:{'flipper':'no ',1: 'yes'}}}
fatindex=labels.index(first ) # 0
for key in second.keys () :
if test[featIndex]==key:
if type (second [ key ]._ _ name _==' dict ' :
class label=classify (第二个[ key ],labels,test ) )。
else:
classlabel=second[key]
返回类标签
以上是我对决策树的理解。 如果有错误的话,请指出来。