找到决策树的最佳属性

Question

为什么我们要选择"最佳"属性？如果我们从任何其他属性中选择,会有什么不同吗？

Answer 1

首先,让我们根据决策树清楚"最佳"属性的含义 - 这是"最佳"分类可用培训示例的属性.为了定义"最佳" - 熵和信息增益,需要熟悉两个术语.熵是来自信息理论的术语 - 它是一个数字,表示一组示例基于其目标类的异构.Anther对熵的看法 - 它是从一组示例中编码随机示例的类所需的位数.另一方面,信息增益表示如果选择特定属性,一组示例的熵将减少多少.替代视角 - 它表示如果选择特定属性,则表示随机示例的类所需的位数减少.

那么,为什么我们根据训练样例选择"最佳"属性？简单的答案是因为这就是构建决策树的算法的工作原理 - 它搜索所有可能的决策树,并选择第一个使用简单到复杂的搜索正确分类训练样例的树.由于基本实现不包括任何重新访问和更改早期决策的机制,因此使用贪婪方法而不是随机方法是有意义的.

这是一个简单的例子,用于说明在构造决策树时不选择"最佳"属性的后果.让我们假设我们有以下培训示例,其中包含属性Exam,Friends,Weather和target Activity.这些示例根据是否有考试,朋友是否可用以及天气是晴天还是下雨来描述首选活动.

???????????????????????????????????????
? Exam ? Friends ? Weather ? Activity ?
???????????????????????????????????????
? yes  ? yes     ? sunny   ? study    ?
? no   ? yes     ? sunny   ? picnic   ?
? yes  ? no      ? rain    ? study    ?
? yes  ? yes     ? rain    ? study    ?
? no   ? yes     ? rain    ? play     ?
? no   ? no      ? rain    ? play     ?
???????????????????????????????????????

当我们进行数学运算时,我们最终得到以下数字以获取信息:

IG(D, Exam) ~ 1
IG(D, Friends) ~ 0.13
IG(D, Weather) ~ 0.46

为决策树的根选择的"最佳"属性是Exam.下一步是决定在考试很快和没有考试时选择哪个属性.如果很快就有考试,活动总是在学习,所以不需要进一步探索.如果没有考试,我们需要计算选择朋友和天气的信息收益:

IG(D-No-Exam, Friends) ~ 0.25
IG(D-No-Exam, Weather) ~ 0.92

遵循与之前相同的策略,我们将选择Weather,最后决策树将如下所示:

      Exam?
      /  \
    yes   no
    /      \
 STUDY     Weather?
            /   \
         sunny  rain 
          /       \
       PICNIC     PLAY

现在让我们构建一个决策树,对示例进行分类,但使用不同的root - Friends,并在需要的地方随机选择属性.我们最终得到以下树:

                Friends?
                /     \
              yes      no
             /          \
          Exam?         Exam?
          /  \           /   \
        yes   no       yes   no
        /      \        |     |
     STUDY   Weather?  STUDY  PLAY
               /   \
            sunny  rain
             /       \
          PICNIC    PLAY

两棵树都正确地对训练样例进行了分类.不同之处在于第二棵树更复杂并且可能过度适应训练数据.通过选择始终最佳属性来构建决策树的算法"更喜欢"较短且较不复杂的树以及首先检查最佳属性的树.