logo-IBA logo-MU
© Institut biostatistiky a analýz
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
logo-MU
ANALÝZA A KLASIFIKACE DAT
prof. Ing. Jiří Holčík, CSc.

logo-IBA logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ POPIS
þrelační struktura je vytvořena z určitých elementárních popisných částí dat, tzv. primitiv a
vzájemných vztahů mezi nimi – relacemi; þrelační struktury zpravidla vyjadřujeme pomocí grafů;

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ POPIS
001.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ POPIS
003.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
TYPY RELAČNÍCH STRUKTUR
þřetězce (uvuuyzuvw)
þpole (především pro reprezentaci 2D obrazů) þstromy (relační struktura neobsahující cykly a
paralelní cesty)
þobecné grafy

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ POPIS
002.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ POPIS
005.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
KOMBINOVANÝ STRUKTURÁLNÍ POPIS
004.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REPREZENTACE KLASIFIKAČNÍ TŘÍDY
þvýčtem relačních struktur
þ (může být bohužel velký až nekonečný)

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REPREZENTACE KLASIFIKAČNÍ TŘÍDY
þvýčtem relačních struktur
þ (může být bohužel velký až nekonečný)
þgenerátorem relačních struktur – gramatika
èGramatika je čtveřice G = (Vn, Vt, P, S), kde Vn a Vt jsou konečné disjunktní množiny (abecedy),
přičemž prvky množiny Vn  nazývají neterminální pomocné symboly a prvky Vt  terminální symboly, S Î
Vn je tzv. axiom gramatiky nebo také počáteční symbol a P je množina substitučních pravidel tvaru
a®b, které definují způsob náhrady dílčí relační struktury a novou strukturou b.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REPREZENTACE KLASIFIKAČNÍ TŘÍDY
þvýčtem relačních struktur
þ (může být bohužel velký až nekonečný)
þgenerátorem relačních struktur – gramatika
èPříklad gramatiky:
è G = ((A,B), (0,1), P, A), P = (A ® 0B1, 0B®00B, B ® „e“).
èPříklad generování řetezce:
èA ® 0B1 ® 00B1 ® 000B1 ® 0001
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REPREZENTACE KLASIFIKAČNÍ TŘÍDY
þvýčtem relačních struktur
þ (může být bohužel velký až nekonečný)
þgenerátorem relačních struktur – gramatika
þpříjemcem relačních struktur – automat
èrůzné typy automatů podle charakteru relační struktury a substitučních pravidel – nejjednodušší
konečný automat
èKonečný stavový automat A je pětice A = (X, S, s0, Sc, Ꮄ), kde X je konečná vstupní abeceda, S je
množina vnitřních stavů, s0 je počáteční stav automatu, Sc je množina cílových stavů automatu a Ꮄ:
X x S ® S je přechodová funkce.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REPREZENTACE KLASIFIKAČNÍ TŘÍDY
þvýčtem relačních struktur
þ (může být bohužel velký až nekonečný)
þgenerátorem relačních struktur – gramatika
þpříjemcem relačních struktur – automat
èPříklad konečného stavového automatu
001.jpg 002.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REPREZENTACE KLASIFIKAČNÍ TŘÍDY
þvýčtem relačních struktur
þ (může být bohužel velký až nekonečný)
þgenerátorem relačních struktur – gramatika
þpříjemcem relačních struktur – automat
þekvivalence gramatiky a automatu – gramatika a automat jsou ekvivalentní, pokud množina relačních
struktur generovaná gramatikou a množina akceptovaná automatem jsou stejné

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE
þnedeformované relační struktury
þztotožnění s reprezentativními relačními strukturami;
þpřijetí automatem

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE
þdeformované relační struktury
003.jpg 004.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ POPIS
001.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE
þdeformované relační struktury
þpodle vzdálenosti od etalonu
þ
þjak vzdálenost určíme?

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE
þdeformované relační struktury
þpodle vzdálenosti od etalonu
þ
þjak vzdálenost určíme?
þ
þvzdálenost vs. metrika
þ?

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
METRIKA - VZDÁLENOST
þMetrika ρ na X je funkce ρ: X × X ® R, kde R je množina reálných čísel, taková, že:
þ$ρ0ÎR: -¥ < ρ0 £ ρ(x,y) < +¥, "x,y Î X
þρ(x,x) = ρ0, "x Î X
þa
þρ(x,y) = ρ(y,x), "x,y Î X. (symetrie)
þKdyž dále
þρ(x, y) = ρ0 když a jen když x = y (totožnost)
èa ρ(x, z) £ ρ(x, y) + ρ(y, z), "x,y,z Î X. (D nerovnost)
þ
þProstor X, ve kterém metrika ρ definována, nazýváme metrickým prostorem.
þVzdálenost je hodnota určená podle metriky.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
METRIKA PODOBNOSTI - PODOBNOST
þMetrická míra podobnosti s na X je funkce s: X × X ® R, kde R je množina reálných čísel, taková,
že:
þ$s0ÎR: -¥ < s(x,y) £ s0< +¥, "x,y Î X
þs(x,x) = s0, "x Î X
þa
þs(x,y) = s(y,x), "x,y Î X. (symetrie)
þKdyž dále
þs(x,y) = s0 když a jen když x = y (totožnost)
èa s(x,y).s(y,z) £ [s(x,y) + s(y,z)].s(x,z), "x,y,z Î X.
è(D nerovnost ?)

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ VZDÁLENOST
þV případě řetězců lze deformační vlivy vyjádřit (na úrovni primitiv) trojicí tzv. elementárních
deformačních transformací – eliminací, substitucí a inzercí
005.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VÁHOVANÁ LEVENŠTEJNOVA METRIKA
006.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VÁHOVANÁ LEVENŠTEJNOVA METRIKA
007.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DALŠÍ STRUKTURÁLNÍ METRIKY
þřetězce
èprostá (neváhovaná) Levenštejnova metrika
èHammingova metrika
þstromy
þ :
þ :
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
KLASIFIKACE DEFORMOVANÝCH STRUKTUR
þvýpočet vzdálenosti mezi reprezentativními strukturami (etalony) klasifikační třídy a
klasifikovanou strukturou; þzačlenění deformačních pravidel do substitučních pravidel gramatiky
(resp. automatu);

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
002.jpg
VYTVOŘENÍ STRUKTURÁLNÍHO ETALONU MNOŽINY PÍSMEN

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VYTVOŘENÍ STRUKTURÁLNÍHO ETALONU MNOŽINY PÍSMEN
001.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
SHRNUTÍ – POKUD MOŽNO CO NEJOBECNĚJI
þzákladní klasifikační úloha je zatřídit (z hlediska prostoru i času) (matematický, abstraktní)
popis daného klasifikovaného objektu do odpovídající třídy/kategorie;
þděje se to na základě klasifikačního pravidla, pomocí kterého je definována klasifikační třída;
þklasifikační třída může být definována:
èvýčtem prvků do ní patřících;
èvzdáleností/podobností (od) vzorů té které třídy;
èhranicemi, vymezujícími prostor dané třídy.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE
þDALŠÍ PŘÍKLAD ZE ŽIVOTA

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ
001.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
002.jpg
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
003.jpg
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ
index
řetězec
četnost výskytu
index
řetězec
četnost výskytu
1
ABCJEF
6
10
ABCDDEL
1
2
ABCJE
3
11
ACJE
1
3
ACJEFF
1
12
ACDJE
1
4
GBCDDEF
3
13
ABCJFF
1
5
AIDDE
2
14
ABIDDF
2
6
GBCDDE
1
15
ACDDK
1
7
ABCJ
2
16
ABCDDKF
1
8
ACJEF
2
17
9
ABCJF
1

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
005.jpg
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
006.jpg
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
007.jpg
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ
Minimální kostra (minimum spanning tree) je
graf, který spojuje všechny objekty tak, že se zde nevyskytují žádné smyčky a zároveň součet délky
spojnic mezi uzly (objekty) je minimální

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
008.jpg
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
STRUKTURÁLNÍ KLASIFIKACE AKUSTICKY EVOKOVANÝCH KMENOVÝCH POTENCIÁLŮ
þetalonové řetězce pro jednotlivé shluky určené iteračními algoritmy jsou:
þ
Ia
ABCJEF
Va
ACDDK
Ib
ABCJEF
IIa
ACJEF
VIa
ABIDDF
IIb
ACDDE
IIIa
AIDDE
VIIa
GBCDDEF
IIIb
ABCDDE
IVa
GCDDF

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þPříprava nových učebních materiálů
þoboru Matematická biologie
þje podporována projektem ESF
þč. CZ.1.07/2.2.00/07.0318
þ„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
logo-MU