当前位置:   article > 正文

决策树代码详解——真正地一行一行来解读_决策树代码复杂吗

决策树代码复杂吗

因为决策树代码构建有点复杂,整体贴上来会显得有点难懂,所以我们在这里将从每个函数开始一点一点进行讲解,最后把这些函数按顺序复制到程序里就能运行:

首先是第一个函数:生成数据集。

  1. def createDataSet():
  2. dataSet = [[1, 1, 1, 'yes'],
  3. [1, 0, 1, 'yes'],
  4. [1, 0, 2, 'no'],
  5. [0, 1, 2, 'no'],
  6. [0, 1, 2, 'no'],
  7. [1, 1, 2, 'yes'],
  8. [0, 0, 2, 'yes'],
  9. [0, 1, 0, 'no'],
  10. ]
  11. labels = ['ddddd','fffff','sssss']
  12. #change to discrete values
  13. return dataSet, labels
'
运行

这个函数没啥可说的了,就是先建立一个数据集,里面每行数据代表一个样本,每个样本的前三个数据代表三个特征,第四个数据代表样本的分类。下面的标签表示每个样本的这三个特征分别是啥。这里为了省事直接用几个字母代替了。

然后是第二个函数:计算信息熵。

  1. # 计算信息熵
  2. def calcShannonEnt(dataSet):
  3. numEntries = len(dataSet) # 样本数
  4. labelCounts = {} #构建一个字典
  5. for featVec in dataSet: # 遍历每个样本
  6. currentLabel = featVec[-1] # 当前样本的类别
  7. if currentLabel not in labelCounts.keys(): # 生成类别字典
  8. labelCounts[currentLabel] = 0
  9. labelCounts[currentLabel] += 1
  10. shannonEnt = 0.0
  11. for key in labelCounts: # 计算信息熵
  12. prob = float(labelCounts[key]) / numEntries
  13. shannonEnt -= prob * log(prob, 2)
  14. return shannonEnt
'
运行

我们来分析一下这个函数。首先它输入一个数据集,就用上面的函数返回的dataSet就好了。

然后我们先计算出样本数,并采用中括号构建一个字典。

然后遍历每个样本,featVec[-1]表示每个样本中的数据的最后一个数据的值,也就是分类用的类别,在我们的数据集里分别是yes和no。如果该类别在字典里没有,则说明是一个新类别,然后我们就让字典包含该类别。然后数值+1。

在我们的例子中,我们先读到第一个数据 [1, 1, 1, 'yes'],此时字典还是空的,所以我们把yes放入字典里,然后yes的值+1。

紧接着我们读到第二个数据:[1, 0, 1, 'yes'],然后发现字典里已经有该类别的值了,所以字典里的数值+1.

然后读到第三个数据:[1, 0, 2, 'no'],发现字典里没有'no',所以字典里生成新的类别,并+1。

等都读取完以后,建立一个变量shannonEnt,表示香农能量熵。

在该for循环中,遍历字典里所有的类别(该例子只有yes和no两个类别),然后计算香农能量熵。

之后我们可以打印测试一下:

  1. myDat,labels=createDataSet()
  2. shannonEnt=calcShannonEnt(myDat)
  3. print(shannonEnt)

输出1.0

然后是第三个函数:划分子数据集。

  1. # 划分数据集,axis:按第几个属性划分,value:要返回的子集对应的属性值
  2. def splitDataSet(dataSet, axis, value):
  3. retDataSet = []
  4. featVec = []
  5. for featVec in dataSet:
  6. if featVec[axis] == value:
  7. reducedFeatVec = featVec[:axis]
  8. reducedFeatVec.extend(featVec[axis + 1:])
  9. retDataSet.append(reducedFeatVec)
  10. return retDataSet
'
运行

在我们构建决策树需要进行进一步分类时,我们需要用到该函数。

该函数的意义是根据用于分类的标签生成子数据集。

举个例子:假如我们输入的是之前建立的dataSet:splitDataSet(DataSet,0,1)

  1.     dataSet = [[1, 1, 1, 'yes'],
  2.                [1, 0, 1, 'yes'],
  3.                [1, 0, 2, 'no'],
  4.                [0, 1, 2, 'no'],
  5.                [0, 1, 2, 'no'],
  6.                [1, 1, 2, 'yes'],
  7.                [0, 0, 2, 'yes'],
  8.                [0, 1, 0, 'no'],
  9.                ]

之后在for中,我们判段dataSet里面的每个样本数据的第0个特征的值,如果是1,就保留,保留的方式是把该特征去掉,用剩下的特征加分类值构成一个子样本数据,如果是0,就不用管。

在dataSet中,第一个样本数据的第0个特征是1,符合,所以去掉该特征然后生成子样本[ 1, 1, 'yes']。

第二个样本数据的第0个特征是1,符合,所以去掉该特征然后生成子样本[ 0, 1, 'yes']

遍历完整个dataSet以后,就得到了根据特征值划分的子空间,打印一下:

  1. asa = splitDataSet(myDat, 0, 1)
  2. print(asa)

打印结果:

[[1, 1, 'yes'], [1, 1, 'yes'], [0, 2, 'no'], [1, 2, 'yes']]'
运行

然后是第四个函数:选择最好的数据集划分方式

  1. def chooseBestFeatureToSplit(dataSet):
  2. numFeatures = len(dataSet[0]) - 1 # 属性的个数。 -1是因为最后一个是分类的标签
  3. baseEntropy = calcShannonEnt(dataSet)
  4. bestInfoGain = 0.0
  5. bestFeature = -1
  6. for i in range(numFeatures): # 对每个属性记录信息增益
  7. featList = [example[i] for example in dataSet]
  8. uniqueVals = set(featList) # 该属性的取值集合
  9. newEntropy = 0.0
  10. for value in uniqueVals: # 对每一种取值计算信息增益
  11. subDataSet = splitDataSet(dataSet, i, value)
  12. prob = len(subDataSet) / float(len(dataSet))
  13. newEntropy += prob * calcShannonEnt(subDataSet)
  14. infoGain = baseEntropy - newEntropy
  15. if (infoGain > bestInfoGain): # 选择信息增益最大的属性
  16. bestInfoGain = infoGain
  17. bestFeature = i
  18. return bestFeature
'
运行

输入数据集然后寻找最好的划分方式,返回值代表最好的用来划分的特征。待会测试的时候输入dataSet为上一个函数生成的子数据集,即 [[1, 1, 'yes'], [1, 1, 'yes'], [0, 2, 'no'], [1, 2, 'yes']] 。

现在详细解释一下这个函数:

dataSet[0]代表第一个样本,即[1, 1, 'yes'],长度为3, 3-1=2,表示该样本的特征数。

然后计算出香农熵。

定义增益初始为0.0,然后初始的特征坐标为-1。

之后用i来把样本的特征遍历一遍。这里只有两个特征。

在每个特征里,首先用 [example[i] for example in dataSet] 提取所有样本第 i 个特征值的列表,此处我们假设正在第0个特征中,把每个样本的第0个特征分别提取出来,就生成了如下值:[1,1,0,1]。之后,通过uniqueVals = set(featList)可以把列表中不同的值都取出来。然后生成新的列表。这里一共就只有两个不同的特征值,一个是1,一个是0。

然后我们进行划分:遍历该特征所有不同的值,分别用该特征不同的值进行划分:subDataSet = splitDataSet(dataSet, i, value),在该例子中我们划分出来的结果是:第0个特征为1时:[[1, 'yes'], [1, 'yes'], [2, 'yes']] ; 第0个特征为0时:[[2, 'no']]。在for循环里计算累加这种靠这种划分方式的熵。

之后再计算增益。找到按哪个特征进行划分增益最大。然后返回该划分方式的索引。

我们把上一个函数中输出的asa输入进去:

  1. bestFeteTest = chooseBestFeatureToSplit(asa)
  2. print(bestFeteTest)

打印结果为 0

我们研究一下这个结果:

如果根据第0个特征划分asa,则生成结果为:

第0个特征为1时:[[1, 'yes'], [1, 'yes'], [2, 'yes']] ; 第0个特征为0时:[[2, 'no']]

如果根据第1个特征划分asa,则生成结果为:

第1个特征为1时:[[1, 'yes'], [1, 'yes']] ; 第1个特征为2时:[[0, 'no'],[1, 'yes']]

显然根据第一个特征进行划分,结果是对半分的(每边都是2个),对半分的划分方式无序性更大,不如第一个划分方式。

然后是第五个函数:通过排序返回出现次数最多的类别

  1. def majorityCnt(classList):
  2. classCount = {}
  3. for vote in classList:
  4. if vote not in classCount.keys(): classCount[vote] = 0
  5. classCount[vote] += 1
  6. sortedClassCount = sorted(classCount.iteritems(), #注意python3.x中要改成.items()函数
  7. key=operator.itemgetter(1), reverse=True)
  8. return sortedClassCount[0][0]
'
运行

这个函数有什么用呢?我们想象这样一种情况:因为每次我们划分数据的时候,都会用掉一个特征来进行划分。用掉的特征以后不会再使用了(因为用一个特征划分好以后,其每个子分支各自的该特征的值都是一样的)。假设在我们不断细分的过程中,发现所有的特征值都用完了,这时候该怎么办呢?很显然我们没法再继续下分了,所以需要返回当前类别,这个类别就用分到这个树枝的所有类别中比例最大的来代替,即假如分到该树枝的类别中有5个yes,2个no,最后我们就把它作为yes返回。

这种统计计数的方式还是靠创建字典来完成实现的。假设在for循环里统计的时候我们生成了这样的数据格式:{'no':2, 'yes':5}。然后用sorted函数对字典记录的每个类别的键值进行排序,排序完之后得到如下结果:[('yes', 5), ('no', 2)]。sortedClassCount[0][0]代表数量最大的那个类别值。

我们做个测试:

  1. aks = ['yes','yes','no','yes','no','yes','yes']
  2. majorityCnt(aks)

输出 

[('yes', 5), ('no', 2)]'
运行

至于为什么我们的输入是 ['yes','yes','no','yes','no','yes','yes']而不是 [['yes'],['yes'],['no'],['yes'],['no'],['yes'],['yes']],下一个构建树的程序会首先提取最后一列:[example[-1] for example in dataSet],提取出来的值是一个一维列表,而不再是二维列表了。后面还会再说。

最后一个函数:构建决策树。

终于到最后一个函数了。

  1. # 递归构建决策树
  2. def createTree(dataSet, labels):
  3. classList = [example[-1] for example in dataSet] # 类别向量
  4. if classList.count(classList[0]) == len(classList): # 如果只有一个类别,返回
  5. return classList[0]
  6. if len(dataSet[0]) == 1: # 如果所有特征都被遍历完了,返回出现次数最多的类别
  7. return majorityCnt(classList)
  8. bestFeat = chooseBestFeatureToSplit(dataSet) # 最优划分属性的索引
  9. bestFeatLabel = labels[bestFeat] # 最优划分属性的标签
  10. myTree = {bestFeatLabel: {}}
  11. del (labels[bestFeat]) # 已经选择的特征不再参与分类
  12. featValues = [example[bestFeat] for example in dataSet]
  13. uniqueValue = set(featValues) # 该属性所有可能取值,也就是节点的分支
  14. for value in uniqueValue: # 对每个分支,递归构建树
  15. subLabels = labels[:]
  16. myTree[bestFeatLabel][value] = createTree(
  17. splitDataSet(dataSet, bestFeat, value), subLabels)
  18. return myTree
'
运行

构建过程涉及递归操作。递归一般很难描述,这里想办法把递归的结构描述一下。

首先要注意我们在函数开头把最后面的类别读出开。然后用两个if判断,如果都是属于同一类别的,则直接将该类作为该树枝里的样本所代表的类。如果用于划分的特征都用完了,就直接把该类中数量最多的类别返回。

如果没有用完特征并且树枝里有许多别的类别,就继续处理:

构建一个树,采用最好的划分特征进行划分。删除该特征的列,然后对每个分支进行递归构建决策树。

至此,整个决策树的程序就构建好了。

我们运行验证一下:

print(createTree(myDat, labels))

打印结果为:

{'sssss': {0: 'no', 1: 'yes', 2: {'ddddd': {0: {'fffff': {0: 'yes', 1: 'no'}}, 1: {'fffff': {0: 'no', 1: 'yes'}}}}}}'
运行

勉强能看出来我们的分类方式。

下面将介绍如何把生成的决策树图表示出来。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/833403
推荐阅读
相关标签
  

闽ICP备14008679号