Что такое idf в seo

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

TF-IDF с примерами кода: просто и понятно

Здесь я расскажу и покажу в примерах на Python, зачем и как считать стандартный TF-IDF, а также его вариации. Примеры я буду давать по ходу объяснения. Чтобы их понять, нужно иметь представления о базовых понятиях языка программирования Python в версии 2.х либо 3.х (основные типы данных, основные структуры данных, цикл-ветвление, функция, основы генераторов списков и словарей) и понимать, как применять класс Counter из стандартной библиотеки collections

Что это вообще такое?

О том, что же такое TF-IDF, можно прочитать, например, в Википедии. Да и формулу там же можно посмотреть, поэтому теории я коснусь по минимуму, показав больше примеров.

Если кратко, то TF-IDF это term frequency-inverse document frequency или, ежели на великом и могучем, частотность терминов-обратная частотность документов. Впрочем, это я зря, непереведенное смотрелось лучше.

Зачем это нужно?

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

Чем хороша эта метрика?

1. Слова, неважные для вообще всех документов, например, предлоги или междометия — получат очень низкий вес TF-IDF (потому что часто встречаются во всех-всех документах), а важные — высокий.

2. Её просто считать

Для чего же можно применять эту метрику?

1. Выявление важных слов и стоп-слов в документах

2. Некоторые расширения этой формулы можно использовать для улучшения работы классификаторов тональности

Принцип работы

Term Frequency

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

TF термина а = (Количество раз, когда термин а встретился в тексте / количество всех слов в тексте)

В виде кода это будет выглядеть так:

Inverse Document Frequency

IDF — это обратная частотность документов. Она измеряет непосредственно важность термина. То есть, когда мы считали TF, все термины считаются как бы равными по важности друг другу. Но всем известно, что, например, предлоги встречаются очень часто, хотя практически не влияют на смысл текста. И что с этим поделать? Ответ прост — посчитать IDF. Он считается как логарифм от общего количества документов, делённого на количество документов, в которых встречается термин а.

IDF термина а = логарифм(Общее количество документов / Количество документов, в которых встречается термин а)

Логарифм, кстати, можно брать любой — потому что TF-IDF является относительной мерой; то есть веса терминов не выражаются в каких-то единицах, а существуют друг относительно друга. Я, например, обычно беру натуральный или десятичный.

В виде кода это будет выглядеть так:

Term Frequency — Inverse Document Frequency

А затем мы умножаем TF на IDF и получаем — барабанная дробь — TF-IDF!

TF-IDF термина а = (TF термина а) * (IDF термина а)

В виде кода это будет выглядеть так:

Мы обходим каждый текст в корпусе текстов, считаем для него TF всех слов, находящихся в нем. Затем для каждого слова считаем IDF и умножаем его на уже посчитанный TF. Полученный словарь (dictionary) мы добавляем в список, чтобы сохранить такой же порядок текстов, какой был на входе. И возвращаем этот список словарей с посчитанными TF-IDF для каждого термина.

from collections import Counter
import math

def compute_idf(word, corpus):

return math.log10(len(corpus)/sum([1.0 for i in corpus if word in i]))

for text in corpus:

for word in computed_tf:

tf_idf_dictionary[word] = computed_tf[word] * compute_idf(word, corpus)

corpus = [[‘pasta’, ‘la’, ‘vista’, ‘baby’, ‘la’, ‘vista’],
[‘hasta’, ‘siempre’, ‘comandante’, ‘baby’, ‘la’, ‘siempre’],
[‘siempre’, ‘comandante’, ‘baby’, ‘la’, ‘siempre’]]

Умозрительный пример (в котором мы применяем десятичный логарифм)

В некотором документе Х, содержащем 100 слов, есть слово «лингвист», которое встречается 5 раз. Таким образом, TF слова «лингвист» равняется 5 / 100 или 0.05. А теперь представим, что всего у нас есть 1000 документов (включая документ Х), и слово «лингвист» встречается в 10 из них. Таким образом, IDF слова «лингвист» равняется lg(1000/10) или 2. Таким образом, TF-IDF слова «лингвист» равняется 2 * 0.05 или 0.1

Естественно, вместо документов у нас легко могут быть какие-нибудь абстрактные категории или конкретные ящики, а вместо слов — абстрактные объекты или конкретные фрукты: TF-IDF — вполне универсальная метрика для измерения важности.

Некоторые расширения TF-IDF

В некоторых случаях TF-IDF может считаться по-иному (если вдруг не нравится работа стандартного алгоритма — можно и поэкспериментировать!)

Расширения TF

1. Можно считать TF бинарно, т.е. просто проверять наличие термина в тексте и присваивать единицу, если термин в тексте есть.

2.Можно считать TF без нормализации, то есть брать просто частоту встречаемости слова в тексте без деления этой частоты на общее количество слов в тексте

3. Можно нормализовать частоту встречаемости слова с помощью логарифма таким образом, что

TF термина а = 1 + логарифм(Количество раз, когда термин а встретился в тексте)

4. Можно проводить двойную нормализацию частоты встречаемости слова таким образом, что

TF термина а = 0.5 + 0.5 * (Количество раз, когда термин а встретился в тексте / Количество раз, когда встретился самый частотный термин этого текста)

Этот вариант полезен для измерения частотности терминов в корпусе текстов, где очень большие тексты соседствуют с очень маленькими — данный вид измерения TF нивелирует возможную ошибку, вызванную влиянием размера текста.

Расширения IDF

1. Можно вообще его не учитывать — считать всегда единицей и всё.

2. Можно произвести смягчение (smoothing) IDF — считать как в стандартном виде, только добавлять единицу в скобках, то есть

IDF термина а = логарифм(1 + (Общее количество документов / Количество документов, в которых встречается термин а))

3. Можно извратиться сильнее и считать IDF так:

IDF термина а = логарифм(1 + (Количество раз, когда встретился самый частотный термин среди тех документов, в которых встречается термин а / Количество документов, в которых встречается термин а))

Этот вариант расчёта IDF призван снизить влияние размера документов на получающийся IDF терминов.

На практике эти расширения используют нечасто, особенно те, которые для расчёта IDF. Чаще всего используют второй, третий и четвертый варианты расчета TF со стандартным способом расчёта IDF.

В следующей статье я планирую коснуться интересных расширений стандартного алгоритма TF-IDF, который можно (а иногда даже и нужно) использовать для классификации тональности

Полезные ссылки

78,965 просмотров всего, 2 просмотров сегодня

Источник

Инструкция по расчету TF-IDF

Задача по расчету TF-IDF документов.

Отранжировать по TF-IDF 5 документов по запросам:

Решение данной задачи сводится к следующим действиям:

Рассмотрим подробно каждый из пунктов

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

Пример слов, которые учитывать не нужно: «как», «с», «со», «и», «или» и т.д. и т.п.

Как производился подсчет (считали количество слов, выделенных зеленым):

Несмотря на то, что данный пункт звучит громоздко и непонятно – сделать его проще простого.

Для начала вспомним наш список запросов:

Разобьем запросы на слова и выделим те, которые являются уникальными по отношению ко всем запросам:

Получился следующий список уникальных слов:

Если Вам не понятно почему «окна» выделили один раз – когда мы анализировали первый раз слова «окна», то до этого оно у нас не встречалось и поэтому оно является уникальным. Последующие повторения уже не являются уникальными.

Что такое словоформа? Это однокоренное слово в той же части речи, что и исходное слово.

Например, попробуем найти словоформы для слова «окна». «Окна» — существительное. Однокоренными словами существительными будут «окно», «окон», «окнам» и т.д. и т.п. А вот слово «оконные» уже не будет являться словоформой, т.к. это уже прилагательные. Не забывайте этот важный момент.

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

Напоминаю, что список уникальных слов с предыдущего этапа у нас

Слово «пластиковые» и его словоформы (вхождения выделены зеленым)

Слово «окна» и его словоформы (вхождения выделены синим цветом)

Важно! Обратите внимание, что мы не посчитали вхождение «Оконные» из 3 документа, т.к. это слово не подходит под определение словоформы по причине того, что это другая часть речи

Слово «пвх» и его словоформы (вхождения выделены красным цветом)

Слово «Krauss» и его словоформы (вхождения выделены оранжевым цветом)

TF – количество употребления ключевого термина по отношению ко всем словам в документе

Т.е. TF считается для каждого из уникальных слов («пластиковые», «окна», «пвх», «kraus») в каждом документе

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

Несколько примеров расчетов:

Все получившиеся значения TF вы можете посмотреть в файле «Расчеты.xlsx»

DF – это отношения количества документов, в котором встречается ключевой термин к общему количеству документов.

Общее количество документов у нас известно – изначально оно составляло 5 штук.

Теперь разберем как считать количество документов, в котором встречается ключевой термин.

На этом моменте ошибаются многие – не будьте в их числе

Все получившиеся значения DF вы можете посмотреть в файле «Расчеты.xlsx»

IDF считается для каждого ключевого термина по формуле «1/DF»

Например, DF ключевого термина «пластиковые» 0,6. Для того, чтобы посчитать IDF мы должны 1 разделить на 0,6 и записать получившийся результат (1,666666667).

Все получившиеся значения IDF вы можете посмотреть в файле «Расчеты.xlsx»

TF*IDF считается для каждого ключевого термина в документе путем умножения TF ключевого термина на его IDF

Например, для термина «пластиковые» первого документа TF*IDF будет равен произведению 0,071428571 (TF ключевого термина «пластиковые» 1 документа) на 1,666666667 (IDF слова «пластиковые») в результате чего получится значение 0,12.

Все получившиеся значения TF*IDF вы можете посмотреть в файле «Расчеты.xlsx»

Теперь нам осталось посчитать вес терминов и в соответствии с ним отранжировать сайты.

Например, чтобы посчитать вес ключевого слова «пластиковые окна» для 5 документа сложим TF*IDF термина «пластиковые» (0,13) и TF*IDF термина «окна» (0,51) в результате чего получим итоговый вес ключевой фразы, равный 0,64 (0,13+0,51)

Если несколько документов имеют один и тот же вес для ключевой фразы, то ранжирование происходит по порядковому номеру документа

Источник

Алгоритм Okapi BM25 – модификация формулы TF-IDF ранжирования документов

BM25 – функция расчета текстовой релевантности документов, разработанная британцами Стивеном Робертсоном и Карен Спарк Джоунс, опубликованная в 1994 году. Основана на эмпирических данных при попытке улучшить результаты работы критерия TF-IDF. Наилучшее соответствие между ожидаемым результатом и рассчитанным показал 25 алгоритм в списке, за что и получил свое название «Best matching», или BM25. Впервые был реализован в поисковой системе Okapi (Окапи), а в дальнейшем – положен в основу текстовых анализаторов современных поисковых машин.

Что такое TF-IDF

TF-IDF – формула оценки значимости определенного слова в документе относительно всей выборки. Разработана Джорджом Солтоном в середине 70-х годов. Согласно TF-IDF, вес слова пропорционален количеству употреблений в текущем документе и обратно пропорционален частоте употребления слова в других документах выборки. Если слово используется в этом документе чаще, чем в других, то оно имеет большую значимость для него – именно такой критерий релевантности документа по запросу был у первых анализаторов поисковых систем.

Расшифровка TF-IDF

TF (term frequency) – это частотность слова, показывающая, насколько часто оно употребляется в документе. В длинном тексте вхождений термина может быть значительно больше, чем в коротком, хотя это вовсе не означает, что он точнее отвечает требованиям посетителей. Чтобы уравнять шансы длинных и коротких документов, используется отношение количества употребления слова к общему количеству слов в документе.

IDF (inverse document frequency) – обратная частота употребления слова в документе. Вводится в формулу для снижения веса часто употребляемых слов в выборке. После расчета TF мы получили только частотность, но слова сами по себе еще равнозначны. Часто употребляемые предлоги и союзы не могут быть сопоставимы по важности с другими словам, так как не несут смысловой нагрузки, поэтому, чтобы перераспределить вес значимости, вводится множитель IDF. Редкие слова получают более высокую значимость, а часто употребляемые – низкую.

Основание логарифма может быть любым, так как IDF является относительной мерой. Итоговая формула выглядит следующим образом:

Расчет TF-IDF

Возьмем условный документ X, состоящий из 456 слов и содержащий 2 вхождения термина «компьютер». TF для этого слова будет составлять:

Вычислим IDF, предположив, что у нас всего 210420 документов в выборке и 10241 из них содержат термин «компьютер»:

Умножив TF на IDF, получаем оценку важности термина «компьютер» для документа X: TF­IDF=0,004386·1,312745=0,005758. Рассмотрим другой пример. У нас есть 4 условных документа, имеющих следующее содержание:

Рассчитаем TF-IDF для данных документов по ключевым словам:

Посчитаем общее количество слов в документах, а также количество вхождений каждого слова из запроса в документ.

Рассчитаем множители TF и IDF для каждого слова:

В итоге получаем TF-IDF равным:

Вес запросов относительно документов рассчитаем как сумму TF-IDF каждого слова из запроса:

Запрос «Релевантность» наиболее значимый в 3 документе, что не удивительно, ведь в нем, больше всего вхождений. По аналогичной причине запрос «Текстовая релевантность» более значим в 1 документе. Дальше интереснее – первый текст вовсе не содержит слов «Документа», «Поиске», но при этом все равно выигрывает у других по оценке TF-IDF. Стоит отметить, что абсолютно все слова, по которым идет поиск, не содержит ни один документ. Больше всего, а именно 3 слова из 4, содержит третий документ. Добавим недостающее слово «Текстовая» в третий текст и посмотрим на результаты:

Ситуация ожидаемо изменилась в пользу документа 3, за ним идет документ 4, а первый – только на третьем месте. При этом в документы 4 и 1 никаких изменений не вносилось. Уберем предыдущее изменение и добавим слово «Релевантность» в документ 4. IDF по этому запросу равен 0, т.к. запрос встречается во всех документах. За счет этого документ 4 выигрывает оценку TF-IDF по запросу «Текстовая релевантность документа в поиске».

Скачать Пример расчета TF-IDF При увеличении вхождений ключевого слова в документ пропорционально увеличивается значение TF. Таким образом, добавление вхождений ключевых слов на страницу значительно повышает ее релевантность. Функция BM25 должна была устранить этот недостаток.

Расшифровка BM25

Робертсон хоть и утверждает, что для получения формулы использовалась вероятностная модель, но некоторые специалисты считают ее «подгонкой» под нужный результат. В функцию БМ25 внедрены свободные коэффициенты, которые могут принимать различные значения. Они подбираются так, чтобы «подогнать» результат работы поиска под заранее имеющиеся данные. Документы сначала оценивают асессоры, которые и говорят что плохо, а что хорошо. Затем на основании этих данных выбирают упомянутые коэффициенты, чтобы расположить документы так же, как это сделали асессоры – так называемый «принцип обезьянки». Оценка релевантности документа

используется сглаженная формула:

Релевантность по запросу Q равна сумме релевантностей по всем словам q_i=q₁,q₂…q_n из запроса. На первый взгляд, принцип работы такой же, как и TF-IDF:

Процентный рост BM25 от числа вхождений

Зависимость Score от объема текста (TF уменьшается).

Немногие помнят «золотую эру SEO», когда вебмастера спамили ключевыми словами, достигали более высокой релевантности за счет их количества и, добавив ко всему этому тысячу сапо-ссылок, за пару недель выходили в ТОП.

Расчет BM-25

Возьмем те же тексты и рассчитаем количество документов, содержащих слова из запроса, и среднюю длину документа.

Далее найдем IDF для каждого слова из запроса

В итоге получаем следующее значение TF и оценку Score по запросу «Текстовая релевантность документа в поиске»:

Скачать Пример расчета BM25 Наглядный пример, того как IDF может принимать отрицательные значения для слов, которые встречаются больше чем в половине документов. Вместо отрицательного значения IDF брали фиксированное IDF=0,01. Наибольшую оценку получил «документ 3», хотя в классической TF-IDF формуле – документ 1, который теперь имеет самую низкую оценку Score по BM25. Распределение оценок по различным запросам:

До этого мы рассматривали ограниченную выборку, в которой заранее известно, что документы околотематические. Для лучшего понимания формулы рассмотрим пример с нетематической коллекцией документов. Найдем Score в выборке из 20 000 документов.

IDF для слова «документа» значительно больше, чем для слов «релевантность» и «текстовая». Теперь увеличим частоту слова «документа» в док2 с 2% до 5%.

Видим значительный рост TF и Score при неизменном IDF. Увеличим частоту «текстовая» до 6% в док 1.

Сумма частот каждого слова из запроса в документе 1 и документе 2 одинаковая и составляет 13%, но термин «документа» меньше употребляется в коллекции. Из итоговой оценки и можно говорить, что значимость узкоспециализированных слов значительно выше, чем других терминов из запроса.

Тошнота документа по Минычу

В 2006-2007 годах по методике пользователя под ником Миныч на форуме Searchengines решили, что в Яндексе при расчете релевантности использовались похожие формулы:

Видим, что по данной формуле максимальная релевантность достигается, когда продвигаемый запрос t_i является самым частотным в документе n(t_i,d)=n_max, а плотность ключевого слова вообще не влияет на оценку. Миныч – первый, кто ввел понятие «Тошнота». В его методике тошнота W=max(√7,√n_max) – квадратный корень от частоты самого употребляемого слова nmax в документе. Если n_max меньше 7, то W=√7. При превышении некоторого порога спамности для конкретного слова, например W>25, накладывалась пессимизация документа.

Недостатки TF-IDF и BM-25

Используемая модель «bag-of-words» (мешок слов) не учитывает:

Поэтому одна лишь формула BM25 в чистом виде для оценки релевантности документа не использовалась.

Текстовые факторы ранжирования Яндекса (РОМИП-2006)

На РОМИП-2006 представители Яндекса несколько приоткрыли завесу тайны по используемым текстовым факторам ранжирования:

Вот несколько цитат:

При подсчете количества вхождений слова в документ мы проводим предварительную лемматизацию слов запроса и слов документа. Использование в качестве меры длины документа максимальной TF среди всех лемм документа ухудшает результат.

Помимо учета количества слов в документе можно учитывать html-форматирование и позицию слова в документе. Мы учитываем это в виде отдельного слагаемого. Учитывается наличие слова в первом предложении, во втором предложении, внутри выделяющих html тегов.

Пара учитывается, когда слова запроса встречаются в тексте подряд (+1), через слово (+0.5) или в обратном порядке (+0.5). Плюс еще специальный случай, когда слова, идущие в запросе через одно, в тексте встречаются подряд (+0.1).

На 2010 год, по словам Дена Расковалова, в Яндексе учитывалось более 420 факторов ранжирования, а приведенные выше – это только малая часть из них.

Модифицированная формула BM25F

Все указанные достоинства и недостатки TF-IDF подобных формул были учтены при создании действующих алгоритмов ранжирования. В 2009 году Яндекс внедрил машинное обучение Матрикснет. Научился понимать морфологию запроса, учитывать наличие синонимов (тезаурусов) в документе, регулярно внедряет новые технологии для улучшения качества поиска. Сегодня релевантность определяется отдельно для зон документа, а за неестественное или чрезмерное количество ключей благополучно накладываются текстовые пост-фильтры. Границы текстовой переоптимизации могут довольно часто сдвигаться, причем независимо для каждой зоны документа. Сегодня документ попал в «зеленую зону» и вы в ТОПе, завтра границы сдвинулись и вы вылетели. BM25 field (BM25F) – функция расчета релевантности по зонам документа:

Для оценки влияния ссылочных факторов существуют отдельные функции: LF-IDF, LinkBM25. Современная SEO-оптимизация – это непрерывные эксперименты с количеством вхождений, словоформой, положением ключевых слов в документе и т.п. Знание и понимание таких основ текстового ранжирования, как TF-IDF, BM25 существенно облегчают жизнь оптимизатора, внося долю ясности в непознанный мир Платонов Щукиных.

Источник