唤醒手腕 - 人工智能 - 决策树（Decision Tree）更新中

决策树基本概念

决策树（decision tree）：是一种基本的分类与回归方法，此处主要讨论分类的决策树。

在分类问题中，表示基于特征对实例进行分类的过程，可以认为是 if-then 的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树通常有三个步骤：特征选择、决策树的生成、决策树的修剪。

用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。

• 决策树学习目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

• 决策树学习本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。

• 决策树学习损失函数：正则化的极大似然函数。

• 决策树学习测试：最小化损失函数。

• 决策树学习结果：在损失函数的意义下，选择最优决策树的问题。

决策树流程图，正方形代表判断模块，椭圆代表终止模块，表示已经得出结论，可以终止运行，左右箭头叫做分支。

衡量标准 - 熵

目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。

衡量标准-熵：熵是表示随机变量不确定性的度量（解释：说人话就是物体内部的混乱程度，比如义务杂货市场里面什么都有那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦）

举个例子：如下，A中决策分类完成后一侧是有三个三角二个圆，另一侧是两个三角一个圆，而B中决策分类后是一侧是三角一侧是圆，显然是B方案的决策判断更靠谱一些，用熵进行解释就是熵值越小（混乱程度越低），决策的效果越好。

决策树信息增益

划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。

特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。

图(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。

图(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。

两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？

这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

什么是信息增益呢？在划分数据集之前之后信息发生的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

from math import log

def creatDataSet():
    # 数据集
    dataSet = [[0, 0, 0, 0, 'no'],
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'],
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    # 分类属性
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
    # 返回数据集和分类属性
    return dataSet, labels


def calcShannonEnt(dataSet):
    # 返回数据集行数
    numEntries = len(dataSet)
    # 保存每个标签（label）出现次数的字典
    labelCounts = {}
    # 对每组特征向量进行统计
    for featVec in dataSet:
        currentLabel = featVec[-1]  # 提取标签信息
        if currentLabel not in labelCounts.keys():  # 如果标签没有放入统计次数的字典，添加进去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1  # label计数

    shannonEnt = 0.0  # 经验熵
    # 计算经验熵
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries  # 选择该标签的概率
        shannonEnt -= prob * log(prob, 2)  # 利用公式计算
    return shannonEnt  # 返回经验熵


# main函数
if __name__ == '__main__':
    dataSet, features = creatDataSet()
    print(dataSet)
    print(calcShannonEnt(dataSet))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50