My data consist of 3d Cartesian coordinates. As shown in the figure below, there are roughly linear "clusters" of points within these data. How should I approach grouping these data in an automated way?

My intuition is that if you rotated each cluster to its principal axis, almost all the variance would be in 1 dimension. While that gives me a post-hoc metric with which to judge the clusters, I am unsure how to incorporate this into the clustering method itself.

enter image description here

  • $\begingroup$ Why did this perfectly clear, concise, meaningdul, and well-illustrated question receive two downvotes?? This is embarrassing. +1. $\endgroup$ – amoeba May 17 '17 at 8:23

There exist several clustering methods designed for this scenario.

For example CASH which uses the Hough transform (a popular technique to detect lines in 2d) in multiple variates. But also 4C clustering and a few more. Check the related work of these authors, I doubt that I know all of it, as I don't have any data that would exhibit such nice and clear correlations as yours...

The basic idea of some of the methods is this: take all neighbors within a distance threshold, then compute PCA on this subset. Neighbors along the principal axes are then kept.

You may need to use a robust PCA here, though.

  • $\begingroup$ Shouldn't DBSCAN work well here? $\endgroup$ – amoeba May 17 '17 at 8:25
  • $\begingroup$ Depending on how close the lines are, yes. But 4C is a DBSCAN extension if I recall correctly. $\endgroup$ – Anony-Mousse May 17 '17 at 20:25
  • 1
    $\begingroup$ I briefly looked into 4C paper (that I did not come across before) and it looks exactly like what OP needs. +1. $\endgroup$ – amoeba May 17 '17 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.