基于Python实现ID3决策树(人工智能实验)【100011918】

# 一、ID3决策树 ## 1. 算法原理 ### 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$的经验熵： $$ \displaystyle H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|} $$ 2. 计算特征$A$对数据集$D$的经验条件熵： $$ \displaystyle H(D|A)=\sum^n_{i=1}\frac{|D_i|}{|D|}H(D_i)=-\sum^n_{i=1}\frac{|D_i|}{|D|}\sum^K_{k=1}\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|} $$ 3. 计算信息增益： $$ g(D,A)=H(D)-H(D|A) $$ 对所有的特征，都计算出相应的信息增益。比较各个特征的信息增益，最终选择使得信息增益最大的特征作为决策点。每次优先选择信息量最多的属性，即使得熵变得最小的属性，以构造使得熵下降最快的决策树，到叶子节点时熵为0或接近0。 ----- ## 2. 伪代码 ### 2.1 训练 考虑到数据样本的标签只有0和1，首先要统计样本中标签为0的个数和标签为1的个数，从而能够计算经验熵。 #### 计算经验熵（含生成叶节点判断） ```pseudocode 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 } ``` #### 计算经验条件熵 接下来要计算经验条件熵，需要对所有的特征进行遍历，计算每个特征的经验条件熵。计算过程如下： ```pseudocode Input: data, A /* 输入：数据集，特征 */ Output: HDA /* 输出：数据集在特征A下的条件熵 */ def calcHDA(data, A){ HDA = 0 /* 对A中的每一个类分别求条件熵分量 */ for eachClass in A count0 = 0 count1 = 0 /* 计算特征A在特征值为eachClass下数据集的经验熵 */ for eachSample in data: if eachSample的特征A等于eachClass /* 统计标签种类和个数 */ then if eachSample的标签为0: then count0++ else: count1++ /* 计算条件熵分量 */ HDA[i] += (count0+count1)/len(data)*(-count0/(count0+count1)*log2(count0/(count0+count1))-count1/(count0+count1)*log2(count1/(count0+count1))) end end return HDA } ``` #### 计算信息增益并选定作为决策点的特征 每个特征下数据集的信息增益`gDA`即为上面求得的经验熵和经验条件熵的差值`HD - HDA`。找到使得`gDA`最大的特征即可。 #### 划分新的数据集，并递归调用 对于选定的特征`A`，以`A`的不同取值为依据划分数据集。 ```pseudocode newData = [] for eachClass in A for eachSample in data if eachSample的特征A的取值为eachClass then 将eachSample加入newData end /* 递归调用生成节点的函数 */ summonNode(ID3tree, newNode, newData) end ``` ## 3. 代码展示 ### 3.1 数据的预处理 本次实验的每个样本有6个特征和1个标签，首先将训练样本存储在列表`data`中，`data`里的每一个节点包含7个数，索引从0到6，分别记录这六个特征和一个标签。 ```python def trainSetRepro(): data = [] with open("car_train.csv") as trainSet: for eachLine in trainSet: s = eachLine.split(',') if s[0] == 'buying': # 去掉第一行的样本说明 continue s[-1] = s[-1][0:-1] # 去掉最后一个单词的结尾处的回车 data.append([s[i] for i in range(7)]) # 将6个特征值和1个标签值组成的列表分别加入data return data ``` ### 3.2 多叉树的表示和特征使用判断 多叉树可以用树的兄弟-儿子表示法用二叉树表示：对于任意一个节点，有两个指针：左指针为下一个兄弟节点，右节点为第一个儿子节点。在我的代码中，我使用数组来表示该二叉树。对于`ID3tree`的节点`node`，左指针的节点索引为`2*node+1`，右指针的节点索引为`2*node+2`。若不存在该节点，则节点值为`None`。 ID3树每一次分叉需要选择一个特征作为判断条件，而某个特征在作为决策点后不会再次作为决策点。我使用了一个数组`attr`来表示。`attr`有6个1，分别表示6个特征是否能够用来选作决策点。若可以则为1。当某个特征被选作决策点后，将对应的值改为0。 二者初始化如下： ```python attr = [1, 1, 1, 1, 1, 1] ID3tree = [None for i in range(10000000)] ``` ### 3.3 训练过程 训练时调用`trainID3(attr, ID3tree, node, data)`函数。其中`node`参数在第一次调用时为0，表示`ID3tree`的根节点。 首先计算数据集的经验熵`HD`。如果数据集的标签只有一种时，直接生成叶子节点。叶子节点的值即为预测的标签值。 ```python # 计算经验熵 # 标签只有0和1，分别统计0和1的个数后计算经验熵 count0 = 0 count1 =0 for eachSample in data: if eachSample[6] == '0': count0 += 1 else: count1 += 1 # 当前数据只包含一种标签，则生成叶子节点 if count0 == 0: ID3tree[node] = 1 return elif count1 == 0: ID3tree[node] = 0 return # 否则进行正常的经验熵运算 else: HD = - count0/(count0+count1)*math.log2(count0/(count0+count1)) - count1/(count0+count1)*math.log2(count1/(count0+count1)) ``` 接着计算经验条件熵。需要注意的是，不是所有的