No title

Recenzenti: prof. Ing. JosefPsutka, CSc. prof. Ing. Petr VavŤín,DrSc.

pracoviště Na frontispisuvidímepohleddo experimentálního KatedrykybernetikyČvUT FEL, pŤedstavující EU-projektCLoPEMA, na němždvojruk! robotprávěŤeší rjlohuskládáníoděvu

Kniha Yznikla a byla vydána s finančnípomocí těchto grantú a vfzkumnfch

ríko|ri:

MsM 6840770038: Rozhodování aÍizeni pro prumyslovou v}írobuIII (2007_2011' MSM) (kapitoly1, 2, 3,5, 7, 8) Projekt RA-DIC financovany firmou Rockwell Automation (kapitoly 2, 5) GAČR P202l|0l0761: Sémantizacewebu (kapitoly 2,6) GAČR P2o2l|0l1825: PatoMat - Automatizace detekce avyuživání návrhov:/ch vzoru v ontologiích(kapitola4) GAČR 103/10/1875:Učeníse zteoní (kapitola 9) GAČR |03ll|l2L70: Pievod ILP technik do statistickéhorelačníhoučení(kapitola 9) MsM 6138439910 (MŠMT ČR, Vfzkumn! záměr): Metody získávání znalostí z dat ajejich využitív ekonomickémrozhodování(kapitola l0) GAČR 20|10810802: Aplikace metod znalostního inženfrství v dob;fvání znalostí (kapitoly10, ll) GAČR P2o2|t0ll333: NoSCoM: nestandardnívypočetnímodely a jejich aplikace ve sloŽitosti,lingvistice a učení(kapitola l2) 1ET100300517 (AV ČR, Program Informačníspolečnost):Metody inteligentníchSystém znalostía zpracovánípĚirozenéhojazyka(kapitola l2) ajejich aplikace pŤidob;Ívání GAČR l02|08lo593: Modelování BTF textur (kapitola l3) měŤenívzhledu materiálrj(kapitola 13) GAČR 103/11/0335:PŤesné GAČR P403l12l1557: Pfistupy k identifikaci faktoru v;/konnosti podnikri s d razem na metody vlběru pŤíznakrive statistickémrozpoznávání (kapitola l3) MŠMT č.1M0572: DAR: Data *Algoritmy - Rozhodování(kapitola 13)

měIá inteligence (6) AC ADEMIA PRAHA 2013

/ ť ď,.

ť'

Y

r'l,tN \.,'ť

q.f [Jw

ťŇq-N \ ř

0\

vo

N*\uN' \\

AUToRSI.Ý KoLEKTIV

KATALoGZACEV

KNIZE - NÁRoDNÍ KNIHoVNA

ČR

Mďík, Vladimír Umělá inteligence. (6) / Vladimír Mďík, olga Štěpánková,JiŤí Lažans$ a kolektiv. - Vyd. 1' - Praha : Academia,2013. - 490 s. : it. ISBN 80-200-0502-1 (soubor). - ISBN 978-80-2M-2276-9 (vin.) 004.8 * 004.891:004.41* 004.62* 004.8:111.1* 004.738.52:C04.822 - umělá inteligence - znalostní inŽenlrství - zpracování dat - ontologie (informatika) - sémantic$ web . kolektivní monografie

prof. Ing. Petr Berka, CSc' berka@)vse'cz

VŠEv Praze'Fakultainformatiky a statistikY Nám. W. Churchilla4, |30 6.|Praha3

Ing. JiÍí Kléma' Ph.D. [email protected]' cz

Čvur v Praze,Fakultaelektrotechnická Technická2. |66 2,7Praha6

Ing. Zdeněk Kouba, CSc. [email protected]. cvut.cz

Čwr y Praze,Fakultaelektrotechnická Technická2, |66 2,7Praha6

tng. Petr KÍemen' Ph.D. [email protected]'cz

Čvur v Praze,Fakultaelektrotechnická Technická2, |66 27 Praha6

Ing. Martin Labskf' Ph.D. [email protected]

VŠEv Praze,Fakultainformatiky a statistiky Nám. W. Churchilla4, |30 67 Praha3

prof. Ing. Vladimír MaŤík' DrSc. [email protected]. cvut.cz

Čvur v Praze,Fakultaelektrotechnická Technická2,166 27 Praha6

doc. Rl[Dr. Jana Novovičová' CSc. [email protected]

republiky Akademievěd České Ústav teorieinformacea automatizace věží4, l82 08 Praha8 Pod vodárenskou

Ing. Marek Obitko, Ph.D. [email protected]

Rockwell AutomationResearchCentre Pekďská 695l|0a,l55 00 Praha5

Prof. Ing. Pavel Pudil, DrSc. [email protected]

VŠBv Praze,Fakultamanagementu Jarošovská| | |7 lII',377 0| JindŤichťrv Hradec

Prof. RI\Dr. Jan Rauch. CSc. [email protected]

VŠBv Praze,Fakultainformatiky a statistiky Nám' W. Churchilla4' |30 67 Praha3

RNOr. Petr Somol, Ph.D. [email protected]

republiky Akademievěd České a automatizace informace Ústav teorie 182 08 Praha8 4, věží Pod vodárenskou

004.8 - Umělá inteligence [23]

@ VladimírMďík, olga Štěpránková, JiŤíLažanslcja kol., 20l3 rsBN 978-80-200-2276_9 ISBN 80-200-0502I (soubor) ISBN 80-200-0469-3 (l. díl) ISBN 80-200-0504-8 (2. díl) ISBN 80-200-0472-6 (3. dit) ISBN 80-200-1044-0 (4. díl) ISBN 978-80-200-l470-2 (5.díl)

427 pod|eznalostiproblému.'..,,,.......,..... l 3.3.3 Volba metodvlběru pŤíznakri .......428 l3.4 optimálnívyh|edávacímetody 1 3 . 4 . | Z á k | a d npi o j m ya v a r i a n t ya l g o r i t m uv ě t v ía m e z í . ' . . . . . . . . .' . '.. ' . ' . , . , . , 4 2 9 ....... l 3 . 4 . 2 N e v l h o d y t r a d i č n í cahl g o r i t m tvi ě t v ía m e z í' . . . ' . . . . . . . ' . . . . . . . . . . . . .4. .3. 0 .....43,| algoritmu..' 13.4.3 Vylepšení,,vylepšeného.. . , ' . ' . . . ' . ' . ' . ' . ' . '4. 3' .4' l 3 . 4 . 4 R y c h l 1 ai l g o r i t m u vs ě t v ía m e z í . ' . , . , . , . , . , . predikce ....'..438 l3'4.5 NovévlastnostialgoritmrivyuŽívajících 13.4.5.lSpecifickévlastnostirychléhoalgoritmuvětvía mezí.'......438 .,.,.'.,.,'..439 l3.4.6 Experimentysoptimálnímv1iběrempňíznakri ''.,.,.,....439 experimenty. 13.4.6.1 Syntetické 44lr ,,,.,.,,'....'..'.'' 13.4.6.2Experimentyna reá|nychdatech , . , . , . , . ,4. 4, 3 h e t o d. .' .' . . '.. . | 3. 4 . 1 S h r n u t ío p t i m á l n í c m .......................444 í etody l 3 . 5 S u b o p t i m á l nvíy h l e d á v a cm ,,.,,,.,...'.,.,445 l 3 . 5 . 1 I n d i v i d u á l nn ě e j l e p špíŤ i z n a k y ,.,.,.445 | 3 . 5 . 2 S e k v e n č nvíy h l e d á v á n í ,.,.,.,.,',',.,.,.,.,.,.446 l 3 . 5 . 3 N e j j e d n o d u šsšeík v e n č nqí| b ě r . . . ' . . . ' . ' . . plovoucívyhledávání. .'.'.'.'.'.'447 |3'5.4 Sekvenční ..'.........448 l 3 ' 5 . 5 D a l š í r o z v opj r i n c i p up l o v o u c í h voy h l e d á v á n í . . ' . ' . ' . ' ' .4. '4 8 l 3 . 5 . 6 o s c i l a č nví y h l e d á v á n í . . . . . . . . . . . . . . . . porovnáníd-parametrizovan ch metod.............'...'.45 l 13'5.7 Experimentální vyhledávání. .....453 l 3.6 optima|izacevelikostipodmnoŽiny- dynamickéoscilační porovnáníd-optima|izujících metod..'.'.'...'.'.'.'.'.'.'.454 13.6.l Experimentální ....455 1 3 . 7 H y b r i d n ía l g o r i t m y ' '''.'.'.''.'..'....' 457 l3.8 V;fběrpŤíznakri za|oženyna modelusměsi hustot . . . . . . .4. .5 8 l 3 . 8 'l K o n e č n ás m ě sh u s t o tp r a v d ě p o d o b n o s. .t .i . . . . .'..' . l 3 . 8 ' 2 M o d i f i k o v a n ák o n e č n sá m ě ss o u č i n o v y ckho m p o n e n t . . . . . . . . . . . . . . . . . . . . . 4 5 8 pŤiuŽitísměsovéhomodelu.................460 l3.8.3 Míry vyznamnostipŤíznakri pravidlaa souhm vlastností l3.8.4 odvozenírozhodovacího pŤístupu........ ..,.460 směsového ...'.'.'..,,,.,461 1 3 . 8 . 5 E x p e r i m e nnt a r e á l n 1 i c dh a t e c h .,.,.,461 l3.9 ProblémpŤeučení a prob|émstabilityvj'běrupŤíznakri'.'.'.' .'.,.,.,.,462 13.9.l Problémstabilityvlběru pŤíznakri .'.'.'.'.'.'.'.,462 l 3 . 9 . 2 V y b r a n ém í r ys t a b i l i t yv f b ě r u p Ť í z n a k r i . . . . . . . 1 3 . 9 ' 3 E x p e r i m e n t ys m í r a m i s t a b i l i t y ,,,.,..'.'.'.'.465 13.10Shrnutíadalšív1/voj .,.,.,.,.,.,.',.,,'',''466 Literatura ........468 C e s k o - a n g l i c k ys l o v n í k

.......'....472

A n g l i c k o - č e s k syl o v n í k . . . .

,.,..,..479

ReistŤík........

.........486

13 Moderní metody vyběru pĚíznakri ve statistickémr ozpoznáv ání

13.1 Úvod C)bor rozpoznávání obraz či prostě rozpoznávání mriže byt s určitym zjednodušením charakterizovánjako Ťešení problémuklasifikace či reprezentacedat popisujícíchzkou. mané objekty reálného světa pomocí vektoru pŤíznaku.Redukce dimenzionality (dimensiona|ityreduction DR) je prováděna buď v podobě extrakce,nebo selekce (Úběru) pŤíznakri,která optimalizuje nějakévhodnékritérium. Yyběr pÍíznakrije jedním z klíčov ch postupťrpŤedzpracovánídat používanypŤiŤešení nejruznějšíchriloh ve statistickém rozpoznávání, strojovém učení,zpracování obrazové informace, klasifikaci dokument , dob;Íváníznalostí z rozsáh|ych databázi atd. Smyslem redukce dimenzionality je nejen ušetŤitčasa prostor vyÍazenímnepodstatn ch částídat, ale i zlepšit rispěšnostklasiflrkace či pňesnostreprezentacedat v budovanémsystémupotlačenímvlivu šumov ch čijinak neinformativních pŤíznakri.

13.2.1 Redukce dimenzionality podle charakteru vfslednfch pĚíznakŮ Z praktich.fch drivodri rozlišujeme dva zríkladnípŤístupyk DR: - redukci áímenzionality pomocí extrakce pŤímakri(feature extraction, FE), - redukci dimenzionality pomocí vyběru pŤíznakri(feature selection, FS). Extrakcí pžíznak rozumíme proces' pŤi němž je vfsledn;Í vektor získán jakoukoliv transformací z vektoru privodního. Vysledné pÍiznaky proto mohou reprezentovat kombinaci informace všech privodních pŤíznakria mohou byt zce|a odlišně inte1pretovatelné' V!,běrempŤíznakúrozumíme speciální pŤípadextrakce, kdy je jednoduše vybrána podmnožina privodních pŤíznakri.Ačkoliv extrakce v obecnosti umožřuje pŤesnějšíreprezentaci dat v podprostoru' v'j'běr bfvá častoupŤednostněnz praktick;Íchdrivodri. Je jednodušší,zachovává privodní vyznam a interpretovatelnost měŤenía umožřuje írspory nákladú pŤi akvizici dat (napŤ' v medicíně je vhodné rozeznat, která měŤenínetŤeba u pacientu nadále provádět, anižby se zhoršila spěšnostautomatickéhodiagnostického systému).V dalšímvykladu se zaměŤímevyhradně na problém ui,běrupŤíznakň. 13.2.2 Redukce dimenzionality podle cíle k redukci dimenzionality podle cíle: Alternativně lze rozlišitdva pŤístupy - redukci dimenzionality pro optimální reprezentaci dat, - redukci dimenzionality pro klasifikaci. V prvním pŤípaděje cílem co nejlépe zachovat v méněrozměmém prostoru informaje cílem maximalizovat rozlišitelci obsaŽenouv privodníchdatech.V druhémpŤípadě tŤíd. nost ruzn;/ch

A'

13.2 Redukce dimenzionality Termínem,,obraz,,budeme omačovat D-ronněmy reáln vektor X : (xt,.,,,xp) e X c RD, jehož prvky jsou měŤeníodpovídajícívlastnostemreprezentovaného objektu. Vektor x budeme rovněž nazyvat vektorem pŤíznaku.PŤíznakyjsou veličiny specifikované pro dan;1iprob|ém odborníkem. Na počátku specifikované pŤíznakyby měly pokryt maximum zjistitelné informace o uvažovanych objektech - moŽnou nadbyečnou informaci lze dodatečněredukovat pomocí metod popisovan ch v tétokapitole. Informaci od počátkuchybějícívšak nahradit nelze. Ve většině praktick1ich loh proto očekávámevysokou vstupnídimenzionalitu. V kontextu statistickéhorozpoznávání nejčastějipŤedpokládáme,že objekt reprezentovan obrazem x mábyt klasifikován do jednéz konečného počtuC ruznych tÍido: @g} . obraz x e patŤící X povaŽujem do tŤídy rr;; za e realizaci náhodnéhovektoru {at,..., vybranou náhodně v souladu s apriomími pravděpodobnostmi P(al) a podmíněnjmi hustotami pravděpodobnostip(x|a,ri),{Di e d). Smys|em redukce dimenzionality je tedy na|ézatautomaticky d noqfch pŤíznakrina základě vstupních D měŤení(pokud možno d <
-A

rF \gt

^r .

t

^L.

A

. , ..,.o -o,

,+n(

21

obr. 13.l Redukce dimenzionality pro optimálnj reprezentaci dat nemusí by't optimální pro rozli-

Na obrázku 13.1ilustnrjeme,ževlsledek DR pro optimálníreprezentacidat nemusí vzorky dvou ruznfch byt vhodn! pro rozlišenítŤíd.Kolečkáa trojrihelnikyréprezentují tŤídv dvojroaněmémprostoru.Aplikujeme-li na tentopŤíkladmetoduhlavníchkomponent- principalcomponentanalysis,PCA,viz napf.(nuda a kol.,2000),budoudata prostoruoptimálněreprezentována osouE1. Tato metodaDR vhoona v jednoiozměrném není vhodná pro pro odlišenítŤídje v tomto Řlasifikaci, neboť však pro reprezentaci E2. osa pŤípadě optimální pŤedevším na problémklasifikace.Pro tentoÚěe||ze V dalšímtextu se soustŤedíme on oÁujaet lokalně,tj. pro každoujednotlivoutiíduzvlášť,neboglobálná, tj. společně