# Looking for a classification (?) algorithm for linearly separable but unlabeled data points

I have a dataset that is linearly separable with two lines - something like that:

Now I'am looking for the right kind of algorithm to do what I guess a SVM would do with labeled data - find the margins or decision boundaries for each class (three in this case). I tried spectral clustering and Gaussian mixture, but those don't seem to work. Origin of the data: edges from tracked bounding boxes for cars on a three lane road. Thanks!

Edit: K-Means is apparently not really working for this kind of distribution:

I also tried out Ismor's suggestion to do some transformation before k-means, which results in:

The output here is very sensitive to the setting of the origin for y0, I couldn't get it right...

• Where would you draw the two lines that separate the data? Why not just draw them by hand? What clusters are you expecting? – Pratik Deoghare Apr 16 at 13:59
• I added the two lines to the graph. The process of finding the "classes" should be automated as this is just one data sample. – Benj Apr 16 at 14:49
• You should add some kind of kernel to k-means. I am searching for a solution but It is the way to go here. K-means does not works with not-rounded shapes – lsmor Apr 16 at 15:15
• What about using a Kernel (aka Kernel Trick) and then do clustering ?Just an idea, you might have explored it already. – TwinPenguins Apr 22 at 13:13
• @TwinPenguins: As far as I know, Kernels are used when a dataset is not linearly separable. But I'm new to the field, so I might be wrong... – Benj Apr 24 at 6:45

I got a partiall solution which migth work for this particular case but it is not easely generalizable: Since all your data converges to the same point: (1400, 500), you can set the center of coordinates there and then cluster in the space of angles. i.e. use the transformation $$\alpha = \arctan\left(\dfrac{y - y_0}{x - x_0}\right)$$ and cluster $$\alpha$$ (be carefull! you might divide by 0)

I have prepare this synthetic example in R and it works!, but again: this is not easely generalizable

library(data.table)
library(ggplot2)

x <- c(1,2,3,4,5)
y1 <- x + 1
y2 <- -x + 11
y3 <- -3*x + 21

# creates a data.table with 3 lines converging at point (5,6)
dt <- data.table( x = rep(x, 3)
, y = c(y1,y2,y3)
)


The data.table looks like this:

Now is time to transform it and make the clusters

dt_transform <- dt[, .(x, y, a = atan((y - 6) / (x - 6)) )] # avoid x - 5 == 0

km <- kmeans(dt_transform$a, 3) dt_cluster <- cbind(dt_transform, cluster = as.factor(km$cluster))


The clustered data.table looks like this:

If you go this way please, share the results with me. I'm interesting to know if it works with real data

• Thanks a lot for your suggestion! I tried it out (see my edit) but it doesn't really work. More out of curiosity: Do you know whether there is a way of fitting multiple linear regression lines to a dataset? – Benj Apr 17 at 20:27
• What a pity!. I was looking for multiple linear regression too but couldn't find anything. I think such a solution is too expensive because you'd need to compute so many coliniarities. W.r.t. arctan approach, could you try to move the origin? I have found that my approach is very sensitive to origin. Maybe use (1400,525) or (1400, 550) as origin. I have Nothing better sorry :( – lsmor Apr 17 at 21:47
• @Benj Oh! You already said about the sensibility of origin... Well have no more clues... This is quite a hard problem. I'll give a try tomorrow – lsmor Apr 17 at 21:50
• If you have any other idea, I‘d be very interested to hear about it. Meanwhile I’ll take slightly different approach to my problem: I’ll grab the y-coordinates at just one x-value (or ‘thin’ region). The output should be more cluster-like and k-means the right tool to handle that. – Benj Apr 18 at 5:08
• I'll take a closer look to that as well: datascience.stackexchange.com/questions/28626/… – Benj Apr 18 at 5:58

Have you tried using a K-means algorithm ? I think it could give good results !

There are other options here as well : https://towardsdatascience.com/unsupervised-learning-and-data-clustering-eeecb78b422a

edit : my first idea was to use a PCA, I'm just note sure it could work for unlabelled data

• Thanks, but K-means doesn't work - I added it's result to my question. – Benj Apr 16 at 11:11

### The red line

In my opinion, the red line is purely subjective, meaning its absence could be equally justified, therefore, we should not expect it to be found in general. For example, it is going through a densely clustered set close to the intersection point (orange circle), and also separates some equally-spaced points down the line (purple circles).

### A general solution

However, the green line (and similar lines that clearly separate two sets) can be found using these steps:

1. Applying a non-convex clustering algorithm such as DBSCAN (tuning its parameters is crucial),
2. Labeling the detected clusters as classes,
3. Using a multi-class classifier with linear decision boundary (e.g. multi-class logistic regression, or mult-class linear SVM) to find the separation line[s] between the classes.

### The red line revisited

As commented by OP, if the assumption is "exactly two lines", I agree that the red line is a very good candidate. We can impose this assumption, i.e. domain knowledge, by tuning the parameters of DBSCAN until we get 3 well-populated clusters.

• Hi Esmailian, thanks a lot for your opinion. I do see your point but given the fact that I could draw the two lines without looking at the ground truth, it was my hope that there is an algorithm aground which could do the same. And yes, the lines ARE subjective. Question is: If I would ask you to separate the data points with two lines, wouldn't you draw something similar? Regarding your 3-step suggestion: I'll definitely try that you! – Benj Apr 21 at 10:57