Clustering Analysis (contd) Video Lecture | What is Data Analytics? - Data & Analytics

hello and welcome to our second lecture
on clustering analysis in the first
lecture we introduced the idea of
clustering differentiated it from say
classification and other supervised
learning techniques and we explained
what clustering is how it's useful where
it can be used and also give you a brief
overview of the different types of
clustering and the different types of
clusters in today's lecture we are going
to introduce two very popular clustering
techniques the first is the k-means
clustering and the second is called the
hierarchical clustering while both these
techniques of are fairly old they still
enjoy immense popularity in terms of
being actually used the first one the
k-means clustering and is like this
choice of k-means and hierarchical you
should find to be also fitting the
overall the first dichotomy that we used
when we talked about clustering
approaches which is partitioning based
approaches in hierarchical approaches so
the k-means clustering is essentially
the partitioning based approach and what
we will do is we will dive into the
algorithm right so we've already
mentioned there is a patterns
partitioning based approach so it's one
where you partition that a dataset into
K clusters essentially and you it's also
very useful to think of the k-means as a
prototype based approach where that's
also something that we discussed in
terms of how clusters are form and the
prototype based approach is one where
there's like this representative for
each cluster and you use these
representatives in some fashion to to to
express what a cluster is and to also
form the clusters so it's essentially
this this prototype based approach where
you create K clusters and it's also not
really that it's an iterative procedure
so so even right at the end of the first
first iteration you already have K
clusters
and they might not be good clusters
because it's just the first iteration
and then like most most optimization
procedures like steepest descent or any
of these other iterative procedures
you'll find that over time you're just
refining a solution and at some point it
doesn't make sense to define anymore
here you're not you're not you know your
clusters are not changing essentially a
prototypes are not changing either
location of who they are and so you stop
at some point okay this procedure is
ideal when all variables are
quantitative now that what we really
mean is that you should be able to take
each data point and you might have some
other data point or some other location
and your location is defined across the
multiple attributes associated with this
data point right so so a data point
again the conception you should have in
your mind is these rows and yeah
basically grouping data points that's
your job and each data point is
described by some attributes which is
these which are these columns in a table
and each column means something right so
with the k-means procedure what you're
doing is you want to say that you want
to take this conception and you want to
actually you want to actually be able to
compute distances between two points
across these dimensions which means the
attributes themselves need to be
quantitative this in a lot of ways
should remind you of this K nearest
neighbors examples that we took up
especially in the case of K nearest
neighbors regression all right where
each of these dimensions in those for
those each data point is a continuous
quantitative variable okay and once you
do that you should just be able to
compute distances typically whenever it
comes to computing distances we've
always used Euclidean distance you could
also use other measures of distance and
you would actually it would still be a
k-means procedure with a different
approach so common ones are Manhattan
distance Euclidean distance and so on
okay so how does it really work so let's
just go through the algorithm in some
sense and then we'll see a graphical
representation of it
the idea is to initialize some cluster
centers kay so what do you mean by
initialized cluster centers what we mean
is essentially think of this and it's
easy to think of it in a graphical sense
or you can think of it in a mathematical
sense but the idea is that each data
point can be expressed in terms of an x
axis y axis z axis WX so on and so forth
depending on the number of attributes
there are right that represent each data
point now while each data point is
represented based on these different
attributes you can create a cluster
Center also on these attributes and
often it really makes sense to put
cluster centers where you think the
clusters are going to be formed but you
see how even if you don't do that
perfectly sometimes the clustering the
k-means clustering will adjust for it
but the most important thing to take
away from this is that the k-means
clustering algorithm therefore could be
sensitive to where you place the cluster
centers if you don't place them in
sometimes the right places you could get
to a solution which is not necessarily
the necessarily a good solution okay so
the idea is that you initialize some
cluster centers so specifically you will
initialize k cluster centers so you
because it's k-means clustering so k is
usually a number between 2 and maybe 10
or 20 depending on the higher limit is a
little more vague most problems you're
looking at between two to two to six or
seven clusters at the most but there are
contexts where your data set is really
large or what you what you intend to do
with the clustering is such that you
don't mind having more clusters okay so
the algorithm initially you you drop in
k cluster centers and then what you do
is you take each data point and you
figure out which of these cluster
centers is closest to the data point and
then you assign the data point to the
closest cluster Center yeah and so
essentially it's like if you if you kind
of
gave names so just to give you some
insight this is where we are we're in
the second bullet point so what we're
doing is we're basically saying if you
wanted to give those K cluster centers
name is cluster 1 cluster 2 cluster 3
then what we would do is we would go to
each data point and say hey which
cluster Center is closest to you and
then I'm going to assign you to that
cluster Center ok now once all of these
points have been assigned what we're
going to do is we're going to recompute
the cluster Center to be essentially the
centroid of this assignment of data
points derived from step two so what
we're going to do is essentially in step
two what you did is you assigned a whole
bunch of data points to different
clusters right so what we'll do is we'll
then for instance take all the data
points that were assigned to cluster 1
to centroid 1 essentially to the Custer
Center 1 and we gave them all the labels
that hey you are assign the data point X
you are assigned to cluster Center one
data point why you're eccentric plus the
center one so all of them that were
assigned to cluster Center one will take
those data points and compute the
centroid of those data points centroid
essentially is in many senses like an
average right it's again it depends on
exactly what measure of distance you
choose but if you were choosing
Euclidean distance the centroid is
essentially like the average and we say
it's the average of these data points
but it's that it's called the centroid
because it's the average across all
those dimensions and the number of
dimensions are the number of attributes
right so across those dimensions what's
the center so once all these points have
been assigned you kind of compute a new
cluster center based on the centroid and
it's essentially like you forget the old
cluster center and now this new cluster
center is your cluster Center and you do
this for each assignment right if ten
data points were assigned to cluster
Center one then you do this step for
cluster Center one data points and then
you go to the next 15 data points that
were perhaps assigned to cluster Center
two for these 15 data points find out
the new centroid and call that the new
cluster Center
so you've got
a new k set of cluster centers what do
you do next you iterate for these new k
cluster centers they go to each data
point and it's almost like you forgot
which cluster Center that data point
belong to because remember that data
point was assigned to say cluster Center
1 or 2 based on the old centroid right
though based on the old cluster Center
now because your cluster centers have
moved based on the centroid you now
assign them all over again and once
you've done the assignment all over
again
you find the centroid once you find the
centroid you do the assignment that's
how it's an iterative process
essentially you're repeating these steps
2 & 3
until the centroid is not moving any
further or in some cases you might say
the centroid is moving by an amount
small enough that is within your
tolerance so this was fairly abstract in
terms of bullet points so let's actually
take a graphical look at this
you've taken an ultra simplistic example
where there are only two attributes so
let's say attribute is x1 x2 always
remember that with clustering which is
unsupervised learning there's no Y there
is no output variable what we're doing
is trying to group the data and here is
the data the data is are these blue
squares and you're trying to group these
blue squares now a fairly naive look at
this can kind of make it obvious that
perhaps this is one cluster and this is
one cluster okay so the blue dots are
actually the data points now
now that's to the naked eye and the
things to remember are that you know if
if for instance there were more
dimensions that were there were more
attributes beyond x1 and x2 it would be
harder to show you this visually right
so at that point the math kind of takes
over in 3 3 dimensions I can show you x1
x2 x3 but then after that what do I do
if you have more attributes okay so the
squares are essentially the data points
and let's say the k-means clustering
algorithm started with two centroids
here obviously that means K is equal to
two so you've initialized two centroids
and you know these like I said the
algorithm itself to some extent could be
sensitive to how you initialize the
centroid so there is a right way in a
wrong way
ideal would be if you could actually
plot the centroids right in the middle
of the clusters but often we don't know
that yet that's why we are doing a
clustering yeah so what's the first step
in a questioning algorithm the first
step is to stake each data point and see
which Center which cluster Center is
closest right so let's say we take this
is data point 1 clearly this the yellow
cluster Center is closest and at least
so for the set of data points this
yellow is closest obviously for another
set it looks like the Green is closest
so each data point basically gets an
assignment it either gets assigned a
yellow color or a green color and that's
essentially what I've done this diagrams
are more conceptual not to scale so I've
kind of eyeballed it and said it looks
like these four data points are close to
the yellow that these three these four
are close to the green so that's how
they've been assigned what's the next
step the next step is given this
assignment the new cluster center for
the yellow data points is the centroid
of the yellow right so what is the
centroid of the air you know the so you
can think of it as essentially the
average of the yellow an average
obviously needs to be on this axis as
well as it needs to be on this axis
right so where would you centrally place
yellow so that it's you know minimizing
the squared deviation which is Euclidean
distance to each data point and that
that's the definition of centroid and so
we move the yellow yellow circle to be
the new centroid and it's probably going
to come somewhere here and the green
circle now the green circle has a little
bit of a problem right it just can't
move to the center of this space out
here because it obviously has an
assignment so this is going to bias
where the green move so perhaps it will
move somewhere
here and that's what I do in the next
step I actually move the yellow and the
green
but once I move it right it's like the
assignments are completely lost you
forgotten the assignments because
remember the assignments were made with
the old centroids right now with the new
centroids you just have new cluster
centers and no assignment you redo the
process when you redo the process you
see now which blue dots are closest to
the yellow and which ones are closest to
the green and we repeat the process and
as you can see we've already gotten
pretty good results out here with the
yellow and green classification which
matched our intuition about what the two
clusters on this graph was clearly in
the next step for instance this green
will move right into this cluster Center
the assignments themselves won't change
too much perhaps a yellow will move a
little bit out sure but essentially
after maybe one or two more steps the
centroids will stop moving your
assignments will probably be the same so
even if you'd stopped one or two stages
earlier you would have gotten in the
clusters that you were interested in
okay so I hope this gives you some idea
of what the k-means algorithm is now
another very popular prototype based
approach which can work and go beyond
k-means in some sense which can go
beyond quantitative attributes because
remember for you for this whole
algorithm to work you have to be able to
compute distances and it makes sense
that your attribute x1 and x2 were
quantitative and continuous right x1 and
x2 there's a little there's medium
there's more and this this is it's a
continuous quantitative variable now
many times you don't have that right so
a very useful alternative is chemi joins
in that case now keep me rods allows you
to go beyond quantitative variables and
so when you have categorical or rather
more importantly nominal variables where
the variable is they are things like
male-female and the attribute is like me
and female or things like that you can
use kami noise but more importantly like
haemorrhoids allows you to go
beyond attributes altogether right when
X 1 and X 2 is an attribute to a point
where all you need is some dissimilarity
matrix what do you mean by dissimilarity
matrix what I mean is you have all these
data points right let's start calling
them 1 2 3 4 right now with k-means the
distance between and I'm gonna give you
the same data points in the columns
right now what k-means I can compute the
distance between data point 1 and data
point 2 through some form of euclidean
distance in marker value X all right but
what if so the whole process of using
euclidean distance required that i go
into each attribute look at how
different it is and then compute that
right squared distance and take the
square root but what if I did not have
that process right what if I had a
process where I gave you just the
differences between each data point so I
had something like a dissimilarity
matrix right so when I have a
dissimilarity matrix that I'm giving you
and and you can get the dissimilarity
matrix through completely different ways
right it can be a user survey or it can
be something extremely subjective where
you say I feel like one and two are
different by this much and I can tell
you how how different one and two are
and I can tell you how different one and
three are you know and I can tell you
how different one and four are and so on
but I can't really break it down into
five different attributes and give it to
you that way right so people do this a
lot of times in social science research
whether there's some kind of a question
I have that's given to people to tell so
please tell me how different these two
are and people are able to say that but
they're not able to break it down into a
set of quantitative variables and say
how different they are on each of those
dimensions so caimito it's is very
useful when you don't have these
attributes but you just have this
dissimilarity matrix of how each data
point is different from every other data
point okay so you'll essentially just
need some kind of a leading diagonal of
data so the data is either on this
data is either on that side because one
is different from to the same amount
that two is different from one there's
no difference between those two okay so
in cases like that kami rice primarily
winds up not having this arbitrary
cluster Center because you really can't
any longer compute things like centroids
right there is no centroid there are no
dimensions on which so what winds up
happening is you nominate a data point
to be that prototype and you'll use the
same core concept of k-means in that
you'll first nominate a data point and
then you'll do an assignment where each
data point chooses between the nominated
data points and once you have one
assignment you find the new nominated me
died that should become the
representative data point it's kind of
like the idea of being a cluster Center
okay now while this works the important
point is the computational intensity
associated with such an approach now
when you had 10 or 20 data points which
had an assignment right so let's take
all these data points right the
computing the average through sum of
squares just was essentially like
computed using the sum of squares
minimization was essentially just
computing an average of these points
across each of these dimensions right
now you don't have something like that
with Kami roids once you have an
assignment to choose which for this
assignment what should be the prototype
requires you to see the dissimilarity
between each data point to each other so
the number of computations that you need
to assess really grows and so Kimmy
rides is often seen as a very
computationally intensive approach okay
okay so this should give you some idea
about k-means and kami roids
the next approach that we're going to
talk about is hierarchical clustering
with hierarchical clustering you don't
really wind up fixing a fixed number of
clusters and essentially the approach
itself starts
with either one very large cluster and
breaks it down step by step so the first
one so one of so one way of doing it is
called the divisive way which is you
have one large cluster which has all the
data points in it and then after that I
break it into two clusters and then
after that I break it into three
clusters so I'd look at the the two
clusters that were broken up and I
choose how to break them down further so
and that's called the divisive approach
you also have the other approach which
is agglomerative and definitely the more
popular approach which is bottom-up
where each data point becomes a cluster
so you have all these so you have the
number of actual clusters you have is
equal to the number of data points
because each data point is a cluster and
then after that you choose the two
closest clusters and merge them together
and we'll talk about how closest is
defined so you choose the two closest
clusters and merge them together so the
end of the first step you are
essentially having if you had n data
point you're having n minus 1 data
points at the end of one step and after
that the next step you'll have n minus 2
because now you have n minus 1 clusters
where all of them except one have one
data point and one cluster has two data
points but you're just treating them as
clusters and you're saying now out of
these n minus one which are the two
closest clusters that I can merge and
that is seen as a bottom-up approach now
because of how we do this essentially
you're going to have nested clusters
right think of the divisive approach if
you created two clusters right now when
you go to create three clusters in this
divisive approach you're going to take
either cluster 1 or cluster 2 and break
it further and the other is going to be
the same so cluster so one breakup could
be the cluster one stays the same and
cluster two gets broken up into two
pieces right so in many ways nest a the
clusters that you're creating a nesting
within one another you can think of them
as parent and daughter and
same approach goes for the accumulative
right where you started with many
individual clusters and you're choosing
to group them it's never like you're
breaking one grouping yeah you're
rethinking an action that you did in the
previous step you never in some sense
going back in time andrey correcting a
decision to either group casters or to
break clusters and so in some sense you
can think of this also as a partly
greedy approach okay now we spoke about
how we're going to take with especially
the agglomerate ER which is what we'll
focus on in the rest of the lecture
because it's the more popular one and
and for a very specific reason that we
talked about you need to take in the
first step for instance you have n data
points and n clusters you need to take
the two closest clusters and merge them
how are you defining closest clusters
and the way you would kind of define
them is through some measure of
dissimilarity between the clusters an
example is for instance that there are
many there are many definitions of
dissimilarity one the three of them that
are listed here really talk about it
more in terms of come more from graph
theory and the first one is called
single linkage and the idea behind
single linkage as a means of talking
about dissimilarity is that it's
essentially when you take two clusters
you take the minimum distance between
two data points that can be in the two
clusters so don't think of it as much in
terms of the file in the first step
right within each cluster there's one
data point so it's not a variant
interesting case now think of a case
where you've got this cluster and you've
got three data points that's what I've
shown here let me give you a concrete
example so here is one cluster and there
are three data points within this
cluster
yeah here is another cluster and here
are versa four data points five data
points okay single linkage basically
takes each combination and sees which
combination is minimum so in this case
probably this would be minimum and so
you know it's a third reason it's
actually called min as a as a as a as a
definition of dissimilarity complete
linkage in contrast takes the maximum
this is which of these combinations I
need to take one from cluster a I need
to take one from cluster B which
combination of points can I take such
that I get the maximum distance and I'm
probably guessing that this connection
that I just drew would have that would
have the maximum distance this group
average which basically takes every
combination of every point to every
other point it takes the overall average
now in addition to that you also have
some approaches that try the more
prototype-based ways and and there you
would for each cluster try to create a
centroid and from that centroid you
would look at the distance from one
centroid to the other and so on and and
and there are some other approaches
there's there's the words method and so
on where you're again trying to take
some kind of a more prototype based
approach to define the dissimilarity but
essentially hierarchical clustering is
it's it's all of these still come in to
the broad umbrella of hierarchical
clustering okay so there are two two
important things in connection with the
hierarchical clustering as you can see
because it's doing this nested
clustering where you start from
with agglomerative you start with each
data point being a cluster and you keep
merging them till you have this one mega
cluster of all the data points and in
the other way around
with this device if you start with this
one mega cluster with all the data
points and keep breaking it till
each data point is its own cluster so
therefore you've not really committed to
creating clusters of a specific size k
right and you can therefore take you can
kind of look at the results overall and
make it make a decision in terms of what
your size should be one important
property that we see with all
agglomerative when you know in some
divisive methods is that the possesses
property called monotonicity and the
idea here is that the dissimilarity
between merged clusters is see there's
some way of measuring the dissimilarity
of a cluster right so that the
dissimilarity between merged clusters is
monotonically increasing with the level
of merger and that should be fairly
intuitive right when you think of the
dissimilarity of a cluster which has
just one data point there is no
dissimilarity right it's only when you
have two data points that you can say
these two data points are different by
this much
so with agglomerative clustering in some
sense the more number of data points
that you have into a cluster the greater
the mesh the amount of dissimilarity
there and that monotonicity is strictly
maintained with agglomerative clustering
so a very useful way of representing it
therefore especially when you have this
monotone the city you can graphically
represent agglomerative clustering
through something called a dendrogram
and what is shown in this slide is the
dendrogram and it's essentially this
binary tree which is plotted so that the
height of each node is proportional to
the value of the dissimilarity between
its datos so what is a node here
essentially you can think of each
partition as being a node right and the
height of this node right so let's take
something very simple the height of this
node has to do with this height right
has to do with the degree of dissimilar
t between B and C between so you're
forcing B and C to be in a cluster right
now that's what you're doing by this
this part of the graph that's what it's
doing right this height has to do with
the dissimilarity of B and C which is
why for instance perhaps DNA was merged
first
so with agglomerated clustering think
that you're going bottom-up and you are
sequentially making decisions and so if
you chose to put D and E together first
that means DNA would have been less
dissimilar to each other than B and C
and that's why DNA was done first and
then B and C was separately done perhaps
later now the really good thing about
the stand rogram
is that now you have a full picture you
can now choose to say I'm interested in
the situation where there are three
clusters and you can essentially draw
this horizontal line and you have the
three clusters cluster one is just data
point a cluster two is data point B and
C cluster three is data points d EF and
G right you basically see what goes into
each of these limbs and that's that's
essentially your cluster so at any level
when you draw a horizontal line you can
the number of vertical lines it cuts
across is the number of clusters that
you have in your so obviously if you had
a line out here and you drew it here
there's just one cluster or sure there
are two clusters and so on okay so this
should hopefully give you some idea
about the two very popular algorithms
k-means clustering and hierarchical
clustering and in hierarchical more
specifically agglomerate thank you