首先通过两个图来引入什么是决策树。
是否学习的决策过程
决策树是仿树结构来进行决策的，例如上图来说，我们要对‘是否学习’这个问题进行决策时，通常伴随一系列的子决策。先看是否有‘对象’，有的话是否需要‘陪伴对象’，通过一次次子决策后得到最终决策：是否学习。
一般情况下，一棵决策树包含一个根节点，若干内部节点和若干叶节点，如下图所示，那么与是否学习的决策过程对应起来，‘女票’为根节点,'陪女友'和‘任务’‘吃鸡’为内部节点，最下面一层为叶子节点。
决策树节点图
决策树算法第一种常见的机器学习方法，常用于分类任务中，从给定的训练数据集中学习到一个模型用于对新示例进行分类。决策树需要两部分数据：
- 训练数据：用于构造决策树，即决策机制
-
测试数据：验证所构造决策树的错误率
下面给出决策树学习算法伪代码：
决策树学习算法伪代码
下面我们以一个具体的小实例来讲解决策树算法
数据为一个简单的判别生物是否为鱼类的数据集，通过对下面数据进行分析，建立决策树。
| 序号 | 不浮出水面是否可以生存 | 是否有脚蹼 | 属于鱼类 |
|---|---|---|---|
| 1 | 是 | 是 | 是 |
| 2 | 是 | 是 | 是 |
| 3 | 是 | 否 | 否 |
| 4 | 否 | 是 | 否 |
| 5 | 否 | 否 | 否 |
第一步是数据处理
def Dataset():
data=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,0,'no']] #数据集
labels=['no surfacing','flipper']
return data,labels
def splitdata(dataset,row,label): #按照特定属性划分数据集
Dataset=[]
for data in dataset:
if data[row]==label:
reducedata=data[:row]
reducedata.extend(data[row+1:])
Dataset.append(reducedata)
return Dataset
伪代码的第8行是决策树建模很关键的一步，那么如何选择最优划分属性的呢？我们希望伴随着划分过程进行时，决策树分支节点所包含 样本尽可能属于同一类别，即节点的纯度越来越高。一般常用方法是利用信息增益。
在介绍信息增益之前先引入一个概念--信息熵
信息熵
信息熵
Ent(D)就是信息熵，其中pk为样本集合D中第k类样本所占比例，Ent(D)的值越小，就代表该样本集D的纯度越高。
信息增益
信息增益
假设属性a有V个可能取值，那么用a来对样本集进行划分，就会产生V个分支节点，Dv是第v个分支所包含的样本。上式就可计算出用属性a对样本集D进行划分所获得的信息增益。信息增益越大，用属性a对样本进行划分的纯度越高。所以选择使得信息增益最大的属性进行划分。具体代码实现如下：
def shannonEnt(dataset): #计算信息熵
lens=len(dataset)
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)
return Ent
def choosefeature(dataset): #选择最优划分属性
lens=len(dataset[0])-1
bestfeature=-1
entropy=shannonEnt(dataset)
bestInfo=0
for i in range(lens):
featurelist=set([example[i] for example in dataset])
Newentropy=0
for j in featurelist:
Data=splitdata(dataset,i,j)
Prob=len(Data)/len(dataset)
Newentropy-=Prob*shannonEnt(Data)
infoGain=entropy+Newentropy
if(infoGain>bestInfo):
bestInfo=infoGain
bestfeature=i
return bestfeature
下面就开始构建决策树并进行测试：
def createtree(dataset,labels):
classlist=[example[-1] for example in dataset]
if classlist.count(classlist[0])==len(classlist): #类别相同停止划分
return classlist[0]
bestfeature=choosefeature(dataset)
bestlabel=labels[bestfeature]
myTree={bestlabel:{}}
del(labels[bestfeature])
tags=set([example[bestfeature] for example in dataset]) #得到列表所包含的所有属性
for tag in tags:
myTree[bestlabel][tag]=creattree(splitdata(dataset,bestfeature,tag),labels)
return myTree
print(createtree(data,labels))#打印树结构
def classify(data,labels,test): #测试
first = list(data.keys())[0]
second = data[first] # {0: 'no', 1: {'flipper': {0: 'no', 1: 'yes'}}}
featIndex = labels.index(first) # 0
for key in second.keys():
if test[featIndex]==key:
if type(second[key]).__name__=='dict':
classlabel=classify(second[key],labels,test)
else:
classlabel=second[key]
return classlabel
以上为我对决策树的理解，如有错误，请指正。
