Let us now ask how to compute such association rules from the data.
There might be many combinations of features in for example, if there are N
features each taking two values. Then we immediately have two to the N
combinations. And even for moderate values of N, you
would have too many combinations to explore.
The key observation, to getting, an efficient algorithm for association rule
mining was made by Agrawal and Srikant, in the 90s.' And that observation was that if
a combination A and B has support greater than S that means it occurs more than,
say, S times in the data, then so does A and B individually.
Because otherwise, the combination A and B would not occur more than S times.
So in some sense, to find combinations with high support, one can go iteratively
start with. All single feature combinations that have
high support, that means greater than S. This set will contain necessarily all
pairs and triplets and quadruplets if any of them have high support.
So, we do not have to check all combinations, one can go step by step.
So, this is how the algorithm works. We first scan all the records and note
down which features have support greater than s, that means which particular values
of data items. That means, you might have diapers have a
high support, beer has a high support, nuts have a high support, but others
don't. For example.
Then we scan only this subset of data. Throw away all the other data.
And look for pairs that have high support. So remember, we have thrown away a lot of
data in the very step. All those records where none of the high
support features occurred can simply be discarded.
Because they can never contain pairs or triplets which have high support.
So now we scan the subset of data for all the pairs which have high support.
And then, discard some more data items, then scan the reduced data set, for
triples, etcetera. Until finally we know, we don't find any
more sets, with a high support. This considerably reduces the complexity
of finding rules and results in an efficient algorithm.
Think about the complexity of rule mining. Once we have, all possible pairs,
singletons, triplets, etcetera, with high support.
We can check each subset for confidence and interestingness.
Now, in practice, you would not get that many rules.
So, I can simply go rule by rule, and compute the confidences by again, by
counting and interestingness of each rule and for each possible antecedent and
prece, and consequent from the features in a rule, and decide which ones to declare
as your, the rules that you learned from the data.
Note, This is all just counting.
You are only scanning the data again and again and counting things. Whether it is
to find those sets with high support or once you found them to compute the
confidences for different positions of antecedent consequent etcetera and compute
the interestingness. It is just counting so map produced like paradigms are ideal
for such tasks. The association rule mining algorithm we
just described is called the Apriori Algorithm The Apriori Algorithm is a very
popular algorithm, and it's used in many settings.
Not just market basket analysis. But there are some problems with it.
First of all, it depends on why one is trying to find association roots.
One of the reasons one finds rules or tries to find rules is to characterize a
class. So when one wants to figure out what
constitutes a buyer? Which kinds of words do they use?
What constitutes an elephant? What are the features an elephant has?
Or what constitutes a positive sentiment? Which words characterize positivity?
The trouble is, association rules only work on high support.
So small classes that do not enjoy high support, they just are not enough
instances of them. They had left out.
For such situations, one does not normally use association rules, but instead uses,
what I call, decision trees. Now we would not go into decision trees in
detail but it is suffice to say that they are based on mutual information so they
are able to compute the mutual information between each feature and each set of
features with the class in question, very similar to the calculations we had done
earlier of mutual information between different features and the class being
decided. Of course, computing mutual information is
costly because it requires all the, joint probabilities to be known.
And is not really possible for large numbers of features.
The other reason why one might want to get rules is to figure out some structure in
the world. And figure out which combinations of
features actually imply others. And essentially learn some structure to
the normal world without presupposing any classes.
Association rules are great for such tasks except that, because they rely on high
support, it means that negative rules, such as milk and not diapers, implies not
beer, are lost. So we do not, we have no way of figuring
out not diapers, We can only look for a value diapers,
because not diapers could be any other value, like cereal, butter or cola, and
there are just too many possible combinations to check in not diapers.
In such situations one does something a little different, and techniques called
Interesting Subgroup Discovery are used instead.
They are very similar to association rules, however, instead of relying only on
high support or, or, relying on high support, they look for correlations in the
data. One of the earliest papers that talked
about this concept was this one in 1997 by Sergey Brin and [inaudible].
[inaudible] Sergey Brin, of course, is one of the founders of Google, this is before
Google. So learning rules from data is fairly
possible and association rules is, are simple.
I support situations are easily covered but figuring out small support situations
or negative rules require more sophisticated techniques.