Hello again! We're just going to take one last look at discretization in this lesson, 2.3.
We're going to look at how J48 does discretization.
Because it does deal with numeric attributes, so somehow, inside of J48, it's got to effectively
discretize an attribute.
Or at least it's got to be able to determine a split point for a numeric attribute.
Let's just review how J48 works.
It's a top-down, recursive, divide-and-conquer algorithm, and we talked about this in the
last course, Data Mining with Weka.
The algorithm involves first of all selecting an attribute to split on at the root node
(that's the "outlook" attribute in this case), creating a branch for every possible value
of that attribute ("sunny", "overcast", and "rainy"), splitting the instances into subsets,
then going down those three branches and repeating recursively for each branch--selecting an
attribute and so on--using only instances that reach the branch.
The key questions are: what's the best attribute to split on? And: when should you stop the
process? The answer to the first question is, the attribute with the greatest "information
gain"--at least, that's J48's answer.
Information gain is the amount of information that's gained by knowing the value of the
attribute, which is the entropy of the distribution before the split minus the entropy of the
distribution after it.
Entropy is defined in terms of p log p's.
We talked about that briefly in the previous course.
The details we didn't really go into, and I don't think they're too important for you
at this point.
In the previous example, the weather data, the information gain for outlook was 0.247
bits according to that calculation, and that was the greatest information gain of all of
the attributes.
So that's the one that was split on.
That's how it works.
Now let's look at a numeric attribute.
This is the temperature attribute in the numeric weather data.
Here the split point is a number.
The trouble is, there's an infinite number of numbers, so we can't possibly try them
all.
However, we're going to choose split points mid-way between adjacent values in the training
set.
This reduces it to a finite problem, n-1 possibilities.
So here, for the temperature attribute, it goes from 64 at the bottom end to 85 at the
top end.
Below are the class values of the instances: when the value of temperature was 64 it was
a "yes" instance; and there were two instances where the value was 72, one "no" and one "yes"
instance.
There are just n-1 possibilities, and we're going to try them all.
Try all possible boundaries.
If we take that split point that's shown, on the left side of the split point we've
got four "yes"s and one "no", and on the right side we've got five "yes"s and four "no"s.
We can calculate the entropy before the split and the entropy after the split and subtract
them, and the information gain in this case is 0.001 bits.
We might choose that if that's the greatest information gain of all of the possible split
points.
That's how it's going to work for numeric attributes.
Here's an example.
We've already split, let's say, on "outlook".
We've chosen that at the root.
If we look at the "sunny" branch, then there are five instances whose outlook is "sunny".
Those are in that little table there.
If you look at the value of "humidity", it's 70 and 70 for the two "yes" instances and
85, 90, and 95 for the three "no" instances.
That neatly splits the instances into "yes"s and "no"s if we choose a split point somewhere
between 70 and 85.
We're going to choose it halfway, at the point 75.
Well, 75 isn't halfway between 70 and 85, but we've got two things at 70 and one thing
at 85, so we're going to use sort of a weighted halfway point.
It's going to be a third of the way from 70 to 85.
That's where we get the 75 from.
That's the split point, and in this case, that's the end of the matter.
We've discriminated the instances into "yes" and "no" instances down that branch.
In a more complicated example, you can imagine we might split on the same attribute more
than once.
If we have a nominal attribute, once we split on it--once we split on "outlook" here--then
we've used all of the information in the "outlook" attribute, and we certainly aren't going to
split further down the tree on the same attribute.
That's not true for numeric attributes.
We could split with a certain threshold for a numeric attribute, and further down the
tree we might split again on the same attribute, but with a different threshold.
Let's just think about this issue: about discretization when building a tree, as I've described, versus
discretization in advance, which we looked at in the last couple of lessons.
When you do discretization when building a tree, you're determining the boundaries in
a more specific context, in the context of that subtree.
A subset of the instances get down here, so you've got a more specific dataset to maybe
give you a better determination of where a discretization boundary should be.
On the other side, the negative side, your decision is based on a small subset of the
overall information.
You've always got to remember when you're working with a tree that as you get further
down to the bottom of the tree, you've got smaller and smaller and smaller numbers of
instances.
Although you might have a large dataset to begin with, by the time you get way down the
tree you're only dealing with a small number of instances, which is maybe not a good basis
on which to make a decision.
Another issue is computational complexity.
As I've described the algorithm, for every internal node, the instances that reach it
must be sorted separately for each numeric attribute, so that you can work out which
split point on which attribute gives you the best information-gain value.
The complexity of sorting is n log n, where n is the number of things you're sorting.
It looks like you've got to repeatedly sort instances, which could be a bit demanding
computationally, but in fact, repeated sorting can be avoided with a better data structure.
It's not computationally disastrous to do internal discretization.
That's it.
C4.5 incorporated discretization very early on.
Pre-discretization, as we've seen in the last lessons, is an alternative, which has been
refined later.
Supervised discretization uses essentially the same entropy heuristic as C4.5.
We can retain the ordering information that numeric attributes imply.
We don't have to keep on sorting them as we go further down the tree.
Will internal discretization in J48 outperform pre-discretization? Well, there are arguments
both for and against, which we've talked about.
It's an experimental question, and you will answer it in the activity associated with
this lesson.
Not just for J48, but for other classifiers, as well.
Good luck with that, and I'll see you in the next lesson.
Bye for now!