##概述
下图是一个假想的邮件分类决策树.
优点: 低计算复杂度, 结果容易理解, 缺失值不敏感, 能够处理不相关特征数据;
缺点: 易过度适应(Prone to overfitting);
适用: 数值, 标称值.
适用于:
- 数据实例由”属性-值”对构成;
- 目标函数具有离散的输出值;
- 可能需要析取的描述(disjunctive description), 因为决策树自然地代表了析取表达式;
- 训练数据可能包含错误, 决策树对错误具有良好的健壮性;
- 训练数据可以包含缺少属性值的实例, 例如某些样本缺少重量的属性数据.
##构造决策树
首先, 找到用于划分数据类别的特征项; 然后, 以此特征项分割不同类数据; 最后, 判断分割后的数据是否还能够分割, 如果可以, 再次重复这个过程.
伪码:
###流程
套用机器学习的几个步骤: 收集数据, 准备输入数据, 分析输入数据, 训练算法, 测试算法, 使用算法.
1. 收集: 任意方法;
2. 准备: 连续型数据需要首先离散化;
3. 分析: 任意方法, 构造完成后visually inspect the tree;
4. 训法: 构造一个决策树的数据结构;
5. 测试: 计算错误率;
6. 使用: ...
###信息增益
划分数据集要以将数据变得更有序/有组织(more organized)为标准. 使用信息论,检测数据分割前后的信息变化, 分割前后信息发生的变化即信息增益, 以信息增益最高为标准, 可以确定采用哪个特征来分隔数据最好.
###熵(entropy)
熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，熵是对不确定性的测量。
如果某个事物可能的分类有多个, 那么事物属于某个类别$x_i$的信息定义为
$$l(x_i)=-\log_2p(x_i)$$
$p(x_i)$是事物属于这个类别的概率.
熵定义为信息的期望值, 即所有位置的所有信息的期望值.
$$H=-\sum_{i=1}^np(x_i)\log_2p(x_i)$$
###算法
过度拟合
定义: 给定一个假设空间$H$, 一个假设$h\in H$, 如果存在其他的假设$h^{\prime}\in H$, 使得在训练样例上$h$的错误率比$h^{\prime}$小, 但在整体实例分布上$h^{\prime}$的错误率比$h$小, 那么就说假设$h$过度拟合(overfit)训练数据.
解决过度拟合的思路分两类:
- 在完美分类训练数据之前就停止树的增长;
- 后修剪法(post-proune), 即允许树过度拟合, 然后再对这个树进行修剪.
最普遍的一种方法: 训练和验证集(training and validation set)法. 可用的数据被分为训练集合和验证集合两个样例集合, 前者用来形成学习到的假设, 后者用来对假设并进行评估和修剪.