Как реализовать многопоточность по алгоритму кластеризации DBSCAN? - PullRequest
Новая
       48

Как реализовать многопоточность по алгоритму кластеризации DBSCAN?

0 голосов
/ 18 февраля 2019

Я реализовал алгоритм dbscan для кластеризации трехмерных данных облака точек.Он работает очень хорошо, но единственная проблема заключается в том, что он занимает слишком много времени.почти 15 сек для облака 6000 баллов.Хочу реализовать многопоточность, чтобы сократить время обработки.Был бы очень признателен, если бы вы могли помочь с реализацией многопоточности в следующем полном фрагменте кода.Спасибо!

public ArrayList<List<Vector>> Run() {
    int index = 0;                      //index for each point cloud (cloud -->input data)
    List <Vector> neighbors;
    ArrayList<List<Vector>> resultList = new ArrayList<List<Vector>>();     //group of cluster --> ArrayList<list<Vector>>
    while (cloud.size() > index) {
        Vector p = cloud.get(index);
        if (!visited.contains(p)) {
            visited.add(p);
            neighbors = get_neighbors(p);
            if (neighbors.size() >= minPts) {                               //minpts = 5
                int ind = 0;
                while (neighbors.size() > ind) {
                    Vector r = neighbors.get(ind);
                    if (!visited.contains(r)) {
                        visited.add(r);
                        List<Vector> individualNeighbors = get_neighbors(r);
                        if (individualNeighbors.size() >= minPts) {
                            neighbors = merge_neighbors(
                                    neighbors,
                                    individualNeighbors);
                        }
                    }
                    ind++;
                }
                resultList.add(neighbors);
            }
        }
        index++;
    }
    return resultList;
}

private List<Vector> merge_neighbors(List<Vector>neighborPts1, List<Vector>neighborPts2) {
    for (Vector n2: neighborPts2) {
        if (!neighborPts1.contains(n2)) {
            neighborPts1.add(n2);
        }
    }
    return neighborPts1;
}

private List<Vector> get_neighbors(Vector pt){
    CopyOnWriteArrayList<Vector> pts = new  CopyOnWriteArrayList<>();
    for (Vector p: cloud) {
            if (computeDistance (pt,p)<=eps*eps) {
                pts.add(p);
        }
    }
    return pts;
}
private double computeDistance (Vector core,Vector target) {
    return Math.pow(core.getX()-target.getX(),2)
            + Math.pow(core.getY()-target.getY(),2)
            +Math.pow(core.getZ()-target.getZ(),2);
}       
}

1 Ответ

0 голосов
/ 18 февраля 2019

A) в вашей реализации заложен большой потенциал оптимизации, который легче реализовать, чем многопоточность.Поэтому сначала оптимизируйте свой код.

В частности, если вы загрузите свои данные в такие инструменты, как ELKI (обязательно добавьте пространственный индекс, который не является значением по умолчанию), вы заметите, что они работают намного быстрее, дажетолько с одним потоком

B) существуют публикации по многоядерному DBSCAN, в которых обсуждаются трудности и проблемы, возникающие при укладке на поддоны DBSCAN.Сначала прочитайте, так как вся эта история очень важна для этого формата вопросов и ответов:

Patwary, MA, Palsetia, D., Agrawal, A., Liao, WK, Manne, F., &Чоудхари, А. (2012, ноябрь).Новый масштабируемый параллельный алгоритм DBSCAN, использующий структуру данных с несвязным множеством.В материалах Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу (стр. 62).IEEE Computer Society Press.

Götz, M., Bodenstein, C., & Riedel, M. (2015, ноябрь).HPDBSCAN: высокопараллельный DBSCAN.В материалах семинара по машинному обучению в высокопроизводительных вычислительных средах (с. 2).ACM.

Welton B., Samanas E. & Miller, BP (2013, ноябрь).Г-н Скан: Кластеризация с высокой плотностью масштабирования с использованием древовидной сети узлов gpgpu.В SC'13: Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу (стр. 1-11).IEEE.

...