我们可以采用递归的原则处理数据集,递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类,则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。

我们可以设置算法可以划分的最大分组数目。像是其他决策树算法,比如C4.5和CART,这些算法在运行时并不总是在每次划分分组时都会消耗特征。由于特征数目并不是在每次划分数据分组时都减少,因此这些算法在实际使用时可能引起一定的问题。

目前我们并不需要考虑这些问题,只要在算法开始运行前计算列的数目,查看算法是否使用了所有属性即可。如果数据集已经处理了所有属性,但是类标签依然不是唯一的,此时我们需要决定如何定义该叶子节点,在这种情况下,我们通常会采用多数表决的方法决定该叶子节点的分类。

import operator

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():classCount[vote]=0
        classCount[vote]=classCount[vote]+1
    sortedClassCount=sorted(classCount.iteritem(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

上述的函数使用分类名称的列表,然后创建键值为classList中唯一值的数据字典,字典对象存储了classList中每个类标签出现的频率,最后利用operator操作键值排序字典,并范围出现次数最多的分类名称。

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])
    featVaues=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featVaues)
    for value in uniqueVals:
        subLabels=labels[:]
        myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

函数createTree()使用两个输入参数:数据集和标签列表。标签列表包含了数据集中所有特征的标签,算法本身并不需要这个变量,但是为了给出数据明确的含义,我们将它作为一个输入参数提供。此外,对数据集的要求这里依然需要满足。

上述代码首先创建了一个名为classList的列表变量,其中包含了数据集的所有类标签。递归函数的第一个停止条件是所有的类标签完全相同,则直接返回该类标签。递归函数的第二个停止条件是使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组。由于第二个条件无法简单地返回唯一的类标签,这里使用majorityCnt函数挑选出现次数最多的类别座位返回值。

下一步程序开始创建树,这里使用Python的字典类型存储树的信息,当然也可以声明特殊的数据类型存储树,但这里没有必要。字典变量myTree存储了树的所有信息,这对于之后绘制树状图非常重要。当前数据集选取的最好特征存储在变量bestFeat中,得到列表包含的所有属性值。

最后代码遍历当前选择特征包含的所有属性值,在每个数据及划分上递归调用函数createTree(),得到的返回值将被插入到字典变量myTree中,因此函数终止执行时,字典中将会嵌套很多代表叶子节点信息的字典数据。

测试代码:


myDat,labels=createDataSet()
print(createTree(myDat,labels))
print(myDat)

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部