决策树学习指南：关于决策树的知识点都帮你整理好了（含代码）

一份你意想不到的决策树学习指南！几乎整合了现在所有决策树知识，希望对大家的学习有所帮助。

介绍

你一生中没有哪一天不需要做出决定。从早餐吃什么到你感兴趣的职业，你的生活都被决策所包围。假设你想出去打球，出门前你会考虑哪些因素？今天会下雨吗？外面会不会太热？作为一名篮球爱好者，你都要被迫接受最后的决定。你从气象部门的网站上查了过去几天的数据，将这些数据与今天的天气状况进行比较，并预测这些条件对于篮球比赛来说是否完的。这就是决策树解决实际问题的途径。

在继续使用决策树的实际功能之前，您需要熟悉以下术语-

• 基尼不纯度（Gini Impurity）

• 熵（Entropy）

基尼不纯度与熵

举例：有两个人感到很无聊，所以他们决定玩一个游戏。谁能最快找到的一根线，最好能够恰好分离蓝色和橙色点，谁就能赢得比赛，唯一的限制是直线必须与任何轴平行。

两人都试了很多方法，找到了以下的线：

从图片就可以很容易看出，乔的尝试比山姆的尝试要好得多，仅是通过直观地显示这些要点即可。 但是，当我们有两种以上的颜色时，事情可能会变得疯狂。 需要一个定量值来判断分裂， 那就是基尼不纯度出现的原因。 它讨论了错误分类点的可能性。

没听懂吗？

让我们先假设条件，然后再进行分裂，即图1。将点错误分类的概率是多少？

我们可以通过两种方式对点进行错误分类。 首先，我们选择一个蓝点并将其分类为橙色。 其次，我们选择一个橙色的点并将其分类为蓝色。

以及

总概率= 0.25 + 0.25 = 0.5（开始时为基尼不纯度）

数据中的任何分割都会将该区域分为两个或更多部分。 最终的基尼不纯度是通过将所有部分的加权和求出的。 基尼不纯度越小，分离效果越好。

让我们分析一下Joe的尝试：

同样，我们也可以分析Sam的尝试：

两次的尝试均显着降低了原始的基尼不纯度，但是Joe进行了更好的拆分，因为基尼不纯度的增益G（之前）-G（之后）对于他的拆分更大。

假设Y是一个随机变量，其取值为{y 1，y 2，y 1，…。，y 1}，那么一种简单的计算基尼不纯度的方法是：

基尼不纯度的性质

令Y取值y₊，y₋（两个类）

情况一：

当100％的数据点属于y₊时。 在这种情况下，系统的基尼不纯度为：

情况二：

当50％的数据点属于y₊时。 在这种情况下，系统的基尼不纯度为：

情况三：

当0％的数据点属于y₊时。 在这种情况下，系统的基尼杂质为：

基尼不纯度w.r.t与y₊的关系图将变为：

接下来，让我们来说说熵。

简单来说，熵就是数据的随机性。 假设您前面有两个盒子。 盒子1装满蓝色球，盒子2装满不同颜色的球。

现在从每个盒子里抽出一个球。你认为从盒子1中抽出的球的颜色最有可能是什么？蓝色，对吧？你能用从2号盒子抽出的球来预测同样的结果吗？我想不是。与盒子1不同，盒子2具有很多随机性。恭喜，你已经明白了熵的含义！如果选择熵作为度量标准，决策树将以这样一种方式拆分数据：每次拆分时，数据的随机性都会不断降低。

假设Y是一个随机变量，取{Y₁，Yü，Y₃，…，Yₖ}的值，则系统的熵计算如下：

熵的性质

令Y取值y₊，y₋（两个类）

情况一：

当99％的数据点属于y₊时，系统的熵在这种情况下为：

情况二：

当50％的数据点属于y₊时。 在这种情况下，系统的熵为：

情况三：

当1％的数据点属于y₊时。 在这种情况下，系统的熵为：

H（y）w.r.t与y₊的关系图将变为：

必须注意的是，当所有值发生的可能性相等时，熵变为最大值=1。

到现在为止，一直都还不错。但是如何利用熵来分割数据呢？

与基尼增益类似，我们使用信息增益（I.G）来决定要分割的最佳特征。

定义如下：

显示基尼系数和y +的熵变化的图形

为什么基尼杂质大于熵？

熵涉及对数计算，而基尼杂质涉及平方计算，计算成本较低，这就是Sklearn库使用基尼杂质作为默认选择标准来构建决策树的原因。

然而，它们之间的差异被观察到是很小的，我们可以继续使用这两个指标中的任何一个。

构建决策树的步骤

1. 决定要断开/拆分数据的特征：对于每个特征，计算信息增益，并选择信息增益最大的特征。
2. 继续拆分数据
3. 如果出现以下情况，请停止拆分数据：

a） 我们得到一个纯节点，即只包含正或负数据点的节点，或者

b） 我们在一个节点上得到很少的点，或者

c） 我们到达树的一定深度

一旦您建立了一个决策树，对于一个查询点，从根遍历树到适当的叶节点。如果叶节点是纯节点，则预测查询点对应的类标签，否则执行多数表决。

分割分类特征

假设我们的数据集是：

有两个特征， 如果只有一个特征，我们没有其他选择。 但是，当我们具有多个特征时，我们需要查看在拆分后提供最大信息增益的特征。

从特征F₁开始：

获得的信息将是：

现在检查特征F2：

（IG）2获得的信息将是：

由于IG2＞ IG1，我们将首先使用特征F2分割数据。 注意，可以使用特征F1进一步分解F2 ＝ IND之后的节点。 最终的树如下图：

直观

让我们使用简单的if-else条件重写上述决策树：

这只是你的决策树。

在编程上，决策树只不过是一系列if-else条件语句。

在几何上，它是一组轴平行的超平面。

分割数值特征

假设我们的数据集是：

1. 按F₁的值排序
2. 如果我们使用F₁取每一个值进行分割

你可以看到，每个节点中只有一个值，这会导致数据过拟合。

解决此问题的方法是定义一个阈值，然后将数据分为两部分-一部分的值小于和等于阈值，另一部分的值大于该阈值。

如何确定阈值？

我们检查每个可能的阈值的信息增益，并选择使其最大化的值。在这里，如果我们使用F₁=4.2分割数据，信息增益将是最大的。

具有多个类别的分类特征

我们已经看到了如何处理分类和数字特征。然而，当一个分类特性有许多分类时，事情会变得疯狂。

假设我们有一个pin代码特性，它可能有1000个pin代码，当我们使用这个特性分割数据时，它将创建1000个子节点，每个节点都有很少的数据点，这将导致过度拟合。

一个技巧是将分类特征转换为数字特征。

代替pin码，我们可以有一个新功能：

所以，现在如果我们使用这个新特性分割数据，子节点将有足够的点来避免过度拟合。

过拟合和欠拟合

当决策树的深度越深，在底部节点出现的数据点就越少，如果这些数据点是离群点，那么我们的模型就会过拟合。由于每次拆分都只是一个if-else条件语句，因此模型的可解释性也会随着树的深度的增加而降低。

当树太浅时，我们可能得不到任何纯节点，纯节点是只有正或负点的节点。在这种情况下，我们必须进行多数表决才能得到结果。

那么决策树的深度应该是多少？

深度是一个超参数，必须使用交叉验证数据集执行超参数调整以获得最佳值。

训练和测试时间复杂性

训练时间复杂性：

在训练阶段会发生的情况是，对于数据集中的每个特征（维度），我们将对数据进行排序（时间为O（n log n）），然后遍历数据点以找到正确的阈值（时间为O（ n）时间。 对于d维，总时间复杂度为：

训练空间复杂性：

训练决策树时，我们需要的是通常以if-else条件存储的节点。

因此，训练空间的复杂性为：O（节点）

测试时间的复杂性为O（深度），因为我们必须从决策树的根节点移动到叶节点。

测试空间的复杂性为O（节点）。

使用决策树进行回归

当我们处理回归问题时，情况会发生变化。 这里的输出不再是一个类，而是一个实数值。

我们如何分割数据？

与分类时的熵或基尼不纯度不同，我们将使用均方误差（MSE）或中位数绝对偏差（MAD）来分割数据。 选择分裂最多的MSE或MAD功能。

我们如何预测测试数据点的价值？

一旦到达叶节点，我们将获取那里已经存在的点的平均值/中位数，并预测其将成为给定测试数据点的输出值。

真实案例

1. 不平衡的数据集：建议通过上采样或类权重来平衡数据集，因为这可能会影响熵值。
2. 高维数据：随着维数的增加，训练的计算时间也增加。建议如果一个特征具有多个类别，则应避免使用一键编码，而应如上所述将其转换为数字特征。
3. 多类别分类：决策树自然可以扩展为处理多个类别。由于可以计算2类以上的熵或基尼杂质，因此也可以通过多数表决做出决定。
4. 特征交互：由于子节点的条件取决于父节点的条件，因此在遍历路径中一起出现的要素相互交互
5. 离群值：如果树很深，离群值会影响树并使树变得不稳定。
6. 可解释性：由于决策树不过是if-else语句的集合，因此它是高度可解释的。但是，随着树的深度增加，可解释性降低。
7. 功能重要性：信息获取量高的那些功能很重要。如果一个功能不止一次用于分割，我们将使用归因于该功能的信息增益的归一化总和。

好处

1. 不需要缩放或标准化数据
2. 高解释性，尤其是当维数较少时
3. 在低延迟系统中有用
4. 更少的超参数数量
5. 适用于分类数据和数值数据
6. 容易明白

局限性

1. 通常需要更多时间来训练模型
2. 当您具有高维数据时，可能不适合
3. 过度拟合数据的可能性很高
4. 数据的微小变化会导致决策树结构的整体变化
5. 树越深越复杂
6. 决策树通常不具备其他分类或回归算法那样的预测准确性

使用Python构建决策树

<code> 
import
 numpy 
as
 np
import
 pandas 
as
 pd
from
 sklearn.datasets 
import
 make_classification
import
 warnings
from
 sklearn.tree 
import
 plot_tree
import
 matplotlib.pyplot 
as
 plt
from
 sklearn.tree 
import
 DecisionTreeClassifier
from
 sklearn.model_selection 
import
 train_test_split
from
 sklearn.model_selection 
import
 RandomizedSearchCV
from
 scipy.stats 
import
 randint


warnings.filterwarnings(
'ignore'
)

 

X, y = make_classification(n_samples=
50
, n_features=
3
, n_informative=
3
,n_redundant=
0
,n_classes= 
2
, weights=[
0.6
],
                           random_state=
15
)

 

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=
0.25
, random_state=
15
,stratify=y)


 

random_search = {
"max_depth"
: list(range(
2
,
7
))+[
None
],
              
"min_samples_leaf"
: range(
3
,
10
),
              
"min_samples_split"
:range(
3
,
10
),
              
"criterion"
: [
"gini"
, 
"entropy"
],
               }
                
clf=DecisionTreeClassifier()


model1 = RandomizedSearchCV(clf,param_distributions=random_search,cv=
4
,random_state=
15
,n_jobs=
-1
,n_iter=
2
,scoring=
"accuracy"
)
model1.fit(X_train,y_train)

 

m1=model1.best_estimator_

 

 
 
plt.figure(figsize=(
8
,
6
))
plot_tree(m1,feature_names=[ 
'f1'
,
'f2'
,
'f3'
],class_names=[
'0'
,
'1'
],filled=
True
);/<code>

感谢sci-kit学习库的plot_tree函数，以可视化决策树。 我们最终得出的决策树：

参考文献

https://victorzhou.com/blog/gini-impurity/

An Introduction to Statistical Learning: With Applications in R

https://towardsdatascience.com/decision-tree-intuition-from-concept-to-application-530744294bb6

Applied Machine Learning by M. Gopal

--END--

欢迎大家关注我们的公众号：为AI呐喊（weainahan）

找工作一定少不了项目实战经验，为了帮助更多缺少项目实战的同学入门Python，我们在头条上创建了一个专栏：《7小时快速掌握Pthon核心编程》，通过一个项目，快速掌握Python，欢迎大家点击链接或者阅读原文进行试看~