决策树-栽树

现在来到了比较难的部分，将ID3的算法实现

这里如果跟着书敲一遍也能敲出来，但可能没办法很好地理解，以及自己去实现

由于本人基础缺失很差，故先自己敲了好几遍，然后再看西瓜书的图4-2.一点点明白

流程：

既然是栽树，首先得从根结点出发

1. 如果此时样本都是同一属性，那么直接标记为相同结点，并且返回，一开始我不太理解这个return，难道return之后还能运行后面的代码吗？return之后的确返回了，但这里的return是迭代里面的，只是返回上一层
2. 如果属性相同，但是分类不同，那么需要根据哪个多选哪个

这里的1和2对应代码中的前两个if

3. 然后选择最优属性。这里按照之前的算法，得出最优是第0维，也就是第1列，对应的是no surfacing属性
4. 从第1列中，得到有两个不同值，一个是1，一个是0
5. 对于0和1，分别再用迭代进行栽树

import majority
import featureSelect

dataSet = featureSelect.dataSet
labelSet = featureSelect.labelSet


def createTree(dataSet, labelSet):
    # classList = ['yes','yes','no','no','no']
    # 这是要分类情况
    classList = [example[-1] for example in dataSet]
    # 如果此时属性都已划分完，则返回最多的类
    if classList.count(classList[0]) == len(classList):
        return classList[0]  # 第一轮次yes为2，no为3，所以继续
    if len(dataSet[0]) == 1:
        # 若只有yes或者no这样的标记，那么需要选择类最多的
        return majority.majorityCnt(classList)
    # 接下来需要选择最有属性bestFeat
    bestFeat = featureSelect.bestFeature(dataSet)
    # 第一次选择的最优属性为0，这个0是列的意思
    # 我们从labelSet=['no surfacing','flippers']选no surfacing
    bestFeatLabel = labelSet[bestFeat]
    # 开始栽树
    # 一开始是{no surfacing:{}}，参照P43页最上方
    myTree = {bestFeatLabel: {}}
    # 删掉no surfacing
    del (labelSet[bestFeat])
    # 按照属性选择的那一套，开始选择属性
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 对于uniqueVals得到的0和1，按照属性选择里面的，划分子集
    for value in uniqueVals:
        subLabels = labelSet[:]
        # 迭代栽树
        myTree[bestFeatLabel][value] = createTree(featureSelect.splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree


if __name__ == "__main__":
    result = createTree(dataSet, labelSet)
    print(result)

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}