机器学习 | 决策树ID3算法

ID3是Quinlan于1979年提出的，是机器学习中一种广为人知的一个算法，它的提出开创了决策树算法的先河，而且是国际上最早最有影响的决策树方法

首先找出最有判断力的特征，把数据分成多个子集，每个子集又选择最有判断力的特征进行划分，一直进行到所有的子集包含同一类型的数据为止，最后得到一棵决策树。

一、ID3算法的基本步骤

1）创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。

2）否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。

3）对测试属性中的每一个值，创建相应的一个分支，并据此划分样本。

4）使用同样自顶向下的递归，直到满足下面的三个条件中的一个时，就停止递归

①给定节点的所有样本都属于同一类。

②没有剩余的属性可以用来进一步划分。

③继续划分得到的改进不明显。

二、分支属性的选择方法

在选择根节点和各个内部节点上的分支属性时，采用信息增益作为度量标准，选择具有最高信息增益的描述属性作为分支属性。

目的：使对所划分获得的训练样本子集进行分类所需要信息最小，即利用该属性进行当前（结点所含）样本集合划分，将会使得所有参数的各样本子集中“不同类别混乱程度”降为最低。

采用信息论方法将帮助有效减少对象分类所需要的次数，从而确保所产生的决策树最为简单，尽管不一定是最简单的。

三、信息增益的计算方法

1、熵

热力学中表征物质状态的参量之一，其物理意义是体系混乱程度的度量

信息论之父C.E.Shannon(香农ÿ