1 00:00:00,270 --> 00:00:02,440 Welcome back to Mining of Massive Datasets. 2 00:00:02,440 --> 00:00:05,220 We continue our discussion of clustering by looking at 3 00:00:05,220 --> 00:00:06,730 hierarchical clustering methods. 4 00:00:09,750 --> 00:00:13,620 To refresh our memory in hierarchical clustering, you can either bottom or 5 00:00:13,620 --> 00:00:14,720 top down. 6 00:00:14,720 --> 00:00:17,280 In bottom up methods, each point, 7 00:00:17,280 --> 00:00:20,300 each data point is initially in a cluster of its own. 8 00:00:20,300 --> 00:00:23,670 At each step we find the two closest clusters and 9 00:00:23,670 --> 00:00:25,210 combine them into a single cluster. 10 00:00:27,020 --> 00:00:31,760 In divisive methods, all the data points are in a single cluster to begin with, 11 00:00:31,760 --> 00:00:34,850 and we recursively split the cluster as we go along. 12 00:00:34,850 --> 00:00:39,230 In this lecture, we're going to focus on the agglomerative or 13 00:00:39,230 --> 00:00:43,180 the bottom-down approach, where we start with each data point as is 14 00:00:43,180 --> 00:00:45,480 its own cluster and then combined clusters. 15 00:00:46,730 --> 00:00:50,730 The ideas in the lecture can be easily adapted to divisive methods as well. 16 00:00:53,290 --> 00:00:57,370 The key operation in hierarchical agglomerative clustering is to 17 00:00:57,370 --> 00:01:01,230 repeatedly combine the two nearest clusters into a larger cluster. 18 00:01:03,820 --> 00:01:06,960 There are three key questions that we've to answer in order to 19 00:01:06,960 --> 00:01:08,650 build a hierarchical clustering algorithm. 20 00:01:10,090 --> 00:01:11,670 Those three important questions are the following. 21 00:01:12,980 --> 00:01:16,410 How do you represent a cluster of more than one data point? 22 00:01:17,950 --> 00:01:20,530 We need, we need a representation of a cluster, so 23 00:01:20,530 --> 00:01:23,430 that we can figure out which clusters are close to each other. 24 00:01:23,430 --> 00:01:26,840 And that brings us to the second question, which is how do you determine 25 00:01:26,840 --> 00:01:30,840 the nearness of clusters, so that we can combine the two nearest clusters? 26 00:01:32,070 --> 00:01:36,290 The third question is, as we, as we keep going along combining clusters, 27 00:01:36,290 --> 00:01:39,240 when do you decide to stop and produce a final output? 28 00:01:40,810 --> 00:01:43,437 So, we look at each of these three questions in turn. 29 00:01:47,290 --> 00:01:50,740 Let's start with a simpler case of a Euclidean space. 30 00:01:50,740 --> 00:01:53,470 In Euclidean space, we can always average two points, 31 00:01:53,470 --> 00:01:56,620 and the average is also a point in the Euclidean space. 32 00:01:59,090 --> 00:02:01,810 This gives us a simple answer to the question of how do 33 00:02:01,810 --> 00:02:03,329 you represent a cluster of many points? 34 00:02:04,340 --> 00:02:06,810 We can represent the cluster by its centroid, 35 00:02:06,810 --> 00:02:08,720 which is the average of its points. 36 00:02:12,707 --> 00:02:16,760 And to determine the nearness of clusters, we just measure the cluster distances by 37 00:02:16,760 --> 00:02:19,910 measuring the distances between the centroids of the clusters. 38 00:02:22,030 --> 00:02:27,550 An example will make this clear, here we have six points in a Euclidean space. 39 00:02:27,550 --> 00:02:33,680 These the, the these O's represent data points in a Euclidean space, 40 00:02:33,680 --> 00:02:37,882 and we're going to apply an agglomerative clustering methods. 41 00:02:37,882 --> 00:02:41,560 initially, let's say we determine that these points, 1, 2 and 42 00:02:41,560 --> 00:02:44,009 2, 1, are the closest points. 43 00:02:45,920 --> 00:02:48,290 We combine them into a single cluster. 44 00:02:49,590 --> 00:02:53,660 And now we're going to represent this cluster by its centroid. 45 00:02:53,660 --> 00:02:56,710 To compute its centroid, we have to compute the average of the two points, 46 00:02:56,710 --> 00:02:59,160 which is just the average along every dimension. 47 00:02:59,160 --> 00:03:04,664 So, the average of the points 1, 2 and 2, 1 is the point 1.5, 48 00:03:04,664 --> 00:03:09,610 1.5 which is the centroid of this newly created cluster. 49 00:03:09,610 --> 00:03:14,910 Now we have, five clusters, remember we started with each data point as its 50 00:03:14,910 --> 00:03:18,260 own cluster, and we have combined two of the data points into the single cluster. 51 00:03:18,260 --> 00:03:20,410 So now, we have five clusters. 52 00:03:20,410 --> 00:03:23,520 Now we need to find, the nearest pair of clusters. 53 00:03:23,520 --> 00:03:25,240 And as it turns out, 54 00:03:25,240 --> 00:03:30,827 the nearest pair of clusters is the pair of points 4,1 and 5,0. 55 00:03:30,827 --> 00:03:35,970 And once you've created this cluster, we then represent it by its centroid. 56 00:03:35,970 --> 00:03:40,825 Now, the centroid of this cluster is the point 4.5, 0.5. 57 00:03:40,825 --> 00:03:46,769 Now, the 4.5 is obtained just by averaging the x coordinates of the two points and 58 00:03:46,769 --> 00:03:52,780 the 0.5 is obtained by averaging the y coordinates which are 1 and 0. 59 00:03:52,780 --> 00:03:56,350 So now, we have four clusters, okay? 60 00:03:56,350 --> 00:03:58,380 And as we go along merging clusters, 61 00:03:58,380 --> 00:04:02,730 we create this this artifact called a dendrogram. 62 00:04:02,730 --> 00:04:07,670 And the dendrogram shows how we merge data points and clusters as we go along. 63 00:04:07,670 --> 00:04:12,820 In the first step, we merge the, the two blue data points, and in the second 64 00:04:12,820 --> 00:04:17,390 step we merge the two green data points, and that's what the dendrogram indicates. 65 00:04:17,390 --> 00:04:22,750 Now, in the next step, we determine that the two closest 66 00:04:22,750 --> 00:04:28,180 clusters are the cluster with centroid 0, 0 and cluster with centroid 1.5, 1.5. 67 00:04:28,180 --> 00:04:33,015 And we and we can measure we do this just by measuring the distance between (0, 68 00:04:33,015 --> 00:04:34,580 0) and (1.5, 1.5), and 69 00:04:34,580 --> 00:04:38,120 finding that to be the shortest distance between any pair of clusters. 70 00:04:39,620 --> 00:04:45,857 Once we do that, we can combine the three points, (1, 2), (2, 1) and (0, 0), 71 00:04:45,857 --> 00:04:50,915 into a single cluster and we can represent it by its centroid, which is 1,1. 72 00:04:50,915 --> 00:04:55,341 Now, to determine the, that the centroid of this combined cluster, 73 00:04:55,341 --> 00:04:59,310 we have to average all three points, 1,2, 2,1 and 0,0. 74 00:04:59,310 --> 00:05:04,884 And the average in the x you know, in the x axis is 0 Plus 1 plus 75 00:05:04,884 --> 00:05:10,870 2 which is 3 divided by 3 gives you 1, and similarly along the way axis. 76 00:05:10,870 --> 00:05:15,365 So now we have three clusters, one cluster centroid 1,1, 77 00:05:15,365 --> 00:05:20,599 another with centroid 5,3, and the third was centroid 4.5, 0.5. 78 00:05:20,599 --> 00:05:26,248 And when we measure the inter cluster distances between these three centroids, 79 00:05:26,248 --> 00:05:31,674 we determine that the the two closest are 5, 3 and 4.5, 0.5. 80 00:05:31,674 --> 00:05:38,292 So, we can combine those, and that new cluster has centroid 4.7, 1.3. 81 00:05:38,292 --> 00:05:42,487 Now, we are reduced to two clusters, and we have no choice at this point but 82 00:05:42,487 --> 00:05:44,620 to merge these two clusters. 83 00:05:44,620 --> 00:05:49,020 So, either we can stop at this point and, and output these two clusters or 84 00:05:49,020 --> 00:05:53,310 we can decide to merge them further and create a single large cluster. 85 00:05:54,940 --> 00:05:58,558 And now, a single cluster doesn't make a lot of sense because we, 86 00:05:58,558 --> 00:06:03,550 our goal was to end up with you know group the points to many different clusters. 87 00:06:03,550 --> 00:06:07,210 But on the other hand, even if we do merge these two clusters and create 88 00:06:07,210 --> 00:06:11,250 a single large cluster, the dendrogram actually shows the order in which these 89 00:06:11,250 --> 00:06:15,970 merges the merges happen, and it contains very useful information in many cases. 90 00:06:15,970 --> 00:06:21,380 For example, if the data point's actually represent you know, 91 00:06:21,380 --> 00:06:25,264 of species of of, of different animals,uh, 92 00:06:25,264 --> 00:06:29,260 then the dendrogram represents the family tree of how these species evolved. 93 00:06:32,000 --> 00:06:36,790 Now, there was the easier Euclidean case of hierarchical agglomerative clustering. 94 00:06:36,790 --> 00:06:38,920 But what if you have a non-Euclidean space? 95 00:06:38,920 --> 00:06:41,230 The problem with a non-Euclidean space is that, 96 00:06:41,230 --> 00:06:44,500 it's not possible to average points and create a centroid. 97 00:06:44,500 --> 00:06:48,450 The centroid may not be a, a valid point in a non-euclidean space. 98 00:06:50,330 --> 00:06:54,190 So, the only points or locations we can talk about in a non-euclidean 99 00:06:54,190 --> 00:06:56,040 space are the points themselves. 100 00:06:56,040 --> 00:07:00,360 There is no concept of average, and therefore we cannot continue to using the, 101 00:07:00,360 --> 00:07:02,200 the centroid to represent a cluster. 102 00:07:04,750 --> 00:07:10,040 So instead, we have to use a different, concept, called a clustroid. 103 00:07:10,040 --> 00:07:14,740 And a clustroid is a datapoint that's closest to the other point in the cluster. 104 00:07:18,330 --> 00:07:21,300 So, once we use clustroids instead of centroids, and 105 00:07:21,300 --> 00:07:25,290 we look at an example of clustroids in the next slide, we can determine the nearness 106 00:07:25,290 --> 00:07:29,520 of clusters by treating the clustroid exactly as if it were the centroid. 107 00:07:29,520 --> 00:07:31,558 And we can measure the distance between two clusters, 108 00:07:31,558 --> 00:07:33,951 we are measuring the distance between the clustroids instead of 109 00:07:33,951 --> 00:07:35,870 measuring the distance between their centroids. 110 00:07:37,495 --> 00:07:41,200 Here's a cluster on three data points in a Euclidean space. 111 00:07:45,520 --> 00:07:49,290 Now, the centroid, which we saw how to compute, 112 00:07:49,290 --> 00:07:52,820 is just the average of all these data points in the cluster. 113 00:07:52,820 --> 00:07:55,860 The x here marks the centroid of the three data points shown. 114 00:07:57,180 --> 00:08:00,220 Notice that the x is actually a data point that 115 00:08:00,220 --> 00:08:04,170 was not among the original three data points in, in the cluster. 116 00:08:04,170 --> 00:08:07,750 It's an artificial point that we created to represent the, the cluster. 117 00:08:09,520 --> 00:08:12,450 Now, the problem in non-Euclidean spaces is that we cannot create this 118 00:08:12,450 --> 00:08:13,730 artificial point. 119 00:08:13,730 --> 00:08:16,790 And therefore, we just have to pick one of the three points as 120 00:08:16,790 --> 00:08:20,690 the clustroid to represent the cluster instead of using x, the centroid. 121 00:08:22,090 --> 00:08:25,114 So, in this case, for example, we might pick the, 122 00:08:25,114 --> 00:08:28,327 the points shown at the clustroid to represent the cluster, 123 00:08:28,327 --> 00:08:31,666 because intuitively, it's in the middle of the cluster, and 124 00:08:31,666 --> 00:08:35,895 it's close, and it sort of seems to be equidistant from the other points. 125 00:08:35,895 --> 00:08:39,518 And therefore we've picked the, the highlighted point as the clustroid. 126 00:08:39,518 --> 00:08:43,190 Notice that the clustroid is actually an existing datapoint. 127 00:08:43,190 --> 00:08:45,007 It's not the centroid, but for 128 00:08:45,007 --> 00:08:49,524 all practical purposes we can treat it as a centroid in clustering algorithms. 129 00:08:56,165 --> 00:08:59,654 Now we've defined the Clustroid to be the point that is closest to 130 00:08:59,654 --> 00:09:01,700 the other points within the cluster. 131 00:09:01,700 --> 00:09:05,100 Now how exactly do we define this notion of closest point? 132 00:09:08,190 --> 00:09:11,430 It turns out that there are multiple ways of defining the notion of closest when we 133 00:09:11,430 --> 00:09:12,710 are picking the Clustroids. 134 00:09:12,710 --> 00:09:15,720 For example, we might want to pick the point that is at 135 00:09:15,720 --> 00:09:19,120 the smallest maximum distance to other points, by which we mean, 136 00:09:19,120 --> 00:09:22,900 we measure the distance between every pair of points, and 137 00:09:22,900 --> 00:09:27,730 then we find a point such that the maximum distance between that point and 138 00:09:27,730 --> 00:09:29,950 any other point in the cluster is as small as possible. 139 00:09:32,130 --> 00:09:36,380 Instead, we might look at the point with the smallest average distance to 140 00:09:36,380 --> 00:09:40,160 the other points, or we might look at the point with the smallest sum of 141 00:09:40,160 --> 00:09:43,100 squares distance to other points and pick that as a clustroid. 142 00:09:44,290 --> 00:09:46,106 Depending on the application, one or 143 00:09:46,106 --> 00:09:50,093 the other of these notions of clustroid might make more sense than the others. 144 00:09:52,806 --> 00:09:57,464 So far we've addressed the, the first two of three key questions of clustering, 145 00:09:57,464 --> 00:10:00,700 the first being, how do you represent a cluster? 146 00:10:00,700 --> 00:10:02,630 And the second being, how do you represent, 147 00:10:02,630 --> 00:10:05,770 how do you determine the distance between clusters? 148 00:10:05,770 --> 00:10:08,800 We now turn to point three, or the termination condition. 149 00:10:08,800 --> 00:10:11,570 How do you know when to stop clustering and produce an output? 150 00:10:13,500 --> 00:10:16,490 The first approach is to pick a number k up front, and 151 00:10:16,490 --> 00:10:18,900 stop when we have k clusters. 152 00:10:18,900 --> 00:10:21,860 Now, this approach makes sense when we know up front that the data falls 153 00:10:21,860 --> 00:10:24,070 naturally into k classes. 154 00:10:24,070 --> 00:10:28,270 For example, the data might be about, galaxies and 155 00:10:28,270 --> 00:10:32,020 quasars, and we know that there are naturally two classes, galaxy and 156 00:10:32,020 --> 00:10:34,970 quasar, and once we have two clusters, we stop. 157 00:10:38,136 --> 00:10:38,817 The second approach, 158 00:10:38,817 --> 00:10:43,080 when we don't know the number k up front, is to keep clustering and, and 159 00:10:43,080 --> 00:10:47,475 stop when the next merge of clusters would create a bad cluster. 160 00:10:47,475 --> 00:10:51,670 Now,how do you define a bad cluster? 161 00:10:52,910 --> 00:10:58,480 We define a notion called cohesion, which measures the goodness of a cluster and 162 00:10:58,480 --> 00:11:02,490 when the cohesion value falls below a certain level, you've created a bad 163 00:11:02,490 --> 00:11:06,370 cluster and we stop when the next merge would create a bad cluster. 164 00:11:08,560 --> 00:11:11,320 How, how exactly do we define this notion of cohesion? 165 00:11:11,320 --> 00:11:16,340 There are multiple approaches to defining cohesion. 166 00:11:18,430 --> 00:11:23,020 The first approach to cohesion is to use the diameter of the merged cluster. 167 00:11:23,020 --> 00:11:27,410 Now, the diameter of the merged cluster is the maximum distance between any pair of 168 00:11:27,410 --> 00:11:28,150 point in the cluster. 169 00:11:29,290 --> 00:11:32,334 We might decide to stop clustering when the diameter of 170 00:11:32,334 --> 00:11:35,719 a newly merged cluster exceeds a certain preset threshold. 171 00:11:40,074 --> 00:11:42,960 The second approach is to use radius. 172 00:11:42,960 --> 00:11:47,660 The radius is the maximum distance of a point from the centroid or the clustroid. 173 00:11:48,890 --> 00:11:51,340 And we might decide to stop clustering, 174 00:11:51,340 --> 00:11:55,410 then we would produce a cluster of greater than a certain threshold radius. 175 00:11:59,110 --> 00:12:03,142 The third approach is to use a density based model. 176 00:12:03,142 --> 00:12:07,260 Now a density of a cluster is the number of points per unit volume of the cluster. 177 00:12:08,630 --> 00:12:11,650 One way of defining density is to simply divide the number of 178 00:12:11,650 --> 00:12:14,670 points in the cluster by the diameter or the radius of the cluster. 179 00:12:16,435 --> 00:12:20,150 We might instead divide the number of points by a power of area such as 180 00:12:20,150 --> 00:12:21,340 a square or a cube. 181 00:12:22,730 --> 00:12:30,340 And at a point where the next merge would create a cluster with a density lower than 182 00:12:30,340 --> 00:12:34,310 a certain piece of threshold, we would stop merging, and produce a final output. 183 00:12:36,080 --> 00:12:40,705 Notice that in each case, we set a predefined threshold either for diameter, 184 00:12:40,705 --> 00:12:45,553 radius, or density, and stop when the next merge would violate that threshold. 185 00:12:48,572 --> 00:12:52,736 We turn now to implementation of hierarchical agglomerative clustering. 186 00:12:56,023 --> 00:12:58,527 At each step in hierarchical clustering, 187 00:12:58,527 --> 00:13:02,860 we need to find the closest pair of clusters and merge them. 188 00:13:02,860 --> 00:13:05,060 In order to find the closest pair of clusters, 189 00:13:05,060 --> 00:13:08,930 we need to compute pairwise distances between all pairs of clusters. 190 00:13:08,930 --> 00:13:12,290 Since we start with each point in its own cluster initially, 191 00:13:12,290 --> 00:13:15,150 there are order n clusters, where n is the number of points, and 192 00:13:15,150 --> 00:13:18,330 therefore computing pairwise distances takes time order n squared. 193 00:13:19,530 --> 00:13:23,950 Over all we might have to do order n steps of merging, and therefore the overall 194 00:13:23,950 --> 00:13:27,940 complexity of hierarchical agglomerative clustering is order n cubed. 195 00:13:27,940 --> 00:13:33,644 [SOUND] Now if you do a careful implementation using priority queues, 196 00:13:33,644 --> 00:13:38,181 you can reduce the complexity to order n squared log n. 197 00:13:38,181 --> 00:13:40,679 N-squared log in though is still too much for 198 00:13:40,679 --> 00:13:44,110 really big data sets that don't fit in memory. 199 00:13:44,110 --> 00:13:47,720 When n is of the order of millions, order n squared log in, 200 00:13:47,720 --> 00:13:49,790 can get out of hand pretty soon. 201 00:13:49,790 --> 00:13:52,780 That's why hierarchical clustering is not commonly used for 202 00:13:52,780 --> 00:13:55,250 really big data sets that don't fit in memory. 203 00:13:55,250 --> 00:13:58,860 It's primarily used for small data sets that do fit in memory. 204 00:13:59,860 --> 00:14:02,250 When we have very large disk-resident data sets, 205 00:14:02,250 --> 00:14:05,680 we use other methods of clustering, which we turn to next.