DBSCAN 及其索引是否应该具有相同的距离函数

Question

DBSCAN及其索引是否要求具有相同的距离函数？如果不是，什么情况下需要使用不同的距离函数？

Scala 代码如何创建 DBSCAN 和索引：

import de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN

import de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN

import de.lmu.ifi.dbs.elki.data.model.Model

import de.lmu.ifi.dbs.elki.data.{Clustering, DoubleVector, NumberVector}

import de.lmu.ifi.dbs.elki.database.{Database, StaticArrayDatabase}

import de.lmu.ifi.dbs.elki.datasource.ArrayAdapterDatabaseConnection

import de.lmu.ifi.dbs.elki.distance.distancefunction.NumberVectorDistanceFunction

import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction

import de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.SimplifiedCoverTree

def createDatabase(data: Array[Array[Double]], distanceFunction: NumberVectorDistanceFunction[NumberVector]): Database = {

  val indexFactory = new SimplifiedCoverTree.Factory[NumberVector](distanceFunction, 1.3, 20)

  // Create a database

  val db = new StaticArrayDatabase(new ArrayAdapterDatabaseConnection(data), java.util.Arrays.asList(indexFactory))

  // Load the data into the database

  db.initialize()

  db

}

def dbscanClustering(data: Array[Array[Double]], distanceFunction: NumberVectorDistanceFunction[NumberVector]): Unit = {

  // Use the same `distanceFunction` for the database and DBSCAN <- is it required??

  val db = createDatabase(data, distanceFunction)

  val dbscan = new DBSCAN[DoubleVector](distanceFunction, 0.01, 20)

  val result: Clustering[Model] = dbscan.run(db)

  println(s"Number of clusters: ${result.getAllClusters.size()}")

  result.getAllClusters.asScala.zipWithIndex.foreach { case (cluster, idx) =>

    println(s"# $idx: ${cluster.getNameAutomatic}")

    println(s"Size: ${cluster.size()}")

    println(s"Model: ${cluster.getModel}")

}

val inputData: Array[Array[Double]] = ???

dbscanClustering(inputData, SquaredEuclideanDistanceFunction)

Answer 1

如果索引使用相同的距离函数，则只能用于加速度。某些索引可以支持多个（但不是任意）距离，例如 R* 树可以支持所有空间距离函数（尽管取得了不同的成功）。显然，如果你建立一个索引来加速余弦距离，但你要求欧几里德最近邻，则该索引不能也不会被使用。你不需要使用索引，但如果没有，你的运行时间将是 O(n²)；使用索引，它可以更快（取决于参数、维度等 - 在最坏的情况下，索引是开销）。