Algoritmus HITS

Algoritmus HITS ( Hyperlink Induced Topic Search ), navržený v roce 1999 Johnem Kleinbergem , umožňuje najít internetové stránky, které odpovídají dotazu uživatele na základě informací obsažených v hypertextových odkazech [1] .

Metrika HITS se často používá k zodpovězení širokých témat a hledání komunit dokumentů ( angl. Tightly-Knit Community ) na internetu . Myšlenka algoritmu je založena na předpokladu, že hypertextové odkazy kódují značné množství skrytých autoritních stránek [2] .

Směrodatný dokument (směrodatná stránka, autor) je dokument odpovídající požadavku uživatele, který má větší podíl mezi dokumenty tohoto subjektu, tj. na tento dokument odkazuje větší počet dokumentů [1] .

Hub dokument (hubová stránka, zprostředkovatel) je dokument obsahující mnoho odkazů na autoritativní dokumenty.

Stránka, na kterou odkazuje mnoho dalších bodů, musí být dobrým „autorem“. Stránka, která odkazuje na mnoho dalších, by zase měla být dobrým „prostředníkem“. Na základě toho algoritmus HITS vypočítá dvě skóre pro každou webovou stránku : skóre autority a skóre prostředníka. To znamená, že pro každou stránku se rekurzivně vypočítá její význam jako „autora“ a „prostředníka“ [3] [4] .

Algoritmus

Prvním krokem v algoritmu HITS je získání nejrelevantnějších stránek ve vyhledávacím dotazu . Tato sada se nazývá kořenová sada a lze ji získat převzetím nejoblíbenějších n stránek vrácených algoritmem textového vyhledávání. Základní sada je tvořena inkrementací kořenové sady se všemi webovými stránkami , které jsou na ni propojeny, a některými stránkami, které na ni odkazují. Webové stránky v základní sadě a všechny hypertextové odkazy mezi těmito stránkami tvoří soustředěný podgraf. Výpočty HITS se provádějí pouze na tomto podgrafu.

Skóre autoritního dokumentu a zprostředkovatele jsou vzájemně definovány ve vzájemné rekurzi . Skóre autority stránky se vypočítá jako součet skóre proxy stránek, které na danou stránku odkazují. Hodnota skóre prodejce se vypočítá jako součet skóre autoritativních stránek, na které odkazuje.

Algoritmus provádí řadu iterací , z nichž každá se skládá ze dvou hlavních kroků:

Aktualizace autority . Aktualizace skóre autority každého vrcholu v podgrafu, ekvivalentní součtu proxy skóre každého z vrcholů, které na ně ukazují.
Aktualizace hubu . Aktualizace proxy skóre každého vrcholu v podgrafu sečtením směrodatných skóre každého z vrcholů, na které ukazují.

Skóre autority a skóre zprostředkování pro vrchol se vypočítá pomocí následujícího algoritmu:

Začněte s vrcholy, jejichž autoritní skóre a proxy skóre je 1.
Provedení pravidla aktualizace oprávnění.
Proveďte pravidlo aktualizace centra.
Normalizace hodnot dělením každého proxy skóre druhou odmocninou součtu čtverců všech proxy skóre a dělením každého skóre autority druhou odmocninou součtu čtverců všech skóre důvěryhodnosti.
Podle potřeby opakujte od druhého kroku.

Detailing

Chcete-li zahájit hodnocení, , a . Zvažte dva typy aktualizací: pravidlo aktualizace autority a aktualizaci centra. K výpočtu skóre autority/proxy se použijí opakované iterace pravidel aktualizace autority a aktualizace centra . K-krok aplikace algoritmu znamená použití prvního pravidla aktualizace autority kkrát a poté pravidla aktualizace centra. $\forall p$ ${\mathrm {auth}} (p)=1$ ${\mathrm {hub}} (p)=1$

Pravidlo aktualizace oprávnění

$\forall p$ , dostaneme = kde n je celkový počet stránek propojených s p a i je stránka propojená s p. Skóre autority stránky se tedy vypočítá jako součet hodnot skóre zprostředkujících stránek, které na tuto stránku ukazují. ${\mathrm {auth}} (p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {hub}}(i)$

Pravidlo aktualizace hubu

$\forall p$ , dostaneme = kde n je celkový počet stránek, na které ukazuje p a i je stránka, na kterou ukazuje p. Skóre proxy stránky se tedy vypočítá jako součet skóre autority stránek, na které odkazuje. ${\mathrm {hub}} (p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {auth}}(i)$

V závislosti na těchto hodnotách je vypočítána důležitost webových stránek pro konkrétní požadavek a následně zobrazena uživateli. Modul HITS Rank vypočítá hodnocení webové stránky offline poté, co byly staženy a uloženy do lokální databáze. [5]

Normalizace

Konečné skóre vrcholů se určí po nekonečném opakování algoritmu. Přímá a konzistentní aplikace pravidel aktualizace centra a aktualizace autority vede k odlišným hodnotám, které je třeba po každé iteraci normalizovat pomocí matice. Hodnoty získané tímto procesem tedy nakonec konvergují.

Algoritmus HITS a PageRank

Algoritmus HITS má několik důležitých rozdílů od algoritmu PageRank . [6]

Algoritmus HITS nejen vypočítá hodnocení každého uzlu, ale také poskytuje proxy skóre.
Algoritmus PageRank obsahuje volný parametr α, který obvykle není zahrnut v algoritmu HITS.
Prioritou, jako výsledek práce algoritmu PageRank, bývají starší zdroje, zatímco algoritmus HITS má v tomto ohledu menší zaujatost.
Algoritmus PageRank může najít pouze jedinečné řešení.

Navzdory rozdílům mezi HITS a PageRank mají tyto algoritmy společné to, že autorita (váha) uzlu závisí na váze ostatních uzlů a úroveň „prostředníka“ závisí na tom, jak autoritativní jsou uzly, na které odkazuje.

Výpočet autority jednotlivých dokumentů je dnes široce používán v aplikacích, jako je určování pořadí skenování dokumentů v síti robotem IPS , řazení výsledků vyhledávání, generování tematických recenzí atd.

V současné době se rozšířily technologie pro umělé zvyšování hodnocení jednotlivých webových dokumentů nebo jejich skupin webových stránek zřizováním hypertextových odkazů, které nesouvisejí s jejich obsahem . Tyto technologie, které jsou nespolehlivou řadou SEO metod optimalizace pro vyhledávače ( Search Engine Optimization ), nazývané „black hat“ SEO, jsou založeny na přizpůsobení se stávajícím algoritmům pro hodnocení webových dokumentů podle nejpopulárnějších ( vyhledávačů ).

Tyto technologie zase vedou k potřebě neustálého zlepšování hodnotících algoritmů ve vyhledávačích se zaměřením na obsahovou složku webových dokumentů při určování jejich hodnocení. [čtyři]

Nevýhody HITS

Při vyhodnocování algoritmu HITS bylo provedeno mnoho výzkumů a ukázalo se, že zatímco algoritmus funguje dobře pro většinu dotazů, pro některé jiné nefunguje. Důvodů je několik [7] :

zprostředkovatelé a autoři.

Není vhodné jasně rozlišovat mezi „zprostředkovateli“ a „autory“, protože mnoho zprostředkovatelských stránek je také autory.

Posun tématu . _ _

Dominantní umístění některých tematicky úzce souvisejících dokumentů v důsledku algoritmu HITS. V některých případech nemusí být tyto dokumenty pro žádost relevantní . V jednom případě, kdy byl vyhledávacím prvkem „Jaguar“, algoritmus HITS konvergoval k fotbalovému týmu zvanému Jaguáři.

K vyřešení tohoto problému byl navržen algoritmus PHITS [4] jako rozšíření standardního algoritmu HITS. V rámci tohoto algoritmu se předpokládá: — soubor citujících dokumentů, — soubor odkazů, — soubor tříd (faktorů). Rovněž se předpokládá, že událost nastane s pravděpodobností . Podmíněné pravděpodobnosti a se používají k popisu závislostí mezi přítomností odkazu , latentním faktorem a dokumentem . $D$ $C$ $Z$ $d\in {D}$ $P(d)$ $P(c|z)$ $P(z|d)$ $c\in {C}$ $z\in{Z}$ $d\in {D}$

Funkce pravděpodobnosti se odhaduje :

L(C|D)=\prod _{{c\in {C},d\in {D))}^{\ }P(d,c)=\prod _{{c\in {C}, d\in {D}}}^{\ }P(d)P(c|d)

P(c|d)=\součet _{{z\in {Z}}}P(c|z)P(z|d)

Cílem algoritmu PHITS je přizpůsobit , , maximalizovat . $P(z)$ $P(c|z)$ $P(z|d)$ $L(C|D)$

Poté:

P(c|z)

– řady „autorů“;

P(z|d)

– řady „zprostředkovatelů“.

Chcete-li vypočítat hodnocení, musíte zadat počet faktorů v sadě a pak bude charakterizovat kvalitu stránky jako "autor" v kontextu tématu. Mezi nevýhody metody patří skutečnost, že iterační proces se nejčastěji nezastaví na absolutním, ale na lokálním maximu věrohodnostní funkce . V situacích, kdy v množině nalezených webových stránek není jasná dominance předmětu dotazu, však PHITS překonává algoritmus HITS. $Z$ $P(c|z)$ $L$

Automaticky generované odkazy.

Některé z odkazů jsou generované počítačem, ale algoritmus HITS jim stále dává stejné hodnoty.

irelevantní dokumenty.

Některé dotazy mohou vrátit irelevantní dokumenty na vysoké místo v žebříčku, což vede k chybným výsledkům algoritmu HITS.

Poznámky

↑ 1 2 Krizhanovsky, 2008 , s. 27.
↑ Metrika HITS, 2005 , str. 55.
↑ Kleinberg, 1999 .
↑ 1 2 3 Algorithm HITS, 2009 .
↑ Centrály a úřady, 2010 , s. 5.
↑ PageRank and HITS, 2010 , str. 257.
↑ Problémy s algoritmem HITS, 2011 , str. 255.

Literatura

Lande D.V., Snarsky A.A., Bezsudnov I.V. Internet. Navigace ve složitých sítích: Modely a algoritmy . - Librokom, 2009. - 264 s. — ISBN 978-5-397-00497-8 . (Ruština)
Cronin B. Annual Review of Information Science and Technology . - 2004. - 674 s. — ISBN 1573872091 .
Kleinberg J. Autoritativní zdroje v prostředí s hypertextovými odkazy . — 1999.
Kleinberg J. Algoritmus HITS: autoritativní zdroje v prostředí hypertextových odkazů / přeložil S. Neilenko. - 1999. Archivováno 12. října 2013. (Ruština)
Gupta GK Úvod do dolování dat s případovými studiemi : 2. vydání . — PHI Learning Pvt. Ltd., 2011. - 491 s. — ISBN 978-81-203-4326-9 .
Leo JG, Jonathan R. P. Diskrétní počet. Aplikovaná analýza grafů pro výpočetní vědu . - Springer, 2010. - 366 s. - ISBN 978-1-84996-289-6 . (nedostupný odkaz)
Scime A. Web Mining : Aplikace a techniky . - Idea Group Inc., 2005. - 433 s. — ISBN 1591404150 .
Križanovský A.A. PhD práce. Matematické a softwarové nástroje pro vytváření seznamů sémanticky blízkých slov na základě hodnocení wiki textů . - Petrohrad. , 2008. - S. 27-30. — 188 str.
Chandranna AK An online verze algoritmu vyhledávání témat vyvolaných hypertextovými odkazy (HITS) . — 2010.