HITS algoritmus

A HITS ( Hyperlink Induced Topic Search ) algoritmus, amelyet 1999-ben John Kleinberg javasolt , lehetővé teszi a felhasználó lekérdezésének megfelelő internetes oldalak megtalálását a hiperhivatkozásokban található információk alapján [1] .

A HITS mérőszámot gyakran használják széles témával kapcsolatos kérdések megválaszolására és dokumentumközösségek (pl . Tightly-Knit Community ) megtalálására az interneten . Az algoritmus ötlete azon a feltételezésen alapul, hogy a hiperhivatkozások jelentős számú rejtett jogosultsági oldalt kódolnak [2] .

Mérvadó dokumentum (hiteles oldal, szerző) a felhasználó kérésének megfelelő, e tárgykör dokumentumai között nagyobb arányú dokumentum, vagyis nagyobb számú dokumentum hivatkozik erre a dokumentumra [1] .

A hub dokumentum (központi oldal, közvetítő) olyan dokumentum, amely számos hivatkozást tartalmaz hiteles dokumentumokra.

Az oldal, amelyre sok más pont hivatkozik, jó "szerzőnek" kell lennie. A sok másra mutató oldalnak viszont jó „közvetítőnek” kell lennie. Ennek alapján a HITS algoritmus minden weboldalra két pontszámot számít ki : egy jogosultsági pontszámot és egy közvetítő pontszámot. Vagyis minden oldal esetében rekurzív módon számítják ki annak „szerzői” és „közvetítői” jelentőségét [3] [4] .

Algoritmus

A HITS algoritmus első lépése a legrelevánsabb oldalak lekérése a keresési lekérdezésben . Ezt a halmazt gyökérhalmaznak nevezzük, és a szövegkereső algoritmus által visszaadott legnépszerűbb n oldal figyelembevételével érhető el. Az alapkészlet úgy jön létre, hogy a gyökérkészletet megnöveli a hozzá hivatkozott összes weblappal , és néhány olyan oldallal, amelyek hivatkoznak rá. Az alapkészletben lévő weboldalak és az oldalak közötti hiperhivatkozások egy összevont részgráfot alkotnak. A HITS számításokat csak ezen az algrafikonon hajtják végre.

A hatósági dokumentum és a közvetítő pontszáma egymásra vonatkoztatva, kölcsönös rekurzióban kerül meghatározásra . Az oldal jogosultsági pontszáma az adott oldalra mutató proxyoldalak pontszámainak összegeként kerül kiszámításra. A viszonteladói pontszám értéke azon mérvadó oldalak pontszámainak összegeként kerül kiszámításra, amelyekre mutat.

Az algoritmus számos iterációt hajt végre , amelyek mindegyike két fő lépésből áll:

Hatóság frissítése . Az algráf minden csúcsának tekintélypontszámának frissítése, amely megegyezik a rájuk mutató egyes csúcsok proxypontszámainak összegével.
Hub frissítés . Az algráf minden csúcsának proxypontszámának frissítése az egyes csúcsok mérvadó pontszámainak összegzésével, amelyekre mutatnak.

Egy csúcs tekintélypontszámát és közvetítési pontszámát a következő algoritmussal számítjuk ki:

Kezdje azokkal a csúcsokkal, amelyeknek a tekintélypontszáma és a proxy pontszáma 1.
A jogosultság frissítési szabály végrehajtása.
Hub frissítési szabály végrehajtása.
Az értékek normalizálása úgy, hogy minden proxy pontszámot elosztunk az összes proxy pontszám négyzetgyökével, és elosztjuk az egyes jogosultsági pontszámokat az összes hitelességi pontszám négyzetgyökével.
Ismételje meg a második lépéstől szükség szerint.

Részletezés

A rangsorolás megkezdéséhez , és . Tekintsen kétféle frissítést: egy jogosultsági frissítési szabályt és egy hub-frissítést. A jogosultság-frissítés és a hub-frissítési szabályok ismételt iterációi kerülnek alkalmazásra a jogosultsági/proxy-pontszámok kiszámításához . Az algoritmus alkalmazásának k-lépése magában foglalja az első jogosultságfrissítési szabály k alkalommal történő alkalmazását, majd a hub frissítési szabályt. $\forall p$ ${\mathrm {auth}}(p)=1$ ${\mathrm {hub}}(p)=1$

Hatóság frissítési szabály

$\forall p$ , azt kapjuk, hogy = ahol n a p-re hivatkozott oldalak száma, i pedig a p-re hivatkozott oldal. Így egy oldal tekintélypontszáma az adott oldalra mutató közvetítő oldalak pontszámainak összegeként kerül kiszámításra. ${\mathrm {auth}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {hub}}(i)$

A hub frissítési szabály

$\forall p$ , azt kapjuk, hogy = ahol n a p-vel mutatott oldalak száma, i pedig a p-vel mutatott oldalak száma. Így egy oldal proxypontszáma a hivatkozott oldalak jogosultsági pontszámainak összegeként kerül kiszámításra. ${\mathrm {hub}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {auth}}(i)$

Ezektől az értékektől függően a rendszer kiszámítja a weboldalak fontosságát egy adott kérés szempontjából, majd megjeleníti a felhasználó számára. A HITS Rank modul a letöltés és a helyi adatbázisban való tárolás után offline módban kiszámítja a weboldal rangját. [5]

Normalizálás

A végső csúcspontszámokat az algoritmus végtelen ismétlése után határozzuk meg. A hub-frissítési és jogosultsági frissítési szabályok közvetlen és következetes alkalmazása eltérő értékeket eredményez, amelyeket a mátrixnak minden iteráció után normalizálnia kell. Így az ebből a folyamatból nyert értékek végül konvergálnak.

HITS algoritmus és PageRank

A HITS algoritmusnak számos fontos különbsége van a PageRank algoritmushoz képest . [6]

A HITS algoritmus nemcsak az egyes csomópontok rangját számítja ki, hanem egy proxy pontszámot is biztosít.
A PageRank algoritmus egy szabad α paramétert tartalmaz, amely általában nem szerepel a HITS algoritmusban.
A PageRank algoritmus munkájának eredményeként a prioritás általában a régebbi erőforrások, míg a HITS algoritmus e tekintetben kisebb torzítással rendelkezik.
A PageRank algoritmus csak egyedi megoldást tud találni.

A HITS és a PageRank közötti különbségek ellenére ezekben az algoritmusokban az a közös, hogy egy csomópont jogosultsága (súlya) a többi csomópont súlyától függ, a "közvetítő" szintje pedig attól függ, hogy mennyire hitelesek azok a csomópontok, amelyekre hivatkozik.

Az egyes dokumentumok jogosultságának számítását manapság széles körben használják olyan alkalmazásokban, mint a dokumentumok IPS robot általi szkennelésének sorrendjének meghatározása a hálózatban, a keresési eredmények rangsorolása, tematikus áttekintések generálása stb.

Jelenleg széles körben elterjedtek azok a technológiák, amelyek mesterségesen növelik az egyes webdokumentumok vagy webhelycsoportjaik rangját olyan hiperhivatkozások létrehozásával, amelyek nem kapcsolódnak a tartalomhoz . Ezek a technológiák, amelyek a keresőoptimalizálás ( Search Engine Optimization ) keresőoptimalizálási módszereinek megbízhatatlan változata , úgynevezett "fekete kalap" SEO, a webes dokumentumok legnépszerűbb ( keresőmotorok ) általi rangsorolására szolgáló meglévő algoritmusokhoz való alkalmazkodáson alapulnak.

Az ilyen technológiák viszont a keresőmotorokban a rangsorolási algoritmusok folyamatos fejlesztésének szükségességét jelentik , a webes dokumentumok tartalmi összetevőire összpontosítva a rangsoruk meghatározásakor. [négy]

A HITS hátrányai

Sok kutatást végeztek a HITS algoritmus kiértékelésével kapcsolatban, és bebizonyosodott, hogy míg az algoritmus a legtöbb lekérdezésnél jól működik, más lekérdezéseknél nem. Ennek több oka is van [7] :

közvetítők és szerzők.

Nem helyénvaló egyértelmű különbséget tenni a „közvetítők” és a „szerzők” között, mivel sok közvetítő oldal is szerződik.

Téma eltolódása _ _ _

Néhány tematikusan szorosan összefüggő dokumentum domináns helye a HITS algoritmus eredményeként. Egyes esetekben ezek a dokumentumok nem relevánsak a kérelem szempontjából . Egy esetben, amikor a keresési elem "Jaguar" volt, a HITS algoritmus a Jaguars nevű futballcsapathoz konvergált.

A probléma megoldására a PHITS algoritmust [4] javasolták a szabványos HITS algoritmus kiterjesztéseként. Ennek az algoritmusnak a keretein belül feltételezzük: — idéző dokumentumok halmazát, — hivatkozások halmazát, — osztályok (tényezők) halmazát. Azt is feltételezzük, hogy az esemény valószínűséggel következik be . Feltételes valószínűségek és a hivatkozások jelenléte , egy látens tényező és egy dokumentum közötti függőségek leírására szolgálnak . $D$ $C$ $Z$ $d\in {D}$ $P(d)$ $P(c|z)$ $P(z|d)$ $c\in {C}$ $z\in{Z}$ $d\in {D}$

A valószínűségi függvény becslése :

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

A PHITS algoritmus célja , , maximalizálása . $P(z)$ $P(c|z)$ $P(z|d)$ $L(C|D)$

Ezután:

P(c|z)

– a „szerzők” rangja;

P(z|d)

– a „közvetítők” sorai.

A rangsorok kiszámításához meg kell adni a faktorok számát a halmazban , majd a témakörben "szerzőként" fogja jellemezni az oldal minőségét. A módszer hátrányai közé tartozik, hogy az iteratív folyamat leggyakrabban nem az abszolút, hanem a likelihood függvény lokális maximumánál áll meg . Azonban azokban a helyzetekben, amikor a lekérdezés tárgyának nincs egyértelmű dominanciája a talált weboldalak halmazában, a PHITS jobban teljesít, mint a HITS algoritmus. $Z$ $P(c|z)$ $L$

Automatikusan generált linkek.

A hivatkozások egy részét számítógéppel generálják, de a HITS algoritmus továbbra is egyenlő értékeket ad nekik.

irreleváns dokumentumok.

Egyes lekérdezések az irreleváns dokumentumokat a rangsorban előkelő helyre juttathatják vissza, ami a HITS-algoritmus hibás eredményeihez vezet.

Jegyzetek

↑ 1 2 Krizhanovsky, 2008 , p. 27.
↑ A HITS metrikája, 2005 , p. 55.
↑ Kleinberg, 1999 .
↑ 1 2 3 Algoritmus HITS, 2009 .
↑ Központok és hatóságok, 2010 , p. 5.
↑ PageRank és HITS, 2010 , p. 257.
↑ Problémák a HITS algoritmussal, 2011 , p. 255.

Irodalom

Lande D.V., Snarsky A.A., Bezsudnov I.V. Internet. Navigálás összetett hálózatokban: modellek és algoritmusok . - Librokom, 2009. - 264 p. — ISBN 978-5-397-00497-8 . (Orosz)
Cronin B. Annual Review of Information Science and Technology . - 2004. - 674 p. — ISBN 1573872091 .
Kleinberg J. Hiteles források hiperhivatkozásos környezetben . – 1999.
Kleinberg J. A HITS algoritmus: hiteles források hiperhivatkozási környezetben / S. Neilenko fordítása. - 1999. Archiválva : 2013. október 12. (Orosz)
Gupta GK Bevezetés az adatbányászatba esettanulmányokkal : 2. kiadás . – PHI Learning Pvt. Kft., 2011. - 491 p. — ISBN 978-81-203-4326-9 .
Leo JG, Jonathan R.P. Diszkrét kalkulus. Alkalmazott elemzés a számítástechnikai grafikonokról . - Springer, 2010. - 366 p. - ISBN 978-1-84996-289-6 . (nem elérhető link)
Scime A. Webbányászat : Alkalmazások és technikák . - Idea Group Inc., 2005. - 433 p. — ISBN 1591404150 .
Krizhanovsky A.A. PhD értekezés. Matematikai és szoftveres eszközök szemantikailag közel álló szavak listáinak összeállításához a wiki szövegek értékelése alapján . - Szentpétervár. , 2008. - S. 27-30. — 188 p.
Chandranna AK A hiperhivatkozások által kiváltott témakereső (HITS) algoritmus online változatai . – 2010.