Structure Discovery

Clustering

Clustering

• A type of Structure Discovery algorithm

• This type of method is also referred to as Dimensionality Reduction, based on a common application

Dimension reduction is used when we’re trying to take a number of dimension of data or data points and collapse them down into a smaller number.

Clustering

• You have a large number of data points

• You want to find what structure there is among the data points

• You don’t know anything a priori about the structure 

• Clustering tries to find data points that “group together”

You do not know what that structure is going to be. It is not like prediction models where you know you want to predict a certain outcome. With cluster, you do not know the structure, except as much as you pick variables that might express it. So imagine all of your data points, and there are some that are clustered down here and others that are clustered up here such that data up here are different from data here but similar to data close to it.

Trivial Example

• Let’s say your data has two variables

  • Number of video interactions

  • Unitized Time

Note: clustering works for (and is effective in)
large feature spaces

Clustering is good for really big feature spaces, where you have thousands of data points.

Example

So we have the number of interactions on the x axis and the united time variables on the y axis.

Example

And first we will talk about K-Means clustering. With K-means, it would says, well these five are our clusters. And I’ll talk about how we get those clusters in just a second.

So we have clusters that correspond to the different colored regions. Each of the clusters defines their own regions, and every points will fit within these 5 regions

Not the only clustering algorithm

• Just the simplest

• We’ll talk about fancier ones soon

K-means is not the only clustering algorithms, but it is the easiest.

How did we get these clusters?

• First we decided how many clusters we wanted: 5

  • How did we do that? More on this in just a few slides.

• We picked starting values for the “centroids” of the clusters…

  • Usually chosen randomly

  • Sometimes there are good reasons to start with specific initial values…

Do you remember the green and purple points? That is a centroid. Once selected randomly, then we will use this as a baseline to select better ones. For example, clusters from another dataset may provide good starting points for another datasets.

Example

So let’s choose five random points. None of them are at the center of clumps.

Then…

• We classify every point as to which centroid it’s closest to

  • This defines the clusters

  • Typically visualized as a voronoi diagram

Example

Voronoi diagram – you take every point and you classify it as being the centroid it is closest to, and then you draw a lines of equal distance to each of the centroids that correspond to the divisions in the space.

You can see that when you create the lines that are equal distance from the points, then you can clearly see the clusters.

Then…

• We re-fit the centroids as the center of the points in each cluster

So in other words, we set the centroids, we set the Voronoi lines to split the space evenly between those centroids, and then define the clusters based on where those centroids are and then we move those centroids to be the center point in the cluster.

Result

So this green dot moved from the side to more of the center, and same fro the other ones. But the orange one ends up in the middle of two points, so this is not a very good cluster.

Then…

• Repeat the process until the centroids stop moving

• “Convergence”

Now we’re going to repeat the process until the centroids stop moving. This is called convergence. So what we will do is that we will move the centroid, change the clusters, move the centroids to the center of the clusters, and repeat this process all over again until the centroids stop moving.

Result

So now we’re going to move the points to match the center of the cluster

Then..

Result

So we redefined the clusters, and you can see that red grabbed a couple of data points from orange.

Example

We move the centroids again.

Example

And again we redefine the clusters.

Example

And you can see here we, kind of converge the clusters. But then again, there are still some outliers, which don’t really fit the clusters.

Result

Same distribution of points, and now with a different configuration of centroids. So what’s the final outcome we will get?

Result

Not very good clusters. Purple clearly has two clusters that are being treated as one.

What happens?

• What happens if your starting points are in strange places?

• Not trivial to avoid, considering the full span of possible data distributions

One Solution

• Run several times, involving different starting points

• cf. Conati & Amershi (2009)

Exercises

• Take the following examples

• And execute k-means for them

• Do this by hand…

• Focus on getting the concept rather than the exact right answer…

• (Solutions are by hand rather than actually using code, and are not guaranteed to be perfect)

Questions? Comments?

Exercise

Solution Step 1

Solution Step 2

Solution Step 3

Solution Step 4

Solution Step 5

No points switched – convergence

Notes

• K-Means did pretty reasonable here

Exercise

Solution Step 1

There are five clusters, and the two points near the yaxis will move toward the center.

Solution Step 2

Solution Step 3

Solution Step 4

Solution Step 5

Notes

• The three clusters in the same data lump might move around for a little while.

• But really, what we have here is one cluster and two outliers…

• K should be 3 rather than 5

  • We will review this more in the next module.

Exercise

Solution

Notes

• The bottom-right cluster is actually empty!

• There was never a point where that centroid was actually closest to any point

Exercise

We have four centroids and three data clumps

Solution Step 1

Solution Step 2

Solution Step 3

Solution Step 4

Solution Step 5

Solution Step 6

Solution Step 7

Approximate Solution

Notes

• Kind of a weird outcome

• By unlucky initial positioning

  • One data lump at left became three clusters

  • Two clearly distinct data lumps at right became one cluster

Questions? Comments?

Exercise

Exercise

Four empty clusters and 1 core cluster in the end.

Notes

• That actually kind of came out ok…

As you can see

• A lot depends on initial positioning

• And on the number of clusters

• How do you pick which final position and number of clusters to go with?

Next module

• Clustering – Validation and Selection of K

Questions? Comments?

Closing thought

• How might you want to use clustering?