HITS

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

HITS (z ang. Hypertext Induced Topic Selection lub Hyperlink Induced Topic Search) – algorytm opracowany przez Jona Kleinberga w 1998 z myślą o silniku przeszukującym pod nazwą CLEVER, wykorzystywany do oceny relatywności tekstu względem termu.

Algorytm HITS zakłada, że dokumenty w zbiorze są ze sobą nawzajem połączone, tworząc pewnego rodzaju graf skierowany. W grafie tym węzłami są dokumenty, a krawędziami odnośniki. Krawędzie są skierowane w taki sposób, aby wskazywały na element cytowany, a wychodziły z elementu cytującego. Same założenia modelu wskazują na naturalne wykorzystanie go odnośnie dokumentów hipertekstowych jako zawierających odnośniki (w tym także dokumentów w sieci WWW).

Algorytm HITS opiera się na dwóch ideach: autorytetu (ang. authority) i koncentratora (ang. hub). Dokumentem autorytatywnym (autorytetem) jest dokument cytowany wskazywany, taki, na który wskazuje wiele dokumentów (wiele dokumentów cytuje ten dokument). Koncentratorem jest dokument cytujący, który wskazuje na dokumenty autorytarne (dokument cytuje wiele ważnych dokumentów).

Kleinberg opracował oparty na odnośnikach model nadawania autorytetu i pokazał jak prowadzi to do metody, która konsekwentnie identyfikuje zarazem relewantne i autorytatywne strony dla zapytania o szerokiej tematyce. Model bazuje na związku, który istnieje pomiędzy autorytetem w danym temacie a tymi stronami, które odsyłają do wielu powiązanych tematycznie autorytetów. Ten drugi typ stron został nazwany koncentratorami. Zaobserwowano, że pomiędzy autorytetami i koncentratorami istnieje pewna naturalna równowaga w grafie zdefiniowanym przez strukturę odnośników. Wykorzystano to do rozwinięcia algorytmu, który identyfikuje jednocześnie oba typy stron. Algorytm operuje na skupionym podgrafie, który został skonstruowany z listy wyników wyszukiwania tekstowej wyszukiwarki. Technika konstruowania podgrafu jest zaprojektowana do uzyskania małego zbioru stron, który najprawdopodobniej zawiera najbardziej autorytatywne strony dla danego tematu.

W trakcie obserwacji zauważono, że autorytatywne strony relewantne do początkowego zapytania powinny mieć nie tylko dużą liczbę odnośników, ale będąc autorytetami we wspólnym temacie, powinno istnieć znaczne pokrycie w zbiorze stron, które do nich odsyłają. Dlatego oprócz wyszukania wysoce autorytatywnych stron, spodziewano się znaleźć koncentratory, czyli strony, które mają odnośniki do wielu autorytatywnych stron. To właśnie koncentratory trzymają razem autorytety we wspólnym temacie i pozwalają pozbyć się niepowiązanych stron z dużą liczbą odnośników.

Koncentratory i autorytety wykazują wzajemny, obopólnie wzmacniający związek (ang. mutually reinforcing relationship). Dobry koncentrator to strona, która wskazuje do wielu dobrych autorytetów. Dobry autorytet to strona, która jest wskazywana przez wiele dobrych koncentratorów. Autor zauważył, że rezultaty uzyskane poprzez czystą analizę struktury odsyłaczy dają o wiele lepsze rezultaty, niż wyszukiwarki oparte na przeszukiwaniu tekstu. W tym przypadku zastąpiono globalną analizę całej struktury odsyłaczy w WWW bardziej lokalną metodą analizy małego skupionego podgrafu.

Algorytm skutecznie sprawdza się w szerokim zakresie tematów, gdzie najsilniejsze autorytety świadomie nie zawierają do siebie wzajemnych odnośników. Mogą one być połączone pośrednio przez warstwę relatywnie anonimowych koncentratorów, które są skorelowane i odsyłają do tematycznie powiązanych grup autorytetów. Ten dwupoziomowy wzór powiązań odsłania strukturę pośród obu zbiorów, koncentratorów, które mogą wzajemnie o sobie nie wiedzieć i autorytetów, które mogą nie chcieć pogodzić się z istnieniem innych autorytetów.

Ostatecznym wynikiem działania algorytmu jest lista węzłów i autorytetów z największymi współczynnikami poprawności.

Zobacz też[edytuj | edytuj kod]

Literatura[edytuj | edytuj kod]

  • J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, pages 668-677, ACM Press, New York, 1998. [1](PDF)
  • J. M. Kleinberg. Authoritative sources in a hyperlinked environment. In Journal of the ACM, 46(5), pages 604-632, 1999
  • A. Strzelecki. Autorytatywne i eksperckie strony źródłem rzetelnych wyników w wyszukiwarkach internetowych, [w:] Informatyka dla przyszłości, pod red. J. Kisielnicki, Wydawnictwo Naukowe Wydziału Zarządzania Uniwersytetu Warszawskiego, Warszawa 2008, s. 193-201 ISBN 978-83-61276-13-5 [2](PDF)