决策树4：构建算法之ID3、C4.5

算法：createTree(dataSet,featList,bestFeatLists)。由给定的训练数据产生一棵判定树。输入：    dataSet：训练数据集    featList：分类属性标签    bestFeatLists：存储选择的最优特征标签输出：    myTree：一棵判定树。方法：createTree(dataSet,featList,bestFeatLists)1）从传入的数据集dataSet中切割出分类标签，yList2）如果yList中只有同一种标签，说明已经递归到分类边界了，则返回该标签3）如果已经处理了dataSet中所有属性（列），但是类标签依然不是唯一的，采用多数判决的方法决定该子节点的分类4）找出dataSet最优划分（信息增益最大）的特征所在位置bestFeatVec5）在分类属性标签featList找出该位置所对应的特征值bestFeatLabel，并将该特征值存储到bestFeatLists中6）将最优划分特征值作为当前（子）树的根节点，生成初始决策树myTree（用字典表示一个树结构）7）在featList中删除当前已经使用过的特征标签（因为每次选择特征作为条件，dataSet会删掉这一列，形成新的子类，因此对应的featList中的值也要删掉）8）确定子树分支：获取已选择的最优划分特征所对应的值分类categories（如“年龄”是最优特征，则“老”“中”“青”三个子类）9）遍历每一个当前特征下的子类，在每个子类中，递归地调用创建决策树的方法，将递归调用的结果作为当前树节点的一个分支（构建树的方法是：特征作为字典的key，所得到的分类结果作为value；子树进行嵌套）

"""函数说明：数据集已经处理了所有属性，但是类标签依然不是唯一的,采用多数判决的方法决定该子节点的分类        即统计yList中出现次数最多的元素（类标签）Parameters：    yList：类标签列表Returns：    sortedClassCount[0][0]：出现次数最多的元素（类标签）"""def majorityCnt(yList):    yCount={}    #统计yList中每个元素出现的次数    for vote in yList:        if vote not in yCount.keys():            yCount[vote]=0        yCount[vote]+=1        #根据字典的值降序排列        sortedYCount=sorted(yCount.items(),key=operator.itemgetter(1),reverse=True)    return sortedYCount[0][0]
"""函数说明：创建决策树
Parameters:    dataSet：训练数据集    featList：分类属性标签    bestFeatLists：存储选择的最优特征标签Returns：    myTree：决策树"""def createTree(dataSet,featList,bestFeatLists):    # 取训练数据集最后一列，即分类标签    yList=[example[-1] for example in dataSet]        # 如果类别完全相同，则停止继续划分，    # 即yList中所有类别都是同一数据值（该类别数值个数等于列表长度）    if yList.count(yList[0])==len(yList):        # 返回该类别数值        return yList[0]            # 数据集已经处理了所有属性，但是类标签依然不是唯一的，    # 则采用多数判决的方法决定该子节点的分类    # 为什么要如此判断？dataSet的列是不断减少的，dataSet某一行的长度，就是列    if len(dataSet[0])==1:        return majorityCnt(yList)        # 选择最优划分的特征index    bestFeatVec = optimalPartition(dataSet)    # 最优特征index所对应的分类标签，作为树的根节点    bestFeatLabel=featList[bestFeatVec]    # 存储选择的最优特征标签    bestFeatLists.append(bestFeatLabel)        # 将最优划分特征值作为当前（子）树的根节点，生成初始决策树（用字典表示一个树结构）    myTree={bestFeatLabel:{}}        # 删除已经使用的特征标签（del删除变量，解除引用）    # 因为每次选择特征作为条件，dataSet会删掉这一列，形成新的子类，因此对应的featList中的值也要删掉    del(featList[bestFeatVec])    print('featList: ',featList)            # 得到训练集中所有最优特征那一列所对应的值    featValues=[example[bestFeatVec] for example in dataSet]    # 去掉重复的属性值，得到最优特征下的子类    categories=set(featValues)        # 遍历最优特征列所对应的值，创建决策树    # 如“年龄”是最优特征，则遍历“老”“中”“青”三个子类    for category in categories:        # 根据当前数据集、最优划分的特征index以及每个分类（条件）得到（条件下的子集）        subDataSet = np.array(currentConditionSet(dataSet,bestFeatVec,category))        # 递归地调用创建决策树的方法，将递归调用的结果作为当前树节点的一个分支        myTree[bestFeatLabel][category]=createTree(subDataSet,featList,bestFeatLists)    return myTree
if __name__=='__main__':    #print('featLabels',featLabels)    bestFeatLists = []    myTree=createTree(dataSet,featList,bestFeatLists)    print(myTree)