首页 > 代码库 > Decision Tree 1: Basis 决策树基础

Decision Tree 1: Basis 决策树基础

 介绍

我们有一些历史数据:

record id\attributes

A B C Result
1 a1 b1 c1 Good
2 a2 b2 c1 Bad
3 a1 b3 c2 Good

 

根据这些数据,我们想回答:

If we got a record 4, that is ‘a1,b1,c2‘,  is record4 Good or Bad?

 

解决方法

我们要分别考量record4的三个属性的先验(Priori)结果。那首先考虑属性C吧。

          C

  /               \

  c1(Subset1: Good-1, Bad-1)      c2(Subset2: Good-1, Bad-0) 

 

由Record4 C==c1,那么record4 属于subset1情况,但是subset1依然是50%对50%, 那么再考量A.

          A

/                  \

a1(Subset3: Good-2, Bad-0)     a2(Subset4: Good-0, Bad-1)

由Record4 A==a1,那么record4 属于subset3情况, 那么record4很可能是Good.

 

完整的decision tree是:

              C

      /               \

      c1(Subset1: Good-1, Bad-1)      c2(Subset2: Good-1, Bad-0) 

          A

/                  \

a1(Subset3: Good-2, Bad-0)     a2(Subset4: Good-0, Bad-1)

 

思考

1. Pure subset: Subset2,3,4,他们只包含单一的结果。当所有叶子为pure subset, 分类结束。

2. Attributes order: 我们也可以先考量A、B, 那么是先考量C好还是先考量A、B好呢。简单来说,我们喜欢pure subset,因为pure subset的不确定性小,如果不能得到pure subset,也要接近它。Entropy(-pLOGp)是一个衡量不确定性的量,Entropy越大,一个系统的不确定性越高。那么通过计算一个attribute split代来的Entropy减少,我们衡量这个split的优劣,即Information Gain。一个好的split应该尽量减小entropy.

    Information Gain =  H_old - Sum(pi*Hi)

 

总结

通过Information Gain 来排列attributes。

通过每个attribute的先验概率来预测。

Decision Tree 1: Basis 决策树基础