Пользовательская метрика расстояния для DBSCAN в Apache Commons Math (v3.1 против v3.6) - PullRequest
Новая
       53

Пользовательская метрика расстояния для DBSCAN в Apache Commons Math (v3.1 против v3.6)

0 голосов
/ 13 сентября 2018

Я хочу использовать Apache Commons Math's DBSCANClusterer<T extends Clusterable> для выполнения кластеризации с использованием алгоритма DBSCAN, но с пользовательской метрикой расстояния, поскольку мои точки данных содержат нечисловые значения. Похоже, что это было легко достижимо в более старой версии (обратите внимание, что полное имя этого класса - org.apache.commons.math3.stat.clustering.DBSCANClusterer<T>, тогда как для текущего выпуска - org.apache.commons.math3.ml.clustering.DBSCANClusterer<T>), которое теперь не рекомендуется. В более старой версии Clusterable будет принимать параметр типа T, описывающий тип кластеризованных точек данных, и расстояние между двумя точками будет определяться реализацией Clusterable.distanceFrom(T), например: 

class MyPoint implements Clusterable<MyPoint> {
    private String someStr = ...;
    private double someDouble = ...;

    @Override
    public double distanceFrom(MyPoint p) {
        // Arbitrary distance metric goes here, e.g.:
        double stringsEqual = this.someStr.equals(p.someStr) ? 0.0 : 10000.0;
        return stringsEqual + Math.sqrt(Math.pow(p.someDouble - this.someDouble, 2.0)); 
    }
}

В текущем выпуске Clusterable больше не параметризуется. Это означает, что нужно придумать способ представления своих (потенциально не числовых) точек данных как double[] и вернуть это представление из getPoint(), например ::

class MyPoint implements Clusterable {
    private String someStr = ...;
    private double someDouble = ...;

    @Override
    public double[] getPoint() {
        double[] res = new double[2];
        res[1] = someDouble; // obvious
        res[0] = ...; // some way of representing someStr as a double required
        return res;
    }
}

А затем предоставьте реализацию DistanceMeasure, которая определяет пользовательскую функцию расстояния в виде double[] представлений двух сравниваемых точек, например ::

class CustomDistanceMeasure implements DistanceMeasure {
    @Override
    public double compute(double[] a, double[] b) {
        // Let's mimic the distance function from earlier, assuming that
        // a[0] is different from b[0] if the two 'someStr' variables were
        // different when their double representations were created.
        double stringsEqual = a[0] == b[0] ? 0.0 : 10000.0;
        return stringsEqual + Math.sqrt(Math.pow(a[1] - b[1], 2.0));
    }
}

Мои точки данных имеют вид (целое, целое, строка, строка): 

class MyPoint {
    int i1;
    int i2;
    String str1;
    String str2;
}

И я хочу использовать функцию / метрику расстояния, которая по существу говорит: «если str1 и / или str2 отличаются для MyPoint mpa и MyPoint mpb, расстояние является максимальным, в противном случае расстояние является евклидовым расстоянием между целые числа ", как показано в следующем фрагменте: 

class Dist {
    static double distance(MyPoint mpa, MyPoint mpb) {
        if (!mpa.str1.equals(mpb.str1) || !mpa.str2.equals(mpb.str2)) {
            return Double.MAX_VALUE;
        }
        return Math.sqrt(Math.pow(mpa.i1 - mpb.i1, 2.0) + Math.pow(mpa.i2 - mpb.i2, 2.0));
    }
}

Вопросы:

  1. Как мне представить String как double, чтобы включить вышеуказанную метрику расстояния в текущем выпуске (v3.6.1) Apache Commons Math? String.hashCode() недостаточно, поскольку коллизии хеш-кода могут привести к тому, что разные строки будут считаться равными. Это кажется неразрешимой проблемой, так как я пытаюсь создать уникальное отображение из бесконечного набора строк в конечный набор числовых значений (64 бита double).
  2. Поскольку (1) кажется невозможным, я неправильно понимаю, как использовать библиотеку? Если да, то сделал ли я неправильный поворот?
  3. Является ли моей единственной альтернативой использование устаревшей версии для такого типа метрики расстояния? Если да, (3а), почему дизайнеры решили сделать библиотеку менее общей? Возможно в пользу скорости? Возможно, чтобы избавиться от самореференции в class MyPoint implements Clusterable<MyPoint>, которую некоторые могут считать плохим дизайном? (Я понимаю, что это может быть слишком самоуверенным, поэтому, пожалуйста, не обращайте на это внимания, если это так). Для экспертов по математике: (3b) какие недостатки есть в использовании устаревшей версии, кроме прямой совместимости (устаревшая версия будет удалена в 4.0)? Это медленнее? Возможно, даже неправильно?

Примечание: Мне известно о ELKI , который, по-видимому, популярен среди пользователей SO, но он не соответствует моим потребностям, так как продается как команда -линия и графический интерфейс, а не библиотека Java для включения в сторонние приложения :

Вы даже можете встроить ELKI в свое приложение (если вы принимаете Лицензии AGPL-3), но в настоящее время мы (пока) не рекомендуем делать это, потому что API все еще существенно меняется. [...]

ELKI не предназначен для встраиваемой библиотеки. Это можно использовать, но это не предназначен для использования таким образом. ELKI имеет множество вариантов и функциональность, и это идет по цене, как во время выполнения (хотя это может легко превзойти R и Weka, например!) использование памяти и в особенно в сложности кода.

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

...