点击上方卡片链接就可以进入专栏，专栏右上角有订阅选项，欢迎大家订阅～

前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第1.9节：决策树-特征选择准则。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

PS：这个月工作和生活上有较多事情需要处理，导致专栏拖更了，跟同学们说声抱歉。接下来鬼仔会加快更新速度，保持质量的同时，坚持每周两～三更！

一、原理

1. 决策树模型

决策树其实就是一个if-else规则的集合，决策树的根结点到叶结点的每一条路径都构建了一条互斥且完备的规则。决策树还表示给定特征条件下类的条件概率分布：决策树将特征空间划分为互不相交的区域，并在每个区域定义了一个类的概率分布。

决策树的学习目标是根据给定的训练数据构建一个决策树模型，使它能够对新的实例进行正确的分类。我们首先要确定决策树的损失函数，一般是正则化的极大似然函数，而决策树的学习策略就是以损失函数为目标函数的最小化。决策树一般采用启发式的递归算法，递归地选择最优特征进行划分，直到所有训练数据被正确分类，或者无法找到合适的特征。

启发式算法构建出的决策树可能会发生过拟合现象，因此需要对已生成的树自下而上进行剪枝，去掉过于细分的叶结点，降低决策树的复杂度，提高泛化能力。如果样本有很多冗余特征，可以先做一轮特征筛选，再去构建决策树。

决策树算法包括三个重要环节：特征选择、结点生成和剪枝，接下来我会一一进行原理+真题讲解。

2. 特征选择准则

直觉上说，如果在当前的数据集合中，一个特征具有更好的分类能力，那么应该选择该特征作为分裂结点。关键在于如何定义特征的分类能力？决策树引入了信息增益、信息增益比和基尼指数等定义，前面两个定义都基于信息论与概率统计中的熵。

2.1. 熵和条件熵

熵是表示随机变量不确定性的度量，越不确定的变量，它的熵就越大。设X是一个有限取值的离散随机变量，其熵的表达式如下：

，

其中代表变量的种不同的离散取值。而代表了X取值为的概率，为以2或者e为底的对数。

熵越大，随机变量的不确定性就越大，从定义可知：

，即当变量的种取值概率都一样时（均为），的熵最大，此时具有最大的不确定性。

进一步地，我们可以定义条件熵，表示在已知随机变量的条件下随机变量的不确定性，其表达式如下：

，其中。

简单来说，条件熵度量了我们在知道以后剩下的不确定性。

2.2. 信息增益

信息增益表示样本集合的熵与给定特征条件下的条件熵之差，这其实等价于集合中类与特征之间的互信息：

。

信息增益表示了由于特征A而使得对数据集的分类的不确定性减少的程度，不同的特征具有不同的信息增益，信息增益大的特征具有更强的分类能力。

所以，决策树可以利用信息增益准则来选择特征：对于给定的数据集合，依次计算