Kapitola 27
Státnice I3: Vyhledávání a extrakce informací

27.1 Informační systémy

- Faktografické vs. dokumentografické

- Zpřístupnění vs. dodání dokumentu

- Indexace nutná – termy

- řízená, neřízená

- tezaury

- Kritérium predikce + maxima

- Precision, recall

27.2 Vyhledávání v textu

- Triviální algoritmus

- Knuth-Morris-Pratt

- Aho-Corrasicková

27.3 Boolské informační systémy

- Dokument reprezentován množinou termů, které ho vystihují

- Dotazy: AND, OR, NOT, wildcards, víceslovné, proximitní omezení, tezaurus, lemmatizace

- Invertovaný indexový soubor (org. po termech)

- Uspořádání výsledků (DNF, počet splněných konjunkcí)

- Zpětná vazba

27.4 Vektorové informační systémy

- Každý z dokument reprezentování -složkovým vektorem vah důležitostí termů ()

- Indexový soubor je matice vah

- Dotaz je taky vektor, vyhodnocení a řazení pomocí:

- základní

- vylepšení na délku vektorů (počet nenulových ) – dělení , nebo

- jiné – normalizace na jednotkovou délku vektorů

- Nerozlišuje se disjunkce a konjunkce

- Negace = přidání záporných vah do dotazů

- Indexace podle term frequency – (podíl počtu výskytů daného termu v dokumentu z celk. počtu termů v něm)

- Normalizovaná (do ).

- Inverzní , pokud se term vyskytuje v dokumentech z .

- Výpočet vah ( je normalizace)

- Matice podobnosti termů – závislost a zastupitelnost termů

27.5 Induktivní systémy

- Dvouvrstvá neuronová síť se zpětnou aplikací vah (1. vrstva — termy, 2. — dokumenty)

- Laterální inhibice – zabránění nárůstu vah

27.6 Signaturové systémy

- Uložení na pomalých médiích – předstupeň k lepší metodě

- Každý dokument i search term má signaturu, která funguje jako maska (pokud je bitový and signatury dokumentu a termu nenulový, je dokument možná relevantní a použije se k detailnímu hledání)

- Přiřazení signatury – každý term: jedna jednička na nějakém místě / hashovací funkce

- Zabránění příliš mnoha jedničkám v signaturách dokumentů – rozdělení na bloky (pevné délky nebo pevného počtu jedniček v signatuře)

- Wildcardy obecně nejsou možné, jen s monotónními signaturami

27.7 Rozšířená boolská logika

- Reprezentace stejná jako vektorový model

- Dotazy stejné jako s boolskou logikou, ale s váhami (pokud nejsou uvedeny, bere se 1)

- OR – vzdálenost od nulového dokumentu jako (kde jsou váhy dotazu)

- AND – vzdál. od jednotkového dokumentu jako

- Pro je to vlastně vektorový model, pro se blíží k boolskému

27.8 Rozlišovací hodnoty termů v indexu

- Informace o tom, jak dobře termy rozlišují dokumenty – co se stane, když nějaký z nich vyhodíme

- Rozlišovací hodnota , kde je průměrná podobnost dokumentů s centroidem (“průměrným dokumentem” ) a je totéž, odstraníme-li -tý dokument.

- Je možné použít jako , má lepší vlastnosti než ten logaritmus (viz výše)

27.9 Přibližné hledání

- Detekce chyb, nalezení blízkých termů ve slovníku:

- Počet společných digramů

- Hammingova míra (počet operací replace při doplnění slova znakem na stejnou délku)

- Levenshteinova míra (počet operací replace, insert nebo delete)

- Lze použít konečné automaty