Диссертация (1137159), страница 5
Текст из файла (страница 5)
Используяколичество слов, как единицу измерения, получаем размер запроса, равный 2, и12вектор запроса υ = (1 ⋅ IDF (связный ) ,1 ⋅ IDF ( граф)) = (0.23,1.05) . Нужно сравнить порелевантности два документа A и B, которые, предположим, одного размера.Тогда мы можем использовать количество вхождений терма в документ вкачестве его TF-значения. В Таблице 1.4 приведены количество вхожденийтермов запроса в документы, а также соответствующие векторы документов.Таблица 1.4. Количество вхождений термов запроса в документы исоответствующие векторы документов.Документ AДокумент BКоличество вхождений терма «связный»102Количество вхождений терма «граф»43Вектор документаδ A = ( 4.6,8.4 )δB = ( 0.92,6.3 )δ A = 9.6δB = 6.4Оценка (по (2))0.960.9975Простой подсчет количества вхождений термов дает преимуществодокументу A, однако видно, что B фактически лучше удовлетворяет запросу.Это интуитивно доказуемо.
Например, большее число вхождений терма24«связный» в документе A показывает, что этот документ посвящен связям внесколько другом контексте, чем «связные графы», и поэтому слабоудовлетворяет запросу.1.1.3.3 Реалистичные модели ранжированияБольшинствопоисковыхсистемвдействительностииспользуютулучшенную модель вектора документа. Тем не менее, существует множествопротивников данной модели, т.к. самый существенный ее недостаток в том, чтоподход, использующий подсчет частоты вхождений термов, может датьошибочные результаты, т.к.
количество слов на странице подсчитывается«вслепую». Поэтому вносятся корректирующие коэффициенты, основанные натаких факторах, как расположение термов относительно друг друга,статистическиеизмерениякорреляциимеждутермамииаспектамиформатирования страницы (такими как шрифт и размер шрифта, которымпредставлены термы).
Одним из популярных методов ранжирования являетсяOKAPI BM25 [93], где рейтинг документа вычисляется на основе формулы:Ρ(τ, ω) =IDF(ω∑∈ωiωi)(k + 1 )TFω (τ )idTFω (τ ) + k( 1 − b + b τ )id,где, обычно, k=1.2, b=0.75, d τ - длина документа τ (т.е. количество слов вдокументе) и d - средняя длина всех документов. Данная функция пытаетсянормализовать рейтинги документов, исходя из их длины: большой документможет содержать гораздо больше повторений отдельных термов, чеммаленький, и, тем не менее, быть менее релевантным запросу.Следующим улучшенным вариантом является функция OKAPI BM25F, вкоторой ранжирующая функция разбивается на части относительно полейдокумента, таких как заголовки, ссылки, основной текст и т.д.Однако у всех представленных методов существует еще одна проблема.Пользователь, совершающий поиск, ожидает найти авторитетную информациюв результатах поиска раньше, чем все остальное.
Хотя в большинстве случаевстандартные слова в поисковом запросе не выделены особым образом на25анализируемых при поиске страницах. Например, не все производителиавтомобилей используют слово «машина» на своих веб-сайтах! Более того,неавторитетные или даже вредоносные ресурсы могут легко обогнатьавторитетные по рейтингу, просто используя термы несколько раз на своихстраницах: например, при поиске «Volvo», главная страница компании Volvoбудет находится гораздо ниже в рейтинге, чем локальные дистрибьюторыавтомобилей, использующие слово «Volvo» десятки раз у себя на страницах.Это не тот результат, который нужен. Необходимо решение, которое позволилобы оценивать качество страницы независимо от запроса.Эта проблема, а также проблема спама, являются основными причинамивведения в функцию ранжирования (1) коэффициента q(τ ) .1.1.4 Оценка качества документа на основе цитирования: алгоритмPageRankРассмотрим один из наиболее популярных и широко используемых методовоценки качества документов, основанный на подсчете количества ссылокмежду документами, так называемый рейтинг цитируемости.
Примерамицитат могут служить список цитированной литературы в научных работах илигиперссылки между веб-страницами. Идея рейтинга цитируемости заключаетсяв определении качественной оценки документа на основании количества икачества ссылающихся на него документов.Абстрагируясь от того, что цитата представляет собой только ссылку содной страницы на другую без каких-либо специфических атрибутов (т.е. неучитывается размещение ссылки в документе, ее формат и т.д.), можнопредставить ссылочную структуру в виде графа. Предположим, репозиторийсостоит из n документов, имеющих уникальные идентификаторы DOCID,последовательно присвоенные документам и находящиеся в интервале V = [1, n] .Определение 1. Цитатой, или ссылкой, называется упорядоченная парадокументов (i, j) ∈ V 2 .
Ссылками называются исходящая связь документа i ивходящая связь документа j.26Сформировав из всех ссылок между документами из V множество E,становится ясно, что G=(V,E) является ориентированным графом с вершинами,являющимися ссылками. Назовем данный граф графом ссылок.Определение 2. Пусть G=(V,E) и i ∈ V . Тогда множество входящих связейбудет обозначаться как I(i), а множество исходящих связей как O(i), т.е.I(i) = {e ∈ E | e = (j,i), j ∈ V },O(i) = {e ∈ E | e = (i, j), j ∈ V } .Страница I(i)|I(i)| Рейтинг1{2}10.0912{1,3}20.183{1,2}20.18154{1,2,3,5}40.365{1}10.0916{4}10.0916243Рисунок 1.1. Индекс цитирования с подсчетом входящих связей.Определение 3. Документ i ∈ V называется висячим, если O(i) = ∅ .Пример 2.
Тривиальным примером для рейтинга цитируемости будетслужить q(i) = const ⋅ |I(i)| , т.е. документу i присваивается рейтинг, прямопропорциональный числу документов, ссылающихся на него. На Рисунке 1.1представлен граф, в котором простой подсчет входящих связей для каждогоузла и формирует представленные показатели рейтинга (после нормализациипо общему числу связей в графе).Данный метод ранжирования редко применяется при ранжированиипечатных работ или авторов в академической сфере.
Очевидный недостатокданного метода заключается в том, что всем цитатам (ссылкам) присваиваютсяравные весовые коэффициенты. Другими словами, цитата автора, на которогоимеется много ссылок из других ресурсов, приравнивается цитате автора, неимеющего ссылок с других ресурсов. В таких средах, как Веб, данная оценкаявляется абсолютно неадекватной, т.к. основной задачей данного метода27является простой подсчет огромного количества входящих ссылок со страниц снизким качеством.Проблема поиска метода оценки качества ссылок, который бы работал втакой разнородной среде, как Веб, наиболее успешно решилась с изобретениемалгоритма PageRank.
Алгоритм разработан Сергеем Брином и ЛоренсомПейджем и в дальнейшем послужил частью технологической базы поисковойсистемы Google (www.google.com). Впервые алгоритм был описан в [42] и [81],после этого была проведена многолетняя работа на основе этих публикаций.1.1.4.1 Вычисление рейтинга страницы по алгоритму PageRankМожно провести аналогию между списками использованной литературы вакадемических работах и ссылками на определенные страницы в Вебе. Подсчетссылок на страницу из разных источников дает приближенное значениеважности или, другими словами, качества страницы.
Алгоритм PageRankрасширяет данный подход не только подсчетом количества ссылок (принимаязначимость ссылок с каждой из страниц равной), но и упорядочивая страницыпо количеству ссылок, содержащихся в них. Рейтинг страницы по PageRankопределяется следующим образом [81]: Предположим, что на документ Aссылаются страницы T1...Tn . Параметр d является коэффициентом затухания,находящимся в интервале (0;1). Обычно d присваивается значение равное 0.85.C(A) определяет количество исходящих со страницы A ссылок.
Тогда рейтингстраницы A по PageRank определяется какPR(A) = ( 1 − d) + d(PR(T1 ) / C(T1 ) + ... + PR(Tn ) / C(Tn )) .Следует отметить, что PagRank определяет распределение вероятностей длякаждой страницы таким образом, что сумма рейтингов PagRank всех страницбудет равна единице.Рейтинг PageRank (PR(A)) может быть вычислен с использованием простогоитеративного алгоритма и будет соответствовать главному собственномувектору нормализованной матрицы ссылок. Нужно отметить, что рейтинг28PageRank для 26 миллионов веб-страниц может быть вычислен за несколькочасов на рабочей станции средней мощности [42].1.1.4.2 Наглядное обоснованиеАлгоритмпользователя.PageRankможнорассматриватьПредполагается,чтокакмодельвеб-серферповедения(пользователь,«путешествующий» по веб-страницам, т.е.
переходящий по ссылкам с одной надругую) с заданной случайным образом стартовой страницы переходит поссылкам (также выбирая их случайным образом) на другие страницы и никогдане возвращается на предыдущую страницу, иногда прерывая переход поссылкам и начиная снова с другой случайной страницы. Вероятность того, чтовеб-серфер посетит определенную страницу и является ее рейтингом PageRank.А коэффициент затухания d определяет, насколько скоро веб-серфер начнетпроцесс заново, перейдя на случайную страницу.
Единственное важноеразличие в задании фактора d заключается в том, что он может быть присвоенкак группе страниц, так и отдельным страницам. Данный подход позволяетперсонализировать выборку и сводит к минимуму вероятность того, чтосистема ошибется, присваивая странице рейтинг.
Существует несколькорасширений алгоритма Page Rank, описанных в [82].Другое наглядное обоснование того, что страница может иметь высокийрейтингPageRank,заключаетсявопределенииколичествастраниц,ссылающихся на нее и имеющих также высокий рейтинг PagRank. Такимобразом, страницы, на которые ссылается множество документов в вебе,являются более предпочтительными. Также страницы, имеющие хотя бы однуссылку,например,сдомашнейстраницыYahoo!,являютсяболеепредпочтительными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
