决策树

1. 概念

决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据集进行分割,使得对各个子数据集有一个最好的分类过程,这一过程对应着对特征空间的划分,也对应着决策树的构建。
开始构建根节点,将所有的训练数据集都放在根节点,选择一个最有特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下获得最好的分类。如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到对应的叶节点中去;如果还有子集不能够被基本正确分类,那么就对这些子集新的选择最优特征,继续对其进行分割,构建相应的结点。如此递归下去,直到所有的训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶节点上,即都有了明确的分类,这就生成了一颗决策树。我们在具体选取的时候会用到两个准则:信息增益或信息增益比。

  • 熵:
    在信息论和概率统计中,熵表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量,其概率分布为:P(X=xi)=pi,i=1,2,…,n。
    则随机变量X的熵定义为

  • 条件熵:
    设有随机变量(X,Y)其联合概率分布为:P(X=xi,Y=yi)=Pij,条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定条件下随机变量Y的条件熵H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的数学期望:H(Y|X)=∑pi H(Y|X=xi)。

  • 信息增益:
    信息增益表示在得知特征X的信息而使得类Y的不确定性减少的程度。
    特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A在给定条件下D的经验条件熵H(D|A)之差,即g(D,A)=H(D)-H)(D|A)。
    根据信息信息增益选择特征的方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较他们的大小,选择信息增益最大的特征。

  • 信息增益比:
    信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量IR(X,Y),它是信息增益和特征熵的比值。表达式如下:

    其中D为样本特征输出的集合,A为样本特征,对于特征熵HA(D), 表达式如下:

    其中n为特征A的类别数, Di为特征A的第i个取值对应的样本个数。|D|为样本个数。
    特征数越多的特征对应的特征熵越大,它作为分母,可以校正信息增益容易偏向于取值较多的特征的问题。
    而在scikit-learn中决策树使用的是CART算法

2. CART分类树建立算法的具体流程

下面我们看看CART分类树建立算法的具体流程
算法输入是训练集D,基尼系数的阈值,样本个数阈值。
输出是决策树T。
我们的算法从根节点开始,用训练集递归的建立CART树。
1) 对于当前节点的数据集为D,如果样本个数小于阈值或者没有特征,则返回决策子树,当前节点停止递归。
2) 计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归。
3)计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。
4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2.
5) 对左右的子节点递归的调用1-4步,生成决策树。

3. API: ·sklearn.tree.DecisionTreeClassifier·

以下是它的源码,

4. 相关参数:

  • criterion:特征选择的标准,有信息增益和基尼系数两种,使用信息增益的是ID3和C4.5算法(使用信息增益比),使用基尼系数的CART算法,默认是gini系数。

  • splitter:特征切分点选择标准,决策树是递归地选择最优切分点,spliter是用来指明在哪个集合上来递归,有“best”和“random”两种参数可以选择,best表示在所有特征上递归,适用于数据集较小的时候,random表示随机选择一部分特征进行递归,适用于数据集较大的时候。

  • max_depth:决策树最大深度,决策树模型先对所有数据集进行切分,再在子数据集上继续循环这个切分过程,max_depth可以理解成用来限制这个循环次数。

  • min_samples_split:子数据集再切分需要的最小样本量,默认是2,如果子数据样本量小于2时,则不再进行下一步切分。如果数据量较小,使用默认值就可,如果数据量较大,为降低计算量,应该把这个值增大,即限制子数据集的切分次数。

  • min_samples_leaf:叶节点(子数据集)最小样本数,如果子数据集中的样本数小于这个值,那么该叶节点和其兄弟节点都会被剪枝(去掉),该值默认为1。

  • min_weight_fraction_leaf:在叶节点处的所有输入样本权重总和的最小加权分数,如果不输入则表示所有的叶节点的权重是一致的。

  • max_features:特征切分时考虑的最大特征数量,默认是对所有特征进行切分,也可以传入int类型的值,表示具体的特征个数;也可以是浮点数,则表示特征个数的百分比;还可以是sqrt,表示总特征数的平方根;也可以是log2,表示总特征数的log个特征。

  • random_state:随机种子的设置,与LR中参数一致。

  • max_leaf_nodes:最大叶节点个数,即数据集切分成子数据集的最大个数。

  • min_impurity_decrease:切分点不纯度最小减少程度,如果某个结点的不纯度减少小于这个值,那么该切分点就会被移除。

  • min_impurity_split:切分点最小不纯度,用来限制数据集的继续切分(决策树的生成),如果某个节点的不纯度(可以理解为分类错误率)小于这个阈值,那么该点的数据将不再进行切分。

  • class_weight:权重设置,主要是用于处理不平衡样本,与LR模型中的参数一致,可以自定义类别权重,也可以直接使用balanced参数值进行不平衡样本处理。

  • presort:是否进行预排序,默认是False,所谓预排序就是提前对特征进行排序,我们知道,决策树分割数据集的依据是,优先按照信息增益/基尼系数大的特征来进行分割的,涉及的大小就需要比较,如果不进行预排序,则会在每次分割的时候需要重新把所有特征进行计算比较一次,如果进行了预排序以后,则每次分割的时候,只需要拿排名靠前的特征就可以了。

5. 决策树算法的优点:

1)基本不需要预处理,不需要提前归一化,处理缺失值。
2)相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释
3)可以交叉验证的剪枝来选择模型,从而提高泛化能力。
4)对于异常点的容错能力好,健壮性高。

6. 决策树算法的缺点:

1)决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
2)决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
3)寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。
4)有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。

0条评论