基于Python的ID3决策树人工智能实验_基本决策树算法的伪代码

人工智能实验ID3决策树
目录
人工智能实验ID3决策树 1
一、 ID3决策树 1

1. 算法原理 1
2. 伪代码 3
3. 代码展示 5
4. 实验结果及分析 13
   二、 C4.5决策树 14
5. 算法原理 14
6. 伪代码 14
7. 代码展示 16
8. 实验结果及分析 17
   三、 CART决策树 17
9. 实验结果及分析 23
   四、 思考题 23
   一、 ID3决策树
10. 算法原理
    1.1 决策树的通用算法
    决策树的生成算法分为以下几个步骤：
    1.初始化：创建根节点，拥有全部的数据集和特征
    2.选择特征：遍历当前节点的数据集和特征，依据某种原则选择一个特征
    3.划分数据：依据所选特征的不同取值，将当前数据集划分为若干个子集
    4.创建节点：为每个子数据集创建一个子节点，并删去刚刚选中的特征
    5.递归建树：对每个子节点，回到第二步进行递归调用，直到达到边界条件，则回溯
    6.完成建树：叶子节点采用多数投票的方式判定自身的类别
    其中，若当前节点的数据集为$D$，特征集为$A$，则边界条件的判断方式如下（满足其一即可）：
    
    若$D$中的样本属于同一类别$C$，则将当前的节点标记为$C$类叶节点
    
    
    $A$为空集，或$D$中所有样本在$A$中所有特征上取值相同，则无法划分。当前节点标记为叶节点，类别为$D$中出现最多的类
    
    
    $D$为空集，则将当前节点标记为叶节点，类别为父节点中出现最多的类
    
    1.2 ID3决策树的信息增益
    ID3决策树指定了上述决策树生成算法第二、三步中，选取特征和取值的原则。
    ID3决策树是采用信息增益来决定通过哪个特征作为决策点的。信息增益越大，说明该特征对得到结果的帮助越大，则优先选用信息增益最大的特征作为决策点。信息增益的算法如下：
    假设训练数据集为$D$，$|D|$表示样本容量，样本有$K$个类，记为$C_k,k=1,2,...,K$，其中$|C_k|$表示该类的样本个数。依据特征A的n个不同取值$a_1,a_2,...,a_n$，将D划分为n个子集$D_1,...,D_n$，记子集$D_i$中属于类$C_k$的样本集合为$D_{ik}$。
    1.计算数据集$D$的经验熵：

1.计算特征$A$对数据集$D$的经验条件熵：

1.计算信息增益：

对所有的特征，都计算出相应的信息增益。比较各个特征的信息增益，最终选择使得信息增益最大的特征作为决策点。每次优先选择信息量最多的属性，即使得熵变得最小的属性，以构造使得熵下降最快的决策树，到叶子节点时熵为0或接近0。

2. 伪代码
   2.1 训练
   考虑到数据样本的标签只有0和1，首先要统计样本中标签为0的个数和标签为1的个数，从而能够计算经验熵。
   计算经验熵（含生成叶节点判断）

Input:ID3tree, node, data
/* 输入：ID3决策树、当前节点、当前数据集 */
Output:HD
/* 输出：经验熵 */
def calcHD(ID3tree, node, data){
	count0 = 0			/* 统计标签为0的样本数 */
	count1 = 0			/* 统计标签为1的样本数 */
	/* 遍历每个样本,统计不同标签对应的样本数 */
	for eachSample in data 		 
		if eachSample的标签为0
			then count0++
		else count1++
	end
	
	/* 若当前数据集的所有样本的标签都相同则直接生成叶子节点 */
	HD = 0
	if count0 == 0
		then ID3tree[node] = 1
	else if count1 = 0
		then ID3tree[node] = 0
	/* 否则计算经验熵 */
	HD = - count0/(count0+count1)*log2(count0/(count0+count1)) - count1/(count0+count1)*log2(count1/(count0+count1))
	return HD
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24