Unsupervised clustering without of Data which is supposed to be on a linear function

Question

When I have a dataset where each datum has x and y, and the (x,y) has a relation of one of y = a_i*x + b_i (i=1,2,...).

Is the process written below available? and which algorithm does it belong to?

The process is.....

I have many points (x, y). The machine finds 2 linear functions which represents the points. The machine eliminates points which are far from the 3 lines.

In this case, I think I put parameters the number of linear functions and criterion to judge if a point is on a line or not..

The first figure is my dataset.

I want to have a machine which accepts the number of line (3 in this case) and finds 3 lines(as the second figure (the lines in the figure are just put for idea without computation)), and then finally suggests points which may belong to neither of them. (In this case, for example, (71.6, 22))

Should I, for instance, extend the k-means algorithm to achieve this procedure?///

Answer 1

Very interesting question!

First Approach: PCA + K-means

Your data will be explained very well on the second principle component. If you apply PCA on your data the first PC captures the data along the lines in which you completely lose the differentiation but the second PC is prependicular to the first one so your data will be projected in a way that points correspondig to each line are placed closer to each other. As you know the number of lines (number of clusters) a priori then you simply apply k-means and that's it! See image in the link to have an idea how the second pc vector would be.

Second approach: GMMs

Gaussian Mixture Models are fitted to clusters in a data using maximum likelihood estimation (you use Expectation Maximization algorithm for that). Your clusters along second PC are pretty gaussian so you will get a good soft-clustering if you fit a mixture of $n$ (number of lines again) Gaussian kernels to them.

Variant: $a$s Are Not Equal

In this case your lines cross each other as slopes are different. Your image does not show that but I include it here anyways. In this case you fit a linear regression to each line and keep the coefficients of the line. The you have a $2D$ data in which each line is described by just a slope and an intercept. Then the prependicular distance between each point and all lines tells you which line is closer so that is the cluster. (The distance can also simply be the residual of that point from regression line. You just need a distance metric to determine the closest line)

If you need implementation as well, please drop a comment here so I can update answer with Python code.

Good luck :)

Answer 2

I would rather look at mixture models. Or, if there is additional noise besides the lines, use computer vision algorithms, for example, some variation of the Hough transform.

Answer 3

Looking at the plot, it seems that you could project it down to 1D.

From here you simply have to calculate the distances to the lines, which will be a cluster center, or point in the 1D. Since running K-Means, or GMM might not give you cluster centers corresponding to the placement of the line it does not seem to be the right thing to do.

Answer 4

You could use a quantile regression model.

Just as regressions minimize the squared-error loss function to predict a single point estimate, quantile regressions minimize the quantile loss in predicting a certain quantile.

The most popular quantile is the median, or the 50th percentile, and in this case the quantile loss is simply the sum of absolute errors.

Other quantiles could give endpoints of a prediction interval; for example a middle-80-percent range is defined by the 10th and 90th percentiles. The quantile loss differs depending on the evaluated quantile, such that more negative errors are penalized more for higher quantiles and more positive errors are penalized more for lower quantiles.

Quantile Regression - Towards Data Science