Должен ли DBSCAN и его индекс иметь одинаковую функцию - PullRequest
Новая
       39

Должен ли DBSCAN и его индекс иметь одинаковую функцию

0 голосов
/ 25 сентября 2019

Требуется ли, чтобы 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)

1 Ответ

1 голос
/ 25 сентября 2019

Индекс можно использовать только для ускорения , если он использует функцию расстояния * .Некоторые индексы могут поддерживать несколько (но не произвольных) расстояний, например, дерево R * может поддерживать все функции пространственного расстояния (хотя и с переменным успехом).

Очевидно, что если вы создадите индекс для ускорения косинусного расстояния,но вы спрашиваете евклидовых ближайших соседей, индекс не может и не будет использоваться.

Вам не нужно использовать индекс, но без времени выполнения у вас будет O (n²);с индексом это может быть намного быстрее (в зависимости от параметров, размерности и т. д. - в худшем случае индекс будет перегружен).

...