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

    Вчера я задал вопрос в своем ХабраБлоге — интересно ли людям узнать, что такое Hadoop с точки зрения его реального применения? Оказалось, интересно. Дело недолгое — статью я написал довольно быстро (по крайней мере, ее первую часть) — как минимум, потому, что уже давно знал, о чем собираюсь написать (потому как еще неплохо помню как я сам тыкался в поиске информации, когда начинал пользоваться Hadoop). В первой статье речь пойдет об основах — но совсем не о тех, про которые обычно рассказывают :-)

    Перед прочтением статьи я настоятельно рекомендую изучить как минимум первый и последний источники из списка для чтения — их понимание или хотя бы прочтение практически гарантирует, что статья будет понята без проблем. Ну что, поехали?

    Что такое Hadoop?




    Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему Hadoop, HDFS и прочая. К сожалению, обычно все заканчивалось на довольно пространном введении и фразе “Продолжение следует”. Так вот: это — продолжение. Кому-то тема, затрагиваемая в этой статье может показаться совершенно тривиальной и неинтересной, однако же лиха беда начало — любые сложные задачи надо решать по частям. Это утверждение, в частности, мы и реализуем в ходе статьи. Сразу замечу, что я постараюсь избежать написания кода в рамках этой конкретной статьи — это может подождать, а понять принципы построения программ, работающих с Map/Reduce можно и “на кошках” (к тому же с текущей частотой кардинального изменения API Hadoop любой код становится obsolete примерно через месяц).

    Когда я начинал разбираться с Хадупом, очень большой сложностью лично для меня стало первоначальное понимание идеологии Map/Reduce (я предпочитаю писать это словосочетание именно так, чтобы подчеркнуть, что речь идет не о продукте, а о принципе). Суть и ценность метода станет понятна в самом конце — после того, как мы решим несложную задачу.
    1. Количество слов в корпусе
    2. Количество терминов в корпусе (под термином здесь и далее я буду понимать уникальное слово-токен)
    3. Количество документов в корпусе
    4. Сколько раз каждый термин встречается в каждом документе
    5. Сколько документов содержит каждый термин.
    Скажем прямо — задача несложная и решается в лоб довольно просто — не думаю, что у вас займет больше получаса написать такую программу. Все становится несколько сложнее, если текста становится больше, количество слов растет неограниченно, количество терминов приближается к количеству слов в языке текста, и словари перестают помещаться в памяти. Самое время вспомнить, что первейший принцип не только разработки сложного ПО, но и вообще решения проблем, был сформулирован уже довольно-таки давно и формулируется как “разделяй и властвуй”. Итак, разделим задачу на составные элементы.

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

    <w11> <w12> <w13> ... <w1N>
    <w21> <w22> <w23> ... <w2M>
    ...

    Иными словами, каждый документ — это набор слов, которые возможно (и вполне вероятно) повторяются, и каждый такой набор слов расположен на одной строке текстового файла. Допущение это небольшое — практически каждый документ может быть представлен в таком виде.

    Подсчет количества слов в корпусе — задача простая, и решается в линейное время, однако, возможно, ее даже не придется решать отдельно. То же самое касается и количества терминов — они посчитаются сами. Самая интересная задача на этом этапе — посчитать, сколько раз каждый термин встречается в корпусе текста.

    Да-да, вы не ошибаетесь, это именно она — самая популярная и замученная уже всеми задача, первый пример в каждом руководстве по Hadoop — программа WordCount. Она настолько популярна, насколько же и проста — я даже не буду приводить ее здесь, ее можно посмотреть в официальном tutorial’е Хадупа. Если очень кратко, то на map-шаге программа формирует следующие пары:

    map1:
        <term1> 1
        <term2> 1
        <term3> 1
    
    map2:
        <term2> 1
        <term3> 1
        <term3> 1
    
    map3:
        <term1> 1
        ...

    На reduce-шаге каждый reduce-task получает ключ (то есть <term1>, <term2> и так далее) и список всех значений ассоциированных с этим ключем, полученных из всех map-задач (в данном случае — просто список единиц). Это будет выглядеть как:

    <term1> 1,1
    <term2> 1,1
    <term3> 1,1,1
    




    Суммируя эти единицы (а по факту — просто считая количество элементов в списке) мы получаем количество вхождений каждого термина в корпус:

    the     19283
    to      3432
    from    343
    ...
    ...
    london  14

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

    Дальше начинается классика information retrieval. Для начала на основе результатов работы WordCount мы строим словарь — то есть общий список терминов корпуса. Наша следующая задача — установить, как часто и какие именно термины словаря встречаются в каждом из документов. Для этого мы реализуем уже немного модифицированный вариант WordCount, который считает количество терминов применимо к конкретному документу. Наверное, самый простой способ добиться этого — это использовать в результатах map-задач ключ, состоящий из идентификатора документа (входной ключ mapper’а) и термина:

    map1:
        1_the       1
        1_the       1
        1_the       1
        1_to        1
        ...
    
    map2:
        2_the       1
        2_the       1
        2_from      1
        ...
    
    map3:
        37_london   1
        ...
    

    Reduce для этой задачи будет идентичен классическому WordCount — он будет просто суммировать значения с одинаковым ключем. В результате мы получим:

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

    Так что же у нас получилось? А получилась у нас так называемая частота терминов — которую гораздо лучше знают как term frequency, сокращенно — tf(t,d) (здесь t и d означают, что значение считается применимо к конкретному документу и конкретному термину). К примеру, в статье про Лондон значение tf для слова london будет, вероятно, выше, чем в статье про свиноводство (а возможно, будет равным нулю — нулевая частота это тоже частота). Вероятно, надо заметить, что у нас получился ненормализованный вариант этой характеристики, для нормализации полученные значения следует разделить на общее количество токенов в корпусе.

    В рамках нашего примера мы разработали алгоритм вычисления одной из наиболее популярных статистических характеристик в information retrieval. Ценность данного метода в том, что он может быть расширен на корпус практически любого размера — и это можно будет посчитать даже на одной машине (а можно без дополнительных усилий распараллелить на кластер в полторы-две тысячи нодов). Таким образом, ответ на вопрос, сформулированный в самом начале статьи звучит так: идеология Map/Reduce позволяет разбить вычислительно сложную задачу на маленькие блоки, которые можно посчитать отдельно, после чего объединить результаты. Эти блоки могут считаться параллельно, могут — последовательно и это не имеет никакого значения: суть в том, что мы превратили одну крайне ресурсоемкую задачу в большое количество задач, каждая из которых может быть решена на вашем домашнем компьютере.

    Пожалуй, здесь мне все-таки следует произнести сакральную фразу — “Продолжение следует”. В следующем посте мы рассмотрим расчет второй части tf-idf — а именно, inverse document frequency, после чего плавно перейдем к решению этой задачи для реального большого (никому мало не покажется) набора данных.

    P.S. Маленькое примечание, которое мне показалось важным: при написании русской версии статьи (а она изначально писалась практически параллельно на двух языках) я старался писать настолько по-русски, насколько это только возможно, однако я не переводил многие устойчивые сочетания (такие как Map/Reduce) и даже не пытался перевести названия фаз этого процесса, оттуда появились map-таски и reduce-таски. К сожалению, русская терминология не вполне устоялась применимо к этому предмету, но великий и могучий настолько велик и могуч, что любой школьник может просклонять слово “таск” по падежам — не говоря уж о программистах, которые и представляют собой целевую аудиторию этого поста.

    Если вам показалось что-то непонятным — пожалуйста, пишите. После того, как долго работаешь в какой-то сфере, мозги до какой-то степени “замыливаются” и многие вещи воспринимаешь как само собой разумеющееся. Если где-то это имело место быть — напишите, и я исправлюсь.

    _________________________________________________________________

    Список литературы для домашнего чтения:
    1. Yahoo! Hadoop Tutorial — рекомендую прочитать первым, потому что лучше документации на данный момент просто нет, включая официальный сайт.
    2. Hadoop QuickStart Guide
    3. Hadoop Map/Reduce Tutorial
    4. Hadoop and Distributed Computing at Yahoo!
    5. Term frequency-inverse document frequency — статья в Wikipedia.


    Оригинал фотографии был опубликован по лицензии Creative Commons: www.flickr.com/photos/antichrist/3427853501

    Update: поскольку НЛО временно отключило возможность создавать новые блоги, опубликовал в алгоритмах — в конце концов, Hadoop это далеко не единственная реализация Map/Reduce, а ни одной строчки кода здесь нет. Когда НЛО смилостивится, создам блог Hadoop и перенесу туда вместе с новыми статьями, которые сейчас пишутся.

    Update 2: я же сказал, что продолжение следует? Ну так вот оно — это самое продолжение — читайте и комментируйте!
    Поделиться публикацией

    Комментарии 18

      0
      кстати, вот ещё неплохая статья по теме с реализаций в амазоновском облаке

      techportal.ibuildings.com/2009/11/02/precision-color-searching-with-gmagick-and-amazon-elastic-mapreduce/
        0
        У Амазона вообще очень интересная реализация Hadoop'a — подробностей особых я не знаю, но было бы интересно разобраться (жду какой-нибудь конференции где будем и мы, и они)
          0
          ElasticMapReduce
          Для решения ресурсоёмких задач — самое то. Решил, заплатил за времярешения. Выключил все сервера — результат положил на S3.
            0
            Ну есть еще один вариант — вы постоянно решаете ресурсоемкие задачи. Но в принципе да, для многих задач такое решение подойдет (потому как даже содержать инфраструктуру из десятков серверов уже совсем не дешево и не просто, не говоря уже о сотнях или тысячах).
              +1
              Если вы постоянно решаете ресурсоемкие задачи, значит извлекаете из этого определенную прибыль. В этом случае будет не проблема оплатить счета за Amazon. Более того, сервера автоматически выключаются после решения задачи, поэтому о сохранении средств можно не беспокоиться.
              В любом случае выгоднее запустить облако, чем покупать или арендовать физические сервера.
                +2
                Скажем так — вы правы, но не для всех случаев такое решение применимо. В моем случае все-таки (наверное) выгоднее иметь свои кластеры :-)
            0
            Амазон, конечно, молодцы, несут Hadoop в массы :)

            Но, как и везде, выгоды эластичного Hadoop-а идут не без цены. И дело не только в деньгах, которые платятся за время работы вашего кластера. Я слушал презентацию одного мужика, который работает на громадном Hadoop-кластере в Yahoo, и он говорил, что физическое расположение машин в кластере имеет громадное значение для его производительности. То есть, на амазоновском Hadoop-е можно делать все, что угодно, но производительность будет хромать, что естественно. Но тут уж, кому что. В целом, возможность запускать задачи Map/Reduce по требованию и платить только за использованное время — это очень круто.
          +2
          Кстати, я ЗА создание отдельного блога по Hadoop :)
            +1
            вот кто б мне еще дал его создать ;-)
              0
              Может быть по положительным отзывам пользователей данному вопросу будет дан ход ;)
                0
                Посмотрим ;-) Статьи будут, это я точно могу сказать.
                  0
                  Приятно слышать.
                  С удовольствием почитаю продолжение серии :)
            +2
            Что такое «корпус»?
              +1
              Лингвистическим корпусом называют собрание текстов, собранных в соответствии с определёнными принципами, размеченных по определённому стандарту и обеспеченных специализированной поисковой системой. Иногда корпусом («корпус первого порядка») называют просто любое собрание текстов, объединённых каким-то общим признаком (языком, жанром, автором, периодом создания текстов).


              ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%80%D0%BF%D1%83%D1%81%D0%BD%D0%B0%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B3%D0%B2%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0

              Крайне расхожий термин в области information retrieval.
                0
                В чем различие «текста» и «корпуса» в рамках данной статьи?
                  0
                  Под текстом чаще понимается документ, под корпусом — коллекция документов. Впрочем, обычно это понятно из контекста.
              +1
              Как-то получилось, что и эта статья остановилась на самом интересном месте. Ну и за то спасибо.
                0
                Все будет, я обещаю ;-)

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

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