决策树算法系列之一 ID3 (2)

       (1) 计算数据集D的经验熵
\[H\left( D \right) = - \sum\limits_{i = 1}^N {\frac{{\left| {{C_i}} \right|}}{{\left| D \right|}}} \log \frac{{\left| {{C_i}} \right|}}{{\left| D \right|}}\]

       (2) 计算属性A对数据集D的经验条件熵
\[ H\left( {D\left| A \right.} \right) = \sum\limits_{i = 1}^n {\frac{{\left| {{D_{ai}}} \right|}}{{\left| D \right|}}} H\left( {{D_{ai}}} \right) = \sum\limits_{i = 1}^n {\left( {\frac{{\left| {{D_{ai}}} \right|}}{{\left| D \right|}}\left( { - \sum\limits_{j = 1}^N {\frac{{\left| {{D_{ai,j}}} \right|}}{{\left| {{D_{ai}}} \right|}}\log \frac{{\left| {{D_{ai,j}}} \right|}}{{\left| {{D_{ai}}} \right|}}} } \right)} \right)} \]

       (3) 计算属性A信息增益
\[ G\left( {D\left| A \right.} \right){\rm{ = }}H\left( D \right) - H\left( {D\left| A \right.} \right) \]

       选择使得G(D|A)最大的属性A作为最优属性进行决策划分

6 具体实例

       (1) 计算数据集D的经验熵
       一共14个样本,9个正例、5个负例
\[ H\left( D \right) = - \left( {\frac{{\rm{9}}}{{{\rm{14}}}}\log \frac{{\rm{9}}}{{{\rm{14}}}}{\rm{ + }}\frac{{\rm{5}}}{{{\rm{14}}}}\log \frac{{\rm{5}}}{{{\rm{14}}}}} \right){\rm{ = }}0.2830 \]

       (2) 计算属性对数据集D的经验条件熵 (天气属性)
       天气一共有晴、阴、雨三个属性
       天气 =晴 , 2个正例、3个负例,所以

\[H\left( {D\left| {{A_晴}} \right.} \right) = - \left( {\frac{2}{5}\log \frac{2}{5}{\rm{ + }}\frac{3}{5}\log \frac{3}{5}} \right){\rm{ = }}0.{\rm{2923}}\]

       天气 =阴, 4个正例、0个负例, 所以
\[H\left( {D\left| {{A_阴}} \right.} \right) = - \left( {\frac{4}{4}\log \frac{4}{4}{\rm{ + }}\frac{0}{4}\log \frac{0}{4}} \right){\rm{ = 0}}\]

       天气 =雨, 3个正例、2个负例,所以
\[ H\left( {D\left| {{A_雨}} \right.} \right) = - \left( {\frac{3}{5}\log \frac{3}{5}{\rm{ + }}\frac{2}{5}\log \frac{2}{5}} \right){\rm{ = }}0.{\rm{2923}} \]

       所以天气属性的经验条件熵为
\[ H\left( {D\left| A \right.} \right) = \frac{{\rm{5}}}{{{\rm{14}}}} \cdot 0.{\rm{2923 + }}\frac{{\rm{4}}}{{{\rm{14}}}} \cdot {\rm{0 + }}\frac{{\rm{5}}}{{{\rm{14}}}} \cdot 0.{\rm{2923 = }}0.{\rm{2}}0{\rm{87}} \]

       (3) 天气属性的信息增益
\[ G\left( {D\left| A \right.} \right) = H\left( D \right) - H\left( {D\left| A \right.} \right) = 0.0{\rm{743}} \]

       同理可以算出温度、湿度、是否有风的信息增益

属性 信息增益
天气   0.0743  
温度   0.0088  
湿度   0.0457  
是否有风   0.0145  

       因此天气的信息增益最大,决策树第一个决策节点选择天气进行决策即有:


决策树算法系列之一 ID3



图2 决策树节点划分

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpsfps.html