DBSCAN 及其索引是否应具有相同的距离函数
Should DBSCAN and its index have the same distance function
是否要求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)
如果使用相同距离函数,索引只能用于加速。
一些索引可以支持多个(但不是任意的)距离,例如 R*-tree 可以支持所有空间距离函数(虽然取得了不同程度的成功)。
很明显,如果你建立一个索引来加速余弦距离,但你要求欧氏最近邻,这个索引不能也不会被使用。
你不需要使用索引,但没有你的运行时将是 O(n²);使用索引可以更快(取决于参数、维度等——在最坏的情况下,索引是开销)。
是否要求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)
如果使用相同距离函数,索引只能用于加速。 一些索引可以支持多个(但不是任意的)距离,例如 R*-tree 可以支持所有空间距离函数(虽然取得了不同程度的成功)。
很明显,如果你建立一个索引来加速余弦距离,但你要求欧氏最近邻,这个索引不能也不会被使用。
你不需要使用索引,但没有你的运行时将是 O(n²);使用索引可以更快(取决于参数、维度等——在最坏的情况下,索引是开销)。