Алгоритм HITS

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

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

История

В журналах

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

В Интернете

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

Алгоритм

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

Шаги

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

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

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

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

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

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

Сравнение с PageRank

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

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

Подробно

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

Правило обновления полномочий

Для каждого мы обновляем до where is all pages that link to page . То есть, рейтинг авторитетности страницы представляет собой сумму всех рейтингов хабов страниц, которые ссылаются на нее. ${\displaystyle p}$ ${\displaystyle \mathrm {auth} (p)}$ ${\displaystyle \mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)}$ ${\displaystyle P_{\mathrm {to} }}$ ${\displaystyle p}$

Правило обновления концентратора

Для каждого мы обновляем до where is all pages which page links to. То есть, оценка хаба страницы — это сумма всех оценок авторитетности страниц, на которые она ссылается. ${\displaystyle p}$ ${\displaystyle \mathrm {hub} (p)}$ ${\displaystyle \mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)}$ ${\displaystyle P_{\mathrm {from} }}$ ${\displaystyle p}$

Нормализация

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

Псевдокод

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

Ссылки

1. Кристофер Д. Мэннинг; Прабхакар Рагхаван; Хинрих Шютце (2008). «Введение в информационный поиск». Cambridge University Press . Получено 2008-11-09 .
2. Клейнберг, Джон (декабрь 1999 г.). «Хабы, власти и сообщества». Корнелльский университет . Получено 09.11.2008 .

• Клейнберг, Джон (1999). «Авторитетные источники в гиперссылочной среде» (PDF) . Журнал ACM . 46 (5): 604–632. CiteSeerX  10.1.1.54.8485 . doi :10.1145/324133.324140. S2CID  221584113.
• Li, L.; Shang, Y.; Zhang, W. (2002). "Улучшение алгоритмов на основе HITS в веб-документах". Труды 11-й Международной конференции World Wide Web (WWW 2002) . Гонолулу, Гавайи. ISBN 978-1-880672-20-4. Архивировано из оригинала 2005-04-03 . Получено 2005-06-03 .{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

Внешние ссылки

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