AIxploratorium
Decision Trees - Page 2


 

Use a Decision Tree to determine who should win the game

Give up?

Below we present a way to learn a good "predictor", which we can then use to predict whether the MallRats will win any specified game... and in particular, to predict who will win this MallRat/Chinook game.

We first need to present some notation: We view this predictor as a "classifier", as it is classifying this future game into either the "Won" or the "Lost" class. We will also view each game description, such as

[Where=Away, When=9pm, FredStarts=No, JoeOffense=Center, JoeDefense=Forward, OppC=Tall].
as an instance, composed of a set of Attribute=Value assignments (eg, Where is an attribute, and Away is its associated value). (Note this also corresponds to a database record.) As we did not indicate the outcome of this game we call this an "unlabeled instance"; the goal of a classifier is finding the class label for such unlabeled instances. An instance that also includes the outcome is called a "labeled instance" --- eg, the first row of the table

Instance # Where When FredStarts Joe offense Joe defense Opp C OutCome
1 Home 7pm Yes Center Forward Tall Won

corresponds to the labeled instance
 [Where=Home, When=7pm, FredStarts=Yes, JoeOffense=Center, JoeDefense=Forward, OppC=Tall, Outcome=Won].

Decision Trees

In general, a decision tree is a tree structure; see left-hard figure below.

   

Like biological trees, our Computer Science trees also have a single root, whose branches lead to various subtrees, which themselves may have have sub-subtrees, until terminating in leaves. A computer science tree, however, grows upside-down: its root is at the top, and its branches go down. Go figure.

Technically: a tree is a set of nodes and arcs, where each arc "descends" from a node to the children of that node; in the figure above, the "FredStarts" node has 2 arcs: one going to the left-most "Won" node (via the "Yes"-arc), and another going (via the "No"-arc) to the "JoeOffense" node. That "JoeOffense" node is itself the root of a subtree, as it has children "Won" and "Lost". Nodes that are not leaves -- both the root "FredStarts", as well as "JoeOffense" --- are called internal nodes Again, see Notation for more details.)

Note each unlabeled instance (remember "instance" -- see above) corresponds to a path through the tree, from the root to a leaf: eg, the instance representing the upcoming MallRat/Chinook game will go "right" at the root, as Fantastic Fred is not starting, then go left at the JoeOffense node, as Joe is playing center on offence. This will end on the "Won" leaf node. That is, this tree is asserting its guess that the MallRats will win this game.

Of course, this is just the opinion of this single tree.  Note the data has a different opinion: there are 4 previous games where "Fred did NOT start and Joe played Center on offense", and the MallRats won only 2 of these 4 ! Similarly, the "FredStarts = Yes" branch points to a "Lost" node; note however the MallRats actually WON 8 of 10 games where Fred started.

This information clearly lessens our confidence that this specific tree is correct, as we naturally assume that these previous games should be relevant. Our task, then, is:

How to use a data set (such as the records from the previous games) to LEARN an accurate decision tree?

We will then use that learned tree to "classify" a new example: here, to determine whether the MallRats will win this upcoming game; see figure below.


Learning Decision Trees

A decision tree needs to decide when to split on which attributes.  In particular, what is the appropriate root (ie, top-most) attribute?  Should it be "FredStarts" or "JoeOffense" or "Where" or ... ?

It is then clear which records (ie, previous games) go to which child: eg, if the root was "FredStart", the records for all 10 "FredStart" games go left (following the "Yes" arc)

Where When Fred Starts Joe offense Joe defends Opp C OutCome
Home 7pm Yes Center Forward Tall Won
Home 7pm Yes Forward Center Short Won
Away 7pm Yes Forward Forward Tall Won
Away 9pm Yes Forward Forward Short Lost
Home 7pm Yes Center Center Tall Won
Away 7pm Yes Center Center Short Won
Away 9pm Yes Center Forward Short Lost
Home 7pm Yes Center Center Short Won
Home 7pm Yes Center Forward Short Won
Home 7pm Yes Center Forward Tall Won

and the other 10 "Fred didn't start" games all go right.

Another question is "When to stop?". For example, after following the "FredStarts = Yes" arc from the root, we could stop here.  Note, however, that the MallRats won 8 of these 10 games, and lost the remaining 2. While this does suggest the MallRats will win in this situation, there are counter-examples, which suggests we should ask some other question here.  Here, if we ask "Where", we see that the MallRats won all 6 of the Where=Home games that Fred started; see below:

Where When Fred Starts Joe offense Joe defends Opp C OutCome
Home 7pm Yes Center Forward Tall Won
Home 7pm Yes Forward Center Short Won
Away 7pm Yes Forward Forward Tall Won
Away 9pm Yes Forward Forward Short Lost
Home 7pm Yes Center Center Tall Won
Away 7pm Yes Center Center Short Won
Away 9pm Yes Center Forward Short Lost
Home 7pm Yes Center Center Short Won
Home 7pm Yes Center Forward Short Won
Home 7pm Yes Center Forward Tall Won

On this branch, we can confidently stop, and produce a "Won" label; see tree. The idea here is to continue splitting until "purity" -- ie, until all of the records that reach the node have the same label. We then create a leaf node, whose value is that label (here, "Won").


Actual Demo

So, for now, the only issue is deciding which attribute to test.  How?

Why not just chose attributes randomly? To find out...

  • run the applet by selecting "Initialize" and then "Run" from the "Algorithm" menu. (Be sure the title above the table (on top left of top-left "Dataset" panel) says "Basketball Training Examples", and that the "Splitting Function" (under the "Algorithm" menu) is set to "Random".)
    If you can't see the entire tree, right-click on the tree panel -- a popup menu will appear. Select "Full Panel Tree View" to expand the panel to full size.
  • Don't worry about how the actual algorithm is running -- we'll discuss that later. (If you really can't wait, see the Manual.)
 

Who will win the game? Decision Trees Random Splits