Skip to content
Quantoros

Do you know how DBScan works?

Classic MLLevel: IntermediateClustering

Do you know how DBScan works?

Hints
  • How does this method define distance and cluster shape?
  • Consider noise, the number of groups and feature scaling.

Answer

  • Two input parameters epsilon (neighborhood radius) and minPts (minimum number of points in an epsilon-neighborhood)
  • Cluster defined as maximum set of density-connected points.
  • Points p_j and p_i are density-connected w.r.t. epsilon and minPts if there is a point o such that both, i and j are density-reachable from o w.r.t. epsilon and minPts.
  • p_j is density-reachable from p_i w.r.t. epsilon, minPts if there is a chain of points p_i -> p_i+1 -> p_i+x = p_j such that p_i+x is directly density-reachable from p_i+x-1.
  • p_j is a directly density-reachable point of the neighborhood of p_i if dist(p_i,p_j) <= epsilon.

Source and licence: Alexey Grigorev & contributors — Data Science Interviews · CC-BY-4.0

Related questions