ХИТ-алгоритм

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

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

История

В журналах

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

В Интернете

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

Алгоритм

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

Шаги

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

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

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

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

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

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

Сравнение с PageRank

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

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

Подробно

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

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

Для каждого $p$ , мы обновляем $\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 := set of pages
for each page p in G do
    p.auth = 1 // p.auth is the authority score of the page p
    p.hub = 1 // p.hub is the hub score of the page p
for step from 1 to k do // run the algorithm for k steps
    norm = 0
    for each page p in G do  // update all authority values first
        p.auth = 0
        for each page q in p.incomingNeighbors do // p.incomingNeighbors is the set of pages that link to p
            p.auth += q.hub
        norm += square(p.auth) // calculate the sum of the squared auth values to normalise
    norm = sqrt(norm)
    for each page p in G do  // update the auth scores 
        p.auth = p.auth / norm  // normalise the auth values
    norm = 0
    for each page p in G do  // then update all hub values
        p.hub = 0
        for each page r in p.outgoingNeighbors do // p.outgoingNeighbors is the set of pages that p links to
            p.hub += r.auth
        norm += square(p.hub) // calculate the sum of the squared hub values to normalise
    norm = sqrt(norm)
    for each page p in G do  // then update all hub values
        p.hub = p.hub / norm   // normalise the hub values

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

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

Несходящийся псевдокод

G := set of pages
for each page p in G do
    p.auth = 1 // p.auth is the authority score of the page p
    p.hub = 1 // p.hub is the hub score of the page p

function HubsAndAuthorities(G)
    for step from 1 to k do // run the algorithm for k steps
        for each page p in G do  // update all authority values first
            p.auth = 0
            for each page q in p.incomingNeighbors do // p.incomingNeighbors is the set of pages that link to p
                p.auth += q.hub
        for each page p in G do  // then update all hub values
            p.hub = 0
            for each page r in p.outgoingNeighbors do // p.outgoingNeighbors is the set of pages that p links to
                p.hub += r.auth

См. также

Рейтинг страницы

Ссылки

^ Кристофер Д. Мэннинг; Прабхакар Рагхаван; Хинрих Шютце (2008). «Введение в поиск информации» . Издательство Кембриджского университета . Проверено 9 ноября 2008 г.
^ Кляйнберг, Джон (декабрь 1999 г.). «Хабы, органы власти и сообщества» . Корнеллский университет . Проверено 9 ноября 2008 г.

Кляйнберг, Джон (1999). «Авторитетные источники в среде с гиперссылками» (PDF) . Журнал АКМ . 46 (5): 604–632. CiteSeerX 10.1.1.54.8485 . дои : 10.1145/324133.324140 . S2CID 221584113 .
Ли, Л.; Шан, Ю.; Чжан, В. (2002). «Улучшение алгоритмов обработки веб-документов на основе HITS» . Материалы 11-й Международной конференции по всемирной паутине (WWW, 2002) . Гонолулу, Гавайи. ISBN 978-1-880672-20-4 . Архивировано из оригинала 3 апреля 2005 г. Проверено 3 июня 2005 г. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

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

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

[1] Кристофер Д. Мэннинг; Прабхакар Рагхаван; Хинрих Шютце (2008). «Введение в поиск информации» . Издательство Кембриджского университета . Проверено 9 ноября 2008 г.

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

[1]

[2]