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

Question

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...

Answer 1

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

Answer 2

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

Answer 3

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.