第八章数据决策分析算法——基于ID3算法的决策分析

2019-11-02 本文已影响0人文颜

在机器学习中决策树是一个预测模型，代表对象属性与对象值之间的一种映射关系。决策树经常用于数据挖掘中的数据分析和预测。

8.1 基于ID3算法的决策分析

ID3是由J.Ross Quinlan在1986年开发的一种基于决策树的分类算法。该算法以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。

ID3建立决策树的主要方法：根据信息增益运用自顶向下的贪心策略。

运用ID3算法的主要优点：建立的决策树模型比较小，查询速度快。

ID3算法建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（简单理论）。但是，该算法在某些情况下生成的并不是最小的树形结构，ID3算法借助信息熵和信息增益提供决策支持

信息量是通信领域中信息含量的概念，表示的是信息的多少的度量方式，信息量可以通过公式 $I=-log_{2}m$ 表示。其中，m表示信息值。信息量是包含的真实信息含量。

信息熵是接收信息量的平均值，用于度量信息的不确定程度，是随机变量的均值。信息的熵越大，信息就越凌乱或传输的信息越多，熵本身的概念源于物理学中描述一个热力学系统的无序程度。信息熵的处理信息是一个让信息的熵减少的过程。

假设X是一个离散的随机变量，且它的取值有限范围 $R=$ { $x_{1},x_{2},…，x_{n}$ }，设 $p_{i}=P$ { $X=x_{i}$ }，则X的熵计算公式如下，其中 $p_{i}$ （ $1\leq i\leq n$ ）为概率密度函数，对数以2为底。

Entropy(x)= $-\sum\nolimits_{i\geq 1}p_{t} log_{2}\frac{1}{p_{t}}$

信息增益用于度量属性A对降低样本集合X熵的贡献大小。信息增益越大，越适合对X进行分析。

信息增益的计算公式如下：

Gain(A,X)=Entropy(X)-Sum( $\frac{\vert Xv \vert }{\vert X \vert }$ XEntropy(Xv))

其中，Xv表示A中所有为v的值；|Xv|表示A中所有为v的值的数量。

输入：样本集合D，属性集合A

输出：ID3决策树

1、对当前样本集合计算出所有属性的信息增益。

2、选择信息增益最大的属性作为测试属性，将测试属性相同的样本转化为同一个子样本。

3、若子样本本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本递归调用本算法。