using Haversine distance in the DBSCAN algorithm

[makjay]

Is there a way to use Haversine distance instead of the euclidean distance in the DBSCAN algorithm?

[muuki88]

Sure. There is an example with DBSCAN

val gdbscan = new GDBSCAN(
    DBSCAN.getNeighbours(epsilon = 1, distance = Kmeans.euclideanDistance),
    DBSCAN.isCorePoint(minPoints = 2)
)

The getNeighbours function is the real interesting part. You can provide your own and use whatever distance you like. The definition for this function is

getNeighbours: (Point[T], Seq[Point[T]]) => Seq[Point[T]] = ???

You receive a single point and a list of all points. The function returns all points that are neighbours. The DBSCAN implementation is straightfoward. Filter all points that are in epsilon range.

 points.filter(neighbour => distance(neighbour.value, point.value) < epsilon)

Hope that helps,
Muki

[InitAction]

Error:scalac: bad symbolic reference. A signature in Kmeans.class refers to term typesafe
in package com which is not available.
It may be completely missing from the current classpath, or the version on
the classpath might be incompatible with the version used when compiling Kmeans.class.

[CavaJ]

You can use the following snippet for the Haversine distance:

val haversineDistance: (DenseVector[Double], DenseVector[Double]) => Double = (x, y) =>
      {
        //x and y will have two coordinates, latitude and longitude
        val thisLat = x.valueAt(0)
        val thisLng = x.valueAt(1)
        val otherLat = y.valueAt(0)
        val otherLng = y.valueAt(1)


        //compute the earth distance between locations
        val earthRadius = 3958.7558657441; // earth radius in miles
        val dLat = Math.toRadians(otherLat - thisLat)
        val dLng = Math.toRadians(otherLng - thisLng)
        val a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(Math.toRadians(thisLat)) * Math.cos(Math.toRadians(otherLat)) * Math.sin(dLng / 2) * Math.sin(dLng / 2)
        val c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a))
        val dist = earthRadius * c

        val meterConversion = 1609.344

        //convert to meters
        dist * meterConversion
      }

val gdbscan = new GDBSCAN(
      DBSCAN.getNeighbours(epsilon = eps, distance = haversineDistance),
      DBSCAN.isCorePoint(minPoints = minimumPoints)
    )