关于“树”的算法：现实生活中的决策树

拼搏现实的明天。 2022-12-23 11:12 149阅读 0赞

> 全文共2874字，预计学习时长8分钟

![880a02b74d04ddca189664b6aba1a54a.png][]

图源：unsplash

就像树木是人类生活的重要组成部分一样，基于树的算法也是机器学习的重要组成部分。树的结构给了我们开发算法的灵感，并再将其反馈到机器，让它们学习我们希望它们学习的东西，以解决现实生活中的问题。

这些基于树的学习算法被认为是最好和最常用的监督学习方法之一：决策树、随机森林、梯度提升等方法在各种数据科学问题中得到了广泛应用。对于每一个机器学习的初学者来说，学习这些算法并将其用于建模非常重要。

**决策树是什么?**

决策树是一种带有节点的树状图，节点表示我们选取一个属性并提出问题，边表示问题的答案，叶表示实际输出或类标签。它们被用于具有简单线性决策面的非线性决策。

决策树对例子进行分类，方法是将它们从树的根排序到某个叶节点，叶节点为例子进行分类。树中的每个节点作为某个属性的测试用例，从该节点下行的每条边都对应于测试用例的可能答案之一。这个过程本质上属于递归性质，并且对于每一个扎根于新节点的子树都要重复进行。

![2d20cb8d97056c82e25a393aaee2b9d7.png][]

**现实生活中的决策树**

你肯定在生活中使用过决策树来做决定。举个例子，决定是否要在某天和孩子一起打网球。

这取决于各种各样的因素，比如你是否能按时下班，是否能提前下班，你是否能在晚上6点之前到家，这取决于交通状况，或者你的孩子那天是否已经安排了其他活动；总的来说，你是否能和孩子一起出去打网球，取决于你和你的孩子在那一天的时间安排和外面的天气。

如果天气很好，你可以按时下班，也可以准时回家，孩子也没有别的课，你可以和他一起去网球场。如果你按时到达，但他那天已经安排了其他活动，你可能只想在家放松一下，看一些电影。

![f6c09075dd27c0aff42a3ac38887dbc8.png][]

这是一个典型的现实生活中决策树的例子。我们已经建立了一个树来模拟一组连续的、分层的决策，这些决策最终会导致一些最终的结果。

请注意，我们还选择了相当“高级”的决策，以保持树的规模。例如，如果我们设置很多可能的天气选项，比如25度晴，25度雨，26度晴，26度雨，27度晴……等等，我们的树将变得巨大！确切的温度其实不太重要，我们只是想知道是否适合户外活动。

因此，你可以把最近几天的因素都计算出来，并绘制一个查询表，如下所示。

![a18c0fe84519d3ac1370d3007c714f25.png][]

**决策树算法如何工作？**

![f68d7a301451d228eabbf7982bddb169.png][]

任何决策树算法背后都有如下基本思想：

1.使用属性选择度量（ASM）选择最佳属性来分割记录。

2.将该属性设为一个决策节点，并将数据集分解为更小的子集。

3.通过对每个子元素递归重复此过程来开始建树，直到满足以下条件之一：

· 所有元组属于同一属性值

· 没有其他属性

· 没有其他实例

ASM通过解释给定的数据集为每个特性（或属性）提供了一个等级。最佳得分属性将被选择为分割属性。对于连续值属性，还需要定义分支的分割点。最常用的选择指标是信息增益、增益比和基尼系数。

**信息增益是什么，如何衡量？**

信息增益是一种统计属性，它测量给定属性根据目标分类分离训练实例的程度。

![231861f5fb358abe2e7acc0a019f0792.png][]

信息增益是熵（随机性）的降低。根据给定的属性值计算数据集分割前熵与分割后平均熵的差值。熵的基本计算公式为：

![ae5cfaf488f1116dd4daf8745d2560be.png][]

其中，Pi是D中任意元组属于类Ci的概率。

那么，信息增益的计算方式为：

![0825233d9df658f14e3ad2469e19b17a.png][]

现在，来计算每个父节点和子节点的熵：

E(Parent Node) =-\[P(tennis)log(base2)P(tennis)

\+ P(Home)log(base2)P(Home)\]

= — \[(1/2)log(base2)(1/2) +(1/2)log(base2)(1/2)\]

= 1

Since P(tennis) = 1/2 and P(Home) = 1/2

现在，让我们看看父节点是否按第一个属性分割，即天气。如果我们看到上面给出的数据，根据天气属性，我们会得到以下值，供我们决定是否打网球：

Rainy: Stay at Home

Sunny: Tennis,Tennis,StayHome

![491ad95dd9f7245495fe4770da1ec856.png][]

右侧子节点的熵——E(rainy)：

= -P(Home)log(base2)P(Home)

=-1log(1)= 0

左侧子节点的熵——E(Sunny)：

\-\[P(Home)log(base2)P(Home)

\+ P(Tennis)log(base2)P(Tennis)\]

= -\[(1/3)log(base2)(1/3) +(2/3)log(base2)(2/3)\] = 0.9

可得

Information Gain(Weather) =Entropy(Parent) — \[sum of(weighted average\*entropy of each child)\]

= 1 — \[(3/4)\*(0.9)+(1/4)\*0\] = 0.325

同样，我们也计算了其他属性的熵和信息增益，得到以下结果：

IG(WorkSchedule) = 1

IG(Traffic) = 0.325

IG(Availability) = 0.325

由于“工作日程”这个属性的信息增益最高，我们可以说，能够预测你当天是否会打网球的最准确的属性是你的工作日程。

**基尼指数是什么？**

决策树算法CART（分类与回归树）采用基尼法创建分割点。

![9d04a18ef9c1d4531f01dd264734c8e8.png][]

其中，pi是D中元组属于Ci类的概率。

基尼指数，又称基尼杂质，指计算随机选取某一特定属性时分类错误的概率。如果所有元素都链接到一个类，那么它就可以被称为pure。基尼指数考虑每个属性的二元分割。你可以计算每个分区杂质的加权和。若对属性A进行二叉分割，将数据D分成D1和D2，则D的基尼指数为：

![d7e71868a1f5a7af5634da16e5f555d0.png][]

在离散值属性的情况下，为所选属性提供最小基尼指数的子集被选为分割属性。对于连续值属性，策略是选择每对相邻的值作为可能的分割点，选择基尼指数较小的点作为分割点。

![d5194a2eabb59ac7ec54c1b4d315b1dc.png][]

选择基尼指数最小的属性作为分割属性。

现在，试着根据天气属性来计算上面数据的基尼指数。

Gini(Sunny) = 1 — \[(2/3)\*(2/3) +(1/3)\*(1/3)\] = 4/9 = 0.444

Gini(Rainy) = 1 — \[(1/1)\*(1/1)\] = 0

可得

Gini(Weather) = (3/4) \* 0.444 + (1/4) \* 0 =0.333

基于其他属性，基尼指数如下：

Gini(Traffic) = (3/4) \* \{1 —\[(1/3)\*(1/3) + (2/3)\*(2/3)\] \} + (1/4) \* \{ 1- \[ (1/1)\*(1/1)\]\} = 0.333

Gini(Work Schedule) = (2/4) \* \[1 —(1\*1)\] + (2/4) \* \[1 — (1\*1)\] = 0

Gini(Availability) = 0.333

因此，基尼系数最小的属性，即工作日程，在这里是决策的分割属性。

![a1b50e80198f389d2109d46a35d0d4e7.png][]

**一起分享AI学习与发展的干货**

**欢迎关注全平台AI垂类自媒体 “读芯术”**

![format_png][]

（添加小编微信：dxsxbb，加入读者圈，一起讨论最新鲜的人工智能科技哦～）

[880a02b74d04ddca189664b6aba1a54a.png]: /images/20221120/f82ba5266a764f029baa2050e05c7b8f.png
[2d20cb8d97056c82e25a393aaee2b9d7.png]: /images/20221120/45cab52060854d0ca4269326dd8876ad.png
[f6c09075dd27c0aff42a3ac38887dbc8.png]: https://img-blog.csdnimg.cn/img_convert/f6c09075dd27c0aff42a3ac38887dbc8.png
[a18c0fe84519d3ac1370d3007c714f25.png]: https://img-blog.csdnimg.cn/img_convert/a18c0fe84519d3ac1370d3007c714f25.png
[f68d7a301451d228eabbf7982bddb169.png]: https://img-blog.csdnimg.cn/img_convert/f68d7a301451d228eabbf7982bddb169.png
[231861f5fb358abe2e7acc0a019f0792.png]: https://img-blog.csdnimg.cn/img_convert/231861f5fb358abe2e7acc0a019f0792.png
[ae5cfaf488f1116dd4daf8745d2560be.png]: https://img-blog.csdnimg.cn/img_convert/ae5cfaf488f1116dd4daf8745d2560be.png
[0825233d9df658f14e3ad2469e19b17a.png]: https://img-blog.csdnimg.cn/img_convert/0825233d9df658f14e3ad2469e19b17a.png
[491ad95dd9f7245495fe4770da1ec856.png]: https://img-blog.csdnimg.cn/img_convert/491ad95dd9f7245495fe4770da1ec856.png
[9d04a18ef9c1d4531f01dd264734c8e8.png]: https://img-blog.csdnimg.cn/img_convert/9d04a18ef9c1d4531f01dd264734c8e8.png
[d7e71868a1f5a7af5634da16e5f555d0.png]: https://img-blog.csdnimg.cn/img_convert/d7e71868a1f5a7af5634da16e5f555d0.png
[d5194a2eabb59ac7ec54c1b4d315b1dc.png]: https://img-blog.csdnimg.cn/img_convert/d5194a2eabb59ac7ec54c1b4d315b1dc.png
[a1b50e80198f389d2109d46a35d0d4e7.png]: https://img-blog.csdnimg.cn/img_convert/a1b50e80198f389d2109d46a35d0d4e7.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS85LzEwLzE2ZDE5NjEzMjBmMTY5YmM?x-oss-process=image/format,png