统计学习方法-决策树笔记

决策树（decision tree）是一种基本的分类与回归方法；其分类决策模型是一种对类进行分类的树形结构，由节点和有向边组成；节点除了根节点外，又分为内部节点和叶节点，前者表示一个特征，后者表示一个类

决策树学习的算法通常是一个递归选择最优特征的过程，比如：先选择一个最优的特征，将训练集分割成子集，如果其中有子集还未被正确分类，则继续根据该子集选择新的最优特征并对其分类，迭代上述步骤直至发生下述情况才结束：

• 当前数据集（子集）都被正确分类，或者说当前子集已经同属同一类（熵达到阈值、增益小于阈值）
• 特征为空，或者说没有合适的特征

因此根据特征值选择的策略不同，有不同的生成决策树的方法：

• ID3：以信息增益准则来选择特征，选择信息增益较大的特征
• C4.5/C5.0：以信息增益比准则来选择特征，选择信息增益率较大的特征
• CART：以基尼系数准则来选择特征，选择基尼系数较小的特征（分类树）、均方差较小的特征（回归树）

上述准则的公式可看《统计学习方法》，从公式中可看出，信息增益比是对信息增益的一种改进，进而克服前者对于选择取值较多的特征的偏好（使得泛化能力弱），但是后者则又带来了对于选择取值较少的特征的偏好（解决办法似乎有：先选择信息增益高于平均值的特征，然后再根据信息增益率来选择上述前提下最大的那个特征，反正计算信息增益率的时候也要先计算信息增益的）

ID3/C4.5/CART都是贪婪算法，只考虑当前条件达到局部最优，而无法达到全局最优，但近似于全局最优；以上三个算法不同点在于：

• ID3/C4.5只能处理分类问题，而CART可以处理分类/回归问题
• ID3/C4.5构建多叉树，而CART构建二叉树（因此其适合于）；因此当某个特征有多个取值时，前者则会产生多个分支，而后者会根据切点，将多个特征取值分割成两部分，变成两个分支；但是由于CART这次没有把该特征完全分开，所以后续还会继续选择该特征；不像ID3/C4.5那样，特征只参与一次节点的构建
• ID3不支持连续型数值，而C4.5/CART则支持（其思路都是将连续的特征离散化，差别在于前者是用信息增益率，而后者则是基尼系数）
• ID3不支持缺失值，而C4.5/CART则支持
• ID3不支持树剪枝，而C4.5/CART则支持

剪枝是为了克服用生成算法产生的决策树过拟合的问题，过拟合是由于在学习的过程中产生了过于复杂的决策树，使得其在训练集中表现的很好，但是泛化能力过低，因此需要对决策进行简化；以及用后来出的随机森林可以减少过拟合现象

决策树的剪枝可以分成两部分：预剪枝和后剪枝：

• 预剪枝是在决策树生成过程中，在划分数据集的时候，根据一些条件，比如：结点中样本数是否小于阈值或者基尼系数是否小于阈值，来判断是否要继续划分
• 后剪枝则是先生成一个完整的决策树，再从底往顶进行剪枝处理，消除多余的结点

对于数据集中的缺失值，要么采用一定方法进行缺失值补空，要么按照其所在的比例分配到各个结点中，进而方便后续的计算

决策树的优点如下(参考自 决策树算法的 Python 实现 ):

• 易于理解和解释，甚至比线性回归更直观；
• 与人类做决策思考的思维习惯契合；
• 模型可以通过树的形式进行可视化展示；
• 可以直接处理非数值型数据，不需要进行哑变量的转化，甚至可以直接处理含缺失值的数据；

缺点如下:

• 对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；
• 特别是当数值型变量之间存在许多错综复杂的关系，如金融数据分析；
• 决定分类的因素取决于更多变量的复杂组合时；
• 模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同。

关于决策树更深的模型有软决策树、决策森林、随机森林等

未含剪枝的决策树CART算法的Python实现如下，基本参考《统计学习方法》：

class decision_tree:
    # 根据公式5.24计算基尼系数
    def calc_sub_Gini(self, y_sub):
        gini_sub = []
        for cls in set(y_sub):
            gini_sub.append((np.sum(y_sub == cls) / len(y_sub)) ** 2)
        return 1- sum(gini_sub)

    # 选择最优特征和最优切点
    def calc_best_feature(self, dataset, label):
        feature_gini = {}
        for feature in range(dataset.shape[1]):
            arr_len = len(np.unique(dataset[:,feature]))
            if (arr_len == 1):
                # 特征都为同一个数值，无切点（或者说该特征已被用尽）
                continue
            elif (arr_len == 2):
                # 二类分类问题
                feature_arr = np.unique(dataset[:,feature])[0]
                split1 = dataset[:,feature] == feature_arr
                split2 = dataset[:,feature] != feature_arr
                gini = sum(split1) / len(split1) * self.calc_sub_Gini(label[split1]) + sum(split2) / len(split2) * self.calc_sub_Gini(label[split2])
                feature_gini[(feature, feature_arr)] = gini 
            else:
                # 多类分类问题
                for feature_arr in set(dataset[:,feature]):
                    split1 = dataset[:,feature] == feature_arr
                    split2 = dataset[:,feature] != feature_arr
                    gini = sum(split1) / len(split1) * self.calc_sub_Gini(label[split1]) + sum(split2) / len(split2) * self.calc_sub_Gini(label[split2])
                    feature_gini[(feature, feature_arr)] = gini
        if (len(feature_gini) == 0):
            # 即该数据集的特征值为空了
            return None
        else:
            # 取最小基尼系数的特征值作为切点
            best_feature = min(feature_gini, key = feature_gini.get)
            return best_feature

    # 分割数据集到两个（左右）子节点中
    def split_dat(self, dataset, label, best_feature):
        feature = best_feature[0]
        feature_value = best_feature[1]

        left_label = label[dataset[:,feature] == feature_value]
        right_label = label[dataset[:,feature] != feature_value]
        left_dat = dataset[dataset[:,feature] == feature_value,:]
        right_dat = dataset[dataset[:,feature] != feature_value,:]

        return left_label,right_label,left_dat,right_dat

    # 生成决策树
    def create_Tree(self, dataset, label):
        # 样本属于同一类，分配到单节点，函数停止
        if (len(np.unique(label)) == 1):
            return label[0]

        best_feature = self.calc_best_feature(dataset, label)

        # 没有更多的特征，特征已用完，函数停止
        if (best_feature == None):
            label_number = {}
            label_number = dict(Counter(label))
            return max(label_number, key=label_number.get) 

        left_label,right_label,left_dat,right_dat = self.split_dat(dataset, label, best_feature)

        # 用字典构建树，并迭代函数
        tree = {best_feature:{}}
        tree[best_feature]["left"] = self.create_Tree(left_dat, left_label)
        tree[best_feature]["right"] = self.create_Tree(right_dat, right_label)

        return tree

    # 通过已构建的决策树预测
    def predict(self, test, tree):
        for k,v in tree.items():
            if (test[k[0]] == k[1]):
                left_leaf = v["left"]
                if (type(left_leaf) == dict):
                    return self.predict(test, v["left"])
                else:
                    return v["left"]
            else:
                right_leaf = v["right"]
                if (type(right_leaf) == dict):
                    return self.predict(test, v["right"])
                else:
                    return v["right"]

先以书中表5.1的训练数据集测试下：

dataset = pd.read_table("tree.txt")
dataset = np.array(dataset)
X = dataset[:,:-1]
y = dataset[:,-1]
dt = decision_tree()
res = dt.create_Tree(X,y)

看下字典中储存的树信息,（2,1）代表第3个特征中1值，left:1代表左枝的标签为1

res
Out[177]: {(2, 1): {'left': 1, 'right': {(1, 1): {'left': 1, 'right': 2}}}}

然后再结合测试数据集 MNIST （数字识别），用上述决策树代码实现如下：

读入测试数据，并按照20%分割训练集和测试集

dataset = pd.read_csv("train.csv")
dataset = np.array(dataset)
dataset[:,1:][dataset[:,1:] != 0] = 1
label = dataset[:,0]

train_dat, test_dat, train_label, test_label = train_test_split(dataset[:,1:], label, test_size = 0.2, random_state = 123456)

构建决策树，并计算测试误差

dtree = decision_tree()
dt = dtree.create_Tree(train_dat, train_label)
error = 0
for i in range(len(test_dat)):
    if (dtree.predict(test_dat[i], dt) != test_label[i]):
        error += 1
print(error / len(test_label) * 100)