# 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

1. What is the actual meaning of eps parameter? Please given an example.
2. Will setting eps=1000 serve my purpose if distance measure is haversine in meters?

I understand that minpts parameter is the cluster size.

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):

1. 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.
2. 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.
• K. Are you saying that eps=1000 will only ensure that distance between any pair of observation in the cluster will be <=1000 m? Or is the interpretation something else? – GeorgeOfTheRF Jul 27 '16 at 9:31
• Distances can be much larger! But between any two points in a cluster, there is a series of steps of at most epsilon each - so 10 steps, 10xepsilon. 100 steps, max 100xepsilon... – Anony-Mousse Jul 27 '16 at 12:53
• Yes. You are right. Basically the distance of any point to its nearest point within a cluster will be <=1000 m. This interpretation should be right? – GeorgeOfTheRF Jul 27 '16 at 13:14
• Yes. More precisely, the distance of any point to it's nearest core point of the same cluster will be less than epsilon. But that is a trivial subset the definition of reachability, so it's not an insight. – Anony-Mousse Jul 27 '16 at 13:28

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.