14.决策树的最终构建

前面是做了一轮决策,按照信息论的方式,对各特征做了分析,确定了能够带来最大信息增益(注意是熵减)的特征。但仅这一步是不够的,我们需要继续对叶子节点进行同样的操作,直到完成如下的目标:

[if !supportLists]1)[endif]程序遍历完所有划分数据集的属性;

[if !supportLists]2)[endif]每个分支下的所有实例都具有相同的分类;

如果程序已经遍历完所有划分数据集的属性,叶子节点下的实例仍然不具备相同的分类,那就采用多数表决的方法(有点像KNN)来决定该叶子节点的分类。

好,上代码

def majorityCnt(classList):

    classCount={}

    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)

    return sortedClassCount[0][0]

如上代码就不逐行展开了,其实就是把一个数组中的标签项数一下数,然后找到哪一个标签出现的次数最多,和KNN中相关的排序方式类似。

我们再来看看,整棵树的遍历:

def createTree(dataSet, labels):

    classList = [example[-1] for example in dataSet]

    if classList.count(classList[0]) == len(classList):

        return classList[0]

    if len(dataSet[0]) == 1:

        return majorityCnt(classList)

    bestFeat = chooseBestFeatureToSplit(dataSet)

    bestFeatLabel = labels[bestFeat]

    myTree = {bestFeatLabel:{}}

    del(labels[bestFeat])

    featValues = [example[bestFeat] for example in dataSet]

    uniqueVals = set(featValues)

    for value in uniqueVals:

        subLabels = labels[:]

        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)

    return myTree

代码一共16行。这段代码比较关键,而且不算太容易看懂,我们来逐行看一下:

def createTree(dataSet, labels):

#定义函数,dataSet实际上是带了标签值的数据集,labels其实是标签值的意义定义,详见前面的数据集定义

    classList = [example[-1] for example in dataSet]

#classList实际上就是标签值的数组,标签值位于数据集的最后一列

    if classList.count(classList[0]) == len(classList):

#这里做了一个判断,count方法的作用就是数出数组中某个元素值的个数,在这里就是对classList[0]做了计数,当它的数量等同于数组的长度时,说明这个数组里没有别的标签了,即已经分到了标签唯一的状态;按决策树叶子节点是否达到不可分的条件2,已经完成

        return classList[0]

#返回classList[0],即当前叶子节点唯一的标签

    if len(dataSet[0]) == 1:

        return majorityCnt(classList)

#如果dataSet的长度为1,那就等于是叶子节点中特征值只有1个,这个时候就满足了决策树叶子节点是否达到不可分的条件1,程序遍历完所有划分数据集的属性,这个时候我们要对叶子节点中的标签进行统计,通过多数表决的方法确定并返回这一分支的标签值。

    bestFeat = chooseBestFeatureToSplit(dataSet)

    bestFeatLabel = labels[bestFeat]

#如果不是上述的两种情况,即节点还可分,那么就用chooseBestFeatureToSplit方法找到最佳的特征项,并对节点进行分解。

    myTree = {bestFeatLabel:{}}

#建立一个字典myTree

    del(labels[bestFeat])

#删除已选出的特征

    featValues = [example[bestFeat] for example in dataSet]

#根据最佳特征的下标,从dataSet里取出相关特征的值的数组

    uniqueVals = set(featValues)

#去重,得到该数组中可能的值

    for value in uniqueVals:

#遍历所有可能的值

        subLabels = labels[:]

#复制出一个label数组,这个数组已经删掉了之前的最佳特征项

        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)

#根据最优的特征进行分叉,每一个分叉再去进行生成子树的递归操作(这是关键,通过递归遍历生成所有的子节点,并根据那两条要求确定是否终止并直接return)

    return myTree

#返回树(注意这里的返回,可能是一棵子树,因为是通过递归生成了整棵树,只有最开始的调用才是根节点)

好了,至此,这段代码结束。这段代码不算太容易看懂,原理好懂,但是算法理论要想跟代码联系在一起,还是挺复杂的。最终生成的树结构如下:

它是个什么呢?其实就是一开始的最优特征项是“no surfacing”,然后进行分叉,左边由于标签一致所以结束,右边进行再分叉,然后因为特征用完,结束。

一棵有意思的树。

版权声明:
作者:lichengxin
链接:https://www.techfm.club/p/46274.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>