Clustering GPS data using DBSCAN but clusters are not meaningful (in terms of size)

6
votes

I am working with GPS data (latitude, longitude). For density based clustering I have used DBSCAN in R.

Advantages of DBSCAN in my case:

  1. I don't have to predefine numbers of clusters

  2. I can calculate a distance matrix (using Haversine Distance Formula) and use that as input in dbscan 

    library(fossil)
dist<- earth.dist(df, dist=T) #df is dataset containing lat long values
library(fpc)
dens<-dbscan(dist,MinPts=25,eps=0.43,method="dist")

Now, when I look at the clusters, they are not meaningful. Some clusters have points which are more than 1km apart. I want dense clusters but not that big in size.

Different values of MinPts and eps are taken care of and I have also used k nearest neighbor distance graph to get an optimum value of eps for MinPts=25

What dbscan is doing is going to every point in my dataset and if point p has MinPts in its eps neighborhood it will make a cluster but at the same time it is also joining the clusters which are density reachable (which I guess are creating a problem for me).

It really is a big question, particularly "how to reduce size of a cluster without affecting its information too much", but I will write it down as the following points:

  1. How to remove border points in a cluster? I know which points are in which cluster using dens$cluster, but how would I know if a particular point is core or border?
  2. Is cluster 0 always noise?
  3. I was under the impression that the size of a cluster would be comparable to eps. But that's not the case because density reachable clusters are combined together.
  4. Is there any other clustering method which has the advantage of dbscan but can give me more meaningful clusters?

OPTICS is another alternative but will it solve my issue?

Note: By meaningful I want to say closer points should be in a cluster. But points which are 1km or more apart should not be in the same cluster.

1
rcluster-analysisdbscan
Hi Sau, have you considered using K-mean clustering? – jinlong
K mean clustering needs to know how many clusters you want to make.Thats the drawback of it. Also I can not pass my distance matrix into k means. – sau
This seems like more of a conceptual question about the nature of different clustering algorithms, rather tha a programming how-to question; it belongs on Cross Validated (ie, stats.SE) instead of here. – gung - Reinstate Monica
There is R code for half a dozen methods for estimating suitable numbers of clusters for k-means over here. You do not really need to 'know' how many clusters your data have. – Ben
possible duplicate of dbscan - setting limit on maximum cluster span – Has QUIT--Anony-Mousse

1 Answers

7
votes

DBSCAN doesn't claim the radius is the maximum cluster size.

Have you read the article? It's looking for arbitrarily shaped clusters; eps is just the core size of a point; roughly the size used for density estimation; any point within this radius of a core point will be part of a cluster.

This makes it essentially the maximum step size to connect dense points. But they may still form a chain of density connected points, of arbitary shape or size.

I don't know what cluster 0 is in your R implementation. I've experimented with the R implementation, but it was waaaay slower than all the others. I don't recommend using R, there are much better tools for cluster analysis available, such as ELKI. Try running DBSCAN with your settings on ELKI, with LatLngDistanceFunction and and sort-tile-recursive loaded R-tree index. You'll be surprised how fast it can be, compared to R.

OPTICS is looking for the same density connected type of clusters. Are you sure this arbitrarily-shaped type of clusters is what you are looking for?

IMHO, you are using the wrong method for your goals (and you aren't really explaining what you are trying to achieve)

If you want a hard limit on the cluster diameter, use complete-linkage hierarchical clustering.