Алгоритм HITS

Поиск тем, вызванный гиперссылками ( HITS ; также известный как концентраторы и авторитетные источники ) - это алгоритм анализа ссылок , который оценивает веб-страницы, разработанный Джоном Кляйнбергом . Идея, лежащая в основе концентраторов и органов власти, возникла из особого понимания создания веб-страниц при первоначальном формировании Интернета; то есть определенные веб-страницы, известные как хабы, служили большими каталогами, которые на самом деле не были авторитетными в информации, которую они держали, но использовались как компиляции широкого каталога информации, который приводил пользователей прямо на другие авторитетные страницы. Другими словами, хороший хаб представляет собой страницу, которая указывает на множество других страниц, а хороший авторитетный центр представляет страницу, на которую ссылается множество различных хабов.^[1]

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

История [ править ]

В журналах [ править ]

Для оценки важности научных журналов использовались многие методы. Одним из таких методов является импакт-фактор Гарфилда . Такие журналы, как Science и Nature , наполнены многочисленными цитатами, поэтому у этих журналов очень высокие импакт-факторы. Таким образом, при сравнении еще двух малоизвестных журналов, которые получили примерно такое же количество цитирований, но один из этих журналов получил много цитирований от Science и Nature , этот журнал должен быть поставлен выше. Другими словами, лучше получать цитаты из важного журнала, чем из неважного. ^[2]

В Интернете [ править ]

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

Алгоритм [ править ]

Расширение корневого набора в базовый набор

В алгоритме HITS первым шагом является получение страниц, наиболее релевантных поисковому запросу. Этот набор называется корневым набором и может быть получен путем взятия верхних страниц, возвращаемых алгоритмом поиска на основе текста. Базовый набор генерируется путем увеличения корневой набор всех веб - страниц, которые связаны с ним и некоторые страницы , которые ссылаются на него. Веб-страницы в базовом наборе и все гиперссылки между этими страницами образуют сфокусированный подграф. Вычисление HITS выполняется только для этого сфокусированного подграфа . По словам Клейнберга, цель построения базового набора состоит в том, чтобы обеспечить включение большинства (или многих) самых сильных авторитетов.

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

Алгоритм выполняет серию итераций, каждая из которых состоит из двух основных шагов:

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

Оценка концентратора и оценка авторитета узла рассчитываются по следующему алгоритму:

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

HITS, как страница и Брина «s PageRank , является итерационным алгоритмом на основе связывания документов в Интернете . Однако у него есть несколько существенных отличий:

Это зависит от запроса, т. Е. Оценки (Центры и авторитет), полученные в результате анализа ссылок, зависят от условий поиска;
Как следствие, он выполняется во время запроса, а не во время индексации, с соответствующим снижением производительности, которое сопровождает обработку во время запроса.
Поисковые системы не используют его. (Хотя аналогичный алгоритм использовался компанией Teoma , которую приобрела компания Ask Jeeves / Ask.com .)
Он вычисляет две оценки для каждого документа, хаб и авторитет, в отличие от одной оценки;
Он обрабатывается на небольшом подмножестве «релевантных» документов («сфокусированный подграф» или базовый набор), а не на всех документах, как в случае с PageRank.

Подробно [ править ]

Для начала ранжирования допустим и для каждой страницы . Мы рассматриваем два типа обновлений: Правило обновления полномочий и Правило обновления концентратора. Чтобы вычислить оценки концентратора / авторитета каждого узла, применяются повторяющиеся итерации правила обновления полномочий и правила обновления концентратора. K-шаговое применение алгоритма Hub-Authority влечет за собой применение k раз сначала правила обновления полномочий, а затем правила обновления концентратора. ${\ Displaystyle \ mathrm {auth} (p) = 1}$ ${\ displaystyle \ mathrm {hub} (p) = 1}$ ${\ displaystyle p}$

Правило обновления полномочий [ править ]

Для каждого мы обновляем информацию о том, где находятся все страницы, которые ссылаются на страницу . То есть оценка авторитета страницы - это сумма всех хаб-оценок страниц, которые на нее указывают. ${\ displaystyle p}$ ${\ displaystyle \ mathrm {auth} (p)}$ $\mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)$ $P_{\mathrm {to} }$ $p$

Правило обновления хаба [ править ]

Для каждого мы обновляем информацию о том, где находятся все страницы, на которые ссылаются страницы . То есть рейтинг страницы - это сумма всех оценок авторитета страниц, на которые она указывает. $p$ $\mathrm {hub} (p)$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ $P_{\mathrm {from} }$ $p$

Нормализация [ править ]

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

Псевдокод [ править ]

G  : = набор страниц для каждой страницы p в G  do  p .auth = 1 // p .auth - оценка авторитета страницы p  p .hub = 1 // p .hub - оценка хаба страницы p для step from 1 to k do // запустить алгоритм на k шагов норма = 0 для каждой страницы p в G  do // обновить все значения полномочий сначала p .auth = 0 для каждой страницы q в p.incomingNeighbors  do // p.incomingNeighbors - это набор страниц, которые ссылаются на p  p .auth + = q .hub norm + = square ( p .auth) // вычислить сумму квадратов значений auth для нормализации norm = sqrt (норма) для каждой страницы p в G  do // обновить оценки аутентификации p .auth = p .auth / norm // нормализовать значения аутентификации норма = 0 для каждой страницы p в G  сделать // затем обновить все значения концентратора p .hub = 0 для каждой страницы r в p.outgoingNeighbors  do // p.outgoingNeighbors - это набор страниц, на которые p ссылается p .hub + = r .auth norm + = square ( p .hub) // вычислить сумму квадратов значений ступицы для нормализации norm = sqrt (норма) для каждой страницы p в G  делаем // затем обновляем все значения хаба p .hub = p .hub / norm // нормализуем значения хаба

Значения концентратора и авторитета сходятся в псевдокоде выше.

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

Несходящийся псевдокод [ править ]

G  : = набор страниц для каждой страницы p в G  do  p .auth = 1 // p .auth - оценка авторитета страницы p.  P .hub = 1 // p .hub - оценка центра страницы pfunction HubsAndAuthorities ( G ) для шагов с 1 по k do // запускаем алгоритм для k шагов для каждой страницы p в G  do // сначала обновляем все значения полномочий p .auth = 0 для каждой страницы q в p.incomingNeighbors  do // p.incomingNeighbors - это набор страниц, которые ссылаются на p  p .auth + = q .hub для каждой страницы p в G do // затем обновляем все значения концентратора p .hub = 0 для каждой страницы r в p.outgoingNeighbors  do // p.outgoingNeighbors - это набор страниц, которые p ссылаются на p .hub + = r .auth

См. Также [ править ]

PageRank

Ссылки [ править ]

^ Кристофер Д. Маннинг, Prabhakar Raghavan & Hinrich Schütze (2008). «Введение в поиск информации» . Издательство Кембриджского университета . Проверено 9 ноября 2008 .CS1 maint: uses authors parameter (link)
^ Клейнберг, Джон (декабрь 1999). «Центры, органы власти и сообщества» . Корнельский университет . Проверено 9 ноября 2008 .

Клейнберг, Джон (1999). «Авторитетные источники в среде с гиперссылками» (PDF) . Журнал ACM . 46 (5): 604–632. CiteSeerX 10.1.1.54.8485 . DOI : 10.1145 / 324133.324140 .
Li, L .; Shang, Y .; Чжан, В. (2002). «Улучшение алгоритмов на основе HITS для веб-документов» . Материалы 11-й Международной конференции в Интернете (WWW 2002) . Гонолулу, штат Гавайи. ISBN 978-1-880672-20-4.

Внешние ссылки [ править ]

Патент США 6,112,202
Создание системы поиска данных из реляционной базы данных. Поисковая машина на C # на основе HITS.

[1] Кристофер Д. Маннинг, Prabhakar Raghavan & Hinrich Schütze (2008). «Введение в поиск информации» . Издательство Кембриджского университета . Проверено 9 ноября 2008 .CS1 maint: uses authors parameter (link)

[2] Клейнберг, Джон (декабрь 1999). «Центры, органы власти и сообщества» . Корнельский университет . Проверено 9 ноября 2008 .

[1]