决策树

决策树

决策树是分类算法，一个未贴标签(未知类别)的新数据(含多个特征)，通过问多个问题（问题是：特征，答案：是或者否），最终问题问完，判断出新数据类别。问问题的流程基于决策树。

所以训练决策树的步骤一般是，先有已知类别的数据集、选择特征问问题生成决策树、测试决策树。决策树模型生成之后就可以用于分类没贴标签的数据集。

要理解决策树算法，首先要知道熵的概念，是信息论里面的知识，用来形容信息的混乱程度。信息越有序则熵值越低，越混乱熵值越大。熵的计算公式，其中p(x) 代表类别x在信息整体中出现的概率

比如计算下面数据的熵值

# yes 代表是鱼类，no 代表不是鱼
1, 1, 'yes'
1, 1, 'yes'
1, 0, 'no'
0, 1, 'no'
0, 1, 'no'

上面信息整体中有鱼类x1，非鱼类x2，出现的概率分别为2/5，3/5，所以上面的信息熵为

- 2/5log(2/5) - 3/5(log3/5) 

应用

用决策树算法来判断生物是否鱼

1. 收集数据

特征1（不浮出水面是否能活）    特征2（是否有脚蹼）       类别(是否鱼)
yes                       yes                  yes
yes                       yes                  yes
yes                       no                   no
no                        yes                  no
no                        yes                  no

# 变成向量的形式：   
dataSet = [
    [1, 1, 'yes'],
    [1, 1, 'yes'],
    [1, 0, 'no'],
    [0, 1, 'no'],
    [0, 1, 'no']
]
# labels 存储的是特征，即决策树的问题
labels = ['no surfacing', 'flippers']

2. 分析数据：这里的数据集不是连续的，都是0,1 离散数据，这步可以省略
3. 构造算法，选择labels 中哪个特征来问题呢，全部特征集合labels存储，逐一尝试，计算分类前后香农熵，选取信息增益(熵差)最大的特征x，划分后的子集去除特征x, 集合labels去除特征x。就这样一直递归下去，直到每个子集的只有一种类别，即信息熵为0

假设我们在特征1和特征2选特征1来分类，即问一个问题(此新数据不浮出能活吗)，安照答案(即特征值yes no )得到分类，并计算该数据集的香农商。分类后

tree1.png

由特征1分类，子集去掉特征1，计算数据集香农熵

#分类前香农熵： 
- 2/5log(2/5) - 3/5(log3/5)    

#分类后香农熵,
- 3/5*(2/3log(2/3)+1/3log(2/3))  - 2/5*(1log1)

分类后香农熵，3/5 表示该子集占全集，2/3表示 yes在子集占比。若子集类别一致，香农熵为 0

4. 最后形成的决策树{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

tree2.png

参考文献

决策树

欢迎大家给我留言，提建议，指出错误，一起讨论学习技术的感受！