ELKI 中的并行 DBSCAN
Parallel DBSCAN in ELKI
Here 我可以看到存在 class clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN，但是当我尝试调用它时，出现错误：
java -cp elki.jar de.lmu.ifi.dbs.elki.application.KDDCLIApplication -algorithm clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN -algorithm.distancefunction EuclideanDistanceFunction -dbc.in infile.txt -dbscan.epsilon 1.0 -dbscan.minpts 1 -verbose -out OUTFOLDER
Class 'clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN' not found for given value. Must be a subclass / implementation of de.lmu.ifi.dbs.elki.algorithm.Algorithm
而这个 class 确实不在可用的 classes 列表中，打印出来的错误消息是：
-> clustering.CanopyPreClustering
-> clustering.DBSCAN
-> clustering.affinitypropagation.AffinityPropagationClusteringAlgorithm
-> clustering.em.EM
-> clustering.gdbscan.GeneralizedDBSCAN
-> clustering.gdbscan.LSDBC
-> clustering.GriDBSCAN
-> clustering.hierarchical.extraction.HDBSCANHierarchyExtraction
-> clustering.hierarchical.extraction.SimplifiedHierarchyExtraction
-> clustering.hierarchical.extraction.ExtractFlatClusteringFromHierarchy
-> clustering.hierarchical.SLINK
-> clustering.hierarchical.AnderbergHierarchicalClustering
-> clustering.hierarchical.AGNES
-> clustering.hierarchical.CLINK
-> clustering.hierarchical.SLINKHDBSCANLinearMemory
-> clustering.hierarchical.HDBSCANLinearMemory
-> clustering.kmeans.KMeansSort
-> clustering.kmeans.KMeansCompare
-> clustering.kmeans.KMeansHamerly
-> clustering.kmeans.KMeansElkan
-> clustering.kmeans.KMeansLloyd
-> clustering.kmeans.parallel.ParallelLloydKMeans
-> clustering.kmeans.KMeansMacQueen
-> clustering.kmeans.KMediansLloyd
-> clustering.kmeans.KMedoidsPAM
-> clustering.kmeans.KMedoidsEM
-> clustering.kmeans.CLARA
-> clustering.kmeans.BestOfMultipleKMeans
-> clustering.kmeans.KMeansBisecting
-> clustering.kmeans.KMeansBatchedLloyd
-> clustering.kmeans.KMeansHybridLloydMacQueen
-> clustering.kmeans.SingleAssignmentKMeans
-> clustering.kmeans.XMeans
-> clustering.NaiveMeanShiftClustering
-> clustering.optics.DeLiClu
-> clustering.optics.OPTICSXi
-> clustering.optics.OPTICSHeap
-> clustering.optics.OPTICSList
-> clustering.optics.FastOPTICS
-> clustering.SNNClustering
-> clustering.biclustering.ChengAndChurch
-> clustering.correlation.CASH
-> clustering.correlation.COPAC
-> clustering.correlation.ERiC
-> clustering.correlation.FourC
-> clustering.correlation.HiCO
-> clustering.correlation.LMCLUS
-> clustering.correlation.ORCLUS
-> clustering.onedimensional.KNNKernelDensityMinimaClustering
-> clustering.subspace.CLIQUE
-> clustering.subspace.DiSH
-> clustering.subspace.DOC
-> clustering.subspace.HiSC
-> clustering.subspace.P3C
-> clustering.subspace.PreDeCon
-> clustering.subspace.PROCLUS
-> clustering.subspace.SUBCLU
-> clustering.meta.ExternalClustering
-> clustering.trivial.ByLabelClustering
-> clustering.trivial.ByLabelHierarchicalClustering
-> clustering.trivial.ByModelClustering
-> clustering.trivial.TrivialAllInOne
-> clustering.trivial.TrivialAllNoise
-> clustering.trivial.ByLabelOrAllInOneClustering
-> clustering.uncertain.FDBSCAN
-> clustering.uncertain.CKMeans
-> clustering.uncertain.UKMeans
-> clustering.uncertain.RepresentativeUncertainClustering
-> clustering.uncertain.CenterOfMassMetaClustering
我想也许这个方法是内部方法，由 clustering.gdbscan.GeneralizedDBSCAN 调用，但它对我来说是单核的。也许我需要添加一些命令行参数来启用多处理？
编辑：感谢@erich-schubert，现在我可以看到时间估算了。我在那里使用了 M-tree 索引，如 docs:
所示
java -Xmx32000M -cp elki-bundle-0.7.2-SNAPSHOT.jar de.lmu.ifi.dbs.elki.application.KDDCLIApplication -algorithm clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN -db.index tree.metrical.mtreevariants.mtree.MTreeFactory -treeindex.pagesize 4096 -mtree.distancefunction EuclideanDistanceFunction -algorithm.distancefunction EuclideanDistanceFunction -dbc.in dump_txt.txt -dbscan.epsilon 1.0 -dbscan.minpts 1 -verbose -out RES
我收到有关忽略参数的警告：
following parameters were not processed: [-treeindex.pagesize, 4096]
以及持续增长的令人沮丧的时间估计：
de.lmu.ifi.dbs.elki.datasource.FileBasedDatabaseConnection.load: 553728 ms
Relation does not have a dimensionality -- simulating M-tree as external index!
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.directory.capacity: 200
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.directory.minfill: 0
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.leaf.capacity: 333
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.leaf.minfill: 0
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.construction: 806160 ms
Index statistics before running algorithms:
de.lmu.ifi.dbs.elki.persistent.MemoryPageFile.reads: 22344677
de.lmu.ifi.dbs.elki.persistent.MemoryPageFile.writes: 3831053
de.lmu.ifi.dbs.elki.persistent.MemoryPageFile.numpages: 17472
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.height: 2
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree$Statistics.distancecalcs: 1773733054
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree$Statistics.knnqueries: 0
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree$Statistics.rangequeries: 0
DBSCAN clustering: 708 [ 0%] 33738 min remaining
我的数据是 3.5M 300 维 word2vec 向量（浮点数）。我可以在合理的时间内以某种方式将其优化为 运行 吗？
我使用 -dbscan.minpts 1 因为我刚刚找到了与相似性相对应的向量之间的距离。
EDIT2：R 树索引快一点：
DBSCAN clustering: 4423 [ 0%] 17248 min remaining
0.7.1版本没有并行DBSCAN版本，需要自己编译
它目前不包括进度日志记录，这是一个相当幼稚的并行化。如果大部分时间花在邻居搜索上，它就可以正常工作，因为集群标记是同步的。 （但是如果你所有的核心都加载了，同步应该没问题）。
我刚刚推送了一项更改，将进度记录添加到并行 GDBSCAN。
确保添加索引。对于大多数数据集，索引产生相当大的加速。有了索引，这个实现的相当差的并行化就会浮出水面，你会看到越来越多的线程在等待同步。
Here 我可以看到存在 class clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN，但是当我尝试调用它时，出现错误：
java -cp elki.jar de.lmu.ifi.dbs.elki.application.KDDCLIApplication -algorithm clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN -algorithm.distancefunction EuclideanDistanceFunction -dbc.in infile.txt -dbscan.epsilon 1.0 -dbscan.minpts 1 -verbose -out OUTFOLDER
Class 'clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN' not found for given value. Must be a subclass / implementation of de.lmu.ifi.dbs.elki.algorithm.Algorithm
而这个 class 确实不在可用的 classes 列表中，打印出来的错误消息是：
-> clustering.CanopyPreClustering
-> clustering.DBSCAN
-> clustering.affinitypropagation.AffinityPropagationClusteringAlgorithm
-> clustering.em.EM
-> clustering.gdbscan.GeneralizedDBSCAN
-> clustering.gdbscan.LSDBC
-> clustering.GriDBSCAN
-> clustering.hierarchical.extraction.HDBSCANHierarchyExtraction
-> clustering.hierarchical.extraction.SimplifiedHierarchyExtraction
-> clustering.hierarchical.extraction.ExtractFlatClusteringFromHierarchy
-> clustering.hierarchical.SLINK
-> clustering.hierarchical.AnderbergHierarchicalClustering
-> clustering.hierarchical.AGNES
-> clustering.hierarchical.CLINK
-> clustering.hierarchical.SLINKHDBSCANLinearMemory
-> clustering.hierarchical.HDBSCANLinearMemory
-> clustering.kmeans.KMeansSort
-> clustering.kmeans.KMeansCompare
-> clustering.kmeans.KMeansHamerly
-> clustering.kmeans.KMeansElkan
-> clustering.kmeans.KMeansLloyd
-> clustering.kmeans.parallel.ParallelLloydKMeans
-> clustering.kmeans.KMeansMacQueen
-> clustering.kmeans.KMediansLloyd
-> clustering.kmeans.KMedoidsPAM
-> clustering.kmeans.KMedoidsEM
-> clustering.kmeans.CLARA
-> clustering.kmeans.BestOfMultipleKMeans
-> clustering.kmeans.KMeansBisecting
-> clustering.kmeans.KMeansBatchedLloyd
-> clustering.kmeans.KMeansHybridLloydMacQueen
-> clustering.kmeans.SingleAssignmentKMeans
-> clustering.kmeans.XMeans
-> clustering.NaiveMeanShiftClustering
-> clustering.optics.DeLiClu
-> clustering.optics.OPTICSXi
-> clustering.optics.OPTICSHeap
-> clustering.optics.OPTICSList
-> clustering.optics.FastOPTICS
-> clustering.SNNClustering
-> clustering.biclustering.ChengAndChurch
-> clustering.correlation.CASH
-> clustering.correlation.COPAC
-> clustering.correlation.ERiC
-> clustering.correlation.FourC
-> clustering.correlation.HiCO
-> clustering.correlation.LMCLUS
-> clustering.correlation.ORCLUS
-> clustering.onedimensional.KNNKernelDensityMinimaClustering
-> clustering.subspace.CLIQUE
-> clustering.subspace.DiSH
-> clustering.subspace.DOC
-> clustering.subspace.HiSC
-> clustering.subspace.P3C
-> clustering.subspace.PreDeCon
-> clustering.subspace.PROCLUS
-> clustering.subspace.SUBCLU
-> clustering.meta.ExternalClustering
-> clustering.trivial.ByLabelClustering
-> clustering.trivial.ByLabelHierarchicalClustering
-> clustering.trivial.ByModelClustering
-> clustering.trivial.TrivialAllInOne
-> clustering.trivial.TrivialAllNoise
-> clustering.trivial.ByLabelOrAllInOneClustering
-> clustering.uncertain.FDBSCAN
-> clustering.uncertain.CKMeans
-> clustering.uncertain.UKMeans
-> clustering.uncertain.RepresentativeUncertainClustering
-> clustering.uncertain.CenterOfMassMetaClustering
我想也许这个方法是内部方法，由 clustering.gdbscan.GeneralizedDBSCAN 调用，但它对我来说是单核的。也许我需要添加一些命令行参数来启用多处理？
编辑：感谢@erich-schubert，现在我可以看到时间估算了。我在那里使用了 M-tree 索引，如 docs:
所示java -Xmx32000M -cp elki-bundle-0.7.2-SNAPSHOT.jar de.lmu.ifi.dbs.elki.application.KDDCLIApplication -algorithm clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN -db.index tree.metrical.mtreevariants.mtree.MTreeFactory -treeindex.pagesize 4096 -mtree.distancefunction EuclideanDistanceFunction -algorithm.distancefunction EuclideanDistanceFunction -dbc.in dump_txt.txt -dbscan.epsilon 1.0 -dbscan.minpts 1 -verbose -out RES
我收到有关忽略参数的警告：
following parameters were not processed: [-treeindex.pagesize, 4096]
以及持续增长的令人沮丧的时间估计：
de.lmu.ifi.dbs.elki.datasource.FileBasedDatabaseConnection.load: 553728 ms
Relation does not have a dimensionality -- simulating M-tree as external index!
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.directory.capacity: 200
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.directory.minfill: 0
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.leaf.capacity: 333
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.leaf.minfill: 0
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.construction: 806160 ms
Index statistics before running algorithms:
de.lmu.ifi.dbs.elki.persistent.MemoryPageFile.reads: 22344677
de.lmu.ifi.dbs.elki.persistent.MemoryPageFile.writes: 3831053
de.lmu.ifi.dbs.elki.persistent.MemoryPageFile.numpages: 17472
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex.height: 2
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree$Statistics.distancecalcs: 1773733054
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree$Statistics.knnqueries: 0
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree$Statistics.rangequeries: 0
DBSCAN clustering: 708 [ 0%] 33738 min remaining
我的数据是 3.5M 300 维 word2vec 向量（浮点数）。我可以在合理的时间内以某种方式将其优化为 运行 吗？
我使用 -dbscan.minpts 1 因为我刚刚找到了与相似性相对应的向量之间的距离。
EDIT2：R 树索引快一点：
DBSCAN clustering: 4423 [ 0%] 17248 min remaining
0.7.1版本没有并行DBSCAN版本，需要自己编译
它目前不包括进度日志记录，这是一个相当幼稚的并行化。如果大部分时间花在邻居搜索上，它就可以正常工作，因为集群标记是同步的。 （但是如果你所有的核心都加载了，同步应该没问题）。
我刚刚推送了一项更改，将进度记录添加到并行 GDBSCAN。
确保添加索引。对于大多数数据集，索引产生相当大的加速。有了索引，这个实现的相当差的并行化就会浮出水面，你会看到越来越多的线程在等待同步。