I have a graph where I need to find a particular point based on sampling

Question

I currently have a graph which looks something like this:

Now I have discrete data that represents the Number of Clusters(the x values), giving us the Average Cluster Distance (the y values). There is only a single elbow point, after which the values just descend to 0. Finally, I do know the maximum amount that K can take (the x domain). Based on this I have three questions:

• Is there a way I can find the value of the elbow point through differentials (first or second order)?

• In which case, what is the smallest sampling rate that will allow me to get a graph with the desired characteristics? I don't care too much about the accuracy as of right now (though I would like to know some kind of a tool that lets me measure the error). If I cannot use differentials, I am still interested in understanding how I could recreate the graph with the lowest sampling rate, and thus find the elbow point with the least amount of processing (For E.g. Nyquist Theorem, I would have 1/2 the amount of elements and still recreate the signal).

• Finally, would incorporating random selection into the selection of the signal help me in any way?

Answer 1

Is there a way I can find the value of the elbow point through differentials (first or second order)?

Yes.

The point you are looking for is the first one for which the first derivative drops to zero. The first derivative gives you the rate of change of your curve. When the curve becomes flat, the curve neither increases and neither decreases. Therefore its rate of change is zero. Technically, what you are showing there is a knee (or even a toe). Not an elbow. The knee is a convex point at the bottom of a (usually sigmoid) curve and the shoulder is the concave point at the top of the curve. These are simple approaches. In the context of your problem and in the presence of noise things can get a bit more complicated.

In which case, what is the smallest sampling rate that will allow me to get a graph with the desired characteristics?

If $K \in \mathbb{Z}$ (i.e. K is an integer), "sampling rate", in the sense of obtaining a "finer grid" of the X-Axis, is indefineable. You cannot have 0.5 clusters (using the standard meaning of a cluster).

I don't care too much about the accuracy as of right now (though I would like to know some kind of a tool that lets me measure the error). If I cannot use differentials, I am still interested in understanding how I could recreate the graph with the lowest sampling rate, and thus find the elbow point with the least amount of processing (For E.g. Nyquist Theorem, I would have 1/2 the amount of elements and still recreate the signal).

We established that if $K \in \mathbb{Z}$ then this concept of "accuracy" is invalid. BUT, if you find yourself in the position of having to select a $K$ and your computation of $K \in \left[a \ldots b\right], b>a$ is taking too long, maybe you can "sample" the interval between $a$ and $b$ and then fit a low degree polynomial that is "guessing" the rest of the points.

So, in your example and assuming that this is more or less the way by which distance changes with number of clusters, you could do your k-means for $K \in \left[1,3,7\right]$ and then fit an exponential decay of the form $y = N \cdot e^{-c \cdot K}$, where you have the $K,y$ and you are looking for $N, c$.

In this case, it would be valid to be talking about accuracy of finding a knee point on the polynomial curve that has been optimised by a few "experimental" data.

Finally, would incorporating random selection into the selection of the signal help me in any way?

I am not sure how "Random Selection" would help you here. Given that K-means includes the initial random assignment step, it might be better to repeat each $K \in \left[a \ldots b\right], b>a$ for a number of times rather than randomly pick a few values across your interval.

Hope this helps.

Answer 2

Based on the graph you posted and the elbow defined, all you have to do is to take the first difference of the signal and compare it to a threshold value, assuming that the signal is monotonically decreasing. Such as this:

if( (y[k] - y[k-1]) < Th )
          elbow = k-1

if the signal is not monotonically decreasing, you should look for other measures as well.

Sorry but I cannot tell the required sampling rate for this graph as you stated it comes from an already discrete data...?

Answer 3

The term elbow is an anatomical one, so it needs to be defined in a numerical way. Looking at your plot, it would appear that the points to the left and the right to your “elbow” are points from two smooth continuous functions, and the elbow would be a place where they intersect. One might propose that at the intersection elbow point, the first derivative would be discontinuous.

This may or may not be a good model. If your points are noisy, it would complicate any approximate derivatives based on numerical differences.

A more dense sampling would help but if the model is wrong, so is the approach. You also have to accommodate elbows that are near the ends of your data, which leads to another possibility that not every case may not have an elbow.

The answer provided by @Fat32 is a workable solution but I suggest you do it in both directions.