Книги, научные публикации
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ ПОИСКОВЫЕ СИСТЕМЫ:
КОМПОНЕНТЫ, ЛОГИКА И МЕТОДЫ РАНЖИРОВАНИЯ А.В. Кириллов, аспирант кафедры инноваций и бизнеса в сфере информационных технологий факультета бизнес-информатики Государственного университета- Высшей школы экономики, инженер-программист ЗАО Фирма Клуб 400.
Адрес: г. Москва, Варшавское шоссе, д. 39, e-mail: antonv.kirillov@gmail.com.
АннотацияВ статье рассматриваются принципы построения поисковой системы и ее ком понентов, а также методы ранжирования результатов, в частности, основанный на рейтин ге цитирования алгоритм PageRank. Детально анализируется проблема выборки документов, релевантных поисковому запросу, в гетерогенной среде, такой как World Wide Web. Продемон стрирована необходимость расширения классических методов поиска информации при помощи методов ранжирования, учитывающих рейтинг цитирования.
Ключевые слова: поисковые машины, рейтинг цитирования, гетерогенное окружение.
1. Введение Фундаментальной проблемой при разработке по исковых систем является определение релевант настоящее время все большее количество ности - ситуации, когда документ соответствует знаний, накопленных человечеством, хра запросу. Архитектура поисковой системы основы В нится в компьютеризированных репозито вается на идеях из области поиска информации, риях, таких как Всемирная Сеть (World Wide Web).
предоставляющей методы определения релевант Данная ситуация влечет за собой проблему поиска ности документа по его фактическому содержимо определенной информации в этих часто неструкту му. Тем не менее, в гетерогенной среде, такой как рированных репозиториях, которая решается при WWW, эти методы сами по себе оказываются неэф помощи поисковых систем. Концепция поисковой фективными. Кроме того, что гораздо хуже, эти ме системы достаточно проста: пользователь вводит тоды не защищены от мошенничества со стороны поисковый запрос, состоящий из нескольких клю- людей, пытающихся извлечь из поисковых систем чевых слов, относящихся к целевым документам, коммерческую выгоду.
которые должны быть извлечены из репозитория. Именно поэтому современные поисковые си стемы рассматривают весовые факторы, которые Результатом работы поисковой системы является упорядоченный набор документов, которые счита- не имеют прямой зависимости от содержимого до кумента. Общий метод, пригодный в информаци ются релевантными данному запросу.
БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ онных репозиториях, использующих гиперссылки, R Множество, являющееся внутренним представ таких как WWW, состоит в анализе структуры ссы лением универсума, называется репозиторием.
U лок, образованной между документами. Наиболее Репозиторий имеет вид R ={ 1 d n}, где d успешным алгоритмом из этой категории является каждое является документом, а Ч соответ d d алгоритм PageRank, предложенный основателями ствующим уникальным идентификатором этого поисковой системы Google.
документа, называющимся DOCID. Когда речь идет о документе d, используется преобразова 2. Поисковые системы ние d. Каждое представление зависит, d d в первую очередь, от поисковой системы.
В повседневной речи под термином поисковая I Следует отметить, что функция обычно при система понимается программное обеспечение, меняется к подмножеству множества, и U U состоящее из базы данных документов, снаб поэтому поиск происходит только в части всего женной пользовательским интерфейсом, позво репозитория R = I(U ). Объясняется это тем, что ляющим пользователю получить упорядоченное множество слишком велико, чтобы быть про U подмножество этих документов как ответ на его по анализировано полностью (см. ниже).
исковый запрос. Основная задача поисковой систе Проиллюстрируем концепцию индексирования мы заключается в выборе наилучшего возможного на примере поисковой системы для Веба. Место подмножества в ответ на конкретный запрос, т.е.
нахождение веб-страниц обычно определяется множества документов, которые наиболее соответ по Unified Resource Locator или URL (например, ствуют тому, что ищет пользователь (обычно в по При индексировании сети си рядке убывания релевантности).
стема имеет дело с набором URL различных доку Самыми распространенными примерами поис ментов (которые в Вебе называются страницами) и ковых систем, используемых повсюду, являются последовательно присваивает им идентификаторы поисковые системы для Веба (такие как Google и (DOCID). Затем данные страницы выгружаются из Yahoo, например), которые применяются для об Веба и создается репозиторий, т.е. хранилище вну наружения текстовой информации (например, до тренних представлений каждой из страниц. Коли кументы в формате HTML и PDF), хранящейся на чество выгружаемых страниц обычно очень велико веб-серверах, расположенных по всему миру. Схо (в современных поисковых системах это порядка жие технологии используются и при поиске инфор 1010 документов), но, тем не менее, оно значитель мации в корпоративных внутренних сетях.
U но меньше реального числа страниц в, т.е. коли чества страниц, находящихся в Интернете. Таким 3 Формальные компоненты поисковой системы образом, основной задачей построения поисковых Большинство поисковых систем состоит из двух систем для Веба является определение адекватного основных, независимых компонентов, которыми подмножества множества.
U U являются компонент индексирования и компонент Рассмотрим компонент поиска, который обраща поиска. Пользователю доступен только поисковый ется к документам, расположенным в репозитирии компонент. Компонент индексирования использу- для того, чтобы осуществить выборку, соответству ется для создания внутреннего эффективного пред- ющую поисковому запросу. Формально, поиско ставления данных, в которых будет производиться вый компонент может быть представлен как про поиск необходимой информации, а поисковый грамма, реализующая преобразование S :, компонент отвечает за получение результатов из где - поисковый запрос, т.е. конечная строка, внутренней базы данных в ответ на поисковый за- введенная пользователем (принадлежащая исполь прос пользователя. зуемому алфавиту). Поисковый запрос принято Формально компонент индексации может быть считать состоящим из термов, являющихся атомар I :U R U представлен функцией. Множество ными словами, поиск которых ведется, и опера называется универсумом и содержит данные, среди торов, которые описывают, как интерпретировать которых будет вестись поиск. Для поисковой системы термы. Например, в поисковом запросе лцепи Мар Интернета - это страницы, которые мы загружаем кова, запрос состоит из термов 1 = Маркова и из сети, для графической поисковой системы им 2 = цепи. Оператором в данном случае будет яв будет являться набор изображений, а для академи- ляться логическое И, что описывает ситуацию, ческой поисковой системы универсум будет пред- когда нам необходимы документы, содержащие оба ставлен, например, собранием работ, статей и книг. этих терма.
БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ использованием логического метода. Основная В преобразовании Ч это ре S :
идея данного метода заключается в том, что резуль зультат, являющийся упорядоченным набо тирующее множество поискового запроса (такого ром (или же вектором) отдельных документов:
как, например, лцепи Маркова) должно содержать, где исполь = (,,..., ) ~ (1,,..., ) 2 r 1 2 r только страницы, относящиеся ко всем уникаль зуется свойство изоморфности документов, такое, ным термам запроса (в данном случае ими будут i : s что фактически является идентификатором являться Маркова и лцепи). Затем ответ на по документа(DOCID). Количество возвращаемых исковый запрос может быть дан после просмотра r = документов,, называется эффективностью всех документов, содержащих термы Маркова и поиска для данного поискового запроса. Очевидно, Цепи, используя документы, содержащие пере что 0 r n.
сечение данных термов как результирующее мно Результат - это информация, представляемая пользователю. Элементы - это все докумен- жество претендентов.
Так происходит по той причине, что основной ты, которые поисковая система сочла достаточно задачей компонента индексации является построе подходящими для включения в результирующий ние инвертированного индекса, являющегося струк набор. Более того, элементы в результирующем i турой данных, в которой термам в соответствие множестве расположены в таком порядке, что считается более значимым для пользователя, чем ставятся документы (или же DOCID), содержащие i+1. При обычном веб-поиске 10 документов, данные слова (как расширение в, например, поис представленных на первой странице результатов, ковой системе изображений, терм лицо может будут соответствовать 1 Ц. Точность опреде- быть привязан ко всем документам, которые клас ляется долей возвращенных документов, которые сифицируются как содержащие лица).
фактически релевантны, т.е.
Таблица 1.
Пример инвертированного индекса.
{Релевантные _ документы} Точность = Терм DOCID документов, содержащих данный терм Здесь понятие релевантности является абсолют но произвольным и полностью зависит от поиско- Маркова 35, 678, 432,1839, 6456, Е вой системы (или, возможно, от ее пользователей).
цепи 7834, 889, 8912, 325, 91, Е Рассмотрим проблему получения на основа-..
нии поискового запроса и репозитория. По-..
R исковая система обычно осуществляет выборку..
в два этапа:
~ 1. Выбор множества претендентов R, та В таблице 1 представлен пример инвертирован ~ кого, что все элементы в той или иной степени ного индекса. Инвертированный индекс является релевантны поисковому запросу. Определение одной из важных частей вышеупомянутого вну релевантности на данном этапе очень прибли треннего представления документов. Запрос, таким женное. Например, может быть использован ло образом, подвергается декомпозиции в древовид гический метод, рассматриваемый далее.
ную структуру с термами (т.е. атомарными слова ~ i 2. Для каждого определяется его ре ми или фразами) в качестве листьев и логическими ~ (i ) левантность Rel, а затем сортируется в операторами в качестве узлов.
порядке уменьшения релевантности. В процес Наиболее используемыми логическими опера се сортировки некоторые элементы, имеющие торами являются AND, OR и NOT, равнозначные релевантность ниже порогового значения, могут операциям (пересечения), (объединения) и быть исключены из выборки. Результирующей (дополнения) между множествами DOCID со выборкой будет являться.
ответственно. В дальнейшем эти символы будут использованы для того, чтобы различать операции над множествами и логические операции. AND 4. Логический метод определения обычно подразумевает отсутствие оператора между множества претендентов двумя термами. Несколько примеров логических Рассмотрим процесс определения множества представлений поисковых запросов представлены ~ претендентов, который обычно происходит с в таблице 2.
БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ Логическое сравнение является простым путем является проблемой в более контролируемых сре ~ получения множества потенциально релевант- дах, таких как поисковые системы для академиче ных документов, но, конечно, не представляет их в ских работ или внутренних сетей.
порядке соответствия запросу. Поэтому необходи- Обратим внимание на особенности ранжиро ~ мо использовать разные методы при сортировке вания в неконтролируемых средах, таких как Веб.
и при получении. Здесь функция ранжирования принимает в расчет Таблица 2. как внешние факторы (on-page factors): информаци Примеры логических интерпретаций онное содержимое и его размещение на странице, так и внутренние факторы (inter-page factors): обыч поисковых запросов.
но, информация о том, как страницы соотносятся с Запрос Логическая интерпретация другими посредством гиперссылок и т.п. Основное внимание следует уделить внутреннему фактору Маркова Цепи {Маркова} {Цепи} гиперссылок между страницами: предварительно проведем небольшой обзор процесса ранжирова Маркова епи {Маркова} {Цепи} ния в целом. Мотивацией к изучению внутренних Маркова {Маркова} ({Цепь} {Процесс}) факторов является то, что все внешние факторы (Цепь OR Процесс) находятся под полным контролем автора страницы.
Изучение различных отношений внутри документа ~ 5. Проблема ранжирования: переход от к с гораздо большим числом страниц позволяет бо лее эластично оценить качество исследуемой стра ~ В дальнейшем, после определения, про ницы.
исходит поиск зависимой от поискового запро В общем случае, функция ранжирования по са функции ранжирования или релевантности исковой системы для Веба выбирается следующим такой, что, образом:
если элемент i считается более релевантным за просу, чем, и, таким образом, должен находить j (1) ся в до него. Другими словами, результирующее множество должно быть отсортировано по убы где (,) является показателем документа для ванию значения. Функции класса явля запроса по внешним факторам, т.е. насколь ются строго охраняемым секретным компонентом ко релевантна информация, расположенная на любой поисковой системы и определяют схему странице, по отношению к запросу, а q( ) ранжирования, т.е. те характеристики документа, является качественной функцией от, которая которые были определены как значимые при фор рассчитывается на основании факторов, не пред мировании результатов для определенного поис ставленных непосредственно на самой странице.
кового запроса.
Качественная функция q может включать в себя Логический метод в той или иной степени явля такие вещи, как внутренние факторы страницы и ется применимым к любому набору данных, одна ручное вмешательство (т.е. страница была специ ко проблема ранжирования в высшей степени за ально изменена для поднятия рейтинга и позиции висит от окружения, из которого данные были U в результатах поиска). Следует отметить, что q не извлечены. Например, поисковые системы для является функцией, зависящей от запроса, а скорее веба постоянно сталкиваются с проблемой спама:
присваивает обобщенный весовой коэффициент веб-страницы, которые пытаются перехитрить каждой странице независимо от запроса. Функция поисковые системы, предоставляя необычайно q принимает значения в пределах [0;
1], таким об высокое значение для конкурентоспособного разом, умножение на q используется для дампинга : s, тем самым, рассчитывая на увеличение ко рангов документов (т.е. набранных ими лочков по личества появлений страницы в результатах поис внешним факторам).
ка. Данная проблема приводит к тому, что функция Рассмотрим далее три возможных метода опреде должна определяться как можно тщательнее и (,) ления.
скептически. Тем временем также и не стоит отсеи вать честные документы. Это приводит к тому, 5.1. Логический метод ранжирования что решение проблемы ранжирования результатов в неконтролируемой среде становится очень вос- Представим простейшую поисковую систему, требованным и перспективным. Обычно спам не принимающую значение (,) =1, и в результате БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ имеющую. Результирующее множе- значение IDF. В таблице 3 представлены примеры ство будет состоять исключительно из множества вычисленных значений IDF для некоторых термов ~ претендентов, отсортированного по убыванию (в примере используются словосочетания), отно значения q. Так функционирует чисто логическая сящихся к хорошо известной теории множеств, но поисковая система: все страницы, имеющие любое с возрастающей степенью обобщения и, поэтому, отношение к термам, которые ищет пользователь, с убывающим количеством содержащейся в доку одинаково релевантны поисковому запросу.
ментах полезной информации.
TF и IDF будут использоваться для определения ~ 5.2. Ранжирование на основе вектора документа оценки документа. Для каждого определим вектор документа, состоящий из L элементов Подход к ранжированию с использованием (по одному для каждого терма), такой, что выпол вектора документа является достаточно популяр няется соотношение ной технологией.
Первым предположением в данной модели яв.
ляется то, что документ должен иметь высо i Элементы вектора документа, таким образом, кий рейтинг по терму, если данный терм часто являются относительной единицей измерения от встречается на этой странице. Предположим, что ношения частоты вхождений терма в документ к L запрос состоит из термов: 1,...,L. Зада частоте появления терма в репозитории в целом и, дим частоту термов,, как отношение коли по существу, данные элементы принимают во вни i чества появлений терма в документе к размеру S ( ) документа в некоторых удобных единицах из- мание как значимость терма в документе, так и его предполагаемую информационную значимость.
мерения (например, количество слов или байтов).
Далее, предположим, что некоторые термы более значимы при поиске, чем другие. Стандартный ме- Таблица 3.
тод определения значимости термов заключается в IDF, вычисленные поисковой системой Yahoo, нахождении инверсивной частоты документа. Пред- при R приблизительно равном 2 R положим, что является подмножеством репози i тория, состоящим из документов, содержащих терм Терм Количество вхождений IDF i. Вероятность p того, что документ, выбранный i случайно, будет содержать терм, такова:
теорема Перрона - Фробениуса 8270 6. R i цепь Маркова 1050000 4..
p = R теория вероятностей 10900000 3. В Теории информации Шэннона [1] это соответ математика 92900000 2. ствует собственной информации (self-information).
log2 ( ) наука 816000000 1. p На основании этого определяется инверсивная Можно рассматривать поисковый запрос как до частота документа кумент сортов, в котором каждый из термов запро R IDF(i) = log( ) са встречается только один раз. Пусть - это L - R - i вектор для каждого i = S IDF(i ) (где S - это, размер запроса, представленный в тех же единицах т.е. логарифм отношения общего числа докумен измерения, что и размер документа, о котором го тов в репозитории к количеству документов, со ворилось ранее). Помимо этого, можно рассма i держащих терм (обычно, принято использовать тривать это как вектор документа для запроса. Так логарифм по основанию 10). Инверсивная частота как неизвестно, каким образом пользователь задает документа представляет собой оценку количества информации, свойственной терму. Если терм часто приоритеты термам в его запросе, то весовые коэф встречается в документах, находящихся в репози- фициенты термам будут присвоены в соответствии тории, то вероятность того, что он весьма общий, с их IDF.
высока, и поиск определенного ресурса при по- Определим зависящую от запроса часть функ мощи поисковой системы не даст значительных ции отношения, т.е. (,) в (1), чтобы устано результатов, поэтому ему присваивается низкое вить соответствие между и, а определением БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ соответствия, в данном случае, будет являться угол 5.3. Реалистичные модели ранжирования между векторами в L -пространстве:
Большинство поисковых систем в действитель ности используют улучшенную модель вектора (,) = cos((,) = (2) ) 2 документа. Тем не менее, существует множество противников данной модели, поскольку самый су щественный ее недостаток в том, что подход, ис Пример 1. Продемонстрируем векторную мо пользующий подсчет частоты вхождений термов, дель на практике, рассмотрев процесс поиска для может дать ошибочные результаты, т.к. количество запроса связный граф.
слов на странице подсчитывается вслепую. По В хорошо известной поисковой системе для Веба этому вносятся корректирующие коэффициенты, можно обнаружить примерно 20109 документов, основанные на таких факторах, как расположение в которых терм связный встречается в 7109 до термов относительно друг друга, статистические кументах, а терм граф в 150106 документах. Та измерения корреляции между термами и аспекта ким образом, значения IDF будут следующими:
ми форматирования страницы (такими как шрифт IDF(связный) = 0.46 и IDF(граф) = 2.1. Используя и размер шрифта, которым представлены термы).
количество слов как единицу измерения, получаем Одним из популярных методов ранжирования размер запроса, равный 2, и вектор запроса является OKAPI BM25 [2], где рейтинг документа вычисляется на основе формулы:
, Необходимо сравнить по релевантности два доку мента A и B, которые, предположим, одного разме ра. Следовательно, мы можем использовать коли где, обычно, k=1.2, b=0.75, d - длина документа чество вхождений терма в документ в качестве его (т.е. количество слов в документе) и d - сред TF-значения. В таблице 4 приведены количество няя длина всех документов. Данная функция пыта вхождений термов запроса в документы, а также ется нормализовать рейтинги документов, исходя соответствующие векторы документов.
из их длины: большой документ может содержать гораздо больше повторений отдельных термов, чем Таблица 4.
маленький, и, тем не менее, быть менее релевант Количество вхождений термов запроса ным запросу.
в документы и соответствующие векторы документов.
Следующим улучшенным вариантом является функция OKAPI BM25F, в которой ранжирующая Документ A Документ B функция разбивается на части относительно полей документа, таких как заголовки, ссылки, основной Количество вхождений 10 текст и т.д.
терма связный Однако у всех представленных методов суще Количество вхождений ствует еще одна проблема. Пользователь, совер терма граф шающий поиск, ожидает найти авторитетную ин формацию в результатах поиска раньше, чем все Вектор документа остальное. Но в большинстве случаев стандартные слова в поисковом запросе не выделены особым Оценка (по (2)) 0.96 0. образом на анализируемых при поиске страницах.
Например, не все производители автомобилей ис Простой подсчет количества вхождений термов пользуют слово машина на своих веб-сайтах!
дает преимущество документу A, однако видно, что Более того, неавторитетные или даже вредонос B фактически лучше удовлетворяет запросу. Это ные ресурсы могут легко обогнать авторитетные интуитивно доказуемо. Например, большее число по рейтингу, просто используя термы по несколь вхождений терма связный в документе A пока- ку раз на своих страницах: к примеру, при поиске зывает, что этот документ посвящен связям в не- Volvo, главная страница компании Volvo будет сколько другом контексте, чем связные графы, и находится гораздо ниже в рейтинге, чем локальные поэтому слабо удовлетворяет запросу. дистрибьюторы автомобилей, использующие сло БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ во Volvo десятки раз у себя на страницах. Это не Страница Рейтинг I(i) тот эффект, который необходим. Необходимо ре I(i) шение, которое позволило бы оценивать качество 1 {(2,1)} 1 0. страницы независимо от запроса.
2 {(1,2),(3,2)} 2 0. Эта проблема, а также проблема спама, явля 3 {(1,3),(2,3)} 2 0. ются основными причинами введения в функцию 4 {(1,4),(2,4),(3,4),(5,4)} 4 0. ранжирования (1) коэффициента q( ).
5 {(1,5)} 1 0. 6 {(4,6)} 1 0. 6. Оценка качества документа на основе цитирования: алгоритм PageRank Рассмотрим один из наиболее популярных и широко используемых методов оценки качества документов, основанный на ссылках между доку ментами, так называемый метод рейтинга цити руемости. Примерами цитат могут служить список цитированной литературы в научных работах или гиперссылки между веб-страницами. Идея рейтин га цитируемости заключается в определении каче ственной оценки документа на основании количе ства и качества ссылающихся на него документов.
Рис. 1. Индекс цитирования с подсчетом входящих связей.
Абстрагируясь от того, что цитата представля ет собой только ссылку с одной страницы на дру Определение 3. Документ i V называется гую без каких-либо специфических атрибутов (т.е.
висячим, если O(i) =.
не учитывается размещение ссылки в документе, Пример 2. Тривиальным примером для рейтин ее формат и т.д.), можно представить ссылочную га цитируемости будет служить, q(i) = const I(i) структуру в виде графа. Предположим, репозито т.е. документу i присваивается рейтинг прямо про рий состоит из n документов, имеющих уникаль порциональный числу документов, ссылающихся на ные идентификаторы DOCID, последовательно него. На рисунке 1 представлен граф, в котором про присвоенные документам и находящиеся в интер стой подсчет входящих связей для каждого узла и вале V = [1,n].
формирует представленные показатели рейтинга (по сле нормализации по общему числу связей в графе).
Определение 1. Цитатой, или же другими Данный метод ранжирования редко приме словами, ссылкой называется упорядоченная пара няется при ранжировании печатных работ или документов (i, j)V. Ссылками называются ис авторов в академической сфере. Очевидный ходящая связь документа i и входящая связь доку недостаток данного метода заключается в том, мента j.
что всем цитатам присваиваются равные весо Сформировав из всех ссылок между документами вые коэффициенты. Другими словами, цитата из V множество, становится ясно, что G = (V, E) E автора, на которого имеется много ссылок из является ориентированным графом с верши других ресурсов, приравнивается цитате автора, нами, являющимися ссылками. Назовем данный не имеющего ссылок с других ресурсов. Кроме граф графом ссылок.
того, в таких средах как Веб, данная оценка яв ляется абсолютно неадекватной, т.к. основной Определение 2. Пусть G = (V, E) где V Ч задачей данного метода является простой под E V *V конечное множество вершин графа,, счет огромного количества входящих ссылок со и i V. Тогда множество входящих связей будет страниц с низким качеством.
обозначаться как I(i), а множество исходящих Проблема поиска метода оценки качества ссы связей как O(i), т.е.
лок, который бы работал в такой разнородной среде как Веб, наиболее успешно решилась с изобретени I(i) ={e E e = ( j,i) j V},, ем алгоритма PageRank. Этот алгоритм был разра ботан двумя аспирантами Стэнфордского универ O(i) ={e E e = (i, j) j V},. ситета: Сергеем Брином и Лоренсом Пейджем, в БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ дальнейшем он послужил частью технологической 6.2. Наглядное обоснование базы поисковой системы Google (www.google.com).
Алгоритм PageRank можно рассматривать как Впервые алгоритм был описан в [3] и [4], после это модель поведения пользователя. Предполагается, го была проведена многолетняя работа в связи с что веб-серфер (пользователь, путешествующий данными публикациями.
по веб-страницам, т.е. переходящий по ссылкам с одной на другую) с заданной случайным образом 6.1. Вычисление рейтинга страницы стартовой страницы переходит по ссылкам (снова по алгоритму PageRank выбирая их случайным образом) на другие стра Можно провести аналогию между списками ницы и никогда не возвращается на предыдущую использованной литературы в академических рабо- страницу, иногда прерывая переход по ссылкам и тах и ссылками на определенные страницы в Вебе.
начиная снова с другой случайной страницы. Ве Подсчет ссылок на страницу из разных источни- роятность того, что веб-серфер посетит определен ков дает приближенное значение важности или, ную страницу, и является ее рейтингом PageRank.
другими словами, качества страницы. Алгоритм А коэффициент затухания d определяет насколько PageRank расширяет данный подход не только под скоро веб-серфер начнет процесс заново, перейдя счетом количества ссылок (принимая значимость на случайную страницу. Единственное важное раз ссылок с каждой из страниц равной), но и упоря личие в задании фактора d заключается в том, что дочивая страницы по количеству ссылок, содержа он может быть присвоен как группе страниц, так и щихся в них. Рейтинг страницы по PageRank опре отдельным страницам. Данный подход позволяет деляется следующим образом [4]:
персонализировать выборку и сводит к минимуму Предположим, что на документ A ссылаются вероятность того, что система ошибется, присваи страницы T1...Tn. А параметр d является коэффи вая странице рейтинг. Существует несколько рас циентом затухания, находящимся в интервале.
(0;
1) ширений алгоритма Page Rank, описанных в [5].
Обычно d присваивается значение равное 0.85.
Другое наглядное обоснование того, что стра Коэффициент d необходим для того, чтобы огра ница может иметь высокий рейтинг PageRank, за ничить количество переходов по ссылкам в графе до ключается в определении количества страниц, кументов. Функция C(T ) определяет количество ссылающихся на нее и имеющих также высокий исходящих со страницы T ссылок. Тогда рейтинг рейтинг PagRank. Таким образом, страницы, на страницы A по PageRank определяется как которые ссылается множество документов в вебе, являются более предпочтительными. Кроме того, страницы, имеющие хотя бы одну ссылку, напри мер, с домашней страницы Yahoo!, являются более Можно видеть, что при вычислении (рей предпочтительными. Если ссылка на страницу не тинга страницы A по PageRank) также учитывают работает, или страница низкого качества, то мало ся рейтинги страниц T1...Tn по PageRank ( ).
вероятно, что домашняя страница Yahoo! будет Таким образом, при определении рейтинга документа ссылаться на нее. PageRank анализирует подобные во внимание принимается рейтинг страниц, ссылаю ситуации, а также рекурсивные ссылки нескольких щихся на него, т.е. рейтинг документа зависит от страниц, посредством которых их владельцы пыта качества ссылающихся на него страниц ются повысить их рейтинг.
Следует отметить, что PageRank определяет распределение вероятностей для каждой страницы 6.3. Анкерный текст таким образом, что сумма рейтингов PageRank всех Рассмотрим некоторые особенности поис страниц будет равна единице.
ковой системы Google, основой которой является Рейтинг PageRank ( ) может быть вычис- алгоритм PageRank. В поисковой системе Google лен с использованием простого итеративного алго- анкерный текст обрабатывается особым образом.
ритма и будет соответствовать главному собствен- Анкером называется слово или группа слов (фраза), ному вектору нормализованной матрицы ссылок. к которым привязана гипертекстовая ссылка. Боль Следует отметить, что рейтинг PageRank для 26 шинство поисковых систем связывают текст ссыл миллионов веб-страниц может быть вычислен за ки со страницей, на которой эта ссылка находится.
несколько часов на рабочей станции средней мощ- В Google анкерный текст так же ассоциируется со ности [3]. страницей, на которую эта ссылка указывает. Дан БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
АНАЛИЗ ДАННЫХ И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ ный подход имеет несколько преимуществ в силу 7. Заключение того, что анкеры обрабатываются особым образом.
Поиск информации в гетерогенной среде, та Во-первых, анкеры содержат более точное описа кой как World Wide Web, является актуальной за ние страниц, чем сами страницы. Во-вторых, анке дачей, для которой существует множество мето ры могут описывать документы, которые не могут дов решения. При поиске данных в репозитории быть проиндексированы системой без графиче поисковой системы производится выборка про ского интерфейса, такие как изображения, прило индексированных документов и определяется их жения и базы данных. Таким образом, становится релевантность поисковому запросу, введенному возможным отбирать веб-страницы, которые фак пользователем. Если для определения множества тически не были проиндексированы.
претендентов для выборки подходит логический Следует отметить, что неиндексированные стра метод, то для определения релевантности доку ницы могут вызвать некоторые проблемы в силу ментов используются гораздо более сложные ме того, что они не проверялись на точность до пред тоды, самым эффективным из которых является ставления пользователю. В таких случаях поисковая алгоритм PageRank. Этот алгоритм основан на система никогда не сможет вернуть страницу, ко анализе как ссылок, исходящих из документа, так торой фактически не существует, однако имеются и документов, ссылающихся на него. При этом гиперссылки, указывающие на нее. Тем не менее, также производится оценка качества ссылающих сортировка результатов по-прежнему возможна, так ся документов.
как с данной проблемой сталкиваются крайне редко.
Тем не менее, перед поисковыми система Идея привязки анкерного текста к странице, на ми стоит множество проблем, таких как проблема которую он ссылается, впервые была реализована спама и ситуации, когда создатель страницы до в World Wide Web Worm [6] именно из-за того, что бавляет искусственную избыточную информацию данный подход позволяет находить информацию, с целью повысить рейтинг своей страницы. Кроме представленную не в виде текста, а также расширя того, существуют проблемы анализа документов, ет возможности стандартной поисковой системы. В не имеющих текстовой информации (таких, как Google используют анкерную привязку в основном изображения или медиа). Для их решения исполь для того, чтобы получить наиболее качественную зуются различные подходы, которые применяются выборку. Эффективное использование анкерного в крупных поисковых системах и являются коммер текста очень проблематично с технической точки зрения: необходимо обрабатывать огромное коли- ческой тайной компаний, их разрабатывающих. В чество информации. К примеру, для репозитория, настоящее время ведется активная работа над су содержащего 24 миллиона страниц, было проин- ществующими методами поиска, направленная на дексировано более 259 миллионов анкеров [3]. их оптимизацию.
Литература 1. Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27 (1948) 2. Sparck-Jones, K., Walker, S., Robertson, S.E.: A probabilistic model of information retrieval: Development and comparative experiments. Inf. Process. Manag. 36(6), 779Ц808 (2000) 3. Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. In: Proceedings of the 7th International World Wide Web Conference, 4. Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web.
Stanford Digital Libraries Working Paper, Stanford University (1998) 5. Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress. 6. Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-26-27 1994. an/mypapers/www94.ps БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.