In elbow curve how to find the point from where the curve starts to rise?

Question

I am computing a distance metric on my data. The result is then being sorted in ascending order. The samples having distance more than a specific threshold are to be marked as outliers and will be discarded. Below is a plot of all distance values.

As evident from the graph, after a certain point, the graph rises quite rapidly and even the datapoints get sparse. I need to calculate that point from where this happens and mark that point as threshold value.

Answer 1

TL;DR

Use the two functions from below to get the index of the elbow:

elbow_index = find_elbow(data, get_data_radiant(data))

Edit: I put all of the code below into a python package called kneebow. Now, you can simply do it like this:

from kneebow.rotor import Rotor

rotor = Rotor()
rotor.fit_rotate(data)
elbow_index = rotor.get_elbow_index()

Long Answer

If this curve is representative for all of the curves (e.g. unimodal and continuous) then a quick and dirty method is to rotate it to some degree and simply take the minimum value.

The rotation can be done by multiplication with the rotation matrix

$$\left( \begin{array}{cc} \cos\theta&-\sin\theta\\ \sin\theta&\cos\theta \end{array} \right)$$

where $\theta$ is the desired angle in radians.

In python, you can do this with the following function:

def find_elbow(data, theta):

    # make rotation matrix
    co = np.cos(theta)
    si = np.sin(theta)
    rotation_matrix = np.array(((co, -si), (si, co)))

    # rotate data vector
    rotated_vector = data.dot(rotation_matrix)

    # return index of elbow
    return np.where(rotated_vector == rotated_vector.min())[0][0]

Note that theta is the angle in radians. You can caculate that by np.radians(angle).

Important: One thing to remember is that the x- and the y-axes may have different scales. So on your plot, it may look like a 45° rotation would be enough, while actually, it is not. Therefore, you can use the following function to calculate which radiant you should use. It takes the slope from the minimum to the maximum values in your data and converts it to radians:

def get_data_radiant(data):
  return np.arctan2(data[:, 1].max() - data[:, 1].min(), 
                    data[:, 0].max() - data[:, 0].min())

If you want to get the angle, run np.rad2deg(get_data_radiant(data)).

Example

How to use

Let's test the approach on a sample data similar to yours:

# Let's define our sample data:
data = np.array([
    [1, 1],
    [2, 2],
    [3, 3],
    [4, 4],
    [5, 5],
    [6, 6],
    [7, 7],
    [8, 8],
    [9, 16],
    [10, 32],
    [11, 64],
    [12, 128],
    [13, 256],
    [14, 512]
])
# y is linear until (8,8) and increases exponentially afterwards

plt.scatter(data[:, 0], data[:, 1])

Plotting the data gives us the following figure:

Now, let's try to find the elbow by combining the functions from above:

elbow_index = find_elbow(data, get_data_radiant(data))

print(elbow_index)        # 10
print(data[elbow_index])  # array([11, 64])

In Detail

To sum it all up, we just calculated the slope from the min to the max value and then rotated the plot in such a way that the slope was zero. Subsequently, we took the min value of the data to get the elbow.

We can get the angle of rotation the following way:

angle = np.rad2deg(get_data_radiant(data))
print(angle)  # 88.543

The plot on the left has the slope included as an orange line. The scales of the axes make it look like it would have an angle of 45° while in reality, it has an angle of 88.5°! After vector rotation, the data looks like the plot on the right. From this data, we took the minimum value which was the 11th data point.

Drawbacks

Note that this method has a drawback: The more inequal the scales of your axes are, the more it will choose points in favor of the larger axis.

You can try to use the scikit-learn MinMaxScaler to scale your data before you use this method in order to reduce this effect. If you use the kneebow package, the data gets scaled by default.

Answer 2

I copied the user, rafaelvalle's code:

# Find Elbow Point, Trade off Point
def elbow_point(data):
    curve = data
    nPoints = len(curve)
    allCoord = np.vstack((range(nPoints), curve)).T
    np.array([range(nPoints), curve])
    
    firstPoint = allCoord[0]
    lineVec = allCoord[-1] - allCoord[0]
    lineVecNorm = lineVec / np.sqrt(np.sum(lineVec**2))
    vecFromFirst = allCoord - firstPoint
    scalarProduct = np.sum(vecFromFirst * np.matlib.repmat(lineVecNorm, nPoints, 1), axis=1)
    vecFromFirstParallel = np.outer(scalarProduct, lineVecNorm)
    vecToLine = vecFromFirst - vecFromFirstParallel
    distToLine = np.sqrt(np.sum(vecToLine ** 2, axis=1))
    idxOfBestPoint = np.argmax(distToLine)

    return idxOfBestPoint