What algorithm to use for fitting several different lines I have a unique problem I'm not sure how to approach.
I have some data. The data was generated by a function that's basically $k$ different lines ($k$ may or may not be given).
Example:
However, since the data is noisy or poorly measured, it doesn't look exactly like $k$ lines when I see it, and it's certainly not labelled. In-fact what I see is this:

My goal is to label each point in this data and assign it to a different line. For instance, in this case, I would like something akin to this:

So this is a variant of clustering problem, where I know for certain that the shape of the cluster has to be almost a straight line.
I tried using k-means and had terrible results, I tried using mixture of Gaussians and saw significant improvement but nothing to write home about.
I am open to new suggestions, I'm unsure what to do.
download link for data sample - https://easyupload.io/deumkr
the column time received is the x-axis, the column tcptimestamp is the y-axis
 A: Here is what the segmented package for R finds if we ask it to find a single break point:

R code:
foo <- read.table("noisy data.csv",header=TRUE,sep=",",dec=".")
library(segmented)

# model without breaks as a starting point
model.0 <- lm(TcpTimeStamp~Time.received,data=foo)

# model with one break
model.1 <- segmented(model.0,npsi=1)
plot(model.1,lwd=2,col="red")
with(foo,points(Time.received,TcpTimeStamp,pch=19,cex=0.8,col="grey"))

You can control the number of breaks to be detected by changing the npsi parameter to segmented(), or alternatively specify a vector of initial break locations with the psi parameter. Depending on your needs, you can change pick a number of breaks that makes sense visually, or base the decision on adjusted $R^2$ or AIC or similar, or even use cross-validation.
Take a look at the help page with ?segmented (or read the documentation at the CRAN page linked above) for more parameters and pointers to literature for the algorithm used.
There are a number of short tutorials online that may be useful, e.g., here. You can also google for "linear spline", "breakpoint detection", "piecewise linear regression" or similar search terms.
