决策树 - 基于CART的决策树

CART
分类回归树(classification and regression tree，CART)模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成以及剪枝组成，既可以用于分类也可以用于回归。同样属于决策树的一种。

算法思想
CART算法采用的是一种二分递归分割的技术，将当前样本分成两个子样本集，使得生成的非叶子节点都有两个分支。因此CART实际上是一颗二叉树。

CART树的特点
CART不是一颗二叉树
CART既是分类树又是回归树
当CART是分类树的时候，采用GINI值作为分裂节点的依据，当CART作为回归树的时候，使用样本的最小方差作为分裂节点的依据
回归树的生成
最小二乘法回归树生成算法
输入：训练数据集D
输出：回归树f(x)f(x)
在训练数据集所在的输入空间中，递归得将每一个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
(1)选择最优切分变量j和切分点s，求解
minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2]
minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2]

遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到误差最小的变量(j,s)，其中R1R1和R2R2表示的是划分之后的空间。
(2)用选定的(j,s)划分区域并决定响应的输出值。
R1(j,s)={x(j)}≤s,R2(j,s)={x|x(j)>s}
R1(j,s)={x(j)}≤s,R2(j,s)={x|x(j)>s}

cm=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2
cm=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2

(3)继续对两个子区域调用步骤(1),(2),直到满足停止条件。
(4)将输入空间划分为M个区域R1,R2,R3....RMR1,R2,R3....RM

数据集合：根据年龄，性别等信息判断是否生还
https://www.kaggle.com/c/titanic/data

image.png

具体步骤：
(1)计算现有特征对该数据集的基尼指数，对于每一个特征A，可以对样本点A是否为a可以将数据集D分成数据集D1,D2；
(2)对于所有的特征A和所有可能的切分点a，选择基尼指数最小的特征以及相对应的切分点作为最优特征和最佳切分点；
选择最佳且分点时，先排序在求当前feature每个切分点的Gini系数，切分点的最小值为当前feature的基尼系数；
(3)对最优子树递归调用(1)(2)，直到满足停止条件，当左D1和D2递归不可分时，众数作为节点的预测结果；
(4)生成CART分类树；
(4)预测时，根据分割点，遍历，一直到有预测结果的节点，把当前节点的预测结果输出；

根据上述训练集合，root的节点的最佳feature为：

   ('Fare', 12.35)：Fare为feature，12.35为最佳分割点

sample code:

# -*- coding: utf-8 -*-
"""
Created on Mon Oct 22 19:02:26 2018

@author: L-ear
"""
import time
import pandas as pd
import numpy as np


# 定义节点类
class node:
    def __init__(self, data_index,
                 left=None, right=None,
                 feature=None, split=None,
                 out=None
                 ):
        self.data_index = data_index  # 集合 落在节点上集合的行索引
        self.left = left  # int 左子树下标
        self.right = right  # int 右子树下标
        self.feature = feature  # string 分裂特征
        self.split = split  # int or float 分割值
        self.out = out  # 叶节点的输出值


def build_tree(S, min_sample_leaf):
    # S为构建决策树使用的数据集
    # min_sample_leaf为叶节点的最小样本数
    # 使用孩子表示法存储树结构
    print(S.index)
    root = node(S.index)
    tree = []
    tree.append(root)
    # i指向当前处理的叶节点
    i = 0
    # j指向tree列表的末尾元素，便于向父节点添加新的叶节点的索引
    j = 0
    # 循环
    # 调用divide函数处理第i个节点
    # 根据返回值判断第i个节点是否可划分
    # 若可划分，则向tree list并入两个新的叶节点，同时为第i个节点添加子树索引
    # 若不可划分，比较i，j大小，若i == j,则跳出循环
    # 否则进入下次循环
    while True:
        res = divide(S, tree[i], min_sample_leaf)
        if res:
            tree.extend(res)  # 将两个叶节点并入树中
            tree[i].left = j + 1
            tree[i].right = j + 2
            j += 2
            i += 1
        elif i == j:
            break
        else:
            i += 1
    return tree


def divide(S, parent, min_sample_leaf):
    # 划分叶节点，判断是否可划分
    print("parent data index : {}".format(parent.data_index))
    data = S.loc[parent.data_index]  # 取出节点数据集
    print("data : {}".format(data))
    res = gini_min(data, min_sample_leaf)
    print("res : {}".format(res))
    if not res:
        parent.out = data.iloc[:, 0].mode()[0]  # 众数作为预测结果
        return None
    feature, split = res
    # gini_min函数返回值为二元组，(最佳分割特征,分割值)
    parent.feature = feature
    parent.split = split
    left = node(data[data[feature] <= split].index)
    right = node(data[data[feature] > split].index)
    return left, right


def gini_min(data, min_sample_leaf):
    # 根据基尼系数得到数据集上的最佳划分
    res = []  # 三元组列表(gini,feature,split)
    S = data.shape[0]
    print('gini_min: %d' % S)
    for feature in np.arange(1, data.shape[1]):
        # 首先判断该列是否为onehot变量，避免onehot变量排序
        if is_one_hot(data, feature):
            bool_indexby0 = data.iloc[:, feature] == 0
            s1 = data.loc[bool_indexby0, data.columns[0]]
            S1 = s1.shape[0]
            S2 = S - S1
            if S1 < min_sample_leaf or S2 < min_sample_leaf:
                continue
            s2 = data.loc[not bool_indexby0, data.columns[0]]
            res.append(((S1 * gini(s1) + S2 * gini(s2)) / S, feature, 0))
        else:
            Gini_list = []  # 二元组列表(gini,split)，存放每个特征的最优gini值和分割点
            s = data.iloc[:, [0, feature]]
            s = s.sort_values(s.columns[1])
            for i in np.arange(min_sample_leaf - 1, S - min_sample_leaf):
                if s.iloc[i, 1] == s.iloc[i + 1, 1]:
                    continue
                else:
                    S1 = i + 1
                    S2 = S - S1
                    s1 = data.iloc[:(i + 1), 0]
                    s2 = data.iloc[(i + 1):, 0]
                    Gini_list.append(((S1 * gini(s1) + S2 * gini(s2)) / S, s.iloc[i, 1]))
            # 存在Gini_list为空的情况
            if Gini_list:
                Gini_min, split = min(Gini_list, key=lambda x: x[0])
                res.append((Gini_min, feature, split))
    # res也可能为空
    if res:
        _, feature, split = min(res, key=lambda x: x[0])
        return (data.columns[feature], split)
    else:
        return None


def gini(s):
    # 1-sum(pi^2)
    p = np.array(s.value_counts(True))
    return 1 - np.sum(np.square(p))


def is_one_hot(data, feature):
    for i in range(data.shape[0]):
        v = data.iloc[i, feature]
        if v != 0 or v != 1:
            return False
    return True


def classifier(tree, sample):
    # 对于一个样本，从根节点开始
    # 根据节点的划分属性和分割值，寻找其子节点
    # 判断子节点是否为叶节点
    # 是，则得到输出，否则继续寻找子节点
    i = 0
    while True:
        node = tree[i]
        if node.out != None:
            return node.out
        if sample[node.feature] <= node.split:
            i = node.left
        else:
            i = node.right


def hit_rate(tree, test):
    # 逐一获取样本的分类结果
    # 对比label属性的数据，确定分类是否准确
    y = test.pop(test.columns[0])
    length = y.size
    y_p = pd.Series([0] * length, index=y.index)
    for i in range(length):
        x = test.iloc[i]
        y_p.iloc[i] = classifier(tree, x)
    #    print(y_p)
    deta = y - y_p
    return deta[deta == 0].size / length


if __name__ == "__main__":
    train = pd.read_csv("data/train.csv")
    test = pd.read_csv("data/test.csv")
    t1 = time.time()
    min_sample_leaf = 31
    print(train.shape)
    tree = build_tree(train, min_sample_leaf)
    t2 = time.time()
    score = hit_rate(tree, test)
    t3 = time.time()
    print('决策树的构建时间为：%f' % (t2 - t1))
    print('测试集分类时间为：%f' % (t3 - t2))
    print('分类正确率为：%f' % score)
    print('参数设置为min_sample_leaf：%d' % min_sample_leaf)

剪枝处理
剪枝是决策树学习算法中对付过拟合的主要手段。主要是从已生成的书中剪掉一些子树或者叶子节点，并将根节点或者父节点作为新的叶子节点，从而简化分类树模型。决策树的剪枝往往是通过极小化决策树的整体损失函数或者代价函数。设树T的叶子节点数为|T|，叶子节点t上有NtNt个样本点，其中k类的样本点数为NktNkt，Ht(T)Ht(T)为结点t上的经验熵，αα>=0为参数，所以损失函数定义为：
Cα(T)=∑t=1|T|NtHt(T)+α|T|
Cα(T)=∑t=1|T|NtHt(T)+α|T|

其中经验熵为
Ht(T)=−∑kNtkNtlogNtkNt
Ht(T)=−∑kNtkNtlogNtkNt
此时令
C(T)=−∑t=1|T|∑k=1KNtklogNtkNt
C(T)=−∑t=1|T|∑k=1KNtklogNtkNt

所以:
Cα(T)=C(T)+α|T|
Cα(T)=C(T)+α|T|
C(T)C(T)表示对训练数据的预测误差，|T||T|表示模型的复杂度。损失函数其实正好表达了两者的平衡。

所以决策树生成的具体流程：

(1)计算每一个结点的经验熵TaTa
(2)递归的从叶子节点开始往上遍历，减掉叶子节点，然后判断损失函数的值是否减少，如果减少，则将父节点作为新的叶子节点。
(3)重复(2)，直到完全不能剪枝。

随机森林--RandomForest

标准随机森林（RF）是以决策树作为基学习器的，一种基于Bagging的拓展算法，在每一轮决策树训练过程中加入了随机属性选择。具体来说，在训练决策树时，是从当前结点的全部属性集合中选择最优的划分属性，而在RF中，对于决策树的每个结点，显示从当前节点的全部属性集合中随机选择一个包含k个属性的子集，之后再从这个子集中选择一个最优的划分属性。毋庸置疑，参数k控制了随机性的引入程度，k越大基学习器的性能越好，但是基学习器之间的独立性会大打折扣；k越小基学习器之间的相关性会降低，但是基学习器的性能也会下降。因此，在很多文献中，这样选择k作为标准随机森林（RF）的两种形式之一，上述算法也被称为Forest-RI，其中RI指的是Random Input（随机输入选择），这种方法适用于原始候选属性集大小d足够大，且该算法由于大大减少了在每个结点进行划分属性的候选属性数量，因此运行时间大大减少。
  但是当d不足够大时，我们就要考虑标准随机森林的另一种形式，即Forest-RC，其中RC指的是Random Combin（随机组合），这种方法通过在每个结点创建候选属性的线性组合，以增加供每个结点进行划分特征选择的候选属性集大小。具体的方法是：从决策树的每个结点的原始候选属性集合中，随机选择L个属性（L < k），之后将这些属性用区间[-1,1]的均匀分布产生的系数进行线性组合，来生成大小为k的候选属性集合，最后从这个集合中选择最优划分属性（线性组合），这样，每个基学习器与多变量决策树类似。
比较多变量CART树、Bagging、以多变量CART树作为基学习器的随机森林；
步骤：

1. 根据输入，自采样，从数据集合中随机挑选出部分feature和部分数据；
   2）根据1中采样的数据，构建决策树；
2. 重复1和2中的步骤，指导构建出K个树；
   3）预测时，根据所有树的结果进行投票，以最大投票或者加权结果作为最终解雇；
   sample code：

import DecisionTree as DT
import numpy as np
import pandas as pd
import time


# ip 随机挑选的样本比例为(ip,1)中的一个随机数
# jp 随机挑选的特征比例


def RandomForest(train, n_trees, min_sample_leaf, ip, jp):
    forest = []  # 存放训练得到的所有的决策树
    fn = int(jp * (train.shape[1] - 1))

    for n in range(n_trees):
        t1 = time.time()
        sf = np.random.choice(
            np.arange(1, train.shape[1]),
            fn,
            replace=False)
        sf = np.append(0, sf)  # 保证label在第一列
        train_n = train.iloc[:, sf]
        p = np.random.random_sample() * (1 - ip) + ip
        train_n = train_n.loc[
            np.random.choice(train_n.index,
                             int(p * train_n.index.size),
                             replace=False)]
        # train_n为随机选出的第n棵树的训练集
        forest.append(DT.build_tree(train_n, min_sample_leaf))
        t2 = time.time()
        print('构建第%d棵树的时间为%f' % (n, t2 - t1))
    return forest


def hit_rate(forest, test):
    # 取出测试集中非标签属性的数据
    # 逐一获取样本的分类结果
    # 对比label属性的数据，确定分类是否准确
    y = test.pop(test.columns[0])
    length = y.size
    y_p = pd.Series([0] * length, index=y.index)
    n_trees = len(forest)
    res = [0] * n_trees  # 存放每棵树的预测结果
    for i in range(length):
        x = test.iloc[i]
        for t in range(n_trees):
            res[t] = DT.classifier(forest[t], x)
        y_p.iloc[i] = max(res, key=res.count)
    deta = y - y_p
    return deta[deta == 0].size / length


if __name__ == "__main__":
    ip = 0.85
    jp = 0.8
    n_trees = 30
    min_sample_leaf = 5
    # 上面是待调参数
    train = pd.read_csv("data/train.csv")
    test = pd.read_csv("data/test.csv")
    forest = RandomForest(train, n_trees, min_sample_leaf, ip, jp)
    t1 = time.time()
    score = hit_rate(forest, test)
    t2 = time.time()
    print('测试集分类时间为%f' % (t2 - t1))
    print('参数设置为n_trees=%d,min_sample_leaf=%d,ip=%f,jp=%f' % (n_trees, min_sample_leaf, ip, jp))
    print('分类正确率为%f' % score)

决策树的优缺点：
优点:
(1)速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词；
(2)准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则.不同于NN网络的黑盒特性；
(3)可以处理连续和种类字段；
(4)不需要任何领域知识和参数假设；
(5)适合高维数据；
缺点:
(1)对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征；
(2)容易过拟合，尤其是噪声过多；
(3)忽略属性之间的相关性；
(4)决策树是建立在feature之间独立，实际应用时feature之间往往是有关联的；

随机森林的优点：

• 表现性能好，与其他算法相比有着很大优势。
• 随机森林能处理很高维度的数据（也就是很多特征的数据），并且不用做特征选择。
• 在训练完之后，随机森林能给出哪些特征比较重要。
• 训练速度快，容易做成并行化方法(训练时，树与树之间是相互独立的)。
• 在训练过程中，能够检测到feature之间的影响。
• 对于不平衡数据集来说，随机森林可以平衡误差。当存在分类不平衡的情况时，随机森林能提供平衡数据集误差的有效方法。
• 如果有很大一部分的特征遗失，用RF算法仍然可以维持准确度。
• 随机森林算法有很强的抗干扰能力（具体体现在6,7点）。所以当数据存在大量的数据缺失，用RF也是不错的。
• 随机森林抗过拟合能力比较强（虽然理论上说随机森林不会产生过拟合现象，但是在现实中噪声是不能忽略的，增加树虽然能够减小过拟合，但没有办法完全消除过拟合，无论怎么增加树都不行，再说树的数目也不可能无限增加的。）
• 随机森林能够解决分类与回归两种类型的问题，并在这两方面都有相当好的估计表现。（虽然RF能做回归问题，但通常都用RF来解决分类问题）。
• 在创建随机森林时候，对generlization error(泛化误差)使用的是无偏估计模型，泛化能力强。

随机森林的缺点：

• 随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够做出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过度拟合。（PS:随机森林已经被证明在某些噪音较大的分类或者回归问题上回过拟合）。
• 对于许多统计建模者来说，随机森林给人的感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。
• 可能有很多相似的决策树，掩盖了真实的结果。
• 对于小数据或者低维数据（特征较少的数据），可能不能产生很好的分类。（处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处）。
• 执行数据虽然比boosting等快（随机森林属于bagging），但比单只决策树慢多了。

1. boosting，它的特点是各个弱学习器之间有依赖关系。
2. bagging，它的特点是各个弱学习器之间没有依赖关系，可以并行拟合。

PS:重要的点：

• RF采用多个决策树的投票机制来改善决策树。
• 为什么不能用全样本去训练m棵决策树？
  答：全样本训练忽视了局部样本的规律，对于模型的泛化能力是有害的（如果有m个决策树，那就需要m个一定数量的样本集来训练每一棵树）
• 产生n个样本的方法，采用Bootstraping法，这是一种又放回的抽样方法，产生n个样本。
• 最终采用Bagging的策略来获得，即多数投票机制。

code and data：
github: https://github.com/LovelyLittleDemon/MLearning/

参考：
https://blog.csdn.net/gzj_1101/article/details/78355234
https://blog.csdn.net/zhongjunlang/article/details/79488955