Параллельный DBSCAN в ELKI

Здесь я вижу, что существует класс 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

И этот класс действительно отсутствует в списке доступных классов, который был распечатан с сообщением об ошибке:

-> 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-дерева, как показано в документации:

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 (float). Можно ли как-то оптимизировать его для запуска в разумные сроки?

я использую -dbscan.minpts 1 потому что я только что нашел расстояние между векторами, которое соответствует сходству.

EDIT2: индекс R-дерева немного быстрее:DBSCAN clustering: 4423 [ 0%] 17248 min remaining

1 ответ

Решение

Параллельная версия DBSCAN отсутствует в версии 0.7.1, но вам нужно скомпилировать ее самостоятельно.

В настоящее время он не включает ведение журнала прогресса, и это довольно наивное распараллеливание. Это работает нормально, если большая часть времени уходит на поиск соседей, потому что метка кластера синхронизирована. (Но если все ваши ядра загружены, синхронизация должна быть в порядке).

Я только что выдвинул изменение, которое добавляет ведение журнала прогресса в Parallel GDBSCAN.

Обязательно добавьте индекс. Для большинства наборов данных индексы значительно ускоряются. При использовании индексов будет наблюдаться довольно плохая распараллеливание этой реализации, и вы увидите, что все больше потоков ожидает синхронизации.

Другие вопросы по тегам