doc. Ing. Jan Platoš, Ph.D. Akademický rok 2018/19 Kancelář: EA432 Konzultační hodiny: Úterý 14:00-15:00

MAD3

Přednášky

  1. Základní informace
  2. Dolování vzorů a pravidel
  3. Výběr atributů a shlukování pomocí reprezentantů a hierarchické
  4. Shlukování na základě hustoty a validace shluků
  5. Speciální shlukovací metody, Detekce odlehlých hodnot
  6. Redukce dimenze, Klasifikace, Výběr atributů a rozhodovací stromy
  7. Rozhodovací stromy, pravidlové systémy, pravděpodobnostní klasifikace, hodnocení klasifikačních algoritmů.
  8. Support Vector Machines
  9. Neuronové sítě
  10. Regrese
  11. Pokročilé přístupy a Ensemble metody

Cvičení

  1. Dolování vzorů (17.9.2018) Zobrazit/Skýt
    1. Vygenerujte všechny kombinace bez opakování o délce 3 z 6 možných.
    2. Na jednom z testovacích souborů (chess, connect) vygenerujte četné vzory z vypočtěte Support.
    3. Z vygenerovaných četných vzorů vypište pravidla a jejich Confidence
    4. Výsledky pro jednotlivé datasety:
      1. Testovací data z přednášky
        2. 
            
      2. Chess
        3. 
            
        
            
      3. Mushroom
        4. 
            
        
            
      4. Connect
        5. 
            
        
            
      5. T10I4D100K
        6. 
            
        
          
      
        
    
        
  2. Výběr atributů a shlukování pomocí reprezentantů (1.10.2018) Zobrazit/Skýt
    3. 
        
      
          
    1. Výběr atributů
      2. 
          
        
            
      1. Načtěte jeden z uvedených datasetů.
        2. 
            
      2. Pomocí Entropie ověřte vlastnosti datasetu pomocí vše atributů.
        3. 
            
      3. Pro výpočet použijte jen numerické atributy a využijte vhodnou mřížku (např. dělení 10).
        4. 
            
      4. Ověřte, možnosti redukce počtu atributů (vypočtěte možnou entropii).
        5. 
            
      5. Nalezněte podmnožinu atributů s minimální entropii.
        6. 
            
      6. Výsledky pro jednotlivé datasety při nastavení dělení N=10 (P je suma pravděpodobnosti, 1=100% bodů):
        7. 
            
          
              
        1. Test.csv
          2. 
              
          
              
        2. Water.csv
          3. 
              
          
              
        3. Wine
          4. 
              
          
              
        4. Wholesale
          5. 
              
          
            
        
          
      
          
    2. k-means shlukovací algoritmus (nepovinný úkol)
      3. 
          
        
            
      1. Načtěte jeden z uvedených datasetů.
        2. 
            
      2. Za pomocí Euklidovy vzdálenosti realizujte/vyzkoušejte k-means algoritmus.
        3. 
            
      3. Projděte si výsledky algoritmu v krocích.
        4. 
          
      
        
    
        
  3. Aglomerativní shlukování (8.10.2018) Zobrazit/Skýt
    4. 
        
      
          
    1. Cílem bude implementovat dvě varianty aglomerativního shlukování a to single a complete linkage.
      2. 
          
    2. Obě metody vychází z matice vzdáleností.
      3. 
          
    3. Cílem bude provést shlukování, které se zastaví buď při vhodné příležitosti, nebo po kompletním shlukování.
      4. 
          
    4. Při kompletním shlukování sestupte dendrogramu shluků a nalezněte ty správné shluky.
      5. 
        
    
        
  4. Shlukování - reálný příklad (15.10.2018) Zobrazit/Skýt
    5. 
        
      
          
    1. Cílem cvičení bude analyzovat reálný dataset, výsledky budou prezentovány rovnou na cvičení, tzn. pozdější odevzdání není možné.
      2. 
          
    2. Načtete si dataset uvedený zde.
      3. 
          
    3. Rozdělte data do vhodných shluků, využít můžete libovolnou metodu, ale počet shluků musíte být schopni zdůvodnit.
      4. 
          
    4. Nalezené shluky by měli vhodně popisovat data.
      5. 
          
    5. Každý nalezený shluk analyzujte a popište typ zákazníků, kteří do něj patří.
      6. 
          
    6. K vašemu řešení připravte krátký report, který mi, včetně zdrojových kódů, zašlete na email.
      7. 
        
    
        
  5. Redukce dimenze (29.10.2018) Zobrazit/Skýt
    6. 
        
      
          
    1. Načtěte dataset pro redukci dimenzi.
      2. 
          
    2. Proveďte redukci dimenze na několik hodnot a změřte si Frobeniovu normu mezi originální a rekonstruovanou maticí.
      3. 
          
    3. Redukci proveďte pomocí SVD a NMF.
      4. 
          
    4. O obou algoritmů si vytiskněte nové bázové vektory.
      5. 
          
    5. Např. v Pythonu je možné obě metody nalézt v Scikit-Learn, Accord.NEt pro C#.
      6. 
        
    
        
  6. Klasifikace rozhodovacím stromem (05.11.2018) Zobrazit/Skýt
    7. 
        
      
          
    1. Načtěte dataset pro klasifikaci.
      2. 
          
    2. Sestrojte klasifikační rozhodovací strom s optimálním dělením.
      3. 
          
    3. proveďte klasifikaci bodů v datasetu.
      4. 
        
    
        
  7. Support Vector Machines (12.11.2018) Zobrazit/Skýt
    8. 
        
      
          
    1. Na adrese knihovny LibSVM nalezněte příklad SVM.
      2. 
          
    2. Otestujte nastavení knihovny na různých zadání bodů a volby kernelů.
      3. 
          
    3. Otestujte různé nastavení kernelů, zejména konstantu C.
      4. 
        
    
        
  8. Neuronové sítě (19.11.2018) Zobrazit/Skýt
    9. 
        
      
          
    1. Nalezněte minimální strukturu sítě pro klasifikaci separabilního datasetu.
      2. 
          
    2. Nalezněte konfiguraci, která maximálně analyzuje separabilní dataset.
      3. 
          
    3. Nalezněte ideální strukturu pro Iris dataset.
      4. 
        
    
        
  9. Regrese (03.12.2018) Zobrazit/Skýt
    10. 
        
      
          
    1. Načtěte regresní data.
      2. 
          
    2. Předzpracujte si je tak bya jste odstranili datum a převedli na den v roce (např.).
      3. 
          
    3. Naučte regresní model na rozdělení dat.
      4. 
        
    
        
  10. Klasifikace - reálný příklad (10.12.2018) Zobrazit/Skýt
    11. 
        
      
          
    1. Cílem cvičení bude analyzovat reálný dataset, výsledky budou odevzdány formou reportu v PDF.
      2. 
          
    2. Načtete si dataset uvedený zde.
      3. 
          
    3. Natrénujte vhodný model (vyzkoušejte i metody z Ensemble přístupů/neuronových sítí).
      4. 
          
    4. K vašemu řešení připravte krátký report, který mi, včetně zdrojových kódů, zašlete na email.
      5. 
        
    
      


      
Datasety

      
    
        
  1. Dolování vzorů: Zobrazit/Skýt
    2. 
        
      
          
    • Test Formát: DAT
      • 
          
    • Chess Formát: DAT
      • 
          
    • Connect Formát: DAT
      • 
          
    • Mushroom Formát: DAT
      • 
          
    • T10I4D100K (generated shopping cart) DAT
      • 
        
    
        
  2. Výběr atributů pro shlukování: Zobrazit/Skýt
    3. 
        
      
          
    • Testová data se 4 nadbytečnými atributy: CSV
      • 
          
    • Wine dataset: CSV
      • 
          
    • Water-treatment dataset: CSV
      • 
          
    • Wholesale dataset: CSV
      • 
        
    
        
  3. Shlukování: Zobrazit/Skýt
    4. 
        
      
          
    • 3 kruhové shluky: CSV
      • 
          
    • 5 kruhových shluků: CSV
      • 
          
    • 5 překrývajících se shluků: CSV
      • 
          
    • Soustředné kruhy: CSV
      • 
          
    • Obdélníky: CSV
      • 
        
    
        
  4. Shlukování reálný příklad Zobrazit/Skýt
    5. 
        
        
  5. Redukce dimenze Zobrazit/Skýt
    6. 
        
      
          
    • Data ke stažení ZDE
      • 
          
        
    
        
  6. Klasifikace Zobrazit/Skýt
    7. 
        
      
          
    • Iris dataset se 4 atributy a 3 třídami. Informace: zde. Formát: CSV, Original
      • 
          
    • Tic-Tac-Toe dataset s 9 atributy a 2 třídami. Informace: zde. Formát: CSV, Original
      • 
          
    • Separabilní 2D dataset. Dataset obsahuje 2 třídy (+1,-1), a jedná se o body v rovině. Každá třída má 50 bodů a mají mezi sebou oddělující pásmo. Formát: CSV
      • 
          
    • Neseparabilní 2D dataset. Dataset obsahuje 2 třídy (+1,-1), a jedná se o body v rovině. Každá třída má 50 bodů, které mají mezi sebou oddělující pásmo a navíc každá třída dalších 20 bodů, které jsou zamíchány v druhé skupině. Formát: CSV
      • 
        
    
        
  7. Regrese Zobrazit/Skýt
    8. 
        
        
  8. Klasifikace reálný příklad Zobrazit/Skýt
    9. 
        
      
 

    

    


    

      

        

          
ARD
      

          

          
Cvičení

          
    
            
  1. Úvod do analýzy dat (04.10.2018) Zobrazit/Skýt
    2. 
            
      
              
    1. Obsah cvičení je vyzkoušet propojení knihoven nad RUIAN daty:
      2. 
              
        
                
      1. Načíst jeden CSV soubor
        2. 
                
      2. Vytisknout tvar a hlavičku dat
        3. 
                
      3. Vytisknout názvy sloupců
        4. 
                
      4. Přejmenovat sloupec dle jeho názvu
        5. 
                
      5. Přejmenovat sloupec dle jeho indexu
        6. 
                
      6. Vybrat dva sloupce dle názvu nebo indexu odpovídající souřadnicím v S-JTSK souřadném systému
        7. 
                
      7. Vytisknout tvar a hlavičku podmnožiny dat
        8. 
                
      8. Zobrazit data v grafy typu Scatter Plot
        9. 
              
      
              
    2. Řešení cvičení: Zobrazit/Skýt
      3. 
              
      
                
      
                
              
      
            
    
            
  2. Pokročilejší analýza (11.10.2018) Zobrazit/Skýt
    3. 
            
      
              
    1. Obsahem cvičení je vyzkoušet propojení knihoven nad RUIAN daty do většího celku s výstupem některých analýz v grafech.
      2. 
              
    2. Program cvičení je:
      3. 
              
        
                
      1. Spojení všech souborů z RUIAN dat (rychlejší je spojení CSV než Pandas.Dataframe).
        2. 
                
      2. Vizualizace všech souřadnic v Scatter grafu (pro správné zobrazení platí x=-y, y=-x) 
        3. 
                 
                
      3. Pro každou obec dle "Kód obce" vypočítat střed ze souřadnic, počet adresních bodů na obec a počet unikátních ulic => DATASET_OBCE (při použití reset_index() jsou sloupce sjednoceny a vznikne novy dataframe)
        4. 
                
      4. Nad datasetem DATASET_OBCE proveďte:
        5. 
                
          
                  
        1. Vypočtěte histogram dle počtu adresních bodů v obci a zobrazte jej pomocí Bar grafu.
          2. 
                   
                  
        2. Vyneste do Scatter grafu 100 obcí s největším počtem adresních míst.
          3. 
                   
                  
        3. Vyneste do Scatter grafu 100 obcí s nejmenším počtem adresních míst.
          4. 
                   
                  
        4. U obou grafů uveďte také názvy obcí a velikost značky přizpůsobte velikosti obce.
          5. 
                
        
                
      5. Nalezněte statistiku počtu obyvatel platnou k 1.1.2018. (ZDE)
        6. 
                
      6. Tuto statistiku propojte s datasetem DATASET_OBCE.
        7. 
                
          
                  
        1. Vypočtěte histogram dle počtu obyvatel v obci a zobrazte jej pomocí Bar grafu.
          2. 
                  
        2. Vyneste do Scatter grafu 100 obcí s největším počtem obyvatel.
          3. 
                   
                  
        3. Vyneste do Scatter grafu 100 obcí s nejmenším počtem obyvatel.
          4. 
                   
                  
        4. Vypište obce s nejmladším obyvatelstvem.
          5. 
                  
          
                  
        5. Vypište obce s největším procentem žen v obci.
          6. 
                  
          
                  
        6. U grafů uveďte také názvy obcí a velikost značky přizpůsobte velikosti obce.
          7. 
                
        
                
      7. Příklad části řešení ZDE
        8. 
              
      
            
    
            
  3. Information retrieval (25.10.2018) Zobrazit/Skýt
    4. 
            
      
              
    1. Obsahem cvičení je vyzkoušet implementaci nástroje pro Information Retrieval.
      2. 
              
    2. Vstupem je kolekce záznamů a výsledkem je nalezení nejpodobnějších dokumentů dle definovaného dotazu.
      3. 
              
    3. Cílem IR je dosažení maximální přesnosti vyhledávání a vráceních všech podobných dokumentu (Precision a Recall).
      4. 
              
    4. Hlavním cílem je toto udělat rychle.
      5. 
              
        
                
      1. Po načtení dat z CSV souboru je možné tyto zkusit zobrazit pomocí metody (Zobrazit/Skýt).
        2. 
                
                
                          def make_image_matrix(rows, cols, images, fileName):
                    img_height = int(math.sqrt(len(images[0])))
                    img_width = img_height
                    mat_width = cols*img_width
                    mat_height = rows*img_height
                    matrix = Image.new('L', (mat_width, mat_height))
                    for row in range(rows):
                      for col in range(cols):
                        idx = row*cols + col
                        data = images[idx].astype(np.int32)
                        data = data.reshape((img_height, img_width), order='F')
                        img = Image.fromarray(data, mode='I')
                        matrix.paste(img, box=(col*img_width, row*img_height))
                    matrix.save(fileName)
                
        
                
      2. Prosté vyhledání Euklidovou vzdáleností a nalezení nejpodobnějších dokumentů vede k tomuto výsledku.
        3. 
                
        
                
      3. Redukce dimenze pomocí metody NMF a podobnost Euklidovou vzdáleností pro 10 a 50 dimenzí.
        4. 
                
        
                
        
                
      4. Redukce dimenze pomocí metody SVD a podobnost Euklidovou vzdáleností pro 10 a 50 dimenzí.
        5. 
                
        
                
        
                
      5. Příklad části řešení Zobrazit/Skrýt a ke stažení ZDE
        6. 
                
        
                  
        
                
        
              
                    
            
    
            
  4. Klasifikace dat (1.11.2018) Zobrazit/Skýt
    5. 
            
      
              
    1. Obsahem cvičení je vytvořit klasifikační nástroj pro dodaná data.
      2. 
              
    2. Vstupem je kolekce záznamů a jejich tříd a cílem je predikce třídy záznamu nad definovaného dotazu.
      3. 
              
    3. Otestujte metody výběru atributů a redukce dimenze.
      4. 
              
    4. Otestujte různé metody klasifikace.
      5. 
            
    
            
  5. Soutěž POKER (1.11.2018) Zobrazit/Skýt
    6. 
            
      
              
    1. Cílem je navrhnout klasifikátor, který co nejlépe analyzuje dataset POKER.
      2. 
              
    2. Hodnocení je dle přesnosti klasifikátoru.
      3. 
              
    3. Hodnocení 20, 15 a 10 bodů za první až třetí místo.
      4. 
              
    4. Při shodné přesnosti se body rozpočítají.
      5. 
            
    
            
  6. Shlukování dat (8.11.2018) Zobrazit/Skýt
    7. 
            
      
              
    1. Vstupem jsou data Movie-lens - hodnocení filmů.
      2. 
              
    2. Otestujte shlukovací metody pro seskupení filmů do skupin.
      3. 
              
    3. Data bude třeba nejprve předzpracovat.
      4. 
              
    4. Příklad části řešení Zobrazit/Skrýt a ke stažení ZDE
      5. 
                
      
                  
      
                
      
            
    
            
  7. Analýza dat ze streamu (29.11.2018) Zobrazit/Skýt
    8. 
            
      
              
    1. Vstupem jsou data ze senzorických vložek do bot, které zaznamenaly postupné procházení, běh a doběh.
      2. 
              
    2. Identifikujte kroky v datech.
      3. 
              
    3. Určete:
      4. 
                
        
                  
      • počet kroků běhu,
        • 
                  
      • čas běhu,
        • 
                  
      • délku běhu v metrech,
        • 
                  
      • jakoukoliv další informaci.
        • 
                
      
              
    4. Příklad části řešení Zobrazit/Skrýt a ke stažení ZDE
      5. 
                
      
                  
      
                
                    
            
    
            
  8. TensorFlow - Part 1 (6.12.2018) Zobrazit/Skýt
    9. 
            
      
              
    1. Základní práce s TensorFlow na nízké úrovni Zobrazit/Skrýt
      2. 
                
      
                  
      Základní potřebné definice pro použití a vytištění verze TensorFlow nainstalované na počítači.
      
                  
      
                 
                  
      TensorFlow je framewrok pro práci s tesnory. Principem frameworku je, že nejprve je definovaný tzv. graf výpočtu a ten je dále vyhodnocen.
      
                  
      
                
                  
      Všechny proměnné a konstanty je možné pojmenovat a toto pojmenování pak využít v rámci vizualizace.
      
                  
                       
                  
      Pro použití vizualizačního nástroje je potřeba do souboru uložit aktuální graf výpočtu. To se dělá pomocí tzv. writeru.
      
                  
      

                  
      TensorFlow umožňuje také spuštění stejné odpoerace nad polem vstupů. výstupem je pak pole jako výstup.
      
                  
      

                  
      Součásti TF jsou také náhodné generátory, a umožňuje s nimi pracovat jako s normálními vektory, všechny matematické operátoru jsou podporované a je možné pak získat požadované hodnoty. Ukážeme si to na příkladu lineární regrese. Nejpreve je třeba připravit data.
      
                  
      

                  
      Dále je třeba vytvořit tzv. vrstvu pro výpočty. Vrstvy definují základní jednotku pro optimalizaci, u kterých je možné ladit nějaké parametry.
      
                  
      

                  
      Jelikož vrstva jako taková je poměrně hloupá, musíme jí nastavit její váhy pomocí optimizéru.
      
                  
      
                
       
              
    2. Je také možné použít připravené estimátory, neboli klasifikátory a regresory. Zobrazit/Skrýt
      3.  
                
      
                  
                      
                
       
              
    3. A nebo rovnou využít high-level api jako je Keras. Zobrazit/Skrýt
      4.  
                
      
                  
                      
                
                  
            
    
            
  9. TensorFlow - Part 2 (13.12.2018) Zobrazit/Skýt
    10. 
            
      
              
    1. Základní analýza MNIST datasetu Zobrazit Notebook
      2. 
              
    2. Základní analýza MNIST datasetu - konvoluční síť Zobrazit Notebook
      3. 
            
    
          


          
Datasety

          
    
            
  1. Geografická RUIAN data
    2. 
            
      
              
    • Originální RUIAN data ZIP/CSV
      • 
              
    • RUIAN v jednom souboru s anglickými názvy sloupců: ZIP/CSV
      •   
              
    • Data o počtu obyvatel s anglickými názvy sloupců: ZIP/CSV
      •               
            
    
            
            
  2. Information Retrieval:
    3. 
            
      
              
    1. Datová kolekce ZIP/CSV
      2. 
              
    2. Dotazy ZIP/CSV
      3. 
            
    
            
  3. Klasifikace dat:
    4. 
            
      
              
    1. Obrazová data - EMNIST (info):
      2. 
              
                        
                
      1. Trénovací sada  X (data): ZIP/CSV, Y (labels): ZIP/CSV
        2. 
                
      2. Testovací sada  X (data): ZIP/CSV, Y (labels): ZIP/CSV
        3. 
              
      
              
    2. Poker Data (info)
      3. 
              
        
                
      1. Popis dat TXT
        2. 
                
      2. Trénovací sada: ZIP/CSV
        3. 
                
      3. Testovací sada: ZIP/CSV
        4. 
              
      
            
    
            
  4. Shlukování MovieLens
    5. 
            
      
              
    1. Základní data 100,000 recenzí, 3600 tagů, 9700 filmů, 610 uživatelů ZDE
      2. 
            
    
            
  5. Streamová data
    6. 
            
      
              
    1. Data ze sensorických vložek v botech ZDE
      2. 
            
                
          
 
    

    


    

      

        

          
AKS / SAC

    
          
Přednášky / Lectures

          
    
            
  1. Základní informace
    2. 
            
  2. Teorie pravděpodobnosti a teorie informace
    3. 
            
  3. Kódy proměnné délky
    4. 
            
  4. Statistické kódování, část 1
    5. 
            
  5. Statistické kódování, část 2
    6. 
            
  6. Slovníkové metody, část 1
    7. 
            
  7. Slovníkové metody, část 2 (od slidu 14)
    8. 
            
  8. Transformace pro kompresi dat
    9. 
            
  9. Aplikace kompresních metod
    10. 
            
  10. Komprese multimediálních dat
    11. 
          

    
          
Cvičení

          
    
            
  1. Histogram pravděpodobností symbolů Zobrazit/Skýt (13.02.2018) 
    2. 
            
      
              
    1. Spočítejte pravděpodobnost jednotlivých symbolů v souboru.
      2. 
              
    2. Proveďte toto pro soubory v češtině, angličtně,
                němčině, francouzštině a maďarštině.
      3. 
              
    3. Vypočtěte entropii v jednotlivých souborech (tedy za jazyky).
      4. 
              
    4. Výsledné histogramy pravděpodobností (pravděpodobnostní funkci) vyneste do jednoho grafu za všechny soubory pro porovnání (např. v Excelu/Matplotlib).
      5. 
              
    5. Porovnejte histogramy pro jednotlivé jazyky pomocí Manhattan distance.
              
    6. Porovnejte vzdálenosti s dalšími třemi soubory Unknown0, Unknown1, Unknown2 a identifikujte jazyk.
              
    7. Výsledky vypadají přibližně takto Zobrazit/Skýt. Výsledky byly dosaženy pomocí čtení souborů po znasích s kódováním utf-8-sig a po převodu všech písmen na malá.
      8. 
              
              
            
    
            
            
  2. Kódování pomocí kódu proměnných délek (19.02.2018) - Hodnocené cvičení!!! Zobrazit/Skýt
    3. 
            
      
              
    1. Implementujte Eliasovo kódování gamma a dekódování.
      2. 
              
    2. Implementujte Fibonacciho kódování a dekódování.
      3. 
              
    3. Pro implementaci nemusíte generovat bity do souboru, stačí do řetězce
      4. 
              
    4. Pro ověření funkčnosti využijte následující datasety:
      5. 
              
        
                
      1. 64k 8-bitových čísel
        2. 
                
          
                  
        1. Uniformní rozdělení data a histogram.
                    Entropie=8.00.
          2. 
                  
        2. Normální rozdělení se středem v 127 a std. odchylkou 16 data a
                    histogram. Entropie=6.05.
          3. 
                  
        3. Exponenciální rozdělení se parametrem 16 data a histogram.
                    Entropie=5.44.
          4. 
                
        
                
      2. 128k 16-bitových čísel
        3. 
                
          
                  
        1. Uniformní rozdělení data a histogram.
                    Entropie=15.59.
          2. 
                  
        2. Normální rozdělení se středem v 2^15 a std. odchylkou 2^11 data
                    a histogram. Entropie=12.97.
          3. 
                  
        3. Exponenciální rozdělení se parametrem 32 data a histogram.
                    Entropie=6.44.
          4. 
                
                        
              
      
              
    5. Výsledné bitové délky a průměrný počet bitů na číslo: Zobrazit/Skýt
      6. 
                
      
            
    

            
  3. Huffmanovo kódování (26.2.2018) Zobrazit/Skýt
    4. 
            
      
              
    1. Nad soubory ze cvičení 1 zjistěte statistiku výskytu symbolů.
      2. 
              
    2. Huffmanovým algoritmem sestavte kódovací strom, a soubor zakódujte.
      3. 
              
    3. Pomocí stejného stromu soubor dekódujte.
      4. 
              
    4. Porovnejte dosaženou kompresi s entropií.
      5. 
              
    5. Opět není nutné pracovat se soubory, ale kódování může být provedeno do pole znaků 0,1
      6. 
              
    6. Výsledky by měly vypadat přibližně takto(pracuji se znaky a soubor čtu v Pythonu pomocí kódování utf-8-sig): Zobrazit/Skýt
      7. 
              
      
            
    
            
            
  4. Statistický model textu N-tého řádu (5.3.2018) - Hodnocené cvičení!!! Zobrazit/Skýt
    5. 
            
      
              
    1. Nad soubory ze cvičení 1 zjistěte statistiku výskytu symbolů.
      2. 
              
    2. Vytvořte model pro daný soubor pro N-tý stupeň kontextového modelování.
      3. 
              
    3. Vypočtěte délku výstupního souboru v bitech (využijte entropie k-tého řádu).
      4. 
              
    4. Vypočtete velikost modelu jako počet uzlů.
      5. 
              
    5. Pro N zvolte 1, 2, 3, (4, 5).
      6. 
              
    6. Výsledky by měly vypadat přibližně takto: Zobrazit/Skýt
      7. 
              
      
            
    

            
  5. Slovníková komprese LZ77 (20.3.2019) - Hodnocené cvičení!!! Zobrazit/Skýt
    6. 
            
      
              
    1. Soubory ze cvičení 1 komprimujte metodou LZ77 nebo LZSS.
      2. 
              
    2. Vyzkoušejte několik velikostí oken (4kB, 16kB, 32kB) a délek nezakódované části (16, 32, 64).
      3. 
              
    3. Vypočtěte délku výstupního souboru v bitech.
      4. 
              
    4. Opět není nutné pracovat se soubory, ale kódování může být provedeno do pole objektů nebo bitů
      5. 
              
    5. Výsledky pro LZ77 by měly vypadat přibližně takto: Zobrazit/Skýt
      6. 
              
      
            
    
            
            
  6. Slovníková komprese LZW (27.3.2019) Zobrazit/Skýt
    7. 
            
      
              
    1. Soubory ze cvičení 1 zkomprimujte metodou LZ78/LZW.
      2. 
              
    2. Vyzkoušejte několik velikostí slovníku (4kB, 16kB, 32kB).
      3. 
              
    3. Vypočtěte délku výstupního souboru v bitech.
      4. 
              
    4. Opět není nutné pracovat se soubory, ale kódování může být provedeno do pole objektů nebo bitů
      5.              

              
    5. Výsledky by měly vypadat přibližně takto: Zobrazit/Skýt
      6. 
              
              
            
    
            
  7. Burrows-Wheelerova transformace (3.4.2019) - Hodnocené cvičení!!! Zobrazit/Skýt
    8. 
            
      
              
    1. Soubory ze cvičení 1 transformujte metodou BWT.
      2. 
              
    2. Velikost bloku nastavte tak, aby se do něj vlezl celý soubor.
      3. 
              
    3. Na výsledek aplikujte metodu Move-to-Front.
      4. 
              
    4. Vypočtěte entropii před a po transformacích.
      5. 
              
    5. Výsledky by měly vypadat přibližně takto: Zobrazit/Skýt
      6. 
              
              
            
    
    
            
  8. Měření podobnosti pomocí komprese (10.4.2019) - Hodnocené cvičení!!! Zobrazit/Skýt
    9. 
            
      
              
    1. Vytvořte algoritmus pro FCD porovnání dokumentů.
      2. 
              
    2. V souboru vždy odstraňte interpunkci a převeďte velikost písmen na malé.
      3. 
              
    3. Slovník vytvořte ze slov pomocí LZW přístupu tvorby frází.
      4. 
              
    4. Vypočtěte vzájemnou podobnost mezi dokumenty.
      5. 
              
    5. Data jsou k dispozici zde
      6. 
              
    6. Výsledky by měly vypadat přibližně takto: Zobrazit/Skýt
      7. 
              
            
    

            
  9. Komprese obrazu - DNN (17.4.2019) Zobrazit/Skýt
    10. 
            
      
              
    1. Otevřete si sdílený sešit s jednoduchou sítí pro kompresi obrazu.
      2. 
              
    2. Proveďte úpravy a najděte vhodnou síť, která generuje optimální kompresi.
      3.               
            
    
          

    
          
Projekty

          
V rámci projektů je třeba ke každému tématu vypracovat prezentaci shrnujícíc vlastní práci, provedené
            experimenty, a dodat zdrojové kódy, data a prezentaci. Rozsah prezentace není definován, ale musí reprezentovat
            celkovou práci, za kterou autor bude hodnocen. Používáte-li další zdroje jako jsou články a cizí prezentace,
            dodejte je jako součást odevzdávaného díla.

          
    
            
  1. Dynamic Markov Coding (DMC) Zobrazit/Skýt
    2. 
            
      
              
    1. Cílem je prostudovat metodu DMC a otestovat tuto metodu v praxi.
      2. 
              
    2. Metoda je popsána v článku.
      3. 
              
    3. Otestování by mělo být provedeno nad vhodnými daty a porovnáno s dalšími metodami.
      4. 
            
    
            
  2. Context Tree Weighting (CTW) Zobrazit/Skýt
    3. 
            
      
              
    1. Cílem je prostudovat metodu CTW a otestovat tuto metodu v praxi.
      2. 
              
    2. Metoda je popsána v článku.
      3. 
              
    3. Otestování by mělo být provedeno nad vhodnými daty a porovnáno s dalšími metodami.
      4. 
            
    
            
  3. Fixed Order Models (FOM) Zobrazit/Skýt
    4. 
            
      
              
    1. Cílem je prostudovat metodu FOM a její varianty a otestovat tuto metodu v praxi.
      2. 
              
    2. Metoda je popsána na této stránce
                a v článcích Matta Mahoneyho .
      3. 
              
    3. Otestování by mělo být provedeno nad vhodnými daty a porovnáno s dalšími metodami.
      4. 
            
    
            
  4. Context Mixing (CM) Zobrazit/Skýt
    5. 
            
      
              
    1. Cílem je prostudovat metodu CM a její varianty a otestovat tuto metodu v praxi.
      2. 
              
    2. Metoda je popsána na této stránce
                a v článcích Matta Mahoneyho ke kompresoru PAQ.
      3. 
              
    3. Otestování by mělo být provedeno nad vhodnými daty a porovnáno s dalšími metodami.
      4. 
            
    
            
  5. Lempel Ziv Markov Algorithm (LZMA) Zobrazit/Skýt
    6. 
            
      
              
    1. Cílem je prostudovat metodu LZMA a otestovat tuto metodu v praxi.
      2. 
              
    2. Metoda je popsána na této stránce
                a této 
                  stránce.
      3. 
              
    3. Otestování by mělo být provedeno nad vhodnými daty a porovnáno s dalšími metodami.
      4. 
            
    
            
  6. Multiple Huffman Table Zobrazit/Skýt
    7. 
            
      
              
    1. Cílem je prostudovat metodu MHT a otestovat tuto metodu v praxi.
      2. 
              
    2. Metoda je popsána v tomto článku
                a ve zdrojovém kódu BZIP2. Další informace je možné najít u kompresního algoritmu Brotli.
      3. 
              
    3. Otestování by mělo být provedeno nad vhodnými daty a porovnáno s dalšími metodami.
      4. 
            
    
    
            
  7. Algoritmus Re-Pair Zobrazit/Skýt
    8. 
            
      
              
    1. Nastudujte algoritmus Re-Pair a jeho praktickou variantu popsanou v článku.
      2. 
              
    2. Otestujte vlastnosti algoritmu na vybraných souborech.
      3. 
            
    
          

        

    


    

      

        

          
SAC - Signal Analysis and Compression

    
          
 Lectures

          
    
            
  1. Basic information
    2. 
            
  2. Probability theory and theory and information
    3. 
            
  3. Variable-length codes
    4. 
            
  4. Statistical coding
    5. 
            
  5. Dictionary-based methods
    6. 
            
  6. Transformation for data compression
    7. 
            
  7. Application of Compression Algorithms
    8. 
            
  8. Multimedia Compression
    9. 
          

    
          
Exercises

          
    
            
  1. Histogram of symbol probabilities Show/Hide
    2. 
            
      
              
    1. Compute the probability of symbols in the file.
      2. 
              
    2. As an input, use the following files in czech, english,
                german, French and hungarian.
      3. 
              
    3. Compute the entropy in each file/languages. 
              
    4. The histogram of symbol probabilities put into one chart for all files. 
              
    5. Compare histogram for each file/language using Manhattan distance. 
              
    6. Compare the distance of histogram for three unknown files Unknown0, Unknown1, Unknown2 and identify the language. 
              
    7. The results looks like Show/Hide. (The results were achieved using python and reading an input file by characters and encoding=utf-8-sig. all letters were converted into lower case.)

              
            
    

            
  2. Variable-length codes - Mandatory!!! Show/Hide
    3. 
            
      
              
    1. Implement Elias Gamma encoding and decoding.
      2. 
              
    2. Implement Fibonacci encoding and decoding
      3. 
              
    3. Do not generate bits, string of 0s and 1s is enough.
      4. 
              
    4. Use the folowwing datasets:
      5. 
              
        
                
      1. 64k 8-bits numbers
        2. 
                
          
                  
        1. Uniform distribution data and histogram.
                    Entropy=8.00.
          2. 
                  
        2. Normal distribution, mean=127, stddev=16 data and
                    histogram. Entropy=6.05.
          3. 
                  
        3. Exponential distribution with parameter 16 data and histogram.
                    Entropy=5.44.
          4. 
                
        
                
      2. 128k 16-bits numbers
        3. 
                
          
                  
        1. Uniform distribution data and histogram.
                    Entropy=15.59.
          2. 
                  
        2. Normal distribution, mean=2^15, stddev=2^11 data
                    and histogram. Entropy=12.97.
          3. 
                  
        3. Exponential distribution with parameter 32 data and histogram.
                    Entropy=6.44.
          4. 
                
                        
              
      
              
    5. The resulting bit lengths and average bits per numbers: Show/hide
      6. 
                
      
            
    

            
  3. Huffman encoding Show/Hide
    4. 
            
      
              
    1. Implement Huffmanovým encoding - build a Huffman tree and encode the file.
      2. 
              
    2. Use the same tree for decoding.
      3. 
              
    3. Use the same files as in Exercice 1.
      4. 
              
    4. Compare the resulting compression ratio to the entropy..
      5. 
              
    5. Do not generate bits, string of 0s and 1s is enough.
      6. 
              
    6. The results looks like: Show/Hide. (The results were achieved using python and reading an input file by characters and encoding=utf-8-sig.):
              
      
            
    
            
            
  4. Statistical model of text with Order-N - Mandatory!!! Show/Hide
    5. 
            
      
              
    1. Create an model of a file of Order-N using context modelling.
      2. 
              
    2. Compute the length of the output file in bits (use Entropy of higher orders)
      3. 
              
    3. Compute the number of nodes in a model. 
      4. 
              
    4. For N select 1, 2, 3, (4, 5).
      5. 
              
    5. The results should looks like: Show/Hide
      6. 
              
      
            
    

            
  5. Dictionary-based compression LZ77 - Mandatory!!! Show/Hide
    6. 
            
      
              
    1. Implement LZ77 or LZSS algorithm.
      2. 
              
    2. Use three different window sizes (4kB, 16kB, 32kB) and lengths of uncompressed part (16, 32, 64).
      3. 
              
    3. Compute the size of the output in bits.
      4. 
              
    4. Use the same files as in Exercice 1.
      5. 
              
    5. Do not generate bits, string of 0s and 1s is enough.
      6. 
              
    6. The results should look like this: Show/Hide
      7. 
              
      
            
    
            
            
  6. Dictionary-based compression LZW Show/Hide
    7. 
            
      
              
    1. Implement LZ78 or LZW algorithm.
      2. 
              
    2. Try three different sizes of the dictionary (4kB, 16kB, 32kB).
      3. 
              
    3. Compute the size of the output in bits.
      4. 
              
    4. Use the same files as in Exercice 1.
      5. 
              
    5. Do not generate bits, string of 0s and 1s is enough.
      6. 
              
              
    6. The results should look like this: Show/Hide
      7. 
              
              
            
    
            
  7. Burrows-Wheeler transform - Mandatory!!! Show/Hide
    8. 
            
      
              
    1. Implement Burrows-Wheeler transform (BWT).
      2. 
              
    2. The size of the block set to cover whole file.
      3. 
              
    3. Apply Move-to-Front transform to the result of BWT.
      4. 
              
    4. compute the entropy before the transforms and after them.
      5. 
              
    5. Use the same files as in Exercice 1.
      6. 
              
    6. The results should look like this: Show/Hide
      7. 
              
              
            
    
    
            
  8. Similarity measurement using compression - Hodnocené cvičení!!! Show/Hide
    9. 
            
      
              
    1. Implement Fast Compression Measure algorithm (FCD) for document comparison.
      2. 
              
    2. Create the vocabulary of phrases using the LZW approach on whole words.
      3. 
              
    3. Compute the similariy between documents.
      4. 
              
    4. Dataset is avaiable here
      5. 
              
    5. The results should look like this: Show/Hide (The version differs in dictionary builnd phase)
      6. 
              
            
    
          

    
          
Projects

          
The projects topics listed bellow is an inspiration for your project, that have to be elaborated for the subject. The result will be a PDF report  with detail about the problem, related informations, description of the experiment and results and their comparison/dicsussion. The length is not defined but it is half of the final exam. Any used sources (source codes, articles, etc.) will be added to the submission.

          
    
            
  1. Dynamic Markov Coding (DMC) Show/Hide
    2. 
            
      
              
    1. The goal is to study DMC method and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in article.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4. 
            
    
            
  2. Context Tree Weighting (CTW) Show/Hide
    3. 
            
      
              
    1. The goal is to study CTW method and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in article.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4. 
            
    
            
  3. Fixed Order Models (FOM) Show/Hide
    4. 
            
      
              
    1. The goal is to study FOM method and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in this page and in articles by Matt Mahoney.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4. 
            
    
            
  4. Context Mixing (CM) Show/Hide
    5. 
            
      
              
    1. The goal is to study CM method and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in this pageand in articles by Matt Mahoney and in documentation of PAQ compressor.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4. 
            
    
            
  5. Lempel Ziv Markov Algorithm (LZMA) Show/Hide
    6. 
            
      
              
    1. The goal is to study LZMA method and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in this page
                and this page.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4. 
            
    
            
  6. Multiple Huffman Table Show/Hide
    7. 
            
      
              
    1. The goal is to study MHT principle and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in article
                and in source codes of BZIP2. More information may be found in Brotli compression algoritmh.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4. 
            
    
    
            
  7. Algoritmus Re-Pair Show/Hide
    8. 
            
      
              
    1. The goal is to study Re-Pair algorithm and evaluate this method in real-cases.
      2. 
              
    2. The algorithms is described in article.
      3. 
              
    3. The evaluation should be performed on suitable data and compared with standard methods.
      4.