The lecture introduces clustering, contrasting hierarchical clustering with partitioning methods such as k‑means. It defines clustering as grouping objects with shared characteristics and provides everyday examples (animal taxonomy, computer folders). The speaker explains hierarchical clustering’s tree‑like structure, the need for a similarity measure (primarily Euclidean distance, with a nod to Jaccard for ecological data), and various linkage criteria (single, complete, and Ward’s method). A detailed, step‑by‑step manual construction of a hierarchical dendrogram for eight 2‑dimensional points (A‑H) illustrates how distance matrices are updated, the smallest distances are repeatedly merged, and the resulting tree is cut at a chosen height to obtain a partition. The concept of partition quality is formalized using within‑class inertia, between‑class inertia, and total inertia, leading to a quality index (between‑inertia / total‑inertia). The lecture then derives Ward’s method, showing how it minimizes the loss of between‑class inertia when merging clusters, and contrasts it with single‑linkage, highlighting Ward’s resistance to chain effects. The session concludes by previewing later videos on applying hierarchical clustering, combining it with k‑means, handling high‑dimensional or qualitative data, and characterizing cluster members.
Chapters
This week, we're going to look at clustering methods, including hierarchical clustering and a partitioning method called k-means. The course videos for this week get into the following things. After a brief introduction on data of interest for clustering, and the goals of clustering, we're going to have a look at some general principles of clustering, and in particular hierarchical clustering. We'll have questions like: what criteria to use? Which algorithm to use? Then, we'll take a close look at a partitioning method, the well-known k-means algorithm. Following this, we'll get into how we can use hierarchical clustering and k-means at the same time, and how to do clustering with high-dimensional data, and also qualitative data. To finish, we'll consider ways to characterize individuals found in the same classes. Let's begin this video with a few definitions, followed by a first look at hierarchical clustering. What does the word clustering mean to us? Here, it means putting together or building classes, clusters, groups, categories. Classes are sets of individuals or objects which have some common features. Well, traits, characteristics, resemblances from the set of characteristics defining each individual or object. Anyway, the whole idea of clustering should come as no shock to you. You already know plenty of examples. For instance, the animal kingdom is simply a particular hierarchical clustering of species. The hard drive of your computer, organized into folders, subfolders and files is another. Classes, you already know a lot about them too: social classes, job categories, political classes. Pretty much, we are grouping together individuals with shared characteristics. Which brings us to 2 different types of clustering. The first, hierarchical, involves building a tree-like structure to see how the individuals or objects are organized with respect to each other. For obvious reasons, this is called hierarchical clustering. And then there are partitioning-type methods where we simply try to divide, that is partition, all of the individuals or objects into groups where the members of each group have certain similarities to each other. Here is an example of a hierarchical tree, the animal kingdom. Look at how it divides into branches. There are branches for Arthropoda, Annelida, Mollusca, Chordata. Then, for the Chordata, there are 2 branches: vertebrates and invertebrates. For the vertebrates, there are new branches: bony fish, amphibians, reptiles, birds, mammals. Within the mammals, it branches yet again, and so on. And as we go deeper and deeper into the tree, we find more and more similar types of animals in each smaller and smaller branch. Deep into the tree, animals in the same branch become very alike. In contrast, as we move in the other direction, classes or branches join together and, on average, the animals in the bigger class resemble each other a little less. And so on and so on up the tree. Let's now look at the general principles of hierarchical clustering. We are going to see what criteria to use as well as algorithms helpful for building hierarchical trees. We'll also look at how to quantify the quality of a partition and take a closer look at a method for Euclidean data called Ward's method. So what types of data are we going to do hierarchical clustering with? Well, it's the same types of data we had for principal component analysis, That is, data tables with individuals as rows and quantitative variables as columns. Even so, the variables are quantitative. We'll see at the end of the video what to do when we have qualitative ones. The goal of our clustering is to build a tree structure with hierarchical links between individuals or groups of individuals. For example, for the hierarchical tree here on the right, Individuals A and C are very close to each other and also fairly close to individual B. These 3 individuals form a class. Similarly, individuals D, E, F, G, and H are similar to each other, and within this group, F and G are even more similar to each other. This tree-like representation also helps us to find the natural number of classes in a population. For example, here it would make sense to split the set of individuals into 2 classes: ABC and DEFGH. Well then, what is our clustering criteria going to be? To perform clustering, we are going to have to define a similarity measure between individuals. When are 2 individuals close to each other? When are we going to put them in the same class? A standard and natural distance measure that is often used to visualize the data is the Euclidean distance. We have already used this measure in PCA, and we are going to see that, in clustering, on tables with individuals as rows and variables as columns, that it's also a natural measure to use. There are also many other similarity measures that could be used, which are sometimes associated with specific subjects. In ecology, for instance, the Jaccard index is often used. Indeed, there are a huge number of ways to define similarity between individuals. In this course, we are mostly going to focus on the Euclidean distance, which will help us to make a link with principal component methods and representations, which are also Euclidean. So that was the similarity between pairs of individuals. Then, how does similarity work between groups of individuals? In the little drawing on the right, we can see 2 groups of individuals and a first idea for measuring the similarity between the groups: the single linkage. It's the red line in the picture. In this measure, the minimal distance between 2 groups is equal to the smallest distance between one individual of one group and one individual of the other. Another distance measure between 2 groups is the complete linkage, which is the largest distance between an individual of the first group and one of the second. Later in the course, we'll have a look at another similarity measure called the Ward criterion. As you can see, there are many similarity measures possible between individuals and groups of individuals. The choice of similarity measure is going to change the clustering result we get. Therefore, depending on the data, we're going to use certain similarity measures between individuals and others between groups of individuals. Starting from a simple example, we're going to build, by hand, a hierarchical tree in order to understand how the algorithm works. Here we consider 8 points A, B, C, D, E, F, G, and H and their coordinates in 2 dimensions. We can therefore plot these points and visualize the distances between them. To start with, each point represents a class made up of just one individual, itself. That's why each point is surrounded by a little ellipse containing only that point. The first thing to do is then to calculate the distances between the points. Here, we'll use the Euclidean distance. We end up with this distance matrix. For example, between points A and B, we have a distance of 0.5, between A and C a distance of 0.25, and between B and C 0.56, etc. What's the next thing we do? Go and find the smallest distance in this matrix. It turns out to be 0.25, corresponding to the points A and C. We thus start to build our hierarchical tree by regrouping the points A and C. This happens at a height of 0.25, that is, the distance between these 2 points. So now, we have groups of individuals made up of just 1 point each, and 1 group with 2 points, A and C. Next, we have to calculate the distance between each individual and the group A, C. To do so, let's use the minimum distance criterion. For the distance between A, C, and B, for the minimum distance, it's going to be 0.5. That's because the distance between A and B is 0.5, and the distance between C and B is 0.56. So the smallest of these 2 distances is 0.5. We then repeat the same process between the AC group and each individual. This gives us a new distance matrix. Then we look for the smallest distance in this new matrix. It turns out to be the distance between the group AC and the individual B. Therefore, we're going to join together these 2 groups at a height of 0.5 on the tree. We now are left with a group of A, B, C and 5 groups of 1 individual each. We now calculate the distance between the A, B, C group and each of the individuals to get a new distance matrix. In this matrix, we see that the smallest distance is between F and G, so they must be put together to form a new group. These 2 points are joined together At the height of 0.61, we then calculate the new distance matrix, which now contains the group FG. This time, the smallest distance is between D and E equal to one. We join D and E at the height of one. So far, we therefore have groups ABC, DE, FG, and H. Time to calculate the next distance matrix. The smallest distance is between FG and the point H. So we join FG with H at a height of 1.12. So now we have only 3 groups left. In the next round, the smallest distance is between the DE group and the FGH group. We merge them at a height of 1.81. Only 2 groups are left now. And they join together at a height of 4.07. The tree is now finished. Therefore, iteratively, we've managed to build a hierarchical tree by joining together step by step the closest groups. Obviously, building a hierarchical tree is pretty simple here because we have only a few individuals. But as soon as we have more, it becomes harder and harder to build a tree by hand And we soon much switch to doing it with a computer. Once we have constructed a tree, a hierarchical tree, we can do what happens to many real trees in the end: cut it. Here, we are going to cut the tree in order to get classes. By defining a certain height at which to cut through the tree, we end up creating a partition. In the next tree, the cutting height represented by the black line, defines a partition into 4 classes. Therefore, it's clear that defining the cutting height corresponds to defining the number of classes. Clearly, having seen how we built trees, this particular partition is not necessarily optimal. Indeed, building the tree involved hierarchical constraints between individuals and groups of individuals, which is not particularly helpful when it comes to defining partitions. By removing this hierarchical constraint, it's possible to improve the partitioning, as we'll see at the end of this section. So, even if the partition obtained by cutting a hierarchical tree is not necessarily optimal, it's nevertheless often a quite good quality one. So what does it mean to have a good quality partitioning? Does it mean that individuals in the same class are very close to each other? That they have similar features? Of course, a partitioning will also be good if individuals from different classes are far from each other, with few features in common. How can we translate these ideas into mathematics? Well, individuals in the same class are close to each other if the within-class variability is small. That is, inside the class, there is very little variability and the individuals have a strong resemblance to each other. And conversely, individuals from different classes will be far from each other if, from one class to the next, there is great variability. That is, there is a large between-class variability. Overall, we thus want to have a small within-class variability and a large between-class one. So which of these criteria should we focus on? It's always a bit delicate to choose one or the other, but thankfully here they both basically represent the same thing. What do we mean by this? Well, the total inertia, the total variability represented in blue, can be broken down into a within-class variability shown in black plus a between-class variability, shown in red. Therefore, here, Xi is the value taken by the ith individual of the class q for the variable k. X-bar is the mean of the kth variable. X-bar is the mean of k in class q for the individuals in class q. The within inertia, it's the variability inside the class, which corresponds to the sum of the squared differences between the Xi qk and the X bar qk. The between inertia is the sum of the squared differences between the means of each class, X bar qk, and the means of each variable, X bar k. Thus, thanks to Wigan's theorem, we know that the total inertia is equal to the between inertia, plus the within inertia. This kind of reasoning can be done variable by variable, considering the sum over the set of variables, to help understand this total inertia equation equal to between plus within inertia. As a consequence, minimizing the within inertia is equivalent to maximizing the between inertia, because the total inertia is constant. Which means, surprise, that really we have just one criteria in the end. We can either concentrate on minimizing the within inertia or maximizing the between inertia. This all leads us to put forward an index to measure the quality of a partition: the ratio of the between inertia over the total inertia. This ratio gives a value between 0 and 1, and the closer it is to 1, the better the partition is. The between inertia over the total inertia equals 0 when, for all variables k, the x bar q_k are equal to the x bar k. This means that all classes have the same mean for each variable. Well, clearly, if all classes have the same mean, We have a partition which doesn't separate the classes and doesn't help with clustering. If the between inertia over the total inertia equals 1, that means that the within inertia is 0. This means that inside each class, the individuals are identical. This means that we have extremely homogeneous classes, which is ideal for clustering. But be careful, don't over-interpret this criterion. In reality, it also depends on the number of individuals and the number of classes. If we increase the number of classes, it's easier to have homogeneous ones. In the other extreme, if we have a small number of classes, the variability inside each will be larger. We should therefore take into account the number of individuals and number of classes before making strong conclusions based on this criterion. This criterion for the quality of a partition suggests a new way to do hierarchical clustering, which is now known as Ward's method. It works like this: we start from the clustering where each individual is its own class. This means, of course, that inside each class, there is no within-class variability, So the between-class variability must be equal to the total inertia. Thus, in a way, it's the perfect partition. The aim is then to choose 2 classes, A and B, so that their aggregation minimizes the decrease of the between-class inertia. Essentially, the between-class inertia can only decrease when we aggregate 2 classes, and we want to minimize this decrease. Let's have a look at how we write the sum of the inertias of a class A and a class B as a function of the inertia of their aggregation. The inertia of A plus B is equal to the inertia of the aggregation of these two classes minus a certain quantity: M A times M B divided by M A plus M B multiplied by D A. Here, m_A is the number of individuals in the class A, m_B the number in the class B, and d_AB squared the squared distance between the centers of gravity of classes A and B. As we want the inertia of their union to be as close as possible to the inertia of A plus the inertia of B, we need to minimize the second part of the formula. Which contains two things: weights and a squared distance. First, let's look at this term: m a times m b divided by m a plus m b. This term pushes us to group together objects with small weights and avoid what are known as chain effects. Here is a little plot with two classes: blue and red. And hierarchical trees, the one on the left using the minimum distance criterion, the one on the right using Ward's method. We can see that, when the 2 classes are well separated, we get similar trees with both methods, clearly separating the 2 classes. However, with the same 2 classes and some extra points that stretch from one class to the other, The minimal distance criteria is overtaken by a chain effect bringing individuals into the cluster one by one. The consequence of this is that you can no longer see the 2 original classes in the hierarchical tree. With Ward's method, on the other hand, due to this weight in the formula, the red and blue classes remain separated in the hierarchical tree. The second part of the term to be minimized is DAB squared. This is the distance between the barycenters of classes A and B. It makes a lot of sense to group together classes whose centers of gravity are close together. In terms of clustering, it's obvious we end up grouping together classes that are close to each other. So So far, we've seen how hierarchical clustering works. In the next videos, we're going to run it on an example and see how to use it to choose the number of classes and thus a partitioning of the individuals. Later, in the last video, we'll see how to characterize individuals found in the same class. Don't forget to do the quiz to be sure that you've understood all of the things we've shown you so far.
More from Yamossoun
Algorithme de calcule de la racine carrée par dichotomie #dichotomy #squareroot #algorithm