The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

247 ratings

Stanford University

247 ratings

Course 3 of 4 in the Specialization Algorithms

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 2

Kruskal's MST algorithm and applications to clustering; advanced union-find (optional).

- Tim RoughgardenProfessor

Computer Science

So, by now we've spent quite a bit of time talking about the minimum cost spanning tree problem. There's a number of motivations why we do that. the first, it's just a uniquely great problem for the study of greedy algorithms. You can propose a bunch of different greedy algorithms, and quite unusually, it's all of them seem to work. So you get correct greedy algorithms, but it's quite subtle what's driving their correctness. You also get a lot of practice, arguing about graphs, and arguing about exchange arguments, and so on. The second reason, it's been worthwhile spending time on these algorithms. It has given us some more practice with data structures and how to use them to speed up algorithms, namely heaps, to speed up Prim's algorithm, to union-find data structure to speed up Kruskal's algorithm. The third reason that we're talking about them is they have applications in their own rights. That's the subject of this video and the next and we're going to focus on applications to clustering problems. So let me begin by just talking about the goal of clustering informally. And then, I'll let you pin me down to a precise objective function on the next slide. So in a clustering problem, the input is n points that we think of as being embedded in space. And it's actually quite rare that in the underlying problem that we care about is it actually intrinsically geometric? Is it actually intrinsically points in space? Usually, we're representing something we care about. Maybe it's web pages. Maybe it's images. Maybe it's a database as points in space. And given a bunch of objects, we want to cluster them into, in some sense coherent groups. For those of you coming from a machine learning background, you'll often hear this problem referred to as unsupervised learning, meaning the data is unlabeled. We're looking for just patterns and data where the data is not annotated. This obviously is a fairly wishy-washy description of a problem, so let's be a little bit more precise. We're going to assume that part of the input is what we're going to call a similarity measure. Meaning for any two objects, we're going to have a function giving us a number indicating how similar or really rather how dissimilar they are to each other. In keeping with the geometric metaphor, we're going to refer to this function as a distance function. One thing that's cool is we don't need to impose many assumptions on this distance function. The one thing we're going to assume is that it's symmetric, meaning the distance from p to q is the same as the distance from q to p. So what are some examples? Well, if you want to really go with the geometric metaphor, if you're representing these points as in a space RM for some dimension M, you can just use the Euclidean distance or if you prefer some other norm, like say, l1 or l-infinity. In many application domains, there are widely accepted similarity or distance measures. one example would be for sequences, as we discussed in introductory lecture the penalty of the best alignment between two genome fragments. So now that we have this distance function, what would it mean to have coherent groups? Well, things which have small distance from each other which are similar, they should generally be in the same group, and things that are very dissimilar that have large distance between them, you would expect to mostly be in different groups. So how can we evaluate how good a clustering is, how well it's doing with the job of putting nearby points together and dissimilar points in different groups? Well, to be honest there's many ways of approaching and formalizing that problem. The approach we're going to take is an optimization-based approach. We're going to positive and objective function on clusterings and then seek out the clustering that optimizes that objective function. I want to warn you that's not the only way to approach the problem. There are other interesting approaches, but optimization is a natural one. Furthermore, just like in our scheduling application, there's more than one objective function that people study and that is well-motivated. So one very popular objective function would be, say the k-means objective, which I encourage you to look up and read more about. For this lecture, I'm just going to adopt one specific objective function. It's natural enough, but it's by no means the only one or even the primary one. But it'll serve the purpose of studying a natural greedy algorithm related to minimum spanning tree algorithms which is optimal in a precise sense.

So let me develop the terminology needed to state the objective function and the optimization problem precisely. One issue that always comes up in clustering problems is how many clusters are you going to use? So to keep things simple in this video, we're going to assume that part of the input k indicates how many clusters you're supposed to use. So we're going to assume you know a priori how many clusters you want. So in some application domains, this is a totally reasonably assumption. You know, you might know for example that you want exactly two clusters, the k = 2. in some domains you may have you know, good domain knowledge from past experience that you know how many clusters you expect to need that's, all fine and good. Also you know, in practice, if you don't really know what k is supposed to be, you can go ahead and run the algorithm we're going to talk about for a bunch of different values of k and then you symmetric or just eyeball it to figure out which is the best solution.

So the objective function we're going to look at is defined in terms of separated pairs of points. That is points that are assigned to distinct clusters. Now you know, if you have more than one cluster, inevitably there's going to be some pairs of points. Some points are going to be one groups, other points are going to be in the different group. So separated points are inevitable and the most alarming separated points are the ones that are the most similar, the ones that have the smallest distance. If points are separated, we want them to be for apart, so we're particularly concerned with nearby points that are separated. So that's going to be our objective function value, called the spacing of a clustering. It's the distance between the closest together pair of separated points. Now what do we want from the spacing of a clustering? Well, we want all of the separated points to be as far apart as possible. That is, we want the spacing to be big. The bigger the better. So that naturally motivates the formal problem statement. You're given as inputs, the, distance measure. You're told the distance between each pair of points. You're also told the desired number of clusters. Amongst all ways of clustering the points into k clusters, find the clustering which makes the spacing as big as possible.

So let's develop a greedy algorithm that seeks to make the spacing as big as possible. And to facilitate the discussion, I'll use an example point set with just six black points up here in the upper right part of the slide. Now, the good idea behind this greedy algorithm is to not worry about the constraints that, at the end of the day, we can only output k different clusters. We're actually going to be infeasible, we'll have too many clusters throughout the algorithm. Only at the conclusion of the algorithm will we be down to k clusters, which will be our final infeasible solution. So that frees us up to initialize the procedure where the degenerate solution, where each point is in its own cluster.

So in our example point set, we have these six pink isolated clusters. In general, you're going to have n clusters and we've got to get down to k. Now, let's remember what the spacing objective is. In the spacing objective, you go over all of the separated pairs of points. So for this degenerate solution, it's all pairs of points. And you look at the most alarming separated pair, that is those, that are the, the closest to each other. So the spacing is the distance between the closest pair of separated points. Now, in a greedy algorithm, you want to increase your objective function as much as possible. But actually, things are pretty cut and dried in this scenario. Suppose I give you a clustering and you want to make the spacing bigger, the only way you can do that is by taking the currently closest pair of separated points and making them not separated any more. That is putting them in the same cluster. So, it's in some sense obvious what you want to do to make the objective function go up at all. You gotta look at the pair of points that is defining the objective, the closest pair of separated points, and you have to fuse them. You have to fuse their clusters so that they're no longer separated.

In this example, it looks to me like the closest pair of points, which of course are separated, is this pair in the upper right. So, if we want to make the spacing bigger, then we fuse them into a common cluster. [SOUND] So we started with six clusters. Now, we're down to five. So now we reevaluate the spacing again of this new clustering. We ask, what is the closest pair of separated points? So that would seem to me to be this pair in the bottom right. [SOUND] And again, the only way we can increase the spacing by merging clustering is to merge these two isolated clusters into one. Now, we do it again. We say, which pair of points determines the current spacing, which the currently separated pair of points that are nearest to each other? That to me would look like this pair that's on the rightmost part of the picture. The only way to merge two clusters and make the spacing actually go up is to merge the clusters containing the pairs of points determining the current spacing. So in this case, two different clusters with two points, each would collapse into a single cluster with four points. Let's assume that we wanted three clusters, clusters anyways, which is where we are. So at this point, the greedy algorithm is going to halt. So let me now spell out the pseudocode of the greedy algorithm more generally, but it's exactly what you'd expect given the discussion so far. All right. So, I'd like you to stare at this pseudocode for ten seconds or however long you need and try to relate this to an algorithm that we've seen in the course. In particular, an algorithm that we've seen quite recently. I hope it reminds you strongly of an algorithm we've already covered. Specifically, I hope you see a strong resemblance between this greedy algorithm and Kruskal's algorithm for computing a minimum cost spanning tree. Indeed, we can think of this greedy clustering algorithm as being exactly the same as Kruskal's minimum cost spanning tree algorithm except aborted early. Stopped when there's k components remaining, that is before the final k - 1 edge additions. So, just to make sure the correspondence is clear. What is the graph? What are the edges? What are the edge costs? Well, the objects in the clustering problem, that is the points. Those correspond to vertices in a graph. The other part of the input of the clustering problem are distances, which are given for every pair of points. So those play the role that edge costs were playing in the minimum spanning tree problem. Since we have a distance or an edge cost for every single pair of points, we can think of the edge set in the clustering problem as being the complete graph because we have an edge cost or a distance for every single pair. So this type of agglomerative clustering has a name. This idea of fusing components one at a time using MST-lik criterion. It's called single-link clustering. So a single n clustering is a good idea. If you work at all with clustering problems or unsupervised learning problems, it definitely should be a tool in your toolbox. we're going to justify its existence in one particular way in the next video, when we show that it does indeed maximize the spacing over all possible k clusterings. But even if you don't care about the spacing objective function per se, you want to be familiar with single-link clustering. It has many other nice properties as well.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.