The video introduces the K‑means partitioning algorithm as a direct alternative to hierarchical clustering. Starting with a 2‑D example, it walks through the steps of initialization (random centers), assignment of points to the nearest center, recomputing centers of gravity, and iterating until convergence. The presenter highlights two main drawbacks—requiring a pre‑specified number of clusters and sensitivity to the initial centers—and suggests remedies such as multiple random restarts and using a hierarchical cut as a smarter initialization. The discussion then expands to practical extensions: (1) applying PCA to reduce dimensionality before clustering; (2) a two‑stage strategy for massive datasets where K‑means creates many small clusters whose centroids are later clustered hierarchically; (3) handling qualitative variables via Multiple Correspondence Analysis (MCA) or specialized distance measures like the Jaccard index. Finally, the benefits of combining principal component methods with clustering are emphasized—noise reduction, more stable classifications, and the ability to visualise both hierarchical trees and class assignments on the same factor plane. The video concludes by previewing the next lesson on describing and characterising the discovered groups.
Chapters
We have seen in the previous video how to do hierarchical clustering with a tree-like structure. Now, we're going to look at a direct partitioning method, not requiring a hierarchical tree. This partitioning method is called K-means. We are going to introduce K-means using a 2D example. The basic K-means algorithm requires as input the number of classes Q, that we want to have at the end. Here, we're going to take Q equals 3, and therefore partition the data into 3 classes. To begin, we choose 3 points, or centers, at random: Moscow, Berlin, and London. This is the first step of the algorithm, called initialization. Next, we associate each individual, each point, with the closest of the 3 centers. Here, all the red individuals are closer to Berlin than to Moscow or London. All those in black are closest to Moscow, and all those in green closest to London. Therefore, we have now divided the individuals into 3 classes, but it's not all over. Next, we calculate the center of gravity of each of the 3 classes. Here they are. They are no longer located on top of individuals. They are just points in the plane. Maybe you can see where we are heading with this. We are going to iterate now, starting from the beginning again, with these 3 points. Again, we associate each individual with the closest of the 3 points. We calculate the center of gravity of each of the 3 new classes. And we iterate again and again. As time goes on, the centers of gravity move and move again. Again, we calculate the centers of gravity, and this time we see that the classes haven't changed and the centers of gravity have stopped moving. This means that the algorithm has converged. We therefore have found our 3 classes. That's how k-means works. It's a very fast algorithm. It can be run with lots of individuals. But it has a couple of drawbacks. The first is that you have to know the number of classes before you begin. And the second is that the final partition depends on the places you put the centers in the initialization step. Which were chosen randomly. For different initializations, the partitions we get at the end can be quite different. To overcome this problem, one thing we can do is to run the algorithm many times and keep the best partition, that is, the one with the smallest within-group inertia. So far, we have seen how to do a hierarchical clustering and how to partition the individuals. Here, we are going to look at a few more issues related to clustering, notably how to make a partition robust, how to do partitioning with high-dimensional data, how to do it with qualitative data, and last but not, not least, what's the interest in combining principal component method and clustering. Sometimes, we can try to reinforce the partition obtained by hierarchical clustering. We have seen that the partition obtained by cutting a hierarchical tree isn't optimal because it can be cut anywhere, giving a whole hierarchy of individuals and groups of individuals. Well, we can reinforce the partition found in this way by using k-means. What we do is start from the partition obtained by a certain cut of the hierarchical tree and use this as as the initialization step in the k-means algorithm and then iterate until convergence. This can only improve the partitioning because, by construction, at each step the k-means criteria decreases. On the other hand, the inconvenience that appears is that we lose the hierarchical links between individuals. Certain individuals are going to change groups with respect to the original tree-based partition and the hierarchical structure will disappear. As we saw earlier in the example, constructing a hierarchical tree involves calculating, at each step, lots of distances between individuals and groups of individuals. For high-dimensional data, this algorithm takes too long and doesn't work very well. So how are we supposed to deal with high-dimensional data? Well, if there are lots of variables, we could start by doing a PCA and only keeping the first dimension, or the first few. As we know, PCA concentrates the information in the first principal components. Then we can move on and do clustering on a data table with the individuals as rows and the first few principal components as columns. Pretty much, this means transforming the data to a smaller and much more manageable size. How about if we have a huge number of individuals? Here, the clustering algorithm takes too long in practice, and we struggle to build a useful hierarchical tree. One possible strategy is to work in steps. First, we build a raw partition using k-means, leading to 100 classes or so. This step, due to the large number of classes, ensures that For the most part, individuals close to each other end up in the same class. Then, we can simply extract the set of centers of the classes, and use these to represent each class, and build a hierarchical classifier, treating them as individuals. We'll also use the number of individuals in each class as a factor in the tree's construction. If we think about it visually, The tree that we obtain should resemble the upper part of the tree we would have had if we'd started with all the individuals. We lose, in a way, the bottom of the tree. Perhaps this isn't such a bad thing if we have a million of individuals. The bottom of the tree would be quite hard to look at anyway, and not of great use, as we are usually most interested in commenting on the top. Here is an example with 300 individuals. On the left, it's the tree built using all of them, and on the right, the one built after first partitioning them into 50 classes. We see that the tops of the trees are very alike, so our interpretation of them will be similar. Up till now, we have only treated the case where the variables are quantitative. What can we do if we have qualitative variables? Well, there are 2 well-known strategies. In the first, we can transform them into quantitative variables using multiple correspondence analysis. MCA can help us move from a table of qualitative variables to one of coordinates of individuals over several dimensions. These coordinates are indeed quantitative variables. We can keep the first few MCA principal components, or even all of them. Once we have rebuilt our table with individuals as rows and quantitative variables as columns, we can run one of our clustering algorithms as before. A second strategy consists of using distance measures specifically adapted to qualitative data. Many such indices exist: similarity measures, dissimilarity measures, and so on, such as, for example, the Jaccard index. These types of measures can help us to create a distance matrix or dissimilarity matrix between individuals. Then, using this matrix, we can construct a hierarchical tree as before. We've just seen how, if we have qualitative data, MCA can give us quantitative principal components which we can directly used to do clustering with the same algorithms. But these principal component methods have other advantages too. We'd especially like to highlight this general strategy of using principal component methods followed by clustering. So why do you think this might be a good thing? Well, principal component methods, whether it be PCA or correspondence analysis or multiple correspondence analysis, tends to concentrate the useful information in the first principal components, leaving just noise in the remaining ones, random noise. Doing principal component method before clustering is therefore a way to try and remove noise before doing clustering. We get rid of the random, that is the noise, before classifying, which gives in practice a more stable classifier. When we say more stable, We mean in the sense that adding or removing a few individuals doesn't perturb the class structure too much. Another positive when using principal component methods along with clustering is the possibility to be able to represent the hierarchical tree as well as the classes on the first principal components. If we manage to put the points, the hierarchical tree, and the individuals, colored in terms of their class, on the same factor plane, we get 3 types of information for the price of one. In particular, we get a continuous vision of how things are due to the principal component method, and a discontinuous one using hierarchical clustering, which also gives us information about what is happening in the 3rd and 4th dimensions, for example. In our example, the individuals are perfectly represented in the 1st plane, so their proximities in this plane are the same as their proximities in the higher-dimensional space. But, in general, it's possible that individuals can seem close in the first plane but actually be far apart in subsequent dimensions, which the hierarchical clustering is able to show in this kind of plot. In other examples, it may be that 3 or 4 dimensions are needed to interpret the PCA well. Overall, this kind of plot is very useful bringing together class information and more subtle information from the factor plane. That's all for this video where we have seen how to construct classes in the data. In the next video, we'll take a closer look at how to describe and characterize groups of individuals found in the same class.
