Česky
Kamil Dudka

Study

File detail

Name:Downloadzzn.txt [Download]
Location: study > min
Size:57.9 KB
Last modification:2009-06-26 20:53

File content

Copyright (c)  2008  Kamil Dudka.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
Texts.  A copy of the license is included in the section entitled "GNU
Free Documentation License".

Získávání znalostí z DB
=======================
- motto: "Topíme se v datech, ale trpíme nedostatkem znalostí"
- snaha o maximální automatizaci procesu získávání znalostí
- získané informace musí být nějak užitečné

- definice: získávání znalostí z databází - extrakce "zajímavých" informací,
  které jsou:
    1) netriviální (nezískám je jediným SQL dotazem)
       - nepatří sem deduktivní DB a expertní systémy
    2) skryté (informace, které nejsou na první pohled vidět)
    3) informace by měla být dříve neznámá (vydolujeme něco, co by nikdo
       nečekal, souvisí s 2) )
    4) získaná informace by měla být k něčemu užitečná (pro další
       rozhodování)

- synonymum: dolování (z) dat - nedolujeme data, ale ZNALOSTI z dat!!
- aplikace získávání znalostí:
    - analýza trhu / management (nákupní košík, reklamní kampaně)
    - finanční analýza / analýza rizik
    - detekce podvodů a neobvyklého chování (na rozdíl od analýzy hledáme
      netypické transakce - používají se opačné algoritmy)
    - získávání znalostí z textu
    - získávání znalostí v proudech dat (nějaký senzor/kamera)
    - analýza biologických dat (využití v genetice, ...)

Proces získávání znalostí z DB
------------------------------
- na půlsemestrální zkoušce budeme vysvětlovat rozdíl mezi dolováním z dat a
  procesem získávání znalostí: dolování z dat je jen jedna část celého procesu
- jednotlivé fáze procesu:
    1. čištění a integrace (DB --> datový sklad)
        - informace mohou obsahovat šum (např. hodnoty mimo) - je třeba
          opravit
        - tato fáze má 90% vliv na kvalitu výsledků
    2. výběr a transformace (datový sklad --> relevantní data)
        - někdy se uvádí ještě jedna fáze:
            redukce dat - když algoritmus není schopný zpracovat všechna data
                        - není triviální (musí se redukovat inteligentně)
                        - rozlišujeme redukce na úrovni řádků/sloupců
    3. dolování z dat (relevantní data --> vzory)
        - výsledkem může být např. naučená neuronová síť (dáme jí na vstup
          data a ona nám řekne výsledek)
    4. vyhodnocení a prezentace (vzory --> znalosti)
        - převedení znalostí do formy srozumitelné uživateli (manažerovi, ...)

    - tento seznam představuje jednu iteraci celého procesu, často je potřeba
      se v průběhu získávání dat vracet o krok (nebo víc kroků) níže a
      jednotlivé etapy opakovat

Business intelligence
---------------------
- metody, techniky a nástroje sloužící k podpoře rozhodování
- pyramida znázorňující rostoucí potenciál podpory rozhodování
    (směrem dolů roste potenciál)
    - datové zdroje (papír, soubory, databázové systémy, OLTP systémy)
    - datové sklady / datová tržiště
    - zkoumání dat (statická analýza, dotazování) - datový analytik
    - dolování z dat (objevování informace) - datový analytik
    - prezentace dat (vizualizační techniky) - obchodní analytik / odborník
      na danou problematiku
    - rozhodování - koncový uživatel - nemusí mít ponětí o dolování z dat

- stačí vědět vztah business intelligence vzhledem k dolování z dat

Druhy dat pro dolování
----------------------
    1. relační databáze
        - nejčastější zdroj dat (SQL)
        - lze rozšířit o třetí rozměr - čas (tabulka --> kostka)

    2. datový sklad
        - modelem je multidimenzionální datová kostka
        - zpřístupnění dat pomocí OLAP operací (drill-up, drill-down)

    3. transakční databáze
        - nemá nic společného s transakcemi v relační databázi
        - transakcí v transakční databázi může být třeba nákup
        - lze jednoduše uložit do relační databáze (přidá se sloupec s ID
          transakce)

Typy dolovacích úloh
--------------------
A) deskriptivní - charakterizují obecné vlastnosti analyzovaných dat
B) prediktivní - předpovídání nějakého chování do budoucna

1) popis konceptu/třídy
    charakterizace dat - např. zjištění, kteří zákazníci utratí v daném
                         obchodě více než 100 000 Kč ročně
                       - sumarizace dat analyzované třídy

    diskriminace dat - zjištění čím se liší zákazníci, kteří nakupují v daném
                       obchodě pravidelně (více než 2x za měsíc) od těch,
                       kteří nakupují zřídka (méně než 3x ročně)
                     - cílová třída je vymezena porovnáním s jinými třídami

2) odhalování vztahů mezi atributy - hledáme asociační pravidla

3) klasifikace a predikce
   - přiřazení objektů do předem daných tříd
   - predikce chybějící hodnoty (na základě informací o člověku odhadnu jeho
     plat)

4) shluková analýza
   - odhalení tříd objektů podobných vlastností
   - důležité je, že třídy nejsou dané předem (hledá je program)
   - např. K-means clustering

5) analýza odlehlých hodnot (které se běžně nevyskytují)

6) analýza chování (?)

Užitečnost nalezených vzorů
---------------------------
    a) subjektivní míra
       - program vrátí více hodnot, analytik si vybere ty "zajímavé"

    b) objektivní míra
       - "zajímavé" hodnoty vybere sám program
       - nejčastěji podle podpory/spolehlivosti


Datové sklady a technologie OLAP pro získávání znalostí
=======================================================
(02_DWOLAP.pdf)

Datový sklad
------------
- definováno neformálně:
    - databáze sloužící k podpoře rozhodování, která je oddělená od operační
      databáze
    - podpora pro zpracování informací poskytnutím platformy sloučených
      historických dat pro analýzu (historická data hrají důležitou roli)

- (podnikově strukturovaný depozitář) subjektově orientovaných, integrovaných,
  časově proměnlivých, historických dat (použitých na získávání informací a
  podporu rozhodování), obsahuje atomická i sumární data.
  (W.H. Inmon)

- data jsou organizována podle hlavních subjektů (zákazník, prodej, zboží, ...)
- vytvořen spojením několika heterogenních zdrojů dat
- čištění, integrace (viz. ^)
- časový horizont je delší než u relačních databází (obvykle 5-10 let)
- obsahuje časový element (implicitně/explicitně)
- data jsou ukládána jako série snímků

- nástroje pro datové sklady většinou neumožňují provádět updaty
  (nebudu měnit 5 let starou objednávku)
- stejně tak většinou není implementované transakční zpracování, zotavení po
  havárii, ...

OLTP = On-Line Transaction Processing
OLAP = On-Line Analytic Processing
- zopakovat si hlavní rozdíly mezi OLTP a OLAP (většinou jasné)
- datový sklad je optimalizován pro složité OLAP dotazy, na rozdíl od relační
  databáze, jejíž DBMS je optimalizován pro vysoký výkon při zpracování
  transakcí, zotavení, ... (OLTP)

Multidimenzionální datový model
-------------------------------
- datová kostka se pěkně kreslí, pokud má tři dimenze
- multidimenzionální kostka může mít obecný počet dimenzí
- jednou dimenzí obvykle bývá čas
- jednotlivá fakta si můžeme představit jako body uvnitř kostky
- analýza se pak realizuje jako řez kostkou

- tabulky dimenzí (položka nebo čas)
- tabulky faktů obsahující metriky a cizí klíče pro jednotlivé dimenze
  (největší tabulka v DB)
- n-D kostka ... základní kuboid
- 0-D kostka ... apex kuboid

- dimenze
    - logicky nebo hierarchicky uspořádané
    - textové popisy (na rozdíl od faktů - numerické)
    - jsou menší a nemění se tak často jako fakta
    - časové, geografické a produktové dimenze (stromové struktury)

- modely datových kostek
    schéma hvězdy
    - tabulka faktů spojená s množinou dimenzí

    schéma sněhové vločky
    - normalizace tabulek dimenzí do více menších

    schéma souhvězdí
    - více tabulek faktů sdílí tabulky dimenzí

    - podívat se na příklady datových skladů pro jednotlivé modely
      (https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/ZZN-IT/lectures/02_DWOLAP.pdf
       sl. 21)

- kostku lze definovat v jazyku DMQL (zkoušet se nebude)
- metriky datové kostky - tři typy metriky:
    distributivní
    - pokud metriku rozdělíme na několik podkostek, můžeme provést výpočet
      paralelně a potom dát dohromady

    algebraické
    - lze spočítat jako algebraickou operaci nad výsledkem několika
      distributivních metrik

    holistické
    - nejhorší (př. nejčastěji se vyskytující položka - modus)

- tvoření hierarchií:
    - schematické hierarchie
    - seskupovací hierarchie

- typické OLAP operace
    roll-up
    - sumarizace dat (např. vezmu data 4 kvartálů a dostanu roční)

    drill-down
    - inverzní operace k roll-up (detailnější data, vytvoření nové dimenze)

    pivot
    - operace se týká spíše vizualizace než samotné datové kostky

    drill across
    - současný posun ve více tabulkách faktů
    - více operací roll-up nebo drill-down

    drill through
    - posun na nejnižší úroveň (až na úroveň relačních tabulek)

- dotazovací model Star-Net (pro interaktivní zadávání dotazu uživatelem)

Návrh datového skladu
---------------------
- čtyři pohledy na návrh datového skladu
    1. pohled shora dolů (výběr relevantních informací)
    2. pohled na datové zdroje (které informace mají být načteny/uloženy)
        a) produkční data   - data získaná z operačních DB podniku
        b) interní data     - privátní soubory zaměstnanců, ...
        c) archivní data    - velká kvanta dat
        d) externí data

    3. pohled na datový sklad (tabulky faktů a dimenzí)
    4. pohled z hlediska dotazů (hodnotí data uložená v datovém skladu
       z perspektivy koncového uživatele

    - přístupy shora-dolů/zdola-nahoru

- datové sklady mohou být rozděleny na datové trhy (Data Marts)

Transformace
------------
- cílem je zvýšit kvalitu vstupních dat před zpracováním
- např. konverze finančních dat do jednotné měny (přechod na Euro v průběhu
  získávání dat, ...)
- také konverze kódování (přechod z MS-DOG na Windows), překlepy lidí, ...
- chybějící hodnoty, konvence názvů pojmů a objektů (sjednocení terminologie)

- tři modely datového skladu
    podnikový sklad
    - informace týkající se celé organizace

    datový trh
    - podmnožina dat předchozího

    virtuální datový sklad
    - pouze jako pohled nad relační databází
    - problém s výkonem (transformace se provádí při každém dotazu)

Architektury OLAP serverů
-------------------------
    relační OLAP (ROLAP)
    - datový sklad je uložen v relační DB (nebo rozšířené relační DB)
    - optimalizace DBMS, implementace agregačních funkcí, ...

    multidimenzionální OLAP (MOLAP)
    - řídké uložení multidimenzionálních dat založené na polích
    - indexování sumarizovaných dat

    hybridní OLAP (HOLAP)
    - kombinace dvou předchozích
    - např. Microsoft SQL Server

    specializované SQL servery
    - SQL dotazy nad modelem hvězdy / sněhové vločky

Implementace datového skladu
----------------------------
- stručně, na zkoušce nebude...
- datovou kostku lze vidět jako množinu kuboidů
    --> materializace datové kostky
- výpočet operace GROUP BY
- optimalizace:
    - pro výpočet agregované operace se používá výsledek dříve vypočtené
      agregované operace
    - cache pro dříve vypočtené kuboidy

Indexování multidimenzionálních dat
-----------------------------------
- používají se bitmapové indexy (!!)
- pro každou hodnotu daného atributu vytvořím bitové pole (vektor)
- také se používají tzv. spojovací indexy (spojení je častá operace)

Analýza datových kostek založená na objevování
----------------------------------------------
- analýza prováděná uživatelem
- založeno na statistické analýze
- výjimečná data jsou označena barevně

Využití datových skladů
-----------------------
- zpracování informací - podpora dotazování
- analytické zpracování - OLAP, multidimenzionální analýza
- získávání znalostí - skryté souvislosti v datech (asociační pravidla, ...)

OLAM = On-Line Analytical Mining
--------------------------------
- dolování z dat pomocí OLAP operací


Získávání frekventovaných množin a asociačních pravidel
=======================================================
(04_AR.pdf)

Získávání pravidel z transakčních DB
------------------------------------
- nemá nic společného s OLTP, jedná se o transakční DB z hlediska obsahu
- každá transakce obsahuje množinu položek
- analýza nákupního košíku, marketing, návrh katalogu, ...

Frekventovaná množina
---------------------
- množina položek, které se často vyskytují v transakci současně
- lze definovat množinou asociačních pravidel
- nemá smysl hledat frekventované množiny mohutnosti 1
- množina položek, které mají vyšší podporu než minimální hodnota, se nazývá
  frekventovaná množina

Asociační pravidlo
------------------
- uživatel zadá minimální podporu a minimální spolehlivost
- pokud má pravidlo vyšší podporu/spolehlivost, než je minimální hodnota,
  nazveme pravidlo silné asociační pravidlo

- můžu hledat levou/pravou stranu asociačního pravidla
- booleovské / kvantitativní asoc. pravidla
- jednodimenzionální / vícedimenzionální asoc. pravidla
- jednoúrovňová / víceúrovňová asoc. pravidla
    víceúrovňová --> jednotlivé položky tvoří hierarchii (rohlík --> pečivo)

Získávání asociačních pravidel
------------------------------
- podpora:      počet zásahů / počet všech transakcí
- spolehlivost: podmíněná pravděpodobnost (Bayes)
- podmnožina frekventované množiny je také frekventovaná množina:
    jestliže {AB} je frekventovaná množina, tak {A} a {B} jsou také
    frekventované množiny (!!)
- lze využít i obráceně:
    jestliže {A} není frekventovaná množina, tak {AB} nemůže být frekventovaná
    množina (!!)

Algoritmus Apriori
------------------
- založeno na výše zmíněné myšlence
- iterativní nalezení frekventovaných množin s kardinalitou od $1$ do $k$
- algoritmus skončí, když už není co spojovat
- generování kandidátů:
    TODO
- optimalizace výpočtu podpory kandidátů:
    TODO
- vylepšení algoritmu Apriori
    - redukce počtu průchodů transakční databází
    - snížení počtu kandidátů

    - počítání množin založené na hashování
      (vyřadím hashovací koš, který neobsahuje frekventované množiny)

    - redukce transakcí (transakce, které neobsahují žádné frekventované
                         k-množiny, jsou vyřazeny z dalšího zpracování)

    - rozdělení (každá množina, která může být frekventovaná, musí být
                 frekventovaná aspoň v některé části DB)
        --> alg. Partition (dva průchody DB - rozdělení, sjednocení)

    - vzorkování frekventovaných množin
        - ideální pokud se vzorek vleze do operační paměti
        - většinou se kombinuje se snížením minimální podpory pro vzorky

Algoritmus MaxMiner
-------------------
- dolování maximálních množin
- frekventované množiny se seřadí sestupně podle míry podpory
- existují i jiné alg., většinou založené na Apriory, tohle se snad zkoušet
  nebude...

FP-strom
--------
- Frequent Pattern Tree
- dolování frekventovaných množin bez generování kandidátů
- snaha zabránit četnému čtení z DB
- dekompozice dolovacích úloh na menší (podstromy)
- princip:
    1) konstrukce podmíněného základu
    2) konstrukce podmíněného FP-stromu
    3) rekurzivní dolování
- projít si příklad !!
- nic efektivnějšího než FP-strom, zatím nikdo nevymyslel

Převod frekventovaných množin na asociační pravidla
---------------------------------------------------
- na základě Bayesova vzorce pro podmíněnou pravděpodobnost
- míru podpory musím mít někde uloženou, abych DB neprocházel znovu

Zobecněná asociační pravidla
----------------------------
- metoda GUHA (prof. Hájek, 1966)


Víceúrovňová asociační pravidla
===============================
- položky často tvoří hierarchii
- položky na nižší úrovni mívají nižší podporu (jasné)
- různé přístupy k dolování víceúrovňových asociací:
    shora dolů
    - nejprve nalezení silných pravidel (na nejvyšší úrovni)
    - potom se postupně hledají slabší asociační pravidla

- problém s nastavením minimální podpory - je potřeba nastavit různou hodnotu
  pro různé úrovně asociačních pravidel
    --> redukovaná podpora - různé strategie:
        1. nezávisle na úrovních
           - nezjišťuje se jestli je předchůdce frekventovaný

        2. filtrování úrovně k-množinou
           - množina je testovaná, je-li množina vyšší úrovně frekventovaná

        3. filtrování úrovně jednou položkou
           - je-li uzel frekventovaný, pak jsou testovány jeho následníci

        4. kontrolované filtrování úrovně jednou položkou
           - navíc se porovnává hodnota podpory s prahem zanoření

- někdy je potřeba filtrovat redundantní pravidla - které o ničem nevypovídají
  (sl. 60)

- dolování víceúrovňových pravidel je také založené na alg. Apriori, FP-Tree

Vícedimenzionální asociační pravidla
====================================
- na rozdíl od jednoduchých implikací hledáme více predikátů (na levé straně
  pravidla)

- dva typy atributů
    kategorické
    - konečný počet možných hodnot (konečnou doménu)
    - většinou řetězcové, někdy číselné (např. známka ve škole)
    - většinou nad nimi není definované uspořádání

    kvantitativní
    - číselné hodnoty
    - nad kterými je definováno uspořádání
    - domény "nejsou konečné", hodnot je příliš mnoho

    - lze diskretizovat - např. rozdělím lidi do skupin podle věku
    - jiný přístup jsou kvantitativní asociační pravidla
      (dynamická diskretizace do "košů" podle rozložení dat)
    - nebo lze použít asociační pravidla založená na vzdálenosti
      (vychází z předchozího, ale zabrání, aby hodnoty ležely blízko sebe)

    - diskretizace do hloubky/do šířky

- 2D kvantitativní asociační pravidla
    --> dám do 2D mřížky a shlukuji sousední buňky mřížky

ARCS = Association Rule Clustering System
-----------------------------------------
- rozdělení do košů, následné shlukování
- potom optimalizace, respin
- pouze kvantitativní atributy, pouze dva na levé straně
- používají se různé alternativy ARCS

K-částečná úplnost
------------------
- metrika pro určení kvality vytvořených intervalů
- určuje ztrátu informace diskretizací
- nerespektuje sémantiku dat
- podívat se na postup (sl. 70)

Optimalizovaná asociační pravidla
---------------------------------
- asociační pravidla s maximální podporou s ohledem na minimální spolehlivost
- vs. asociační pravidla s minimální spolehlivostí
- smysluplnější diskretizace:
    - podle hustoty/počtu bodů uvnitř intervalu
    - podle blízkosti bodů uvnitř intervalu

Asociační pravidla založená na vzdálenosti
------------------------------------------
    1. nalezení shluků hodnot
    2. vytváření asociačních pravidel, které obsahují shluky hodnot

Metoda adaptivního slučování numerických atributů
-------------------------------------------------
- setřiďování numerických atributů podle různých kritérií
- metrika Diff se musí počítat pro všechny *sousední* intervaly
  (pokud mám 100 intervalů, počítám 99x Diff)
- dále počítám vzdálenost prvků uvnitř intervalu
- shlukování se musí zastavit (aby nevznikl jeden interval obsahující všechny
  hodnoty)
    --> kritérium zastavení: $c_{i+1}-c_i > 3d$

Metoda založená na průměrné vzdálenosti
---------------------------------------
- cílem je oddělit zpracování kvantitativních a kategorických atributů

    1. zpracování kategorických atributů
    2. zpracování kvantitativních atributů
    3. generování asociačních pravidel

Metoda založená na statistice
-----------------------------
    TODO

Metriky zajímavosti pravidel
----------------------------
- objektivní: podpora, spolehlivost
- subjektivní: neočekávané/akční pravidla

- podpora/spolehlivost není vždy vhodná
    --> korelace (pozitivní/negativní)


Asociační pravidla založená na omezeních
========================================
- vhodné spíše pro Booleovská pravidla
- nutné při velkých objemech dat
- různé druhy omezení:
    1. omezení typu znalosti
    2. omezení úrovně/dimenze
    3. omezení pravidel
        a) podle tvaru - metapravidly řízené dolování
        b) podle obsahu - optimalizace dotazu

        - lze omezovat jednu stranu nebo obě strany pravidla
        - jednoduchá omezení přímo na datové položky
          (např. na pravé straně pravidla pouze zboží >=100Kč)
        - také lze omezit celé domény nebo zavést agregační omezení

    4. omezení zajímavostí

- správný alg.:
    nalezne pouze frekventované množiny, které splňují omezení

- kompletní alg.:
    všechny frekventované množiny splňující omezení jsou nalezeny

- antimonotónní omezení
    pokud množina nesplňuje omezení, nesplňuje jej ani žádná její nadmnožina

- monotónní omezení
    pokud množina splňuje omezení, každá její nadmnožina jej také splňuje

- strohost omezení na zkoušce nebude...


Předzpracování dat
==================
- základem jsou kvalitní vstupní data (zásadní vliv na spolehlivost
  vydolovaných znalostí)
- slajdy jsou zkrácená verze slajdů k učebnici (Jiawei Han)
- doplňující informace jsou v extra souborech (nelze doplňovat přímo kvůli
  licenčním omezením)
- začátek: sl. 12 (01_HanJZ.pdf)

Kritéria kvality dat
--------------------
    přesnost - vztah k realitě (např. průzkum musí zasáhnout cílovou skupinu)

    úplnost - do šířky (atributy), do hloubky (záznamy)

    konzistence - případné nekonzistence by měly být opraveny během procesu
                  čištění

    aktuálnost - znalosti obsažené v datech se s časem mění
               - někde nevadí (např. analýza struktury DNA)

    důvěra - pokud nevěříme datům, nemůžeme věřit ani získaným znalostem

    interpretovatelnost hodnot - vhodně zvolené intervaly, klasifikační třídy

Typy atributů (opak.)
---------------------
    kvantitativní
    - numerické, potenciálně nekonečné domény
    - nad hodnotami kvantitativního atributu je definována relace uspořádání

    kategorický
    - nabývá diskrétních hodnot
    - počet možných hodnot je omezený (a zpravidla malý)
    - rozdělení do kategorií
    - speciálním typem je binární atribut
    - rozlišují se dva podtypy:
        nominální - není definováno uspořádání (barva, kategorie výrobku, ...)
        ordinální - je definováno uspořádání (vzdělání, známka z předmětu)

Míry z hlediska možnosti distribuce výpočtu
-------------------------------------------
    distributivní - výslednou hodnotu lze počítat distribuovaně
                  - stejný celkový výsledek při použití mezivýsledků
                  - př.: počet prvků, suma, ...

    algebraická - výsledek algebraické operace nad jednou nebo několika
                  distributivními mírami
                - př.: průměr

    holistická - výpočet musí vždy probíhat nad celým datovým souborem
               - př.: výpočet nejčastější hodnoty (tzv. modus)

Problémy s kvalitou vstupních dat
---------------------------------
    nekompletní data - postrádají některé atributy potřebné k dolování z dat
                     - např. nevíme, jestli si zákazník koupil zboží na
                       základě inzerce

    šum v datech - např. záporný plat, nepochopení otázky v dotazníku

    nekonzistence - používají se různé způsoby kódování téhož (zvlášť pokud
                    pracujeme s více zdroji dat)
                  - např. věk vs. datum narození (pokud je zadáno obojí, mělo
                    by sedět...)

Základní úlohy předzpracování dat
---------------------------------
    čištění dat - odstranění výše zmíněných problémů

    integrace dat - spojení dat z více zdrojů

    transformace dat - normalizace - např. převedení hodnot na interval <0, 1)
                     - agregace

    redukce dat - odstranění části dat bez vlivu na celkový výsledek dolování
                  (opět redukce řádků/sloupců)

    diskretizace dat - viz. výše
                     - redukce počtu hodnot
                     - převod kvantitativního atributu na kategorický

Charakterizace středu dat
-------------------------
    průměr / vážený průměr

    medián
    - lichý počet hodnot ... seřadíme, hodnota uprostřed
    - sudý počet hodnot ... seřadíme, průměr dvou prostředních hodnot (!!)

    modus - nejčastější hodnota v souboru

- pokud jsou data nějakým způsobem vychýlená, hodnoty průměru, modu a mediánu
  leží daleko od sebe

Charakterizace rozptylu dat
---------------------------
    kvantily (!!)
    - osu pravděpodobnosti rozdělíme na q stejných intervalů
      (vznikne q-1 hodnot)
    - pro q=100 se kvantil nazývá percentil, pro q=4 kvartil, ...

    rozsah vymezený kvantily (IQR)
    - IQR = mezikvartilová vzdálenost ($Q_3 - Q_1$)
    - např. pro kvartily řekneme, že cokoliv mimo rozsah $Q_3 - Q_1$ je
      vychýlená hodnota

    pěti-číselná sumarizace: $Min, Q_1, M, Q_3, Max$
        M ... medián

    krabicové grafy - velikost boxu odpovídá IQR, dělící čára znázorňuje M,
                      vousy znázorňují (rozumné) min/max

    histogram - znázornění diskrétních / diskretizovaných dat
              - zobrazení jedné proměnné (!!)

    kvantilový graf - na x osa udávající pravděpodobnost, y udává hodnoty

    Q-Q graf - umožňuje vzájemně porovnat dvě hodnoty (Q ... quantile)
             - např. rozložení ceny prodaného zboží u dvou poboček

    Loess Curve - křivka proložená body podle lokální regrese
                  (Loess je zkratka od "local regression")

- v SAS Enterprise Data Miner: blok Insight

Normální rozložení pravděpodobnosti
-----------------------------------
- pravidlo 3\sigma: 99.8% hodnot leží v intervalu +/-3\sigma
  (\sigma je směrodatná odchylka)

Ošetření chybějících hodnot
---------------------------
- pokud alg. neumí pracovat s chybějícími hodnotami, je potřeba tento problém
  vyřešit v rámci předzpracování (ale doporučuje se, i když to alg. umí...)

- lze řešit vynecháním řádků s chybějícími hodnotami, ale může vést k nevhodné
  redukci dat, která má negativní vliv na získaný výsledek

- v ojedinělých případech lze chybějící hodnotu doplnit ručně

- nahrazení chybějících hodnot konstantou má spíše formální charakter (protože
  chybějící hodnota je také informace - viz. hodnota NULL v DB)

- lze chybějící hodnoty nahradit průměrnými hodnotami (snaha co nejméně
  ovlivnit výsledek touto úpravou)

- lepším řešením je doplnit průměrnou hodnotou odpovídající třídy
  (řízené klasifikační metody - strojové učení "s učitelem")

- nejlepším řešením je nahrazení nejpravděpodobnější hodnotou (na základě
  okolních hodnot předpovíme chybějící hodnotu - predikce) - výpočetně
  náročnější


Čištění dat
===========
- sem spadají také způsoby ošetření chybějících hodnot

Odstranění šumu (vyhlazení dat)
-------------------------------
- odstranění dat, jejichž hodnoty nějakým způsobem vybočují
- např. pokud je zdrojem dat dotazník, může být problém s nepochopením otázky
- metody odstranění šumu
    1. binning (zařazení do košů=intervalů)
       - diskretizační metoda
       - redukuje počet možných hodnot
       - diskretizace do šířky/hloubky
            do šířky - intervaly stejné šířky (ekvidistantní) - dobré výsledky
                       pouze při rovnoměrném rozložení dat
            do hloubky - intervaly s přibližně stejným počtem hodnot
       - různé způsoby vyhlazení
            a. všechny hodnoty v koši nahradíme průměrem/mediánem/modem
            b. transformace podle hraničních hodnot (hodnoty v koši nahradím
               jednou z hranic koše, která je k číslu blíž)

    2. regrese (predikce pro kvantitativní hodnoty)
       - proložíme hodnoty křivkou (např. polynomem)
       - nejčastěji lineární regrese ... proložení (regresní) přímkou
       - používá se metoda nejmenších čtverců
       - vyhlazujeme body (hodnoty) vzdálené od regresní přímky

    3. shlukování
       - snažíme se najít shluky hodnot
         (hodnoty v metrickém prostoru blízko u sebe)
       - vyhlazujeme hodnoty ležící mimo shluky (nebo příliš malé shluky)
       - shlukování lze použít i pro diskretizaci - nahrazení všech hodnot
         shluku jednou hodnotou (např. těžištěm shluku)
       - K-means (víme)

    4. kombinace strojové korekce a korekce uživatelem (pokud šumu není hodně)

Čištění jako proces
-------------------
- čištění může do dat zanést nový šum
- proto je někdy nezbytné proces čištění opakovat
- důležitým zdrojem informací jsou metadata (zejména pokud čerpáme z více
  datových zdrojů)

Integrace dat
-------------
- zejména pokud používáme data z více zdrojů
- ale někdy i pokud máme jeden zdroj (záleží na schématu DB)
- vyřešení duplicitních informací, nekonzistence

- problém různé identifikace entit v jednotlivých zdrojích
  (např. auto-inkrement ID vs. rodné číslo zákazníka)

- detekce redundantních atributů (buď duplicitní nebo závislé na jiných)
  --> korelační analýza
      - zjistíme do jaké míry jsou atributy svázány (korelují)
      - korelační koeficient v intervalu <-1,+1>
             0 ... atributy jsou nezávislé
            <0 ... negativně korelované
            >0 ... pozitivně korelované
          +/-1 ... jedna z hodnot je redundantní a lze ji eliminovat

      - chí-kvadrát (viz. EVO), kontingenční tabulka
             - TODO: podívat se do sešitu EVO na výpočet
             - důležitá je hladina významnosti

Transformace dat
----------------
    min-max normalizace - lineární transformace hodnot z nějakého rozsahu
                          např. do intervalu <0,1>

    z-score normalizace - pokud předem neznáme rozsah
                        - odečtení střední hodnoty
                        - podělení střední odchylkou

    normalizace posunutím desetinné tečky

Redukce dat
-----------
- hlavním cílem je získat redukovaná data vhodná pro dolování
- redukce by neměla znehodnotit data z pohledu dolovaných znalostí

- redukce počtu atributů (vhodné zejména pro alg. s exponenciální složitostí)
- používá se tzv. extrakce rysů
    - transformace do nového prostoru atributů
    - nahrazení několika atributů novým atributem
    - cílem je redukce dimenzionality

- metody extrakce rysů
    PCA = Principal Component Analysis
    - využívá prostředků lineární algebry (maticové operace)
    - kovariační matice
    - hledají se "vlastní vektory", které jsou ortonormální

Strategie redukce dat
---------------------
- TODO
- vhodná redukce dat je často důležitější než samotné dolování
- pokud se nám např. podaří vybrat vhodné atributy, můžeme pak pro samotné
  dolování použít jednoduché (a výpočetně nenáročné) alg.
- speciálním případem dolování dat je dolování v proudu dat (zpracování
  signálů)

- různé heuristiky: TODO
- agregace ... zvýšení úrovně abstrakce pohledu (v SQL jako GROUP BY)

Vzorkování
----------
- snížení počtu řádků (na rozdíl od předchozího)
- výběr reprezentující podmnožiny dat
- při běžném vzorkování mohou méně zastoupené skupiny vypadnout
- proto se používá tzv. stratifikované vzorkování, adaptivní vzorkování


Klasifikace a predikce
======================
    (05_klasifikace_predikce.ppt)
- klasifikace má dvě fáze: trénovací a testovací
    --> trénovací/testovací data
- predikce ... předpověď hodnoty (většinou spojité) fce. pro daný objekt

Příprava dat pro klasifikaci
----------------------------
    čištění dat - viz. ^

    významnostní analýza - odstranění atributů, které nejsou potřebné pro
                           danou klasifikaci 

    transformace dat - viz. ^, např. zobecnění dat, diskretizace, ...
                     - speciálním případem je normalizace dat

Vlastnosti klasifikačních metod
-------------------------------
    přesnost předpovědí

    rychlost - výpočetní složitost

    robustnost - odolnost proti šumu / chybějícím hodnotám

    stabilita - schopnost práce s velkými objemy dat

    interpretovatelnost - jak je model složitý pro pochopení

Rozhodovací strom
-----------------
    vnitřní uzel ... test hodnoty atributu

    koncový uzel ... reprezentuje třídu, do které bude daný objekt
                     klasifikován

- atributy musí mít diskrétní charakter

Algoritmus pro vytvoření rozhodovacího stromu
---------------------------------------------
- alg. na straně 9 - TODO: zkusit/pochopit
    - alg. je rekurzivní
    - volá se se dvěma parametry:
        S - seznam vzorů
        L - seznam atributů

    - rekurze má dvě zarážky:
        1. všechna data jsou v jedné třídě
        2. není už atribut, podle kterého by se dala třída větvit
           --> najde se odpovídající třída podle statistik
               (zjistí se, do které třídy vzorky obvykle patří)

    - klíčovým problémem je výběr "vhodného" atributu pro větvení

Výběr vhodného atributu (metoda ID3)
------------------------------------
- je potřeba nějakým způsobem měřit množství informací, které atribut
  poskytuje
- čím méně je jev pravděpodobný, tím větší nese informaci
  (pokud je něco 100% pravděpodobné, nenese atribut žádnou informaci)
- lze vyjádřit vztahem:
    $$Info(a) = -log_2(p(a))$$

    průměrná hodnota atributu - vážený průměr podle pravděpodobnosti

    entropie - průměrné množství informace ($E$)
             - podívat se na vztah
             - leží v intervalu <0,  log_2m>

- dokážeme spočítat pravděpodobnosti padnutí vzorku do jednotlivých tříd
- na základě těchto dat spočítáme entropii, tj. jaké množství informace nese
  daný atribut
- provádí se dvojúrovňově:
    1. podle atributů
    2. pro každý atribut podle hodnot

    (vypadá složitě, ale je to jasné)

    $$Info_A(S)= \sum{\frac{\abs{S_j}}{\abs{S}}Info(S_j)}{j=1}{v}$$

    - za $Info(S_j)$ dosadím z předchozího vztahu (entropie)
    - hodnotu $Info_A(S)$ se naopak snažíme minimalizovat (!!)

- výběr atributu pomocí funkce $Gain(A)$:
    $$Gain(A = Info(S)-Info_A(S)$$


Diskretizace spojitých hodnot
-----------------------------
- je potřeba stanovit split-pointy (hranice intervalů)
- je dobré stanovit split-pointy na základě entropie (aby se nám co nejméně
  informací ztrácelo)
- pozn. obvykle se dělí do dvou skupin (jeden split-point), jinak by bylo
  příliš složité

Metoda C4.5
-----------
- metoda ID3 má problém s atributy, které mají hodně hodnot
  (např. sebere login jako atribut a naučí se "nazpaměť")
- vylepšení oproti ID3 na principu normalizace $Gain(A)$
- $Gain(A)$ podělíme hodnotou $SplitInfo(A)$
- podívat se na výpočet hodnoty $SplitInfo(A)$

- na půlsemestrálce budeme porovnávat C4.5 s ID3 :-)
- vztahy se nemusíme učit nazpaměť

Metoda Gini indexu
------------------
- metoda C4.5 má výkonnostní problém
- snaha zabránit častému výpočtu logaritmu
- podívat se na vztahy (dostaneme stejné výsledky bez logaritmu)
- hodnotu Gini lze použít pro výběr potenční množiny, pokud tvoříme binární
  strom (binární strom se lépe implementuje)

Ořezání stromu
--------------
- bude na půlsemestrálce
- dvě metody:
    1. prepruning - větve, které nemají význam nejsou vůbec generovány
    2. postpruning - napřed vytvoříme úplný strom, potom odstraníme větve
                     s malým významem (pomalejší, ale přesnější)

    - metody lze kombinovat (využití výhod obou metod)

Bayesovská klasifikace
----------------------
- podmíněná pravděpodobnost (Bayesův vzorec, víme)
- jev je daný uzel ve stromu
- hledáme třídu, pro kterou je podmíněná pravděpodobnost nejvyšší
  (spočítáme pomocí Bayesova vzorce)
- str. 28
- Laplaceova korekce ... přidání jednoho prvku do všech tříd
                         (tím se vyhneme dělení nulou)

Bayesovské sítě
---------------
- orientovaný acyklický graf
- tabulky podmíněných pravděpodobností
- během učení klasifikátoru je potřeba určit topologii sítě
- potom se spočítají tabulky podmíněných pravděpodobností pro jednotlivé uzly
- aby pracovalo správně, tak jednotlivé atributy musí být na sobě nezávislé

Neuronové sítě
--------------
- základní koncepce neuronu, bázová, aktivační funkce
- bázová funkce ... většinou skalární součin (vstupy * váhy)
- perceptron - klasifikace do dvou tříd: {-1, 1}, aktivační funkce je signum
- učení perceptronu - viz. SFC
- princip činnosti neuronu/sítě bude na zkoušce (!!)

- backpropagation
    - pokud chci klasifikovat do $k$ tříd, potřebuji $k$ neuronů
      (nepoužívá se binární soustava)
    - vstupy neuronové sítě je dobré normalizovat
    - příklad na BP na zkoušce nebude

SVM = Support Vector Machines
-----------------------------
- modifikace perceptronu
- snaha nalézt dělící přímku co nejdál od bodů obou tříd
- definuje se "zakázané pásmo", které tvoří rezervu pro klasifikaci vzorků,
  které nebyly použity během testování

- řešení nelineárních dat
    - snaha převést nelineární data na lineární za cenu zvýšení počtu atributů
    - problém s nalezením vhodného mapování do lineárního prostoru

Klasifikace založená na pravidlech
----------------------------------
- výstupem jsou pravidla ve tvaru if-then
- problém je, jak taková pravidla získat
- používají se dvě metriky
    1. pokrytí - podíl vzorků pokrytých pravidlem / počet všech vzorků
    2. přesnost - kolik vzorků je klasifikovaných dobře/špatně
- pravidla lze získat z rozhodovacího stromu (viz. ^)

Klasifikátor založený na k-nejbližším sousedství
------------------------------------------------
- princip bude na zkoušce
- mezi vzorky definujeme Euklidovskou vzdálenost
- podívat se na princip
- $k$ je tam proto, aby se zvýšila odolnost proti šumu (aby jeden prvek mimo
  nestáhl k sobě celé okolí)
- experimentálně lze určit, pro která $k$ dává klasifikátor lepší výsledky
- atributy je nutné normalizovat (např. do intervalu <0,1>), aby Euklidovská
  vzdálenost fungovala
- pro diskrétní atributy se vzdálenost definuje následovně:
    0 <-- stejné hodnoty atributů
    1 <-- různé hodnoty atributů

Klasifikátor založený na genetických algoritmech
------------------------------------------------
- na státnicích vůbec nezmiňovat, mohl by se v tom někdo rýpat a moc se to
  neprobírá nikde :-)

Klasifikátor založený na fuzzy množinách
----------------------------------------
- zařazení hodnot do fuzzy množin (jasné)
- zamezuje se striktní diskretizaci na jednotlivé třídy


Predikce
========
- neříkáme, do které třídy prvek patří
- předpovídáme hodnotu nějakého atributu, která může být obecně spojitá
  (dána spojitou funkcí)
- často se používá lineární regrese
- znát rozdíl mezi interpolací/aproximací (jasné)
    - interpolací např. pomocí polynomu (Langrageův interpolační polynom)
    - aproximace např. metodou nejmenších čtverců (LMS)

Lineární regrese
----------------
- soubor hodnot aproximujeme přímkou
- rovnici přímky jsme schopni z hodnot spočítat

Vícenásobná regrese
-------------------
- výsledná hodnota je závislá na více atributech
- regresní funkce má potom více parametrů (ideální když je stále lineární)
- nelineární regrese se většinou transformuje na lineární (např. přidání
  atributu s kvadrátem jako dalšího atributu)


Shluková analýza
================
- rozdělení objektů do tříd (podle podobnosti)
- proces je automatický - nepotřebujeme žádnou trénovací množinu
  (učení bez učitele)
- vstupem jsou hodnoty atributů jednotlivých objektů

- lze použít jako samostatný nástroj nebo jako předzpracování pro jiné alg.
- také se používá pro kompresi dat (shluky zastupují objekty)
- segmentace dat (hustě a řídce obsazené prostory objektů)
- původní využití v biologické taxonomii
- plánování výstavby v městech, ...

- cílem je:
    1. velká podobnost mezi objekty uvnitř třídy (intra-class similarity)
    2. malá podobnost mezi objekty z různých tříd (inter-class similarity)

- požadavky:
    škálovatelnost - efektivní zpracování rozsáhlých množin dat

    schopnost zpracovávat různé typy atributů

    vytváření shluků různého tvaru
    - použití vzdálenostní funkce vede zpravidla ke kulovitým shlukům

    minimální požadavky na znalost problému při určování parametrů

    nezávislost na pořadí vkládání dat

- datové struktury:
    datová matice
    - obsahuje hodnoty atributů

    vzdálenostní matice
    - neobsahuje hodnoty jednotlivých parametrů
    - ale hodnoty vzdálenostní funkce mezi hodnotami objektů
    - matice je trojúhelníková, v diagonále má nulu (vzdálenost objektu od
      sebe samého je nulová)

Vzdálenost podle typu proměnné
------------------------------
    intervalové proměnné
    - spojitá měřítka, přibližně lineární rozdělení
    - někdy je třeba provést standardizaci dat
    - výpočet střední odchylky, z-score

    binární proměnné
    - používá se kontingenční tabulka (na základě četnosti ?)
    - jako vzdálenost se používají koeficienty shody/neshody
    - symetrické/asymetrické (podle toho, jsou-li oba jevy stejně
      pravděpodobné)
    - používají se dva typy vzdálenosti:

        symetrická --> koeficient shody
        asymetrická --> asymetrická binární vzdálenost,
                        binární podobnost (Jaccardův koeficient)

    nominální proměnné
    - zobecnění binárních (více než 2 hodnoty)
    - používá se koeficient jednoduché shody

    ordinální proměnné
    - nad hodnotami je definována relace uspořádání
    - jednotlivým hodnotám lze přiřadit hodnotu a transformovat na interval
      <0,1>

    poměrové proměnné
    - používají se pro děje, které probíhají exponenciálně
    - růst populace kvasinek :-)
    - většinou se aplikuje logaritmická transformace (potom lze zpracovat
      stejně jako intervalové proměnné)

- problém zpracování proměnných různých typů:
    1. provést shlukovou analýzu pro jednotlivé skupiny proměnných
    2. zpracovat všechny typy proměnných dohromady
       - bude na zkoušce !!

Vzdálenostní funkce
-------------------
- může být libovolná, ale musí splňovat základní axiomy
- musí být nezáporná, symetrická, 0 pro d(x,x) a trojúhelníková nerovnost

    Minkowského vzdálenost - viz. Euklidova, ale libovolná mocnina místo 2

    Manhattanovská vzdálenost - žádná mocnina, jenom abs. hodnoty
                              - konkrétní případ Minkowského

    Euklidovská vzdálenost - konkrétní případ Minkowského

Rozdělení shlukovacích metod
----------------------------
- sl. 27/78

Metody založené na rozdělování
------------------------------
- rozděluji $n$ objektů do $k$ tříd
- každý prvek může patřit jen do jedné třídy
- $k$ je parametrem metody (musí být <= $n$)
- jako kritérium se nejčastěji používá čtverec chyby
- alg.:
    1. náhodně se vybere $k$ objektů, které reprezentují jednotlivé shluky,
       ostatní prvky se rozdělí do těchto tříd na základě podobnosti

    2. v cyklu se určují nové středy shluků a objekty se přesunují do shluků
       na základě vzdálenosti

    3. cyklus končí, pokud v iteraci nedojde k žádnému přesunu

- používají se dvě heuristiky:
    A. k-means
       - metoda založená na centrálním bodu
       - třída je reprezentována fiktivním centrálním bodem
       - funguje dobře, pokud data tvoří kompaktní, dobře oddělené, shluky
       - jinak může být počet iterací vysoký
       - metoda je citlivá na šum a odlehlé hodnoty (posunují středy shluků)
       - hledá pouze kulové shluky, nedokáže nalézt shluky nekonvexního tvaru
       - existují různé modifikace (speciální inicializace, ...)

    B. k-medoids
       - metoda založená na reprezentujícím objektu
       - snažíme se zjistit, jak se změní vzdálenosti, když změníme
         reprezentující objekt (objekt se vybírá náhodně)

Hierarchické metody
-------------------
- hierarchický rozklad množiny (strom)
- metody shora-dolů/zdola-nahoru
- na rozdíl od původní metody nelze na nižších úrovních přerozdělit podle
  kritérií, která byla definována na vyšší úrovni
- na jedné úrovni je potřeba vyhodnotit vzdálenosti všech dvojic
    --> metody nejsou dobře škálovatelné

Metody založené na hustotě
--------------------------

DBSCAN
------
- DBSCAN = Density-Based Clustering Method on Connected Regions
  with Sufficiently High Density
- shluk je maximální množina bodů spojených na základě hustoty

    \epsilon-okolí - okolí objektu o poloměru \epsilon

    jádro - objekt, jehož \epsilon-okolí obsahuje alespoň minimální počet
            objektů (dané jako parametr metody)
          - při stanovení následujících vztahů je potřeba napřed zjistit,
            které objekty jsou/nejsou jádrem

    objekt přímo dosažitelný na základě hustoty - sl. 47/78

    objekt dosažitelný na základě hustoty

    objekt spojený na základě hustoty

- problém je vhodně určit hodnoty parametrů \epsilon a $minPts$

DENCLUE
-------
- DENCLUE = DENsity-based CLUstEring
- založené na distribuční funkci pravděpodobnosti
- definuje se tzv. funkce vlivu jako vliv každého objektu na jeho okolí
  (formálně/matematicky dobře popsatelné)

- dokáže nalézt i shluky nekonvexního tvaru
- dobře se vyrovnává se šumem / odlehlými hodnotami
- rychlejší než DBSCAN
- problémem je vhodné nastavení parametrů \sigma, prahu

Metody založené na mřížce
-------------------------
- prostor objektů se rozdělí na konečný počet buněk, které tvoří mřížku
- doba zpracování pak není závislá na počtu objektů, ale na počtu buněk
- metoda WaveCluster (na základě vlnkové transformace)

Metody založené na modelech
---------------------------
    (jenom okrajově...)

Konceptuální shlukování
-----------------------
- hledá klasifikační schéma pro objekty
- hledá charakteristický popis pro každou skupinu
- klasifikační strom / pravděpodobný popis
- metoda COBWEB

Shlukování vysoce-dimenzionálních dat
-------------------------------------
- efektivita klasických shlukovacích metod klesá s rostoucím počtem dimenzí
- používá se redukce počtu dimenzí:
    Metoda transformace rysů
    - nedochází k odstranění atributů
    - rysy je těžké interpretovat

    Metoda CLIQUE (Clustering In QUEst)
    - shlukování od 1D podprostoru směrem k více-dimenzionálním
    - shluky se pak hledají v oblastech, které se prolínají
      (hledají se kandidáti - viz. alg. Apriory)
    - využívá mřížku, hustotu objektů

Analýza odlehlých hodnot
------------------------
- odlehlá hodnota je objekt, který se výrazně liší od ostatních
- používají se metody založené na vzdálenosti/hustotě
- problém s definicí odlehlé hodnoty


Bioinformatika
==============
- mechanismy kódování a sdílení v živých systémech
- všechny žijící organismy jsou schopny uchovávat a předávat životně důležité
  informace (na molekulární úrovni)
- genetický materiál každé buňky (genom) je uložen v DNA

DNA
---
- DNA je nositelem dědičnosti
- uložena v jádru každé buňky
- dvojitá pravotočivá šroubovice
- vlákno je tvořeno sekvencí nukleotidů
- nukleotidy: Adenin(A), Guanin(G), Cytosin(C), Thymin(T)
- nukleotidy se mohou párovat: A-T, C-G (2 nebo 3 vodíkové vazby)
    --> princip komplementarity
- vlákno má dva konce (5' konec, 3' konec), které jsou vždy protilehlé
- druhé vlákno lze odvodit z prvního na základě principu komplementarity

Gen
---
- jednotka dědičnosti
- geny se mohou nacházet na obou vláknech DNA
- soubor všech genů organismu se označuje jako genom
    (lidský genom: 30000 genů, 3*10^9 bází, 23 párů chromosomů)

Exprese genu
------------
- centrální dogma molekulární biologie
- přepis informace na protein (který způsobí nějaký znak
  organismu)
- proces exprese genu spotřebuje buňce nějakou část energie
- dva kroky:
    1. transkripce
    2. translace

    DNA --> transkripce --> RNA --> translace --> protein

RNA
---
- podobné složení jako DNA
- liší se v cukru (ribóza na rozdíl od DNA, kde je deoxy-ribóza)
- vyskytují se báze A, C, G; místo Thyminu je Uracyl
- z pohledu bioinformatiky řetězec nad abecedou {A,C,G,U}
- existují 3 typy: ribozomální, mediátorová, transferová

Transkripce
-----------
- gen je rozdělen do několika úseků (exony)
- jednotlivé úseky jsou odděleny nekódujícími oblastmi (introny)

Translace
---------
- cíl: pořadí nukleotidů v DNA odpovídá pořadí aminokyselin v bílkovinách

Genetický kód
-------------
- tři po sobě jdoucí báze (kodon) --> kód jedné aminokyseliny
- 4 organické báze --> 4^3=64 možných kodonů
- máme ale pouze 20 aminokyselin (jedna aminokyselina může být kódována
  několika způsoby)
- kód je redundantní - některé záměny nukleotidů se neprojeví na výsledném
  složení proteinů
- některé kodony mají speciální význam - start/stop kodony

Proteiny
--------
- stavební funkce (kolagen)
- katalyzátory chemických reakcí (enzymy)
- transport látek v organismu (hemoglobin)
- ... mnoho dalších využití

- podle reakce na vodu se aminokyseliny rozdělují na hydrofobní/hydrofilní


Databáze biologických dat
=========================
- molekulární biologie a genomický výzkum vyžadují práci s obrovským množstvím
  dat
- databáze jsou veřejně přístupné
- primární databáze:
    - databáze sekvencí nukleotidů
    - databáze sekvencí proteinů
    - databáze struktur proteinů
    - genomové databáze
    - databáze s informacemi o expresi genů

- sekundární databáze: informace získané analýzou dat v primárních databázích

Porovnání sekvencí
------------------
- je potřeba vhodně zarovnat a maximalizovat tak počet pozic se shodnými
  symboly
- používá se k detekci vývoje sekvencí v přírodě (mutace, inserce, delece)
- někdy se používá vkládání mezer (odpovídá inserci a deleci)
- řeší se optimalizační problém (hledá se optimální zarovnání)

- počítá se skóre shody/neshody
    - lze jednoduše spočítat shodující se prvky
    - ale je dobré zahrnout do výpočtu skóre nějaké znalosti
    - je třeba upravit při vkládání mezer (další složka výpočtu skóre)

Algoritmus Needleman-Wunsch
---------------------------
- vychází z dynamického programování - rozdělení problému na podproblémy
- hledají se nejlepší zarovnání postupně pro jednotlivé pozice
- používají se tabulky částečného skóre

Zarovnávání skupin sekvencí
---------------------------
- alg. Needleman-Wunsch je pro skupiny výpočetně příliš složitý
- používá se evoluční strom (metoda Clustal)
    - nejprve zarovná dvojice a postupně přidává další sekvence
    - nemusí nalézt úplně nejoptimálnější řešení

- často je potřeba porovnat nějakou sekvenci s celou databází sekvencí
    - využívají se heuristiky, indexy
    - nástroje FASTA, BLAST
    - nemusí nalézt všechny podobné sekvence

BLAST
-----
- BLAST = Basic Local Alignment Search Tool
- nehledá identitu, ale podobnost (na základě hledání podřetězců)

Tvorba evolučních stromů
------------------------
- snaha zachytit evoluci pomocí stromů
- uzly reprezentují abstraktní organizmus, jehož existence se předpokládá,
  a tvoří společného předchůdce svých následníků
- obvykle binární stromy
- využití vzdálenostních matic
- metoda UPGMA

Hledání vzorů v sekvencích
--------------------------
- geny lze popsat gramatikou, ta je ale nejednoznačná a proto se nepoužívá
- používá se pravděpodobnost (skrytý Markovův model)

Předpovídání struktury molekul ze sekvence
------------------------------------------
- snažíme se odhadnout 2D/3D strukturu molekuly
- hledání energetický nejvýhodnějších konfigurací

Predikce struktury proteinu
---------------------------
- běžné metody neumí odhadnout tvar proteinu, který dříve neviděly
- některé metody to umí - např. skládají výsledek ze strukturních fragmentů

Sestavování fragmentů DNA
-------------------------
- není triviální
- převede se na problém hledání nejkratší cesty grafu


Dolování v textu a na webu
==========================
    (Ing. Vladimír Bartík, Ph.D.)

- text ... nestrukturovaná data, problém s nalezením vhodné reprezentace
- charakteristika textových dat z pohledu dolování:
    - vysoká dimenzionalita rysů
    - řídkost rysů (malá podpora vzorů)

- někdy se dají nalézt i náznaky struktury (např. nadpis dokumentu, množina
  klíčových slov, abstrakt, závěr, ...)

- nejčastější rysy textových dokumentů:
    znaky - např. na detekci použitého jazyka

    slova - je jich mnohem více než znaků - je třeba optimalizovat

    termy - slova nebo slovní spojení - vyžaduje slovník

    koncepty - téma dokumentu, synonyma, ...

Text jako množina slov
----------------------
- máme informaci o četnosti slov v dokumentech
- ztrácí se informace o pořadí slov (sémantika dokumentu, kontext)
    --> vedlo ke vzniku NLP (Natural Language Processing)

Zpracování přirozeného jazyka (NLP)
-----------------------------------
- původní přístup:
    1. lexikální analýza
    2. syntaktická analýza
    3. sémantická analýza

- problém s dvojznačností:
    - na úrovni slov
    - syntaktická dvojznačnost
      (např. samotný pojem NLP je nejednoznačný)

- důležitý je kontext (který může dokonce ležet mimo samotný dokument)

Vyřešené NLP problémy
---------------------
- lze stáhnout anglický lexikon (WordNet)
- lze detekovat fráze (na základě syntaktických stromů a pravděpodobnosti)

- složitější je odstranění dvojznačnosti (většina anglických slov má více
  významů)
- ontologie (např. WordNet - viz. ^)

Předzpracování textových dokumentů
----------------------------------
- k nestrukturovaným dokumentům je potřeba přidat strukturovanou informaci
- kategorizace (tagging) - lze provádět ručně
- extrakce informace - strojová kategorizace dokumentů

Vyhledávání informací
---------------------
- tyto dva pojmy se pletou
    information extraction - převod nestrukturované inf. na strukturovanou
    information retrivial - vyhledání informace (souvisí s DB systémy)

Měřením úspěšnosti vyhledávání
------------------------------
- používají se dvě základní metriky:
    1. přesnost - procento nalezených dokumentů, které odpovídají zadanému
                  dotazu
    2. úplnost - procento skutečně nalezených dokumentů ze všech relevantních

Techniky vyhledávání informací
------------------------------
- dokument je popsán množinou reprezentativních klíčových slov
  (tzv. index terms)
- různé index termy mají různou důležitost (přiřazují se váhy)
- používá se seznam "stop slov" - častá slova (např. spojky)

Vyhledávání založené na podobnosti
----------------------------------
- použití stop-listu je nutné
- používají se kořeny slov (stemming)
- používá se frekvenční tabulka

Invertovaný index
-----------------
- používají se dvě indexovací tabulky (strom nebo hash)
    1. tabulka dokumentů
    2. tabulka termů

Vector space model
------------------
- stupeň podobnosti dokumentu je vypočten jako korelace mezi vektory
- používá se Cosinova / Euklidova vzdálenost

LSI = Latent Semantic Indexing
------------------------------
- hledání skryté sémantiky
- snaha vyřešit problém víceznačnosti

Metody dolování v textu
=======================

Asociační analýza založená na klíčových slovech
-----------------------------------------------
- nalezení slov, které se vyskytují často společně
  (a najít mezi nimi asociace/korelace)
- lze použít Apriori alg., ale často se používá jeho modifikace:
    Multipass-Apriori
    - k rozdělení dojde o jeden krok dále (moc jsem nepochopil)
    - ušetří spoustu času

Klasifikace textu
=================
- rozdělení dokumentů do kategorií podle tématu
- TODO