http://habrahabr.ru/post/263983/
В предыдущей части мы узнали как выполнить запрос к построенному индексу и теперь мы можем получить ссылки на документы, в которых встречается то, что мы запросили. Но есть проблема: это просто список документов, в которой, возможно, есть то, что нам нужно. Он не отсортирован по важности, для нас, информации, содержащейся в документе. Про эту проблему мы и поговорим в этой части.Ранжирование результатов запросов
Заключительным шагом в построении поискового движка является создание системы для ранжирования документов по их релевантности к запросу. Это наиболее сложная часть, поскольку она не имеет прямого технического решения: она требует творчества и вашего собственного взгляда. В этой мы реализуем TF-IDF ранжирование (от англ. TF — term frequency (частота слова) и IDF — inverse document frequency (обратная частота документа)), которое является одним из простейших способов сортировки наших документов. В этой части не будет никакого кода, но вы можете изучить финальную версию движка на
GitHub. Мы только изучим теорию TF-IDF, а его реализация довольно проста, причем большая часть работы делается во время построения индекса.
Так что, термин «частота» является первой частью нашей систему ранжирования? Ну, это именно то, что приходит на ум, когда вы его слышите: количество раз, которое встречается каждое слово в конкретном документе. Термин частота, как метрика, не учитывает запрос: он предполагает, что документ — это просто амбивалентный набор маркеров, и точное представление о нём можно получить всего лишь пересчитав, сколько раз каждый маркер (слово) встречается. Это не совсем точное предположение, но оно широко используется в области классификации документов. Формально, он больше известен как модель “мешок слов”.
Одним простым представлением модели мешка слов является векторизация документов. То есть, мы раскладываем документ на вектор длинны
N, где
N — общее число уникальных терминов в документе, и каждая запись — это количество раз, которое конкретный термин встречается в этом документе. Для нескольких документов, более удобный способ определения N является количество уникальных слов во всех документах в пространстве поиска. Это позволяет представлять каждый документ как вектор, и все эти векторы имеют равные размерности.
Но подождите! Есть, в настоящее время, большой недостаток в нашей модели. Рассмотрим эти два документа: «Путь они едят торт» и «Пусть они едят тор. Путь они едят торт». Они одинаковы, если не считать того, что второй — просто повторяющийся первый, но их векторное представление очень различно: [1, 1, 1, 1] по сравнению с [2, 2, 2, 2]. Чтобы решить эту проблему, мы превращаем каждый вектор в единичный вектор путем деления его величины (рассчитывается путем извлечения квадратного корня из суммы квадратов каждой записи в векторе), “нормализуем” его. Это превратит наши предыдущие векторы в [½, ½, ½, ½] и [½, ½, ½, ½], делая их такими, какими мы и намерены.
Однако, этого ещё не до достаточно. Частота слова является фатальным недостатком (это гармония для любой греческой трагедии). Этот недостаток заключается в том, что «мешок» рассматривает каждый термин как в равной степени важные в представлении документов. Но это не так: слово “и” говорит нам намного меньше о документе, чем слова “Шекспир” или “хламидиоз”. Но слово «и» встречается гораздо чаще, чем слово “хламидиоз” (по крайней мере в документах, которые читал я), что создаёт ложное подобие сходства между документами (поскольку почти все они содержат слово «и»).
Чтобы избежать этого мы должны кое-что добавить в нашу систему ранжирования: обратную частоту документа. Определим частоту, с которой слово встречается в документе, как
Dt, а
t — как частоту, с которой слово встречается во всех проиндексированных документах. Тогда, если у нас есть
K документов, то обратная частота документа (
Lt) этого слова будет отношением
K к
Dt: общее количество документов, делённое на количество документов, в которых встречается это слово.
Есть ещё один, последний нюанс: это корректирует слишком сильно. Если у нас есть 10 документов (
K = 10) и одно слово встречается в этих документах 10 раз, а другое слово всего 1 раз, то получается, что второе слово в 10 раз важнее первого. Линейное поведение этой функции является слишком радикальным, и будет искусственно снижать сходство из-за слишком сильной корректировки. Чтобы исправить это, мы просто добавим функцию натурального логарифма, которая будет «выравнивать» нашу функцию, делая её коррекцию более плавной. Теперь наша функция выглядит так: в наборе из K документов, для некоторого слова
t,
Lt = ln(K/Dt), где
Dt — это частота документа слова
t, а
ln — это функция натурального логарифма.
Примечание реализации: как вы могли заметить, ни одна из этих величин не зависит от запроса, и обе они могут (и должны) быть вычислено для каждого маркера (слова, термина) и документа заранее!
Теперь, чтобы объединить термины частота слова (в документе) и обратная частота документа в одну метрику мы можем их просто перемножить. То есть, вес каждого маркера (слова, термина) в нашем наборе документов определяется как
Tt×Lt: частота, с которой встречается слово в документе и обратная частота документа.
Теперь, если у нас есть набор из
K документов и все эти документы имеют общее число
N уникальных терминов, то наши документы будут представлены как вектора, каждый длинны
N, где значение каждой записи (которое соответствует термину) равно частоте, с которой термин встречается в документе, умноженной на обратную частоту документа для этого термина в наборе документов. Каждый вектор будет иметь значение 0 для терминов, не встречающихся в документе (помните, что наши вектора представляют все уникальные термины во всём наборе документов). Обратная частота документа никогда не будет равна 0, потому что это уровень сбора метрик.
Теперь мы сделаем то же самое и для запросов: мы будем представлять его в виде вектора в
N-мерном пространстве, как и документы, и вычислять TF-IDF для каждого термина в запросе. Очевидно, это будет более редким (разбросанным), чем в документах.
Небольшое отступление. Попробуем рассчитать показатель подобия между запросом и его результирующем множеством, и ранжировать документы в результирующем множестве за счёт этого. Есть множество различных подходов к этому, но я буду использовать здесь то, что называется коэффициентом Отиаи (cosine similarity), который по сути просто берет скалярное произведение запроса и вектора документа в результирующем множестве и делит это на произведение величин этих двух векторов, который возвращает косинус угла между этими векторами (я мог неправильно объяснить формулу «на словах», поэтому, если вам интересно, можете прочитать статью на
Википедии и
этот вопрос на StackOverflow для уточнения). Это особенно полезный показатель, так как он не берёт во внимание величины двух векторов при вычислении сходства (в отличие, скажем, Евклидова расстояния), что весьма важно, когда у вас есть один очень разреженный вектор (запрос), и другой значительно менее разреженный вектор (наш документ).
Так что, для ранжирования результатов, это то, что мы будем делать:
- Во-первых нужно заранее рассчитать значение TF и IDF для каждого термина, и построить вектор длинны N для каждого документа, используя произведение TF на IDF в качестве записи.
- Затем, мы вычисляем запрос, и получить в результате набор соответствующих документов (с использованием ранее описанной методики).
- После этого мы вычисляем вектор запроса, который также имеет длину N и использует произведение TF×IDF в качестве каждой из этих записей.
- Затем, мы рассчитываем схожесть запроса и каждого документа в результирующем множестве (через коэффициент Отиаи), и получить балл для каждого документа.
- Мы сортируем документы по этому баллу.
И бум, мы всё сделали!
Заключение
Создать поисковой движок, который сможет масштабироваться до размеров гугла невероятно сложно. Но, сделать простой для личного использования (или даже как доказательство концепции) вовсе не так сложно. На самом деле, способ построения индексов поисковых систем, ранжирования и запрос документов совсем понятный, и построение движка — это упражнение, которое стоит сделать.
Модель мешка слов, что мы использовали здесь проявляется везде. Еще один отличный модуль для поискового движка — это спам-фильтр, или классификатор документов, или рекомендация статей, или любой другой модуль. Это очень крутой концепт, и стоит задуматься над тем, как вы будете использовать его для осуществления любой из вышеупомянутых (или чего-то круче).
Как ни крути, это конец статьи. Если у вас есть какие-либо отзывы или вопросы, вы можете оставить комментарий к
оригинальной статье или написать автору на
электронную почту/
facebook/любую другую новомодную социальную сеть, которую используют ваши дети в настоящее время.