Запуск DBSCAN в ELKI

Я пытаюсь сгруппировать некоторые геопространственные данные, и я ранее пробовал библиотеку WEKA. Я нашел этот тест и решил попробовать ELKI.

Несмотря на совет не использовать ELKI в качестве библиотеки Java (которая, как предполагается, требует меньшего обслуживания, чем пользовательский интерфейс), я включил ее в свое приложение и могу сказать, что я очень доволен результатами. Структуры, которые он использует для хранения данных, гораздо более эффективны, чем те, которые используются Weka, и тот факт, что он имеет возможность использовать пространственный индекс, безусловно, является плюсом.

Однако, когда я сравниваю результаты DBSCAN Weka с результатами DBSCAN от ELKI, я немного растерялся. Я бы согласился с тем, что разные реализации могут привести к получению немного разных результатов, но различие в таких масштабах заставляет меня думать, что с алгоритмом что-то не так (возможно, с моим кодом). Количество кластеров и их геометрия очень различны в двух алгоритмах.

Для записи, я использую последнюю версию ELKI (0.6.0), и параметры, которые я использовал для моих симуляций:

Минут =50 Эпсилон =0,008

Я кодировал две функции DBSCAN (для Weka и ELKI), где "точкой входа" является CSV с точками, а "выходные данные" для них обоих также идентичны: функция, которая вычисляет вогнутый корпус набора точек (по одному на каждый кластер). Поскольку функция, которая считывает файл csv в "базу данных" ELKI, относительно проста, я думаю, что моя проблема может быть:

а) при параметризации алгоритма; б) чтение результатов (скорее всего).

Параметризация DBSCAN не создает никаких проблем, и я использую два обязательных параметра, которые я ранее тестировал через пользовательский интерфейс:

ListParameterization params2 = new ListParameterization();
params2.addParameter(de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN.Parameterizer.MINPTS_ID,        minPoints);
params2.addParameter(de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN.Parameterizer.EPSILON_ID, epsilon);

Чтение результатов немного сложнее, поскольку я не совсем понимаю организацию структуры, в которой хранятся кластеры; Моя идея состоит в том, чтобы перебрать каждый кластер, получить список точек и передать его в функцию, которая вычисляет вогнутую оболочку, чтобы сгенерировать многоугольник.

    ArrayList<Clustering<?>> cs = ResultUtil.filterResults(result, Clustering.class);
    for (Clustering<?> c : cs) {
        System.out.println("clusters: " + c.getAllClusters().size());
      for (de.lmu.ifi.dbs.elki.data.Cluster<?> cluster : c.getAllClusters()) {
              if (!cluster.isNoise()){
                 Coordinate[] ptList=new Coordinate[cluster.size()];
                 int ct=0;
                    for (DBIDIter iter = cluster.getIDs().iter(); iter.valid(); iter.advance()) {
                        ptList[ct]=dataMap.get(DBIDUtil.toString(iter));
                        ++ct;
                    }                   
                //there are no "empty" clusters
                assertTrue(ptList.length>0);

                GeoPolygon poly=getBoundaryFromCoordinates(ptList);
                if (poly.getCoordinates().getGeometryType()==
                        "Polygon"){

                    try {
                        out.write(poly.coordinates.toText()+"\n");
                    } catch (IOException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }           

                }else
                    System.out.println(
                            poly.getCoordinates().getGeometryType());

              }//!noise
      }
    }

Я заметил, что "шум" возник как кластер, поэтому я проигнорировал этот кластер (я не хочу его рисовать). Я не уверен, что это правильный способ чтения кластеров, так как я не нахожу много примеров. У меня также есть несколько вопросов, на которые я еще не нашел ответов:

  • В чем разница между getAllClusters() и getTopLevelClusters()?
  • Являются ли кластеры DBSCAN "вложенными", то есть: можем ли мы иметь точки, которые принадлежат многим кластерам одновременно? Зачем?
  • Я где-то читал, что мы не должны использовать идентификаторы базы данных для определения точек, так как они предназначены для внутреннего использования ELKI, но как еще можно получить список точек в каждом кластере? Я читал, что вы можете использовать отношение для меток, но я не уверен, как на самом деле реализовать это...

Любые комментарии, которые могли бы указать мне правильное направление, или любые предложения по коду для итерации по набору результатов DBSCAN ELKI, будут действительно приветствоваться! Я также использовал OPTICSxi от ELKI в своем коде, и у меня есть еще больше вопросов относительно этих результатов, но я думаю, что я оставлю это для другого поста.

Источник

2 ответа

Решение

Доступ к DBIDs ELKI работает, если вы обратите внимание на то, как они назначены.

Для статической базы данных getDBIDs() вернет RangeDBIDs объект, и он может дать вам смещение в базу данных. Это очень надежно. Но если вы всегда перезапускаете процесс, DBIDs в любом случае будет назначен детерминистически (только при использовании MiniGUI они будут отличаться, если вы повторно запустите задание!)

Это также будет более эффективным, чем DBIDUtil.toString,

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

Что касается Weka, он иногда выполняет автоматическую нормализацию. Тогда значение эпсилона будет искажено. Для географических данных я бы предпочел геодезическое расстояние в любом случае, евклидово расстояние по широте и долготе не имеет смысла.

Проверьте эту часть кода Wekas: функция "норма", используемая EuclideanDataObject. Мне кажется, что Wekas ​​DBSCAN обеспечивает нормализацию набора данных! Попробуйте масштабировать ваши данные до [0:1] (я уверен, что в ELKI есть фильтр для этого), если результаты впоследствии будут идентичны?

Судя по фрагменту кода, я бы обвинил Века. Код выше также выглядит немного неэффективным для меня. Подход с использованием фильтров имеет ИМХО больше смысла, чем принудительная фильтрация объектов данных.

Источник

В основном это продолжение @Anony-Mousse, который дал довольно полный ответ.

  • getTopLevelClusters() а также getAllClusters() сделать то же самое для DBSCAN, так как DBSCAN не создает иерархических кластеров.
  • Кластеры DBSCAN не пересекаются. Обработка кластеров isNoise()==true как одиночные объекты, вероятно, лучший способ справиться с шумом. Кластеры возвращены нашими OPTICSXi реализация также не пересекается, но вы должны рассматривать элементы всех дочерних кластеров как часть внешнего кластера. Для выпуклых оболочек эффективный подход состоит в том, чтобы сначала вычислить выпуклую оболочку дочерних кластеров; затем для родителя вычислите выпуклую оболочку на дополнительных объектах + точки выпуклой оболочки всех дочерних элементов.
  • RangeDBIDs Подход, упомянутый @Anony-Mousse, довольно чист для статических баз данных. Чистый подход, который также работает с динамическими базами данных, заключается в наличии дополнительного отношения, которое идентифицирует объекты. При использовании файла CSV в качестве входных данных вместо того, чтобы полагаться на согласованность нумерации строк, вы просто добавляете нечисловой столбец, содержащий метки, например object123, Это лучший подход с логической точки зрения - если вы хотите иметь возможность идентифицировать объекты, присвойте им уникальный идентификатор.;-)
  • Мы используем ELKI для обучения, и мы очень тщательно проверили его алгоритм DBSCAN (вы можете найти пошаговую демонстрацию DBSCAN здесь, и результаты ELKI точно соответствуют этому). Код DBSCAN и OPTICS в Weka был предоставлен студентом давным-давно и никогда не проверялся в той же степени. После быстрой проверки Weka не дает правильных результатов в нашем наборе данных упражнений.
  • Поскольку набор данных упражнения имеет одинаковое расширение 10 в каждом измерении, мы можем отрегулировать параметр epsilon на 1/10, и тогда результат Weka, кажется, соответствует решению; так что @Anony-Mousses обнаружил, что это правильно: реализация Weka предусматривает масштабирование [0;1] для данных.
Источник
Другие вопросы по тегам