决策树

   决策树是一种树状的机器学习模型，模型中以数据属性做为分支结点，最后的分类结果作为叶子结点。下图是西瓜书里所描述的一棵决策树，其分支结点是数据的属性(纹理、根蒂、触感、色泽)，而叶子结点则是其分类结果。(好瓜、坏瓜)

决策树.PNG

---

决策树的构建

   整个决策树的构建过程如下：

createBranch( 数据集D, 属性集A ){
   if  数据集D不能再分
       形成叶子结点并返回

   寻找划分的最佳特征，将数据集D切分成相应的子集：D_1,D_2,...,D_K
    
    for i: 1 to K
        createBranch( 数据集D_i )
}

整个决策树构建过程，是一个递归过程，不断递归创建直至整个数据集完成为止。这里面最重要的是：寻找划分的最佳特征，因为最佳特征的标准的不同，就代表着构建决策树构建算法的不同。
   构建决策树的算法主要有：ID3(信息增益+多叉树)，C4.5(增益率+多叉树)，C5.0，CART(基尼指数+二叉树)

信息增益与增益率

   信息增益是指数据集划分前与划分后信息熵的差；信息熵的定义：
其中为属于第c类的样本出现的频率，那么信息增益的定义可以写成：
信息增益就是分解前数据集D的信息熵Ent(D)，和根据属性a分解成K个子集后的信息熵的加权平均的差。
   增益率是在信息熵的基础下定义的：
其实增益率相当于是信息增益除以数据集的“数量”，类似于信息增益的平均值，但是这个基数并非只是数据集的规模。

基尼指数

   基尼指数则是CART决策树使用的划分标准。首先基尼值的定义：
其实基尼值主要是形容从一个集合中随机抽取两个样本，其不属于同一类别的概率；在这基础上，基尼指数可定义成：

ID3决策树实现

   本文章中，ID3决策树的数据结构形式参考的是《机器学习实战》中的形式：    关于信息熵和信息增益的实现，只需按着公式实现即可。而关于“寻找最佳划分特征”，遍历属性集中的属性值，分别计算以此属性划分后的集合的信息熵，然后计算信息增益，找到信息增益最大的属性所对应的下标返回，代码如下：

def ID3Core( dataset ):
    
    n = dataset.shape[0]
    dims = dataset.shape[1] - 1
    
    pre_ent = Ent(dataset)
    max_delta = 0.0
    best_idx = -1
    
    for i in range( dims ):
        pro_values = set(dataset[:, i])
        after_ent = 0
        
        for v in pro_values:
            sub_set = dataset[ np.where( dataset[:, i] == v )[0] ]
            after_ent += sub_set.shape[0] * 1.0 / n  * Ent( sub_set )
            
        delta = pre_ent - after_ent
        
        if ( delta > max_delta ):
            max_delta = delta
            best_idx = i
    
    return best_idx

而决策树建立的代码如下：

def createTree(dataset, attr):
    
    #计算集合dataset中最多的类别
    set_value = np.argmax( np.bincount( dataset[:, -1] ) )
    
    #如果dataset中的类别只有一类，建立叶子结点
    if len( set(dataset[:, -1]) ) == 1:
        return dataset[0, -1]
    
    #找到最佳的划分特征
    split_idx = ID3Core(dataset)
    set_values = set(dataset[:, split_idx])
    branch = {}
    
    #根据划分特征里面的特征值，递归地建立决策树
    for v in set_values:
        sub_set = dataset[np.where( dataset[:,split_idx] == v)[0]]
        branch[v] = createTree( np.delete(sub_set, split_idx, axis=1), np.delete(attr, split_idx) )
      
    #属性值没有覆盖到的值，设立为该数据集较多的类别的叶子结点
    rest = attr_values[attr[split_idx]] - set_values
    if len(rest) > 0:
        for v in rest:
            branch[v] = set_value
            
    return { attr[split_idx] : branch }

而具体的分类函数如下：

def classify(Tree, attr, data):
    
    proper = list(Tree.keys())[0]
    branch = Tree[proper]
    idx = attr.index(proper)
    
    for key in branch.keys():
        if data[idx] == key:
            if type(branch[key]).__name__ == 'dict':
                classLabel = classify(branch[key], attr, data)
            else:
                classLabel = branch[key]
                
    return classLabel

   上述实现中，数据集是将其量化成数据，即将数据集合中的属性值相应的属性，标记为数字：0,1,...,k。ID3算法也是适合用于离散值数据，对于连续性数据需要进行离散化。

CART决策树实现

   这里CART的实现，是参考《机器学习实战》。CART与ID3不同之处，CART是一颗二叉树，分支结点不再是某一属性的所有分支，而是某个属性的具体某个值的一个大于和小于的二分；这也意味着，与ID3不同，所有属性不再是使用一次后，将其全部分解，而是可以同时使用，并也可处理连续型数据。对于叶子结点来说，可以是回归类型(一个数值)或者是模型类型(一段线性函数)
回归类型：

def regLeaf(dataset):
    return np.mean( dataset[:, -1] )

def regErr(dataset):
    m = dataset.shape[0]
    return m * np.var( dataset[:, -1] )

模型类型：

def linearSolve(dataset):
    
    m, n = dataset.shape
    X = np.ones((m, n)); y = np.ones((n, 1))
    X[:, 1:n] = dataset[:, 0:n-1]; y = dataset[:, -1]
    
    xTx = np.mat(np.dot(X.T, X))
    
    if np.linalg.det(xTx) == 0.0:
        raise NameError("this matrix is singular, can't do inverse")
        
    ws = np.dot( xTx.I, np.dot(X.T, y) )
    
    return ws, X, y
    
def modelLeaf(dataSet):
    ws, X, Y = linearSolve(dataSet)
    return ws

def modelErr(dataSet):
    ws, X, Y = linearSolve(dataSet)
    yHat = np.dot(X, ws.T)
    
    return np.sum( np.power(Y - yHat, 2) )

选择划分特征的代码：

def chooseBestSplit(dataset, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    
    #数据集仅包含一个类别，直接返回该数据集的类别
    if ( len(set(dataset[:, -1])) == 1):
        return None, leafType( dataset )
    
    tol_gini = ops[0]; tol_n = ops[1]
    m, n = dataset.shape
    
    best_gini = np.inf; best_idx = 0; best_val = 0
    pre_gini = errType( dataset )
    
    for i in range( n-1 ):
        for v in set(dataset[:, i]):
            s1, s2 = splitDataset(dataset, i, v)
            
            #分成两个数据集后，数据集规模太小则不进行切分
            if (s1.shape[0] < tol_n) or (s1.shape[0] < tol_n):
                continue
                
            new_gini = errType(s1) + errType(s2)
            
            if new_gini < best_gini:
                best_gini = new_gini
                best_idx = i
                best_val = v
    
    #如果最好的特征划分后，基尼值的提升不足，则不划分，直接作为叶子结点
    if (pre_gini - best_gini) < tol_gini:
        return None, leafType(dataset)
    
    s1, s2 = splitDataset(dataset, i, v)
    #分成两个数据集后，数据集规模太小则不进行切分, 设置为叶子结点
    if (s1.shape[0] < tol_n) or (s1.shape[0] < tol_n):
        return None, leafType(dataset)
    
    return best_idx, best_val

创建树的代码：

def createTree(dataset, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    
    idx, val = chooseBestSplit(dataset, leafType, errType, ops)
    
    if idx == None:
        return val
    
    tree = {}
    tree['splitIdx'] = idx
    tree['splitValue'] = val
    
    set1, set2 = splitDataset(dataset, idx, val)
    tree['left'] = createTree(set1, leafType, errType, ops)
    tree['right'] = createTree(set2, leafType, errType, ops)
    
    return tree

可以看到，创建回归树和模型树，只是叶子结点和衡量标准不同，其他地方是没什么差别的；并且，可以做进一步想象，对于模型树，叶子结点可不可以选择不只是线性模型，也可不可以选择一个简单的神经网络作为叶子结点？顺便说一下，sklearn里面的decision tree的具体实现是优化版的CART树。

---

决策树的剪枝

   剪枝主要解决的是决策树的“过拟合”的手段。剪枝的基本策略主要有：预剪枝和后剪枝。
   预剪枝是在决策树生成时进行剪枝；对于当前的分支结点，假设此时把它看成叶子结点时其对于训练数据的正确率，然后将该节点进行划分，计算其划分后的孩子结点的正确率；若有所提高则划分(不剪枝)，若没有则不进行划分(剪枝)。
   后剪枝是在决策树生成后进行剪枝；使用后剪枝时，会将训练集分成两部分，一部分用来生成决策树，另一部分进行剪枝。当决策树生成后，会从底到顶遍历分支结点，和预剪枝类似，计算该分支结点的正确率，然后将该分支结点合并成叶子结点再计算其正确率；若正确率有提升，则将该分支结点合并成叶子结点；反之则不做处理。
   这里并未展现剪枝的代码，在《机器学习实战》中，有CART树的剪枝方法。而sklearn的决策树中，并未提供剪枝的方法，但可通过调整关于树的深度等参数，来防止决策树的过拟合。

---

最后

   作为一个分类问题，不可避免地谈到其分类边界；如果把数据的每个属性看作是样本空间的一个坐标轴，而决策树的分类边界其实是由一段段与轴平行的分段所组成，决策树的每个分支结点，则代表一段这样的分段。在真实任务中，决策树也会相对复制，因为决策边界的组成则会有很多段小线段组成。
   也有一种决策树，“多变量决策树”，每个分支结点不再是一个属性，而是属性的线性组合；这样的话，分类边界不再是与轴平行的“线段”，也可以是“斜线”。OC1则是构建“多变量决策树”的主要算法。