第4章 决策树

1. 引言

决策树(decision tree)学习的目的是产生一课泛化能力强的树，在非叶节点进行属性测试，每个叶结点对应了一个判定测试序列。其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）的策略。

2. 算法流程

决策树算法流程
根据算法流程图可知，决策树的生成就是一个递归的过程，三种情形会导致递归返回。其中，最重要的一个步骤是从属性集A中选择一个最优划分属性，下面介绍如何选择最优划分属性。

3. 划分选择

3.1信息增益

在进行介绍之前，首先说明一下熵的概念。

• 热力学熵：熵是一种不可逆性。温度只能自发的从高到低，熵增意味着所能使用的能量的减少。从一种有序的状态到一种无序的状态，无法利用的能量越来越多。老子有一句话，“天之道，损有余而补不足”。
• 信息熵：反应了对一件事物的了解程度。了解的越少，熵越大。
• 构象熵：反映了对一件东西的不确定性。越不确定，熵越大。
  进入正题……
  信息熵（information entropy）是度量样本集合纯度最常用的一种指标。
  信息熵和信息增益
• Ent(D)的值越小，则D的纯度越高。
• 信息增益的值越大，意味着使用属性a进行划分获得的“纯度提升”越大。则选择最优属性时计算出信息增益，然后选择出增益最大的那一个属性作为这个结点的划分属性。

3.2 增益率

信息增益对取值较多的属性有所偏好，这样导致的结果是分支过多，而每个分支结点的样本数较少。因此提出了增益率的概念，C4.5决策树算法使用增益率进行度量。

增益率
增益率可能对取值较少的属性友好。所以，作为一个权衡，使用一个
启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3.3 基尼指数

CART决策树使用基尼指数（Gini index）来选择划分属性。

基尼值和基尼指数
Gini(D)表示从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini（D）越小，数据集的纯度越高。
在进行选择时，选择基尼指数最小的作为最优划分属性。

4. 防过拟合——剪枝处理

• 预剪枝（prepruning）：指在决策树生成过程中，对每个结点在划分前先进进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。
  预剪枝虽然降低了过拟合的风险，但带来了欠拟合的可能。基于“贪心”本质禁止展开分支，可能会导致暂时不能提高泛化性能但对之后有帮助的展开无法继续。
• 后剪枝（postpruning）：先从训练集中训练出一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
  后剪枝带来的欠拟合风险很小，泛化性能优于预剪枝。但是，由于后剪枝是在决策树生成之后进行操作，因此训练时间开销比未剪枝决策树和预剪枝决策树大得多。
  采用“留出法”（留出一部分数据集用来验证能否带来泛化性能的提升），用信息增益进行最优划分属性的选择。

5. 连续与缺失值

5.1 连续值

简言之，就是寻找连续属性的最佳分割点，使取该点时获得的信息熵是最大的。

连续属性的处理

5.2 缺失值的划分

1. 在属性值缺失的情况下进行划分属性的选择
   在进行最优划分属性的选择时，增加未缺失样本的比重，用未缺失样本计算类、属性的比重。

   
   属性值缺失时的处理

2. 划分时属性值缺失
   将该样本划分到所有子结点中，但是所占的比重不同，这个比重根据完整值样本中的比重决定。

   
   属性值缺失的划分

6. 多变量决策树

决策树的分类边界由若干与坐标轴平行的分段组成。

决策树分类边界
每次划分只对应一个属性的选择会有很大的开销，多面量决策树（multivariate decision tree）进行了简化。非叶结点不止针对一个属性，而是对属性进行线性组合，构建一个线性组合分类器。比如通过OCI贪心的寻找到每个属性的最有权值，在局部优化的基础上对分类边界进行随机扰动以找到更好的边界。或者使用最小二乘法、感知机树等构造神经网络的方法。
多变量决策树
另外，决策树的学习也可以使用增量学习，接收到新样本之后在已学得的样本上进行调整，主要机制是通过调整分支路径上的划分属性次序对树部分进行重构。

7. 基于决策树进行西瓜好坏的分类

• 数据来源：西瓜书上的西瓜数据

A.加载数据集

def loadExcel(dataPath):
    #返回的数据类型为dataFrame,导入的数据是存在标题行的
    ori_data = pd.read_excel(dataPath)
    #转化为numpy的展示方式，转化之后第一行消失
    ori_data = ori_data.values
    #增加标签栏
    label = ["编号","色泽","根蒂","敲声","纹理","脐部","触感","密度","含糖率","好瓜"]
    label_exist = [0,0,0,0,0,0,0,0,0,0]
    temp_data = []
    for i in range(len(ori_data)):
        temp_data.append([])
        for j in range(len(label)):
            temp_data[i].append(ori_data[i][j])
    #将数据转化到列表中
    ori_data = temp_data
    return ori_data, label,label_exist

数据集

B.创建树模型

这是主函数

if __name__ == "__main__":
    train_path = "/home/stardream/DDML/MachineLearning/dataSet/watermelon3.0.xlsx"
    #加载表格中的数据
    dataSet, labels,l_exist = loadExcel(train_path)
    #创建树模型
    decisionTree = createTree(dataSet,labels,l_exist)
    print(decisionTree)

C.createTree()

这是中间涉及的相关函数。

def mostClass(result):
    #创建一个字典
    className = {}
    for name in result:
        #字典中的键值不存在，增加一个新的
        if name not in className.keys():
            className[name] = 0
        className[name] += 1
    #依据键值对进行排序
    sortedClass = sorted(className.iteritems(), reverse = True)
    #返回最多的类别
    return sortedClass[0][0]

def calEnt(ori_data):
    result = {}
    #得带对应类别的数目
    for data in ori_data:
        if data[-1] not in result.keys():
            result[data[-1]] = 0
        result[data[-1]]  += 1
    Ent = 0.0
    #依据公式进行熵的计算
    for key in result:
        Pk = float(result[key]/len(ori_data))
        Ent -= Pk* math.log(Pk,2)
    return Ent

#若使用属性划分，则划分出来的子集整理为小数据集
def spiltSet(value, i, ori_data, seq):
    sub_set = []
    if i==7 or i==8:
        if seq == 0:
            for j in ori_data:
                if j[i] < value:
                    temp = j[:i]
                    temp.extend(j[i + 1:])
                    sub_set.append(temp)
        elif seq == 1:
            for j in ori_data:
                if j[i] >= value:
                    temp = j[:i]
                    temp.extend(j[i + 1:])
                    sub_set.append(temp)
    else:
        # 对应属性下的数据集
        for j in ori_data:
            if j[i] == value:
                temp = j[:i]
                temp.extend(j[i + 1:])
                sub_set.append(temp)

    return sub_set

def continue_value(sum_en,index,ori_data):
    conGain = 0.0
    classEnt = 0.0
    bestGain =0.0
    conFlag = 0
    feature = [example[index] for example in ori_data]
    sorted(feature)
    for i in range(len(feature)-1):
        midVal = float((feature[i]+feature[i+1])/2.0)
        for j in range(2):
            subSet = spiltSet(midVal,index,ori_data,j)
            # 总增益
            classEnt -= float(calEnt(subSet) * len(subSet) / len(ori_data))
        conGain = sum_en + classEnt
        if bestGain < conGain:
            bestGain = conGain
            conFlag = midVal
    return conGain, conFlag

def gain_choose(ori_data):
    #计算熵
    sum_enropy = calEnt(ori_data)
    temp_enropy = 0.0
    flag2 = -1
    #跳过编号，从第1个开始。因为编号的增益是最大的，使用编号之后算法停止，然而类别太多
    #不考虑最后一列的好瓜列表
    for i in range(1,len(ori_data[0])-1):
        feature = [example[i] for example in ori_data]
        feature = set(feature)
        classEnt = 0.0
        if i==7 or i==8:
            Gain_data, conFlag = continue_value(sum_enropy,i,ori_data)
        else:
            for value in feature:
                 #将属性的每一个值进行计算对应的增益
                 subSet = spiltSet(value, i, ori_data,-1)
                 #总增益
                 classEnt -= float(calEnt(subSet)*len(subSet)/len(ori_data))
            Gain_data = sum_enropy + classEnt
        #选出最大的增益
        if Gain_data>temp_enropy:
            flag = i;
            temp_enropy = Gain_data
            print("2flag")
            print (flag)
            print(flag2)
        if flag ==7 or flag == 8:
            flag2 = conFlag
    #返回最大增益属性
    return flag,flag2

#构建决策树
def createTree(ori_data,label,lEx):
    subLabels = []
    print(label)
    #每一组数据的结果保存在temp_result中
    temp_result = [result[-1] for result in ori_data]
    #如果只有一种结果，那么直接返回这一种结果，无需继续构建决策树
    if len(set(temp_result)) == 1:
        return temp_result [0]
    #若每组数据中的属性值都相同，则无须继续构建，直接返回所占比重最大的结果;或者没有属性值是无须构建
    #取除结果以外的数据进行对比
    temp_result2 = [result[:len(label)-1] for result in ori_data]
    flag = 1
    for i in range(len(temp_result2)):
        for j in range(len(temp_result2[0])):
            if temp_result2[i][j] != temp_result2[i+1][j]:
                flag=0
                break;
        if flag == 0:
            break;
    if flag == 1 or len(ori_data[0]) == 1:
        return mostClass(temp_result)
    #计算增益，返回增益最大的对应的属性
    best_Feature,flag2 = gain_choose(ori_data)
    bestLabel = label[best_Feature]
    decision_tree = {bestLabel:{}}
    lEx[best_Feature] = 1
    #del(label[best_Feature])
    print(bestLabel,flag2)
    if best_Feature == 7 or best_Feature==8:
        for j in range(2):
            for p in range(len(lEx)):
                if lEx[p] == 0:
                    subLabels.append(label[p])
            #递归进行划分
            decision_tree[bestLabel][flag2] = createTree(spiltSet(flag2, best_Feature, ori_data, j), subLabels, lEx)
    else:
        featValues = [example[best_Feature] for example in ori_data]
        # 得到属性下的各个值
        uniqueVals = set(featValues)
        for value in uniqueVals:
            for p in range(len(lEx)):
                if lEx[p] == 0:
                    subLabels.append(label[p])
            #递归进行划分
            decision_tree[bestLabel][value] = createTree(spiltSet(value, best_Feature, ori_data,-1), subLabels, lEx)
    return decision_tree

数据集在这里

编号  色泽  根蒂  敲声  纹理  脐部  触感  密度  含糖率 好瓜    
1   青绿  蜷缩  浊响  清晰  凹陷  硬滑  0.697   0.46    是
2   乌黑  蜷缩  沉闷  清晰  凹陷  硬滑  0.774   0.376   是
3   乌黑  蜷缩  浊响  清晰  凹陷  硬滑  0.634   0.264   是
4   青绿  蜷缩  沉闷  清晰  凹陷  硬滑  0.608   0.318   是
5   浅白  蜷缩  浊响  清晰  凹陷  硬滑  0.556   0.215   是
6   青绿  稍蜷  浊响  清晰  稍凹  软粘  0.403   0.237   是
7   乌黑  稍蜷  浊响  稍糊  稍凹  软粘  0.481   0.149   是
8   乌黑  稍蜷  浊响  清晰  稍凹  硬滑  0.437   0.211   是
9   乌黑  稍蜷  沉闷  稍糊  稍凹  硬滑  0.666   0.091   否
10  青绿  硬挺  清脆  清晰  平坦  软粘  0.243   0.267   否
11  浅白  硬挺  清脆  模糊  平坦  硬滑  0.245   0.057   否
12  浅白  蜷缩  浊响  模糊  平坦  软粘  0.343   0.099   否
13  青绿  稍蜷  浊响  稍糊  凹陷  硬滑  0.639   0.161   否
14  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  0.657   0.198   否
15  乌黑  稍蜷  浊响  清晰  稍凹  软粘  0.36    0.37    否
16  浅白  蜷缩  浊响  模糊  平坦  硬滑  0.593   0.042   否
17  青绿  蜷缩  沉闷  稍糊  稍凹  硬滑  0.719   0.103   否

---

代码放在(决策树)[https://github.com/RuiDream/simpleAl]，很遗憾运行不正确，原因是加入了连续值的处理，而没有处理好。如果把连续值的那一部分去了对离散值来说是对的，本想改一改，一个国庆假期间隔太久，改不动了。意思到就行，以后不能写这样的半吊子代码了。