Anotace předmětu
Cílem předmětu je seznámit studenty se základními i pokročilými technikami analýzy textových dat. Po absolvování předmětu bude student schopen: popsat jednotlivé metody analýzy textových dat, porozumět těmto metodám, implementovat tyto metody, případně využít existující knihovny, začlenit tyto metody do vlastního návrhu analýzy konkrétních dat.
Garant předmětu, přednášející
doc. Mgr. Jiří Dvorský, Ph.D.
Přednášky
Přednášky probíhají čtvrtek od 10:45 do 12:15 v učebně EB330.
Osnova přednášek
- Úvod do problematiky informačních systémů. Historie a vývoj vyhledávání v textech. Rozdíly mezi faktografickými
a dokumentografickými IS. Obecný model dokumentografických systému.
- Algoritmy pro přesné vyhledávání v textech. Algoritmy vyhledávání jednoho vzorku. Algoritmy vyhledávání více
vzorků (algoritmus Aho-Corasickové). Vyhledávání regulárních výrazů konečnými automaty. Algoritmy pro přibližné
vyhledávání v textech.
- Sufixové stromy. DAWG. Patricia a podobné datové struktury.
- Primární zpracování textů. Lexikální analýza. Stemming. Lematizace. Stop slova.
- Konstrukce indexových systémů. Zipfův zákon a odhad velikosti indexového systému. Indexování založené na třídění.
Poziční indexové systémy. Metody vážení termů. TF-IDF váhy termů. Metody komprese indexových systémů. Metody kódování
přirozených čísel.
- Dotazovací jazyky. Relevance dokumentu. Míra podobnosti dvojice dokument-dotaz. Relevance vs. podobnost. Struktura
a vyhodnocení dotazu. Booleovský DIS. Hodnocení dokumentografických systémů (přesnost, úplnost, F-míra).
- Signaturové metody. Řetězené a vrstvené kódování signatur. Efektivní vyhodnocení dotazů.
- Latentní sémantika. Metody redukce dimenze. Metody založené na rozkladu matic. Náhodná projekce. Vektorové DIS.
Konstrukce a vyhodnocení vektorových dotazů. Ostatní typy DIS (rozšířené Booleovské). Indexování, struktura dotazů,
vyhodnocení dotazů.
- Vyhledávání na webu. Analýza hypertextových dokumentů, strukturální metody. PageRank a HITS. Metavyhledávání
a kooperativní vyhledávání. Aplikace výpočetní inteligence a soft computingu ve zpracování a vyhledání textu.
Podmínky udělení zápočtu
- Předmět je ukončen klasifikovaným zápočtem.
- Zápočet bude udělen:
- aktivní účast na cvičení a
- za vypracování projektu na vybrané téma a následné obhajobě, pohovoru, s vyučujícím.
- Za aktivní účast na cvičeních lze získat maximálně 30 bodů, za vypracování a obhajobu projektu maximálně 70 bodů.
- Projekt může mít buď formu rešerše nebo implementace vybraného algoritmu, metody spadající pod téma předmětu.
- Deadline na odevzdání projektu je 19. května 2024.
- Projekt se odevzdává ve formě pdf dokumentu, v případě rešerše, nebo zip archivu, v případě implementačního projektu. Jméno dokumentu či archivu musí odpovídat Vašemu loginu.
Témata rešerší
Následující témata rešerší jsou orientační, lze si zvolit i téma vlastní.
- Indexování a vyhledávání v matematických textech
- Indexování a vyhledávání ve zdrojových kódech programů
- Metody komprese indexových struktur
- Metody komprese grafů
- Metody komprese textových dokumentů
- Využití soft computingu (např. genetické algoritmy) ve zpracování textu
- Paralelní algoritmy pro zpracování dokumentů
- Využití speciálního hardware (CUDA apod.) pro zpracování dokumentů
- Open source knihovny pro indexování a vyhledávání dokumentů
- Metody a knihovny pro redukci dimenze (SVD, NMF atd.)
- Vektorový model a zpracování dokumentů
- Metody sumarizace textu
- Modern lossless compression methods, see Proceedings of Data Compression Conference (DCC), https://dblp.org/db/conf/dcc/index.html
- Compression methods based on context-free grammar, see https://en.wikipedia.org/wiki/Grammar-based_code
Témata implementačních projektů
- Témata pro implementační projekt nutno konzultovat s garantem předmětu.
- Je možno využít i téma projektu zpracovávaného do jiného předmětu, pokud se bude toto téma týkat i předmětu MATD.
Učební materiály
Základní literatura
- Kopecký M., Pokorný J.: Dokumentografické informační systémy, Karolinum 2006, ISBN 8024611481
- Manning, C. D.; Raghavan, P. & Schutze, H.: Introduction to Information Retrieval, Cambridge University Press, 2008.
Doplňková literatura
- Witten I. H., Moffat A., Bell T. C.: Managing Gigabytes (2nd ed.): Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers Inc., 1999, ISBN 1-55860-570-3
- Baeza-Yates R. A., Ribeiro-Neto B.: Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., 1999, ISBN 020139829X
- Feldman R., Sanger J.: The Text Mining Handbook: Advanced Approaches in Analyzing Unstructured Data, Cambridge University Press, 2006, ISBN 978-0521836579
- Berry M. W., Kogan J.: Text Mining: Applications and Theory, Wiley, 2010, ISBN 978-0470749821
- Weiss S. M., Indurkhya N., Zhang T.: Fundamentals of Predictive Text Mining, Springer, 2010, ISBN 978-1849962254
- Langville, A. N. & Meyer, C. D. Google's PageRank and Beyond: The Science of Search Engine Rankings Princeton University Press, 2006
- Korfhage, R. R. Information Storage and Retrieval, John Wiley & Sons, 1997
Ostatní materiály