If we use a modeling method like K-means or Gaussian mixtures to define our clusters, this is relatively straightforward: The model assumes that each cluster of data points is sampled from a Gaussian blob and the model consists of the centroids of these blobs. If we’re using a Gaussian mixture, the model will also include the variance and covariance values for each blob. For K-means, we can calculate the variance by adding up the squares of the distances from a given centroid to each data point associated with it, then taking the square root.

The variance tells us, roughly speaking, the radius of each Gaussian blob. This is indicated by the length of the green line on the left in the Figure below. If we have two overlapping Gaussian blobs, i.e. blobs whose variance/radius values are much larger than the distance between their centroids, as on the right in the Figure, then when we sample points from them, it will look very similar to what we would get from a single elongated Gaussian blob. So, if the K-means algorithm gives us two centroids whose variances are much larger than the distances between them, then we would surmise, even without being able to directly look at/visualize the data, that the two Gaussian blobs should really be replaced by a single cluster.

So, this gives us a very simple quality measure for the clusters discovered by K-means: For each of the resulting centroids, we divide the variance of the points associated to it by the distance to the closest other centroid. If this number is very small, it indicates that the cluster is tightly packed relative to the rest of the data set, like we wanted. We can determine the quality of the overall set of clusters by either taking the average of these values over all the centroids, or taking the maximum value. Since the results of both K-means and Gaussian mixtures depend on both the number K of clusters and on the initial starting points, this value is often used to compare different sets of clusters and different numbers of clusters returned by the algorithm.

For example, one might run K-means 100 times for each value of K from 1 to 10, using randomly chosen initial centroids each time. That produces 1000 different possible sets of clusters. Since we only want a single set of clusters, we can measure the quality of each set of clusters as above and choose the one with the lowest value. Note that this gives us a fairly sound way of choosing the value of K, which we otherwise would have had to either guess, or choose based on domain knowledge, etc.

But if we’re interested in more general types of clusters than just Gaussian blobs, such as the ones shown on the left, things aren’t so simple. Since clusters may be elongated and curved, the centroid/center of mass of cluster may not be a good representative of the clusters. In fact, it’s even possible that the centroid of one cluster will be contained in another cluster, as with the cluster circled in blue. This example may seem far fetched, but most real world data sets aren’t made up of Gaussian blobs, so only looking at centroids and variances isn’t enough.

In other words, we need measures that do not assume the data fits a specific model. For example we might try to measure the density inside a set of clusters compared to the density between clusters. This is more or less what the DBSCAN algorithm does, except that as we noted in the previous post, DBSCAN requires setting a hard cutoff for the density, then calculates the clusters accordingly. What we’re looking for is a way of comparing the inside and outside densities for a given set of clusters.

The key to this problem is finding a meaningful baseline. For the variance/distance measure for the Gaussian blobs above, we are comparing two distances, so the number that we come up with will be comparable between data sets. If one data set has a lower value than the other, then we could legitimately say that it has more tightly packed clusters. In particular, if we scale the data set (i.e. multiply every vector by the same number) then this ratio won’t change. So, we want a similar measure for general clusters.

The normalized mean cut from last week gives us a good way of comparing clusters within a data set, but it does not give us an objective baseline to compare clusters between data sets. Essentially, this is because we’re comparing area (the cross section of the bottleneck) to volume (the number of vertices or edges on either side of the cut). For example, in the Figure below, each of the two graphs can be cut along three edges to form two clusters of seven vertices. So the best (normalized) cuts in both graphs have the same areas and volumes. However, while this picks out an obvious bottleneck in the graph on the left, the graph on the right doesn’t have a bottleneck at all. If we were to run spectral clustering on these graphs, and calculate the normalized mean cut values, we would get the same number for both of them, so it wouldn’t tell us whether or not there is a bottleneck.

One alternative measure that is much closer to the idea of comparing densities inside and outside a subset of a graph is what’s called the modularity. This idea is popular in network analysis, though it doesn’t seem to have filtered into data mining/machine learning quite as much. The idea is to compare the number of edges inside a cluster to the number of edges we would expect to find between similar vertices in a randomly constructed graph that has that same overall number of edges as our original graph. If there are a lot more edges in our cluster, that indicates the cluster is more densely packed than the rest of the graph. But the question is, how many edges would we expect to find between a similar collection of vertices in a similar graph with the same number of edges?

We can think of the expected number of edges as an expected value in the sense of probability: We consider all possible outcomes and average them, weighted by how likely each outcome is. Here, the possible outcomes are the possible graphs that we can get by connecting the vertices of our given graph in different ways. We’ll want to take into account the number of edges that initially go into each vertex, i.e. its valence, since this will make a big different in our expectation value.

So, given our initial graph, we’ll record the number of edges that go into each vertex. Then we’ll look at all the different ways of connecting the vertices by edges, so that each vertex ends up with the same number of edges going into it as it had originall. For each of these graphs, we’ll count the number of edges between the vertices of our original cluster. Then we’ll take the average of all these numbers and compare it to the actual number of edges in our cluster.

In practice, we don’t actually have to construct every possible graph in order to calculate the expected number of edges; there’s a relatively simple formula that will tell you the number we would get if we did form all possible graphs. This leads to a fairly simple formula for the modularity, which you can read about on its wikipedia page.

The important part is that modularity gives us a good measure of how well separated a given cluster is from the rest of the data set. It makes a very good analogue of the distance vs. variance measure for the clusters found by K-means, except that modularity will work on general clusters, rather than just Gaussian blobs. One thing to note is that modularity is measuring something closely related to the relative density of each cluster, rather than the bottlenecks that spectral clustering was looking for. Next week, I’ll introduce a way of measuring clusters (and an accompanying clustering algorithm) that gets much closer to the idea of measuring bottlenecks.

But first, lets take a minute to think about what a cluster would look like in a graph. Remember that we want to think of the graph as representing a probability distribution made up of a number of different connected shapes, as in the Figure below. Here there are clearly at least three different clusters, though the lower two overlap slightly. We get the data set in the middle by randomly picking points, such that the points in the darker parts of the probability distribution are more likely to get picked. Then we form the graph on the right by connecting nearby points by edges, without knowing what the shapes that made up the distribution were. If these shapes overlap slightly, as the bottom two clusters do, then we will be forced to connect points from the different clusters and the graph that we get will be connected.

However, as in the picture, the places where the clusters overlap will often be thinner than the in the middle of the clusters. In other words, these spots are bottlenecks: If we were doing the morning commute between edges in the graph, we would be able to tell roughly where the transition between clusters is, because that’s where traffic would be the slowest. That’s where lots of lanes would merge into just a few.

This might be more intuitive in terms of social networks. Recall that a social network defines a graph in which each vertex is a person and edges connect any two people who “know each other” (i.e. are facebook friends, twitter followers, etc.) The clusters in a social network are communities: Any two people within a community are very likely to know each other, so there will be lots of edges within each community. Most people in a community will also know people outside of the community, so there will be edges between different communities, but not as many of them. (This is complicated by the fact that people can belong to multiple communities, but lets not worry about that for now…)

In a social network, the traffic is news, opinions, information, cat pictures, etc. Information spreads quickly within each community because there are lots of connections. It also flows between communities, but much more slowly, since there aren’t as many people who connect different communities and they can only transmit a limited amount of information. In other words, the bottlenecks in social networks are what reduce communication between different communities/clusters.

So in order to look for clusters in connected graphs, we need to define exactly what we mean by a bottleneck. In general, given any two vertices in a graph, there will be a lot of different paths that the traffic between them can take. So it’s difficult to find a single edge with a lot of traffic. But we can find sets of edges that, when removed, will separate the graph into two pieces/components. Any traffic between those components will have to go across one of the edges, though we don’t know which one.

To make things simple, lets pretend that there is an equal amount of traffic from each vertex in the graph to any other vertex. If we choose edges that only cut off a few vertices from the rest of the graph, such as the purple edges on the left of the Figure below, then there won’t be much traffic that wants to get across the edges, and they won’t make a bottleneck. (Think of the bridge to nowhere in Alaska.) On the other hand, if there are a lot of vertices on both sides of the edges, as on the right of the Figure below, then the edges will have a large amount of traffic. (Think of the bridges that divide Manhattan from the rest of New York.)

So in order to find a bottleneck in the graph, we want to find a relatively small number of edges that divide the graph into two pieces, each of which has a lot of vertices. There are a few different names for such a set of edges, each of which has a slightly different meaning and is used by different people. If E is the number of edges and N, M are the number of vertices on each side then the min cut max flow (which comes from optimization theory) is the set of edges that minimizes E/NM. Note that NM is the number of pairs of vertices on opposite sides of the cut. The normalized mean cut (which comes from computer science) is the set of edges that minimizes E/N + E/M (though, sometimes N and M are the number of edges on either side, rather than the number of vertices.) In mathematics/geometry, the Cheeger constant is the minimum value of E/N, for N < M. All of these terms are sometimes used interchangeably, or with slightly different meanings.

In practice, the small differences between these terms doesn’t matter because there is no computationally efficient way to compute any of them. Essentially, the only way to find the set of edges that achieves the min cut max flow/normalized min cut/cheeger constant is to try every possible combination, which makes the problem NP complete. (In other words, it’s impractical to run it on any data set bigger than perhaps a few hundred points.)

Instead, the usual approach is to approximate them, i.e. to find a set of edges that has a pretty good value for E/NM or E/N + E/M. Since we only need to get a rough idea of where the clusters are, this will be good enough and is computationally more efficient. This is where the physics comes in.

When you play a stringed instrument like a guitar, the sound that you hear is caused by each string vibrating in a very specific manner determined by its weight, length, tension, etc. The pattern of vibration is very complicated, but it’s actually made up of a small number of very simple patterns, namely sine waves with different wavelengths, as on the left in the Figure below. The longest one has a single hump in he middle. The next longest has two humps (one above and one below), then there’s one with three humps and so on. The frequency at which the humps move up and down depends on how many there are, and thus how short they are. The wave with one hump has the lowest frequency. The one with two humps has twice that frequency and so on.

Something very similar happens when you hit the head of a drum: The drumhead vibrates, with different points moving up and down in some complicated pattern. Again, this pattern is made up of a number of relatively simple patterns, moving at different frequency, but that look complicated when you combine them. The patterns in these waves are determined by the shape of the drum. Most drumheads are round, but there are also square drums out there, and in theory you could make a drum in any shape that you want. Most importantly, you could even build drumheads in shapes that have bottlenecks, as on the right in the Figure above.

We wouldn’t have to build a physical drumhead to see what patterns of vibration we get from them. There’s a differential equation from physics, involving an operator called the Laplacian, that tells us how a drumhead of any given shape will vibrate. The idea is pretty simple: We can tell which way a point will be pulled by looking at the nearby points and whether they are above or below it. If most of the points are above then the point will accelerate upwards. If they’re below, then it will accelerate down. The differential equation allows us to analyze all the points in the drumhead like this at the same time, to figure out the possible patterns.

But here’s the key: If we do this for a drumhead like the one in the Figure with two blobs connected by a bottleneck, then for the lowest frequency wave, the points in one of the blobs will go up whenever the points in the other blob go down (as indicated in the Figure). In between them, there will be an arc of points that don’t move at all, right at the bottleneck. In other words, this arc of stationary points will be very close to the min cut, max flow arc.

The idea behind spectral clustering is that we can do something very similar with a graph: Pretend that the graph is a rigid object made up balls connected by springs. If we hit it with a mallet, it will begin to vibrate in a pattern that is determined by an equation very similar to the differential equation for the drumhead. In this case, we can figure out whether each vertex will be pulled up or down by looking at the vertices that it is connected to by edges.

We end up with an equation defined by a matrix whose rows and columns corresponds to the vertices of the graph. This matrix has a lot in common with the covariance matrix that we saw in the post on principle component analysis (PCA), and in particular the eigenvectors of this matrix will tell us the simple patterns that make up the vibration of the graph.

Like the drumhead, if the graph is made up of a number of clusters connected by bottlenecks, then the low frequency vibrations will be divided into vertices that are moving up and vertices that are moving down. And it turns out that the edges between these two sets will be very close to the min cut max flow/normalized mean cut/cheeger constant. As we discussed above, they won’t be exactly the best, but they will often be close enough to give us a rough idea of the clusters. So, the spectral clustering algorithm consists of forming the matrix that defines the vibration, then calculating its lowest eigenvector, and returning the two clusters defined by the upward moving vertices and the downward moving vertices. The term spectral refers to the fact that the whole list of eigenvectors (or rather their eigenvalues) can be thought of as the spectrum of frequencies that the graph vibrates at.

The first thing to note is that unlike DBSCAN and mapper, spectral clustering does not explicitly rely on any parameters that determine the scale. However, these parameters are really just hidden in the step where we construct the graph, when we decide the rule for which vertices to connect. But in practice, this approach tends to do well over a wide range of parameters, so it is not as important that we pick the parameters just right.

On the other hand, there are some drawbacks to spectral clustering compared to DBSCAN and other methods. The main drawback, and probably the main reason that it isn’t more widely used is that finding the eigenvectors of a large matrix (which is the core of the spectral clustering algorithm) is slow and memory intensive. This makes it hard to scale the algorithm to large data sets.

The drawback that is more troubling from a theoretical perspective is that the spectral algorithm doesn’t tell you if the clusters that it finds are actually any good. With DBSCAN, we know that there is a real separation between the clusters that it finds. If the data set didn’t have clusters, then DBSCAN would either return a single cluster containing all the data points, or a large number of very small clusters. Spectral cluster, on the other hand, will always give you two roughly equal clusters. (There are ways to make it find more than two clusters, but that’s for a future post.) For example, if the data set is a Gaussian blob, spectral clustering will find a relatively efficient way to cut it in half, but it won’t tell you that the cut isn’t actually a bottleneck. So, depending on how you plan to use the clusters, you may need to do further analysis to see if you’ve found legitimate clusters.

We’ll start off by returning to the basic clustering algorithm I introduced last week: Recall that this algorithm works by starting with a parameter d and forming a graph with edges between any two data points whose distance apart is less than d. The clusters returned by the algorithm are the connected components of this graph. These clusters can change drastically if we give it a different value. But if there are clusters that show up for many different values, this would tell us that whatever structure was defining these clusters could be seen at a lot of different scales, and was thus significant. Of course, we can’t try every single value of d (since there are infinitely many of them) but the basic clustering algorithm is fast enough that we can pick a (finite) number of different values and try them all.

The question is, can we organize the results in a way so that we can understand how the different clusters are related? To see how to do this, we have to consider what happens when we increase or decrease d. Recall that the basic clustering algorithm implicitly creates a distribution representing the data set, by placing a ball of radius d around each data point, as in the Figure below. (This is shown in 2D. As always, this is really happening with higher-dimensional balls in a higher dimensional space.) The clusters are then defined by the connected pieces of this distribution. If we increase d then these balls will get larger. Balls that already overlap will continue to overlap, but some balls that were separated might bump into each other. If this happens then two clusters defined by the smaller value of d will become a single cluster for the larger value. In the Figure, this happens twice: First when the two single points on the left join together from step one to step two. Second, when the two large clusters combine between step three and step four.

In other words, as we turn the dial that controls d, the balls increase in size, so the clouds of foam that they create gets bigger and bigger. When two clouds bump into each other, they merge together. So as d increases, each cluster gets bigger and the number of clusters gets smaller. In order to organize these changes (without being able to actually see what’s happening in higher dimensions) we use what’s called a dendrogram.

First, we pick the values of d that define the different scales that we want look at. For simplicity, lets say we’ve picked the values 1, 2, 3, 4 and 5. We’ll mark these values along the y-axis. Next, we’ll calculate the clusters at the first value of d by drawing edges between any two data points that are distance at most 1 apart. For each of the resulting clusters, we’ll draw a point in our diagram at height 1, but we’ll space them out left to right so we can see them all. Then we’ll do the same thing for d = 2, drawing the new points at height 2 and so on.

For small values of d, there will be a lot of points along the horizontal line, while for larger values of d, there will be only a few. In fact, if we pick d to be large enough so that all the data points are connected, there will be just one. As noted above, each cluster for a given value of d is contained in a cluster for the next highest value; It may be the entire cluster at the next step, or it may have merged with some other clusters. Either way, we will connect each point corresponding to a cluster to each point at the next level corresponding to the cluster that contains it. So each point at height 1 will be connected to some point at height 2. Each point at height 2 will be connected to exactly one point at height 3, but may be connected to more than one point at height 1. The dendrogram that comes from the data set and the values of d in the first Figure is shown on the right. The three points on the bottom horizontal line correspond to the three clusters on the left of the first Figure and so on.

This tree captures the basic information about how the clusters merge as we increase d. In particular, if we have a very long line of edges without any branches, as on the right in the dendrogram above, then this corresponds to a cluster that doesn’t change as we increase d, so as mentioned above, this probably means this cluster defines a significant feature of the data’s geometric structure.

However, as I mentioned last time, the basic clustering algorithm isn’t used very much in practice because it only works well on very homogeneous data (where the density is relatively consistent). The DBSCAN algorithm is a generalization of the basic algorithm that is much more common. But it relies on two parameters instead of one: a distance d and a density K. It would be nice if we could make something like a dendrogram for DBSCAN, that would allow us to understand how clusters change when we vary two parameters instead of just one.

This is the idea behind the mapper algorithm. Mapper is not as commonly used as most of the algorithms I’ve discussed in previous posts, so it hasn’t been implemented in the standard data analysis libraries like R, SciKit and ELKI. But there is a very nice open source implementation in python written by Daniel Müllner and Aravindakshan Babu. As mentioned above, this is also the algorithm behind the (proprietary) software developed by the topological data analysis startup Ayasdi.

In order to understand how mapper works, first note that each edge in the dendrogram we constructed above corresponds to a particular range of lengths in our original data set: Each edge from height 1 to height 2 corresponds to a number of edges that were added when we changed d from 1 to 2, so all these edges have length between 1 and 2. We can therefore construct something very similar to the original dendrogram as follows: First attach all edges of length at most 1 between the data points, calculate the clusters and draw the points on the diagram along the horizontal line at height 1. Now throw away all those edges between the data points and draw in the edges of length between 1 and 2. These will give you new clusters that are much smaller than the old height-two clusters. In fact, there may be a lot more of them as well. But nevertheless, we’ll draw those along the horizontal line at height 1. Then, draw a line from each point at height 2 to each point at height 1 whenever the corresponding clusters share a data point.

If we choose the values of d too close together, the resulting graph may look quite ugly, with too many points at each horizontal level. In practice, though, it seems that in most cases one can choose them so that you get back the original histogram. But the real fun starts when we add a second parameter such as density. There are a number of different ways of calculating the “density” of a data point (or rather of the data set around that point). To keep things simple, you can think of the density as being one divided by the distance to the 10th closest data point (where 10 was chosen arbitrarily). So the farther away the 10 closest neighbors are, the lower the density.

We’ll also choose a number of values for the density parameter, say 1, 1/2, 1/3, 1/4 and 1/5. We can then form a graph much like the second form of the dendrogram above, but using both parameters: First draw an edge between any two points with density at least 1 that are distance less than 1 apart, and draw a point for each cluster. This time, we won’t insist on putting them on a particular horizontal line. Then erase the edges that we just drew between data points and draw in edges between any two vertices with density at least one that are between distance 1 and 2 apart. Draw points for the resulting components and connect them to the points corresponding to the previous round of components whenever two have a data point in common. We’ll then erase the second round of edges from the data points and repeat the process with edges between points density between 1 and 1/2 that are distance less than one apart. (Note how this third round is different from the second round.)

This is getting a bit complicated, but hopefully you see the pattern: We form the components for all possible pairs of ranges for the two parameters and then connect the ones that both have points in common AND have overlapping parameter ranges. The result is a graph that looks kind of like a dendrogram, though it may no longer be a tree. Because this graph takes into account both the distances between points and the densities of points, this graph will usually capture much more information about the data set. In particular, it is more likely to see the less dense part of the data set that both DBSCAN and the basic clustering algorithm miss. Note that mapper doesn’t give you particular clusters the way that DBSCAN doesn, but it does give you a nice visualization of the data that includes cluster-like information.

In particular, most clustering algorithms will not attempt to determine the overall shape (i.e. the extrinsic structure) of each cluster – they will simply try to decide which points fall into which clusters. For this reason, clustering algorithms tend to focus on the intrinsic structure of a given data set, which as we saw last week can be encoded by a graph.

We’ll start out by looking at the simplest possible clustering algorithm. Like the nearest neighbors algorithm, which I used to introduce the idea of classification algorithms, this algorithm is generally too simple to use in practice. But it will be good for a warm up.

Recall that for a given data set in vector form, we can form a graph that represents its intrinsic structure by adding a vertex for each data point and adding edges between nearby data points, either connecting any two edges whose distance is below some threshold or connecting each data point to its K closest neighbors for some value K. If we do this to a data set that is made up of a small number of well separated clusters then we would expect each data point to be closest only to other data points in its own cluster. If this is the case then the vertices of each cluster will form their own separate graph (called a connected component) with no edges between the different clusters.

So our first naive approach to clustering will be to simply form a graph from the data set, then determine the connected components of the graph. If there happens to be a relatively small component that is disconnected from the rest of the graph then we’ll decide that it’s a cluster. (Incidentally, I don’t know if there is a name for this algorithm – As I said, it doesn’t seem to be used in practice.)

There are a number of immediate issues with this approach. The first is that it relies heavily on choosing the right method and the right parameters for building the graph. When we choose the cutoff for how far apart the vertices that we connect should be or how many closest neighbors to connect, we are essentially deciding what scale we want to look at the data at. You can think of forming the graph as applying a blur to the data set and connecting vertices whenever the resulting clouds overlap. The larger our distance threshold or our value K, the more we are blurring the points. So this is very similar to an issue that we discussed in the post on probability distributions. If we blur things too much then distinct clusters will end up overlapping and forming a single connected component. If we don’t blur things enough then the gaps between points in a single component may be big enough to separate the resulting graph, making one component appear to be many clusters.

It’s also possible that there will not be a single parameter value that separates the correct clusters without creating unwanted separations within individual clusters. This is the case, for example, with the Iris data set, in which the clouds of data points corresponding to two of the species are close enough that they overlap slightly. 

A second problem with this algorithm is that it is possible for a few stray data points, often caused by noisy data, to create unwanted connection between clusters. This is particularly a problem if we connect each vertex to its K closest neighbors – A stray data point that is half way between two clusters will form edges to vertices in each cluster, making them into a single connected component. This is what happens in the (oversimplified) data set shown on the left in the Figure below, which consists of two clusters of four points (one cluster on the left and one on the right) connected by a long chain of data points. The resulting graph would have a single connected component.

The DBSCAN algorithm is a modification of the basic clustering algorithm described above, designed to avoid these issues. (The acronym stands for Density Based Spatial Clustering of Applications with Noise.)  The basic premise behind the algorithm is that we expect each cluster to be defined by a probability distribution that is darker in the center and lighter near the edges. In other words, the probability of picking a point near the central core of the distribution should be much higher. (Note that the central core may be a complicated shape.) If we randomly pick a large number of points from the distribution, we’ll get points from both the central core and the outer edges, but we should be able to tell the difference between them because the outer edge points will be farther apart from each other. In other words, we can tell the difference by how dense the points are.

If two clusters overlap slightly, the overlap will be within the outer edges of the distributions, rather than the central cores. (If they overlap a lot then the central cores will overlap, but this situation is much harder to deal with, so lets not worry about it for now.) So the idea behind DBSCAN is to try and ignore the data points that are more spread out and focus on the dense parts, which should be the central cores of the clusters.

We still have to choose two parameters, which means that we have to make a judgement call about the “scale” that we want to work at. (The problem of picking the “correct” scale is more or less unavoidable – Next week, I’ll discuss methods that rely less on having the correct scale, but they will still be affected somewhat by parameters.) In fact, we will pick two numbers: The first number is a distance d, which determines how large of an area around each data point we want to look at. (This parameter is often called , but I’ll stick with Roman letters to minimize Greek-symbol anxiety.) The second number is a density value K.

We will say that a data point is dense if there are at least K other data points that are distance at most distance d away from it. This is roughly the property that we would expect points along the outer edges of a density distribution to have. The DBSCAN algorithm works by connecting all pairs of data points such that the the two data points are distance at most d away and one of them is dense. Then, as in the basic clustering algorithm that we started with, we take each connected component of the resulting graph to be a cluster.

To understand how this compares to the basic clustering algorithm, consider the example in the Figure above. The blue disk around each data point represents all points in the data space that are distance less than d away from that point. As noted above, if we construct a graph by connecting each data point to all other data points within distance d, i.e. within each blue disk, we will get a single connected graph. You can think of this as defining a distribution whose density function is made up of all these disks, i.e. the blue density cloud shown on the left of the Figure. This distribution appears to be made up of a single piece and, sure enough, the basic clustering algorithm will tell us that there is a single component.

If we run DBSCAN with K = 3 then only the data points in the two clusters will be dense. (Each of the data points along the path only has two other data points inside its blue disk.) The resulting graph will have two components, one connecting the four points of the cluster on the left and one connecting the four points of the cluster on the right. (Technically, it will have four components, since each of the two data points in the middle forms its own connected component with no edges, but DBSCAN will not mark these as clusters.)

Again, we can think of this as forming a density distribution made up of small disks around the points. But the distribution defined by DBSCAN leaves out the disks around the four points in the middle that aren’t dense, as on the right in the Figure. In this case, the resulting distribution has two distinct pieces and DBSCAN finds two distinct clusters.

Remember that we are assuming/pretending that there is an underlying probability distribution that produced this data set. Neither of the distributions suggested by either the basic clustering algorithm or DBSCAN will give us exactly the original distribution. In particular, the original distribution will probably have lots of grey-scale values, while the distributions produced by these two algorithms are black and white. The difference between the two algorithms is how they decide what to do with the apparent grey areas: The basic clustering algorithm makes all the grey areas black, by including points in the outer areas of the probability cloud in the distribution that it constructs.

DBSCAN, on the other hand, turns the grey scale areas to white, leaving the outer fringes of the distributions out of the distribution that it constructs. This means that some points may be left out all together, such as the points in the middle above. (These left out points are often called outliers and there’s a whole family of algorithms for the process called outlier detection.) So DBSCAN may leave some points out of the clusters that should ideally be in there. But that’s OK, since the goal of a clustering algorithm is to determine roughly where the clusters are, even if it doesn’t put every single point in the correct cluster. It’s much better to leave some points out than to combine multiple clusters that should be distinct.

DBSCAN seems to be a very popular clustering algorithm in practice (second only to K-means, which as I mentioned above shouldn’t be considered a clustering algorithm at all.) That’s because it is very fast, but still flexible enough that it tends to do a good job of finding complex clusters. There are limitations, of course: As noted above, the results rely heavily on the choice of parameters d and K. This can be fixed to a certain extent by running it multiple times with different parameters. The perhaps more important limitation is that it does not work as well on data sets where two clusters overlap more than just along their periphery, or where different clusters have different internal densities. (In the later case, DBSCAN might decide that a less-dense cluster is actually just a bunch of outliers.) In the next few posts, I’ll describe a number of other clustering algorithms that attempt to overcome these problems.

You can see a similar distinction with subway maps, such as the famous London tube map. This map records how the different tube stops connect to each other, but it distorts how the stops sit within the city. In other words, the coordinates on the tube map do not represent the physical/GPS coordinates of the different stops. But while you’re riding a subway, the physical coordinates of the different stops are much less important than the inter-connectivity of the stations. In other words, the intrinsic structure of the subway is more important (while you’re riding it) than the extrinsic structure. On the other hand, if you were walking through a city, you would be more interested in the extrinsic structure of the city since, for example, that would tell you the distance in miles (or kilometers) between you and your destination.

Data sets also have both intrinsic and extrinsic structure, though there isn’t a sharp line between where the intrinsic structure ends and the extrinsic structure begins. These are more intuitive terms than precise definitions. In the figure below, which shows three two-dimensional data sets, the set on the left has an intrinsic structure very similar to that of the middle data set: Both have two blobs of data points connected by a narrow neck of data points. However, in the data set on the left the narrow neck forms a roughly straight line. In the center, the tube curves around, so that the entire set roughly follows a circle.

If you were somehow shrunk down so that you could walk around “inside” the data set and could only see nearby data points, you might think of the two blobs in each data set as rooms, and the narrow neck as a hallway. If you walked from one room to the other, you might not notice whether or not it was curving. So as in the building example, you would have a hard time telling the difference between the two sets from “inside” of them. Thus the difference between the two data sets is mostly a matter of intrinsic structure, rather than extrinsic structure.

On the other hand, the set on the right has a very similar extrinsic structure to the data set in the middle: Both sets roughly follow a circle, so from far away, we might not notice the difference. However the data set on the right consists of a single circular neck/hallway, without any blobs. Thus the intrinsic structures of the center data set and the right data set are very difference.

As we noted above, in real life, we will sometimes be more interested in intrinsic structure and sometimes we’ll be more interested in extrinsic structure. Similarly, we will sometimes be more interested in the intrinsic structure of data set and sometime in its extrinsic structure. More precisely, we will be interested in both, but will focus more on one or the other at different stages in the analysis. For example, a simple model fitting algorithm, such as regression, logistic regression or SVM, gives us a description of the extrinsic structure of the data set by giving us a best fit hyperplane or a decision boundary. However, these algorithms don’t tell us anything about the intrinsic structure. In some sense, these algorithms assume that the intrinsic structure is relatively simple and can lead to very inaccurate models if it isn’t. So ideally, we would want to understand the intrinsic structure of the data set before we apply such an algorithm.

More flexible algorithms, such as KNN, neural networks and decision trees, are able to adapt to the intrinsic structure of a data set, and thus produce a more accurate model. (Though each algorithm has parameters that affect how flexible it can be in adapting to different intrinsic structures.) Of course, they encode the intrinsic and extrinsic structure in a way that is essentially unreadable by humans. Somewhere in the middle is the mixture model algorithm: The output of this algorithm reflects the extrinsic structure of the data set, but in order to use a mixture model, you first need to choose the types of simple models that will make up the mixture. This boils down to deciding what intrinsic structure we want the final model/distribution to have. If that intrinsic structure matches the intrinsic structure of the data set then the final model will be reasonably accurate. So again, an approach like this will work better if you first spend some time trying to understand the intrinsic structure of the data.

The distinction between intrinsic and extrinsic structure is closely related to the difference between local and global structure: The local structure of something is the structure that you see when you zoom in very close, while the global structure is what you see when you look at it from far away. For example, the local structure of your shirt is a tangle of crisscrossing threads. Its global structure is a two-dimensional shape with four holes (one for your head, two for your arms and a big hole at the bottom for your waist.) The extrinsic structure of an object is essentially the same as its global structure. However, an object’s intrinsic structure isn’t the same as its local structure. Instead, it’s more or less what you get by combining all the local structures and fitting them together. So the intrinsic structure of your shirt is also two-dimensional with four holes, but the intrinsic structure doesn’t know whether the shirt is folded up, hanging, or crumpled in a pile. The intrinsic/extrinsic dichotomy is also closely related to the difference between geometry and topology, but that’ll have to wait for a later post.

Note that some data sets don’t have a natural extrinsic structure, or at least not one that makes sense. For example, consider how we would analyze a data set of books based on their subjects. We can all agree that two books about physics will be very similar, and a book about chemistry will be slightly less similar to either of the physics books. However, it’s not obvious whether a book on poetry would be closer to a physics book than a book on management would be. In other words, it is clear what the distances between nearby books should be (the local/intrinsic structure), but not what the distances between far away books should be (the global/extrinsic structure).

We could define an extrinsic structure on books, for example by counting how many times each word appears in each book, and defining vectors based on this word count. However, it is unlikely that the resulting vectors would accurately reflect the structure that we want. There are various ways to modify this structure, such as by combining synonyms, disambiguating different uses of the same word, but there is no canonical approach. In fact, when data analysts choose these more complicated structures, the goal is essentially to find an extrinsic structure that best reflects the (relatively) well defined intrinsic structure.

Another example of a data set with no extrinsic structure is a social network: The connections in the network (friends on Facebook, followers on twitter, etc.) define the nearby points, similar to a subway map. However, there generally won’t be a natural extrinsic structure. (I’ll go into more detail about graphs and networks in next week’s post.) As with the books example, there are different ways to impose an extrinsic structure on a data set of this form, but there isn’t a single best extrinsic structure.

The main way in which the intrinsic structure of a data set is usually explored in practice is by searching for clusters, or clumps of data points. There are a number of different ways in which clusters are defined, and a corresponding number of algorithms for finding them, some of which I’ll cover in upcoming posts. Clusters can be densely packed sets of data points surrounded by less dense parts of the data set. Or, they can be blobs of data points that are either separated from the rest of the data set or connected by relatively thin bottlenecks, as in the Figure above. As you can see, both of these descriptions are in terms of intrinsic properties of the data set.

Up until now, the posts on this blog have focused primarily on extrinsic structure, with the goal of building models/distributions. These algorithms mostly fall into the category of supervised learning or predictive analytics: Building models that answer specific questions about data, by using a training data set for which the answer is already known. The next few posts will focus on unsupervised learning or descriptive analytics – methods whose goal is not to build a model or answer a specific question, but rather to better understand the structure as a preliminary step before building a model. Finding clusters is one of the main problems in this area and will be the focus of the upcoming posts. Throughout these posts on unsupervised learning, the intrinsic structure will be an underlying theme.

The basic idea behind the K-means algorithm is essentially a very restricted mixture model: We select a number K and create a mixture model with K simple models, each of which is a Gaussian blob. However, unlike in general mixture models where we allow each Gaussian blob to be a different size and to be stretched in different directions, as on the left in the Figure below, K-means requires that each blob be a fixed size and completely symmetrical (so no stretching), as on the right. You can imagine the sorts of complaints that this would face: Most data sets aren’t made up of symmetric Gaussian blobs of the same size. In fact, unless you miraculously scale your data perfectly, you’re pretty much guaranteed that it won’t be.

However, if the data is made up of well separated clumps, even if those clumps aren’t perfectly round and all the same size, K-means will often (though not always) be able to find them. (These “clumps” are often called clusters, but I’m going to leave a general discussion of clusters for a later post.)

So when you use K-means as a substitute for a mixture, you’re taking a risk that the final answer will be pretty lousy. The trade-off for taking this risk is that the algorithm is much much faster than training a general Gaussian mixture model. K-means still follows the two-step Expectation Maximization outline of a mixture model, but each step has been optimized to the point that you can barely tell where it came from.

First, note that since each of the Gaussian blobs in our mixture model is the same exact size and shape, the only information we need to record about each blob is its center. So our “model” will consist of K points spread throughout the data space. Recall that the first step in the Expectation Maximization algorithm is to assign each data point to one of the simple models (i.e. one of the Gaussian blobs) based on which one assigns it the highest probability. The probability that one of the Gaussian blobs assigns to a given point goes down as we get farther away, and all the blobs are identical. Thus each data point will simply be assigned to whichever center point is closest to it. That’s step one.

To understand what’s happening here, consider the data points shown in black in the figure below. We have a smaller number of blob centers, shown in blue. When we assign each data point to its closest blob center, this should remind you of the nearest neighbor algorithm. In the post on nearest neighbors, we noted that the set of all points that were closer to a given data point than to any other data point form what’s called a Voronoi cell around each data point. For K-means, we’ll get something very similar, except that the Voronoi cells are around the blob centers rather than data points. The Voronoi cells are outlined in blue on the left of the Figure. Each data point will be in the Voronoi cell around one of the blob centers, and we will assign it to this blob.

For step two, we need to adjust each of the Gaussian blobs to maximize the probability of all the points assigned to it. In general mixture models, this involves repeatedly adjusting the parameters using the notion of a gradient. However, if we’re not allowed to stretch the Gaussian blobs then we can immediately figure out exactly where to put them: We’ll want the point where we get the smallest possible number when we add up the distances squared from the center point to each of the data points assigned to it, i.e. all the data points in a given Voronoi cell.

In other words, if we take all the data points in one of the Voronoi cells and think of these data points as heavy balls connected by bars that hold them in place, we will want to move the center point of the Gaussian blob to the center of gravity of this structure. This center of gravity is called the centroid. As it turns out, the center of gravity is straightforward to calculate – you just take the average of the data values in each dimension. So for step two we move each Gaussian blob so that it is centered at the centroid of the points that were assigned to it in the first step. These centroids are shown in red in the center Figure.

Then we repeat – We go back through the data points and reassign them based on the new center points of the Gaussian blobs. (In other words, we form new Voronoi cells around the red points.) Then we calculate the centroids of each of the new subsets of data points (the points in each new Voronoi cell), then reassign the data points and so on.

After we repeat these two steps enough times, we’ll get to a point where step one assigns the data points to centers in exactly the same ways as the previous time that we ran it. So there won’t be a need to calculate the centroids again (since we’ll just get the ones we already have) and the K-means algorithm will terminate. In the Figure above, these would be something like the blue points shown on the right. It’s also common to run through the two steps a fixed number of times, rather than running it all the way to the point where the centroids stop moving, hoping that this will give you a reasonably good approximation of the final answer.

If the data happens to be separated into a certain number of well defined, tightly packed clumps/clusters and you happen to select K to be equal to this number then there’s a reasonable chance that the blob centers that the algorithm ends with will be the centers of these clumps/clusters. As always, we usually won’t be able to directly “see” whether or not this is the case, since most data has more than three dimensions. However, there are a number of measures that have been devised to measure how good K-means has done.

The most common one is to compare the distances between the final center points to the average distance from each data point to the center that it is assigned to. If the first of these numbers is much higher than the second then that means that K-means has found well separated clusters. Since the quality of the final answer depends heavily on picking the right value of K, this is often used to decide which K to use: Simply run K-means with different values of K and choose the one in which the difference between the two numbers is as large as possible.

Of course, this doesn’t solve the problem of what to do when our data set is not composed of a small number of well separated clumps. One of the main criticisms of K-means is that many (perhaps most) interesting data sets tend to have more complicated structures, so it would be naive to try using K-means on them. But like I said at the beginning of this post, I’ve now come to like K-means, nonetheless, by looking at it from a different perspective. In particular, I want to suggest using K-means for an off-label usage very similar to a technique from signal processing called vector quantization. This use of K-means has been suggested by others in the past, but doesn’t seem to be widespread. (It seems to be better known within the signal processing community, since that’s where the idea of vector quantization is well understood, but not as much within machine learning and data mining.)

Notice that the data set shown in the Figure above is not made up of a small number of round Gaussian blobs. In fact, it isn’t even made up of stretched Gaussian blobs, since one of clusters/clumps of points forms a curved shape. But you can see that the final blob centers found by K-means still reflect the structure of the data set, just in a more subtle way: We end up with three blob centers within the round cluster in the lower half of the data set and the rest of the blob centers forming an arc that follows the curved cluster.

To understand why this happens, note that each step in the K-means algorithm reduces the average distance squared from the data points to the blob centers. In other words, we can think of K-means as trying to place the blob centers so that each data point is as close as possible to some blob center. This has the effect of spreading the blob centers evenly around the data set, so the “shape” of the set of blob centers will be very similar to the overall shape of the data set.

So the blob centers found by K-means are very similar to a random sample of the original data set. However, there are two important differences: First, unlike a random sample, the blob centers are not in the original data set. One slight modification would be to take a sample of the original data set by choosing the data point closest to each blob center. Second, the blob centers are not random (though they do depend on the initial choice of centers, which are often chosen randomly.)

The blob centers have two important advantages over the original data: First, there are fewer of them, allowing one to run more sophisticated algorithms in a reasonable amount of time. Since K-means on its own is very fast, this would be a good trade-off. Second, the set of center points are less random than the original data set. In data analysis it’s common to think of randomness as being a good thing: We want random samples of our data to make sure it’s evenly distributed, and of course the field of Statistics is devoted to understanding all the facets of randomness. However, from geometric perspective the problem with random samples is that by their nature, they contain large gaps that can be mistaken for geometric features. This is a fundamental principle of randomness, and in fact you should be suspicious of any “random sample” that does not have both many large gaps between points and many points that are very close together.

One idea that has come out of numerical analysis (a field within mathematics) is that a homogeneous sample is often better than a random sample for large scale simulations. In other words, it’s often good to have data points that are “evenly” spread out within the probability distribution, but with more concentration in the darker parts of the density function. If we choose the number K of blob centers to be relatively large (though still much smaller than the number of data points) then the final set of points that K-means gives us should have this property: It will be relatively evenly spread out, but still have the rough shape of the original data set. So the set of blob centers can be used for the types of more computationally expensive forms of exploratory data analysis (which we’ll discuss in upcoming posts) whose goal is to understand the overall structure of the data well enough to decide what types of models and what types of kernels to use.

Another possible use for the blob centers is to use them as the anchor points for a Gaussian kernel. Recall from last week’s post that a Gaussian kernel is defined by choosing a small number of points in the data space. We want these points to be fairly evenly spread out, but close to the original data set. If we use all the original data points for make the Gaussian kernel then we are more or less guaranteed that our model will suffer from over-fitting. Thus the blob centers will often be a much better option for defining a Gaussian kernel.

So, that’s my take in K-means: If you think of it as a clustering algorithm, or as a substitute for a Gaussian mixture model, then you may be asking for trouble. However, I think that K-means has a great deal of unexplored potential as a quick way to reduce the data set to a relatively small number of representatives for us in exploratory data analysis or forming a Gaussian kernel.