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?
