1 00:00:05,944 --> 00:00:07,672 [MUSIC]. If there's one more algorithm I want to 2 00:00:07,672 --> 00:00:10,912 talk about that's less well known than k-means but it has slightly nicer 3 00:00:10,912 --> 00:00:16,169 properties, so it's another good one to be familiar with, that is DBSCAN. 4 00:00:16,169 --> 00:00:20,694 So, how DBSCAN works is, given points say in a two dimensional space as always, 5 00:00:20,694 --> 00:00:25,174 we're going to look for points that are separated by a distance of no more than 6 00:00:25,174 --> 00:00:29,700 some epsilon. Okay. 7 00:00:29,700 --> 00:00:34,110 And so, if you can hop from one point to another by hopping no more than epsilon 8 00:00:34,110 --> 00:00:37,950 at each point, then all those points will be considered to be in the same cluster. 9 00:00:37,950 --> 00:00:41,239 And so, whenever you need to jump a little further in epsilon, you'll be 10 00:00:41,239 --> 00:00:45,050 entering a new cluster. Okay. 11 00:00:45,050 --> 00:00:52,280 So, in this example, if epsilon is this distance then we know we can get 12 00:00:52,280 --> 00:01:01,752 [INAUDIBLE]. These points are within Epsilon, these 13 00:01:01,752 --> 00:01:06,280 points are within Epsilon and so on. She's sort of induced this graph over 14 00:01:06,280 --> 00:01:10,740 the, over the data and so all of this A you know, B is reachable from A by hops 15 00:01:10,740 --> 00:01:12,939 of more than Epsilon so all of these are in the same cluster. 16 00:01:14,290 --> 00:01:20,295 And actually, C is also reachable from D by hopping the same cluster, but D is not 17 00:01:20,295 --> 00:01:23,090 and so D is in a different cluster. So all these solid points are in one 18 00:01:23,090 --> 00:01:28,104 cluster and all these hollow points are in the other one. 19 00:01:28,104 --> 00:01:32,470 Alright. So there's some advantages here, that are 20 00:01:32,470 --> 00:01:36,985 kind of illustrated by this picture. So, one is it can find non linearly 21 00:01:36,985 --> 00:01:39,880 separable clusters. So right here, there's no line you can 22 00:01:39,880 --> 00:01:44,330 draw to separate these two clusters and yet clearly there's kind of a dense 23 00:01:44,330 --> 00:01:47,630 region and another dense region. And so you want to try to draw a curved 24 00:01:47,630 --> 00:01:50,900 line, and DBSCAN finds this naturally but k-Means won't. 25 00:01:50,900 --> 00:01:54,160 K-Means will sort of find a point you know, depending on again, depending on 26 00:01:54,160 --> 00:02:00,527 where you start you know, maybe here and here or something. 27 00:02:00,527 --> 00:02:09,580 In which case, you'll get clusters like this, okay. 28 00:02:09,580 --> 00:02:15,680 So, there is no opinion on a fixed number of starting to clusters like k-means was. 29 00:02:15,680 --> 00:02:19,630 There's no dependence on starting conditions you sort of compute this from, 30 00:02:21,570 --> 00:02:23,973 you need the vertices in the graph and start making hops. 31 00:02:23,973 --> 00:02:29,730 There's only two parameters to this: one is this distance threshold epsilon and 32 00:02:29,730 --> 00:02:33,865 the other is a minimum number of neighbors, and what this controls is. 33 00:02:33,865 --> 00:02:40,520 Like if I find a point way out here in space that doesn't have any neighbors, 34 00:02:40,520 --> 00:02:44,510 doesn't you know, only has a few neighbors, then maybe I just consider 35 00:02:44,510 --> 00:02:46,340 that point noise, and I ignore it completely. 36 00:02:46,340 --> 00:02:50,290 I don't try to, I don't try to put it in any cluster whatsoever. 37 00:02:50,290 --> 00:02:55,900 And so here, if you, if you put many neighbors at 0, you'd get this one in 38 00:02:55,900 --> 00:02:58,550 it's own, very own little cluster, this one in it's very own little cluster, and 39 00:02:58,550 --> 00:03:00,810 so on. And so that just keeps on, it requires a 40 00:03:00,810 --> 00:03:03,430 extra bit of book keeping. It's not necessarily a big pull on the 41 00:03:03,430 --> 00:03:05,469 algorithm, you'll still find the obvious two main clusters. 42 00:03:05,469 --> 00:03:13,522 But you can set this guy second neighbors parameter to control the extra book 43 00:03:13,522 --> 00:03:19,990 keeping that you have to do to maintain the single thing cluster, okay. 44 00:03:19,990 --> 00:03:24,422 Fine, and then you know, the, the core primitive here as it's operating is to 45 00:03:24,422 --> 00:03:27,412 find me all the neighbors within epsilon, find me all the neighbors within epsilon, 46 00:03:27,412 --> 00:03:30,240 find me all neighbors within epsilon. And so this operation is amenable to 47 00:03:30,240 --> 00:03:36,370 spacial indexing techniques, which can be implemented in log in so that every 48 00:03:36,370 --> 00:03:38,750 lookup requires only a logarithmic number of steps. 49 00:03:38,750 --> 00:03:40,946 Remember, as we talked about in the scalability lecture. 50 00:03:40,946 --> 00:03:50,330 And so the overall run time of this is n log in, alright? 51 00:03:50,330 --> 00:03:54,830 So some disadvantages here is that it's sensitive to Euclidean distance 52 00:03:54,830 --> 00:03:57,840 measurement problem. And, if you remember a few, a few 53 00:03:57,840 --> 00:04:01,680 lectures ago I made a point to say that whenever you see euclidean distance, you 54 00:04:01,680 --> 00:04:04,690 should be thinking about, there's, there's one big major problem with it 55 00:04:04,690 --> 00:04:09,100 which is recursive dimensionality right. So as you get a very, very large number 56 00:04:09,100 --> 00:04:13,840 of this of dimensions, Euclidean distance search becomes somewhat meaningless. 57 00:04:13,840 --> 00:04:18,995 It starts to get bigger and bigger and bigger, and the data sets starts to get 58 00:04:18,995 --> 00:04:22,920 sparser and sparser and sparser. The space that it's embedded in is very, 59 00:04:22,920 --> 00:04:25,170 very sparse. But k-means also has this problem, 60 00:04:25,170 --> 00:04:27,200 because it also tends to rely on euclidean distance. 61 00:04:27,200 --> 00:04:30,323 And you actually can define other distance measures and have, and have 62 00:04:30,323 --> 00:04:32,882 adapt k-means and DBSCAN both to use them. 63 00:04:32,882 --> 00:04:37,530 Okay. And then another problem is that, you're 64 00:04:37,530 --> 00:04:41,260 kind of making this implicit assumption that the density that defines a cluster 65 00:04:41,260 --> 00:04:43,903 is constant throughout the data set. And so, this is related to this concept 66 00:04:43,903 --> 00:04:44,754 of heteroskedasticity that we talked about. 67 00:04:44,754 --> 00:04:46,400 That may have seemed a little unusual at the time, but it comes up in various 68 00:04:46,400 --> 00:04:54,690 guises in different contexts, so I want to make sure that I mentioned it. 69 00:04:54,690 --> 00:04:59,640 So, for example, this plot is actually the same one that we generated for, to 70 00:04:59,640 --> 00:05:03,670 make the point of that heteroskedasticity in the statistics segments. 71 00:05:03,670 --> 00:05:09,930 But what I've done is just cut out some portions of the data here and here. 72 00:05:09,930 --> 00:05:14,910 And so now, it looks to our eyes that it ought to be three clusters here. 73 00:05:14,910 --> 00:05:18,060 Right. One here, one here and one here. 74 00:05:19,970 --> 00:05:24,814 But DBSCAN, given its sensitivity to this epsilon number, you do define epsilon 75 00:05:24,814 --> 00:05:29,170 such that this cluster is very easy to detect; you know, a very small epsilon 76 00:05:29,170 --> 00:05:32,995 about this kind of distance. Or do you find a slightly bigger epsilon 77 00:05:32,995 --> 00:05:35,730 so that you can capture these kinds of clusters. 78 00:05:35,730 --> 00:05:39,402 And if you're not careful, I suppose here I've actually dotted this one where it's 79 00:05:39,402 --> 00:05:43,074 probably okay to use the bigger one, but if your not careful you'll, you'll you 80 00:05:43,074 --> 00:05:46,683 know. The density region here may be on par 81 00:05:46,683 --> 00:05:49,903 with the distance between these two clusters here. 82 00:05:49,903 --> 00:05:52,693 In which case, with a small change to epsilon you might all of the sudden put 83 00:05:52,693 --> 00:05:55,875 the whole, the whole data set into one cluster, okay. 84 00:05:55,875 --> 00:05:59,655 And so, adaptive epsilon, depending on which region you're in, might be 85 00:05:59,655 --> 00:06:03,206 something you could, you could think about. 86 00:06:03,206 --> 00:06:06,716 Alright. And just like with k-means, you can think 87 00:06:06,716 --> 00:06:11,000 about how to paralyze DBSCAN, and the, the only trick I want to point out here 88 00:06:11,000 --> 00:06:15,420 is that you need to worry about this halo region around each cluster, or rather 89 00:06:15,420 --> 00:06:20,834 around each segment. So here we divide up the space into say 90 00:06:20,834 --> 00:06:23,586 four different processors and each processor is going to be responsible for 91 00:06:23,586 --> 00:06:27,918 that space. And in the middle, internal to this 92 00:06:27,918 --> 00:06:34,750 processor, you can run DBSCAN as usual. But when you get close to the boundary of 93 00:06:34,750 --> 00:06:40,970 the, of the region handled by this processor you need to be, you need to do 94 00:06:40,970 --> 00:06:43,750 some careful book keeping. Okay. 95 00:06:43,750 --> 00:06:46,560 And so all the ones that are within this boundary region need to be sent to this 96 00:06:46,560 --> 00:06:52,590 other processor for comparison, to see whether you need to relabel C4 and C6 as 97 00:06:52,590 --> 00:06:54,930 part of the same cluster. Whether those two clusters are connected 98 00:06:54,930 --> 00:06:59,040 by a distance epsilon or they're not. And so, they'll independently find all 99 00:06:59,040 --> 00:07:02,340 their clusters, but then you'll merge some clusters when you combine and you 100 00:07:02,340 --> 00:07:06,390 can actually express this in terms of a sequence of MapReduce jobs. 101 00:07:06,390 --> 00:07:11,450 Which I won't go into details of, but there's some work done by a student here 102 00:07:11,450 --> 00:07:21,076 a few years ago to describe and analyze the, the algorithm here. 103 00:07:21,076 --> 00:07:24,420 Okay. So finally, I just want to wrap up with 104 00:07:24,420 --> 00:07:33,350 this great picture from the scikit-learn Python library website, which talks about 105 00:07:33,350 --> 00:07:36,410 the differences between various Clustering algorithms. 106 00:07:36,410 --> 00:07:39,445 And we've only talked about two of these. We talked about K means, we talked about 107 00:07:39,445 --> 00:07:47,900 DBSCAN and mini batch k-means is a, online version if K means that uses batch 108 00:07:47,900 --> 00:07:53,360 at a time to compute centroids. But you can see some of the, some of the 109 00:07:53,360 --> 00:07:57,090 strengths and weaknesses here. k-means actually doesn't do that great in 110 00:07:57,090 --> 00:08:00,140 any one of these admittedly tricky challenge problems. 111 00:08:00,140 --> 00:08:05,430 Where here, you would probably think that you want this internal circle to be a 112 00:08:05,430 --> 00:08:09,810 cluster and the outer circle to be a second cluster, and k-means doesn't quite 113 00:08:09,810 --> 00:08:12,090 get that right depending on where you have the starting condition. 114 00:08:12,090 --> 00:08:15,810 Meanwhile these two clusters kind of overlap in space as well. 115 00:08:17,210 --> 00:08:20,200 And here, if you have a bad starting condition between these two clusters, you 116 00:08:20,200 --> 00:08:25,010 might put them all in the same cluster, or really anything, anytime the starting 117 00:08:25,010 --> 00:08:27,270 condition is up here. And so down here, this one will sort of 118 00:08:27,270 --> 00:08:29,900 gravitate towards this cluster and this one will sort of gravitate towards this 119 00:08:29,900 --> 00:08:32,700 cluster and end up in the middle. And so on. 120 00:08:32,700 --> 00:08:38,730 Meanwhile in DBSCAN, this hop from this cluster to this cluster is greater than 121 00:08:38,730 --> 00:08:44,160 epsilon, and so you'll, you'll do the what seems to be the correct thing, which 122 00:08:44,160 --> 00:08:46,275 is put in the inner circle in one cluster and the outer circle in another. 123 00:08:46,275 --> 00:08:50,320 Similarly here, the distance between these clusters is enough where DBSCAN 124 00:08:50,320 --> 00:08:56,160 figures it out and some where over here. And for the noisy case, DBSCAN puts all 125 00:08:56,160 --> 00:09:00,070 of these points on the same cluster; which to our eyes that's probably the 126 00:09:00,070 --> 00:09:04,620 right thing to do, okay. Then the take away here is that at least 127 00:09:04,620 --> 00:09:09,680 in these for challenge problems, DBSCAN does the right thing in every case. 128 00:09:09,680 --> 00:09:13,069 And so, that's a good one to be familiar with.