{"id":19997,"date":"2019-05-23T14:31:46","date_gmt":"2019-05-23T12:31:46","guid":{"rendered":"https:\/\/relaunch.striped-giraffe.com\/?p=19997"},"modified":"2026-05-25T14:26:17","modified_gmt":"2026-05-25T12:26:17","slug":"looking-for-similarities-with-association-rule-mining","status":"publish","type":"post","link":"https:\/\/www.striped-giraffe.com\/en\/blog\/looking-for-similarities-with-association-rule-mining\/","title":{"rendered":"Looking for Similarities With Association Rule Mining"},"content":{"rendered":"

[vc_row][vc_column width=”1\/3″][\/vc_column][vc_column width=”2\/3″][vc_column_text]<\/p>\n

We like having our ten stripes in a row and we ask ourselves who else does?<\/h3>\n

 <\/p>\n

Life is unfair! Some geniuses are acknowledged and honored during their lifetime, some even long after it, but there are a lot of fundamental research pioneers who have unfortunately fallen into obscurity in society\u2019s collective memory. Petr H\u00e1jek (6 Feb. 1940 \u2013 26 Dec. 2016), Professor and Director of Research at the Institute of Mathematics of the Czech Republic\u2019s Academy of Science, was one of those pioneers who built the foundation of modern machine learning theory, and it is he to whom I devote this article.<\/p>\n

More than 50 years ago, in 1966 \u2013 the year of the mini-skirt, Vietnam war protests and the space-race between United States and Soviet Union \u2013 Petr H\u00e1jek, together with his colleagues Tom\u00e1\u0161 Havr\u00e1nek, Ivan Havel and Metod\u011bj Chytil, formulated the GUHA (General Unary Hypotheses Automation) principle. The GUHA principle describes the idea of using computers to generate series of hypotheses that describe relations between the properties of objects. Ultimately, the GUHA principle forms the foundation for Knowledge Discovery in Databases (KDD) (better known as data mining or knowledge extraction) and for unsupervised machine learning techniques, the research areas being emerged several decades later.<\/p>\n

In this article, I would like to talk about association analysis, a simple but extremely useful unsupervised learning technique that traces back to H\u00e1jek\u2019s GUHA principle. Generally speaking, association analysis addresses the problem of finding highly probable subsets of data and the highly probable subset combinations.<\/p>\n

 <\/p>\n

As we know, many businesses have enormous amounts of customer and customer purchasing data. For example, a grocery store definitely owns data containing the product names purchased in each transaction. Other retailers and the majority of online dealers also have similar data on purchases at their stores. Using these data, we might want to find subgroups of products that tend to co-occur, in either purchasing or in viewing behavior.<\/p>\n

Retailers might be interested in cross-promoting product combinations with different deals, if they know that these products are very highly correlated in such a way that people purchase them together. Online platforms can use this information to generate content recommendations. Another huge topic is strategic product placement within grocery stores, because certain product arrangements encourage consumers to purchase them both at the same time. And of course, the variety of use cases goes far beyond the grocery store example! For instance Netflix-like applications recommending content based on viewing behavior, even without any feedback at all from the customer. Further embodiments of these ideas could lead to use cases covering the analysis of social trends and even the promotion of political campaigns.<\/p>\n

 <\/p>\n

Let\u2019s look at the simplest version of association analysis based on grocery basket analysis \u2013 the canonical way of thinking about finding associations among data. We\u2019re assuming that six people have a basket at a grocery store, and they have different objects in their basket at checkout time. Imagine now that we have millions of these checkout transactions and they\u2019re across thousands of products; we now might want to use this type of data to analyze\u00a0patterns of co-occurrence<\/strong>!<\/p>\n

Which products tend to appear in baskets at what rate, and what are the association rules? And\u00a0knowing those association rules, given that they\u2019ve got one object in their basket, we\u2019re going to predict that they are more likely to have a second object in their basket<\/strong>.<\/p>\n

For example, consider the following \u201cgrocery baskets\u201d of six customers:<\/p>\n\n\n\n\n\n\n\n\n\n
Basket ID<\/strong><\/td>\nItems<\/strong><\/td>\n<\/tr>\n
1<\/td>\nCola, Butter, Bread, Cheese<\/td>\n<\/tr>\n
2<\/td>\nBread, Cheese, Milk<\/td>\n<\/tr>\n
3<\/td>\nBread, Fanta, Beer, Eggs, Butter<\/td>\n<\/tr>\n
4<\/td>\nEggs, Salami, Butter, Beer, Cola, Toast<\/td>\n<\/tr>\n
5<\/td>\nToast, Eggs, Butter, Fanta<\/td>\n<\/tr>\n
6<\/td>\nBread, Milk, Butter, Fanta, Cheese<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Based on these data, we want to analyze patterns of co-occurrence:<\/p>\n

\ud835\udc35<\/span>\ud835\udc5f<\/span>\ud835\udc52<\/span>\ud835\udc4e<\/span>\ud835\udc51<\/span>\u27f6<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span><\/span><\/span><\/span><\/p>\n

Let\u2019s look at this problem from a more abstract perspective.<\/p>\n

First, imagine that we have\u00a0\ud835\udc56<\/span><\/span><\/span><\/span><\/em>\u00a0different objects, for example, there could be\u00a0\ud835\udc56<\/span><\/span><\/span><\/span><\/em>\u00a0different items for sale in a grocery store, and each of these items has a unique index from one to\u00a0\ud835\udc3c<\/span><\/span><\/span><\/span><\/p>\n

\ud835\udc56<\/span>\u2208<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span><\/p>\n

Then let us assume we have a collection of subsets of these items, i.e.\u00a0\ud835\udc37<\/span>\ud835\udc5b<\/span><\/span><\/span><\/span><\/span>\u00a0for the\u00a0\ud835\udc5b<\/span>\ud835\udc61<\/span>\u210e<\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00a0subset would be a subset of items from one to\u00a0\ud835\udc3c<\/span><\/span><\/span><\/span>. In other words, we should think of\u00a0\ud835\udc37<\/span>\ud835\udc5b<\/span><\/span><\/span><\/span><\/span>\u00a0as giving the list of things purchased by customer\u00a0\ud835\udc5b<\/span>=<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span><\/span>\ud835\udc41<\/span><\/span><\/span><\/span><\/p>\n

\ud835\udc37<\/span>\ud835\udc5b<\/span><\/span>=<\/span><\/span>\u2282<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span><\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span><\/p>\n

So now there are\u00a0two objectives<\/strong>\u00a0we want to accomplish here. The first is to perform an association analysis. This is simply about locating subsets of products that have a high probability of occurring together. For instance, let\u2019s agree on<\/p>\n

\ud835\udc3e<\/span><\/span><\/span><\/span>, being\u00a0\ud835\udc4f<\/span>\ud835\udc5f<\/span>\ud835\udc52<\/span>\ud835\udc4e<\/span>\ud835\udc51<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc5a<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc52<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span><\/span><\/span><\/span><\/p>\n

and then we\u2019ll count how many of the grocery baskets contain those three products together. By dividing this figure by the total number of baskets, we get the fraction of customers that purchased bread, milk and eggs together:<\/p>\n

\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>=<\/span>#<\/span>{<\/span>\ud835\udc5b<\/span>\u00a0<\/span>\ud835\udc60<\/span>\ud835\udc62<\/span>\ud835\udc50<\/span>\u210e<\/span>\u00a0<\/span>\ud835\udc61<\/span>\u210e<\/span>\ud835\udc4e<\/span>\ud835\udc61<\/span>\u00a0<\/span>\ud835\udc3e<\/span><\/span>\u2286<\/span><\/span>\ud835\udc37<\/span>\ud835\udc5b<\/span><\/span>}<\/span><\/span>\ud835\udc41<\/span><\/span><\/span><\/span><\/span><\/p>\n

So, our goal is to find these subsets\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>, where\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span><\/span><\/span><\/span>\u00a0is a large number.<\/p>\n

Another objective is to discover association rules. This is the problem of finding objects that are highly correlated. Let\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0be two disjoint subsets\u00a0\ud835\udc34<\/span><\/span>\u2229<\/span><\/span>\ud835\udc35<\/span><\/span>=<\/span><\/span>\u2205<\/span><\/span><\/span><\/span>\u00a0of the products\u00a0{<\/span>1<\/span>\u2026<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span>. Then\u00a0\ud835\udc34<\/span>\u27f9<\/span>\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0can be interpreted in a way that purchasing\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0increases the likelihood of purchasing\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0as well.<\/p>\n

In order to learn all those figures, we need to represent our basket in a different way:<\/p>\n\n\n\n\n\n\n\n\n\n
Basket ID<\/strong><\/td>\nBeer<\/strong><\/td>\nBread<\/strong><\/td>\nButter<\/strong><\/td>\nCheese<\/strong><\/td>\nCola<\/strong><\/td>\nEggs<\/strong><\/td>\nBoys<\/strong><\/td>\nMilk<\/strong><\/td>\nSalami<\/strong><\/td>\nToast<\/strong><\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
2<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
3<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
4<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
5<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
6<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Following our first objective, we\u2019re looking for a subset of those 10 items that co-occur with high probability. This probability could be defined by some threshold, let\u2019s say 49%. In this simple case, we could easily discover that eggs and butter appear in 50% of all baskets, which is beyond the threshold and therefore we\u2019re stating that these two items co-occur with high probability in this dataset.<\/p>\n

Unfortunately, or luckily \ud83d\ude09, real-life situations are much more sophisticated. There is a good probability that we have more than 6 customers and way more items for sale. So how about having\u00a0\ud835\udc41<\/span>\u2248<\/span>10<\/span>8<\/span><\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc3c<\/span>\u2248<\/span>10<\/span>4<\/span><\/span><\/span><\/span><\/span>?<\/p>\n

Using straightforward combinatorics would lead us to the conclusion that a simple brute-force search approach is not going to be possible in this case.<\/p>\n

The first question we could ask ourselves is how many product subsets\u00a0\ud835\udc3e<\/span>\u2286<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span>\u00a0are there at all? Each subset can be represented by a binary indicator vector of length\u00a0\ud835\udc3c<\/span><\/span><\/span><\/span>\u00a0and the total number of possible vectors is\u00a02<\/span>\ud835\udc3c<\/span><\/span><\/span><\/span><\/span>.<\/p>\n

And what if we didn\u2019t check all those possible product combinations, as only very few people (and I think I know them all personally \ud83d\ude0a) will have a basket with all of the grocery store items in it? How about if we only check up to\u00a0\ud835\udc4f<\/span><\/span><\/span><\/span>\u00a0items? Hmm, the number of sets of size\u00a0\ud835\udc4f<\/span><\/span><\/span><\/span>\u00a0picked from\u00a0\ud835\udc3c<\/span><\/span><\/span><\/span>\u00a0items is<\/p>\n

(<\/span><\/span>\ud835\udc3c<\/span>\ud835\udc4f<\/span><\/span><\/span><\/span>)<\/span>=<\/span>\ud835\udc3c<\/span>!<\/span><\/span>\ud835\udc4f<\/span>!<\/span>(<\/span>\ud835\udc3c<\/span><\/span>\u2013<\/span><\/span>\ud835\udc4f<\/span>)<\/span>!<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

which might become a lifetime job with a lot of follow-up tasks for your descendants. If we had only\u00a0\ud835\udc3c<\/span>=<\/span>10<\/span>4<\/span><\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc4f<\/span>=<\/span>5<\/span><\/span><\/span><\/span>\u00a0the total number of possible product combinations would be<\/p>\n

(<\/span><\/span>10<\/span>4<\/span><\/span><\/span><\/span>5<\/span><\/span><\/span><\/span>)<\/span>=<\/span>10<\/span>18<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

As you can imagine, the solution to this tricky problem needs an algorithm that reduces the calculation effort and somehow reduces the count of subsets\u00a0\ud835\udc3e<\/span>\u2286<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span>\u00a0that need to be taken into consideration.<\/p>\n

But first, let us decide which terms need to be calculated. As already mentioned, we\u2019re still looking at all relevant product subsets\u00a0\ud835\udc3e<\/span>\u2286<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span>. And of course, we\u2019re still bearing in mind those disjoint product subsets\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0so that\u00a0\ud835\udc34<\/span>,<\/span>\ud835\udc35<\/span>\u2282<\/span>\ud835\udc3e<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc34<\/span>\u222a<\/span>\ud835\udc35<\/span>=<\/span>\ud835\udc3e<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc34<\/span>\u2229<\/span>\ud835\udc35<\/span>=<\/span>\u2205<\/span><\/span><\/span><\/span>.<\/p>\n

So the first term of an interest is the probability of\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>, which can also be written as the joint probability of subsets\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>.<\/p>\n

\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>,<\/span>\ud835\udc35<\/span>)<\/span><\/span><\/span><\/span><\/p>\n

We call this term the prevalence or\u00a0support<\/strong>\u00a0of the items in\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>. In essence, we\u2019re looking for all subsets of\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0such that their combination in\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0co-occurs often.<\/p>\n

E.g. if\u00a0\ud835\udc3e<\/span>=<\/span>{<\/span>\ud835\udc38<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span>,<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span>,<\/span>\ud835\udc40<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc34<\/span>=<\/span>{<\/span>\ud835\udc38<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc35<\/span>=<\/span>{<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span>,<\/span>\ud835\udc40<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span>}<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>=<\/span>0<\/span>,<\/span>2<\/span><\/span><\/span><\/span>\u00a0then eggs, butter and milk will be purchased together in 20% of all cases (baskets).<\/p>\n

And then we\u2019d like to learn the conditional probability of set\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0given set\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>. In other words, if you know that\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0is in the grocery basket, what is the probability that\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0will also appear in the basket. We call it\u00a0confidence<\/strong>, which will be used as the basis for assumption\u00a0\ud835\udc34<\/span>\u27f9<\/span>\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0(purchasing\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0increases the likelihood of also purchasing\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>).<\/p>\n

\ud835\udc43<\/span>(<\/span>\ud835\udc35<\/span>|<\/span>\ud835\udc34<\/span>)<\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>,<\/span>\ud835\udc35<\/span>)<\/span><\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>)<\/span><\/span><\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span><\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

e.g. if\u00a0\ud835\udc3e<\/span>=<\/span>{<\/span>\ud835\udc38<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span>,<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span>,<\/span>\ud835\udc40<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc34<\/span>=<\/span>{<\/span>\ud835\udc38<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc35<\/span>=<\/span>{<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span>,<\/span>\ud835\udc40<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span>}<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc35<\/span>|<\/span>\ud835\udc34<\/span>)<\/span>=<\/span>0<\/span>,<\/span>65<\/span><\/span><\/span><\/span>\u00a0then eggs were purchased in 65% of all checkouts where butter and milk were also purchased.<\/p>\n

Finally, we want to know how much more certain we are of getting\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0in the basket if\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0is already there, and that compared to the simple prevalence of\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>.<\/p>\n

\ud835\udc3f<\/span>(<\/span>\ud835\udc34<\/span>|<\/span>\ud835\udc35<\/span>)<\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>,<\/span>\ud835\udc35<\/span>)<\/span><\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>)<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc35<\/span>)<\/span><\/span><\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>)<\/span><\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>)<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc35<\/span>)<\/span><\/span><\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span><\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc35<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

This is called the\u00a0lift<\/strong>\u00a0of rule\u00a0\ud835\udc34<\/span>\u27f9<\/span>\ud835\udc35<\/span><\/span><\/span><\/span>\u00a0(purchasing\u00a0\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0increases the likelihood of also purchasing\u00a0\ud835\udc35<\/span><\/span><\/span><\/span>).<\/p>\n

E.g. if\u00a0\ud835\udc3e<\/span>=<\/span>{<\/span>\ud835\udc38<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span>,<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span>,<\/span>\ud835\udc40<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc34<\/span>=<\/span>{<\/span>\ud835\udc38<\/span>\ud835\udc54<\/span>\ud835\udc54<\/span>\ud835\udc60<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc35<\/span>=<\/span>{<\/span>\ud835\udc35<\/span>\ud835\udc62<\/span>\ud835\udc61<\/span>\ud835\udc61<\/span>\ud835\udc52<\/span>\ud835\udc5f<\/span>,<\/span>\ud835\udc40<\/span>\ud835\udc56<\/span>\ud835\udc59<\/span>\ud835\udc58<\/span>}<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc3f<\/span>(<\/span>\ud835\udc34<\/span>|<\/span>\ud835\udc35<\/span>)<\/span>=<\/span>1<\/span>,<\/span>6<\/span><\/span><\/span><\/span>\u00a0then it is 1,6 times more likely that butter and milk will be purchased given that eggs are in the grocery basket.<\/p>\n

Again, remember that we agreed on setting a threshold\u00a0\ud835\udf0f<\/span><\/span><\/span><\/span>\u00a0and that the empirical probability of\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0needs to exceed this threshold. The GUHA principle based on the\u00a0Apriori<\/strong>\u00a0algorithm provides us with the solution to find all subsets\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0without having to search in all\u00a02<\/span>\ud835\udc3c<\/span><\/span><\/span><\/span><\/span>\u00a0product combinations.<\/p>\n

First, we need to set\u00a00<\/span><<\/span>\ud835\udf0f<\/span><<\/span>1<\/span><\/span><\/span><\/span>\u00a0such that only a relatively small fraction of all subsets\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0satisfies\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>><\/span>\ud835\udf0f<\/span><\/span><\/span><\/span>. The Apriori algorithm restricts the number of subsets\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0that need to be checked by comparing their probabilities with the above-mentioned threshold. And of course, if\u00a0\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0satisfies\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>><\/span>\ud835\udf0f<\/span><\/span><\/span><\/span>\u00a0it appears in\u00a0\ud835\udc41<\/span>\u22c5<\/span>\ud835\udf0f<\/span><\/span><\/span><\/span>\u00a0of\u00a0\ud835\udc41<\/span><\/span><\/span><\/span>\u00a0baskets.<\/p>\n

Before we come to the definition of the Apriori algorithm, let me remind you of some basic probability rules that form its foundation:<\/p>\n

If\u00a0\ud835\udc3e<\/span>\u2032<\/span><\/span>=<\/span>\ud835\udc3e<\/span>\u222a<\/span>\ud835\udc34<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc3e<\/span>\u2282<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span>,\u00a0\ud835\udc34<\/span>\u2282<\/span>{<\/span>1<\/span>,<\/span>\u2026<\/span>,<\/span>\ud835\udc3c<\/span>}<\/span><\/span><\/span><\/span>
\nthen\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span><<\/span>\ud835\udf0f<\/span>\u27f9<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>\u2032<\/span><\/span>)<\/span><<\/span>\ud835\udf0f<\/span><\/span><\/span><\/span>
\nbecause\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>\u2032<\/span><\/span>)<\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>,<\/span>\ud835\udc34<\/span>)<\/span>=<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>|<\/span>\ud835\udc3e<\/span>)<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>\u2264<\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span><<\/span>\ud835\udf0f<\/span><\/span><\/span><\/span><\/p>\n

And conversely, if\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>><\/span>\ud835\udf0f<\/span><\/span><\/span><\/span>\u00a0and\u00a0\ud835\udc34<\/span>\u2282<\/span>\ud835\udc3e<\/span><\/span><\/span><\/span>\u00a0then\u00a0\ud835\udc43<\/span>(<\/span>\ud835\udc34<\/span>)<\/span>><\/span>\ud835\udc43<\/span>(<\/span>\ud835\udc3e<\/span>)<\/span>><\/span>\ud835\udf0f<\/span><\/span><\/span><\/span><\/p>\n

The problem can be represented as a lattice diagram:<\/p>\n

 <\/p>\n

\"Lattice<\/p>\n

 <\/p>\n

And here is the simplified version of the Apriori algorithm:<\/p>\n