Map/Reduce: решение реальных задач — TF-IDF — 2

    Продолжая статью “Использование Hadoop для решения реальных задач”, хочу напомнить, что в прошлой статье мы остановились на том, что посчитали такую характеристику как tf(t,d), и сказали, что в следующем посте мы будем считать idf(t) и завершим процесс вычисления значения TF-IDF для данного документа и термина. Поэтому предлагаю долго не откладывать и переходить к этой задаче.

    Важно заметить, что idf(t) не зависит от документа, потому как считается на всем корпусе. Это нетрудно увидеть, посмотрев на формулу:



    Вероятно, она нуждается в некоторых пояснениях. Итак, |D| это мощность корпуса документов — иными словами, просто количество документов. Мы знаем его, поэтому считать ничего не надо. Знаменатель же логарифма — это количество таких документов d которые содержат интересующий нас токен t_i.



    Как это можно посчитать? Способов тут немало, но я предлагаю следующий. В качестве входных данных мы будем использовать результат задачи, которая расчитала нам ненормализованные значения tf(t,d), напомню, что они выглядили вот так:

    1_the       3
    1_to        1
    ...
    2_the       2
    2_from      1
    ...
    37_london   1

    В чем будет заключаться наша задача? Мы хотим понять: сколько, например, документов содержат слово the? Решение, в общем-то, интуитивно: мы берем каждое значение, такое как 2_the, делим его на пару (2, the) и пишем в вывод map-задачи, что у нас есть как минимум один документ, который содержит слово the:

    the     1
    

    Делая это для всех документов, мы получим данные следующего формата:

    the     1
    to      1
    the     1
    from    1
    london  1

    Дальше все более или менее очевидно: reduce-таск получает эти данные (получает он термин и список единиц), считает количество этих самых единиц и выдает нам:

    the     2
    to      1
    from    1
    london  1

    Что и требовалось доказать. Теперь задача посчитать непосредственно idf(t) становится тривиальной (впрочем, и ее можно делать на гриде, просто потому, что список слов может быть очень большой).

    На последнем шаге мы считаем непосредственно TF-IDF. Вот тут-то и начинаются неприятности! Все дело в том, что у нас есть два файла — один со значениями TF, другой — со значениями IDF. В общем случае ни тот, ни другой в память не полезут. Что делать? Тупик!

    Тупик, да не совсем. Здесь помогает такое странное, но весьма популярное в Map/Reduce решени как проброс данных (passthrough). Поясню свою идею на примере. Если обрабатывая наш файл со значениями TF (смотри выше), вместо единицы в вывод map-таска мы запишем комбинацию docID_tfValue? Получится что-то вроде:

    the     1_3
    to      1_3
    the     2_2
    from    2_1
    ...
    london  37_1

    Мы по-прежнему можем посчитать количество документов, в который входит то или иное слово — и действительно, мы же не суммировали единицы а просто считали их количество! В то же время, у нас есть некоторые дополнительные данные, а значит, мы можем модифицировать вывод reduce-таска следующим образом:

    the     2_1_3   # количество документов с the - идентификатор документа - количество the в этом док-те
    the     2_2_2
    to      1_1_3
    from    1_2_1
    ...
    london  1_37_1

    Имеем следующую забавную ситуацию — reducer на самом деле количество данных не уменьшил, но добавил некоторую новую характеристику к ним! Что мы можем сделать теперь? Да практически все что угодно! Предполагая, что мы знаем значения N и |D| (то есть количество токенов и количество документов в корпусе) мы можем реализовать простейшую Map/Reduce программу (которой и Reduce-то не понадобится). Для каждого входящей строки она будет представлять данные в следующем виде

    term = key
    (docCount, docId, countInDoc) = value.split("_")

    Я надеюсь, вы понимаете, что псевдокод весьма и весьма условен (так же, как условно и использование символа подчеркнивания для разделения значений) — но суть, как мне кажется, ясна. Теперь мы можем сделать следующее:

    tf = countInDoc / TOTAL_TOKEN_COUNT
    idf = log(TOTAL_DOC_COUNT / docCount)
    
    result = tf * idf
    
    output(key = docId + "_" + term, value = result)

    Что у нас получилось? У нас получилось значение TF-IDF.

    В рамках этой статьи мы закончили пример с расчетом значения TF-IDF для корпусов текста. Важно отметить, что увеличение мощности корпуса не приведет к возможным проблемам с нехваткой памяти, а всего лишь увеличит время расчетов (что может быть решено добавлением новых узлов в кластер). Мы рассмотрели одну из популярных техник data passthrough, часто применяемую для решения комплексных задач в Map/Reduce. Мы изучили некоторые принципы дизайна Map/Reduce приложений в целом. В дальнейших статьях мы рассмотрим решение этой и других задач для реальных данных, с примерами работающего кода.

    P.S. как всегда, вопросы, комментарии, уточнения и отзывы приветствуются! Я постарался сделать это все как можно понятнее, но возможно не вполне преуспел — напишите мне об этом!

    Для домашнего чтения рекомендую просмотреть слайды, выложенные товарищами из Cloudera на Scribd:
    В частности, в одной из них рассматривается решение нашей задачи (но немного другим методом).

    Для интересующихся также напоминаю, что английская версия статьи (целиком) доступна вот здесь: romankirillov.info/hadoop.html — там же можно скачать и PDF версию.
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 13
    • 0
      Спасибо!
      • +1
        Пожалуйста :-)

        Наблюдаю интересную ситуацию: статью плюсуют, но не комментируют. Тут два варианта: либо все понятно и нечего комментировать, либо понятны только предлоги, но явно что-то умное. WTF?! :-)
        • 0
          Всё понятно, что ничего не понятно :-)
          • +1
            Блин ну спрашивайте! Я объясню или хотя бы постараюсь! :-)
          • 0
            скорее всего причина в заголовке…
            мало кто на практике знает, что такое tf-idf, эту серию статей было бы неплохо начать
            с введения в решаемую задачу, т.е. tf-idf

            я, вот, на тойже википедии, о нем когда-то читал… но реально имею смутное представление

            и хадуп тоже хоть продукт и известный, но все же редкий зверь у рядового девелопера

            PS: (немного PR) но у нас в компании на нем (hadoop+nutch) построили экспериментальный узко-специализированный поисковик onfood.ru
            • 0
              Ну да, согласен… вероятно, надо все-таки написать описание этого метода до того, как перейдем к написанию кода. Хотя, честно говоря, там ничего сложного нет — этот метод лежит в основе практически всех поисковиков.
            • 0
              Статья хороша, но мало кому нужна. Map/Reduce имеет смысл на огромных массивах данных, а они есть только у кучки предприятий и организаций.
            • 0
              Ну да, довольно злая бумага по ranker'ам — но это как мне кажется, не вполне релевантно теме статьи (хотя слайды я не досмотрел если честно). А вообще-то с Machine Learning на Hadoop только сейчас начал намечаться какой-то прогресс (да и то: сейчас мне нужен какой-то очень хороший SVM классификатор который бы работал на гриде и ничего найти не могу; сижу пишу имейлы по всем частям компании, возможно, у кого-то есть внутренние реализации, которые можно доработать напильником).
            • 0
              рассчитываю, что продолжение будет :)
              • +1
                Будет. Вот немного дыхание переведу — и будет.
              • 0
                sigizmund, вопрос не совсем по теме, но почему Hadoop? Судя по вашему месту работы, вы же используете собственные разработки?
                • 0
                  Когда статья писалась я работал в Yahoo! — а там используют Hadoop.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое