机器学习实战读书笔记 - 03 - 决策树

解决的问题

一个经典的例子是猜人游戏。参与游戏的一方默想一个人名，另一方向他提问题，最终猜出这个人名。
决策树属于监督学习，可以处理上面的分类问题。这个问题的特点是：

训练数据全面，计算数据被训练数据覆盖了。
训练数据是标称型数据，数值型数据必须离散化。

决策树算法是找到一个优化的决策路径（决策树），使得每次分类尽可能过滤更多的数据，或者说问的问题尽量少。
决策树算法可以用来优化一些知识系统，帮助用户快速找到答案。

优势

使用决策树可以更好地理解数据的内在含义。

基本概念

属性(Feature): 训练数据中每列都是一个属性。
标签(Label)：训练数据中的分类结果。

决策树的一般流程

收集数据：可以使用任何方法。
准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
训练算法：构造树的数据结构。
测试算法：使用经验树计算错误率。
使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

如何构造决策树

这里，要解决的问题是采用哪些数据属性作为分类条件，最佳次序是什么？

方法一：采用二分法，或者按照训练数据中的属性依次构造。
方法二：使用香农熵计算公式。这是书中使用的方法。
方法三：使用基尼不纯度2 （Gini impurity）。
流行的算法: C4.5和CART

香农熵（Shannon Entropy）简介

熵的定义
在信息论中，熵是接收的每条消息中包含的信息的平均量，又被称为信息熵、信源熵、平均自信息量。
熵定义为信息的期望值。
熵实际是对随机变量的比特量和顺次发生概率相乘再总和的数学期望。
熵的单位通常为比特, bit 或者sh(annon) (基于2)，但也用nat(基于自然对数)、Hart（基于10）计量，取决于定义用到对数的底。
熵值是一个>=0的值。
如果为0，则表明结果可以准确预测。从下面的公式可以看出，其概率为1.
因此，熵值越大，越不容易被准确预测。
期望值
在概率论和统计学中，一个离散性随机变量的期望值（或数学期望、或均值，亦简称期望，物理学中称为期待值）是试验中每次可能结果的概率乘以其结果的总和。
比如掷骰子, 其点数的期望值是3.5： E(x) = 1 * 1 / 6 + 1 * 2 / 6 + 1 * 3 / 6 + 1 * 4 / 6 + 1 * 5 / 6 + 1 * 6 / 6 = 3.5

核心公式

数据集的信息熵的计算公式

[H(X) = sumlimits_{i=1}^n P(x_i)I(x_i) = - sumlimits_{i=1}^n P(x_i)log_2 P(x_i) \ where \ qquad H(X) : 数据集合X的信息熵值。 \ qquad X : 数据集合X。 \ qquad x_i : 数据集合X的标签的一个枚举值。 \ qquad I(x_i) ：x_i的资讯量 (information self). I(x_i) = -ln(P(x_i)) \ qquad P(x_i) : 发生x_i的概率。x的机率质量函数（probability mass function）。 P(x_i) = count(x_i)/len(X). ]

数据集合X在属性F上的信息熵的计算公式

[H(F, X) = sumlimits_{i=1}^n P(f_i)H(X_fi) \ where \ qquad H(F, X) : 数据集合X在属性F上的信息熵值。 \ qquad F : Feature F。 \ qquad X : 数据集合X。 \ qquad f_i : Feature F的一个枚举值。 \ qquad H(X_fi) ：集合X_fi的信息熵。 \ qquad X_fi ：数据集合X中属性F为f_i的子集。 \ qquad P(f_i) : 发生f_i的概率。f_i的机率质量函数（probability mass function）。 P(f_i) = count(f_i)/len(X). ]

构造决策树

输入
- 数据集
输出
- 决策树
  建造一个决策树。决策树的json表示如下：

{
    'no surfacing': 
    {
        0: 'no', 
        1: 
        {
            'flippers': 
            {
                0: 'no',
                1: 'yes'
            }
        }
    }
}

'no surfacing'和'flippers'是数据的属性名。
0, 1是标称数据。
'yes', 'no'是决策结果。

逻辑过程
- createTree

[ ext{(jsonTree) createTree(dateset)} = \ { \ qquad ext{if (the value of the dateset labels are same)} \ qquad { \ qquad qquad return dataset.lables[0] \ qquad } \ qquad \ qquad ext{if (dataset.features.length = 1)} \ qquad { \ qquad qquad return mostAppeard(dataset.lables) \ qquad } \ qquad \ qquad feature = findBestFeature(dateset) \ qquad jsonTree = {feature.label:{}} \ qquad extstyle {foreach}_ ext{value}^ ext{feature.values} \ qquad { \ qquad qquad jsonTree[feature.label][value] = createTree(dateset.subset(feature, value)) \ qquad } \ } ]

* findBestFeature

[ ext{(feature) findBestFeature(dateset)} = \ { \ qquad baseFeatureEntroy = infinite \ qquad ext{foreach}_ ext{current_feature}^ ext{dataset.features} \ qquad { \ qquad qquad featureEntroy = calculateFeatureEntroy(dateset, feature) \ qquad qquad ext{if (featureEntroy < baseFeatureEntroy)} \ qquad qquad { \ qquad qquad qquad baseFeatureEntroy = featureEntroy \ qquad qquad qquad feature = current_feature \ qquad qquad } \ qquad } \ } ]

使用Matplotlib注解绘制树形图

见原书。

测试和存储分类器

见原书。

个人总结

决策树对数据质量要求比较高。那猜人名的游戏来说，需要收集大量的人名和人名对应的数据。

参考：

Machine Learning in Action by Peter Harrington
熵 (信息论)
期望值