# Unsupervised Classification of Linear Trends

I have a data set which results in a series of non-parallel linear trends on a scatter plot.

I'm trying to find a way to classify each data point into its closest corresponding linear trend. There are six linear trends in this data set.

This blog post appears to have already done that using K-means clustering.

My attempt at clustering the data using K-means resulted in the following:

Here is the code I am using (as well as some dummy data):

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

data = {'a': {0: 2.0,  1: 3.0,  2: 4.0,  3: 5.0,  4: 6.0,  5: 7.0,  6: 8.0,  7: 9.0,  8: 10.0,  9: 11.0,
10: 1.0,  11: 1.5,  12: 2.0,  13: 2.5,  14: 3.0,  15: 3.5,  16: 4.0,  17: 4.5,  18: 5.0,
19: 5.5,  20: 6.0,  21: 6.5,  22: 7.0,  23: 7.5,  24: 8.0,  25: 8.5,  26: 9.0,  27: 9.5,
28: 10.0,  29: 10.5,  30: 11.0, 31: 1.0,  32: 1.2,  33: 1.4,  34: 1.6,  35: 1.8,  36: 2.0},
'b': {0: 110,  1: 140,  2: 170,  3: 200,  4: 230,  5: 260,  6: 290,  7: 320,  8: 350,  9: 380,
10: 160,  11: 190,  12: 220,  13: 250,  14: 280,  15: 310,  16: 340,  17: 370,  18: 400,
19: 430,  20: 460,  21: 490,  22: 520,  23: 550,  24: 580,  25: 610,  26: 640,  27: 670,
28: 700,  29: 730,  30: 760,  31: 300,  32: 350,  33: 400,  34: 450,  35: 500,  36: 550}}

df = pd.DataFrame.from_dict(data)

kmeans = KMeans(n_clusters=3)
kmeans.fit(df)

plt.scatter(df['a'], df['b'],c=kmeans.labels_)


The result from the above code on the dummy data:

The correct result would have the clusters corresponding to each line.

How can I reliably classify these trends?

If they all go through zero, you can calculate the slope of each point, that's y divided by x, and use any clustering method on those, k-means with the correct number of clusters would do it. If they all start in a specific point, you can calculate the slope from that point and use that.

The problem is slightly more complicated if they don't share a common intersection. I cannot think of an equally simple solution at least. But then, you can calculate the following: for all pairs of points, calculate the corresponding slope and intercept (you don't need all of them, just take a sample of combinations). Then, on the resulting set of slopes and intercepts, perform a clustering, for example, k-means with the correct amount of centers again. The cluster centers will give you, approximately, the equation of the lines. Then you can cluster the points by assigning them to the closest line.

If you don't know how many centers there are, you'd need to do some work on determining it, allthough, in this case, it shouldn't be to hard because the correct number is very obvious.

• They all go through zero and fortunately it is fairly easy to choose the correct K, so your first suggestion was the simple and elegant solution I was looking for. Much appreciated! – Rocky K Nov 3 '18 at 9:38
• Cool! Nice problem. – Gijs Nov 3 '18 at 9:40

You could try one of the following:

• Spectral clustering: as long as your data is dense enough, you could use the kernel trick. If you already know the number of clusters you are looking for, there is a ready-to-use function in sklearn: see here. Otherwise, you will need a bit of code (compute the eigen values of the Laplacian matrix and plot them, see the first link).
• Gaussian mixture models: what you are trying to fit may be considered as a set of bivariate gaussians with a very strong component and a very weak one. Thus, gaussian mixtures could do the job. You also have a sklearn implementation for this.

I would go for Gaussian mixtures first, because it should be more robust with small datasets.