HITS-algoritmi

John Kleinbergin vuonna 1999 ehdottama HITS ( Hyperlink Induced Topic Search ) -algoritmi mahdollistaa käyttäjän kyselyä vastaavien Internet-sivujen löytämisen hyperlinkkien sisältämien tietojen perusteella [1] .

HITS-mittaria käytetään usein vastaamaan laajoihin aihekyselyihin ja etsimään dokumenttiyhteisöjä ( esim . Tightly-Knit Community ) Internetistä . Algoritmin idea perustuu oletukseen, että hyperlinkit koodaavat huomattavan määrän piilotettuja auktoriteettisivuja [2] .

Valtuutettu asiakirja (valtuutettu sivu, kirjoittaja) on käyttäjän pyyntöä vastaava asiakirja, jolla on suurempi osuus tämän aiheen asiakirjoista, eli suurempi määrä asiakirjoja viittaa tähän asiakirjaan [1] .

Keskusdokumentti (keskitinsivu, välittäjä) on asiakirja, joka sisältää monia linkkejä arvovaltaisiin asiakirjoihin.

Sivun, jolle monet muut kohdat linkittävät, on oltava hyvä "tekijä". Moniin muihin viittaavan sivun pitäisi puolestaan olla hyvä "välittäjä". Tämän perusteella HITS-algoritmi laskee kullekin verkkosivulle kaksi pistettä : auktoriteetin ja välipisteen. Toisin sanoen jokaiselle sivulle sen merkitys "tekijänä" ja "välittäjänä" lasketaan rekursiivisesti [3] [4] .

Algoritmi

Ensimmäinen askel HITS- algoritmissa on saada hakukyselyn osuvimmat sivut . Tätä joukkoa kutsutaan juurijoukoksi, ja se voidaan saada ottamalla tekstihakualgoritmin palauttamat suosituimmat n sivua. Perusjoukko muodostetaan lisäämällä juurijoukkoa kaikilla siihen linkitetyillä verkkosivuilla ja joillakin siihen linkitetyillä sivuilla. Perusjoukon verkkosivut ja kaikki näiden sivujen väliset hyperlinkit muodostavat tiivistetyn alikaavion. HITS-laskelmat suoritetaan vain tälle alakaaviolle.

Auktoriteettiasiakirjan ja välittäjän pisteet määritellään toistensa suhteen keskinäisessä rekursiossa . Sivun auktoriteettipisteet lasketaan kyseiselle sivulle osoittavien välityssivujen pisteiden summana. Jälleenmyyjän pistemäärä lasketaan niiden arvovaltaisten sivujen pisteiden summana, joille se osoittaa.

Algoritmi suorittaa useita iteraatioita , joista jokainen koostuu kahdesta päävaiheesta:

Viranomaisten päivitys . Päivitys aligraafin kunkin kärjen auktoriteetin arvosta, joka vastaa kunkin niihin osoittavan kärjen välityspisteiden summaa.
Hubin päivitys . Päivitetään aligraafin kunkin kärjen välityspisteet laskemalla yhteen kunkin niiden pisteen arvovaltaiset pisteet, joihin ne osoittavat.

Vertexin auktoriteettipisteet ja välityspisteet lasketaan seuraavalla algoritmilla:

Aloita pisteistä, joiden auktoriteettipisteet ja välityspisteet ovat 1.
Valtuutuksen päivityssäännön suorittaminen.
Suorita keskittimen päivityssääntö.
Arvojen normalisointi jakamalla kukin välityspalvelinpisteet kaikkien välityspalvelinpisteiden neliöiden summan neliöjuurella ja jakamalla kukin auktoriteettipisteiden kaikkien uskottavuuspisteiden neliösumman neliöjuurella.
Toista vaiheesta kaksi tarpeen mukaan.

Yksityiskohdat

Luokituksen aloittamiseksi , ja . Harkitse kahdenlaisia päivityksiä: auktoriteetin päivityssääntöä ja keskittimen päivitystä. Auktoriteettipäivityksen ja keskittimen päivityssääntöjen toistuvia iteraatioita sovelletaan valtuus-/välityspalvelinpisteiden laskemiseen . Algoritmin k-vaiheessa käytetään ensimmäistä auktoriteetin päivityssääntöä k kertaa ja sitten keskittimen päivityssääntöä. $\forall p$ ${\mathrm {auth}}(p)=1$ ${\mathrm {hub}}(p)=1$

Viranomaisten päivityssääntö

$\forall p$ , saamme = missä n on p:hen linkitettyjen sivujen kokonaismäärä ja i on p:hen linkitetty sivu. Siten sivun auktoriteettipisteet lasketaan kyseiselle sivulle osoittavien välisivujen pistearvojen summana. ${\mathrm {auth}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {hub}}(i)$

Keskittimen päivityssääntö

$\forall p$ , saamme = missä n on p:n osoittamien sivujen kokonaismäärä ja i on sivu, johon p osoittaa. Siten sivun välityspisteet lasketaan niiden sivujen auktoriteettipisteiden summana, joihin se linkittää. ${\mathrm {hub}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {auth}}(i)$

Näistä arvoista riippuen verkkosivujen merkitys tietylle pyynnölle lasketaan ja näytetään sitten käyttäjälle. HITS Rank -moduuli laskee verkkosivun sijoituksen offline-tilassa sen jälkeen, kun ne on ladattu ja tallennettu paikalliseen tietokantaan. [5]

Normalisointi

Lopulliset kärkipisteet määritetään algoritmin loputtoman toiston jälkeen. Keskittimen päivityksen ja auktoriteetin päivityssääntöjen suora ja johdonmukainen soveltaminen johtaa poikkeaviin arvoihin, jotka matriisin on normalisoitava jokaisen iteraation jälkeen. Siten tästä prosessista saadut arvot lopulta lähentyvät.

HITS-algoritmi ja PageRank

HITS- algoritmilla on useita tärkeitä eroja PageRank-algoritmiin verrattuna . [6]

HITS-algoritmi ei vain laske kunkin solmun sijoitusta, vaan tarjoaa myös välityspalvelimen pistemäärän.
PageRank-algoritmi sisältää ilmaisen parametrin α, joka ei yleensä sisälly HITS-algoritmiin.
PageRank-algoritmin työn seurauksena prioriteetti on yleensä vanhemmat resurssit, kun taas HITS-algoritmilla on pienempi harha tässä suhteessa.
PageRank-algoritmi voi löytää vain ainutlaatuisen ratkaisun.

Huolimatta eroista HITS:n ja PageRankin välillä, näille algoritmeille on yhteistä, että solmun auktoriteetti (paino) riippuu muiden solmujen painosta ja "välittäjän" taso riippuu siitä, kuinka arvovaltaisia solmut, joihin se viittaa.

Yksittäisten asiakirjojen auktoriteetin laskentaa käytetään nykyään laajalti sellaisissa sovelluksissa kuin IPS -robotin suorittaman asiakirjojen skannausjärjestyksen määrittäminen verkossa , hakutulosten luokittelu, temaattisten arvostelujen luominen jne.

Tällä hetkellä tekniikat, joilla keinotekoisesti nostetaan yksittäisten verkkodokumenttien tai niiden Web-sivustoryhmien rivejä luomalla hyperlinkkejä, jotka eivät liity niiden sisältöön, ovat yleistyneet . Nämä tekniikat, jotka ovat epäluotettava valikoima SEO-menetelmiä hakukoneoptimoinnissa ( Search Engine Optimization ), joita kutsutaan "mustahattu" SEO:ksi, perustuvat mukautumiseen olemassa oleviin algoritmeihin, joilla suosituimmat ( hakukoneet ) luokitellaan verkkoasiakirjoja.

Tällaiset tekniikat puolestaan johtavat tarpeeseen jatkuvasti parantaa hakukoneiden sijoitusalgoritmeja, keskittyen verkkodokumenttien sisältökomponenttiin niiden sijoituksia määritettäessä. [neljä]

HITSin haitat

HITS-algoritmin arvioinnissa on tehty paljon tutkimusta ja on osoitettu, että vaikka algoritmi toimii hyvin useimmissa kyselyissä, se ei toimi joillekin muille. Syitä on useita [7] :

välittäjiä ja kirjoittajia.

Ei ole tarkoituksenmukaista tehdä selkeää eroa "välittäjien" ja "tekijöiden" välillä, koska monet välittäjäsivut ovat myös tekijöitä.

Aiheen ajautuminen . _ _

Joidenkin temaattisesti läheisesti liittyvien asiakirjojen hallitseva sijainti HITS-algoritmin seurauksena. Joissakin tapauksissa nämä asiakirjat eivät välttämättä liity pyyntöön . Eräässä tapauksessa, kun hakuelementti oli "Jaguar", HITS-algoritmi konvergoi jalkapallojoukkueeseen nimeltä Jaguars.

Tämän ongelman ratkaisemiseksi ehdotettiin PHITS-algoritmia [4] vakio-HITS-algoritmin jatkeeksi. Tämän algoritmin puitteissa oletetaan: — joukko viittausasiakirjoja, — joukko viittauksia, — joukko luokkia (tekijöitä). Oletetaan myös, että tapahtuma tapahtuu todennäköisyydellä . Ehdolliset todennäköisyydet ja niitä käytetään kuvaamaan linkin , piilevän tekijän ja asiakirjan välisiä riippuvuuksia . $D$ $C$ $Z$ $d\in {D}$ $P(d)$ $P(c|z)$ $P(z|d)$ $c\in {C}$ $z\in{Z}$ $d\in {D}$

Todennäköisyysfunktio on arvioitu :

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

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

PHITS-algoritmin tavoitteena on sovittaa , , maksimoida . $P(z)$ $P(c|z)$ $P(z|d)$ $L(C|D)$

Sen jälkeen:

P(c|z)

– "tekijät";

P(z|d)

– "välittäjien" arvot.

Ristojen laskemiseksi sinun on määritettävä joukon tekijöiden lukumäärä , ja sitten se luonnehtii sivun laatua "tekijänä" aiheen yhteydessä. Menetelmän haittoja ovat se, että iteratiivinen prosessi ei useimmiten pysähdy absoluuttiseen, vaan todennäköisyysfunktion paikalliseen maksimiin . Kuitenkin tilanteissa, joissa kyselyn aiheella ei ole selvää määräävää asemaa löydettyjen verkkosivujen joukossa, PHITS toimii paremmin kuin HITS-algoritmi. $Z$ $P(c|z)$ $L$

Automaattisesti luodut linkit.

Osa linkeistä on tietokoneella luotuja, mutta HITS-algoritmi antaa niille silti samat arvot.

merkityksettömiä asiakirjoja.

Jotkut kyselyt voivat palauttaa merkityksettömiä asiakirjoja korkealle sijoitukselle, mikä johtaa HITS-algoritmin virheellisiin tuloksiin.

Muistiinpanot

↑ 1 2 Krizhanovsky, 2008 , s. 27.
↑ HITSin metriikka, 2005 , s. 55.
↑ Kleinberg, 1999 .
↑ 1 2 3 Algorithm HITS, 2009 .
↑ Keskittimet ja viranomaiset, 2010 , s. 5.
↑ PageRank ja HITS, 2010 , s. 257.
↑ Ongelmia HITS-algoritmin kanssa, 2011 , s. 255.

Kirjallisuus

Lande D.V., Snarsky A.A., Bezsudnov I.V. Internet. Navigointi monimutkaisissa verkoissa: mallit ja algoritmit . - Librokom, 2009. - 264 s. — ISBN 978-5-397-00497-8 . (Venäjän kieli)
Cronin B. Annual Review of Information Science and Technology . - 2004. - 674 s. — ISBN 1573872091 .
Kleinberg J. Arvovaltaiset lähteet hyperlinkkiympäristössä . – 1999.
Kleinberg J. HITS-algoritmi: arvovaltaiset lähteet hyperlinkkiympäristössä / kääntänyt S. Neilenko. - 1999. Arkistoitu 12. lokakuuta 2013. (Venäjän kieli)
Gupta GK Johdatus tiedon louhintaan tapaustutkimuksilla : 2. painos . — PHI Learning Pvt. Ltd., 2011. - 491 s. — ISBN 978-81-203-4326-9 .
Leo JG, Jonathan R.P. Discrete Calculus. Laskennallisen tieteen graafien soveltava analyysi . - Springer, 2010. - 366 s. - ISBN 978-1-84996-289-6 . (linkki ei saatavilla)
Scime A. Web Mining : Sovellukset ja tekniikat . - Idea Group Inc., 2005. - 433 s. — ISBN 1591404150 .
Krizhanovsky A.A. Tohtorin väitöskirja. Matemaattiset ja ohjelmistotyökalut semanttisesti läheisten sanojen luetteloiden muodostamiseen wikitekstien luokituksen perusteella . - Pietari. , 2008. - S. 27-30. — 188 s.
Chandranna AK Hyperlinkitettyjen aiheiden hakualgoritmin (HITS) online - versiot . – 2010.