Hello again, and welcome to Lesson 3.2 of More Data Mining with Weka.
In the last lesson, we looked at decision rules versus decision trees.
They are kind of similar representations, but they are interestingly different in how
they express things.
We also looked at a bottom-up covering algorithm for generating rules called "PRISM".
If you did the activity associated with that lesson, then you will realize that PRISM is
not really a terribly good machine learning method.
It's not really meant for serious use.
In this lesson, we're going to look at a couple of schemes for rule learning and show how
to use them in Weka.
The first scheme we're going to look at is called "PART", and it's a way of forming rules
from partial decision trees.
It's the basic separate and conquer algorithm: make a rule, remove the instances it covers,
and continue creating rules for the remaining instances.
To make a rule, PART builds a tree.
It builds and prunes a decision tree for the current set of instances, and reads off the
rule for the largest leaf--the most important rule, if you like.
Then it throws the tree away, and carries on with the covering algorithm.
It seems very wasteful, and I suppose perhaps it is a bit wasteful, but it turns out you
can build just a partial tree--you don't have to build a whole tree.
That's how PART works.
The second method is called "RIPPER": in fact, in Weka it's called "JRip".
It's a basic incremental reduced-error pruning algorithm.
There's class of algorithms that go by this name.
The idea is that PRISM is good at producing rules, but it produces exact rules.
Typically, we want to produce rules that are not necessarily exact, but merely very good.
What incremental reduced-error pruning does is to take the instances, the training set,
and split them into two sets, one called Grow and one called Prune, in the ratio 2:1.
It uses the Grow set for growing rules, adding clauses to rules until you get a perfect rule.
Then it uses the Prune set when you're pruning rules, deleting the clauses from the rule
until you're left with a good rule.
For each class, while there are instances of that class in both these sets, we're going
to use PRISM to create the best perfect rule for that class.
Then we're going to calculate the worth of the rule.
Now, we need some measure of the "worth" of a rule.
There are different ways of measuring the worth of a rule, and different incremental
reduced-error pruning algorithms do different things.
For example, you might just use the success rate, or you might use some more complicated
thing, perhaps even some entropy metric.
Anyway, whatever you do, let's assume you've got a way of measuring the worth of a rule.
We calculate the worth of that rule, and then we omit the final condition--the last one
that we added--and look at the worth of that.
If it's worthwhile, then we take away that final condition and carry on trying to remove
conditions from the rule until we get an optimal version of the rule.
So we build up the rule on the Grow set, and then we prune it back on the Prune set until
we get a rule whose worth is good.
It turns out it's better to prune backwards than to prune on the way forwards.
Again, it sounds a bit wasteful, but it's a good idea to build up the whole rule and
then prune backwards.
Then we just carry on.
We select the rule with the largest worth, and we prune it and remove the instances it
covers, carrying on with the basic covering algorithm.
RIPPER follows this by a fiendishly complicated global optimization step that's really detailed,
really complex, not really very principled, but works really well.
I'm not going to tell you about that.
It's just not worthwhile--you'd never remember it, it's just too hard to--I mean, I don't
remember it.
It's just really complicated.
But this is the basic kind of incremental reduced-error pruning algorithm that it uses
to generate the rule set in the first place.
All right, let's go to Weka.
I've loaded the diabetes dataset.
I'm going to try J48, PART, and JRip.
So here we are in Weka.
Here's the diabetes dataset: 768 instances.
I go to Classify, and I've already run J48.
This is the result from J48.
I've got a decision tree here, quite a complicated decision tree: it's got 20 leaves and a total
of 39 nodes in this tree.
It gets 74% accuracy.
PART produces a rule set that looks like this.
See these rules--"If plas <= 127 and mass <= 26.4, etc.
then tested_negative" (in this dataset, there are two classes, negative and positive).
There's a rule for negative, and a rule for positive, and so on.
This rule set has got 13 rules, involving 25 separate tests.
We get 75% accuracy.
RIPPER does really well, 76% accuracy, there at the top.
It has only 4 rules.
Amazing, eh?
In fact, going back to the slide, here are the results, and here are the 4 rules.
Actually, RIPPER starts out by taking the majority class--in this case tested_negative--and
leaving that to the end.
So it only produces rules for the other classes, and then leaves the majority class for the
default clause like this.
So tested_positive is the smaller class, and tested_negative is the larger class.
These are the rules it's come up with.
Only 4 rules, 9 tests, and the best performance of all.
That's pretty amazing.
PART is quick and quite an elegant algorithm, really.
Repeatedly constructing decision trees and discarding them is less wasteful than it sounds.
Incremental reduced-error pruning is a standard technique.
RIPPER does incremental reduced-error pruning followed by a global optimization step:
it usually produces fewer rules than PART.
There's some stuff in the course text on classification rules, so go and read that.
The activity associated with this lesson involves using the Experimenter to do more reliable
comparisons between rule systems.
I thought I'd end up by telling you about Australia and New Zealand.
You know, a lot of people in the northern hemisphere think that Australia and New Zealand
are really close together.
This map is false.
They're not that close together.
Actually, in New Zealand, we say there are three islands: the North Island, the South
Island, and the West Island--the people who live there call it Australia.
It's quite a long way from New Zealand, and the countries are completely different.
In fact, here's a little encapsulation of what's in Australia, which is not very much
and a lot of dangerous things here in Australia.
New Zealand's completely different.
It's clean and green, and a nice place to live.
I just thought I'd leave you with that thought, and I'll see you in the next lesson.
Bye for now!