[MUSIC] Iceberg lattices are good when we want to see only the most general concepts in our concept lattice. But this is not always what we want. Sometimes we want to see other interesting concepts that don't cover that many objects, but that are still meaningful in our domain. In this case, other criteria for concept selection are more useful. One of them, and one of the most popular ones, is concept stability. Well, there are at least two kinds of stability. Let's talk about the intensional stability first. The intensional is the stability of a concept intent. The idea here is that you look at a concept (A, B). So A is the extent, B is the intent. And you want to know how strongly this concept intent depends on particular objects of the concept extent. So we know that A' equals B. So the intersection of all object intents from A gives us B. But what if our context doesn't contain all objects from A? What if some of them are noisy? So let's suppose that our context contains only objects from the subset C of A. Are we going to get B as the concept intent in this situation? This is what the intensional stability measures. So formally, the intensional stability is the ratio between the number of subsets of A that generate B, so such subsets C for which C' equals B, and the number of all subsets of A, which is 2 to the size of A. And it can be shown that this is precisely the probability of preserving the intent after removing an arbitrary number of objects from the context assuming that every object subset has equal chances to be removed from the context. So each object subset has equal chances to be noisy and therefore to be removed from the context. And we can define extensional stability similarly. Extensional stability shows how strongly the concept extent depends on particular attributes of the concept intent. Let's look at a few examples of intensional stability. So once you have the concept lattice of your context, you can compute the concept stability, the intensional stability of every concept, and keep only those that have the highest stability index. It's up to you how many such concepts you want to keep. So here, we kept only 12 most stable concepts from the Zoo context. And you can see that some of these concepts are the same that you can see in the iceberg lattice. So we have the concept of all animals that lay eggs, and it's a large concept, it covers something like 58% of all objects. But some of the concepts are not that large, are not that general. For example, we have a concept of animals who have a backbone, who have a tail, and who lay eggs. If we look at the extent of this concept, we'll see that it's populated by all birds, all fish, and most reptiles. Well, does it make sense to group them together in one concept from the biological point of view? Maybe yes, maybe no. But it makes sense if we want to see the conceptual structure of our data. So this is one way to use stability. We keep only the most stable concepts. But that's not the only way. It's also possible to compute stability for every concept and then look at how the stability of each concept relates to the stability of its upper and lower neighbors. So if a concept is at least as stable as all its upper and lower neighbors, then it makes sense. Otherwise, it may be noisy, and we remove it. So let's say that a concept is locally stable if its intensional stability is at least as high as that of all its upper and lower neighbors. If we apply this criterium to our Zoo data set, then we'll get these eight concepts. Well, in this case, these concepts are mostly incomparable. First of all, the bottom concept is always locally stable, because the intensional stability of the bottom concept is always 1. It's always 1, and therefore it's always at least as high of the stability of all its upper neighbors, and it has no lower neighbors at all. This also means that if we look at concepts just above the bottom concept, they're not going to be locally stable, because their stability will be less than 1, and the bottom concept is their lower neighbor. So we're not going to see very specific concepts, concepts in the bottom of the diagram, except for the very bottom one. And something similar is happening in the upper part of the lattice. Well, the top concept is not guaranteed to have stability equal to 1, but it often has stability very close to 1 and its stability is often higher than that of its lower neighbors. So, if we choose locally stable concepts, then we're likely to get concepts from the middle of the diagram, which are kind of interesting. Hopefully interesting. So let's look at what we get here. So one of the concepts is the concept of all animals who have a backbone, who breathe, who are catsize, which means that their size is at least that of an average cat, those that have hair, that produce milk, and so on. It turns out that this concept roughly corresponds to mammals. So most mammals are in the extent of this concept, and there is nobody else there. So if we want to have a general overview of our data, then this is the concept of mammals. Now, this is the concept of fish. Almost all fish that we have in our context have properties "aquatic", "backbone", "eggs" and so on. And in this concept, we have only two objects, a seal and a sea lion. And sea lion from the layman's perspective is the same as a seal. So, it makes sense so that we have them grouped together here. Okay, so how do we compute intensional stability? Well, we can do this individually for every formal concept using the definition. But that's going to take a lot of time, because, to determine the concept stability, we need to consider all subsets of the concept extent, and this may take exponential time and we may have exponentially many concepts in our lattice. So, there are various ways to make this a little bit more efficient, but still it is computationally hard to compute the stability. So, here is one approach. This approach works when we have already computed the entire lattice and also its covering graph. Then we can use this covering graph to compute the stability of every concept. To determine the stability index of the concept (A, B), we compute the number of subsets E of A that generate the intersection B, that is, those for which E' = B, and we store it in s[(A, B)]. The stability index of (A, B) is simply the number of such subsets divided by the number of all subsets of A, that is, by 2 to the size of A. Once computed, the stability of (A, B) is stored in sigma[(A, B)], which is the output of the algorithm. The algorithm traverses the covering graph from the bottom concept upwards. A concept is processed only after the stability indices of all its subconcepts have been computed; n[(A, B)] is used to keep track of concepts that become eligible for processing. In the beginning of algorithm, n[(A, B)] is initialized to the number of lower neighbors of (A, B). Once the stability index is computed for some lower neighbor of (A, B), we decrement n[(A, B)]. By the time n[(A, B)] reaches zero, we have computed the stability indices for all lower neighbors of (A, B), and, consequently, for all subconcepts of (A, B). Then it is possible to determine the stability index of (A, B). Initially, s[(A, B)] is set to the number of all subsets of A, that is, 2 to the size of A. Before processing (A, B), we process all subconcepts (C, D) of (A, B) and decrement s[(A, B)] by the number of subsets of C generating the intersection D. By doing so, we actually subtract from 2 to the size of A the number of subsets of A which do not generate B. Indeed, every subset of A generates either B or the intent of a subconcept of (A, B). Thus the value of s[(A, B)] eventually becomes equal to the number of subsets of A generating B. And so our algorithm works correctly. [SOUND]