HITS-algoritm

HITS ( Hyperlink Induced Topic Search ) -algoritmen , som föreslogs 1999 av John Kleinberg , låter dig hitta Internetsidor som matchar användarens fråga baserat på informationen i hyperlänkar [1] .

HITS-måttet används ofta för att svara på breda ämnesfrågor och hitta dokumentgemenskaper ( eng. Tightly-Knit Community ) på Internet . Idén med algoritmen är baserad på antagandet att hyperlänkar kodar ett betydande antal dolda auktoritetssidor [2] .

Ett auktoritativt dokument (auktoritativ sida, författare) är ett dokument som motsvarar användarens begäran, som har en större andel bland dokumenten för detta ämne, det vill säga ett större antal dokument hänvisar till detta dokument [1] .

Ett navdokument (hubsida, mellanhand) är ett dokument som innehåller många länkar till auktoritativa dokument.

Sidan som många andra punkter länkar till måste vara en bra "författare". I sin tur bör en sida som pekar på många andra vara en bra "mellanhand". Baserat på detta beräknar HITS-algoritmen två poäng för varje webbsida : ett auktoritetspoäng och ett mellanpoäng. Det vill säga för varje sida beräknas dess betydelse som "författare" och "förmedlare" rekursivt [3] [4] .

Algoritm

Det första steget i HITS- algoritmen är att få fram de mest relevanta sidorna i sökfrågan . Denna uppsättning kallas rotuppsättningen och kan erhållas genom att ta de mest populära n sidorna som returneras av textsökningsalgoritmen. Basuppsättningen bildas genom att rotuppsättningen ökas med alla webbsidor som är länkade till den och några av sidorna som länkar till den. Webbsidorna i basuppsättningen, och alla hyperlänkar mellan dessa sidor, bildar en klumpad undergraf. HITS-beräkningar utförs endast på denna subgraf.

Auktoritetsdokumentet och medlarpoängen definieras i termer av varandra i ömsesidig rekursion . En sidas auktoritetspoäng beräknas som summan av poängen för proxysidorna som pekar på den sidan. Återförsäljarens poängvärde beräknas som summan av poängen för de auktoritativa sidor som den pekar på.

Algoritmen utför ett antal iterationer , som var och en består av två huvudsteg:

Myndighetsuppdatering . En uppdatering av auktoritetspoängen för varje hörn i subgrafen, motsvarande summan av proxypoängen för var och en av de hörn som pekar på dem.
Hub uppdatering . Uppdatering av proxypoängen för varje hörn i subgrafen genom att summera de auktoritativa poängen för var och en av de hörn de pekar på.

Auktoritetspoängen och medlingspoängen för en vertex beräknas med hjälp av följande algoritm:

Börja med hörn vars auktoritetspoäng och proxypoäng är 1.
Utförande av myndighetsuppdateringsregeln.
Kör en navuppdateringsregel.
Normalisering av värden genom att dividera varje proxypoäng med kvadratroten av summan av kvadraterna av alla proxypoäng, och dividera varje auktoritetspoäng med kvadratroten av summan av kvadraterna av alla trovärdighetspoäng.
Upprepa från steg två efter behov.

Detaljering

För att börja rangordna, , och . Överväg två typer av uppdateringar: en myndighetsuppdateringsregel och en navuppdatering. Upprepade iterationer av auktoritetsuppdateringen och navuppdateringsreglerna tillämpas för att beräkna auktoritets-/proxypoäng . K-steget att tillämpa algoritmen innebär att den första auktoritetsuppdateringsregeln tillämpas k gånger och sedan navuppdateringsregeln. $\forall sid$ ${\mathrm {auth}}(p)=1$ ${\mathrm {hub}}(p)=1$

Authority Update Rule

$\forall sid$ , vi får = där n är det totala antalet sidor som är länkade till p och i är sidan som är länkade till p. Således beräknas en sidas auktoritetspoäng som summan av poängvärdena för de mellanliggande sidorna som pekar på den sidan. ${\mathrm {auth}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {hub}}(i)$

Hubuppdateringsregeln

$\forall sid$ , får vi = där n är det totala antalet sidor som pekas på av p och i är sidan som pekas på av p. Således beräknas en sidas proxypoäng som summan av auktoritetspoängen för sidorna den länkar till. ${\mathrm {hub}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {auth}}(i)$

Beroende på dessa värden beräknas webbsidornas betydelse för en viss begäran och visas sedan för användaren. HITS Rank-modulen beräknar rankningen för en webbsida offline efter att de har laddats ner och lagrats i en lokal databas. [5]

Normalisering

De slutliga vertexpoängen bestäms efter en oändlig upprepning av algoritmen. Direkt och konsekvent tillämpning av navuppdateringen och auktoritetsuppdateringsreglerna resulterar i divergerande värden som måste normaliseras av matrisen efter varje iteration. Således konvergerar de värden som erhålls från denna process så småningom.

HITS Algoritm och PageRank

HITS - algoritmen har flera viktiga skillnader från PageRank - algoritmen . [6]

HITS-algoritmen beräknar inte bara rangen för varje nod, utan ger också en proxypoäng.
PageRank-algoritmen innehåller en fri parameter α, som vanligtvis inte ingår i HITS-algoritmen.
Prioritet, som ett resultat av arbetet med PageRank-algoritmen, tenderar att vara äldre resurser, medan HITS-algoritmen har en mindre bias i detta avseende.
PageRank-algoritmen kan bara hitta en unik lösning.

Trots skillnaderna mellan HITS och PageRank har dessa algoritmer det gemensamt att auktoriteten (vikten) för en nod beror på vikten av andra noder, och nivån på "mellanhanden" beror på hur auktoritativa noderna som den refererar till.

Beräkningen av auktoriteten för enskilda dokument används i stor utsträckning idag i sådana applikationer som att bestämma ordningen för att skanna dokument i nätverket av IPS -roboten , rangordna sökresultat, generera tematiska recensioner etc.

För närvarande har tekniker för att på konstgjord väg öka raden av enskilda webbdokument eller deras grupper av webbplatser genom att upprätta hyperlänkar som inte är relaterade till deras innehåll blivit utbredd . Dessa tekniker, som är en opålitlig mängd olika SEO-metoder för sökmotoroptimering ( Search Engine Optimization ), kallade "black hat" SEO, är baserade på anpassning till befintliga algoritmer för att rangordna webbdokument efter de mest populära ( sökmotorer ).

I sin tur leder sådana tekniker till behovet av kontinuerlig förbättring av rankningsalgoritmer i sökmotorer, med fokus på innehållskomponenten i webbdokument när de bestämmer deras rangordning. [fyra]

Nackdelar med HITS

Mycket forskning har gjorts för att utvärdera HITS-algoritmen och det har visat sig att även om algoritmen fungerar bra för de flesta frågor, fungerar den inte för vissa andra. Det finns flera skäl [7] :

medlare och författare.

Det är olämpligt att göra en tydlig åtskillnad mellan "förmedlare" och "författare", eftersom många mellanhandssidor också är författade.

Ämnesdrift _ _ _ _

Dominerande placering av vissa tematiskt närbesläktade dokument som ett resultat av HITS-algoritmen. I vissa fall kanske dessa dokument inte är relevanta för begäran . I ett fall, när sökelementet var "Jaguar", konvergerade HITS-algoritmen till ett fotbollslag som heter Jaguars.

För att lösa detta problem föreslogs PHITS-algoritmen [4] som en förlängning av standardalgoritmen HITS. Inom ramen för denna algoritm antas det: — en uppsättning citerande dokument, — en uppsättning referenser, — en uppsättning klasser (faktorer). Det antas också att händelsen inträffar med sannolikhet . Villkorliga sannolikheter och används för att beskriva beroenden mellan närvaron av en länk , en latent faktor och ett dokument . $D$ $C$ $Z$ $d\in {D}$ $P(d)$ $P(c|z)$ $P(z|d)$ $c\in {C}$ $z\in{Z}$ $d\in {D}$

Sannolikhetsfunktionen uppskattas :

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)=\summa _{{z\in {Z}}}P(c|z)P(z|d)

Målet med PHITS - algoritmen är att passa , , maximera . $P(z)$ $P(c|z)$ $P(z|d)$ $L(C|D)$

Därefter:

P(c|z)

– raden av "författare";

P(z|d)

– raden av "mellanhänder".

För att beräkna rangen måste du ange antalet faktorer i uppsättningen , och sedan kommer det att karakterisera sidans kvalitet som en "författare" i sammanhanget av ämnet. Nackdelarna med metoden inkluderar det faktum att den iterativa processen oftast inte stannar vid det absoluta, utan vid det lokala maximum av sannolikhetsfunktionen . Men i situationer där det inte finns någon tydlig dominans av frågeämnet i uppsättningen av hittade webbsidor, överträffar PHITS HITS-algoritmen. $Z$ $P(c|z)$ $L$

Automatiskt genererade länkar.

Vissa av länkarna är datorgenererade, men HITS-algoritmen ger dem fortfarande samma värden.

irrelevanta dokument.

Vissa frågor kan returnera irrelevanta dokument till en hög plats i rankningen, vilket leder till felaktiga resultat av HITS-algoritmen.

Anteckningar

↑ 1 2 Krizhanovsky, 2008 , sid. 27.
↑ The metric of HITS, 2005 , sid. 55.
↑ Kleinberg, 1999 .
↑ 1 2 3 Algoritm HITS, 2009 .
↑ Nav och myndigheter, 2010 , sid. 5.
↑ PageRank och HITS, 2010 , sid. 257.
↑ Problem med HITS-algoritmen, 2011 , sid. 255.

Litteratur

Lande D.V., Snarsky A.A., Bezsudnov I.V. Internet. Navigera i komplexa nätverk: modeller och algoritmer . - Librokom, 2009. - 264 sid. — ISBN 978-5-397-00497-8 . (ryska)
Cronin B. Årlig översyn av informationsvetenskap och teknik . - 2004. - 674 sid. — ISBN 1573872091 .
Kleinberg J. Auktoritativa källor i en hyperlänkad miljö . — 1999.
Kleinberg J. HITS-algoritmen: auktoritativa källor i en hyperlänkmiljö / översatt av S. Neilenko. - 1999. Arkiverad 12 oktober 2013. (ryska)
Gupta GK Introduktion till datautvinning med fallstudier : 2: a upplagan . — PHI Learning Pvt. Ltd., 2011. - 491 sid. — ISBN 978-81-203-4326-9 .
Leo JG, Jonathan R.P. Diskret kalkyl. Tillämpad analys av grafer för beräkningsvetenskap . - Springer, 2010. - 366 sid. - ISBN 978-1-84996-289-6 . (inte tillgänglig länk)
Scime A. Web Mining : Tillämpningar och tekniker . - Idea Group Inc., 2005. - 433 sid. — ISBN 1591404150 .
Krizhanovsky A.A. Doktorsavhandling. Matematiska och mjukvaruverktyg för att konstruera listor med semantiskt nära ord baserade på betygsättningen av wikitexter . - St Petersburg. , 2008. - S. 27-30. — 188 sid.
Chandranna AK En onlineversion av Hyperlinked-Induced Topics Search (HITS) Algorithm . — 2010.