Как добавить индекс в базу данных, используя ELKI Java API для пользовательского POJO с полями типа String

Я использую DBSCAN для кластеризации некоторых категориальных данных, используя POJO. Мой класс выглядит так

public class Dimension {
    private String app;
    private String node;
    private String cluster;
 .............

Все мои поля являются String вместо целых или Float, потому что они имеют дискретное / категориальное значение. Остальная часть моего кода выглядит следующим образом.

    final SimpleTypeInformation<Dimension> dimensionTypeInformation = new SimpleTypeInformation<>(Dimension.class);
    PrimitiveDistanceFunction<Dimension> dimensionPrimitiveDistanceFunction = new PrimitiveDistanceFunction<Dimension>() {
        public double distance(Dimension d1, Dimension d2) {
            return simpleMatchingCoefficient(d1, d2);
        }
        public SimpleTypeInformation<? super Dimension> getInputTypeRestriction() {
            return dimensionTypeInformation;
        }
        public boolean isSymmetric() {
            return true;
        }
        public boolean isMetric() {
            return true;
        }
        public <T extends Dimension> DistanceQuery<T> instantiate(Relation<T> relation) {
            return new PrimitiveDistanceQuery<>(relation, this);
        }
    };
    DatabaseConnection dbc = new DimensionDatabaseConnection(dimensionList);
    Database db = new StaticArrayDatabase(dbc, null);
    db.initialize();
    DBSCAN<Dimension> dbscan = new DBSCAN<>(dimensionPrimitiveDistanceFunction, 0.6, 20);
    Result result = dbscan.run(db);

Теперь, как и ожидалось, этот код отлично работает для небольшого набора данных, но становится очень очень медленным, когда мой набор данных становится больше. Поэтому я хочу добавить индекс, чтобы ускорить процесс. Но весь индекс, о котором я мог подумать, требует от меня реализации NumberVector. Но в моем классе есть только строки, а не числа. Какой индекс я могу использовать в этом случае? я могу использовать функцию расстояния double simpleMatchingCoefficient(Dimension d1, Dimension d2) для создания IndexFactory?

Заранее спасибо.

Источник

2 ответа

Решение

Существует (как минимум) три широких семейства индексов:

  1. Индексы, основанные на координатах, такие как kd-tree и R-tree. Они хорошо работают на плотных, непрерывных переменных
  2. Метрические индексы, которые требуют, чтобы функция расстояния удовлетворяла неравенству треугольника. Они могут работать с любыми видами данных, но все же может потребоваться довольно плавное распределение значений расстояний (например, они не помогут с дискретной метрикой, то есть 0 из x=y и 1 в противном случае).
  3. Инвертированные индексы поиска. Они в основном используются для текстового поиска и используют для каждого атрибута только небольшое подмножество данных. Они хорошо работают для дискретных атрибутов высокой мощности.

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

И, конечно же, профилируйте свой код и проверьте, можете ли вы улучшить реализацию своей функции расстояния! Например, интернирование строк может помочь, оно может сократить время соответствия строк тестированию на равенство, а не сравнивать каждый символ...

Источник

Прежде всего, обратите внимание, что SMC обычно определяется как функция подобия, а не функция расстояния, но 1-SMC является обычным преобразованием. Только не путайте этих двоих.

Для простого коэффициента соответствия вы, вероятно, захотите построить свой собственный инвертированный индекс для вашего конкретного типа данных POJO. Из-за вашего дизайна POJO (Dimension звучит как очень плохое имя, кстати.), это не может быть реализовано в общем, многократно, легко. Это потребует дорогостоящего самоанализа и все еще требует настройки: должны ли совпадения строк быть чувствительными к регистру? Они нуждаются в отделке? Должны ли они быть токенизированы?

Ваш инвертированный индекс, вероятно, будет содержать серию карт, специфичных для вашего POJO:

Map<String, DBIDs> by_app;
Map<String, DBIDs> by_node;
Map<String, DBIDs> by_cluster;
...

и для каждого атрибута вы получаете соответствующие DBID и подсчитываете, как часто они появляются. Наиболее часто возвращаемый DBIDs иметь самый высокий SMC (и, следовательно, самое низкое расстояние). В какой-то момент вы можете забыть подсчитать кандидатов, которые больше не могут попасть в набор результатов. Просто посмотрите в информационно-поисковой книге, как работает такой поиск.

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

Источник
Другие вопросы по тегам