决策树一决策树与if-then规则二决策树算法三特征选择四决策树的生成

75 阅读 0 评论 50 点赞

我是靠谱客的博主端庄小白菜，最近开发中收集的这篇文章主要介绍决策树一决策树与if-then规则二决策树算法三特征选择四决策树的生成，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

决策树是一种基本的分类与回归方法。

决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

一决策树与if-then规则

将决策树转换成if-then规则的过程是这样的：

由决策树的根节点到叶节点的每一条路径构建一条规则

路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说：每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

二决策树算法

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

决策树学习算法只要由三部分构成：特征选择，决策树生成，决策树的剪枝。

三特征选择

如果利用一个特征进行分类的结果与随机分类的结果无异，则可以认为这个特征是不具备分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益和信息增益比。

熵(entropy)

在信息论与概率论中，熵(entropy)用于表示随机变量不确定性的度量。

设X是一个有限状态的离散型随机变量，其概率分布为

$p(x = x_i) = p_i, i=1,2,cdots,n$

则随机变量 $x$ 的熵定义为

$h(x)= - sum_{i=1}^{n} p_{i}log(p_i)$

熵越大，随机变量的不确定性就越大。

条件熵(conditional entropy)

随机变量 $x$ 给定的条件下，随机变量 $y$ 的条件熵 $h(y|x)$ 定义为：

$h(y|x) = sum_{i=1}^{n}p_i h(y|x=x_i)$

其中， $p_i = p(x = x_i)$ 。

信息增益(information gain)

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益 $g(d,a)$ 定义为集合D的经验熵 $h(d)$ 与特征A给定条件下D的经验条件熵 $h(d|a)$ 之差，即

$g(d,a)=h(d)-h(d|a)$

根据信息增益准则进行特征选择的方法是：对训练数据集D，计算其每个特征的信息增益，并比它们的大小，从而选择信息增益最大的特征。

假设训练数据集为D，样本容量为|D|,有 $k$ 个类别 $c_k,|c_k|$ 为类别 $c_k$ 的样本个数。某一特征 $a$ 有n个不同的取值 ${a_1,a_2,cdots,a_n}$ 。根据特征A的取值可将数据集D划分为n个子集 $d_1,d_2,cdots,d_n$ , $|d_i|$ 为 $d_i$ 的样本个数。并记子集 $d_i$ 中属于类 $c_k$ 的样本的集合为 $d_{ik},|d_{ik}|$ 为 $d_{ik}$ 的样本个数。