We now turn to finding rules from data.
Now rules are essentially correlations
between different features as we've seen
earlier features need not be independent
so finding rules is essentially finding
out which features or which sets of
features are related to each other or
correlated.
In some sense we are trying to cluster
features rather than cluster the data.
For example we might want to discover
rules which say that if you have, like and
lot in a comment than it's very likely to
be positive.
If you have an not and like in a comment
it's very likely to be a negative.
Similarly, we, one might like to find a
rule which says that searching for flowers
means that one is searching for a cheap
gift or in the case of the animal example.
If an animal's a bird, then it chirps or
squeals.
If an animal chirps and has two legs then
it's a bird.
In the case of people buying items, we
might want to figure out interesting
situation that those who buy diapers and
milk also buy beer. In each case what it
is trying to not look at clustering of
objects or data item.
But is looking at clustering the features,
and seeing which features co-occur
together in the data very often.
So, what one is trying to do is find
statistical rules based on the frequency
of co-occurrence of features.
In our unified framework.
What this means is we're trying to find
regions, again, of X that indicate
correlation of features, that is those
regions have more data items than would be
expected if all the features were
independent.
Think about it again.
If features are completely independent,
then you wouldn't have that many
situations of birds chirping or squealing.
Because these features don't necessarily
co-occur together.
But if these features are correlated, that
is, there are actually birds that chirp
and squeal you'll see many such instances.
And those regions will be more populated,
than say objects or animals that chirp and
have four legs.
So this time.
Instead of comparing our data to random
data, we're comparing our data to.
Data which has the same features but,
where the features are independent.
So, P zero now is the distribution
assuming independent features so, it's
just the product of the distributions of
each feature.
Now, these are not uniform distributions,
they happen to be just the independent
distributions of every feature in the data
that we actually observe.
So if we can conduct our thought
experiment again, and set y equal to one
for all the real data, that means the data
that actually exists.
And add y equal to zero, points, that
means extra points, by picking points
where each feature is uniformly chosen not
at random, but from the data.
So the probability of choosing a chirp
depends on the number of times [inaudible]
occurs in the data independently of any
other feature.
Similarly, the probability of choosing
four legs is simply dependent on how many
times four legs occur in the data rather
than any other feature occurring alongside
that.
So instead of comparing the actual data to
random data, one compares it to.
Artificially generated data, where each
feature's chosen independently.
Now if we choose F of X, again it's the
expected value Y given X where Y is one
for the real data and zero for these newly
added points.
This again estimates R upon one + R where
R is P(x) by P0(x).
This time P0(x) is this distribution not
the random distribution but a distribution
that assumes that features are
independent.
Again, the extreme region of f(x) indicate
those.
That have high support and we'll explain
what support means in a minute, and are
therefore, regions where we can
potentially find rules, like the one we've
shown above.
Let's see how, the most popular technique
for finding rules in data is called
associated rule mining and it works on
data which consists of instances which
have features.
So for example, you can have animals that
have features, you could have shopping
transactions where the features are the
items that people buy.
And one wants to infer rules of the form
a, b, and c implies d, where all four are
just features.
We don't really know upfront which ones
are on the left and which ones are on the
right.
But we'll decide based on certain
principles.
Fourth principle is, that this combination
a, b, c, and d has high support.
What this means is, that the probability
of finding a combination ABCD is
reasonably high in the data.
Typically, we choose twenty, 30 or 40%
support.
Those are considered extremely high.
But the point is that this combination
occurs high enough to warrant it being
considered as a potential rule.
Next principle is that, the rule that went
in first out of this combination of four
features, is one where the confidence is
high.
All that means is that.
Of all the cases where you have a, b and
c.
A large number of them actually have'd'.
So now you are considering more instances
than just the ones where there is'a', 'b',
'c' and'd', you are considering those
where they might be only'a', 'b' and'c'
but of those that have only'a', 'b'
and'c', a large number of them also
have'd'.
So the Conditional Probability of'd'
given'a', 'b' and'c' is [inaudible], so
there is a high confidence that'a', 'b'
and'c' result in a'd' actually occurring.
And lastly, this rule should be
interesting, in the sense that.
The confidence that d occurs given a, b
and c is significantly higher than the
probability of d occurring just by itself.
So, for example, if d always occurred in
the data, that means you always had a
value d, that everybody always bought,
say, milk, then any rule that you came up
with, with whatever confidence would not
be interesting because.
The probability of D given A, B, and C
would be the same as the probability of D
and it really wouldn't be very
interesting.
On the other hand, if one found that those
who bought beer also bought diapers.
More, than those people who bought, beer
just like that.
That means the propensity to buy beer is
higher if [inaudible], if the person also
buys diapers.
Now, that's interesting because that tells
us something about how one might want to
place items on the shelves in the store.
This is actually the classical example of
a correlation between beer and diapers
that a large retail chain found way back
in the 80's.
And it sparked all this interest in what
is called, market basket analysis and
Resulted in algorithms for association
rule mining.
But association remaining is more than
just for transactions.
If one thinks about objects in the real
world, one might come to conclusions like
birds chirp or.
Squirrels squeal or lions roar.
Which is quite interesting.
Since these are rules which we consider to
be common sense, and the technique like
association rule mining might actually
allow us to such rules amongst the
features, apart from just knowing that
features are correlated with each other.