Внедрение взаимной информации

У меня есть коллекция текстовых документов в индексе Lucene. В индексе чуть более 4 000 000 документов. Программа выполняет поиск на основе пользовательского запроса и возвращает N документов, соответствующих запросу. Затем идея состоит в том, чтобы выполнить вычисление взаимной информации для терминов в N документах и ​​найти термины, которые тесно связаны с коллекцией в целом.

По сути, по запросу «компьютер» программа должна вернуть список таких терминов, как «компьютер, сеть, программист, клиент, сервер» и так далее. Это должно работать в теории, но я никогда не получаю ожидаемого результата, и я не могу сказать, просто ли я его неправильно реализую, или есть что-то в моих коллекциях, что делает это неэффективным.

Это код:

public class CoOccurrence {
    private Map<String, Double> cooccurrenceMatrix = new HashMap<String, Double>();
    private int n;
    private List<String> terms = new ArrayList<String>();

    public CoOccurrence(List<String> abstracts){
        n = abstracts.size();

        for(int i = 0; i < abstracts.size(); i++){
            String[] line = abstracts.get(i).split(" ");
            for(String word: line){
                if(!Utils.containsDigits(word)){
                    if(!terms.contains(word)){
                        terms.add(word);
                    }
                }
            }
        }
        getMutualInformation(abstracts);
    }

    private void getMutualInformation(List<String> abstracts){
        double n = this.n;
        double sum;

        for(int f1 = 0; f1 < terms.size()-1; f1++){
            sum = 0;
            for(int f2 = f1 + 1; f2 < terms.size(); f2++){
                Bigram bigram = new Bigram(terms.get(f1), terms.get(f2));

                //Fetch number of documents that contains both term.f1 and term.f2
                double p_xy = docsContainingXandY(bigram, abstracts) / n;

                //Fetch number of documents containing term.f1
                double p_x = docsContainingX(bigram, abstracts) / n;

                //Fetch number of documents containing term.f2
                double p_y = docsContainingY(bigram, abstracts) / n;

                sum += (p_xy) * Utils.logWithoutNaN( p_xy / (p_x * p_y) );
            }
            cooccurrenceMatrix.put(terms.get(f1), sum);
        }
    }
}

Может ли кто-нибудь увидеть, что я выполняю расчеты каким-то ошибочным образом или какие-либо другие ошибки или недоразумения, которые мешают желаемому результату?

РЕДАКТИРОВАТЬ: класс Bigram представляет собой простую оболочку, содержащую две строки: String x, String y.

Класс Util содержит много разных задач, но logWithoutNaN выглядит так:

public static double logWithoutNaN(double value) {
    if (value == 0) {
        return Math.log(EPSILON);
    } else if (value < 0) {
        return 0;
    }
    return Math.log(value);
}

Где ЭПСИЛОН = 0,000001

Что касается вывода: Поиск по слову «компьютер» дает 20 терминов, которые должны быть релевантными, но (в основном) таковыми не являются: дать ассоциации наука дать"


person Geir K.H.    schedule 06.02.2014    source источник
comment
Нужно знать больше, тем более что у нас нет классов BigGram и Utils. Что за ошибка или плохой результат? Предоставьте дополнительную информацию, например трассировку стека.   -  person aliteralmind    schedule 06.02.2014
comment
@aliteralmind Я добавил запрошенную информацию.   -  person Geir K.H.    schedule 06.02.2014


Ответы (1)


Сразу приходит на ум пара вещей. Но мне трудно говорить, так как я не знаю ваших данных (сколько документов, насколько они велики и т.

Но справа от летучей мыши terms должен быть набором, а не списком, тогда «содержит» (который постоянно сканирует список) должен быть более эффективным.

Затем, хотя разделение является похвальной целью, я бы объединил подпрограммы docContaining... в одну подпрограмму. Вы перебираете список документов, и я предполагаю, что все их содержимое 3 раза. Вы (вероятно) могли сканировать их один раз и получать все 3 значения (p_xy, p_x, p_y) одновременно.

Итак, я просто вижу много повторяющихся сканирований, где, возможно, какой-то лучший выбор алгоритмов и структуры данных потенциально может иметь большое влияние.

Дополнения: Удивительно, что может принести душ.

Фундаментальной проблемой здесь является основной двойной цикл for в центре, где вы перебираете пары слов. Это то, что убивает вас. Это n^2. Больше слов, гораздо хуже производительность.

Таким образом, настоящая цель состоит в том, чтобы исключить слова как можно раньше.

Во-первых, вы должны запустить стеммер для слов. Stemming устраняет такие вещи, как множественное число, сокращения и тому подобное. Вы также должны исключить общие стоп-слова («the», «a», «then» и т. д.). Оба эти процесса уменьшат количество слов. Вы можете поискать алгоритмы стемминга, они наверняка уже есть в Lucene.

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

Наконец, я бы начал выбрасывать малоиспользуемые слова, которые являются общими. Если вас интересует КАЖДАЯ корреляция, то вам не стоит этого делать. Но большинство людей интересуют «несколько лучших». Таким образом, должно быть несложно заранее исключить те слова, которые явно не поднимутся в начало списка. Например, слова, которые используются только один раз в 2 документах. Вы можете попробовать некоторую эвристику, например, усреднить количество вхождений слов во всех документах и ​​отбросить эти слова ниже определенного порога.

Целью всего этого является сокращение общего списка слов, поскольку каждое новое слово оказывает огромное влияние на общую производительность.

person Will Hartung    schedule 06.02.2014
comment
Да, вы правы в том, что сейчас это не то, что вы могли бы назвать эффективным временем. Однако ни одна из этих вещей не меняет результат программы, на чем я сейчас застрял. Я отредактирую свою запись с дополнительной информацией. - person Geir K.H.; 06.02.2014
comment
Вы предлагаете здесь несколько отличных идей для повышения производительности, но прежде всего: хотя выделение корней может сократить общее количество слов, оно разрушительно для точности поиска, к чему я здесь и стремлюсь. (Стемминг хорош для припоминания и плох для точности). Во-вторых: это вообще не отвечает на мой вопрос. Моя проблема не в производительности. Да, это медленная, неоптимальная программа, но меня сейчас не волнует производительность. Сначала мне нужно это, чтобы дать ожидаемый результат. - person Geir K.H.; 06.02.2014