[MUSIC] Implications are one of the most important tools of formal concept analysis. But when we deal with real data, it just often doesn't work. Chances are that, for every interesting implication, the real data has a counterexample, because real data may contain noise, or, well, because life is complex. So when we work with real data, we switch to so-called association rules. Association rules have been particularly popular in market basket analysis. There, people study supermarket transactions. Each transaction consists of several items, and researchers try to identify items that are commonly bought together. A legendary finding was people who buy diapers with high probability also buy beer. This finding made it possible to identify a special category of shoppers, young fathers. And so some supermarkets now can cater for them, and maybe they want to put diapers and beer close to each other, so that a person buying diapers could see the beer, remember that he likes beer, and take it as well. And so supermarkets will earn more money. Let's define association rules formally. An association rule is just like an implication, a relation between two attribute sets. So we have attribute set A and attribute set B, and we're going to say that A implies B. The first definition we'll need is that of support. So the support of an attribute set A is the number of objects that have all attributes from A, or, in our terms, it's the size of A’. The support of an association rule A —> B… So you can see that we denote association rule in the same way as we denote an implication, A —> B. But now we're going to have two parameters to measure the importance of this rule, A —> B, and also of the validity of this rule. So support measures the importance of A —> B. And the support of A —> B is defined as the support of A union B. It's easy to see that A —> B is a valid implication if and only if the support of A equals the support of A union B, which is the same as the support of the implication A —> B, of the rule, of the association rule, A —> B. So why is it so? Well, if A —> B is a valid implication, then all objects that have all attributes from A also have all attributes from B— so they have attributes from the set A union B. And therefore, the support of A equals the support of A union B and so equals the support of the association rule A —> B. And the reverse is also true. If the support of A equals the support of A union B, it simply means that all objects that have all attributes from A also have all attributes from B, and so A —> B is a valid implication. Well, the idea here is that if the support is large enough, then the association rule is kind of important: it applies to a large number of objects. If the support is low, then it's not that important. Another property of association rules is called confidence. Association rules don't have to be valid implications. It's okay for them to have a few counterexamples. So the confidence of an association rule measures how many counterexamples a particular association rule has. So the confidence of A —> B is defined as the ratio between the support of A union B and the support of A. In other words, we look at how many objects have all attributes from B among those objects that have all attributes from A. Well, this definition makes sense only if the support of A is not 0. We can't divide by 0. So this is true if A' is not empty. And if A' is empty, then we define the confidence of A —> B as 1. So if A' is empty, then A —> B is a valid implication, because it has no counterexamples at all: there's no object that has all attributes of A, and so there cannot be any object that violates this implication. And more generally, A —> B is a valid implication if and only if its confidence equals 1. So this is the relation between implications and association rules. Implications are precisely association rules with confidence equal to 1. [MUSIC] [BLANK AUDIO]