决策树是一种常见的机器学习方法，因为它的处理流程和人类做决策时思考的方式很类似，因此具有很强的可解释性。

基本流程

举个例子来说决策树的基本流程，假设你是一个女生，现在家里给你介绍了一个相亲对象，你的决策就是决定是否和这个男生相处下去。那么首先第一眼看到这个男生，你发现这个男生长得很一般，如果你是个极端的颜控的话，此时可能就会把不帅的筛选掉了。好，我们假设你对这点不那么在意，那么接下来聊天发现这个男生还木有钱，也许你还能忍受；再深入了解发现此男还很自私，到这里可能你就做出拒绝的决策了。如果用树的结构来构建整个过程，“帅不帅”，“有没有钱”，“性格好不好”等等这些特征都是树上的一个节点，每经过一个节点，不同类型的数据就可能会分开进入不同的后续处理。到某个叶子节点时，也就是你已经做出来最后的决策，对满足从根节点到这个叶子节点的路径上所有节点条件的数据，都会做出相同的判断。

用算法伪代码描述如下：

在决策树生成的递归过程中，处理节点时可能遇到三种情况会导致递归返回：

  • 当前节点包含的样本都属于同一类别，无需划分
  • 当前属性集为空，或者所有样本在所有属性上取值相同
  • 当前节点包含的样本集为空，不能划分

举个例子来说明这三种情况，我们仍然以相亲为例，第一种情况可以看作是极端颜控遇到帅哥，那么所有分到帅哥这个属性的样本全都被划分到“接受”，因而无需再划分了。第二种情况是划分到最后，已经没有属性了，例如我们对男生有三种属性——相貌，身家，性格，现在划分到了相貌帅，身家高，性格好，满足这些条件的男生既有可以接受的也有需要拒绝的，但是此时已经没有属性可以继续往下划分的了，又或者划分到身家高的属性时发现所有满足身家高的男生性格都好，那么也会导致递归返回。第三种情况很容易理解，举例就是决策树到相貌帅，身价高之后继续划分性格属性，发现满足前两个条件的男生没有性格好的，因此也无法划分了。

这三种情况都会导致当前节点被标记为叶节点，情况一自不必说，第二种情况下，我们将类别设定为该节点所含样本最多的类别；第三种情况下我们将其类别设为其父节点所含样本最多的类别。值得注意的是，后两种情况处理实质有些不同，第二种情况是利用了当前节点的后验分布，第三种情况则将父节点分布当作先验信息。

节点划分

了解了决策树的推断过程，不难发现的是算法中最重要的部分就是如何选择划分的属性。这里遵循的一个朴素思想就是，我们希望每次划分之后每个子节点内的样本类别尽可能一致。由此出现了很多划分依据。

信息增益

信息熵最早是信息论中的一个概念，常被用来衡量样本集合纯度。我们假设样本集合$D$中第$k$类样本所占的比例为$p_k(k=1,2,..,|\mathcal{Y}|)$,那么信息熵则为：

若Ent($D$)值越小，则纯度越高，约定$p=0\rightarrow p\text{log}_2p=0$。

这个信息熵即定义了节点上的纯度。现在我们来对这个节点做划分，假设我们先来看离散属性$a$，该属性有$V$个可能的取值，那么如果选择它来划分，就会产生$V$个不同的分支，第$v$个节点包含了$D$中在属性$a$上取值为$a^v$的样本，我们记作$D^v$。根据上式，我们可以计算出每个子节点的信息熵，再由子节点分到的样本数赋予其权重$|D^v|/|D|$，那么可以计算出用属性$a$来对$D$划分得到的信息增益：

这个值可以理解为，如果使用该属性，那么信息熵会降低多少，信息增益越大，说明纯度提升越多。
一个用信息增益来划分属性的算法就是著名的ID(Iteractive Dichotomiser)3算法。

增益率

简单使用信息增益作为准则有一个较大的问题，就是它更偏好取值较多的属性。例如，当相貌这个属性有帅和不帅两个取值，而身家这个属性有贫穷，小康，中产，富裕四个取值，那么信息增益会更偏好身家这个属性。为了减少这个影响，C4.5使用增益率来选择最优化分属性：

其中:

称作是$a$的固有值。属性的取值数目越多，该值越大。
当然，这么一来，有些矫枉过正，即增益率准则现在又偏好取值数目较少的属性了。因此C4.5算法并不是简单选择增益率最大的候选属性，而是使用了一个启发式规则： 先找出侯选属性中信息增益高于平均水准的，再从中挑增益率最高的。

基尼指数

常用的CART决策树使用基尼值作为纯度的衡量标准。我们定义基尼指数如下：

直观上，基尼值反应了从数据集中随机抽两个样本，其类别不一致的概率，因而基尼值越小，纯度越高。
由基尼值我们导出基尼指数来选择最优划分属性：

我们在侯选属性集合中选择基尼指数最小的那个作为划分属性。

剪枝处理

做过OI的同学对剪枝技术应该不陌生，我们通常会在搜索问题中用到剪枝。当然这里决策树中也可以建模为一个搜索算法，这里的剪枝是一种应对过拟合的主要手段。
我们设想，在学习中，为了分类正确，我们会不断划分节点，如果样本属性足够的话，我们会造成过多的分支。这时就有可能将一些训练集自身的特性当成所有数据具有的特性来学习，而导致过拟合。因此我们需要去掉一些分支来降低过拟合的风险。

基本的剪枝策略有预剪枝和后剪枝两种，前者是指在节点划分之前就预先判断，如果在该节点上继续划分无法带来泛化能力的增强，那么就停止划分而将其作为叶子节点；后者则是指先生成一颗完整的决策树之后自底向上检查非叶子节点，如果将其改为叶子节点能使泛化性能提高，那么就将其替换为叶子节点。

那么这里一个很重要的问题就是如何判断泛化性能是否提升，通常我们还是使用在训练集中留出一部分数据做验证集的方法。具体的过程较为简单，就不赘述了。

连续值和缺失值

连续值

到目前为止我们讨论的都是离散属性，但是现实任务中我们不可避免的会遇到连续属性，此时我们应该如何处理呢？

C4.5算法给出的方案是用二分法来对连续属性进行处理。假设样本集为$D$，其中有一连续属性$a$,假设$a$在$D$上有$n$个不同的取值，我们将其由小到大排序${a^1, a^2,\cdots,a^n }$。 我们设定一个划分点$t$将$D$分为两个子集$D^-_t,D^+_t$，前者包含属性$a$上小于等于$t$的样本，后者包含大于$t$的样本。显然这里$t$在两个相邻$a$值之间取任意值不会影响划分结果，那么$t$值就有$n-1$个候选项。通常我们可将划分点设为各个区间的中位点，即：

那么我们就可以像离散值一样考察这些划分点，例如当使用信息增益时：

需要注意的是，连续属性被用来在某个节点做划分之后，仍然可以在后续节点被用到，这和离散属性不同。

缺失值

现实任务中往往会遇到缺失值的问题，例如样本的某些值较为敏感或者涉及到隐私，又或者因为种种原因丢失了，此时如果简单地放弃不完整的样本，显然是对数据的很大浪费。

具体而言，这里需要解决两个问题：

  • 如何在属性值缺失的情况下进行划分属性的选择？
  • 在给定划分属性的情况下，如果样本在该属性上缺失，那么如何对该样本划分？

C4.5算法给出了如下的解决方案。

对于给定的数据集$D$和属性$a$，令$\tilde{D}$为$D$中在属性$a$上没有缺失值的样本子集。那么对于问题一，我们可以仅根据$\tilde{D}$来判断属性$a$的优劣。我们令$\tilde{D}^v$表示$\tilde{D}$中在属性$a$取值为$a^v$的样本子集，而$\tilde{D}_k$表示$\tilde{D}$中属于第$k$类的样本子集。我们给每个样本赋予一个权重$w_x$（权重初始为1）。接着我们定义这样几个概念：

其中$\rho$表示无损样本的比例，$\tilde{p}_k$表示无缺失值样本中第$k$类样本所占比例，$\tilde{r}_v$表示无缺失值样本在属性$a$中取值$a^v$的样本所占比例。 基于此，我们可以将信息增益的计算式推广到：

那么对于第二个问题，如果样本$x$在属性$a$上的取值未知，那么则将$x$同时划入所有子节点，且调整样本在不同属性值$a^v$的子节点下的权值为$\tilde{r}_v\times w_x$。

多变量决策树

到现在为止我们讨论属性划分时都只考虑了单一属性，即每次节点的划分只涉及一个属性；如果以属性为坐标轴，则绘制出的分类边界都是平行于各个坐标轴的。
这时如果真实的分类边界非常复杂时，划分的段数会非常多，此时决策树会非常复杂。如果我们能够使用斜的划分边界，那么模型能够得到极大的简化。例如下图中，平行分类边界需要9段，而斜的划分边界只需要3段。

此时，在非叶节点划分时不再针对某个属性，而是对属性的线性组合进行测试，即每个非叶节点都可以看作是一个形如$\sum_{i=1}^dw_ia_i=t$的线性分类器，其中$w_i$是属性$a_i$的权重,$w_i$和$t$都可以学习得到。因此，多变量决策树在非叶节点不再寻求最优划分属性，而是构建一个线性分类器。

习题及参考答案

1. 试证明对于不含冲突数据（特征向量完全不同但标记不同）的训练集，必存在与训练集一致的（训练误差为0）的决策树。

假设对现有的决策树，其训练误差不为零，该决策树在$x_1,x_2,…,x_k$共$k$个样本上分类错误。那么在决策树的节点上针对这$k$个样本划分出从根节点到叶子节点的决策路径，即可将训练误差降为0。因为不存在冲突数据，因此新划分的决策路径不会影响到之前的正确决策。

2. 试析使用“最小训练误差”作为决策树划分选择准则的缺陷。

这里使用最小训练误差显然是利用了贪心的思想，那么不可避免的会遇到过早陷入局部最优的问题。

3. 试编程实现基于信息熵进行划分选择的决策树算法，并为表4.3中数据生成一颗决策树。
4. 试编程实现基于基尼指数进行划分选择的决策树算法，并为表4.2中数据生成预剪枝，后剪枝决策树，并与未剪枝决策树进行比较。
5. 试编程实现基于对率回归进行划分选择的决策树算法，并为表4.3数据生成一颗决策树。

这里方便起见（好吧其实就是懒），我们都选择表4.2的数据从而免去处理连续值的麻烦。
这里第五题的题目有些不明白，如果是用对数几率回归来做多变量决策树，那就不存在“划分选择”的问题，所以我倾向于理解为使用对数几率(log odds)$ln(y/(1-y))$作为衡量纯度的标准。 因为这里不太确定，因此也就不放出来误人子弟了。
总的代码见github。其中三种划分方式的核心选择最优划分属性的代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# 信息熵

def infogain_selector(data, dataID, props):
    subdata = data.loc[dataID]
    maxgain = -1024
    
    for prop in props.keys():
        infogain = cal_gain(subdata, props[prop])
        
        if infogain > maxgain:
            maxgain = infogain
            candinate = prop
    return candinate

def cal_gain(data, prop):
    """
    Calcluate the infomation gain of given property in certain dataset
    """
    info_gain = 0
    global_ent = cal_entropy(data)
    total_count = len(data)
    for v in prop['values']:
        subdata = data[data[prop['name']] == v]
        count = len(subdata)
        info_gain -= count/total_count * cal_entropy(subdata)
    info_gain += global_ent
    return info_gain

def cal_entropy(data):
    """
    Calculate the infomation entropy. 
    """
    ent = 0
    total = len(data)
    for l in data['label'].unique():
        p = len(data[data['label'] == l]) / total
        ent -= p * math.log2(p)
    return ent 

# 基尼指数 
def ginindex_selector(data, dataID, props):
    subdata = data.loc[dataID]
    minginindex = 1024
    
    for prop in props.keys():
        ginidex = cal_gini(subdata, props[prop])
        
        if ginindex < minginindex:
            minginindex = ginindex
            candinate = prop
    return candinate

def cal_ginindex(data, prop):
    """
    Calculate the gini index 
    """
    ginindex = 0
    total_count = len(data)
    for v in prop['values']:
        subdata = data[data[prop['name']] == v]
        count = len(subdata)
        ginindex += count/total_count * cal_gini(subdata)
    
    return ginindex

def cal_gini(data):
    """
    Calculate the gini
    """
    gini = 1
    total = len(data)
    for l in data['label'].unique():
        p = len(data[data['label'] == l]) / total
        gini -= p*p 
    return gini

预剪枝部分的核心代码为： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def pre_pruning(data, dataID, prop):
    """
    Decide if or not to prune
    """
    subdata = data.loc[dataID]
    total_count = len(data)
    label = subdata['label'].value_counts().argmax()
    acc = len(subdata[subdata['label']==label]) / total_count  
    correct_count = 0 
    
    for v in prop['values']:
        temp = subdata[subdata[prop['name']]==v]
        if len(temp) > 0:
            label = temp['label'].value_counts().argmax()
        correct_count += len(temp[temp['label'] == label])
    new_acc = correct_count / total_count  
    if new_acc >= acc:
        return False
    else:
        return True

后剪枝的核心部分在： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Tree(): 
    def __init__(....):
        .....  
    
    def train(self, data): 
    .... 
    if self.prune == 'post':
        for cur_node in self.queue[::-1]:
            
            flag = post_pruning(cur_node, data, val_data)
            if flag:
                cur_node.split_prop = None
                cur_node.label = data.loc[cur_node.dataID]['label'].value_counts().argmax()
                for son in cur_node.sons:
                    son.label = None
                    son.split_prop = None
                cur_node.sons = []
        new_queue = []
        for i in self.queue:
            if not(i.label == None and i.split_prop == None):
                new_queue.append(i)
        self.queue = new_queue  

    
def post_pruning(node, data, val_data):
    if node.split_prop == None:
        return False

    subdata = data.loc[node.dataID]
    total_count = len(val_data)
    label = subdata['label'].value_counts().argmax()
    acc = len(val_data[val_data['label']==label]) / total_count
    correct_count = 0 
    
    for v in node.split_prop['values']:
        temp = subdata[subdata[node.split_prop['name']]==v]
        temp_val = val_data[val_data[node.split_prop['name']]==v]
        if len(temp) > 0:
            label = temp['label'].value_counts().argmax()
        correct_count += len(temp[temp['label'] == label])
    new_acc = correct_count / total_count  
    if new_acc >= acc:
        return False
    else:
        return True

注意这里由于训练集和验证集是随机划分的，所以生成的决策树和书上的会有一些不同。
在使用Gini指数作为划分标准时，我们可以看到三种剪枝策略分别生成如下决策树。可以发现后剪枝生成的决策树节点会比预剪枝要多一些。

6 试选择4个UCI数据集，对上述3中算法所产生的未剪枝，预剪枝，后剪枝决策树进行实验比较，并进行适当的统计显著性检验。

这里偷点懒吧，就选3个数据集，分别是Car Evaluation, Balance Scale, Audiology。 这里我将数据做了一些预处理（加列名/填充缺失值/格式调整/种类ID化）放在这里。

我们随机按8：2来分割训练集和测试集，实验结果跑10遍取平均值:
Audiology 这里是一个24类的分类，而且有69个属性，但数据量仅仅有200+，所以accuracy会比较低：

训练集/测试集acc Gini指数 信息增益
不剪枝 1/0.214 0.836/0.205
预剪枝 1/0.230 1/0.156
后剪枝 1/0.245 1/0.063

我们可以看到这些算法都有严重的过拟合（因为数据量太小而类数过多）。
相交而言使用Gini指数加上后剪枝的算法会在测试集上去的较好的结果。

Car Evaluation
这个数据集是一个三分类的问题，数据有6个属性，总共1700多条数据。相比上面的24分类，这个的准确度就高很多了。

训练集/测试集acc Gini指数 信息增益
不剪枝 0.814/0.790 0.836/0.0.844
预剪枝 0.841/0.835 0.839/0.828
后剪枝 0.821/0.775 0.831/0.795

这里可以看到预剪枝能够成功提高模型的泛化能力，但是注意到后剪枝带来的效果基本为负的。 这里有些令人费解，没有找出相关的原因。

Balance Scale
该数据集是一个四变量的三分类问题，共有600+数据。

训练集/测试集acc Gini指数 信息增益
不剪枝 0.830/0.827 0.823/0.803
预剪枝 0.837/0.803 0.823/0.800
后剪枝 0.827/0.808 0.829/0.792

总结起来可以发现，决策树算法在面临过多分类和过多属性（相比于数据量）的数据时，会表现很差，往往会有严重的过拟合。
而在类数较少，数据较多的情况下能够取得较好的成绩。

7 图4.2是一个递归算法，若面临巨量数据，则决策树的层数会很深，使用递归方法易导致“栈”溢出。试使用“队列”数据结构，以参数MaxDepth控制树的最大深度，写出与图4.2等价，但不使用递归的决策树生成算法

这个一般我写代码都会默认把这个搜索写出广度优先了，核心代码部分形如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Tree():

    def __init__(self, mode='Gain', prune='no'):
        pass
        

    def train(self, data):
        i = 0
        while i < len(self.queue):
            new_nodes = self.queue[i].split(data, mode=self.mode)
            if new_nodes is not None:
                self.queue.extend(new_nodes)
            i += 1

8 试将决策树生成的深度优先搜索过程修改为广度优先搜索，以参数MaxNode控制树的最大节点数，将题4.7中基于队列的决策树算法进行改写，对比题4.7中的算法，试析哪种方式更易于控制决策树所需存储不超过内存。

改写就不写了，简单分析下吧。
应该来说，队列模拟递归的深度优先会比广度优先更加省内存一些，但是不加剪枝的话，深度优先可能更容易导致过拟合。

9 试将4.4.2节对缺失值的处理机制推广到基尼指数的计算中去。

这个仿照4.12式可得：

其中：

10 从网上下载或编程实现任意一种多变量决策树算法，并观察其在西瓜数据集3.0上的结果。