Rozdělování dat do trénovacích a testovacích množin Marcel Jiřina Rozpoznávání je důležitou metodou při zpracování reálných úloh. Rozpoznávání je definováno dvěma kroky a to pořízením dat o reálném rozpoznávaném objektu a jeho následná klasifikace. Pořízení dat je problematikou samo o sobě a je úzce svázáno s rozlišovací úrovní. V každém případě získaná data obsahují jen část informace, kterou objekt představuje. Klasifikace, která je druhým krokem v úloze rozpoznávání, představuje proces zatřiďování objektů do tříd. Objekty jsou v tomto případě popsány příznaky, které tvoří tzv. příznakový vektor ´, který také označujeme jako vzor. V případě, kdy řešíme klasifikační úlohu, je potřeba získat k daným vzorům i odpovídající informaci o třídě – identifikátor. Pokud máme naměřena data a zpracovány příznaky resp. vzory, stojíme před úlohou jak nastavit klasifikátor, abychom dosáhli úspěšné klasifikace. V zásadě existují dva možné přístupy. Jedním z nich je nastavit klasifikátor na základě analýzy problému přímo tím, kdo úlohu řeší. Druhý přístup je využít přímo dostupná data o objektech a na jejich základě klasifikátor nastavit. Existuje celá řada klasifikačních algoritmů. Mohli bychom je rozdělit na dvě skupiny. Na ty, co klasifikují podle minimální vzdálenosti a ty, které klasifikují podle nejmenší chyby. Příkladem první skupiny je např. lineární klasifikátor nebo metoda k-nejbližších sousedů. Příkladem druhé skupiny je např. tzv. Bayesův klasifikátor založený na Bayesově vztahu. Specifikace problému Zaměřme se blíže na nastavování klasifikátorů, které je založeno na využití naměřených datech o objektech. Předpokládejme, že jsme naměřili data, ty zpracovali na příznaky, z nich sestavili příznakové vektory – vzory a tyto vzory máme následně k dispozici v podobě tabulky, kde řádky představují jednotlivé vzory a sloupce jednotlivé příznaky doplněné o informaci o třídě, kam daný objekt popsaný vzorem zařadit. Základním krokem, který je potřeba provést, je rozdělení dat do trénovací a testovací množiny. Často bývá tento krok doplněn o rozdělení vzorů ještě do tzv. validační množiny. Doporučené a nejčastěji používané rozdělení je v poměru 2:1:1. Trénovací množina slouží k nastavení, tzv. trénování, klasifikátoru a testovací množina k otestování, jak úspěšně byl klasifikátor nastaven (natrénován). Validační množina slouží k zabránění přeučení (overfittingu) klasifikátoru. Pro naše úvahy se omezme pouze na případ, kdy rozdělujeme data do dvou množin a to do trénovací a testovací množiny. Zobecnění úlohy pro validační množinu je pak jednoduché. Všeobecně rozšířeným způsobem rozdělovaní dat do množin je náhodný výběr z dostupné množiny vzorů. Nejčastěji bez opakování, ale je možné toto rozdělení provést i s opakováním. V takovém případě se tento proces v anglické literatuře označuje pojmem bootstrapping (vzorkování s opakováním). V množinách se tedy může vyskytovat více stejných vzorů a součet všech vzorů v trénovací a testovací množině je tak vyšší než celkový počet dostupných vzorů. Náhodný výběr, který se používá, je přirozeným způsobem jak rozdělit data. Zdá se být i spravedlivý. Pokud bude vzorkování rovnoměrné a vzorů bude dostatek, pak je velká šance, že budou vzory rozděleny do množin tak, aby nesly stejný díl informace, která je důležitá pro správné nastavení klasifikátoru. Spoléháme tedy na zákon velkých čísel. V každém případě se může ale stát, že toto rozdělení nebude ideální a je to navíc bohužel
velmi pravděpodobné. Nejistota je tak dána stochastickým přístupem k rozdělování vzorů. Zřejmou výhodou je, že tento přístup má přirozené opodstatnění a je dobře statisticky podchycen. Je ovšem lákavé zvolit jiný přístup, který by byl deterministický a přesto by byl funkční a plně ospravedlnitelný. Rozdělování vzorů Nejprve uvažme následující případ. Máme množinu vzorů, která je sestavena ze vzorů, které patří do dvou tříd. Vzory první třídy jsou uspořádány do prstence. Vzory druhé třídy jsou uspořádány vně tohoto prstence s tím, že dva vzory se nacházejí uvnitř prstence, viz obrázek níže.
Příklad rozložení vzorů dvou tříd Připusťme, že budeme tuto množinu vzorů rozdělovat do dvou množin, trénovací a testovací, ve stejném poměru a pomocí náhodného výběru. Vzory z prstence i vzory vně tohoto prstence si podle všeho zachovají zhruba stejný tvar, tj. výběr vzorů bude celkem spravedlivý. Podívejme se ale podrobněji na dva vzory uvnitř prstence. Při náhodném výběru mohou nastat čtyři možné situace: oba vzory budou zařazeny do jedné nebo druhé třídy nebo jeden vzor bude zařazen do jedné třídy a druhý do druhé resp. naopak. Pravděpodobnost, že jeden vzor bude zařazen do jedné třídy a druhý do druhé je jen ½. Tento případ je ale žádoucí. Důvodem je, že chceme, aby v trénovací množině byly zařazeny vzory, na kterých se může klasifikátor natrénovat a být tedy schopen správně klasifikovat vzory z testovací množiny. Pokud tento případ nenastane, nemá klasifikátor možnost podchytit tyto případy a jeho klasifikační schopnost může klesnout. Uvažme následující algoritmus rozdělování vzorů do dvou množit ve stejném poměru. Navíc uvažujme pouze jednu třídu dat. Pro druhou množinu je algoritmus stejný. Nejprve vezmeme všechny dostupné vzory a najdeme takové dvojice vzorů, aby součet vzdáleností všech dvojic vzorů byl minimální. Toto rozdělení považujeme za optimální. Pokud by se nám to podařilo, můžeme nyní rozdělit dvojice vzorů tak, aby se do jedné množiny dostal jeden vzor a do druhé množiny druhý vzor. Je otázkou jaký vzor z dvojice dát do které množiny. Tím, že jsou vzory blízko sebe, není tato otázka kritická a rozdělení můžeme provést např. náhodně.
Pokud se podíváme na obě množiny takto rozdělených vzorů vidíme, že obě množiny si jsou velmi podobné. To je tedy dobrým předpokladem pro následné úspěšné natrénování klasifikátoru. Výše jsme uvedli příklad, kdy jsme měli dva vzory uvnitř prstence. V případě popsaného algoritmu máme zajištěno, že se jeden vzor dostane do trénovací množiny a druhý vzor do testovací množiny. Pokud se zamyslíme nad kritériem optimality rozdělení vzorů, které jsme zavedli výše, je úloha nalezení optimálního nalezení dvojit vzorů časově velmi náročná. Měli bychom vlastně vyzkoušet všechny kombinace dvojic vzorů a z nich vybrat tu optimální. To ale povede na exponenciální složitost a tedy tento algoritmus je kandidátem na NP-úplnou úlohu. Z tohoto důvodu je účelné se zamýšlet nad vhodnými heuristikami, které by se optimálnímu rozdělení blížili, ale současně by byly výpočetně zvládnutelné. Dále uvedeme dvě možné jednoduché heuristiky, ale nabízí se řada dalších. Heuristiky pro rozdělování vzorů První heuristika, kterou zde uvedeme, je pravděpodobně nejpřímějším řešením problému rozdělování vzorů. Její princip je následující: Vyberme libovolný vzor a k němu najděme nejbližšího souseda, se kterým vytvoříme dvojici. Tyto vzory nově zařadíme do trénovací a testovací množiny a celý proces opakujme. Je zřejmé, že tato heuristika není příliš kvalitní. Lze předpokládat, a obrázek níže to potvrzuje, že ze začátku vybíráme dvojice, které si jsou blízké, ale s postupem času se díky vyřazování vzorů vzdálenosti mezi nejbližšími sousedy prodlužují. Ke konci je tento jev mimořádně výrazný. Na druhou stranu je tato heuristika v průměru stále úspěšnější než náhodné rozdělní vzorů a je navíc rychlá. Poznamenejme, že se bohužel může stát i to, že vzory, které jsou blízko sebe a současně oba vzdáleny mimo hlavní skupinu, viz příklad výše, vzorů mohou být rozděleny nevhodně. Je to dáno tím, že tyto vzory mohou zůstat nevybrány téměř až do konce celého rozdělovacího procesu a potom se stanou nejbližšími kandidáty pro jiné vzory.
Závislost vzdálenosti dvou nejbližších vzorů na počtu iterací pro první heuristiku Variantou k uvedené heuristice je, že zpětně ověříme, zda pro druhý vzor je první vzor také nejbližší.
Další heuristika sleduje podobnou myšlenku jako v prvním případě, s tím rozdílem, že v každém kroku nevezmeme libovolný vzor a k němu nejbližší vzor, ale vytvoříme nejbližší dvojice ze všech libovolně vybraných vzorů, ze kterých následně vybereme tu dvojici vzorů, které mají mezi sebou nejmenší vzdálenost. Ani tento algoritmus není optimální a navíc je časově náročnější než předchozí, ale opět mírně zlepšuje kvalitu rozdělení vzorů, viz obrázek níže.
Závislost vzdálenosti dvou nejbližších vzorů na počtu iterací pro druhou heuristiku Diskuze Vzniká důležitá otázka, zda navrhované rozdělení je opravdu možné, resp. obhajitelné. Tím, že celý proces je daleko systematičtější než prostý náhodný výběr, mohou vzniknout dohady, zda tento přístup lze opravdu použít. Vyjděme z předpokladu, že dostupná data, která uvažujeme v klasifikační úloze jsou dostatečně reprezentativní. Už jen pojem „dostatečně reprezentativní“ zaslouží zpřesnění. Tímto pojmem se obecně rozumí, že daná data zachycují veškerou informaci, kterou může měřený systém vygenerovat a nelze s jinými, dále naměřenými, daty získat novou informaci, která by mohla kvalitu klasifikace ovlivnit. Je to předpoklad, který nemusí být v praxi vždy splněn. Protože proces primárního pořízení dat neovlivníme, můžeme vzhledem k naší úloze předpokládat, že data, se kterými pracujeme, jsou dostatečně reprezentativní. Za uvedeného předpokladu pracujeme s daty, která obsahují nosnou informaci. Tím, že data budeme rozdělovat do dvou množin, na trénovací a testovací, může dojít ke ztrátě informace. Pokud data nebudou obsahovat redundantní informaci, jakékoliv rozdělení původních dat nutně povede ke ztrátě informace a tedy i úspěšné natrénování klasifikátoru nemusí být možné. Pokud budeme předpokládat, že podobnost vzorů je dána jejich vzdáleností, a tedy že dva sobě blízké vzory nesou přibližně stejnou informaci, je navržené rozdělení ospravedlnitelné. Daným rozdělením zaručíme, že v obou množinách je obsažena téměř stejná informace. Poděkování
Problematika uvedená v tomto příspěvku je řešena v rámci projektu Transdisciplinární výzkum v oblasti biomedicínského inženýrství II, MSM6840770012. Literatura [1] Kotek, Z., Vysoký, P., Zdráhal, Z.: Kybernetika. SNTL, 1990 [2] Mařík, V., Štěpánková, O., Lažanský, J. a kol.: Umělá inteligence (1), Academia, Praha 1993
