决策树算法系列之一 ID3

  • 时间:
  • 浏览:0
  • 来源:大发快三_快三最新版_大发快三最新版
  • 通俗来说,决策树分类的思想你是什么于找对象
  • 1个多多女孩的母亲要给你是什么女孩介绍男亲们 (分类难题、见或不见)
  • 女孩有另一方的一套标准
某箭队经理 不见
中等 某大学得生会主席 不见
中等 中等 某NN记者 不见
中等 某上市公司CTO
中等 公务员

       没法有下面的对话

       女儿:长的帅不帅?

       母亲:挺帅的。

       女儿:收入高不?

       母亲:不算很高,中等清况 。

       女儿:是公务员不?

       母亲:是,在税务局上班呢。

       女儿:那好,我去见见。

       每次取舍1个多多属性进行判断, 若并能并能得出结论,继续取舍其

他属性进行判断,直到并能“肯定地”判断

       长相 -> 收入 -> 职业

       如可让机器学习到你是什么有递进关系、且考虑有优先顺序属性内部人员的分类法律法律依据?



图1 一颗简单的决策树
  • 步骤1:将所有的数据看成是1个多多节点,进入步骤2;
  • 步骤2:从中取舍1个多多数据内部人员对节点进行分割,进入步骤3;
  • 步骤3:生成若干孩子节点,对每1个多多孩子节点进行判断若满足停止分裂的条件,进入步骤4;但会 ,进入步骤2;
  • 步骤4:设置该节点是子节点,其输出为该节点数量占比最大的类别。

       某些1个多多多难题:

       (1) 数据如可分割

       离散型数据的分割

       连续型数据的分割

       (2)如可取舍分裂的属性

       分裂算法(ID3 C4.5 CART)

       (3)有哪些就让停止分裂

       最小节点数、树深层、所有内部人员可能性使用完毕

凉爽
凉爽
凉爽
凉爽

       训练集为D, 总样本数|D|

       训练集中有 N个类别,|Ci|为第i个类别的数量

       假设其中1个多多属性A有n个不同离散取值(a1,a2…an)

       假设取值a1样本集为Da1,个数为|Da1|,其中属于第j个类的个数为|Da1,j |

       假设取值a2样本集为Da2,个数为|Da2|,其中属于第j个类的个数为|Da2,j|

       …

       假设取值an样本集为Dan,个数为|Dan|,其中属于第j个类的个数为|Dan,j|

       (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作为最优属性进行决策划分

       (1) 计算数据集D的经验熵

       一共11个多多样本,9个正例、六个负例

\[ 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.28150 \]

       (2) 计算属性对数据集D的经验条件熵 (天气属性)

       天气一共有晴、阴、雨1个多多属性

       天气 =晴 , 1个多多正例、六个负例,某些

\[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}}\]

       天气 =阴, 1个多多正例、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}}\]

       天气 =雨, 六个正例、1个多多负例,某些

\[ 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

       但会 天气的信息增益最大,决策树第1个多多决策节点取舍天气进行决策即有:



图2 决策树节点划分