Today we're going to talk about clustering
Do you ever find when you're on YouTube you'll watch a video on something and then suddenly you're being recommended a load of other videos
That you hadn't even heard of that are actually kind of similar. This happens to me
I watched some video on some new type of saw trying to learn it because you know don't know what I'm doing and suddenly I'm
Being recommended videos on turning verses on wooden lathes and all kinds of weird stuff
And what's happening is I'm being clustered into groups of people
Who are liking those and watching those kind of videos or these kind of videos are all being clustered together as similar, right?
So clustering is it's one of the sort of core technologies at the heart of this kind of stuff in fairness
I did end up watching a bunch of those woodturning videos
We've talked about the different kinds of datasets you might have right and until up to now we've been talking about things like cleaning data
transforming data and reducing data
Now what we want to do is start trying to derive some knowledge now sort of a typical way to do
This would be something like a classification algorithm or maybe a regression ad with them
But today we're going to talk about how do you separate out data and group data together?
When we don't have any labels for that data, so this is an example of unsupervised learning
Different types of machine learning that we can use one is unsupervised. This is where we don't have any labels
Then we have supervised learning where we have labels
so for example a supervised learning task might be one where you have some labels for you for your products or your videos and you're
Trying to classify them like that. So maybe you're trying to classify videos into a genre right or
Unsupervised learning we don't have any labels
Maybe we've just got a load of products and we're trying to group them into into similar categories
So these are all the tools and these will be electronic products
And these are all the toys
right
and maybe we want to do that without having to have a person go through and click on them all so why wouldn't we just
Label everything and then use that to perform nice powerful machine learning algorithms like classification
Well, sometimes it's just too expensive to produce labels if you're running a music recommendation system
I
like the wonder power Spotify maybe going through and defining what genre everything is by hand is going to take
Absolutely ages and one waste of time right way if we can do this automatically so sometimes you aren't gonna have labels for data
And it's too expensive to obtain. It's too time-consuming. It's too difficult
Maybe you don't
people disagree over what John or two pieces of music are so in that case you are going to have labels and so
Clustering is a good option
right
Let's group things together with things that are similar in terms of their attributes without actually knowing what they are
What we're going to try and do then is take all the attributes and all the instances
objects and use them to group them into similar objects, but the question is what is similar like well
Let's think back to the way that we structure our data we're going to have rows as our instances and we're going to have columns
As our attributes and another way
We remember to think about that is that these actually are data points in some space
Where the position of each point or the position of each instance depends on the attributes?
So, for example, we could have a three attribute data set
So maybe we have Row 1 2 3 4 and we have attribute a B and C, right?
So, I don't know maybe one has a value for a in a value for B and a value for C
So this means this is a sort of three dimensional data set with our axes a B and C
So we're going to have something like this and then see you guys office
So this is a this is B, and this is C
So maybe in this data set, you know instance 1 appears here and 2 over here and 3 over here and 4 over here
Right you've just I'm imagine
These are in some sort of 3d space, you know, perhaps intuitively we can say well ok
One is maybe closer to 4 than 2 is because this is shorter distance
But of course, this is a three dimensional space is hard to visualize but doesn't matter how many attributes we have
We can still say well ok, in this space. These instances are closer to these instances and then we can start grouping things together
So maybe I mean actually 2 is very far away from free
So maybe we sort of group these two up and group these two up or something like this
So typically we're going to use you're clearly in distance for this
Right, which is going to be this best distance here between points 1 & 2 in this 3 dimensional space
There's obviously going to be questions about how many groups are we grouping them into?
It's 3 too far away to be in any of these groups
These are things we have to think about but this applies to any number of dimensions
as just simply the only thing holding you back is just how fast your computer is and how fast
Go food is we're gonna look at two different
Clustering algorithms, right? The first is going to be k-means and then we're going to look at pam
Alright, which is slightly different now
We talked about k-means in computer file before but we're going to talk about it here for this course
So just you know to keep things simple for my arm and drawing i'm gonna think the two dimensions here and we've got some sort
Of data, right which is sort of looks like this and there may be some more data over here
And you know to us we can sort of say well maybe there's two groups
But we want to sort of formalize this process and you've got to consider that in two dimensions
Maybe it's quite clear that there's two groups
if you've got a sort of
n-dimensional space maybe a thousand dimensions or ten thousand dimensions
Picking out where the groups are is not something you want to be doing by hand
So what k-means does is it splits some data into K groups, right?
So I'm going to specify them Oh strike straight away but K is 2 in this case because I think there are two classes here
Now if I get that wrong, obviously, that's a problem. We'll talk about that. Later
But what we're gonna do is we're gonna pick two random points in this space. So let's say this one here and
This one here
So we've got two classes and we're going to start to assign each of these points based on whichever of these means is closer
So these are the center points for our new groups generally speaking. Obviously, this is going to be clearly in distance
So essentially a circle in this case
So we're going to sort of look sort of like this and the blue one's going to come around
So kind of like this kind of like this and these will probably be red because they're slightly closer
So now but all these are red. What we're going to do is we're going to label these all red
I can only do one iteration of this because now painted all over my picture we start by assigning all of them now
We might be finished. But let's imagine. We're not what we want to try and do is
Reevaluate where the positions of our clusters are based on this information
So we take the mean or the average position of this group here the red group and we can say well, okay
It's sort of bang in the middle here. So we get rid of this one. I'm gonna this above our pen. Oh it worked
Here's my new center position here
Right, the blue one, which I'm going to have to scribble out is going to move to our about there something like this
So that's iteration one right now. We've we calculated these center points
so this blue region of what's going to be classified as blue and what's going to be classified as red it's kind of going to
Move this way a little bit. So I guess we're going to maybe reevaluate and this is going to become blue
Ooh, this is going to be an iterative process
we're going to keep recalculating these means based on the points that have moved back and forth between these two groups and
Eventually, these means should begin to converge and stop moving around as things settle down
And usually this actually happens pretty quickly. I even in a large dimensional space k-means is a very popular algorithm. It's got a few drawbacks
One is that let's imagine. We had a single point way over here an outlier right now
Hopefully you've got rid of most of our lives from the previous video
But if you haven't and you've got an outlier here that you weren't expecting
Then what's going to happen is this is going to be assigned it in the first iteration to be blue
It's going to pull the mean of this group this way
which means that more of them are going to be assigned red and
Red is going to go this way as well and it's just going to move the means around and cause a bit of a problem
We might get away of it in this case
But you can imagine if you've got a large high dimensional space and you're trying to cluster lots and lots of clusters
Getting the means in the wrong position could cause a bit of instability cause the wrong plate things to be classified and clustered together
There's a couple more issues one is that you know
Where you start your means on the first iteration is obviously quite important if you place it at random
There's a charge you're going to put it right up here and things could take a lot longer to converge or could settle on some
Clustering that you're not happy with so this outlaw is going to be a problem, right?
It's going to make K means struggle slightly
So as an alternative we can use which is called Pam or partitioning around meds by or Kay meds
Whatever you want to call it instead of calculating a mean for our cluster and moving those means around what we're going to do is
Use actual points from our cluster
So what we do is we start off exactly the same as k-means but instead of picking two random positions we pick two random points
So for example, what we'll do is we'll pick this red one here and we'll pick this blue one here now
These are treated exactly like the means in kami
So we've in cluster our data around these two points and then we calculate an error for each cluster
That is the distance from all the other points. We assign to it
into that cluster so you can imagine hopefully if this point has been chosen in the middle of a cluster then the distance will be
Quite small because everything will be tightly bound together if it's we're over here as an outlier
It's going to be a huge error because the distance to all of these points is massive
So then what we do is we pick a group at random and we move the center to another point
So we okay we were here
let's move to here and we
Repartition our data and we calculate a new error per distance to all our new clusters based on this new position that we just picked
And if it's better, we permanently move our center point there
if it's not we go back to where we were before we pick a new cluster at random and a new point at random and
We repeat this process. So in k-means you move both means in fact, however, many
Group clusters, you've got you're going to move all the means at the same time, right?
Because you repartition the data all the means are going to move around and then you reposition the data and you repeat like this in
Pam you just move one mean or one
Exemplar or meadow at a time?
So let's say you pick the red one first
You move that and maybe pick the red one again and you move that and then it's blues turn you move that
And obviously this is gonna take a little while to do over time
Hopefully what will happen is you find that?
More and more of a time you try and move and it doesn't work because you just increase the error because you settled on something
really helpful
and
Also eventually if you take long enough doing this you're gonna visit it all your points and then you might as well stop as well
so typically
What you would do is stop after you
Fail a number of times to move somewhere better
Because really you actually found somewhere pretty good
this neatly avoids our problem of outliers because this one here won't affect the position of this cluster because if we ever chose it to
Be a center it will be immediately discarded because the error is so large
As opposed to it actually affecting the mean and pulling this cluster this direction
So there's one last problem and that is the problem of how did we get? This - I
Said that I thought there were two clusters in this data and happily there were and that worked out really nicely
But if you've got, you know a huge data set
There's no way to guess how many clusters this is going to be
And or if you do maybe that's not the optimal number of clusters
So for example, if you're trying to cluster up songs and Spotify, I mean how many clusters is that?
I have no idea like lots so you put 80 in and it's okay
But is that should you go up should you do 100 or should you do 60? I don't know
so there are approaches like DB scan which will try and bring in the concept of a neighborhood and have the ability to increase or
Decrease the number of clusters as appropriate for your data. All right
So what's going to happen is they'll say this looks good
But if we split this in two and had two clusters here instead
That will be a better fit right so these are very useful
Technique so you can use if you want something a little bit more powerful
Now it wouldn't be a date of an artist course if we didn't look at the iris dataset at least once this is a classic
Data set everyone uses and it's good for clustering nice and small and we can have a look and this data set
We've got three different species of flower. We've got so Tosa versicolor and
Virginica, we've got four attributes. We've got several length sepal width petal length petal width just for this occasion
I looked up what a sepal is and it's the green bit that covers the flower when it's folded up right now
I don't know much about these flowers, but they are subtly different. One of them is a little bit more different than the others
So it makes for a good clustering problem because we're hoping for three distinct clusters
the iris dataset is one of the ones that's built into our you can literally call data iris and
It'll load it up for you now
Let's have a quick look at what we've got because they're lovely function in are called pairs
Which just shows us a load of scatter plots of different attributes
so if I run this
This is only going to work for a few attributes before the whole thing becomes very difficult to look at
So we've got things like sepal length sepal width and the correlations of these and these are colored by the different class of flower
so you can see if the three class is one of them is actually quite different a lot of the time and then some of
Them bees this red and green class. They've got quite a lot of overlap
So clustering nose is going to be a little bit more difficult bearing in mind. We're using four dimensions to do it
Not the two you're seeing in any individual scatter plot. Okay. So let's just start off with standard k-means
so we're going to call km3 k-means with three clusters is
K-means, there's a function for this in R on the iris data set all of the rows 1 to 4
So not the species of plant
We're not going to custom on that three clusters and we're going to allow it to go 400 iterations
K-means will stop early if it doesn't improve itself, but if it keeps going maybe it's just going back and forth a little bit
It's time to stop that did not take very long
This object returned by the k-means function is going to have an integer
determining which of our
instances have been assigned to which cluster so all of these first ones have been assigned to cluster two and
The Centers for all of our clusters as well
So remember that in our we only have a data frame like this iris we can add other
columns to it
So we're going to just add our k-means result back into our it's data frame so we can keep track of it
So we're going to say iris
km3
is equal to km3
dollar
Cluster that's gonna be in there. Okay, so let's put it in a table
We'll have a look at how our clusters match up to our actual number of flowers
We've got so it's going to be a table of the irf species versus the iris clusters from k-means
Alright, so if we have a look at that
the first thing we'll see is that it doesn't make absolutely much sense because for example say Tozer which is our class 1 in some
Sense has been assigned to cluster 3. So what we're going to do is we're going to reorder these columns so that the
Correct. Classifications are down the diagonal much like a confusion matrix. So we have a function to do that that we're going to call and
If we look at this result, we can see that the results are an 89%
Classification accuracy, there were 50 of each plant in this dataset 48 of these plants have been correctly assigned to cluster two together
But two of them were in cluster 1 along with the other virginities and finally the virginica has been 36 of 50
Correctly assigned to cluster 1 and 14 have been incorrectly clustered into cluster 2, right so it worked pretty well. It's not perfect
Bearing in mind if you really want to separate out plants. Maybe you need more than 4 dimensions
Maybe you can't absolutely tell what a plant is just based on 4 dimensions
All right, some of these plants are similar enough, but the clustering isn't very well defined
So perhaps we can make our life a little bit easier by using principal component analysis to do dimensionality reduction
Or just to reframe our data onto some different axes to get better clustering result. So we're going to do a very similar thing
We're going to run PCA on
The iris dataset and we're going to project our points into that new
Principal component space and then we're going to take only the first two dimensions
So this is principal component 1 and principal component 2 as we covered in the principal component video
Then what we're going to do is we're going to apply caming stavos results rather than the original data
So what we've done is we've transformed our 4 dimensions of sepal width sepal length
Petal length and petal width onto our principal component axes and then we've discarded the last two and kept just two axes
So I'm going to run that that didn't take very long
Ok
We're going to sign that back to our iris data set just like we did with the results of k-means and then we can bring
Up another table and see how the results compare table to and then we'll order that again by the diagonal
Results were almost exactly the same. I think it was 88% 89% something like this
You can see that one extra
Versicolor was put into cluster 2 when it shouldn't have been I but this is with only 2 dimensions instead of 4 dimensions
So we've Harbor number of dimensions but by using PCA
we've got almost the exact same result for datasets that
You don't have labels for maybe the labels are too hard to get or you don't know what they would be
I
Think clustering is a good way to group up data and start to derive some knowledge the knowledge we can derive or what what items
are similar to each other by which products in our database are similar to each other so that we can start using them for a
Recommender system, you know, what movies are like each other what songs are like each other like what flowers are like each other?
So the ideas that were clustering data up and by doing that we can look at these clusters and start to gain some knowledge
Don't forget also that each of these is going to have a prediction as well
so this one here attribute one is going to have let's say like a label if we did play tennis or this person is
Healthy or this person has this disease. It depends on you