Hello and welcome back to the course on Machine Learning.
Today we're talking about the intuition behind the a priori algorithm.
So let's get started.
And we're going to get started by talking about a story.
It's a somewhat legend of data science
or a legend that is, quite well known in data science.
And you may have heard of, this, legend.
It's not a myth. It's actually happened.
But, as you know, things when they happened a long time ago
and then time passes and the facts get the story.
But I'll tell you my story of this legend.
And, it might not be exactly correct, but this is how I,
know about and how I've heard about it.
So, what do you think the commonality is between these two products?
Pampers or diapers and beer?
What do you think they have in common, and why are they
part of this, or, urban legend?
why are they part of this data science lesson?
Well, as the story goes,
a company we're not going to name the company,
but a company that is actually actually like a, convenience store,
did some analytics around the,
products that people are purchasing.
And so they were looking at,
you know, what people are checking out with what are the commonalities?
And they analyzed thousands and thousands and thousands of, transactions.
So thousands of people who actually checked out, if not tens of thousands and,
they found a very interesting thing that,
very often during certain times of the day
when people shop in the afternoon, between six and, 9 p.m.,
people who buy, diapers also buy beer.
And it was like, out of the blue, completely out of the blue.
like how why these two products are completely not connected.
Right.
why would somebody buy, beer when they're buying diapers?
Or why buy diapers when they're buying beer? Right.
So, that was the fact that they came across in the data
and, the explanation to this
fact, one of the plausible explanations is that,
in the afternoons or in the evenings when,
the husband gets home, and they're like him,
the husband and the wife are taking care of the their baby.
they sometimes find that they run out of diapers.
And who has to go pick up the diapers?
Well, the husband has to go pick up the diapers, right?
Or the wife sends the husband to go pick up the diapers.
And while he's picking up the diapers,
because it's really after hours after work,
he also he's already in the convenience store.
He also picks up some beer. Right.
And so that is a plausible explanation.
Might be the case, might not be the case, but sounds pretty reasonable
and based on that.
So that's something that you can't really think of just by yourself.
But that comes from the data. Right.
And based on that you can decide how to arrange products in your store.
Right.
So some stores might decide to put these two products
closer to entice people to buy a beer when they're buying diapers.
But actually, a lot of stores
do the opposite.
There are a lot of stores, separate, beer and diapers, right?
Just like they try to separate and you'll probably notice
this from your convenience store that they try to separate,
bread and milk as far as possible. Why?
Because that way.
Yeah, they already know that these two products are bored together.
And so you actually have to walk through the whole store to pick up,
you know, you've picked up your bread and then to get to the milk,
you have to get all the way through the whole store to the completely opposite
corner of the store.
So as you're walking through the store, you see more other products
and you're more likely to pick up
an additional item that you weren't actually planning on buying
when you got to the store in the first place.
So there's a lot of interesting marketing tactics that are used based on this data.
But the question is, how do you get to this data?
And one of the ways to get to it is that a priori algorithm.
So let's talk about a priori in a bit more detail. Now.
All right.
So a priori is about people who bought something, also bought something else,
or who watched something, also watch something else
or who did something also did something else.
So, it analyzes and this whole association,
rule learning a part of the course is all about analyzing when things,
come in pairs or in triplicate or in, in C, like not in sequence,
but they are combined together for some reason,
looking for those, rules and those ways that this happens.
All right.
So let's have a look.
for instance, movie recommendation. Right.
So you've got user IDs, you've got movies that the people liked.
Movie one, two, three, four, movie one and two for the second person, and so on.
And from here, just by looking at it, even without not knowing anything about,
association rule learning or a priori, all the a priori algorithm,
you can really tell that, there are some potential rules
that can come out of this that, for instance, everybody who watches movie
one, not everybody, but it is likely that people who watch movie one will,
or who like movie one will also like movie number two.
And people who like
movie number two are quite likely to also like movie number four.
And people who like movie number one are also quite likely to like movie
number three.
So there you can
you can come up with lots of different
potential rules, but some are going to be stronger,
some are going to be weaker, and we want to find the very strong ones
in order to build our business decisions or our other decisions,
on those rules that we can see in the data.
Right.
We don't have to go and ask people, hey, do you like movie number one?
And would you like movie number two because of that?
Do you like movie number two or what is your taste and preference?
We can see these things from the data and we want to extract this information.
And as long as, you know, we have a large enough sample size,
know if it's not just like five people, if it's 50,000 or, 500,000 people
that we're analyzing, we can come up with quite some quite solid rules.
All right.
So, here's
another example where we've got a market basket.
So, example of, people who, buy a grocery, not just groceries,
but this small kind of like a, restaurant or a, takeaway place.
And here you can see there's a link, obviously, in burgers and French fries,
interesting vegetables and fruits and people
trying to be healthy burgers, French fries and ketchup.
So again, these are potential rules, not necessarily
the ones that we're going to take away from data.
This is just an example of something that you might observe,
visually just by looking at this data set.
All right.
So how does that apriori algorithm work?
Well, the apriori algorithm has three parts to it.
It has got the support, the confidence and the lift.
So we're going to start off with the support.
and you will see that it's, it's very similar to
something we've already discussed.
It's very similar to the way we talked about the intuition for the Bayesian,
for the Naive Bayes, classifiers.
So let's have a look here.
We've got movie recommendations, support for movie. is
the number is defined as the number of users,
who watched movie M divided by the total number of users.
Right.
And Market basket optimization, same thing.
number of transactions containing.
So an item I divided by the total number of transactions.
Let's, have a look at an illustration here.
We've got 100 people, so we've got five rows
and 20 columns of human beings.
and,
let's see how many of them,
let's say we're talking about a movie
and I'm going to, give an example of one of my favorite movies, Ex Machina.
And if you haven't seen it, definitely check it out.
It's all about AI and machine learning.
So let's say let's see how many of these people have actually seen Ex Machina.
So there we go.
There's ten people who have seen Ex Machina right out of 100.
So what does that mean?
That means our support here is 10% quit.
Okay.
Now let's move on to step two.
Step two is we need to find the confidence.
What is the confidence?
Well, confidence is, defined as the number.
Let's go for movies.
So the number of, people who have seen, movies
M1 and M2 divided by the number of people have seen a movie M1.
So here we're going to assume that we we're testing a rule.
We're testing a rule that, let's say people who have seen interstellar, right?
Where we have a hypothesis that, says that people have seen interstellar,
they are also or have, liked interstellar
are also, likely to like, mixed machine.
Oh, let's let's even go.
We've seen that people have seen interstellar are also likely
to have seen, Ex Machina.
So basically here movie number one, M1 is going to be
the, interstellar movie,
the one that we're saying, okay, so we're going to take
everybody who's seen interstellar and we're going to check
how many of them have seen Ex Machina.
And that's exactly what we're doing here.
And Market Basket optimization, same thing.
You can think of an example of French fries and burgers, for instance.
People have had burgers.
We've ordered burgers also likely to order French fries.
So, at the top you would have people have ordered burgers and French fries.
And at the bottom you have people who have ordered burgers only,
who have ordered burgers, regardless of whether they've ordered
French fries or not.
much easier to talk about this with an illustration.
let's say those great people in colored in green
are the ones who have seen interstellar, right?
Who have, watch this movie.
Now we want to know, not out of a whole population,
but out of just those people who have seen interstellar.
How many of them have seen Ex Machina?
So out of them, we have seven people who have also seen Ex Machina.
So there's only seven people who have seen both movies.
That's what we're after.
And so our confidence is going to be seven divided by 40, just by definition.
This is how it's calculated.
40 people have seen, interstellar
and seven people out of those 40 have actually also seen Ex Machina.
So, the conference here is 17.5%.
Good.
And the next part or the third and last step is the lift.
And what is the lift?
Lift is very simple.
Again, is going to be very similar to, what we had in the naive Bayes, naive
Bayesian classifiers, in that algorithm when we were discussing it.
So the lift is basically the confidence divided by the support.
so what we calculated in step two divided by what we calculated in step one.
And let's just to talk about it in the illustration,
because it's going to make way more sense that way.
so here's our population.
Those people in green are the ones who have seen interstellar.
And all of these people in red are the ones who have seen Ex Machina.
So basically our lift is all right.
So if we just randomly, right, randomly suggest
to a person to watch Ex Machina, right.
what is the likelihood that they will, you know, that it's a movie for them.
It's a movie that's not in this population.
Like out of the out of this population.
We know that out of 100 people, only ten actually works.
What shakes machine.
And we're going to assume that watched and like are interchangeable terms here.
So we're going to assume that if they if they didn't watch it,
they're not going to like it anyway.
So if we take another random,
this population and then, what is the likelihood
that if we recommend
to a random person in that population, that brand new population,
we recommend that, the Ex Machina movie, what is the likelihood
that they will like it?
Well, the likelihood is, 10%, right?
Because we only out of 100 people, only ten of them actually liked that movie.
But now the question is, can we improve that result by using some prior knowledge?
That's why the algorithm is called a priori.
in that new population, let's
only recommend Ex Machina to people who have already seen interstellar.
So people who are marked as green in this population.
So we will only find out.
We will only ask, have you seen interstellar?
If they have, then we'll recommend Ex Machina.
What is the likelihood that a person will actually like Ex Machina
if we recommend them that way?
Well, in that case, the likelihood, as we've calculated out of the green people
only, not only of the green people, 17.5% actually elect ex machina.
So the lift is the improvement in your prediction.
So your original prediction, your original predictions 10%.
Right.
If you just randomly take a person out of your new population
and recommend them Ex Machina, they'll like it with a likelihood of 10%.
If you first ask the question, have you seen and liked interstellar?
If they say yes and then you recommend Ex Machina, the likelihood
of a successful recommendation there is 17.5%.
So the lift is by definition 1.75.
There we go.
That is what, the lift is defined as
and that's pretty much the whole apriori algorithm.
That's the steps that it involves.
And now we're just going to put it all together,
in, in this one kind of, step by step process.
So step one, you need to set up a minimum support and confidence.
Right?
So you won't want to only, because there's so many different recommendations.
Right. We only looked at, one example.
well, one specific example to simplify things, we talked about,
Ex Machina and interstellar.
But as you can see in the examples before that you could have like
100 different movies and the different combinations, like a priori
is actually quite a slow algorithm because it just goes through,
all of these different algorithms or all of these different combinations.
So it says, what if movie one is a good, recommendation
for movie two or movie one means a personal like movie two.
Movie one means a personal, like movie three and movie one, movie four.
And then it actually combines more.
It says movie one and movie two might mean that personal, like movie three
and so on.
And so it actually combines lots and lots and lots of not just pairs, not triplets.
like it, combines four, five,
six, seven items in one, in one set and so on.
And yeah, so it gets quite big.
And therefore you need to set some kind of limitations.
so you need to set a minimum support.
For instance, you might not want to look at products
that are, that have a support of less than 20%.
You might not even want to consider them because you don't want to waste your time,
building a model for something that is only has
a, success rate of 20% on its own.
Right? So. Or you might limit at 5%.
then you, you might want to also limit a confidence.
So in our example the confidence was 17.5%.
Right.
that somebody who was somebody who liked one movie will like the other one,
maybe you might want to limit it, to, you know, anything less than 12%,
you don't want to look at it because it's not a strong enough,
factor for you is not a strong enough rule for you, because there is going
to be so many different rules on the output of this algorithm.
you already know that you'll have much stronger ones.
So you don't want to consider anything that's less than 12% or 20% or,
whatever percentage you decide to set for you in that specific scenario.
then once you've set those, then you take all the subsets in,
transactions having higher support than minimum,
then the minimum support take all the rules of the subset
having high confidence and minimum confidence.
Basically apply those two minimums that you've said.
And then at the end, of course, you sort the rules by the decreasing lift.
So that's where the lift comes in.
The rule with the highest lift
given these criteria is going to be the strongest rule.
And that's the one you might want to look into first. Right.
Something like I don't know if a person buys a burger and French fries,
then they're likely to buy, tomato sauce or ketchup as well.
And because, you know and and that some of that sometimes it makes sense, right.
Because you need ketchup
to a lot of people like to eat ketchup with their burgers and French fries.
So basically you find the ones with the highest lift,
and those are the ones in your top ten or top five, and those are the ones
that you consider for actually implementing a business decision.
and basing it on them.
So that's pretty much how the apriori algorithm works.
it was quite a long story.
Well, I thought we had some some good fun here.
There's there's another example that I wanted to share with you.
Oh, okay.
So just wanted to mention that recommender systems like things like,
companies like Amazon News and others and Netflix and so on.
there like a good there would be a, there would be a good,
example for using a priori.
I probably would be good there.
But of course, they are much more sophisticated.
They're not just a priori, they actually use combinations or, very,
specific or specifically designed algorithms. So,
I just don't want you to be confused that a priori
that means that everything uses apriori.
Apriori is just a basic, kind of,
straightforward approach to, to solving this problem.
And it's a good example of, you know, how it can be done.
But of course, there are other ways of doing it.
And for instance, you know, we'll look at the
we'll look at some of the methods and in fact,
some of the methods that we already use can be used to build,
recommender systems as well.
All right.
So on that note, thank you for your attention.
And off we go to had to look at how
we can code a priori in, R and Python.
And I'll see you here next time.
Until then, happy analyzing.