Pull to refresh

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

Reading time 3 min
Views 14K
Продолжая статью “Использование 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 версию.
Tags:
Hubs:
+32
Comments 13
Comments Comments 13

Articles