机器学习之决策树——ID3算法简介

决策树简介

    在相亲过程中，女方会根据男方的一些特征（年龄、长相、收入、是否公务员）来决策自己的行为（见还是不见）。如果利用kNN算法来预测女方是否去见相亲对象的话，需要保存样本数据，且需要将年龄等这些特征先转换为对应的数值，同时需要对所有数据计算距离值，非常耗时。因此，我们可以利用概率测量方法（决策树）来处理分类问题。

决策树定义

    决策树的基本组成部分：决策节点、分支和叶子。

    在上图中，第一次的决策节点是年龄；分支是长相、收入、公务员；叶子是见、不见。上图就是利用决策树进行分类的过程，是我们需要的结果。

ID3算法简介

    对于女方来说，一个男人的特征权重是不一样的，到底哪个最重要，哪个次之，是需要进行分类的。如何分类，我们就需要利用一些决策树算法。下面将介绍一种算法：ID3算法。

    ID3算法使用信息增益度来进行分类，关于相关概念，我们用一个简单的示例来介绍。

基于ID3算法的分类流程

1、样本数据如下：

2、计算根结点的熵值：

从类别来看，好=6次，差=6次，因此，根结点的熵值为：

E=-(6/12)log2(6/12)-(6/12)log2(6/12)=1

信息熵的普及：

信息熵表示的是不确定的量度。信息存在不确定性，一般来说，小概率事件比大概率事件包含的信息量大，而熵就是度量信息量大小的方法。假设X是一个离散随机变量，X的熵定义为：

对于结果只有2种情况（如好和差），即P{X=0}=p，P{X=1}=1-p，则H(X)=plogp-(1-p)log(1-p)，熵函数曲线如下：

3、计算样本中各个属性（性格、父母的教育程度、性别）的熵值及信息增益度：

对于属性“性格”来说，分为“内向”和“外向”。我们先来计算“内向”的信息熵：

E(性格，内向)=-(4/6)log2(4/6)-(2/6)log2(2/6)=0.9183

以此内推：

E(性格，外向)=-(4/6)log2(4/6)-(2/6)log2(2/6)=0.9183

所以，属性为性格的信息增益度为：

Gain(性格)=E-E(性格)=1-[(1/2)*0.9183+(1/2)*0.9183]=0.0817

同理可得：

Gain(父母教育程度)=0.4591

Gain(性别)=0

4、按照信息增益度的大小进行第一次分类：

因为Gain(父母的教育程度)>Gain(性格)>Gain(性别)，所以第一次划分属性时，以“父母的教育程度”进行划分，其第一次的决策树如下图：

5、计算样本中各个属性（性格、性别）的熵值和增益度：

经过一次划分后，属性“父母教育程度”为良的结果都为“好”；因此，第二次划分的样本如下：

Gain(性格)=0.3113

Gain(性别)=0.2045

6、按照信息增益度的大小进行第二次分类：

Gain(性格)>Gain(性别)，因此用“性格”来划分，得到的决策树如下：

7、得到最终的决策树：
    目前只有“父母教育程度”为“中”和“差”的“外向”小学生还没有明确类别，需要用属性“性别”来进一步划分，得到最终的决策树如下：