1 00:00:00,190 --> 00:00:02,440 Welcome back to Mining of Massive Datasets. 2 00:00:02,440 --> 00:00:05,300 Be looking at K-means algorithms for clustering. 3 00:00:05,300 --> 00:00:09,600 And we've sort of seen that the K-means algorithm is, you know, produces good 4 00:00:09,600 --> 00:00:14,960 clusters and it's linear for each scan or each round of the K-means clustering. 5 00:00:14,960 --> 00:00:15,960 But it can take a really, 6 00:00:15,960 --> 00:00:19,520 large number of rounds to convert the K-means clustering algorithm. 7 00:00:19,520 --> 00:00:22,955 So, our question is: Can we come up with an algorithm that can do something like 8 00:00:22,955 --> 00:00:26,380 k-Means clustering but in one pass over the data, if you have a really, 9 00:00:26,380 --> 00:00:28,930 really large dataset that doesn't fit in memory? 10 00:00:28,930 --> 00:00:31,700 The answer to that question is the Bradley-Fayyad-Reina or 11 00:00:31,700 --> 00:00:34,039 BFR algorithm, which you're going to cover in this segment. 12 00:00:36,280 --> 00:00:38,600 BFR is a variant of K-means. 13 00:00:38,600 --> 00:00:42,490 And is sort of optimized for really large data set that are actually disclicids. 14 00:00:42,490 --> 00:00:45,540 The data site is so large that it doesn't fit in memory. 15 00:00:45,540 --> 00:00:49,350 And so you really want to just can the dataset once in disk and 16 00:00:49,350 --> 00:00:50,200 come up with the clustering. 17 00:00:51,490 --> 00:00:55,930 However, to accomplish this the BFR algorithm makes a very strong assumption. 18 00:00:55,930 --> 00:00:58,730 It assumes, not only that we have a Euclidian space, 19 00:00:58,730 --> 00:01:02,780 which is an assumption that all K-means algorithms make, but it also assumes that 20 00:01:02,780 --> 00:01:07,820 each cluster is normally distributed around a centroid in Euclidean space. 21 00:01:07,820 --> 00:01:08,780 Let's see what this means. 22 00:01:09,830 --> 00:01:11,990 Let's start with a refresher on the normal distribution. 23 00:01:13,530 --> 00:01:19,200 Here's a variable, x, and here its, here is its frequency distribution. 24 00:01:19,200 --> 00:01:21,290 Assuming that x is normally distributed. 25 00:01:21,290 --> 00:01:25,930 Let's say x has, mean 0 and standard deviation sigma. 26 00:01:25,930 --> 00:01:31,450 Then, if you look at the frequency distribution, it's it's apparent that, 27 00:01:31,450 --> 00:01:34,660 you know, we, we sort of end up in this bell-shaped curve. 28 00:01:34,660 --> 00:01:41,520 and, most, observations of x are going to cluster very closely around the mean zero. 29 00:01:41,520 --> 00:01:49,461 In fact about 68% of the values which is you know here 0.34 plus 0.34 so that's 68% 30 00:01:49,461 --> 00:01:55,560 of observations are going to lie within the one standard deviation of the mean. 31 00:01:55,560 --> 00:01:58,700 Plus or minus one sigma from the mean. 32 00:01:58,700 --> 00:01:59,700 Right? 33 00:01:59,700 --> 00:02:06,680 and, about 95% of the values are going to lie, 34 00:02:06,680 --> 00:02:10,970 at a distance of at most 2 sigma from the mean, plus or 35 00:02:10,970 --> 00:02:13,120 minus 2 sigma from, from the mean. 36 00:02:13,120 --> 00:02:16,360 And about 99% of observations are going to be at 37 00:02:16,360 --> 00:02:18,540 a distance of about 3 sigma from the mean. 38 00:02:19,890 --> 00:02:22,860 All right so, this is just a refresher. 39 00:02:22,860 --> 00:02:24,370 It should be evident to, 40 00:02:24,370 --> 00:02:27,960 most of you should recall this from your elementary statistics classes. 41 00:02:29,010 --> 00:02:32,570 Now the, the nice thing, if, 42 00:02:32,570 --> 00:02:39,870 if you assume tha,t the, that the data is normally distributed in each dimension. 43 00:02:39,870 --> 00:02:44,210 Let's say X here is a dimension, and, the mean of x is zero, 44 00:02:44,210 --> 00:02:50,880 which means that the centroid in x dimension for a given cluster is at zero. 45 00:02:50,880 --> 00:02:57,130 Then, we, we sort of know that, about 68% of the points, 46 00:02:57,130 --> 00:03:03,560 lie within one standard deviation, off the centroid, along x dimension. 47 00:03:03,560 --> 00:03:05,900 And we can say the same thing about each dimension, and 48 00:03:05,900 --> 00:03:08,660 we assume that all the dimensions are independent of each other. 49 00:03:08,660 --> 00:03:12,860 So in general, we can quantify the likelihood given, you know, given a point, 50 00:03:12,860 --> 00:03:16,660 given the point, belongs to a cluster, we can quantify the likelihood of 51 00:03:16,660 --> 00:03:20,910 finding that point at a certain distance from the centroid of the cluster. 52 00:03:20,910 --> 00:03:25,440 And this is the property that we are going to use, in the BFR algorithm as, you know, 53 00:03:25,440 --> 00:03:26,800 as it'll become apparent later on. 54 00:03:28,570 --> 00:03:31,060 Now recall that, although in this case, you know, 55 00:03:31,060 --> 00:03:34,310 I've shown, single standard deviation sigma. 56 00:03:34,310 --> 00:03:37,390 We don't make the assumption that a standard deviation is actually the same 57 00:03:37,390 --> 00:03:38,760 along every dimension. 58 00:03:38,760 --> 00:03:43,390 Each dimension actually has its own mean, and its own standard deviation. 59 00:03:43,390 --> 00:03:49,470 Now the implication of the, of this idea that each dimension has its own mean and 60 00:03:49,470 --> 00:03:55,270 its own standard deviation is that the, the, the clusters actually look like, 61 00:03:55,270 --> 00:03:58,580 ellipsis, that are aligned along the axis. 62 00:03:58,580 --> 00:04:04,860 For example, here's here's a cluster the pink cluster, and the, 63 00:04:04,860 --> 00:04:10,780 notice that it's, it's off a flat ellipse that's aligned along the, the x axis. 64 00:04:10,780 --> 00:04:15,030 Which means that the, the standard deviation is higher along the x 65 00:04:15,030 --> 00:04:18,460 axis than along the y axis for this particular cluster. 66 00:04:18,460 --> 00:04:22,750 Whereas the green cluster here, has, you know, 67 00:04:22,750 --> 00:04:25,190 is more elongated along the y dimension. 68 00:04:25,190 --> 00:04:29,230 Which means that its standard deviation along the y dimension is more than its 69 00:04:29,230 --> 00:04:30,940 standard deviation along the x dimension. 70 00:04:32,320 --> 00:04:35,190 Whereas the blue cluster is like, looks more like a circle, 71 00:04:35,190 --> 00:04:38,889 which means that it has roughly the same standard deviation along both dimensions. 72 00:04:40,130 --> 00:04:42,430 Let's start with an overview of the BFR algorithm. 73 00:04:42,430 --> 00:04:45,680 Remember that the data, set that we're looking at is very, very large. 74 00:04:45,680 --> 00:04:47,319 So and it's actually on disc. 75 00:04:47,319 --> 00:04:51,170 Now the data is so large, that it doesn't actually fit. 76 00:04:51,170 --> 00:04:53,660 All of it doesn't really fit into memory, right? 77 00:04:53,660 --> 00:04:59,290 So what we're going to do is we're going to page the data one chunk of the data in, 78 00:04:59,290 --> 00:05:01,550 you know, at, at a time into memory. 79 00:05:01,550 --> 00:05:02,700 Right? 80 00:05:02,700 --> 00:05:07,700 When we bring a chunk of data in, and, and read it, we also, 81 00:05:07,700 --> 00:05:11,050 at the same time, in memory, we're going to maintain, 82 00:05:11,050 --> 00:05:14,370 metadata about all the clusters that we've created thus far. 83 00:05:15,530 --> 00:05:16,280 Right? We're going to 84 00:05:16,280 --> 00:05:18,340 bring a chunk of the data into memory. 85 00:05:18,340 --> 00:05:21,330 We're going to update the metadata about the clusters. 86 00:05:21,330 --> 00:05:23,050 And then we're going to throw that chunk of data away. 87 00:05:23,050 --> 00:05:25,740 And then we're going to bring the next chunk of data into memory. 88 00:05:26,880 --> 00:05:30,060 And we're going to continue with this process until we've gone through all, 89 00:05:30,060 --> 00:05:34,120 all the chunks of data, at which point we've ended up with our final clustering. 90 00:05:34,120 --> 00:05:34,780 Okay? This is the, 91 00:05:34,780 --> 00:05:37,330 this is the high-level overview of the, BFR algorithm. 92 00:05:39,950 --> 00:05:44,550 To summarize, the points are read from disk, one main memory full at a time. 93 00:05:44,550 --> 00:05:45,540 Right? 94 00:05:45,540 --> 00:05:50,150 And most points from previous memory loads are actually summarized by 95 00:05:50,150 --> 00:05:53,910 simple statistics, since we don't have space to store all those points, 96 00:05:53,910 --> 00:05:56,490 we summarize all those points with simple statistics. 97 00:05:56,490 --> 00:05:59,070 And we'll see what these statistics are, going forward. 98 00:06:00,920 --> 00:06:06,050 To begin with we're going to, when we load the first set of data, or the first 99 00:06:06,050 --> 00:06:11,940 chunk of data into memory, we're going to select, the initial K centroids for, 100 00:06:11,940 --> 00:06:16,580 the k-Means algorithm from that chunk of data using some sensible approach. 101 00:06:16,580 --> 00:06:20,210 For example you might use one of the techniques that we saw in the, 102 00:06:20,210 --> 00:06:23,160 in the k-Means lecture, prior to this. 103 00:06:24,310 --> 00:06:28,370 Now as we go through, we, we'll see that points fall into three, 104 00:06:28,370 --> 00:06:32,700 three different categories that we, that we need, that we need to keep track of. 105 00:06:32,700 --> 00:06:36,070 The first category of points is called a discard set. 106 00:06:36,070 --> 00:06:39,650 And the discard set of points are points that are close enough 107 00:06:39,650 --> 00:06:42,100 to the centroid of an existing cluster. 108 00:06:42,100 --> 00:06:47,050 So if a point is close to a centroid of an existing cluster, then we just update the, 109 00:06:47,050 --> 00:06:49,910 metadata, the statistics of that cluster to account for 110 00:06:49,910 --> 00:06:52,100 the fact that we've added the new point to the cluster. 111 00:06:52,100 --> 00:06:53,220 And then we throw the point away. 112 00:06:53,220 --> 00:06:56,120 That's why this set of point is called the discard set. 113 00:06:56,120 --> 00:07:00,820 Because we discard points that are close enough to the centroid of a cluster. 114 00:07:00,820 --> 00:07:02,409 So we don't need to keep them around any longer. 115 00:07:03,690 --> 00:07:08,600 The, the second set of points is called a compression set, or the CS. 116 00:07:08,600 --> 00:07:12,040 Now, these are points that are close to each other, but 117 00:07:12,040 --> 00:07:15,460 are not close to any existing, centroid. 118 00:07:15,460 --> 00:07:16,380 Right? 119 00:07:16,380 --> 00:07:20,890 So these points form a separate mini cluster of their own, but 120 00:07:20,890 --> 00:07:24,880 they don't really naturally merge with any of our existing K-clusters. 121 00:07:24,880 --> 00:07:29,370 So what we do with these points, is that we compress them into mini clusters and 122 00:07:29,370 --> 00:07:30,490 summarize them. 123 00:07:30,490 --> 00:07:33,320 But we don't assign them to any of the existing clusters. 124 00:07:33,320 --> 00:07:35,460 and, and the, the resulting, you know, 125 00:07:35,460 --> 00:07:39,460 com, summarized sets are what we call the compression set, or the CS. 126 00:07:39,460 --> 00:07:40,820 And we'll see more about this later. 127 00:07:42,370 --> 00:07:46,090 Finally, we have the, the third set, which is called the retained set. 128 00:07:46,090 --> 00:07:49,060 And a retained set contains points that are kind of isolated. 129 00:07:49,060 --> 00:07:53,790 They don't fit into any of the existing clusters, and they're not close, 130 00:07:53,790 --> 00:07:55,800 close together to any of the other points so 131 00:07:55,800 --> 00:08:00,280 they can be, you know, made by any compressed set. 132 00:08:00,280 --> 00:08:02,926 They're kind of outliers that are on their own. 133 00:08:02,926 --> 00:08:06,180 And these are called the retained set or RS. 134 00:08:06,180 --> 00:08:08,120 These are isolated points. 135 00:08:08,120 --> 00:08:12,970 and, you know, we might eventually, fu, in the future, as we load in more points, 136 00:08:12,970 --> 00:08:18,390 we might find that they get close to, you know, a, a compression set. 137 00:08:18,390 --> 00:08:22,790 But at the moment they are too far away to be assigned to, and, and 138 00:08:22,790 --> 00:08:25,950 they just kept, isolated, as part of the retained set of points. 139 00:08:25,950 --> 00:08:27,390 So the retained set of points. 140 00:08:27,390 --> 00:08:31,050 Is the only set of points that we actually have to keep track of in memory. 141 00:08:31,050 --> 00:08:33,070 Both the discard set and the compression set, 142 00:08:33,070 --> 00:08:38,340 we can throw away the actual points and only keep metadata points in memory. 143 00:08:38,340 --> 00:08:42,260 So here's a picture that will help you visualize these three, class of points. 144 00:08:42,260 --> 00:08:45,840 Remember, there are three, sets that we need to keep track of. 145 00:08:45,840 --> 00:08:49,240 The discard set, the compression set and the retained set. 146 00:08:51,010 --> 00:08:56,320 So heres, you know a cluster, one of the K-clusters that, that we're maintaining, 147 00:08:57,380 --> 00:09:03,720 and, here is it's centroid, and any point that's close enough to, to the centroid of 148 00:09:03,720 --> 00:09:08,400 this cluster is assigned to this cluster and becomes part of the discard set. 149 00:09:08,400 --> 00:09:10,089 We don't need to keep track of the point anymore. 150 00:09:11,660 --> 00:09:16,670 Now here are a bunch of, you know, smaller, mini-clusters. 151 00:09:16,670 --> 00:09:18,380 Now these are compressed sets. 152 00:09:18,380 --> 00:09:23,470 These, the points in, in these mini-clusters are close to each other, so 153 00:09:23,470 --> 00:09:27,560 we could actually cluster them into these mini-clusters, but these, but 154 00:09:27,560 --> 00:09:30,060 they're too far away from any of the existing clusters, so 155 00:09:30,060 --> 00:09:35,840 I can't really merge the, points in this mini cluster with the, with 156 00:09:35,840 --> 00:09:42,190 this cluster here, but I can keep track of them independently as a mini cluster. 157 00:09:42,190 --> 00:09:45,760 So the points that are in these mini clusters are said to be in 158 00:09:45,760 --> 00:09:47,320 the compressed set. 159 00:09:47,320 --> 00:09:50,750 So for the points, we just need to keep track of the mini cluster. 160 00:09:50,750 --> 00:09:53,630 We don't need to keep track of the, each individual point. 161 00:09:53,630 --> 00:09:56,120 And so these points are in the compressed set. 162 00:09:56,120 --> 00:10:01,350 And finally, we have isolated points that are not close to any mini-cluster or 163 00:10:01,350 --> 00:10:02,860 they are not close to each other. 164 00:10:02,860 --> 00:10:05,240 They are not close to any of the existing cluster, so 165 00:10:05,240 --> 00:10:08,670 we just keep track of them independently as individual points and 166 00:10:08,670 --> 00:10:13,000 these are the points that are the retained set, or RS. 167 00:10:13,000 --> 00:10:17,160 So let's look at how we summarize, sets of points that are in the, 168 00:10:17,160 --> 00:10:18,120 in the discard set. 169 00:10:19,400 --> 00:10:22,790 Remember the discard set is, is particular this discard set, 170 00:10:24,120 --> 00:10:27,330 pertains to one of the K-clusters that we're keeping track of. 171 00:10:27,330 --> 00:10:30,780 So each of the K-clusters, we, we keep track of the number of 172 00:10:30,780 --> 00:10:33,980 points in the cluster, let's, let's say, let's call that N. 173 00:10:35,300 --> 00:10:39,030 we, keep, track of vector SUM, and 174 00:10:39,030 --> 00:10:43,600 SUM is just the, sum of the points that are in the cluster. 175 00:10:43,600 --> 00:10:45,930 So there are N points in the cluster. 176 00:10:45,930 --> 00:10:50,720 And we, sum them, dimension wise. 177 00:10:50,720 --> 00:10:55,900 And the SUM vector is just the sum of all the points that are in the cluster. 178 00:10:55,900 --> 00:10:59,430 So the ith component of the SUM vector is the sum of the coordinates of 179 00:10:59,430 --> 00:11:01,940 the points along the ith dimension, and so on. 180 00:11:04,010 --> 00:11:07,650 And similarly, the sum square vector is just the sum of 181 00:11:07,650 --> 00:11:09,800 the squares of the coordinates. 182 00:11:09,800 --> 00:11:14,730 So the ith component of the, sum square vector is the sum of the squares of 183 00:11:14,730 --> 00:11:18,450 the coordinates of all the end-points along the ith dimension. 184 00:11:19,650 --> 00:11:22,830 In a moment, it'll be apparent why we maintain the sum and 185 00:11:22,830 --> 00:11:24,240 the sum square vectors. 186 00:11:24,240 --> 00:11:26,840 It should be fairly apparent that we need to keep track of the number of 187 00:11:26,840 --> 00:11:27,730 points in a cluster. 188 00:11:29,720 --> 00:11:33,350 Notice that if d is the number of dimensions, we can 189 00:11:33,350 --> 00:11:38,590 represent a cluster by 2d plus 1 values, independent of the size of the cluster. 190 00:11:38,590 --> 00:11:41,009 The cluster can have 10 points or 10 million points. 191 00:11:42,040 --> 00:11:46,180 The number of values that we use to represent that cluster is two d plus one, 192 00:11:46,180 --> 00:11:47,980 where d is the number of dimensions. 193 00:11:47,980 --> 00:11:48,720 Why is this? 194 00:11:48,720 --> 00:11:54,930 Well we need one, one point or one value, 195 00:11:54,930 --> 00:12:01,020 for to, to, to store n, the number of, the number of points in the cluster. 196 00:12:01,020 --> 00:12:03,320 The sum is a d dimensional vector, 197 00:12:03,320 --> 00:12:06,230 and the sum squares are on the D dimensional vector. 198 00:12:06,230 --> 00:12:10,689 So, overall, we need two d + 1 values to represent the cluster, and 199 00:12:10,689 --> 00:12:15,340 this is independent on the number of points in the cluster. 200 00:12:15,340 --> 00:12:20,190 Now, the centroid of the cluster is just the average along each dimension. 201 00:12:20,190 --> 00:12:23,120 And the, the, it's very simple to calculate the centroid. 202 00:12:23,120 --> 00:12:25,060 We just have to go to the SUM vector and 203 00:12:25,060 --> 00:12:29,080 divide each component of the SUM vector by N and the total number of points, and 204 00:12:29,080 --> 00:12:33,320 then we end up with a vector that's just the centroid of the cluster. 205 00:12:33,320 --> 00:12:37,090 We can also calculate the variance of the, of the, 206 00:12:37,090 --> 00:12:38,649 of the cluster along any dimension. 207 00:12:39,670 --> 00:12:40,710 The variance of the, 208 00:12:40,710 --> 00:12:44,850 cluster along the ith dimension is just given by this formula here. 209 00:12:44,850 --> 00:12:49,440 You take the, SUMSQ values along the ith dimension, divide them by N, and 210 00:12:49,440 --> 00:12:54,480 then subtract the square of the SUM values along the ith dimension divided by N. 211 00:12:54,480 --> 00:12:59,560 This is, from elementary statistics, the, the, the, the formula for 212 00:12:59,560 --> 00:13:01,799 standard, the variance, from elementary statistics. 213 00:13:03,140 --> 00:13:07,110 And the, standard deviation along the dimension i, 214 00:13:07,110 --> 00:13:10,400 it, it's the square root of the variance along the dimension i. 215 00:13:10,400 --> 00:13:15,940 All right, so we just take the, the variance along dimension i, and you take 216 00:13:15,940 --> 00:13:22,540 the square root of that, and you get the standard deviation along, dimension i. 217 00:13:22,540 --> 00:13:26,250 So now it should be apparent, why we maintain the, the sum and 218 00:13:26,250 --> 00:13:30,000 the sum square of vectors, for, for each cluster. 219 00:13:30,000 --> 00:13:33,250 Because using them and the number of values in the cluster, 220 00:13:33,250 --> 00:13:37,860 it's quite easy to compute both the, the centroid of the cluster. 221 00:13:37,860 --> 00:13:39,980 And the standard deviation along every dimension. 222 00:13:41,560 --> 00:13:43,763 Next we're going to look at how we actually do the clustering. 223 00:13:43,763 --> 00:13:47,820 We're going to] page in one chunk of, 224 00:13:48,850 --> 00:13:52,530 data points at a time and they're going to update, the cluster metadata. 225 00:13:52,530 --> 00:13:55,490 And we just saw the metadata that we're going to, that it keep track of for 226 00:13:55,490 --> 00:13:59,440 each cluster, the N, the SUM and the SUM squared, values. 227 00:13:59,440 --> 00:14:02,550 So once we have a chunk of points in a, in memory, 228 00:14:02,550 --> 00:14:07,470 we're going to find the points that are sufficiently close to a cluster centroid. 229 00:14:07,470 --> 00:14:09,710 And we'll see what sufficiently close means in a moment, but 230 00:14:09,710 --> 00:14:14,130 let's just assume that, that for now we know that given a point that it's, 231 00:14:14,130 --> 00:14:19,151 it's sufficiently close to a cluster centroid for one of the, the K-clusters, 232 00:14:19,151 --> 00:14:23,460 which means, that it is that, which means at that point it is in the discard set. 233 00:14:23,460 --> 00:14:26,340 They're going to merge the point of the cluster and throw the point away. 234 00:14:28,010 --> 00:14:29,780 And here is how we do that. 235 00:14:29,780 --> 00:14:34,490 We, we add the point to the cluster and then we add the point to the cluster we 236 00:14:34,490 --> 00:14:39,000 have to update the N, the sum, and the sum squared for that cluster. 237 00:14:39,000 --> 00:14:43,860 To our just end, we just are incremented by one to indicate that we've 238 00:14:43,860 --> 00:14:46,829 added a value to the, added a point to the cluster. 239 00:14:47,940 --> 00:14:52,360 To income and sum, we just have to add the point to the sum value for the cluster. 240 00:14:52,360 --> 00:14:56,340 And to update sum square, we just have re, to compute the square of the, the, 241 00:14:56,340 --> 00:14:59,770 the values, of the, of that point along each dimension. 242 00:14:59,770 --> 00:15:01,760 And add that to the sum square vector for the cluster. 243 00:15:03,160 --> 00:15:06,910 Now we see the advantage of the NSUM and SUMSQS presentation. 244 00:15:06,910 --> 00:15:11,100 It's very easy to incrementally add value, you know, add points to a cluster and 245 00:15:11,100 --> 00:15:14,560 increment for a cluster without doing complex computations. 246 00:15:15,910 --> 00:15:18,792 Now the points that are actually close to, 247 00:15:18,792 --> 00:15:22,413 the centroid of a cluster we've added, to a cluster. 248 00:15:22,413 --> 00:15:27,360 However, the points that are not close to any cluster, we know, 249 00:15:27,360 --> 00:15:29,260 we know how to deal with those points. 250 00:15:29,260 --> 00:15:31,030 What we're going to do is to take these points, 251 00:15:31,030 --> 00:15:35,980 the points that are in this memory load of points, but that are not, you know, 252 00:15:35,980 --> 00:15:39,130 that we have not, added to the discard set. 253 00:15:39,130 --> 00:15:40,830 And you're going to take those points, and 254 00:15:40,830 --> 00:15:45,840 we're going to add in the old, retained set, the, the, those points from before. 255 00:15:45,840 --> 00:15:47,760 That they've not done anything with. 256 00:15:47,760 --> 00:15:50,900 And you're going to take these new points and the old reading set, and 257 00:15:50,900 --> 00:15:55,440 we are going to use some main memory clustering algorithm to cluster them all. 258 00:15:55,440 --> 00:15:59,010 You would use either Kamian's clustering, or we could use hierarchical clustering. 259 00:15:59,010 --> 00:16:00,360 It doesn't matter. 260 00:16:00,360 --> 00:16:03,810 We use any main memory clustering algorithm and recluster these points. 261 00:16:03,810 --> 00:16:08,170 Now, once we do that clustering, the clusters that, that come all, 262 00:16:08,170 --> 00:16:10,610 which we'll call, we'll call these the mini clusters. 263 00:16:10,610 --> 00:16:11,970 They go into the compress set. 264 00:16:13,030 --> 00:16:18,390 And the outlying points, that don't, fall into any cluster in this, 265 00:16:18,390 --> 00:16:20,230 according to this main memory algorithm. 266 00:16:20,230 --> 00:16:22,310 Go into the new, retained set. 267 00:16:23,740 --> 00:16:29,280 Now we have, now we've added a whole bunch of mini-clusters into the compressed set. 268 00:16:30,320 --> 00:16:35,190 And it might happen that two of the new, mini clusters, you know, 269 00:16:35,190 --> 00:16:38,320 one of the new mini-clusters that we, we're adding to the compressed set is 270 00:16:38,320 --> 00:16:44,230 actually very close to one of the existing mini-clusters so we might want to merge, 271 00:16:44,230 --> 00:16:47,570 these, these mini-clusters in, in, in the compressed set. 272 00:16:47,570 --> 00:16:53,090 and, so that's, we will see in a moment, what metric we might use 273 00:16:53,090 --> 00:16:57,380 to determine that, mini-clusters are close enough and, and, and need to be merged. 274 00:16:58,820 --> 00:17:01,460 Right? So we might consider doing that. 275 00:17:01,460 --> 00:17:05,140 and, and if this is the last round, You know, 276 00:17:05,140 --> 00:17:08,020 if this is not the last round, we just drop at this point. 277 00:17:08,020 --> 00:17:11,980 And we just read in the next chunk of data, data points into memory. 278 00:17:11,980 --> 00:17:16,920 But if this is the last round, then we take each, mini-cluster, or 279 00:17:16,920 --> 00:17:19,520 each compressed set in the CS. 280 00:17:19,520 --> 00:17:22,770 And we merge it to its closest cluster centroid. 281 00:17:23,800 --> 00:17:26,130 And we take each point in the retained set, or 282 00:17:26,130 --> 00:17:30,330 the RS, and we, we assign it to, to its nearest centroid. 283 00:17:30,330 --> 00:17:31,750 And that's the end of our clustering. 284 00:17:33,270 --> 00:17:36,460 If this is not the last round, we just keep the compressed set and 285 00:17:36,460 --> 00:17:37,820 the retained set as it is. 286 00:17:37,820 --> 00:17:40,210 And we read in the next chunk of data points, and 287 00:17:40,210 --> 00:17:41,420 we repeat the whole process again. 288 00:17:43,970 --> 00:17:47,850 So the end of, the algorithm, we have gone through the, 289 00:17:47,850 --> 00:17:49,775 the entire data set exactly once. 290 00:17:49,775 --> 00:17:53,300 We page the entire data set to memory exactly once, and we, 291 00:17:53,300 --> 00:17:55,055 we've produced K-clusters. 292 00:17:59,450 --> 00:18:02,450 And there are two questions that, 293 00:18:02,450 --> 00:18:05,260 we left unanswered during the discussion of the algorithm. 294 00:18:06,280 --> 00:18:09,250 The first question is, how do we decide if a point is 295 00:18:09,250 --> 00:18:12,970 close enough to a cluster that we will add that point to the cluster? 296 00:18:12,970 --> 00:18:17,810 We handled a little bit about this, during our discussion of the algorithm, and now 297 00:18:17,810 --> 00:18:22,630 we're going to look at, a way to determine if a point is close enough to a cluster 298 00:18:22,630 --> 00:18:26,000 that we will add it to the cluster and make it part of the discard set. 299 00:18:26,000 --> 00:18:28,320 The second question, which we left unanswered, 300 00:18:28,320 --> 00:18:32,540 is how do we decide whether two mini-clusters in the compressed set 301 00:18:32,540 --> 00:18:36,130 are close enough that they deserve to be combined into one mini-cluster, or 302 00:18:36,130 --> 00:18:40,090 whether we should just leave them as separate, mini-clusters. 303 00:18:40,090 --> 00:18:41,159 Let's look at that next. 304 00:18:43,030 --> 00:18:49,220 Let's start with the first question which is how do we decide whether a point that, 305 00:18:49,220 --> 00:18:54,260 that we is close enough to one of the cluster centroids that we 306 00:18:54,260 --> 00:18:55,870 decide to add that point to the cluster? 307 00:18:59,470 --> 00:19:03,670 The key, concept here is something called the Mahalanobis distance. 308 00:19:03,670 --> 00:19:06,860 And the Mahalanobis distance, quantifies the, 309 00:19:06,860 --> 00:19:10,650 likelihood of a point belonging, to, a centroid. 310 00:19:12,450 --> 00:19:15,750 Let's, and the Mahalanobis distance, 311 00:19:15,750 --> 00:19:20,870 depends very, crucially on our assumption about the points being 312 00:19:20,870 --> 00:19:23,530 normally distributed about the centroid along each dimension. 313 00:19:27,260 --> 00:19:29,930 Let's say, cluster C has, 314 00:19:29,930 --> 00:19:34,480 centroids, C one through C d remember there are d dimensions. 315 00:19:34,480 --> 00:19:40,250 And the value C one through C d represent the, the mean along 316 00:19:40,250 --> 00:19:45,340 each of the d dimensions so the centroid of the cluster is C one through C d. 317 00:19:45,340 --> 00:19:50,280 And, let's say the standard dimen, dimensions, along those dimensions, along, 318 00:19:50,280 --> 00:19:54,190 standard deviations along those dimensions are sigma 1 through sigma d. 319 00:19:56,870 --> 00:20:00,700 And let's say we have a point, x1 through xd. 320 00:20:00,700 --> 00:20:06,580 Now, what we need to determine is if this point P is close enough to the cluster C, 321 00:20:06,580 --> 00:20:09,720 so that we can add the point P to the cluster C, 322 00:20:09,720 --> 00:20:13,070 or is it too far away to be considered part of the cluster C? 323 00:20:13,070 --> 00:20:20,890 We're going to define, the normalized distance of a point, along 324 00:20:20,890 --> 00:20:27,240 dimension i from the centroid to be yi, which is xi minus ci divided by sigma i. 325 00:20:27,240 --> 00:20:31,830 We take the, the value of the point along the dimension, subtract the centroid along 326 00:20:31,830 --> 00:20:35,570 the dimension, and divide by the standard deviation along that dimension. 327 00:20:38,520 --> 00:20:40,969 And this gives the normalized distance along that dimension. 328 00:20:42,340 --> 00:20:46,930 Now, consider the point, along dimension i that is at a distance of one 329 00:20:46,930 --> 00:20:48,990 standard deviation away from the centroid. 330 00:20:50,670 --> 00:20:54,460 What this means is that x i minus c i is equal to sigma i. 331 00:20:56,380 --> 00:20:58,670 But if x i minus c i is equal to sigma i, 332 00:20:58,670 --> 00:21:02,210 then the normalized distance in dimension i, which is y i, is equal to one. 333 00:21:03,660 --> 00:21:08,620 So Y i measures the number of standard deviations away from the mean, 334 00:21:08,620 --> 00:21:09,630 along dimension i. 335 00:21:12,010 --> 00:21:17,690 The Mahalanobis distance of point P from cluster C is the square root of 336 00:21:17,690 --> 00:21:22,839 the sum of the squares of the normalized, distances Y i, along each dimension. 337 00:21:23,980 --> 00:21:27,600 Let's see what, how we use the Mahalanobis distance. 338 00:21:27,600 --> 00:21:31,330 Now suppose point P is one standard deviation away 339 00:21:31,330 --> 00:21:33,120 from the centroid along each dimension. 340 00:21:35,280 --> 00:21:40,530 Now we saw that in that case, each yi is going to be 1, since yi 341 00:21:40,530 --> 00:21:44,630 measures the number of standard deviations away from the centroid along dimension i. 342 00:21:44,630 --> 00:21:48,640 And since there are D dimensions, the, the mahalanobis distance to the point P 343 00:21:48,640 --> 00:21:53,930 from cluster C is going to be square root of D, where D is the number of dimensions. 344 00:21:53,930 --> 00:21:59,330 Now going back to ou,r bell curve from the, Gaussian, or normal, distribution. 345 00:22:01,150 --> 00:22:07,530 the, the probability, that each YI is equal to one, 346 00:22:07,530 --> 00:22:12,710 or that the point is one standard deviation of A along each dimension. 347 00:22:12,710 --> 00:22:18,115 1 standard deviation, not less, in each dimension, is 0.68. 348 00:22:18,115 --> 00:22:25,800 0.34 + 0.34 here, and so the probability, that, 349 00:22:25,800 --> 00:22:33,220 that point is Mahalanobis distance of square root of d or less, is 68 percent or 350 00:22:33,220 --> 00:22:38,630 point, 68 of those points are in this area for each dimension, right? 351 00:22:38,630 --> 00:22:43,290 And similarly, the probability that the Mahalanobis distance of a point 352 00:22:43,290 --> 00:22:48,470 belonging to a cluster is, within, two times square of D, 353 00:22:48,470 --> 00:22:53,684 from, it-it-it's-it's 95%, and, an-and 354 00:22:53,684 --> 00:22:58,980 99% of points have Mahalanobis distance less than three times, square root of D. 355 00:23:01,590 --> 00:23:06,190 So, this sort of motivates us to, formulate the Mahalanobis acceptance 356 00:23:06,190 --> 00:23:12,210 criterion for the BFR algorithm, which is to accept point P into the cluster C. 357 00:23:12,210 --> 00:23:14,710 It its Mahalanobis distance from the center, is, 358 00:23:14,710 --> 00:23:18,050 from the cluster centroid is less than some three sets ratio. 359 00:23:18,050 --> 00:23:23,110 For example, we might, bring the threshold to be three times, square root of D. 360 00:23:23,110 --> 00:23:28,640 Which means that, it's, the-the-the prob, that it's less than 1% probability, 361 00:23:28,640 --> 00:23:34,389 that the, the-the pont, is, you know, does not belong to that, cluster. 362 00:23:35,680 --> 00:23:39,280 The second question that we left open during our discussion of the algorithm, 363 00:23:39,280 --> 00:23:42,300 was whether two subclusters or 364 00:23:42,300 --> 00:23:47,800 mini clusters in the compress set should be combined or compressed into each other. 365 00:23:49,490 --> 00:23:52,730 The simple way to address this question is to compute the variance of 366 00:23:52,730 --> 00:23:54,480 the combined sum, subcluster. 367 00:23:55,870 --> 00:23:59,100 The way we do that is to just add N, SUM and 368 00:23:59,100 --> 00:24:03,130 SUM square values of the two clusters to each other. 369 00:24:03,130 --> 00:24:06,910 And then we can compute the,the centroid, and 370 00:24:06,910 --> 00:24:12,710 the variance of a combined hypothetical combined sub-cluster. 371 00:24:12,710 --> 00:24:17,610 If we find that the combined variance is below, some threshold. 372 00:24:17,610 --> 00:24:21,010 Uh,then that might indicate to us that these two clusters actually do 373 00:24:21,010 --> 00:24:25,325 belong together, and we might decide to combine those two, 374 00:24:25,325 --> 00:24:29,030 sub-clusters in the compressed set into a single cluster. 375 00:24:31,290 --> 00:24:35,370 Now this is just one approach, to this, to answer this question and 376 00:24:35,370 --> 00:24:37,160 there, there, there could be other approaches. 377 00:24:37,160 --> 00:24:41,300 For example, some dimensions will be more important than others. 378 00:24:41,300 --> 00:24:44,260 You know, in the, in, in the data for example. 379 00:24:44,260 --> 00:24:48,230 Height may be more, more important than weight, in, and so 380 00:24:48,230 --> 00:24:51,020 we might want to rate dimensions, differently. 381 00:24:51,020 --> 00:24:55,030 Or we might want to use a density-based metric, like we, 382 00:24:55,030 --> 00:24:57,190 studied when we looked at algorithmic clustering