[MUSIC]. 
If there's one more algorithm I want to 
talk about that's less well known than 
k-means but it has slightly nicer 
properties, so it's another good one to 
be familiar with, that is DBSCAN. 
So, how DBSCAN works is, given points say 
in a two dimensional space as always, 
we're going to look for points that are 
separated by a distance of no more than 
some epsilon. 
Okay. 
And so, if you can hop from one point to 
another by hopping no more than epsilon 
at each point, then all those points will 
be considered to be in the same cluster. 
And so, whenever you need to jump a 
little further in epsilon, you'll be 
entering a new cluster. 
Okay. 
So, in this example, if epsilon is this 
distance then we know we can get 
[INAUDIBLE]. 
These points are within Epsilon, these 
points are within Epsilon and so on. 
She's sort of induced this graph over 
the, over the data and so all of this A 
you know, B is reachable from A by hops 
of more than Epsilon so all of these are 
in the same cluster. 
And actually, C is also reachable from D 
by hopping the same cluster, but D is not 
and so D is in a different cluster. 
So all these solid points are in one 
cluster and all these hollow points are 
in the other one. 
Alright. 
So there's some advantages here, that are 
kind of illustrated by this picture. 
So, one is it can find non linearly 
separable clusters. 
So right here, there's no line you can 
draw to separate these two clusters and 
yet clearly there's kind of a dense 
region and another dense region. 
And so you want to try to draw a curved 
line, and DBSCAN finds this naturally but 
k-Means won't. 
K-Means will sort of find a point you 
know, depending on again, depending on 
where you start you know, maybe here and 
here or something. 
In which case, you'll get clusters like 
this, okay. 
So, there is no opinion on a fixed number 
of starting to clusters like k-means was. 
There's no dependence on starting 
conditions you sort of compute this from, 
you need the vertices in the graph and 
start making hops. 
There's only two parameters to this: one 
is this distance threshold epsilon and 
the other is a minimum number of 
neighbors, and what this controls is. 
Like if I find a point way out here in 
space that doesn't have any neighbors, 
doesn't you know, only has a few 
neighbors, then maybe I just consider 
that point noise, and I ignore it 
completely. 
I don't try to, I don't try to put it in 
any cluster whatsoever. 
And so here, if you, if you put many 
neighbors at 0, you'd get this one in 
it's own, very own little cluster, this 
one in it's very own little cluster, and 
so on. 
And so that just keeps on, it requires a 
extra bit of book keeping. 
It's not necessarily a big pull on the 
algorithm, you'll still find the obvious 
two main clusters. 
But you can set this guy second neighbors 
parameter to control the extra book 
keeping that you have to do to maintain 
the single thing cluster, okay. 
Fine, and then you know, the, the core 
primitive here as it's operating is to 
find me all the neighbors within epsilon, 
find me all the neighbors within epsilon, 
find me all neighbors within epsilon. 
And so this operation is amenable to 
spacial indexing techniques, which can be 
implemented in log in so that every 
lookup requires only a logarithmic number 
of steps. 
Remember, as we talked about in the 
scalability lecture. 
And so the overall run time of this is n 
log in, alright? 
So some disadvantages here is that it's 
sensitive to Euclidean distance 
measurement problem. 
And, if you remember a few, a few 
lectures ago I made a point to say that 
whenever you see euclidean distance, you 
should be thinking about, there's, 
there's one big major problem with it 
which is recursive dimensionality right. 
So as you get a very, very large number 
of this of dimensions, Euclidean distance 
search becomes somewhat meaningless. 
It starts to get bigger and bigger and 
bigger, and the data sets starts to get 
sparser and sparser and sparser. 
The space that it's embedded in is very, 
very sparse. 
But k-means also has this problem, 
because it also tends to rely on 
euclidean distance. 
And you actually can define other 
distance measures and have, and have 
adapt k-means and DBSCAN both to use 
them. 
Okay. 
And then another problem is that, you're 
kind of making this implicit assumption 
that the density that defines a cluster 
is constant throughout the data set. 
And so, this is related to this concept 
of heteroskedasticity that we talked 
about. 
That may have seemed a little unusual at 
the time, but it comes up in various 
guises in different contexts, so I 
want to make sure that I mentioned it. 
So, for example, this plot is actually 
the same one that we generated for, to 
make the point of that heteroskedasticity 
in the statistics segments. 
But what I've done is just cut out some 
portions of the data here and here. 
And so now, it looks to our eyes that it 
ought to be three clusters here. 
Right. 
One here, one here and one here. 
But DBSCAN, given its sensitivity to this 
epsilon number, you do define epsilon 
such that this cluster is very easy to 
detect; you know, a very small epsilon 
about this kind of distance. 
Or do you find a slightly bigger epsilon 
so that you can capture these kinds of 
clusters. 
And if you're not careful, I suppose here 
I've actually dotted this one where it's 
probably okay to use the bigger one, but 
if your not careful you'll, you'll you 
know. 
The density region here may be on par 
with the distance between these two 
clusters here. 
In which case, with a small change to 
epsilon you might all of the sudden put 
the whole, the whole data set into one 
cluster, okay. 
And so, adaptive epsilon, depending on 
which region you're in, might be 
something you could, you could think 
about. 
Alright. 
And just like with k-means, you can think 
about how to paralyze DBSCAN, and the, 
the only trick I want to point out here 
is that you need to worry about this halo 
region around each cluster, or rather 
around each segment. 
So here we divide up the space into say 
four different processors and each 
processor is going to be responsible for 
that space. 
And in the middle, internal to this 
processor, you can run DBSCAN as usual. 
But when you get close to the boundary of 
the, of the region handled by this 
processor you need to be, you need to do 
some careful book keeping. 
Okay. 
And so all the ones that are within this 
boundary region need to be sent to this 
other processor for comparison, to see 
whether you need to relabel C4 and C6 as 
part of the same cluster. 
Whether those two clusters are connected 
by a distance epsilon or they're not. 
And so, they'll independently find all 
their clusters, but then you'll merge 
some clusters when you combine and you 
can actually express this in terms of a 
sequence of MapReduce jobs. 
Which I won't go into details of, but 
there's some work done by a student here 
a few years ago to describe and analyze 
the, the algorithm here. 
Okay. 
So finally, I just want to wrap up with 
this great picture from the scikit-learn 
Python library website, which talks about 
the differences between various 
Clustering algorithms. 
And we've only talked about two of these. 
We talked about K means, we talked about 
DBSCAN and mini batch k-means is a, 
online version if K means that uses batch 
at a time to compute centroids. 
But you can see some of the, some of the 
strengths and weaknesses here. 
k-means actually doesn't do that great in 
any one of these admittedly tricky 
challenge problems. 
Where here, you would probably think that 
you want this internal circle to be a 
cluster and the outer circle to be a 
second cluster, and k-means doesn't quite 
get that right depending on where you 
have the starting condition. 
Meanwhile these two clusters kind of 
overlap in space as well. 
And here, if you have a bad starting 
condition between these two clusters, you 
might put them all in the same cluster, 
or really anything, anytime the starting 
condition is up here. 
And so down here, this one will sort of 
gravitate towards this cluster and this 
one will sort of gravitate towards this 
cluster and end up in the middle. 
And so on. 
Meanwhile in DBSCAN, this hop from this 
cluster to this cluster is greater than 
epsilon, and so you'll, you'll do the 
what seems to be the correct thing, which 
is put in the inner circle in one cluster 
and the outer circle in another. 
Similarly here, the distance between 
these clusters is enough where DBSCAN 
figures it out and some where over here. 
And for the noisy case, DBSCAN puts all 
of these points on the same cluster; 
which to our eyes that's probably the 
right thing to do, okay. 
Then the take away here is that at least 
in these for challenge problems, DBSCAN 
does the right thing in every case. 
And so, that's a good one to be familiar 
with.