问题一: 机器学习的基本流程( 五 ) _机器学习

问题2 举例说明信息增益原理及其改进途径
上面这些定义听起来有点像绕口令，不妨我们用一个例子来简单说明下信息增益原理计算过程.假设共有5个人追求场景中的女孩，年龄有两个属性（老，年轻），长相有三个属性（帅，一般，丑），工资有三个属性（高，中等，低），会写代码有两个属性（会，不会），最终分类结果有两类（见，不见）.我们根据女孩有监督的主观意愿可以得到下表.
年龄长相工资写代码类别
小A
老
帅
高
不会
不见
小B
年轻
一般
中等
会
见
小C
年轻
丑
高
不会
不见
小D
年轻
一般
高
会
见
小L
年轻
一般
低
不会
不见
在这个问题中,
H ( D ) = ? 3 5 log ? 2 3 5 ? 2 5 log ? 2 2 5 = 0.971 H(D)=-\frac{3}{5} \log _{2} \frac{3}{5}-\frac{2}{5} \log _{2} \frac{2}{5}=0.971 H(D)=?53?log2?53??52?log2?52?=0.971
根据式
H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ( ? ∑ k = 1 k ∣ ∣ D i k ∣ ∣ D i ∣ log ? 2 ∣ D i k ∣ ∣ D i ∣ ) , H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}\left(-\sum_{k=1}^{k} \mid \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right), H(D∣A)=i=1∑n?∣D∣∣Di?∣?H(Di?)=i=1∑n?∣D∣∣Di?∣?(?k=1∑k?∣∣Di?∣∣Dik?∣?log2?∣Di?∣∣Dik?∣?),
可计算出4个分支结点的信息熵为
H ( D ∣ 年龄 ) = 1 5 H ( 老 ) + 4 5 H ( 年轻 ) = 1 5 ( ? 0 ) + 4 5 ( ? 2 4 log ? 2 2 4 ? 2 4 log ? 2 2 4 ) = 0 。8 , H ( D ∣ 长相 ) = 1 5 H ( 帅 ) + 3 5 H ( ? 般 ) + 1 5 H ( 丑 ) = 0 + 3 5 ( ? 2 3 log ? 2 2 3 ? 1 3 log ? 2 1 3 ) + 0 = 0 。551 , H ( D ∣ 工资 ) = 3 5 H ( 高 ) + 1 5 H ( 中等 ) + 1 5 H ( 低 ) = 3 5 ( ? 2 3 log ? 2 2 3 ? 1 3 log ? 2 1 3 ) + 0 + 0 = 0 。551 , H ( D ∣ 写代码 ) = 3 5 H ( 不会 ) + 2 5 H ( 会 ) = 3 5 ( 0 ) + 2 5 ( 0 ) = 0 \begin{} H(D \mid \text { 年龄 }) &=\frac{1}{5} H(\text { 老 })+\frac{4}{5} H(\text { 年轻 }) \\ &=\frac{1}{5}(-0)+\frac{4}{5}\left(-\frac{2}{4} \log _{2} \frac{2}{4}-\frac{2}{4} \log _{2} \frac{2}{4}\right)=0 。
8, \\ H(D \mid \text { 长相 }) &=\frac{1}{5} H(\text { 帅 })+\frac{3}{5} H(-\text { 般 })+\frac{1}{5} H(\text { 丑 }) \\ &=0+\frac{3}{5}\left(-\frac{2}{3} \log _{2} \frac{2}{3}-\frac{1}{3} \log _{2} \frac{1}{3}\right)+0=0 。551, \\ H(D \mid \text { 工资 }) &=\frac{3}{5} H(\text { 高 })+\frac{1}{5} H(\text { 中等 })+\frac{1}{5} H(\text { 低 }) \\ &=\frac{3}{5}\left(-\frac{2}{3} \log _{2} \frac{2}{3}-\frac{1}{3} \log _{2} \frac{1}{3}\right)+0+0=0 。551, \\ H(D \mid \text { 写代码 })=\frac{3}{5} H(\text { 不会 })+\frac{2}{5} H(\text { 会 }) \\ =\frac{3}{5}(0)+\frac{2}{5}(0)=0 \end{} H(D∣年龄)H(D∣长相)H(D∣工资)H(D∣写代码)=53?H(不会)+52?H(会)=53?(0)+52?(0)=0?=51?H(老)+54?H(年轻)=51?(?0)+54?(?42?log2?42??42?log2?42?)=0 。8,=51?H(帅)+53?H(?般)+51?H(丑)=0+53?(?32?log2?32??31?log2?31?)+0=0 。551,=53?H(高)+51?H(中等)+51?H(低)=53?(?32?log2?32??31?log2?31?)+0+0=0 。551,?
于是, 根据式
g ( D , A ) = H ( D ) ? H ( D ∣ A ) . g(D, A)=H(D)-H(D \mid A) . g(D,A)=H(D)?H(D∣A).
可计算出各个特征的信息增益为
g ( D ,年龄 ) = 0.171 , g ( D ,长相 ) = 0.42 , g ( D ,工资 ) = 0.42 , g ( D ,写代码 ) = 0.971. \begin{} g(D \text {, 年龄 })=0.171, g(D \text {, 长相 })=0.42, \\ g(D \text {,工资 })=0.42, g(D \text {, 写代码 })=0.971 . \end{} g(D,年龄)=0.171,g(D,长相)=0.42,g(D,工资)=0.42,g(D,写代码)=0.971.?
显然, 特征“写代码”的信息增益最大, 所有的样本根据此特征, 可以直接被分到叶结点（即见或不见）中, 完成决策树生长.当然, 在实际应用中, 决策树往往不能通过一个特征就完成构建, 需要在经验熵非 0 的类别中继续生长.