Algoritmul HITS

Algoritmul HITS ( Hyperlink Induced Topic Search ), propus în 1999 de John Kleinberg , vă permite să găsiți pagini de Internet care se potrivesc cu interogarea utilizatorului pe baza informațiilor conținute în hyperlink-uri [1] .

Valoarea HITS este adesea folosită pentru a răspunde la interogări de subiecte ample și pentru a găsi comunități de documente ( de exemplu, Tightly -Knit Community ), pe Internet . Ideea algoritmului se bazează pe presupunerea că hyperlinkurile codifică un număr semnificativ de pagini de autoritate ascunse [2] .

Un document autorizat (pagină cu autoritate, autor) este un document corespunzător solicitării utilizatorului, având o pondere mai mare între documentele acestui subiect, adică un număr mai mare de documente se referă la acest document [1] .

Un document hub (pagină hub, intermediar) este un document care conține multe link-uri către documente autorizate.

Pagina către care se leagă multe alte puncte trebuie să fie un „autor” bun. La rândul său, o pagină care indică multe altele ar trebui să fie un bun „intermediar”. Pe baza acestui lucru, algoritmul HITS calculează două scoruri pentru fiecare pagină web : un scor de autoritate și un scor intermediar. Adică, pentru fiecare pagină, semnificația ei ca „autor” și „intermediar” este calculată recursiv [3] [4] .

Algoritm

Primul pas în algoritmul HITS este obținerea celor mai relevante pagini în interogarea de căutare . Acest set se numește setul rădăcină și poate fi obținut luând cele mai populare n pagini returnate de algoritmul de căutare text. Setul de bază este format prin incrementarea setului rădăcină cu toate paginile web care sunt legate la acesta și unele dintre paginile care leagă la acesta. Paginile web din setul de bază și toate hyperlinkurile dintre acele pagini formează un subgraf grupat. Calculele HITS sunt efectuate numai pe acest subgraf.

Documentul de autoritate și scorurile mediatorului sunt definite unul în termenii celuilalt în recursivitate reciprocă . Scorul de autoritate al unei pagini este calculat ca suma scorurilor paginilor proxy care indică acea pagină. Valoarea scorului de reseller este calculată ca suma scorurilor paginilor autorizate către care indică.

Algoritmul efectuează un număr de iterații , fiecare dintre ele constând din doi pași principali:

Actualizare de autoritate . O actualizare a scorului de autoritate al fiecărui vârf din subgraf, echivalent cu suma scorurilor proxy ale fiecărui vârf care indică spre ele.
Actualizare hub . Actualizarea scorului proxy al fiecărui vârf din subgraf prin însumarea scorurilor autorizate ale fiecărui vârf către care indică.

Scorul de autoritate și scorul de mediere pentru un vârf sunt calculate folosind următorul algoritm:

Începeți cu nodurile al căror scor de autoritate și scor proxy este 1.
Executarea regulii de actualizare a autoritatii.
Executați o regulă de actualizare a hub-ului.
Normalizarea valorilor prin împărțirea fiecărui scor proxy la rădăcina pătrată a sumei pătratelor tuturor scorurilor proxy și împărțirea fiecărui scor de autoritate la rădăcina pătrată a sumei pătratelor tuturor scorurilor de credibilitate.
Repetați de la pasul doi după cum este necesar.

Detaliere

Pentru a începe clasarea, , și . Luați în considerare două tipuri de actualizări: o regulă de actualizare de autoritate și o actualizare de hub. Iterațiile repetate ale regulilor de actualizare a autorizării și de actualizare hub sunt aplicate pentru a calcula scorurile de autoritate/proxy . Pasul k de aplicare a algoritmului implică aplicarea primei reguli de actualizare a autorității de k ori și apoi a regulii de actualizare a hub-ului. $\forall p$ ${\mathrm {auth}}(p)=1$ ${\mathrm {hub}}(p)=1$

Regula de actualizare a autorității

$\forall p$ , obținem = unde n este numărul total de pagini legate de p și i este pagina legată de p. Astfel, scorul de autoritate al unei pagini este calculat ca suma valorilor scorului paginilor intermediare care indică acea pagină. ${\mathrm {auth}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {hub}}(i)$

Regula de actualizare a hub-ului

$\forall p$ , obținem = unde n este numărul total de pagini indicate de p și i este pagina indicată de p. Astfel, scorul proxy al unei pagini este calculat ca suma scorurilor de autoritate ale paginilor la care se leagă. ${\mathrm {hub}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {auth}}(i)$

În funcție de aceste valori, importanța paginilor web pentru o anumită solicitare este calculată și apoi afișată utilizatorului. Modulul HITS Rank calculează rangul unei pagini web offline după ce acestea au fost descărcate și stocate într-o bază de date locală. [5]

Normalizare

Scorurile finale la vârf sunt determinate după o repetare infinită a algoritmului. Aplicarea directă și consecventă a regulilor de actualizare a centrului și de actualizare a autorității are ca rezultat valori divergente care trebuie normalizate de matrice după fiecare iterație. Astfel, valorile obținute în urma acestui proces converg în cele din urmă.

Algoritmul HITS și PageRank

Algoritmul HITS are câteva diferențe importante față de algoritmul PageRank . [6]

Algoritmul HITS nu numai că calculează rangul fiecărui nod, dar oferă și un scor proxy.
Algoritmul PageRank conține un parametru liber α, care de obicei nu este inclus în algoritmul HITS.
Prioritatea, ca urmare a muncii algoritmului PageRank, tinde să fie resursele mai vechi, în timp ce algoritmul HITS are o părtinire mai mică în acest sens.
Algoritmul PageRank poate găsi doar o soluție unică.

În ciuda diferențelor dintre HITS și PageRank, acești algoritmi au în comun faptul că autoritatea (greutatea) unui nod depinde de ponderea altor noduri, iar nivelul „intermediarului” depinde de cât de autoritar sunt nodurile la care se referă.

Calculul autorității documentelor individuale este utilizat pe scară largă astăzi în aplicații precum determinarea ordinii de scanare a documentelor în rețea de către robotul IPS , clasarea rezultatelor căutării, generarea de recenzii tematice etc.

În prezent, s- au răspândit tehnologiile de creștere artificială a rangului documentelor web individuale sau a grupurilor lor de site-uri web prin stabilirea de hyperlinkuri care nu au legătură cu conținutul lor . Aceste tehnologii, care reprezintă o varietate nesigură de metode SEO de optimizare a motoarelor de căutare ( Search Engine Optimization ), numite „black hat” SEO, se bazează pe adaptarea la algoritmii existenți pentru clasarea documentelor web de către cele mai populare ( motoarele de căutare ).

La rândul lor, astfel de tehnologii duc la necesitatea îmbunătățirii continue a algoritmilor de clasare în motoarele de căutare, concentrându-se pe componenta de conținut a documentelor web atunci când se stabilesc pozițiile acestora. [patru]

Dezavantajele HITS

S-au făcut multe cercetări în evaluarea algoritmului HITS și s-a demonstrat că, deși algoritmul funcționează bine pentru majoritatea interogărilor, nu funcționează pentru altele. Există mai multe motive [7] :

mediatori și autori.

Este inadecvat să se facă o distincție clară între „intermediari” și „autori”, deoarece multe pagini intermediare sunt, de asemenea, scrise.

Derivarea subiectului . _ _

Locația dominantă a unor documente strâns legate tematic ca urmare a algoritmului HITS. În unele cazuri, aceste documente pot să nu fie relevante pentru cerere . Într-un caz, când elementul de căutare a fost „Jaguar”, algoritmul HITS a convergit către o echipă de fotbal numită Jaguars.

Pentru a rezolva această problemă, algoritmul PHITS [4] a fost propus ca o extensie a algoritmului standard HITS. În cadrul acestui algoritm, se presupune: — un set de documente citate, — un set de referințe, — un set de clase (factori). De asemenea, se presupune că evenimentul are loc cu probabilitate . Probabilitățile condiționale și sunt folosite pentru a descrie dependențele dintre prezența unei legături , a unui factor latent și a unui document . $D$ $C$ $Z$ $d\în {D}$ $P(d)$ $P(c|z)$ $P(z|d)$ $c\în {C}$ $z\in{Z}$ $d\în {D}$

Funcția de probabilitate este estimată :

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

P(c|d)=\sum _{{z\in {Z}}}P(c|z)P(z|d)

Scopul algoritmului PHITS este de a se potrivi , de a maximiza . $P(z)$ $P(c|z)$ $P(z|d)$ $L(C|D)$

După aceea:

P(c|z)

– rangurile „autorilor”;

P(z|d)

– rânduri de „intermediari”.

Pentru a calcula rangurile, trebuie să specificați numărul de factori din set , iar apoi va caracteriza calitatea paginii ca „autor” în contextul subiectului. Dezavantajele metodei includ faptul că procesul iterativ se oprește cel mai adesea nu la absolut, ci la maximul local al funcției de probabilitate . Cu toate acestea, în situațiile în care nu există o dominație clară a subiectului interogării în setul de pagini web găsite, PHITS depășește algoritmul HITS. $Z$ $P(c|z)$ $L$

Link-uri generate automat.

Unele dintre link-uri sunt generate de computer, dar algoritmul HITS le oferă în continuare valori egale.

documente irelevante.

Unele interogări pot returna documente irelevante la un loc înalt în clasament, ceea ce duce la rezultate eronate ale algoritmului HITS.

Note

↑ 1 2 Krizhanovsky, 2008 , p. 27.
↑ Metrica HITS, 2005 , p. 55.
↑ Kleinberg, 1999 .
↑ 1 2 3 Algoritmul HITS, 2009 .
↑ Huburi și autorități, 2010 , p. 5.
↑ PageRank și HITS, 2010 , p. 257.
↑ Probleme cu algoritmul HITS, 2011 , p. 255.

Literatură

Lande D.V., Snarsky A.A., Bezsudnov I.V. Internet. Navigarea în rețele complexe: modele și algoritmi . - Librokom, 2009. - 264 p. — ISBN 978-5-397-00497-8 . (Rusă)
Cronin B. Revizuirea anuală a științei și tehnologiei informației . - 2004. - 674 p. — ISBN 1573872091 .
Kleinberg J. Surse autorizate într- un mediu hyperlinked . — 1999.
Kleinberg J. Algoritmul HITS: surse autorizate într-un mediu de hyperlink / tradus de S. Neilenko. - 1999. Arhivat la 12 octombrie 2013. (Rusă)
Gupta GK Introducere în data mining cu studii de caz : Ediția a 2-a . - PHI Learning Pvt. Ltd., 2011. - 491 p. — ISBN 978-81-203-4326-9 .
Leo JG, Jonathan R.P. Calcul discret. Analiza aplicată a graficelor pentru știința computațională . - Springer, 2010. - 366 p. - ISBN 978-1-84996-289-6 . (link indisponibil)
Scime A. Web Mining : Aplicaţii şi tehnici . - Idea Group Inc., 2005. - 433 p. — ISBN 1591404150 .
Krizhanovsky A.A. Teză de doctorat. Instrumente matematice și software pentru construirea de liste de cuvinte apropiate semantic pe baza evaluării textelor wiki . - Sankt Petersburg. , 2008. - S. 27-30. — 188 p.
Chandranna AK O versiuni online ale algoritmului de căutare a subiectelor induse de hiperlegături (HITS) . — 2010.