So we're going to talk about sort of an entry level
Clustering approach called K-means now K-means comes up a lot in other fields so machine learning uses K-means quite a lot
It's what we call an unsupervised clustering method often what you have is a situation where you have some training [data]
But you already know what it is, and then you try and teach your network to find the same thing again
So we've got labeled training Data in K-means what we've got is just some data and we say split that into three please
I'll start by showing a very simple overview here of
How caimans works if we imagine we've got some some data if it's grouped up
So I'm going to do some x's here and some x's here, so if we wanted to split this data up
We have no idea about this data to my eye
It looks like there are two clusters here right partly because I cheated and drew two clusters, but you know
So if we were giving this data, which is in two dimensions to a machine and said cluster this into two
What would it do basically is a question there's lots of different approaches K-means is just one of these approaches
I'm going to show you today
It's [Cayley] like just a variable or yeah k is a variable we input at the beginning
So if it's two we're going to split this into two if it's five we're going to split this into five which will kind of
Be over splitting this
arguably, but it depends when images come in then you might imagine splitting it into 256 so we can turn it into a
256-Color Palette image as an example okay, so the number of k is very much dependent on the situation
You're looking at so how do we do this? Well? What we do is. We have K averages for this data so K-means
That's how it works
So I've got myself a couple of squares of paper here, [but] I'm going to use with my mean position
So I'm going to have this as mean position one
and this is mean position two now if I was to calculate the mean position of all of this data this one is going to
Be somewhere in the middle and what K-means is going to do is
partition this into two and then calculate the means and
then we partition it based on those means and try and iteratively work out where the
Ideal means should be so let's start number one over here and let's start number two over here
We want to partition this data into these groups
It's probably going to put a partition somewhere around here, and maybe this is going to be in group two
So these these will be decided you know depending on which their nearest to and so that's our initial segmentation
Which is pretty poor because put a line straight through the middle of this data, and it's no it's not really any good
But it's a start and so then what we do is. We say what we've got all of these in group one
So what is the actual average position of these and maybe this one's in group one as well?
So it remember moves just down there a little bit. Just just tweaks a little bit now this one
It's got quite a lot of these in it, so this is going to come up a little bit
So that's step one, right?
so we partition them into these two means and
Then we move the means a little bit based on how these new partitions. [have] formed for now. Let's assume
We've picked one [and] two at [Random]. We might talk a bit about how you initialize them in a minute, but for step two
We do the exactly same [thing] again
So we say well now look the data has changed somewhat okay, so I'm gonna use [my] green pen now
So maybe these ones are now closest to one and these ones are now closest to two
So we're getting there, okay?
so then we
Reclassify them and we compute the means again and [to] comes up here and one comes a bit down here
and then we do it again and two comes over here and one comes over here and
Gradually we settle on the optimal mean position for our groups, okay?
And then what that finally means is we put a big nice line between these two bits of Data, okay?
which is exactly what we wanted is it possible they could get it completely wrong good question yes
So absolutely right?
So if I was if I was putting in one and two at Random [so] for example if I put one and two over here
Okay, you might imagine a [situation] where if we're drawing a line down like this. They're kind of evenly distributed
There's no real pull [right] away, and they just kind of get stuck there okay, so that could happen all right?
So often what we might do is run K-means a few times with different starting positions, and then pick the best one okay?
Pick the best one as in each of the ones in this cluster a nearer to one
Than they would be in this situation what we sometimes do is instead of picking these at random because you know if I put over?
Here that's not hugely helpful. It's just going to take longer to
Converge on a solution what we sometimes do is pick two points as our starting positions
So I could pick a point here and a point here [now]. [that's] not going to [necessarily] completely solve the problem
You know [if] you pick really bad points that might be a problem, but on average
It's going to work out okay, okay?
There are other there are other
Initialization methods like amy's plus plus and things like this you can read about that do slightly more complex things
But the very general idea is we have an guess how to separate our data
We separate it and then we calculate the centers of those regions
And then we repeat that process to try and converge on a good separation and K-Means is very effective. You know
It's simple really simple two steps basically move these points into one of the two classes and then we compute the means and just do
That over and over again now
This is [two-dimensional] data x and y, but there's no reason it couldn't be free or for five dimensional data
Right which I can't draw a five dimensional
Than what that's called, but you know a five dimensional object here on the paper
I could barely draw a three dimensional one so but in in an image of course we've usually got three dimensions [RG] and B
So what we have is we [have]
One mean for the red position and one mean for the blue position and one mean for the green position and we're trying to move
Around these in this color space trying to find
What are the dominant colors so K-means on an image will not only tell you?
Which pixels belong to which of the three classes or four classes or five classes?
It'll also tell you what's the average color of those classes, so [then] we can simplify our image
So if you wanted to compress an image for example and change it to say [sixteen] colors
Right then you would [just] split it into K clusters. Where K is 16
And then those dominant colors are what you're going to pick and it will look kind of like the original image not great
But you know people are used to seeing compressed images like this you know on the internet
So let's look at some moods and see what it does you could pick any initial image to do this to my eye
There's maybe three or four dominant colors here. There's green obviously blue and black and to a lesser extent white
I suppose because of these clouds or gray what we will do is we will pick three
Pixels of random okay, and they will be the initial values for our means okay, so let's imagine
I'm splitting this image into three because I think maybe there are three dominant colors
So I pick I have three means instead of just number one
I have [a] two and a three they get started at random with Random RGB values
And I cluster the whole image into those regions one two or three
Then I recompute these mean values and I cluster again, and I recompute [the] mean values [in] my cluster again
And this is what happens on this image for a k of three
So we've got the black or very dark green down here [like] Green Gray blue sky
So that's done. Exactly what we hoped. It would do okay it split
the image into three if we start to increase the amount of
Classes, we can slowly start to improve the image and maybe start to get towards what the original image actually look like this is eight
Classes you can see that now. We're starting to see what we were looking at before
There's now a difference between the cloud in the sky and quite a lot of difference now on these bushes here, okay?
And as we go up it gets better and better [now] on 256 colors
We've had a problem here [with] some of these have [been] put into a weird cluster
But that's just what happens sometimes with K-means do we initialize it?
But you can see that actually the [sky] [is] now looking quite a lot like it did originally because we've got lots of different colors
That we can represent it in terms of image processing we might segment this image to try and find the dominant objects
In this image, it's not hugely helpful because even in
Even with a few classes. We've got objects all over place
We can't for example pick out the trees particularly well because the trees are the same color as a grass
And the same [colors] [as] [brees] bushes here. So doesn't really help us, but it depends on the image
You're using if there was a red bus and nothing else in the image was red
We could pick that class out nicely so it depends on the situation
Going forward. They're [a] much more complicated segmentation approach it. So things like super pixels that we can talk about another time
They're trying group coherent regions of the image locally so they're bringing spatial information into it as well
Which makes a lot more sense because our bus isn't going to be distributed in the red throughout?
The image is going to be in a box so we can start to look for things like that. I
Did particular implementation in Matlab because Matlab can do this in [about] five six lines of code?
We can make that available in the comments
So if you want to see the Matlab code that does this it uses the inbuilt K-means function of Matlab so I didn't have to
Work too hard to get it to work, and if you haven't got a matlab license octaver also do this using the same code
So you can have a go?