决策树算法系列之一 ID3

  • 时间:
  • 浏览:0
  • 通俗来说,决策树分类的思想类事于找对象
  • 有另一一三个白女孩的母亲要给一种女孩介绍男他们 (分类问提、见或不见)
  • 女孩有此人 的一套标准
某箭队经理 不见
中等 某大科学学生会主席 不见
中等 中等 某NN记者 不见
中等 某上市公司CTO
中等 公务员

       这样 有下面的对话

       女儿:长的帅不帅?

       母亲:挺帅的。

       女儿:收入高不?

       母亲:不算很高,中等情況。

       女儿:是公务员不?

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

       女儿:那好,我去见见。

       每次选择有另一一三个白属性进行判断, 若这样 得出结论,继续选择其

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

       长相 -> 收入 -> 职业

       何如让机器学习到一种有递进关系、且考虑有优先顺序属性特性的分类措施?



图1 一颗简单的决策树
  • 步骤1:将所有的数据看成是有另一一三个白节点,进入步骤2;
  • 步骤2:从中选择有另一一三个白数据特性对节点进行分割,进入步骤3;
  • 步骤3:生成若干孩子节点,对每有另一一三个白孩子节点进行判断若满足停止分裂的条件,进入步骤4;随后,进入步骤2;
  • 步骤4:设置该节点是子节点,其输出为该节点数量占比最大的类别。

       也不有有另一一三个白问提:

       (1) 数据何如分割

       离散型数据的分割

       连续型数据的分割

       (2)何如选择分裂的属性

       分裂算法(ID3 C4.5 CART)

       (3)什么随后停止分裂

       最小节点数、树宽度、所有特性可能使用完毕

凉爽
凉爽
凉爽
凉爽

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

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

       假设其带有另一一三个白属性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的经验熵

       一共1有另一一三个白样本,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的经验条件熵 (天气属性)

       天气一共有晴、阴、雨有另一一三个白属性

       天气 =晴 , 有另一一三个白正例、一三个白负例,也不

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

       天气 =阴, 有另一一三个白正例、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}}\]

       天气 =雨, 一三个白正例、有另一一三个白负例,也不

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

       随后天气的信息增益最大,决策树第有另一一三个白决策节点选择天气进行决策即有:



图2 决策树节点划分