决策树

一、什么是决策树

人工智能有三大流派：符号主义、连接主义、行为主义。决策树是属于符号主义的一种人工智能回归分类算法。符号主义认为通过给予计算机一些最基本的规则和逻辑，计算机可以自行进行一系列的演算、推理从而获得智能。决策树顾名思义，它的算法过程与数据结构中的二叉树类似。决策树具有根节点（即需要划分的整个数据集），将根节点输入到DecisionTreeClassifier函数中，即可输出一棵树，这棵决策树完整地体现了整个数据集的划分逻辑过程。

二、决策树的应用

决策树是集成学习中最为广泛使用的基模型。梯度提升树(GBDT)，XGBoost以及LightGBM等先进的集成模型都采用了决策树作为基模型，在广告计算、CTR预估、金融风控等领域大放异彩。

三、决策树构建的逻辑过程

输入：训练集D={(𝑥1x1,𝑦1y1),(𝑥2x2,𝑦2y2),....,(𝑥𝑚xm,𝑦𝑚ym)};

特征集A={𝑎1a1,𝑎2a2,....,𝑎𝑑ad}

输出：以node为根节点的一颗决策树

过程：函数TreeGenerate(𝐷D,𝐴A)

下面是我整理的决策树算法的流程图：

决策树的构建过程是一个递归过程。函数存在三种返回状态：（1）当前节点包含的样本全部属于同一类别，无需继续划分；（2）当前属性集为空或者所有样本在某个属性上的取值相同，无法继续划分；（3）当前节点包含的样本集合为空，无法划分。

四、最优划分属性 $a{*}$ 的选择

(一)利用信息增益选择最优划分属性（ID3算法）

1、信息熵：用来度量信息的纯度，信息熵越小，信息的纯度越高

设S是训练集，S的目标属性（特征集）是C，且C具有m个类标号值。 $p_{i}$ 是类标号值为 $C_{i}$ 的样本占S样本容量的比值，则信息熵（Entropy）表示如下：

$Entropy(S)=-\sum_{i=1}^{m} p_{i}\ast log_{2}p_{i}$

2、信息增益：数据集划分前的信息熵减去数据集划分后的信息熵

假设离散属性 $a$ 有 $v$ 个可能的取值{𝑎1a1,𝑎2a2,....,𝑎𝑉aV}，若使用 $a$ 对数据集D进行划分，则产生个 $v$ 分支节点，记为 $D^v$ 。则使用a对数据集进行划分所带来的信息增益被定义为：

$\operatorname{Gain}(D, a)=\operatorname{Entropy}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Entropy}\left(D^{v}\right)$

(二)利用信息增益比选择最优划分属性（C4.5算法）

信息增益比=惩罚参数 $*$ 信息增益

惩罚参数：

$\frac{1}{H_{A}(D)}=\frac{1}{-\sum_{i=1}^{n}\frac{\left | D_{i} \right | }{\left | D \right | } log_{2}\frac{\left | D_{i} \right | }{\left | D \right | } }$

其中 ${H_{A}(D)}$ 是特征a的作为D的随机变量的经验熵

(三)利用利用基尼指数选择最优划分属性（CART算法）

基尼指数：

$\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned}$

基尼指数反映了从数据集𝐷D中随机抽取两个的类别标记不一致的概率。

使用特征𝑎a对数据集𝐷D划分的基尼指数定义如下：

$\operatorname{Gini}\operatorname{index}(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)$

决策树