概述

决策树算法是一种基本的分类与回归算法，我们这里只讨论分类的决策树。
决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类。
决策树通常包括3个步骤：特征选择，决策树的生成和决策树的修剪。

一个邮件分类系统，大致工作流程：
image.png

定义

分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点(node)和有向边(directed edge)组成。节点有两种类型：内部节点(internal node) 和 叶节点(leaf 节点)。内部节点表示一个特征和属性，叶节点表示一个类(labels)。

决策树原理

信息熵 && 信息增益

熵(entropy)： 熵指得是体系的混乱程度，在不同的学科中也引申出更为具体的定义。
熵的公式如下：
image.png
信息论(information theory) 中的熵(香农熵)：是一种信息的度量单位，表示信息的混乱度。信息越有序，信息熵越低。
信息增益(information gain)：在划分数据集前后信息发生的变化称为信息增益。

相关阅读：通俗理解条件熵

决策树 工作原理

如何构造一个决策树？
我们使用createBranch()方法

  1. def createBranch():
  2. '''
  3. 此处运用了迭代的思想。 感兴趣可以搜索 迭代 recursion， 甚至是 dynamic programing。
  4. '''
  5.     检测数据集中的所有数据的分类标签是否相同:
  6.         If so return 类标签
  7.         Else:
  8.             寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
  9.             划分数据集
  10.             创建分支节点
  11.                 for 每个划分的子集
  12.                     调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
  13.             return 分支节点

决策树 开发流程

  1. 收集数据：任何方法
  2. 准备数据：树构造算法（这里使用ID3算法，只适用于标称型数据，这就是为什么数组型数据必须离散化。还有其他的树构造算法，比如CART）
  3. 分析数据：可以使用任何方法，构造树完成后我们应该检查图形是否符合预期。
  4. 训练算法：构造树的数据结构
  5. 测试算法：使用训练好的树计算错误率
  6. 使用算法：此步骤可以适用于任何监督学习任务，使用决策树可以更好的理解数据的内在含义。

    决策树 算法特点

    优点：计算复杂度不高，输出结果易于理解，数据缺失也能跑，可以处理不相关特征
    缺点：容易过拟合
    适用数据类型：数值型和标称型