Association Rule Mining (contd) Video Lecture | What is Data Analytics? - Data & Analytics

hello and welcome to the second module
on Association rule mining in this
module we'll look at a very popular
algorithm that's useful Association rule
money
as I said earlier the main problem in
mining Association rules this comping
part so typically how we would do it is
that you would generate candidate
frequent itemsets and then count how
many times they occur and then you prune
the candidates based on the count so if
the count is above a certain frequency
then you're going to all the most
frequent itemsets and if they're below a
certain frequency is going to the tip
thing but then the problem with doing
such an approach is that you have a
combinatorial number of candidates and
it's a think about it so you have have
like ten different items from which your
transactions can be drawn and let us say
you are considering two item sets so
that essentially gives you ten choose to
candidate item sets now this is a small
number think about the real applications
where these candidates it's can be
millions millions of candidates how
would you even generate candidate item
sets have more than this very very small
size of candidates so you really need a
clever way of generating fewer
candidates so the very first approach
for looking at generating fewer
candidates came aboard the late 90s
which is the a priori property so the a
priori property is a very clever
observation it says that all non-empty
subsets of a frequent item set must also
be frequent even if one of the item the
subsets is not frequent then I don't
have to consider the larger item set I
don't even have to come deep adds an
item set right so the first paper that
proposed this a priori property and came
up with a faster
Mining Association rules was proposed in
1994 and it has been a very seminal
algorithm now the whole first they
introduced this problem of finding
frequent itemsets in the database of
transaction it set the tone for the
entire field in fact this use of the
term Mining Association rules almost was
the reason for the whole subfield of
data mining and since then there have
been numerous improvements that have
been proposed on top of the a priori
algorithm that love you to mind really
large data scale up to millions and so
on so forth but still the a priori
algorithm is well so in this module I
will talk about the a priori algorithm
and give you a more like introduction by
an example so I'd leave it to you to
look up other algorithms if you are
interested in Association rules so it is
we start off with a very simple example
so look at a very small ranch sectional
database so it has got only four
transactions in it so it's a fingerprint
ID and there are a total of five
different items which could be figuring
in these transactions we are going to
call them it through E so let's look at
the the set of one item sets so we're
having a 2 e and this count the
frequency of these item sets but suppose
that I have a minimum threshold for the
support of to have four transactions an
item set can be called frequent if it
appears in at least two of these four
transactions so you can immediately see
that item set D is not frequent so not
only is the one item set be on
frequently any larger item set that
contains D as an element in it can also
not be free so I am looking at the
candidates I have to use for generating
two items it's I can completely
low-beam right and
of all the candidates to item sets are
those that do not have years I mean do
not have D as part of it so essentially
the to item sets that will have to
consider oh maybe a c a b c and b c so
these are recently generated by looking
at all possible combinations of the
frequent one night of sex now now that
we have these candidate to item sets so
we run a second scan through the data
and then we count the frequency of the
to wake up sex now you can see that baby
yayyyyy actually not frequent among
these and therefore we can room those
away so we have a list of frequent to
item sets which comprise ac/dc b and c
isn't clear so far so we had we started
off top flip all the one item sets
dissolve the candidate momentum cells
the conquer their frequency we left out
the one i trip said that was not
frequent and then from the frequent on
item sets we generated a set of
candidate to item sets which could be
frequent then we counted the frequency
of these two item sets and from there we
are pruned away then the two that were
not frequent so this early frequent to
item cells from this we can generate
candidate 3/8 of cells so if you think
about it so the candidate three item
sets could be a b c a be e and BCE so
can a b c be a candidate if they cannot
be a candidate because they subset a b
is no longer it's not frequent that
since the subset a v is not frequent ABC
cannot be candidate item set and
likewise can we look at the DC in DC be
a candidate the frequent itemsets
yes because bc is frequent bees
frequencies
and what about a ve again that cannot be
a candidate get upset because a a AE s
is not a frequent itemsets essentially
we have only one candidate three a cup
set and then we count the frequency of
the three item set and then we find that
it's actually frequent come on we have
the complete set off of frequent makeup
sex so one three item set which is PCE
for two item sets and then for one item
sells is a non flicker we don't have to
look for larger items of civil goods
potentially possible because we do have
high elements from 5e items but we don't
have to look for any other liquid makeup
since because there is only one frequent
three items so the in theory property
allows system room the number of
candidate item sets that will have to
generate so but still there is a problem
in that so every time we generate a
candidate sets of larger size we
essentially do another scan over the
data so the more recent algorithms try
to minimize the number of scans you have
to perform over the entire data set
because that's a very expensive
operation this is a big challenge but
there are one other caveat which I want
to point out so scaling up to large data
sets is a big challenge with this one
with the caveat which I want to point
out the high confidence is not always a
good idea so you have to be really
careful about what we mean by high
confidence so I can say that somebody
buys games implies they buy videos
confidence of success is present the
support of 37 percent so this is
something that was actually observed in
the real data set from anon we do rental
company now which also was selling video
games in there so from the real data
they found that somebody buys games then
they've also buy videos with the
confidence of successes person in
support of 37 person so essentially it
means 37 percent of the people that came
to their show shop bought games and
videos and 66% of the people to block a
also Bach Biggles but then if you just
look at what fraction of their customers
bought videos right that is 75% of the
customers actually bought videos so even
though this rule has a high confidence
you can see that if you buy a game
actually implies negatively on buying
videos this is a video store after all
and so people typically come in to buy
videos but the occasional person who
comes in to buy a game is not that
interested in buying videos so it's
actually implied a negative correlation
and if you just blindly been using come
from support and confidence to determine
rules then you will actually pick this
out as an important rule in terms of
having a high confidence right so one
measure that people use instead of
confidence and support alone is known as
lift lift is essentially the ratio of
the confidence of the rule to that of
the default rule so can have a lift up
one that means that it really does not
imply anything so whether a happened or
not B is always going to happen with the
same frequency in place we miss a lift
of one and it is not significant rule
but if a implies B has a lift much
larger than one that would mean that so
the things tend to mean a is truly an
indicator of B but again if you think
about in this case of games of video the
lift will be lesser than 1 in which case
it indicates is from negative
confirmation so lift is a useful measure
to have and what lift is not the only
measure that people have proposed
another variety of different measure is
the typical of the first analyze
Association rules and Association rule
mining is a very very active area of
research and so this is essentially just
an introductory module and if you're
interested in the Association rule
mining if you spend more time and in
looking at the various modifications and
additions of people have come up with
all of the earth
so just to summarize the the major
challenges in the secession rule mining
is how do you extend this to millions of
transactions there could be billions and
billions of potential itemsets so how do
you do the pruning efficiently how do
you minimize the number of passes how do
you reduce theorem the amount of memory
that is required while you are doing the
counting so there are many many rules
and many many issues that they have to
consider in applying this to large data
set so we have talked about
transactional data now so it's in some
sense easy to come and discrete events
that are happening but what about
continuous data like time series data
images how would you go about even
identifying Motul cooperate items
discounting and/or data with rich
structure like graphs so frequent
pattern mining in graphs is a very very
important topic which is used in diverse
areas like drug discovery and social
influence prediction and so on alright
so how would you can you leverage the
structure or can you make computation
more efficient and random in structured
data so that is something which is a
very active area of research and
exploration and one important twist to
this whole frequent pattern mining issue
is that we are not fair sometimes not
interested in frequency but in
significance so where a occurs that
assay in point three percent of all
transactions right but when B occurs it
occurs in one point two percent of the
transcription so that means we employ
yay and that's a significant effect
because it improves the frequency of a
four point three to one point two and a
might be the needle in the haystack that
we are looking for and finding B and
actually uses a greater evidence for the
presence of a so-so so such patterns are
significant but if you just go by the
frequency alone this off be very very
infrequent occurrence
so how do we actually look at such
frequent non frequent but significant
pattern occurrence already so that's a
big challenge of the Association rule
mining community again I guess with the
activity of research that links us to be
in the fee