What is the interpretation of eps parameter in DBSCAN clustering? I want to cluster lat-long data such that all clusters formed will have radius<=1000 meters
Questions


*

*What is the actual meaning of eps parameter? Please given an example.

*Will setting eps=1000 serve my purpose if distance measure is haversine in meters?


I understand that minpts parameter is the cluster size.
 A: Epsilon is the local radius for expanding clusters. Think of it as a step size - DBSCAN never takes a step larger than this, but by doing multiple steps DBSCAN clusters can become much larger than eps.
If you want your "clusters" to have a maximum radius, that is a set cover type of problem, so you will probably want a greedy approximation. It's not a clustering problem, because you do not allow the clustering algorithm to discover structure larger than that. You want to approximate your data with a cover, ignoring structure.
But there are some clustering algorithms where you can bound the cluster radius (but they probably won't try hard enough to optimize for your problem):


*

*LEADER is kind of like DBSCAN minus the cluster expansion. Choose an unclustered point and add everything within a radius of x. Repeat until all points are "clustered". It does not optimize anything, and you do not get a whole lot of theoretical properties. But the maximum distance in a cluster is 2x. Run it twice and you would get very different results.

*Complete-link HAC after cutting the dendrogram at height x, that is the maximum distance of two points. The results should be much better than Leader's, and more stable. Nevertheless, complete-link HAC may not find he optimum.
3 CLINK is a faster variant of complete Link (just O(n²) rather than n³) but tends to find much worse solutions. You may want to run this several times on permutation of your data.

A: The meaning of $\epsilon$ is that of the neighbourhood size. The neighbourhood of a point $p$, denoted by $N_{\epsilon}(p)$, is defined as the $N_{\epsilon}(p) = \{q \in D | dist(p,q) \leq \epsilon \}$. Here $D$ is a database of $n$ objects (points) and $q$ a query point.
$\epsilon$ is what would be constitute a reasonable radius for your particular problem. For example when looking to cluster cities tens of kilometres is probably reasonable. See also this post. Yes, I guess $\epsilon = 1000$ seems like a reasonable first estimate. I would probably try something bigger first but this does not seems horribly misplaced. Let me point out that choosing your distance metric is probably more important than your $\epsilon$ in a way. You can also re-run your analysis with a different $\epsilon$ and see the influence of it but your insights will be tied directly to the distance metric used.
