人工智能实验ID3决策树

目录

人工智能实验ID3决策树

一、 ID3决策树

1. 算法原理

2. 伪代码

3. 代码展示

4. 实验结果及分析

二、 C4.5决策树

1. 算法原理

2. 伪代码

3. 代码展示

4. 实验结果及分析

三、 CART决策树

4. 实验结果及分析

四、 思考题

一、 ID3决策树

1. 算法原理

1.1 决策树的通用算法

决策树的生成算法分为以下几个步骤：

1. 初始化：创建根节点，拥有全部的数据集和特征

2. 选择特征：遍历当前节点的数据集和特征，依据某种原则选择一个特征

3. 划分数据：依据所选特征的不同取值，将当前数据集划分为若干个子集

4. 创建节点：为每个子数据集创建一个子节点，并删去刚刚选中的特征

5. 递归建树：对每个子节点，回到第二步进行递归调用，直到达到边界条件，则回溯

6. 完成建树：叶子节点采用多数投票的方式判定自身的类别

其中，若当前节点的数据集为$D$，特征集为$A$，则边界条件的判断方式如下（满足其一即可）：

·

若$D$中的样本属于同一类别$C$，则将当前的节点标记为$C$类叶节点

·

·

$A$为空集，或$D$中所有样本在$A$中所有特征上取值相同，则无法划分。当前节点标记为叶节点，类别为$D$中出现最多的类

·

·

$D$为空集，则将当前节点标记为叶节点，类别为父节点中出现最多的类