Hlavní navigace

Bloková analýza vylepšuje PageRank

14. 9. 2004
Doba čtení: 5 minut

Sdílet

Většina vyhledávačů používá pro hodnocení relevance stránek analýzu odkazů. Zářným příkladem jsou dva nejznámější algoritmy - PageRank a HITS. Ačkoliv dostáváme uspokojivé výsledky, mohou být ještě vylepšeny, například o hodnocení odkazů na stránce podle jejich sémantiky. To je také úkol blokové analýzy odkazů.

Většina algoritmů se chová ke každé webové stránce jako k uzlu grafu. Odkazy umístěné na stránce jsou orientované hrany, spojující jednotlivé uzly. Odkazy v různých částech stránky mají rozdílnou sémantiku a měly by mít také rozdílně započítánu váhu.

PageRank simuluje nahodilé prohlížení stránek na webu, každé stránce jsou přiřazeny body důležitosti. Algoritmus HITS přiřadí každé stránce dokonce dvě bodové hodnoty – jednak podle toho, nakolik je stránka autoritativní (authority score), a jednak podle toho, jak moc je egocentrická (hub score). Tyto dvě hodnoty jsou vzájemně posilovány.

Oba algoritmy vychází ze dvou předpokladů:

  • Odkazy vyjadřují lidskou podporu – pokud existuje odkaz ze stránky A na stránku B dvou různých autorů, tak tvůrce stránky A považuje stránku B za hodnotnou. Důležitost může být propagována z A na B.
  • Stránky, na které je odkazováno z A, budou pravděpodobně souviset s tématem na stránce A probíraným.

Bohužel ve většině případů tyto předpoklady nebývají splněny. Typický příklad je stránka http://news.y­ahoo.com/, která obsahuje několik sémanticky odlišných částí. Jednotlivé oblasti věnované tématickým zprávám (z domova, ze světa, sport, …) a také levý sloupec obsahující navigaci a reklamu. V tomto případě může dojít k chybnému vypočtení PageRanku a nebo k odchylce při použití algoritmu HITS.

Tento problém je zapříčiněn tím, že jedna stránka často obsahuje několik sémanticky odlišných částí s různou důležitostí. Z pohledu sémantiky by neměla být nejmenší jednotkou stránka. Odkazy obsažené v rozdílných sémantických blocích obvykle odkazují na rozdílná témata. Rozdělením stránky do bloků a získáním vztahů mezi blokem a stránkou dostaneme sémantiku stránek. Pokud vezmeme bloky jako uzly, každý z nich již reprezentuje jeden sémantický význam. Na základě těchto postupů můžeme upravit PageRank i algoritmus HITS tak, aby používaly blokovou analýzu.

Rozčlenění stránky na základě vzhledu

Vision-based Page Segmentation (VIPS) algoritmus se snaží získat sémantickou strukturu stránky podle toho, jak stránka vypadá. VIPS plně využívá celého rozvržení stránky. Nejdřív z DOM (Document Object Model) modelu získá všechny vhodné bloky. Následně najde hranice těchto bloků. Hranicí je zde myšlená svislá nebo vodorovná přímka, která neprotíná žádný z bloků a na základě těchto přímek je vybudován sémantický strom. Listy stromu reprezentují jednotlivé bloky stránky. Navigace a reklamy mohou být jednoduše odstraněny, protože se vyskytují většinou na pevných pozicích. Různá témata budou rozlišena v oddělených blocích.

Vytvoření grafu závislostí jednotlivých bloků

Pro další použití zatím získaných informací je třeba vytvořit graf závislostí jednotlivých bloků a stránek. Budeme sledovat dva typy vztahů: blok-stránka a naopak stránka-blok.

Analýza bloků

Vytvoříme si matici Z vztahů blok-stránka. Jedním rozměrem bude počet bloků – n a druhým rozměrem bude počet stránek – k. Pokud bude některý z bloků (s indexem i) odkazovat na stránku (s indexem j), tak se na dané souřadnice vloží hodnota 1/(počet stránek, které jsou blokem i odkazovány). V opačném případě zde bude 0. Můžeme se na vkládanou hodnotu dívat také jako na pravděpodobnost, že se uživatel z daného bloku i dostaneme právě na stránku j.

Analýza rozvržení stránky

Podobně vytvoříme také matici X vztahů stránka-blok. Ta bude rozměrově opačně než předchozí. Prvním rozměrem počet stránek – k a druhým počet bloků – n. Obdobně definujeme hodnotu na souřadnicích i,j. Když je blok j na stránce i, tak je vložena hodnota 1/(počet bloků na stránce i) a v opačném případě 0.

Tuto definici lze modifikovat a místo „pravděpodobnosti“ lze vkládat hodnotu nějaké funkce f, která bude pro každou stránku určovat důležitost daného bloku. Například může být brána v úvahu velikost bloku a jeho vzdálenost od středu stránky ( f(j) = B * (velikost j) / (vzdálenost j od středu i)). B je normalizační faktor, který zapříčiní, že součet f() aplikovaných na všechny bloky bude roven 1. Můžeme na ni nahlížet také jako na pravděpodobnost, že se uživatel zaměří právě na blok j při prohlížení stránky i. Podobně lze vytvořit další hodnotící funkce, které budou brát v úvahu použitou barvu pozadí, font a podobně.

Konstrukce grafů

Na základě vytvořených matic ještě vytvoříme dva ohodnocené grafy.

Graf stránek – stránky se stanou uzly, jejich vzájemné odkazy nám vytvoří v grafu hrany. Hrany spojující stránky A a B budou ohodnoceny pravděpodobností, s jakou uživatel ze stránky A vybere blok obsahující stránku B a klikne na něj.

1337

Graf stránek

Graf bloků – analogicky bude tvořen bloky jako uzly. Dva bloky O a P budou spojeny hranou, pokud v bloku O existuje odkaz na stránku obsahující blok P. Hrana bude ohodnocena pravděpodobností, s jakou uživatel prohlížející si blok O vybere odkaz stránky obsahující blok P a klikne na něj. Ohodnocení je ještě modifikováno, aby počítalo i s přechodem mezi bloky na jedné stránce.

1336

Graf bloků

Úprava algoritmů na zpracování bloků

Blokový PageRank

Algoritmus jako takový je úplně stejný. Klíčovou změnou jsou data, na kterých je prováděn. Místo grafu na úrovni stránek totiž počítá s grafem na úrovni bloků (popsaným výše). Jediná úprava, potřebná před použitím algoritmu, byla řádková normalizace (součet hodnot v řádcích matice roven 1). Takto vypočítaný PageRank již bere v úvahu zmiňovanou sémantickou strukturu stránek. Ignoruje také bloky s reklamou, neboť se jedná o nedůležité části stánky.

Blokový HITS

Taktéž blokový HITS vychází ze stejné myšlenky jako původní HITS. Hlavním rozdílem je pouze fakt, že body za autoritu získávají pouze stránky a body za egocentrismus pouze bloky. Jinak algoritmus pracuje identicky jako původní HITS.

BRAND24

Experimentální ověření algoritmů

Ověření výše zmíněných algoritmů bylo prováděno na datech z domény .gov získaných v roce 2002. Bylo v nich obsaženo 1 053 372 textových dokumentů. Ukázalo se, že algoritmy upravené na základě blokové analýzy odkazů překonaly původní PageRank a HITS.

Před nasazením na některý z internetových vyhledávačů bude muset být zodpovězeno ještě mnoho souvisejících otázek. Ale jako uživatelé se již můžeme těšit na změny, které jsou připravovány a pomalu se před námi začínají rýsovat.

Bude bloková analýza to pravé vylepšení vyhledávačů?

Byl pro vás článek přínosný?

Autor článku

Autor studuje na Matematicko-fyzikální fakultě Univerzity Karlovy a pracuje jako programátor.
Upozorníme vás na články, které by vám neměly uniknout (maximálně 2x týdně).