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

决策树(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实现基本思路如下,基本参考《统计学习方法》:

  • 对每个特征的每个切点分别计算基尼系数
  • 选择基尼系数最小的切点将数据集分成两部分(二叉树)
  • 迭代上述两个步骤,直到满足停止阈值才停止,最终形成一个决策树

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)

测试误差为:13.5%,跟之前的朴素贝叶斯的结果差不多,但是这个是未剪枝的,如果按照成熟的决策树算法,应该误差会再小一点

参考资料:
「决策树」| Part4—CART决策树
Python实现决策树2(CART分类树及CART回归树)
决策树之CART算法原理及python实现
机器学习|决策树算法及实现
统计学习方法|决策树原理剖析及实现
「决策树」| Part5—Python实现CART决策树

本文出自于http://www.bioinfo-scrounger.com转载请注明出处