Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Функции оценки релевантности

Рассмотрим три наиболее часто используемые функции оценки релевантности:

• TF-IDF

• LexRank

• PageRank

TF-IDF

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

Приведем один из вариантов формулы расчета этого показателя:

TF (term frequency — частота слова) — отношение числа вхождения некоторого слова к общему количеству слов документа. Так оценивается важность слова t в пределах отдельного документа. Вычисляется этот показатель обычно так:

, где n_i есть число вхождений слова t в документ, а в знаменателе находится общее число слов в документе d

IDF (inverse document frequency — обратная частота документа) — инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт IDF уменьшает вес широкоупотребительных слов.

, где |D| — количество документов в коллекции документов, а — количество документов, в которых встречается t (иногда, чтобы избежать возможного деления на 0, к знаменателю прибавляют 1 или же вычисляют idf только в случае, если tf(t,d) не равно 0).

Результирующая мера получается при помощи перемножения полученных чисел tf и idf.

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

LexRank

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

Центральность сообщения обычно понимается как центральность тех слов, которые оно содержит. Обычно для оценки центральности слова прибегают к сравнению его с так называемым центроидом набора документов в векторном пространстве. Центроид – это псевдо-документ, который содержит все слова, для которых рассчитанный показатель tf-idf превышает некоторую заданную границу. В некоторых алгоритмах, основанных на этой идее, предложения, которые содержат большое количество слов, принадлежащих центроиду, считаются центральными.

При использовании алгоритма LexRank поступают следующим образом:

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

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

Первая величина определяется как косинус угла между двумя векторами в N-мерном пространстве (N-количество всех слов в языке, на котором написан текст). Элементы вектора являются произведениями числа вхождений слова в предложения и idf слова. Так, мы приходим к формуле:

, где - число вхождений слова в предложение

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

Формальное обоснование алгоритма вычисления LexRank опирается на теорию цепей Маркова и является довольно громоздким. Опустим его. Суть алгоритма заключается в том, что мы на основе некоторой заданной границы строим по исходному графу граф схожести. После этого те элементы матрицы схожести, которые больше заданной границы, заменяются единицами, а остальные обнуляются. Затем ненулевые элементы матрицы схожести умножаются на степень вершины в графе схожести. Нормированный вектор собственных значений полученной матрицы и содержит значения величины LexRank для каждого из предложений.

Существует модификация этого показателя – непрерывный LexRank. Его идея заключается в том, что не стоит заменять значения в матрице схожести на единицы, а использовать их нормированные значения при вычислении показателя по следующей формуле:

Коэффициент затухания d присутствует в формуле для обеспечения сходимости метода, остальные обозначения имеют очевидный смысл.

PageRank

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

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

Сам алгоритм вычисления этой величины основан на следующем принципе: эта величина принимает значение от 0 до 1, которое показывает, насколько правдоподобным является тот факт, что человек, произвольным образом кликающий на ссылки, попадает на конкретную страницу. В некоторых научных работах полагают, что при начале вычислений эти вероятности должны быть поровну разделены между всеми документами коллекции. Вычисления показателя PageRank требуют нескольких «проходов» по всей коллекции документов. Это делается для того, чтобы полученные показатели наиболее точно отражали реальное соотношение «важности» документов коллекции.

Приведем упрощенную схему алгоритма вычисления PageRank

Предположим, что в нашей коллекции имеется всего 4 веб-страницы: A, B, C и D. Первоначальные значения PR для всех страниц будут равны 0.25.

В оригинальном алгоритме все начальные значения были бы равны 1. Это было сделано для того, чтобы суммарные значения PageRank равнялись общему числу веб-страниц на тот момент. Более поздние модификации алгоритма инициализировали значения показателей значениями, полученными из некоторого распределения.

Если у каждой из страниц B, C и D имеются ссылки только на страницу A, то PR(A) будет равен сумме PR(B), PR(C) и PR(D), так как все ссылки в этой простой системе будут указывать на A:

Предположим теперь, что на странице B расположена ссылка на страницы A и C, а на странице D имеется ссылка на все документы коллекции. В этом случае показатель PR(A) необходимо рассчитывать так:

Получается, что каждая из страниц дает вклад в значение PR, равный PR этой страницы, отнесенной к количеству исходящих ссылок (каждая ссылка на конкретный уникальный документ учитывается только один раз).

В общем случае значение этого показателя для произвольной страницы u может быть вычислено по приведенной ниже формуле:

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

Также при вычислении этой величины иногда исходят из предположения, что даже воображаемый интернет-серфер рано или поздно остановит просмотр. Вводят специальную величину – damping factor (коэффициент затухания). Этот коэффициент показывает, какова вероятность того, что на произвольном шаге пользователь (возможно, воображаемый) продолжает просмотр. Опытным путем были получены различные значения этой величины, но обычно предполагается, что этот коэффициент примерно равен 0.85.

В случае, если мы хотим учитывать этот фактор, формула для подсчета PR слегка модифицируется и принимает вид:

, где d – damping factor, N – число документов в коллекции.

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

Современная модель работы поисковой системы

Рассмотрим современную модель работы поисковой системы. Приведем иллюстрацию:

Дадим краткую характеристику каждому компоненту системы:

client - это программа просмотра конкретного информационного ресурса. В настоящее время наиболее популярны мультипротокольные программы типа Netscape Navigator. Такая программа обеспечивает просмотр документов World Wide Web, Gopher, FTP-архивов, почтовых списков рассылки и групп новостей Usenet. В свою очередь все эти информационные ресурсы являются объектом поиска информационно-поисковой системы.

Характеристики

Список файлов лабораторной работы