Vyhledávání 2

34. hodina MVOP WBF

Matěj Cajthaml — SSPŠ

©

Co je to Booleanový model?

Co je to Rozšířený booleanový model?

Co je to invertovaný seznam?

Vektorový model

Vektorový model

  • navazuje na rozšířený Booleanový model
  • dotaz je vektor slov, které se hledají
  • každá stránka je uložena jako vektor slov, které obsahuje
  • slova jsou hodnocena, např. vážena dle frekvence výskytu

Ukázka vektoru dotazu a stránek

kocka zirafa pes
DOTAZ 0.1 0.1 0.5
Stránka 1 0.5 0.2 0.0
Stránka 2 0.0 0.9 0.4

Kolik prvků má daný vektor pro dotaz / stránku?

Čím je tentokrát tvořen požadavek?

Hodnocení slov na stránce

  • automaticky
  • přednost mají důležitá slova
  • znovu předzpracování
  • možnosti:
    • hodnocení dle frekvence slov na stránce
    • hodnocení dle frekvence slov na všech stránkách
  • normalizace

Dotazování

  • obyčejná vzdálenost (Euklidova) není dostatečná
  • používáme vzdálenost dle kosinu
  • určujeme treshold pro výsledky (o kolik se mohou lišit)

Optimalizace

  • znovu používáme invertovaný seznam
  • každé slovo má svůj seznam seřazený dle stránky a jeho ohodnocení

Výhody

  • výsledky jsou řazeny podle podobnosti
  • výsledky jsou relevantní
  • není potřeba přesné zadávání
  • možnost říct jakou stránku chcete vyhledat dle podobnosti

Nevýhody

  • chybí přesnost zápisu (neobsahuje x, ...)
  • geometrizace způsobuje ztrátu informací

Jaké obecné nevýhody vidíte ještě v Booleanovém a Vektorovém modelu?

Latentní sémantické indexování

  • = LSI
  • slova nejsou oddělená — jsou důležité výrazy a slovní spojení
  • mývalí mainská kočka nejsou tři slova, ale jeden typ kočky

Hodnocení pozic

Hodnocení pozic

  • = pagerank
  • způsob jak zhodnotit, jak je stránka populární

Mapa stránek

  • orientovaný graf
  • node = stránky
  • edge = propojení se šipkou

  • odchozí odkaz
  • příchozí odkaz

Co se získává jednodušeji? Seznam příchozích či odchozích odkazů?

Hodnocení

Nechť identifikátor stránky je Pi, její hodnocení Rk(P), číslo iterace k.

  1. všechny stránky ohodnotíme 1/n
  2. provedeme několik iterací, pro každou stránku:
    • za každou stránku Pj, která směruje do přičteme:
    • hodnocení z minulé iterace / počtem odchozích odkazů
  3. seřadíme sestupně

Ukázka hodnocení

pagerank
Iterace 1 Iterace 2 Iterace 3 Hodnocení
R1(P1) = 1/3 R2(P1) = 1/6 R3(P1) = 1/12 1
R1(P2) = 1/3 R2(P2) = 1/6 R3(P2) = 1/12 1
R1(P3) = 1/3 R2(P3) = 1/3 R3(P3) = 1/6 2

Kolikrát musíme iteraci provést?

Co když v grafu bude cyklus?

Vyhledávání

Vyhledávání

  1. uživatel zadá požadavek
  2. vyhledávač najde obsahově podobné stránky
  3. vyhledávač seřadí výsledky dle pageranku

Jsou při vyhledávání výsledky upravovány dle uživatele, který vyhledává? Kdy by takové seřazení nastalo?

Děkuji za pozornost!

  • matej.cajthaml@ssps.cz
  • https://ssps.cajthaml.eu/