6
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – GeorgeOfTheRF Jul 27 '16 at 9:31
  • $\begingroup$ 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... $\endgroup$ – Anony-Mousse Jul 27 '16 at 12:53
  • $\begingroup$ 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? $\endgroup$ – GeorgeOfTheRF Jul 27 '16 at 13:14
  • $\begingroup$ 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. $\endgroup$ – Anony-Mousse Jul 27 '16 at 13:28
4
$\begingroup$

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.

$\endgroup$

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.