{{Stub}} {{TOC float}}

{{Sources|Velkou část otázky pokrývá předmět Dokumentografické informační systémy Michala Kopeckého -- User:Rajjo 17:37, 29 Aug 2010 (CEST)

• slidy k předmětu Dokumentografické informační systémy

• wen:Information_retrieval

}}

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

Vyhledávání v textu

• Triviální algoritmus

• Knuth-Morris-Pratt

• Aho-Corrasicková

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

Vektorové informační systémy

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

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: \in \̲[̲0,1]

  )

• Indexový soubor je matice vah $m\times n$

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

  • základní $Sim(\vec{w}_i,\vec{q}) = \sum_{k=1}^n w_{i,k}q_k$

  • vylepšení na délku vektorů (počet nenulových $w_k$) -- dělení $\sum w_i + \sum q$, $\sum w_i + \sum q - 2 \sum wq$ nebo $\sqrt{\sum w_i^2 \cdot \sum q^2}$

  • 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 -- $TF_{i,j} = \frac{t_j}{\sum_{i=1}^m t_i}$ (podíl počtu výskytů daného termu v dokumentu z celk. počtu termů v něm)

  • Normalizovaná $NTF = \frac{1}{2} + \frac{TF}{2 \max(TF)}$ (do

    ParseError: KaTeX parse error: Undefined control sequence: \[ at position 12: \{0\} \cup \̲[̲1/2,1]

    ).

  • Inverzní $ITF_j = \log(n/k)$, pokud se term $j$ vyskytuje v $k$ dokumentech z $n$.

• Výpočet vah $w = \frac{NTF\cdot ITF}{Z}$ ($Z$ je normalizace)

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

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

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

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 $DF = (0,\dots,0)$ jako

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 6: \sqrt\̲[̲p]{\frac{q_a^p …

  (kde $q_a,q_b$ jsou váhy dotazu)

• AND -- vzdál. od jednotkového dokumentu jako <maht>1 - \sqrt[p]{\frac{q_a^p(1-w_{i,a})^p + q_b^p(1-w_{i,b})^p}{q_a + q_b}}$

• Pro $p = 1$ je to vlastně vektorový model, pro $p\to\infty$ se blíží k boolskému

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 $DV_k = Q^{(k)} - Q$, kde $Q = \frac{\sum_{i=1}^n Sim(d_i,C)}{n}$ je průměrná podobnost dokumentů s centroidem ("průměrným dokumentem" $C = \frac{\sum_{i=1}^n d_i}{n}$) a $Q^{(k)}$ je totéž, odstraníme-li $k$-tý dokument.

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

Přibližné hledání

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

  • Počet společných digramů

  • wen:Hamming%20distance (počet operací replace při doplnění slova znakem $\lambda$ na stejnou délku)

  • wen:Levenshtein%20distance (počet operací replace, insert nebo delete)

• Lze použít konečné automaty

{{Statnice I3}}