ID3算法哺乳动物分类实例

• 算法key：属性是否重要通过信息增益大小判断，而信息增益本质是两个熵值之差(不考虑$i$i属性的分类结果的熵值与考虑$i$i属性分类结果的熵值)
  $max(Gain(S,A_i))=Entropy(S)-\sum_{j=1}^v\frac{S_j}{S}Entroy(S_j)$max(Gain(S,Ai​))=Entropy(S)−j=1∑v​SSj​​Entroy(Sj​)

  其中，$v$v表示属性$i$i的类型，$j=1,2,3...v$j=1,2,3...v表示属性$i$i的类型有$v$v种，$Entropy(S)$Entropy(S)表示一个属性也不考虑的分类结果熵值，后面一部分是考虑属性$i$i的熵值，前面系数赋权，$S$S表示样本个数，$S_j$Sj​表示样本中属性$i$i的类型$j$j的数量。

• 是否哺乳动物分类ID3算法实例如下：
  

1. 观察样本数据发现如下：
   第一，有14个样本
   第二，有4个属性$i=1,2,3,4$i=1,2,3,4
   第三，有2种分类结果,是否哺乳
2. 计算公式如下：
   $Entropy(S)=-\sum_{i=1}^mP_i*log2^{P_i}$Entropy(S)=−i=1∑m​Pi​∗log2Pi​

$max(Gain(S,A_i))=Entropy(S)-\sum_{j=1}^v\frac{S_j}{S}Entroy(S_j)$max(Gain(S,Ai​))=Entropy(S)−j=1∑v​SSj​​Entroy(Sj​)

3. ID3具体算法操作如下：

• 首先，计算不考虑4个属性的样本本来的熵值$Entropy(S)$Entropy(S)

• 接着计算考虑属性$i$i的样本熵值，并作差
  $max(Gain(S,A_i))=Entropy(S)-\sum_{j=1}^v\frac{S_j}{S}Entroy(S_j)$max(Gain(S,Ai​))=Entropy(S)−j=1∑v​SSj​​Entroy(Sj​)

  比如，不考虑属性$i=1,2,3,4$i=1,2,3,4(即饮食习性，胎生动物，水生动物，会飞),且针对属性$i$i的类型$j=1,2,3...v$j=1,2,3...v的计算结果如下：
  

• 取增益最大属性胎生动物，即胎生动物为决策树根节点

• 简化压缩表格(不考虑已选出属性)，重复算法做递归，不断选取次优属性，直到完成全部分类，作出决策树。