Press "Enter" to skip to content

如何决策:决策树

之前看了一本书《家长效能训练手册》,周末刚好讨论起了关于孩子的教育问题,什幺样的路径可能对于孩子是最好的选择呢。是给与自由,还是用以权威,还是交给时间吧。本科是数学系, 把基础再捡一捡,如果能有一种算法可以解决人生的选择、决策问题,那就完美了,可能不能完全做到,毕竟人生的选择路径,环境,客观因素太多,即使不照着做,可能也会提供一些借鉴意义。决策树,提供了一种思路。

 

01

 

什幺是决策树

 

首先,是一种算法,用来解决分类和回归问题,今天主要切入分类。

 

相比于其他算法有几个优点,

 

 

一般类似于人脑的思考过程,易于理解;

 

相比于其他黑盒的算法,如SVM,NN等,可以更加了解数据处理的逻辑。

 

 

如下图所示, 决策树有如下特点

 

a. 每个节点代表了一个特性(属性);

 

b. 每条树枝代表了一个选择(规则);

 

c. 每个叶子节点代表了一个结果。

 

 

构建决策树有很多种方式, 今天主要说说ID3(Iterative Dichotomiser 3)和CART(Classification and Regresstion Trees)。

 

02

 

ID3 – Iterative Dichotomiser 3

 

以http://santini.se/teaching/ml/2016/Datasets/weather.nominal.arff 的数据为例

 

 

其中有4个属性X(outlook, temp, humidity, windy),1个结果Y(play)。

 

我们需要的是建立X和Y的关系,而建立关系的第一步,是要找到对应的根节点。

 

根节点的选取原则是基于能够基于训练数据得到最好分类效果的树,是基于启发式的贪心算法。

 

如何选择最优的属性最为根?

 

在ID3算法中选择带有最高 信息增益(Information Gain) 的属性。

 

曾经在信息论和通信原理课程中,有个很重要的信息概念, 熵(entropy) ,用来量化信息量。

 

 

信息增益的WikiMapia定义如下:

 

 

计算步骤如下:

 

 

compute the entropy for data-set

 

for every attribute/feature:

a.calculate entropy for all categorical values

b.take average information entropy for the current attribute

c.calculate gain for the current attribute

 

pick the highest gain attribute.

 

 

4. Repeat until we get the tree we desired.

 

 

其中Y的值,yes: 9, no: 5,

 

所以

 

 

对于每个属性,计算熵和信息增益:

 

Sunny属性和outcome的因果性,计算E(outlook = sunny),其他类似

 

 

 

Outlook的熵为

 

 

其他计算类似, 最终得出最高增益的属性

 

 

最后选择根节点Outlook

 

 

递归得到最终的决策树:

 

 

03

 

CART – Classification and Regresstion Trees

 

与ID3不同的是,CART使用Gini Index来进行分类

 

我们使用如下数据源来作为说明

 

 

使用Gini Index,我们需要对每个属性随机设置分类阈值,

 

A        B            C         D  >= 5     >= 3.0      >= 4.2    >= 1.4   < 5      < 3.0       < 4.2     < 1.4

 

对于属性A

 

 

另一分类区间

 

 

最后Gini值为

 

 

其他值计算类似

 

Positive    NegativeFor A|>= 5.0     5           7     |<5         3           1Ginin Index of A = 0.45825 

 

Positive    NegativeFor B|>= 3.0    8       4     |< 3.0     0       4Gini Index of B= 0.3345

 

Positive    NegativeFor C|>= 4.2    0       6     |< 4.2     8       2Gini Index of C= 0.2    

 

Positive    NegativeFor D|>= 1.4    0       5     |< 1.4     8       3Gini Index of D= 0.273

 

最终构建决策树为

 

 

参考:

 

https://en.wikipedia.org/wiki/ID3_algorithm

 

https://en.wikipedia.org/wiki/Entropy_(information_theory)

 

https://towardsdatascience.com/decision-trees-in-machine-learning-641b9c4e8052

 

https://medium.com/deep-math-machine-learning-ai/chapter-4-decision-trees-algorithms-b93975f7a1f1

 

https://www.cnblogs.com/wxquare/p/5379970.html

 

https://en.wikipedia.org/wiki/Decision_tree_learning

 

HE END

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注