Mean Shift from Scratch - Practical Machine Learning Tutorial with Python

what's going on everybody welcome to
part 41 of our machine learning tutorial
series in this video in the next couple
videos or me talking about building our
own custom mean shift clustering
algorithm from scratch so to start we're
going to grab some code that we've
already written before so why not just
copy that I'm going to get it from part
37 if you have part 37 code copy and
paste that code or just this part
basically from the top all the way down
to colors or go to the part 37 tutorial
on Python program internet or this
tutorial number 41 and just grab that
starting code so I'm just going to copy
that paste and this is what we have if
we were to graph this up we get just
this it's just that simple cluster that
we've been we've been working with up to
this point so also let's we could add a
couple to this just for just for kicks
feel free you can keep the original if
you want or you can add the new data
that I'm going to add it doesn't really
matter or make up your own so we'll do a
210 two and nine three so that should
just give us like a new cluster too so
now I've got three clusters to deal with
just something interesting to do okay so
that's our data now I'm going to go
ahead and comment out these two lines
because we don't need to be graphing
those anymore we'll graph once we've
made some centers and then maybe later
it graph some colors with their groups
and all that so if you recall the the
the steps for the mean shift algorithm
is first assign every single feature set
is a cluster Center okay and then take
all of the data points or feature sets
within that cluster centers radius or
within the band width and then take the
mean of all those data sets or feature
sets and that is your new cluster Center
and then step three is basically repeat
step two until you have convergence
which just means many of the clusters
will converge on each other and become a
single cluster and then some will just
stop moving and once that's happened
you've got convergence you're done
and you've completed mean shift okay so
to start we are going to call this meet
class mean shift but you didn't see that
coming then we are going to have a
define in it and then we're going to
have self and then bandwidth and for now
we're going to set bandwidth to a hard
or and later on we'll we'll talk more
about bandwidth and waiting the band
widths and stuff like that which we kind
of already started talking about before
but I think that's a way better way than
having any hard-coded pin with but we'll
start with this for now to keep it nice
and simple and then we're gonna say self
at band width equals band width and
that's all for now in the initialization
now we're going to do a define fit and
again here we pass self and data and
then we're going to have centroids
equals an empty dictionary we don't need
anything there and then we're going to
set the initial centroids so for I in
range Len of data we're going to say
centroids I so we're giving the centroid
a an ID so that I will be their ID and
then that's the key and then the value
is just data I so whatever that value is
as we iterate through our data that is
the centroids location now with mean
shift you you can't have a max
iterations and you can also have a
tolerance if you want for now we're not
going to have well we'll have tolerance
because we'll still hit end up hitting a
tolerance most likely but for the most
part I'm pretty sure even on psychic
learns mean shift there's no tolerance
or max iterations so anyway so we'll
start off again pretty basic with it
just while true
so just infinite loop and then we're
going to say new centroids and we're
just going to say that's an empty list
so whenever we find new centroids we
throw them in there and then now we're
going to cycle through basically all of
our known centroids so we're going to
say for I in centroids we're going to
have now a new variable which will be in
bandwidth and that's just going to be an
empty list for now but this will soon be
populated
with all of the feature sets that are
within our bandwidth or within our
radius okay and then we're going to say
centroid equals centroids I okay so this
is just how we can get the the centroid
itself because I will just be the key
basically but to get that value of that
centroid we do that and then now what
we're going to do is we're going to
iterate through the data and decide
whether or not that feature set is
within the radius or bandwidth of this
specific centroid so what we're going to
say is if and we're going to say or
rather we're going to say for feature
set in data we're going to say if NP Lin
al norm let me go up to the top make
sure we are importing numpy yeah okay
cool
so if NP l in alcott norm and we'll just
put the whole method in here norm and
then this would be basically that
feature set - the centroid right
centroid is defined here if that
Euclidean distance is less than the self
dot bandwidth that we're allowing for
and really that's an unfortunate name
honestly cuz I'm trying to convince you
all that bandwidth and radius are not
the same you could save some things
within the bandwidth but if something's
within the radius is a distance and
bandwidth is like the entire thing so
I'm going to actually call this radius
I'm probably get in trouble for this
because uh anyway whatever self that
radius will say radius right okay so if
that norm is less than the radius that
means we are within the bandwidth or
within the radius so then we're going to
say in bandwidth this can stay bandwidth
because that still makes logical sense
dup end feature set so we just append
that feature set if it happens feature
set if it happens to be within that
bandwidth okay
now outside of the if outside of the for
loop we're going to recalculate that
mean of that centroid so we're going to
say the new centroid is going to be NP
average and then in bandwidth
axe is equals zero so this just gives us
the mean vector basically of all of our
vectors so NP average and then we're
going to add that to our new basically a
new centroids list
so we're say new underscore centroids
dot append and then we append the tuple
version of the new centroid that will
become apparent down the line while
we're doing that because basically a
tuple and numpy arrays have different
attributes than things that you can do
with them so we're going to be
converting this to a tuple for now
because later on we're going to have to
reference some things and anyway it'll
be a parent more parent later on while
we're doing that but we're just
converting an array to a tuple okay
so then that will be basically we're
done with the four I in centroids so now
we're going to come back over and we're
just in line with this for loop we've
completed the for loop we're ready to go
on so now what we're going to say is we
want to get the unique elements from the
new centroids list okay so we're gonna
say uniques equals the sorted value of
list of the list version of the set of
new centuries okay so this is why we
were using a tuple because you can get a
set of tuples in set just basically is
unique elements and you could do
something like numpy has a unique like
NP unique I'm pretty sure or uniques
maybe but the problem is it gives you
it's the unique of each value in the
array it's not unique of the arrays
which is really frustrating so anyway we
can use set and take the set of a bunch
of tuples and we can figure out which
ones are the unique versions and then
we're taking the list version and then
we are sorting that list fantastic so
that's the unique centroids because
again as they're as we get sort of like
a convergence we're going to find that
many centroids are the identical copy of
another centroid so what's that we don't
need two of the exact same centroid so
that's kind of how we get convergence
and we
them down over time so now what we're
going to do is we're going to say previs
or centroids equals the dict
version of centroids and so that again
is just our way of copying the centroids
dictionary without taking the attributes
and all that and that way we can like
save it and as we modify it centroids
it's not also modifying previous
centroids and then we're going to say
our new centroids we're just going to
define a new centroids dictionary so
we're going to say again centroids
equals empty dict
but remember this was an empty dick then
we populated it and then now we're
actually within this while true loop as
we start modifying centroids so
centroids is empty dict again but then
we're going to say for I in range of the
Len of the uniques what are we going to
do well we're going to say centroids I
equals NP or a so we're converting back
to that array version of the unique
eyuth element fantastic
so then what we say is we're going to
revert to our innocent until proven
guilty again so we're going to assume
we're optimized unless we find a reason
why we're not so we check to see if
there's any movement so for i in
centroids and i believe this will be
identical to that k-means code that we
wrote
but it'll be a if not NP or a underscore
MP dot array equal so if not the if
basically if the the elements of the
first of all this is why we sorted the
list so we sorted these lists because we
wanted to make sure because at any given
time it's kind of like random which one
would be which as we append them and
iterate through them because they don't
normally have an order so when we sort
that list and then we create the
centroids based on that sorted list the
centroids are now sorted so then we can
say we can iterate through the previous
version in the new version they're
sorted in the same way so then we can
find out if they're equal or not this
way
so now that I'm thinking about we
probably don't this probably is not the
same code from Keynes I don't recall
doing this from King but I might have
it's been a while
centroids I like if you did the previous
centroids I so we're just comparing the
two arrays to see if they're equal if
they're not we say optimized equals
false and then we could break it here we
could say most likely well we could
break the for loop we could say if if if
not optimized break so that breaks the
for loop and then again we could ask if
not optimize the break and we add the D
here I think that'll work
and that'll save us from continuing to
iterate through centroids if we found
one one that's moved there's no reason
to continue and especially for very
large data set that'll save a lot of
processing so we'll go ahead and throw
that in there that should work anyway so
there's that and then finally now we're
outside of this while true loop right so
once we finally are optimized or rather
what a newb okay so for i if not
optimized you want to break this for
loop right there's no reason to continue
on but then if optimized we break out of
the while loop okay what a newb okay so
now outside of this while loop right so
we're basically two tabs over let's
where to hit tab but I guess not let's
see one two right so in line with the
while loop now so coming on down here
we're going to say now once we're all
done we're going to reset our centroids
finally so self dot centroids equals
whatever the centroids are when we're
done and then coming down now one tab
over still within our class we're going
to just define predicts we're not
actually going to populate it for now
but we'll just throw it in there predict
we'll pass for now and then coming on
down here we're going to say CLF equals
mean shift and then we're going to say
self dot fit and we're going to fit that
X parameter there or the X stuff in the
parameter X variable that we find up
there fit X and then we're going to say
whatever the centroids are then we're
going to grab those from CLF centroids
we will we could print the centroids I
don't too much point though so then what
we're going to do is we're going to
scatter what we scattered up here so
we'll just copy this copy paste
uncomment on comment so that scatters
the data now will scatter the centroids
so I'm going to say for see in centroids
PLT dot scatter and we're going to
scatter let's see centroids see 0 and
then centroids c1 will say the color
equals K marker will be a star and then
s size 150 ok great so let's see what we
got hmm for I in range Len data try
again band width not defined of course
ah killing me
okay so self let's see self dot I I just
forgot to change these derp and I think
otherwise I don't use the bandwidth now
so let's try it one more time oh my
goodness this is a lot that's a lot of
errors okay coming down so for I unique
so so unique okay strike one more time
oh my goodness there we go okay cool
so here you can see we've done the
clustering algorithm and sure enough we
got our cluster Center here here and
here so that appears to have worked in
the way we intended now I'll let you
guys sleep happy for now without ruining
too much of your parade but I will
point out that that worked very nicely
mostly because we set this radius to 4
what if we set it to 4 D we didn't stay
in forever ok setting it to 40 we see
that oh we found one cluster Center
which is basically all of these data
points because everything is within a
radius of 40 what if we set it to 2 okay
I guess I'm really rain down on your
parade sorry guys
so anyway setting it to 2 worked out for
these two clusters but this one didn't
work out these are too too much spread
out so now they got their own little
each one is a cluster Center okay that's
pretty unfortunate and as the scientist
how are you supposed to know without
like looking through your data set I
guess and then you're going to have to
like figure out what this radius ought
to be that doesn't make any sense
that's not unsupervised machine learning
in my opinion so in the next tutorial
we're going to work on how we can just
automate this and not have to hard to
code in not I guess is not really hard
coding but basically it's hard coding
that value how we can just automatically
determine a decent radius to use but
then also use those various layers of
bandwidths and then just simply apply a
weight because basically the the radius
being like like allowing a radius that
is the size of 40 is great as long as
like let's say you're clustering here
right these data points here should have
a much higher weight they're closer to
the cluster Center than say these points
over here so if you apply a much higher
weight to them you're more likely to
have that average here and the more that
you're penalized for outliers you're
more likely to get these clusters
correct okay so that's what we're gonna
be talking about the next tutorial so
stay tuned for that if you have any
questions comments concerns whatever up
to this point on this code and all that
feel free leaving below otherwise as
always thanks for watching things for
all the support and subscriptions and
until next time