Function createTree

DecisionTree/DecisionTree.py:190–242

递归创建决策树 :param dataSet:(trainDataList， trainLabelList) <<-- 元祖形式 :return:新的子节点或该叶子节点的值

(*dataSet)

    return retDataArr, retLabelArr

def createTree(*dataSet):
    '''
    递归创建决策树
    :param dataSet:(trainDataList， trainLabelList) <<-- 元祖形式
    :return:新的子节点或该叶子节点的值
    ''&#x27;
    #设置Epsilon，“5.3.1 ID3算法”第4步提到需要将信息增益与阈值Epsilon比较，若小于则
    #直接处理后返回T
    #该值的大小在设置上并未考虑太多，观察到信息增益前期在运行中为0.3左右，所以设置了0.1
    Epsilon = 0.1
    #从参数中获取trainDataList和trainLabelList
    #之所以使用元祖作为参数，是由于后续递归调用时直数据集需要对某个特征进行切割，在函数递归
    #调用上直接将切割函数的返回值放入递归调用中，而函数的返回值形式是元祖的，等看到这个函数
    #的底部就会明白了，这样子的用处就是写程序的时候简洁一点，方便一点
    trainDataList = dataSet[0][0]
    trainLabelList = dataSet[0][1]
    #打印信息：开始一个子节点创建，打印当前特征向量数目及当前剩余样本数目
    print('start a node', len(trainDataList[0]), len(trainLabelList))

    #将标签放入一个字典中，当前样本有多少类，在字典中就会有多少项
    #也相当于去重，多次出现的标签就留一次。举个例子，假如处理结束后字典的长度为1，那说明所有的样本
    #都是同一个标签，那就可以直接返回该标签了，不需要再生成子节点了。
    classDict = {i for i in trainLabelList}
    #如果D中所有实例属于同一类Ck，则置T为单节点数，并将Ck作为该节点的类，返回T
    #即若所有样本的标签一致，也就不需要再分化，返回标记作为该节点的值，返回后这就是一个叶子节点
    if len(classDict) == 1:
        #因为所有样本都是一致的，在标签集中随便拿一个标签返回都行，这里用的第0个（因为你并不知道
        #当前标签集的长度是多少，但运行中所有标签只要有长度都会有第0位。
        return trainLabelList[0]

    #如果A为空集，则置T为单节点数，并将D中实例数最大的类Ck作为该节点的类，返回T
    #即如果已经没有特征可以用来再分化了，就返回占大多数的类别
    if len(trainDataList[0]) == 0:
        #返回当前标签集中占数目最大的标签
        return majorClass(trainLabelList)

    #否则，按式5.10计算A中个特征值的信息增益，选择信息增益最大的特征Ag
    Ag, EpsilonGet = calcBestFeature(trainDataList, trainLabelList)

    #如果Ag的信息增益比小于阈值Epsilon，则置T为单节点树，并将D中实例数最大的类Ck
    #作为该节点的类，返回T
    if EpsilonGet < Epsilon:
        return majorClass(trainLabelList)

    #否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的
    # 类作为标记，构建子节点，由节点及其子节点构成树T，返回T
    treeDict = {Ag:{}}
    #特征值为0时，进入0分支
    #getSubDataArr(trainDataList, trainLabelList, Ag, 0)：在当前数据集中切割当前feature，返回新的数据集和标签集
    treeDict[Ag][0] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 0))
    treeDict[Ag][1] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 1))

    return treeDict

def predict(testDataList, tree):
    ''&#x27;