决策树算法

决策树（DT）是一种基本的分类和回归方法。在分类问题中它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，学习思想包括ID3,C4.5,CART（摘自《统计学习方法》）。

CLS
ID3
C4-5
CART

概述

1.1 决策树（DT）是一种基本的分类和回归方法。在分类问题中它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，学习思想包括ID3,C4.5,CART（摘自《统计学习方法》）。

1.2 Bagging :基于数据随机重抽样的集成方法（Ensemble methods），也称为自举汇聚法（boostrap aggregating）,整个数据集是通过在原始数据集中随机选择一个样本进行替换得到的。进而得到S个基预测器（ base estimators），选择estimators投票最多的类别作为分类结果，estimators的平均值作为回归结果。（摘自《统计学习方法》和scikit集成方法介绍）

1.3 随机森林（RF）：基于boostrap重抽样和随机选取特征，基预测器是决策树的集成方法（Ensemble methods）

1.4 Boosting :通过改变样本的权重（误分样本权重扩大）学习多个基预测器，并将这些预测器进行线性加权的集成方法（摘自《统计学习方法》）

1.5 梯度提升决策树（GBDT）:基于boosting方法，提升方向是梯度方向的决策树的集成方法（Ensemble methods）

1.6 XGBDT:基于GBDT的一种升级版本，对目标函数做了二阶导数，主要改进是使用了正则化和特征分块存储并行处理（参考大杀器xgboost指南）

1.7 回归/分类树树模型函数：

image

，这里数据集被划分为R1,...,Rm个区域，每一个区域对应一个预测值Cm;其中I()是指示函数，当满足条件时返回1，否则为0

1.8 决策树常见的损失函数：

用于分类的损失函数：01损失，LR的对数损失，softmax的mlogloss

用于回归的损失函数：线性回归的MSE

原理

<统计学习方法> 李航第5章决策树

本质

决策树学习本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树。能对训练数据进行正确分类的决策树可能有多个，也可能一个也没有.我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力. 决策树学习是由训练数据集估计条件概率模型.基于特征空间划分的类的条件概率模型有无穷多个. 我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测.

CLS（Concept Learning System）算法

CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础

CLS基本思想

从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集：
 如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。