决策树算法的理解及实现

 决策树算法的理解及实现

 

本文基本复制原文来源:http://www.cnblogs.com/lliuye/p/9008901.html,我个人认为已经非常详细了,所有理论基本来自周志华《机器学习》的决策树章节!

我主要是将该博客提供的源码进行了实践与大量注解,以便读者更容易理解。而为了读者方便理解,我将注解提供在源码内。经过源码注解,我已将作者小错误

classCount+=1改成classCount[value]+=1。我将代码附在原理后面,你可以通过debug形式解读代码等,因为代码已经是可以直接运行的,希望对学习机器学习的

决策树算法有帮助。

1. 决策树

  决策树(decision tree)是一种基本的分类与回归方法(本文主要是描述分类方法),是基于树结构进行决策的,可以将其认为是if-then规则的集合。一般的,一棵决策树包含一个根节点若干内部节点若干叶节点。其中根节点包含所有样本点,内部节点作为划分节点(属性测试),叶节点对应于决策结果。

  用决策树进行分类,是从根节点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子节点,若该子节点仍为划分节点,则继续进行判断与分配,直至将实例分到叶节点的类中。

 


  若对以上描述不太明白,可以结合以下图进行理解。


决策树算法的理解及实现

 

  根据以上决策树,现在给你一个实例:{色泽:青绿,根蒂:稍蜷,敲声:清脆,纹理:清晰,脐部:稍凹,触感:光滑},来判断该瓜是否是好瓜。其过程是:脐部(稍凹)-->根蒂(稍蜷)-->色泽(青绿)-->好瓜。

  以上是由决策树来进行分类的过程。而决策树的学习(构建)通常是一个递归地选择最优特征的过程。那么构建决策树时如何选择特征作为划分点(即选择哪个特征作为根节点或者选择哪个特征作为非叶子节点)?当训练数据量大、特征数量较多时构建的决策树可能很庞大,这样的决策树用来分类是否好?

  由这些问题我们可以知道,构建决策树的三个要点:
  (1)特征选择
  (2)决策树的生成
  (3)决策树修剪


2. ID3算法

  基于ID3算法的决策树构建,其选择特征的准则是信息增益。信息增益(information gain)表示得知特征 XX的信息而使得类 YY 的信息的不确定性减少的程度。也就是说,信息增益越大,通过特征 XX ,就越能够准确地将样本进行分类;信息增益越小,越无法准确进行分类。

  在介绍信息增益之前,我们需要先对熵进行一下讲解。

2.1 熵(Entropy)

  熵是度量样本集合纯度最常用的一种指标,它是信息的期望值。我们首先了解一下什么是信息。由《机器学习实战》中定义:

如果待分类的事务可能划分在多个分类之中,则符号(特征) kk 的信息定义为:

l(k)=−log2p(k)l(k)=−log2⁡p(k)
其中 p(k)p(k) 为选择该分类的概率。

 

  而熵计算的是所有类别所有可能值包含的信息期望值,其公式为:

Ent(D)=−∑k=1Np(k)log2p(k)Ent(D)=−∑k=1Np(k)log2⁡p(k)
  其中 NN 为类别个数。

  现在我们使用例子,来理解熵的计算:

 


决策树算法的理解及实现

 

  (1)对于最终分类(是否为好瓜),计算其信息熵:
    由上表可看出,一共有17个样本,属于好瓜的有8个样本,坏瓜的有9个样本,因此其熵为:

Ent(D)=−∑k=12pklog2pk=−(817log2817+917log2917)=0.998Ent(D)=−∑k=12pklog2⁡pk=−(817log2⁡817+917log2⁡917)=0.998
  (2)对于特征“色泽”,计算其信息熵:
    由于特征“色泽”取值有:{青绿,乌黑,浅白}。若使用该属性对 DD 进行划分,可得到3个子集,分别记为: D1D1 (色泽=青绿), D2D2 (色泽=乌黑), D3D3 (色泽=浅白)。

    其中 D1D1 包含样本 1,4,6,10,13,171,4,6,10,13,17 ,其中类别为好瓜的比例为 p1=36p1=36 ,坏瓜的比例为 p2=36p2=36 ; D2D2 包含样本 2,3,7,8,9,152,3,7,8,9,15 ,其中类别为好瓜的比例 p1=46p1=46 ,坏瓜的比例为 p2=26p2=26 ; D3D3 包含样本 5,11,12,14,165,11,12,14,16 ,其中类别为好瓜的比例 p1=15p1=15 ,坏瓜的比例为 p2=45p2=45 ,因此其三个分支点的信息熵为: Ent(D1)=−(36log236+36log236)=1.000Ent(D1)=−(36log2⁡36+36log2⁡36)=1.000 Ent(D2)=−(46log246+26log226)=0.918Ent(D2)=−(46log2⁡46+26log2⁡26)=0.918 Ent(D3)=−(15log215+45log245)=0.722Ent(D3)=−(15log2⁡15+45log2⁡45)=0.722

 

2.2 信息增益(information gain)

  信息增益,由《统计学习方法》中定义:

特征 aa 对训练数据集 DD 的信息增益 Gain(D,a)Gain(D,a) ,定义为集合 DD 的经验熵(即为熵)与特征 aa 给定条件下的经验条件熵 Ent(D|a)Ent(D|a) 之差,即:

Gain(D,a)=Ent(D)−Ent(D|a)Gain(D,a)=Ent(D)−Ent(D|a)
其中特征 aa 将数据集划分为: D1,D2,...,DvD1,D2,...,Dv,而经验条件熵为: Ent(D|a)=∑i=1v|Di||D|Ent(Di)Ent(D|a)=∑i=1v|Di||D|Ent(Di)

  我们根据例子对其进行理解:
  对于特征“色泽”,我们计算其信息增益,由2.1中,集合 DD 的熵为: Ent(D)=0.998Ent(D)=0.998 ,对于特征“色泽”的三个分支点的熵为: Ent(D1)=1.000,Ent(D2)=0.918,Ent(D3)=0.722Ent(D1)=1.000,Ent(D2)=0.918,Ent(D3)=0.722,则“色泽”特征的信息增益为:

Gain(D,色泽)=Ent(D)−∑i=13|Di||D|Ent(Di)=0.998−(617×1.000+617×0.918+517×0.722)=0.109Gain(D,色泽)=Ent(D)−∑i=13|Di||D|Ent(Di)=0.998−(617×1.000+617×0.918+517×0.722)=0.109

 

2.3 算法步骤

  ID3算法递归地构建决策树,从根节点开始,对所有特征计算信息增益,选择信息增益最大的特征作为节点的特征,由该特征的不同取值建立子节点;再对子节点递归地调用以上方法构建决策树;知道所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一个决策树。

  在算法中(C4.5也是),有三种情形导致递归返回:

  (1)当前节点包含的样本全属于同一类别,无需划分。
  (2)当前属性集为空,或是所有样本在所有属性上取值相同,无法划分。(此时将所含样本最多的类别设置为该叶子节点类别)
  (3)当前节点包含的样本集合为空,不能划分。(将其父节点中样本最多的类别设置为该叶子节点的类别)


  输入:训练数据集 DD ,特征集 AA , 阈值 ϵϵ ;
  过程:函数 TreeGenerate(D,A)TreeGenerate(D,A) .
  1:计算节点信息增益 Gain(D,a)Gain(D,a) :
  2:  节点a的熵: Ent(D,a)Ent(D,a)
  3:  节点D的熵: Ent(D)Ent(D)
  4:  节点信息增益: Gain(D,a)=Ent(D)−Ent(D,a)Gain(D,a)=Ent(D)−Ent(D,a)
  5:生成节点node:
  6:if DD 中样本全属于同一类别 CC then
  7:  将node标记为 CC 类叶节点;return
  8:end if
  9:if A=∅A=∅ OR DD 中样本在 AA 上取值相同then
  10:  将node标记为叶节点,期类别标记为 DD 中样本数最多的类;return
  11:end if
  12:按照节点信息增益,从 AA 中选择最优划分属性 a∗a∗
  13:for a∗a∗ 中的每一个值 ai∗a∗i do
  14:  为node生成一个分支;令 DiDi 表示 DD 中在 a∗a∗ 上取值为 ai∗a∗i 的样本子集;
  15:  if DiDi 为空,then
  16:    将分支节点标记为叶节点,其类别标记为 DD 中样本最多的类;return
  17:  else
  18:    以 TreeGenerate(Di,A/a∗)TreeGenerate(Di,A/a∗) 为分支节点
  19:  end if
  20:end for
  输出:以node为根节点的一棵决策树



3. C4.5算法

  实际上,信息增益准则对可取值书目较多的属性有所偏好,例如如果将前面表格中的第一列ID也作为特征的话,它的信息增益将达到最大值,而这样做显然不对,会造成过拟合。为了减少这种偏好可能带来的不利影响,C4.5算法中将采用信息增益比来进行特征的选择。信息增益比准则对可取值数目较少的属性有所偏好。接下来,我们首先对信息增益比进行介绍。

3.1 信息增益比(增益率)

  信息增益比的定义为:

Gain_ratio(D,a)=Gain(D,a)IV(a)Gain_ratio(D,a)=Gain(D,a)IV(a) ,
  其中: IV(a)=−∑i=1v|Di||D|log2|Di||D|IV(a)=−∑i=1v|Di||D|log2⁡|Di||D|
  我们根据例子对其进行理解:

  对于特征“色泽”,我们计算其信息增益比,由2.2计算得 Gain(D,色泽)=0.109Gain(D,色泽)=0.109,而 IV(色泽)=−(617×log2617+617×log2617+517×log2517)=1.580IV(色泽)=−(617×log2⁡617+617×log2⁡617+517×log2⁡517)=1.580
  则 Gain_ratio(D,色泽)=0.1091.580=0.069Gain_ratio(D,色泽)=0.1091.580=0.069。

 

3.2 算法步骤

  C4.5算法同ID3算法过程相似,仅在选择特征时,使用信息增益比作为特征选择准则。


  输入:训练数据集 DD ,特征集 AA , 阈值 ϵϵ ;
  过程:函数 TreeGenerate(D,A)TreeGenerate(D,A) .
  1:计算节点信息增益比 Gainratio(D,a)Gainratio(D,a) :
  2:  节点a的熵: Ent(D,a)Ent(D,a)
  3:  节点D的熵: Ent(D)Ent(D)
  4:  节点信息增益: Gain(D,a)=Ent(D)−Ent(D,a)Gain(D,a)=Ent(D)−Ent(D,a)
  5:  节点固定值: IV(a)IV(a)
  6:  节点信息增益比: Gainratio(D,a)=Gain(D,a)IV(a)Gainratio(D,a)=Gain(D,a)IV(a)
  7:生成节点node:
  8:if DD 中样本全属于同一类别 CC then
  9:  将node标记为 CC 类叶节点;return
  10:end if
  11:if A=∅A=∅ OR DD 中样本在 AA 上取值相同then
  12:  将node标记为叶节点,期类别标记为 DD 中样本数最多的类;return
  13:end if
  14:按照节点信息增益,从 AA 中选择最优划分属性 a∗a∗
  15:for a∗a∗ 中的每一个值 ai∗a∗i do
  16:  为node生成一个分支;令 DiDi 表示 DD 中在 a∗a∗ 上取值为 ai∗a∗i 的样本子集;
  17:  if DiDi 为空,then
  18:    将分支节点标记为叶节点,其类别标记为 DD 中样本最多的类;return
  19:  else
  20:    以 TreeGenerate(Di,A/a∗)TreeGenerate(Di,A/a∗) 为分支节点
  21:  end if
  22:end for
  输出:以node为根节点的一棵决策树



4. 剪枝处理

  针对于在第1部分提到的最后一个问题:当训练数据量大、特征数量较多时构建的决策树可能很庞大,这样的决策树用来分类是否好?答案是否定的。决策树是依据训练集进行构建的,当决策树过于庞大时,可能对训练集依赖过多,也就是对训练数据过度拟合。从训练数据集上看,拟合效果很好,但对于测试数据集或者新的实例来说,并不一定能够准确预测出其结果。因此,对于决策树的构建还需要最后一步----即决策树的修剪。
  决策树的修剪,也就是剪枝操作,主要分为两种:
  (1)预剪枝(Pre-Pruning)
  (2)后剪枝(Post-Pruning)
  接下来我们将详细地介绍这两种剪枝方法。

4.1 预剪枝(Pre-Pruning)

  预剪枝是指在决策树生成过程中,对每个节点在划分前先进行估计,若当前节点的划分不能带来决策树泛化性能的提升,则停止划分并将当前节点标记为叶节点。
  我们使用例子进一步理解预剪枝的过程:
  将本文开始的西瓜数据集表划分成两部分,一部分作为训练集用来构建决策树,一部分作为验证集用来进行决策树的剪枝。具体划分见下图:


决策树算法的理解及实现

 

  使用ID3算法进行决策树的构建,即使用信息增益进行特征的选择。首先选择特征“脐部”作为决策树根节点,如何判断该节点是否需要剪枝,需要对剪枝前后验证集精度进行比较。由“脐部”这个特征将产生三个分支“凹陷”、“稍凹”、“平坦”,并认定其分支结果(可采用多数表决法,当分类数量相当时,任选一类即可),如下图:


决策树算法的理解及实现

 

  查看验证集,若将“脐部”看做节点,并将其标记为“好瓜”,那么划分前的精度为: 37=0.42937=0.429。符合“脐部”=“凹陷”的样本有: 4,5,134,5,13 ,其中正样本(是好瓜)为 4,54,5 ,正样本个数为2,按照上图预测正确数为2;同理“脐部”=“稍凹”的样本中正样本个数为1,预测正确数为1;“脐部”=“平坦”的样本中负样本个数为2,预测正确个数为2。因此使用“脐部”这个特征进行划分,划分后的精度为: 57=0.71457=0.714。由于预测后精度大于预测前精度,因此不对“脐部”进行剪枝,即将其作为划分点进行划分。


决策树算法的理解及实现

 

  同理我们“色泽”以及“根蒂”特征进行划分前后精度的计算。对于“色泽”,划分后的精度为 0.5710.571 ,而划分前为 0.7140.714 ,划分使得结果变差,因此不以该特征进行划分,即将该节点记为叶子节点并标记为“好瓜”;同理“根蒂”特征划分前后的精度都为 0.7140.714 ,效果并未提升,因此也不将该特征进行划分,而是将其作为叶子节点并标记为“好瓜”。由此,决策树构建完毕。此时的决策树为只有一层的树。

  可有由图中看出,该决策树有点过于简单,虽然降低的过拟合的风险,但是由于其基于“贪心”的本质禁止了其它分支的展开,给预剪枝决策树带来了欠拟合的风险。

4.1 后剪枝(Post-Pruning)

  后剪枝是指先从训练集生成一棵完整的决策树,然后自底向上地对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策能力的提升,则将该子树替换成叶节点。
  我们使用例子进一步理解后剪枝的过程:
  同样适用4.1中的划分数据集。针对已建立好的决策树,我们首先对“纹理”特征节点进行处理,判断其是否需要剪枝,见下图。


决策树算法的理解及实现

 

  首先,使用整个决策树对验证集进行预测,并将其预测结果与真实结果进行对比,可得到如下结果(预测结果与真实结果相同,标记为“正确”,否则标记为“不正确”):

{(4,正确),(5,不正确),(8,不正确),(9,不正确),(11,正确),(12,正确),(13,不正确)}{(4,正确),(5,不正确),(8,不正确),(9,不正确),(11,正确),(12,正确),(13,不正确)}
  首先我们判断是否需要对“纹理”进行剪枝:剪枝前精确度由上结果可以得到为 37=0.42937=0.429 ,剪枝后(即将该节点标记为“好瓜”),此时对于样本 ((8,正确))((8,正确)) ,其它样本结果不变,其精度提升到 47=0.57147=0.571 ,因此对该节点进行剪枝。对节点5“色泽”,剪枝前精确度为 0.5710.571 ,剪枝后仍旧为 0.5710.571 ,对此我们可以不进行剪枝(但在实际情况下仍旧会需要剪枝);同理对“根蒂”、节点2“色泽”进行计算,所得结果见上图。由此得到后剪枝决策树。

  后剪枝决策树通常比预剪枝决策树保留了更多的分支,一般情况下,后剪枝决策树欠拟合的风险很小,其泛化能力往往优于预剪枝预测数。但由于其是基于创建完决策树之后,再对决策树进行自底向上地剪枝判断,因此训练时间开销会比预剪枝或者不剪枝决策树要大。

 

 

 

代码如下:

 


# -*- coding:utf-8 -*-
from math import log
import operator

# C4.5算法与ID3算法仅有细微差别,其差别与代码在注释中体现
# #-------------------------------------构造决策树-----------------------------------------
# 计算给定数据集的香农熵
def calcShannonEnt(dataSet):
'''
:param dataSet: 样本第一维度是样本个数,最后一个维度是每个样本的类别
:return: 计算出每个类别的香浓熵
'''
numEntries = len(dataSet) # 计算样本个数
labelCounts = {} # 用来统计每个标签的个数,如有3类,0类4个,1类5个,3类32个,则{0:4,1:5,2:32}
for featVec in dataSet: # 遍历样本
currentLabel = featVec[-1] # currentLabel保存分类标签 数据集最后一个为类别
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannanEnt = 0.0
# shannonEnt = -(求和)[p(xi)log(2,p(xi))]
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
# 以2为底求对数
shannanEnt -= prob * log(prob, 2)
return shannanEnt

# 按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
'''
:param dataSet: 数据集
:param axis: 想要删掉的列
:param value: 判断axis列删掉的值是否等于value,否则不能删除。原因在于该
chooseBestFeatureToSplit函数将每个列循环,而value将某列值循环,这样就可以排除
axis列的值不再value中而删除了。
:return: 返回一个axis列满足value值的新数据,如[array([21., 1., 61.]), array([ 17., 41., 1.]),
'''
# 将dataSet中满足dataSet[axis] = value的行进行保留,
# retDataSet中存储了保留行中除了axis列之外的其它列
retDataSet = []
for featVec in dataSet:
# 除掉featVec[axis]列的内容
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
# extend() 函数用于在列表末尾一次性追加另一个序列中的多个值(用新列表扩展原来的列表)
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet

# 遍历数据集,循环计算香农熵和splitDataSet()函数,
# 找到最好的划分方式(计算所有特征的信息增益,并进行比较选出最优的特征)
def chooseBestFeatureToSplit(dataSet):
'''
该函数执行一次便可以选择一个最好的节点
:param dataSet: 需要筛选节点时候的所有数据集和,
行表示样本数,列最后一列表示最终分类,其它列为属性值,
每个属性可能包含多个特征
:return: 返回最好的节点序号,如第3列属性最好,便返回3.(0列属性也包含)
'''
# 计算总特征数,数据集最后一列为分类标签。dataSet[0]是指第一条数据
numFeatures = len(dataSet[0]) - 1 # 排除最后一列的干扰
# 按照分类标签计算香农熵
# baseEntropy为经验熵H(D)
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeaature = -1
# 创建唯一的feature取值列表(分别对每个feature进行),对每个唯一feature值划分一次数据集
for i in range(numFeatures):
featList = [example[i] for example in dataSet] # 得到dataSet数据集中第i列所有值,集第i个属性
uniqueVals = set(featList) # 第i个属性不同特征的集合,排除相同的特征
newEntropy = 0.0 # newEntropy为经验条件熵H(D|A)
# 计算每种划分方式的信息熵,并求该feature熵和
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
# subDataSet是feature[i]=value的所有条目的列表(不包含feature[i])
# len(subDataSet)表示feature[i]=value的条目总数
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
# (C4.5)分裂信息:splitInfo
# splitInfo -= prob * log(prob, 2)
# 信息增益:g(D,A) = H(D) - H(D|A)
inforGain = baseEntropy - newEntropy
# (C4.5)信息增益率
# inforGainRate = inforGain / splitInfo
if inforGain > bestInfoGain:
bestInfoGain = inforGain
bestFeaature = i
return bestFeaature


def majorityCnt(classList):
'''
该函数是构建决策树停止条件之一,当数据集只剩下最后一列的标签时候,
会出现多个标签,则“投票法”,将选择标签最多的一个为最终标签
:param classList: 为最终标签类的一列
:return: 返回一个最终标签
'''
classCount = {} # 保存数据集classList每个类别的数量
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True) # 默认为从小到大
'''
a = [1,2,3] 
>>> b=operator.itemgetter(1)      //定义函数b,获取对象的第1个域的值
>>> b(a) 

>>> b=operator.itemgetter(1,0)   //定义函数b,获取对象的第1个域和第0个的值
>>> b(a) 
(2, 1) 
'''
return sortedClassCount[0][0] # 返回数量最多类的名字

# 创建树的函数代码
def createTree(dataSet, labels):
'''
:param dataSet: (m,n)表示m行n列,第0--(n-1)列表示属性,
第n列表示每个样本的分类结果,属于哪一类。
:param labels: 是属性对应的标签,如有3个属性分别为第0、1、2列,
那标签应为['颜色','纹理','触感']
:return:函数返回的是myTree,则在myTree[bestFeatLabel][value]建立
myTree = {bestFeatLabel: {}},一直在myTree[bestFeatLabel][value]建立
'''

classList = [example[-1] for example in dataSet] # 创建样本类别标签列表

# 下面的代码用最终分类即标签判断是否停止循环
if classList.count(classList[0]) == len(classList): # 类别完全相同则停止继续划分
# classList.count(classList[0])表示该列classList中第一名字的数量
return classList[0] # 返回最终的结果
# 遍历完所有特征时,返回出现次数最多的类别(dataset中只剩下一列类别)
if len(dataSet[0]) == 1:
# 表示只剩下类别了,这里处理最后一个节点应该给最终标签是什么。
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet) # 得到dataSet数据集中最好的属性作为节点,为数字型式
bestFeatLabel = labels[bestFeat] # 该属性作为节点的名字
myTree = {bestFeatLabel: {}} # 建立最好的属性值为空
del(labels[bestFeat]) # 删除该节点
# 得到列表包含的所有属性值
featValues = [example[bestFeat] for example in dataSet] # 得到bestFeat列所有值
uniqueVals = set(featValues) # 得到bestFeat列的属性值
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] =\
createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
# 已经是新的数据集了 新的标签
return myTree # 返回值是myTree





# 简单测试数据集
def createDataSet():
dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
labels = ['no surfacing','flippers']
return dataSet, labels






#-------------------------------------构建分类器-----------------------------------------

def classify(inputTree, featLabels, testVec):
'''
:param inputTree: 输入的是树的结构,以字典形式给出
:param featLabels: 输入测试数据的属性,要有训练数据的属性
:param testVec: 测试数据,直接为1列,只有属性没有最终的类
:return: 返回了最终的分类属性
'''
firstStr = list(inputTree.keys())[0] # 树的第一个节点的名字
restDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr) # 得到树firstStr节点对应的属性
'''
若树为{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
firstStr就是得到树的第一个节点的名字no surfacing
restDict就是得到'no surfacing'的其它字典,形式为
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
featIndex 在labels找到对应的标签
'''
for key in restDict.keys():
if testVec[featIndex] == key:
# testVec 测试数据集在featIndex下只有一个值
if type(restDict[key]).__name__ == 'dict':
classLabel = classify(restDict[key], featLabels, testVec)
else:
classLabel = restDict[key] # 因为这里只剩下该key键值的一个最终类
return classLabel # 返回了最终的分类属性



#-------------------------------------存储决策树(避免每次分类时都需要重新构建)-----------------------------------------
def storeTree(inputTree, filename):
'''
:param inputTree: 输入树的字典
:param filename: 需要保存的文件路径
'''
import pickle
# fw = open(filename, "w")
fw = open(filename, "wb+")
pickle.dump(inputTree, fw)
fw.close()


def grabTree(filename):
'''
:param filename: 从文件中读取字典
:return:
'''
import pickle
fr = open(filename, "rb+")
return pickle.load(fr)



if __name__ == '__main__':
# 构建训练数据集
dataSet, labels = createDataSet()
# 训练模型生成决策树
decision_tree_dict = createTree(dataSet, labels)
print(decision_tree_dict) # 打印决策树,为字典类型保存
# 构建测试数据集
featLabels=['no surfacing','flippers']
testVec=[0,1]
# 采用下面的分类函数,就可以对测试数据进行分类了
test_result=classify(decision_tree_dict, featLabels, testVec)
print(test_result) # 打印最终测试结果

 

结果如下:

 

决策树算法的理解及实现

 

 

最后:本人仅仅对代码进行了改动与详细的注解,感谢下方博客作者的提供,若有所见解或异议可在下方评论,谢谢!
原文来源http://www.cnblogs.com/lliuye/p/9008901.html

上一篇:AutoCAD 实体添加超级链接


下一篇:决策树的公式推导——ID3