České vysoké učeńı technické v PrazeFakulta elektrotechnická

Diplomová práce

Analýza antropologických dat metodami výpočetńı inteligence

Bc. Jakub Novák

Vedoućı práce: Ing. Kord́ık Pavel, Ph.D.

Studijńı program: Elektrotechnika a informatika strukturovaný magisterský

Obor: Informatika a výpočetńı technika

květen 2008

ii

Poděkováńı

Chtěl bych moc poděkovat Ing. Pavlu Kord́ıkovi, Ph.D. za jeho výborné vedeńı mé práce. Jehopozitivńı př́ıstup a vstř́ıcnost, se kterou přistupoval k mým dotaz̊um a problémům.

iii

iv

Prohlášeńı

Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil jsem pouze podkladyuvedené v přiloženém seznamu.Nemám závažný d̊uvod proti užit́ı tohoto školńıho d́ıla ve smyslu §60 Zákona č. 121/2000 Sb.,o právu autorském, o právech souvisej́ıćıch s právem autorským a o změně některých zákon̊u(autorský zákon).

V Praze dne 23.5.2008 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

v

vi

Abstract

A computational intelligence methods are suitable instrument for work with the anthropologicaldata which represents senescence indicators along with other inputs. Based on this informationwe try to predict the age of skeleton. But this is a very difficult process and obtain high-qualityresults is complicated. My goal in this diploma thesis is to find and valorize the best methodswhich can handle well the anthropological data and give us the best results.

Abstrakt

Metody výpočetńı inteligence jsou vhodným nástrojem pro práci s antropologickými daty, kterépředstavuj́ı kosterńı ohledáńı spolu s některými daľśımi vstupy, ze kterých se snaž́ıme predikovatvěk zesnulého. Proces to však neńı v̊ubec jednoduchý a dostat kvalitńı výsledky je poměrněkomplikované. Proto si touto praćı kladu za ćıl nalézt a zhodnotit nejvhodněǰśı metody, kteréby uměly dobře zpracovat daná antropologická data a podat co nejlepš́ı výsledek.

vii

viii

Obsah

Seznam obrázk̊u xi

Seznam tabulek xiii

1 Úvod 1

2 Metody pro analýzu antropologických dat 22.1 Źıskáváńı znalost́ı z dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Typy dolovaćıch úloh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2.1 Klasifikace a predikce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.2 Shlukováńı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.3 Analýza odlehlých objekt̊u . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.4 Analýza nalezených vzor̊u . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.3 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3.1 Antropologická data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.4 Prediktivńı metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.5 Klasifikačńı metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.6 Shlukové metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Předzpracováńı dat - teoretická část 163.1 Čǐstěńı dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1.1 Nekompletńı data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.1.2 Zašumělá data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2 Integrace a transformace dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.3 Redukce dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3.1 Početńı redukce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.4 Daľśı možné metody předzpracováńı . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Výsledky experiment̊u 224.1 Prediktivńı metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.1.1 GMDH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.1.2 GAME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 Klasifikačńı metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2.1 LVQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.2.2 Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2.3 RBF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.3 Metody shlukové analýzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3.1 SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.4 Předzpracovaćı metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.4.1 Výsledky jednotlivých metod . . . . . . . . . . . . . . . . . . . . . . . . 344.4.2 Výsledky experiment̊u za použit́ı modulu pro automatické předzpracováńı

dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 Zhodnoceńı výsledk̊u 41

6 Závěr 45

7 Literatura 47

ix

A Seznam použitých zkratek 49

B Obsah přiloženého CD 51

x

Seznam obrázk̊u

2.1 Ukázka GMDH śıtě jako černé skř́ıňky . . . . . . . . . . . . . . . . . . . . . . . 52.2 Struktura śıtě GMDH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Ukončeńı učeńı śıtě GMDH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Př́ıklad śıtě GAME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.5 Prostor 2D a hraničńı př́ımka . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6 Model perceptronu jako neuronu . . . . . . . . . . . . . . . . . . . . . . . . . . 92.7 Struktura RBF śıtě . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.8 Ukázka typických Radial Basis Function . . . . . . . . . . . . . . . . . . . . . . 112.9 Trénovaná RBF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.10 Struktura neuron̊u Kohonenovy mapy . . . . . . . . . . . . . . . . . . . . . . . 132.11 SOM - možné struktury uspořádáńı neuron̊u . . . . . . . . . . . . . . . . . . . . 142.12 SOM - př́ıklad adaptace vah neuronu . . . . . . . . . . . . . . . . . . . . . . . . 152.13 U-matice pro śıt’ 10 x 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1 Př́ıklad rozděleńı do shluk̊u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Metody výběru podmnožiny atribut̊u . . . . . . . . . . . . . . . . . . . . . . . . 19

4.1 Výsledný GMDH model v KnowledgeMiner softwaru . . . . . . . . . . . . . . . 224.2 LVQ - celkový přehled úspěšnosti ohodnoceńı . . . . . . . . . . . . . . . . . . . 254.3 Rozptyl úspěšnosti klasifikace pomoćı automaticky generované śıtě . . . . . . . 274.4 Rozptyl úspěšnosti klasifikace pomoćı minimálńı śıtě . . . . . . . . . . . . . . . 284.5 2D prostor vstupńıch vektor̊u obsahuj́ıćı dva shluky . . . . . . . . . . . . . . . . 294.6 RBF - správně zařazené vzorky pro n=4 a σ = 0,775 . . . . . . . . . . . . . . . 304.7 SOM - vliv pohlav́ı na predikci . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.8 SOM - rozděleńı podle národnosti . . . . . . . . . . . . . . . . . . . . . . . . . . 314.9 SOM - rozděleńı podle kontinentu . . . . . . . . . . . . . . . . . . . . . . . . . . 324.10 SOM - výsledné ”shluky” koster podle stář́ı . . . . . . . . . . . . . . . . . . . . 334.11 Ukázka programu GAME spolu s předzpracovaćım dialogem . . . . . . . . . . . 34

5.1 Ukázka grafu trénovaćıch dat pomoćı 2D regrese . . . . . . . . . . . . . . . . . 435.2 Rozptyl výsledných hodnot MAPD - vybrané PM metody . . . . . . . . . . . . 445.3 Rozptyl výsledných hodnot MMVI . . . . . . . . . . . . . . . . . . . . . . . . . 45

xi

xii

Seznam tabulek

4.1 GMDH věková regrese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Výsledky GMDH a GAME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3 Parametry śıtě LVQ1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.4 LVQ1 - procentuálńı úspěšnost klasifikace . . . . . . . . . . . . . . . . . . . . . 254.5 Parametry automaticky generované śıtě . . . . . . . . . . . . . . . . . . . . . . 264.6 Parametry minimálńı śıtě . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.7 Pr̊uměrná úspěšnost klasifikace na automaticky generované śıti . . . . . . . . . 264.8 Pr̊uměrná úspěšnost klasifikace na minimálńı śıti . . . . . . . . . . . . . . . . . 274.9 Zastoupeńı ve věkových tř́ıdách . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.10 Zastoupeńı žen Evropanek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.11 RBF - nejlepš́ı výsledky pro n=4 a σ = 0,775 . . . . . . . . . . . . . . . . . . . 294.12 Přepoč́ıtány výsledky GMDH a GAME . . . . . . . . . . . . . . . . . . . . . . 354.13 Výsledek předzpracovaćıch metod - All units, 1N . . . . . . . . . . . . . . . . . 364.14 Výsledek předzpracovaćıch metod - All units, ensemble (3N) . . . . . . . . . . . 364.15 Výsledek předzpracovaćıch metod - linear, 1N . . . . . . . . . . . . . . . . . . . 364.16 Výsledek předzpracovaćıch metod - linear, ensemble (3N) . . . . . . . . . . . . 374.17 Výsledky č.1 - modulu pro automatické předzpracováńı dat . . . . . . . . . . . 394.18 Pr̊uměrné hodnoty z tabulek 4.13 až 4.16 . . . . . . . . . . . . . . . . . . . . . 404.19 Výsledky č.2 - modulu pro automatické předzpracováńı dat . . . . . . . . . . . 40

5.1 Porovnáńı výsledk̊u klasifikačńıch metod - tučně nejlepš́ı výsledek . . . . . . . . 415.2 Vybrané výsledky algoritmů GAME a GMDH - chyba RMS . . . . . . . . . . . 425.3 Vybrané nejlepš́ı předzpracovaćı metody . . . . . . . . . . . . . . . . . . . . . . 42

xiii

xiv

KAPITOLA 1. ÚVOD 1

1 Úvod

V této diplomové práci se zaměřuji na r̊uzné metody výpočetńı inteligence k nasazeńı pro do-lováńı znalost́ı z dat (tzv. data mining). Zkoumám jejich využit́ı, kvalitu výsledných dat, kterénám mohou poskytnout a jejich nasazeńı na reálných datech. Pro experimenty se všemi me-todami využ́ıvám antropologická data. Z nich se snaž́ım źıskat co nejlepš́ı hodnoty za použit́ır̊uzných metod neuronových śıt́ı.

Experimentuji s r̊uznými předzpracovaćımi metodami, tak aby nám poskytly co nejlepš́ı úpravupředložených dat a t́ım se pokusily pomoci k dosažeńı ještě lepš́ıho výsledku. S t́ımto ćılem takétestuji modul pro automatické předzpracováńı dat, implementovaný do programu GAME, jehožvýsledky poté porovnávám s ostatńımi metodami. Mou snahou bylo také shromáždit a porov-nat výsledky, které vznikly v rámci r̊uzných praćı, a vybrat z nich ty nejvhodněǰśı pro prácis antropologickými daty.

K této práci mě motivovalo navázat na výzkum, který jsem prováděl v rámci své bakalářsképráce, která byla také založená na antropologických datech a neuronových śıt́ıch. Proto možnostpokračovat v této problematice a pokusit se posunout výsledky v této oblasti dále, mě přǐslo ve-lice lákavé. Pokusit se vylepšit přesnost predikce stář́ı kosterńıch poz̊ustatk̊u, zmapovat použit́ıjiných technologíı a předzpracovaćıch metod.

Tato práce se děĺı do několika kapitol. Prvńı z nich je Metody pro analýzu antropologických dat(AD). Zde teoreticky popisuji metody, které jsou vhodné pro práci s AD, jak funguj́ı a jakýchvýstup̊u z nich můžeme dosáhnout.

V druhé kapitole popisuji r̊uzné metody úpravy dat. Co je možné s daty udělat, aby poskytovalyco nejlepš́ı vypov́ıdaćı hodnotu. Za t́ımto účelem, že můžeme data r̊uznými zp̊usoby upravovat,redukovat a čistit, k čemuž nám dopomáhaj́ı předzpracovaćı metody.

V daľśı kapitole popisuji experimenty, které byly s AD provedeny. Jakých prostředk̊u a metodk nim bylo použito a jaké výsledky nám poskytly.

Následuje kapitola, kde shrnuji dosažené výsledky a porovnávám je mezi sebou. T́ım se snaž́ımnalézt nejlepš́ı metody a ty doporučit pro práci s AD.

Posledńı kapitolou je závěr. Ta uzav́ırá mou diplomovou práci a hodnot́ı, k jakým výsledk̊umjsem dospěl.

2 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

2 Metody pro analýzu antropologických dat

2.1 Źıskáváńı znalost́ı z dat

Metody výpočetńı inteligence pro źıskáváńı znalost́ı z dat jsou vhodným nástrojem pro odha-lováńı předem skrytých vztah̊u mezi daty. Hlavńı techniky použ́ıvané při vytěžováńı dat jsouregrese, klasifikace a shlukováńı. Pomoćı těchto technik můžeme z antropologických dat źıskatpožadované informace. Na základě vstupńıch dat můžeme pomoćı regrese predikovat výstup,č́ımž je stář́ı kostry. V podstatě jde o to, že si vezme soubor dat a pomoćı matematického vzorcese tyto data poṕı̌śı. T́ım vznikne určitý model, který popisuje dané data.

2.2 Typy dolovaćıch úloh

Řada metod použ́ıvaných v problematice źıskáváńı znalost́ı vycháźı z umělé inteligence. Úlohyse rozděluj́ı na 2 typy: deskriptivńı a prediktivńı. Deskriptivńı funkce charakterizuj́ı a popisuj́ıdata podle jejich vlastnost́ı. Prediktivńı funkce pracuj́ı tak, že na základě trénovaćıch dat jsouschopny předpovědět vlastnosti dat nově př́ıchoźıch.

2.2.1 Klasifikace a predikce

Jedná se o prediktivńı dolovaćı úlohy. Ćılem klasifikace je nalezeńı pravidel, která rozlǐsuj́ı azároveň popisuj́ı tř́ıdy dat. Tato pravidla se pak použij́ı k predikci tř́ıdy objektu, jehož zařazeńıneznáme. Model je sestavován pomoćı podmı́nkových pravidel, rozhodovaćıch stromů nebojiných prostředk̊u. Proces klasifikace se sestává ze tř́ı krok̊u:

1. Trénováńı – na základě trénovaćı množiny je vytvořen model pro klasifikaci. Tato fázese označuje také jako učeńı.

2. Testováńı – ověřeńı kvality modelu testováńım pomoćı testovaćı množiny.

3. Aplikace – použit́ı modelu ke klasifikaci dat, jejichž tř́ıdu neznáme. Klasifikace se použ́ıvák predikci diskrétńıch tř́ıd. Oproti tomu predikce předpov́ıdá hodnoty spojitých atribut̊u.V tomto př́ıpadě předpov́ıdáme numerickou nedostupnou hodnotu. Nejčastěǰśı metodoupredikce je regresńı analýza. V př́ıpadě antropologických dat jde o predikci věku kostry.

2.2.2 Shlukováńı

Shluková analýza (Cluster Analysis) na rozd́ıl od klasifikace a predikce analyzuje objekty bezznalosti přǐrazeńı do tř́ıd. Ćılem je nalézt tř́ıdy objekt̊u, které maj́ı co nejv́ıce společného tak,aby se objekty r̊uzných tř́ıd co nejv́ıce lǐsily. Nalezené tř́ıdy maj́ı podobu tzv. shluk̊u.

2.2.3 Analýza odlehlých objekt̊u

Jde o nalezeńı objekt̊u, které se nějakým zp̊usobem významně odlǐsuj́ı od ostatńıch. Takovédatové objekty se nazývaj́ı odlehlé (outlier). Tato analýza může např́ıklad v praxi odhalitpodvodné zneužit́ı kreditńıch karet, extrémně velké nebo podezřelé nákupy. U antropologickýchdat jde o nalezeńı tzv. ”ustřelených” hodnot a ty pro modelováńı nepouž́ıvat, protože zanáš́ıchybu do predikce stář́ı.

2.2.4 Analýza nalezených vzor̊u

Systém pro źıskáváńı znalost́ı z dat je schopen generovat obrovské množstv́ı vzor̊u nebo pravidel.Vzniká tak d̊uležitá otázka zaj́ımavosti nalezených vzor̊u. V praxi je zaj́ımavá pro koncového

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 3

uživatele pouze malá část. Zaj́ımavé vzory nebo pravidla pak představuj́ı znalost. Aby bylvydolovaný vzor pro uživatele zaj́ımavý, muśı mı́t 4 základńı vlastnosti, které určuj́ı mı́ruzaj́ımavosti:

• Srozumitelnost – vzor muśı být srozumitelný pro člověka

• Platnost – pro nová nebo testovaćı data

• Užitečnost – vzor muśı mı́t reálnou užitečnost

• Novost – přináš́ı nové poznatky

Užitečným vzorem může být i vzor, který validuje hypotézu, kterou se snaž́ı uživatel potvrdit.Pro určeńı mı́ry zaj́ımavosti existuj́ı objektivńı a subjektivńı metody. Objektivńı metody jsouzaloženy na struktuře objevovaných vzor̊u a statistických údaj́ıch k nim vztažených. Mezi tytometody patř́ı dř́ıve zmı́něné frekventované vzory a asociačńı pravidla (mı́ra podpory a spoleh-livosti). Subjektivńı mı́ry by měly doplňovat objektivńı, které samy o sobě nejsou dostatečnýmkritériem pro vyhodnoceńı zaj́ımavosti. Mezi taková kritéria patř́ı např. novost, neočekávanostapod.

2.3 Data

Pro źıskáńı kvalitńıho výsledku mohou být limituj́ıćı data sama. Je d̊uležité rozhodnout kterádata (vstupy) jsou d̊uležité a které méně, pro výsledek, kterého se snaž́ıme dosáhnout. Nevšechny informace jsou vhodné pro vytěžováńı dat. Je zapotřeb́ı porozumět struktuře, pokryt́ıa kvalitě daných dat. Často je také zapotřeb́ı předzpracovat daná data, abychom z nich odstra-nili informace, které nejsou pro námi požadovaný model potřebná nebo dokonce jsou zaváděj́ıćıa směřuj́ı k špatným výsledk̊um. Takovým dat̊um ř́ıkáme zašumělá. Pomoćı předzpracovaćıchmetod se snaž́ıme takovýmto zaváděj́ıćım hodnotám přecházet a eliminovat je.

Bylo vyvinuto mnoho technik pro źıskáváńı znalost́ı z dat. Pro predikci biologického stář́ıčlověka z jeho kosterńıch poz̊ustatk̊u na antropologických datech se hod́ı nejv́ıce regresivńımodelováńı. Protože na trénovaćıch datech se vytvoř́ı model popisuj́ıćı jednotlivé vztahy meziproměnnými (neuronová śıt’) a pomoćı ńı na testovaćıch datech se dá predikovat stář́ı kostry.Jednak můžeme určovat stář́ı kostry př́ımo nebo si stanovit určité věkové skupiny a stář́ı danékostry určovat podle toho do které skupiny spadá - klasifikace.

Pro určováńı věku koster se jako vhodné jev́ı metody lineárńı regrese a to GMDH (GroupMethod of Data Handling) a GAME (Group of Adaptive Models Evolution). Dı́ky nim můžemeodhadovat věk koster. Daľśımi metodami jsou LVQ (Learning Vector Quantization), Perceptron- technický model organické nervové śıtě a nebo RBF (Radial Basis Function). Tyto metody jsouvhodné pro klasifikaci do věkových tř́ıd. A třet́ı zaj́ımavou skupinou pro práci s AD jsou metodyshlukové analýzy. Do těch spadaj́ı mapy SOM - Self-Organizing Map. Jednotlivé metody budoupopsány dále v práci spolu s výsledky experiment̊u.

2.3.1 Antropologická data

Stěžejńım prvkem o který se oṕırá tato diplomová práce jsou použité antropologické data. Tynaše škola źıskala za spolupráce s Université Bordeaux, přesněji ve spolupráci s JaroslavemBr̊užkem, který dané data poskytnul. Ty jsou posb́ırány z muzéı celého světa. Obsahuj́ı r̊uznépř́ıznaky opotřebeńı kost́ı, ke kterým docháźı při stárnut́ı. Podle těchto ohledáńı se snaž́ımepredikovat věk kostry. Bohužel jak se ukázalo, tak jsou tyto data velmi zašumělá a predikce

4 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

neńı př́ılǐs přesná, jak bude vidět dále ve výsledćıch experiment̊u.

Data reprezentuj́ı množinu hodnot, kterými je ohodnocena lidská kostra pro účely odhadustář́ı z lidského skeletonu (Schmitt, 2001; Schmitt et al., 2002). Jde o vizuálńı ohodnoceńımorfologických změn povrchu dvou kost́ı pánevńıch. Vzorek je sebrán z 955 koster, u kterýchje známo pohlav́ı a věk. Tato kolekce obsahuje data:

• Kontinent: Europe, Africa, North America, Asia.• Národnost: Portugal, Africaner, ZULU, USAW, Spain, Suisse, SOTO, Thailand, USAB.• Pohlav́ı: Female, Male.• Č́ıselné parametry: PUSA, PUSB, PUSC, SSPIA, SSPIB, SSPIC, SSPID.

Věk zesnulých se pohybuje mezi 19 a 100 lety.

Vstupńı data obsahuj́ı informace identifikačńı č́ıslo kostry, které ale neńı pro predikci d̊uležité.Dále data popsaná výše, z nichž nejd̊uležitěǰśımi faktory jsou:

3 vstupy jsou ohledáńı spony stydké na pánvi:

• Zadńı ploténka (PUSA) ohodnocena na stupnici (1-2-3)• Předńı ploténka (PUSB) ohodnocena na stupnici (1-2-3)• Zadńı hřbet (PUSC) ohodnocena na stupnici (1-2)

4 pozorováńı sacropelvic povrchu ilia:

• Př́ıčné uložeńı (SSPIA) ohodnoceńı (1-2)• Změny na povrchu kloubu (SSPIB) hodnoceńı (1-2-3-4)• Změny na hrotu kosti (SSPIC) hodnoceńı (1-2)• Změny na iliu tuberosity (SSPID) hodnoceńı (1-2)

A jako posledńı informaćı, a to výstupńı, je stář́ı kostry. Ten slouž́ı k naučeńı neuronové śıtěv pr̊uběhu fáze trénováńı a ve fázi testováńı se pokouš́ıme tuto hodnotu predikovat, popř́ıpaděklasifikovat. Nakonec jsou ještě data rozdělily do dvou množin a to do trénovaćı, která obsahuje639 vzork̊u a testovaćı, č́ıtaj́ıćı 319 vzork̊u.

2.4 Prediktivńı metody

GMDH

Neuronové śıtě typu GMDH jsou polynomiálńı śıtě. Lze je použ́ıt např́ıklad pro predikce (ban-kovnictv́ı, předpov́ıdáńı počaśı), ale např́ıklad také pro rozpoznáváńı. Śıtě se uplatńı všudetam, kde si řešený problém lze představit jako ”černou skř́ıňku” maj́ıćı několik nezávislýchvstup̊u a jeden výstup. Úkolem śıtě je naj́ıt hodnotu výstupu v závislosti na nějaké kombinacivstup̊u. Idea śıtě GMDH spoč́ıvá v nalezeńı analytického vyjádřeńı (funkce), které bude praco-vat takovým zp̊usobem, že śıt́ı predikovaná hodnota výstupu bude co nejvěrohodněji vyjadřovatskutečnou hodnotu. Tuto funkci hledáme postupně při učeńı śıtě pomoćı uč́ıćı množiny. Auto-rem śıtě GMDH je DrSc. Alexey Grigorievich Ivakhnenko.

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 5

Obrázek 2.1: Ukázka GMDH śıtě jako černé skř́ıňky

Śıtě typu GMDH jsou śıtě polynomiálńıho typu ”s učitelem”. Učitel zde spoč́ıvá v tom, žeśıti při učeńı předkládáme dvojice vstupńı vektor - požadovaná hodnota. Jejich základńıčinnost spoč́ıvá v aproximaci funkćı f : A ⊂ Rn ⇒ R, což demonstruje obrázek 2.1.Z obrázku je patrné, že śıt’ má n vstup̊u (X1 − Xn) a jeden výstup (Y ). Horńı mez počtuvstup̊u neexistuje, pouze ovlivňuje nároky na výpočetńı prostředky, které muśıme vynaložit.Pokud budeme cht́ıt využ́ıt všech vlastnost́ı GMDH, je minimálńı počet vstup̊u 3. Hlavńı na-sazeńı śıtě je v oblastech, kde je potřeba aproximace funkćı. Po úpravě lze śıt’ použ́ıt např́ıkladpro predikce, či klasifikace. Což se právě hod́ı k určováńı věku v antropologických datech.

Struktura neuronové śıtě, ze které také vycháźı princip GMDH, lze vidět na obrázku 2.2:

Obrázek 2.2: Struktura śıtě GMDH

Jak již bylo řečeno výše, činnost śıtě spoč́ıvá v aproximaci funkćı f : A ⊂ Rn ⇒ R. Funkcemapuj́ı podmnožinu n-rozměrného Euclidovského prostoru do množiny reálných č́ısel. Př́ıkladna obrázku 2.2 má 4 vstupy (složky vstupńıho vektoru X1−Xn) a jeden výstup y′, což je odhadfunkce y = f(X). Na obrázku si lze všimnout toho, že śıt’ se skládá z jednotlivých vrstev, každávrstva je složena z prvk̊u (neuron̊u).Vrstvy můžeme rozdělit na 3 kategorie:

• vstupńı - slouž́ı k distribuci složek vstupńıho vektoru do śıtě, konkrétně do prvńı skrytévrstvy. Obsahuje tolik neuron̊u, kolik je prvk̊u vstupńıho vektoru;

• výstupńı - pokud při procesu učeńı dospějeme do stavu, kdy výstup śıtě splňuje našekritéria, posledńı vrstvu prohláśıme za výstupńı a ukonč́ıme tvorbu śıtě. Neuron, kterýdává nejlepš́ı výsledky v závislosti na testovaćıch datech, prohláśıme za výstup śıtě;

• skryté - vrstvy, které jsou mezi vstupńı a výstupńı vrstvou. Śıt’ GMDH by měla mı́t

6 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

pro svou správnou funkci alespoň jednu skrytou vrstvu. Maximálńı počet skrytých vrstevneńı nijak omezen.

Vstupńı vrstva neńı pro funkci śıtě nijak významná, slouž́ı pouze pro distribuci jednotlivýchsložek vstupńıho vektoru do daľśıch vrstev (na vstupńı vrstvu navazuje prvńı skrytá vrstva,na prvńı skrytou druhá skrytá atd.). Skryté vrstvy obsahuj́ı výkonné prvky śıtě (neurony).Výstupńı vrstva obsahuje pouze jeden neuron, který zároveň tvoř́ı výstup celé śıtě.

Vlastńı chováńı śıtě je založeno na principu dopředného š́ı̌reńı (v př́ıpadě obrázku 2.2 zleva do-prava). Na jednotlivé vstupy śıtě (vstupy neuron̊u vstupńı vrstvy) přilož́ıme hodnoty vstupńıhovektoru, které jsou vstupńı vrstvou distribuovány do prvńı skryté vrstvy, kde jsou provedenypř́ıslušné kombinace. Výstup prvńı skryté vrstvy je dále distribuován na vstupy druhé skrytévrstvy a tak dále. Posledńı vrstvou je vrstva výstupńı, která obsahuje pouze jeden neuron (jedenvýstupńı neuron neńı pravidlem, v některých modifikaćıch GMDH jich může být i v́ıce). Jej́ımvýstupem je reálné č́ıslo y, které je současně výstupem celé śıtě. Počet skrytých vrstev neńıomezen a neńı předem určen. Vyplývá ze složitosti řešeného problému a požadavk̊u kladenýchna přesnost výstupu.

Na obrázku 2.2 si lze všimnout, že mezi neurony jednotlivých vrstev neexistuje úplné propo-jeńı. Dále si všimněme, že každý neuron (vyjma neuron̊u vstupńı vrstvy) má právě dva vstupya jeden výstup (výstup se mnohačetně distribuuje do neuron̊u daľśıch vrstev). Z toho plynoujistá omezeńı pro minimálńı počet vstup̊u. Śıt’ s jedńım vstupem vytvořit nejde a ani to nemásmysl. Śıt’ se dvěma vstupy neobsahuje žádné skryté vrstvy - vzniklá śıt’ je jiného charakteru.Pokud chceme vytvořit śıt’, která bude mı́t všechny vlastnosti GMDH jsme omezeni minimálńımpočtem vstup̊u 3.

Śıt’ GMDH se od ostatńıch śıt́ı lǐśı předevš́ım t́ım, že docháźı ke splynut́ı procesu učeńı a tvorbyśıtě. Na počátku neńı dána ani struktura śıtě, ani počet neuron̊u. Známe pouze počet složekvstupńıho vektoru→ vytvoř́ıme vstupńı vrstvu s odpov́ıdaj́ıćım počtem neuron̊u. Na této vrstvěpostupně procesem učeńı vyr̊ustaj́ı daľśı a daľśı vrstvy, dokud neńı splněn požadavek na výstupśıtě. Algoritmus tvorby jednotlivých vrstev je stále stejný. Každá nově vytvořená vrstva sevždy samostatně zadaptuje a zmraźı (během daľśıho učeńı se již jej́ı parametry neměńı a tatovrstva slouž́ı pouze k distribuci signálu). Na této vrstvě posléze stav́ıme stejným zp̊usobemdaľśı vrstvu a celý postup opakujeme, dokud śıt’ nesplňuje požadavky, které na ńı klademe.Pokud doraźıme do tohoto bodu, tvorbu śıtě zastav́ıme.

Ukončeńı výpočtu nastane, jakmile śıt’ splňuje požadavky na ”přesnost” výstupu. Postupujemetak, že v každém uč́ıćım kroku (po přidáńı nové vrstvy a vyč́ısleńı koeficient̊u) otestujeme, zdajsme již nedosáhli požadovanou hodnotu a zda bychom právě v tomto kroku neměli tvorbuśıtě ukončit. Pr̊uběh středńı kvadratické chyby v závislosti na počtu skrytých vrstev ukazujeobrázek 2.3.

Na něm si můžeme všimnout toho, že s počtem vrstev se výsledná chyba śıtě zmenšuje. Jakmileale dosáhne minima, zač́ıná se opět zvětšovat. My muśıme toto globálńı minimum naj́ıt a ukončitzde tvorbu śıtě. Tvorbu śıtě tedy můžeme ukončit:

• v okamžiku, kdy dosáhneme globálńıho minima• v okamžiku, kdy śıt’ dosáhne lepš́ıho výstupu než požadujeme

Zde je třeba si uvědomit, že je při učeńı třeba obej́ıt mı́sta lokálńıho minima. Lze to provéstnapř́ıklad tak, že předpokládáme, že nalezené mı́sto je globálńım minimem, ale pokračujeme

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 7

Obrázek 2.3: Ukončeńı učeńı śıtě GMDH

v přidáńı ještě několika vrstev. Podle vývoje chyby se bud’ vrát́ıme do p̊uvodńıho mı́sta, nebopokračujeme dál. Posledńı vrstvu označ́ıme za výstupńı vrstvu. Neuron s nejlepš́ım výstupemv této vrstvě označ́ıme jako výstupńı neuron celé śıtě. Odstrańıme ostatńı neurony, které neo-vlivňuj́ı výstup śıtě. T́ım je śıt’ naučena a máme model postihuj́ıćı předložená data. Ten potémůžeme aplikovat na testovaćı data. [GMDH web]

GAME

Daľśı metodou vhodnou pro použit́ı na antropologických datech je GAME (Group of AdaptiveModels Evolution). Jedná se v podstatě o vylepšenou variantu GMDH, ze které také vycháźı.Př́ıklad tvorby śıtě GAME je vidět na obrázku 2.4. Z něj je patrné, že se śıt’ vytvář́ı vrstvu povrstvě v pr̊uběhu procesu učeńı z jednotek, které přenášej́ı informace dopředně ze vstup̊u navýstup. Śıt’ se tak postupně rozr̊ustá a uč́ı. Genetický algoritmus muśı v každé vrstvě vybratvhodné jednotky, které budou použity dále pro vytvořeńı modelu. Vı́ce informaćı o tomto mo-delováńı lze naj́ıt v [Kord́ık, 05], podle [Kord́ık, Šnorek, 05].

GAME může vytvářet modely pro klasifikaci, predikci, identifikaci a regresi. Topologie GAMEmodel̊u se přizp̊usobuje povaze skrytých dat. Metoda je odolná v̊uči neplatným nebo redun-dantńım položkám, vhodná pro krátké a zašumělé vzorky. V GAME rostou jednotky z mi-nimálńı formy, počet vstup̊u je minimálně jeden a shora omezen pořad́ım skryté vrstvy, ve kteréjednotka je. Vstupy jednotek již nejsou pouze z př́ımé předchoźı vrstvy. Mohou být připojenyna vstup jakékoli jednotky z předchoźıch vrstev, stejně tak k libovolnému vstupu modelu.

Za použit́ı śıtě GAME byla využita tzv. ensemble technika. Ta je založena na tom, že konečnémnožstv́ı model̊u neuronových śıt́ı nauč́ıme na stejné úloze. A když dáme dohromady všechnytyto modely, tak spolu popisuj́ı daný problém (data) daleko lépe než každý model sám. Využ́ıváse dvou př́ıstup̊u a to bud’ tzv. bagging nebo boosting. Bagging neboli jakési pytlováńı čisáčkováńı představuje postup, kdy jsou jedny trénovaćı data rozděleny na v́ıce soubor̊u a z nichjsou poté trénovány jednotlivé modely. GAME śıtě použ́ıvané programem GAME použ́ıvaj́ıpřesně takový př́ıstup, při použit́ı ensemble techniky.

8 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

input variables

output variable

first layer

second layer

third layer

output layer

interlayer connection

3 inputsmax

4 inputs max

P C P G

P P C

L

P L C

Obrázek 2.4: Př́ıklad śıtě GAME. Śıt’ se vytvoř́ı pomoćı trénovaćıch dat obsahuj́ıćıch vhodnéjednotky pro přenos (P-jednotky perception optimalizované pomoćı backpropagation algoritmu,L-lineárńı a C-polynomiálńı přenosové jednotky, oboj́ı optimalizované pomoćı Quasi Newtonmetody).

2.5 Klasifikačńı metody

LVQ

Metodou vhodnou pro klasifikaci do tř́ıd, tud́ıž zde se již nepokouš́ıme určit přesný věk kostry,ale padnut́ı do tř́ıdy, je LVQ - Learning Vector Quantization. Tato neuronová śıt’ vycháźı z Ko-honenovy śıtě, která patř́ı k samoorganizuj́ıćım neuronovým śıt́ım, takže nepotřebuje ke svémutrénováńı učitele. Jejich funkce je založena na principu shlukové analýzy ( nalezeńı určitýchvlastnost́ı a závislost́ı př́ımo v předkládaných trénovaćıch datech ). Kohonen̊uv základńı modelje většinou dvojdimenzionálńı i když může mı́t i jiné uspořádáńı výstupńıch neuron̊u. Tentomodel obsahuje jen vstupńı a výstupńı vrstvu. Počet vstup̊u do śıtě je roven dimenzi vstupńıhoprostoru. Počet vstup̊u neuronu ve výstupńı vrstvě je roven počtu vstup̊u do Kohonenovy śıtě.Váhy těchto vstup̊u neuronu slouž́ı k zakódováńı vzor̊u. Jedinou operaćı, kterou neuron provád́ı,je výpočet vzdálenosti předloženého vzoru od vzoru zakódovaného ve vahách daného neuronu.Výstupńı neurony jsou propojeny se všemi svými sousedńımi neurony. Každý vstup je spojens každým neuronem výstupńı mř́ıžky.

LVQ je modifikovaná Kohonenova śıt’, která je schopna pracovat s pomoćı učitele. Fáze učeńıje o něco komplikovaněǰśı než u Kohonenovy śıtě, vybavovaćı fáze je shodná. Existuj́ı tři verzeLVQ1,LVQ2 a LVQ3, které se od sebe lǐśı algoritmem hledáńı nejlepš́ı hranice mezi tř́ıdami.

LVQ1: Neuronová śıt’ LVQ vylepšuje své chováńı podle informace o tř́ıdě do které vstupńı vek-tor patř́ı. V prvńı fázi běž́ı LVQ jako klasická Kohonenova śıt’. T́ım se zajist́ı určité samovolnéuspořádáńı neuron̊u do tř́ıd. Pak přijde na řadu LVQ1. Přivád́ıme na vstupy znovu trénovaćıvektory a v př́ıpadě, že vektor byl zařazen do správné tř́ıdy, přiklońı váhy ještě v́ıce k danétř́ıdě. V opačném př́ıpadě muśı být váhy od špatné tř́ıdy odkloněny. T́ım se zvýrazňuj́ı hranicemezi tř́ıdami a zmenšuje riziko špatně zařazeného vektoru. LVQ1 může být ještě vylepšenaa tato vylepšená verze se nazývá Optimalizovaná LVQ1. Rozd́ıl je v individuálńım nastaveńı

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 9

parametru rychlosti učeńı pro každý neuron. [MOON web]

Perceptron

Daľśı podobnou metodou klasifikace koster do skupin je neuronová śıt’ založená na per-ceptronu. Ten představuje něco jako lidský neuron, do kterého vedou vstupy (vstupńı in-formace) a výstupem jsou zpracované vstupńı informace v podobě požadovaného formátuvýsledku. Úkolem perceptronu (rep. obecně neuronové śıtě) je nalézt hranici mezi těmito dvěmaskupinami. Správné určeńı hranice je d̊uležité pro budoućı správné zařazeńı nového vzoru.

Obrázek 2.5: Prostor 2D a hraničńı př́ımka

Obrázek 2.6: Model perceptronu jako neuronu

Algoritmus učeńıUčeńı je interaktivńı proces, kdy se v každém kroku trochu pooprav́ı jednotlivé složky váhovéhovektoru. Vzory, které slouž́ı k učeńı, se vyb́ıraj́ı z množiny všech vstupńıch vzor̊u. Těchto vzor̊umůže být libovolný počet. Na počátku jsou váhy nastaveny na své počátečńı hodnoty, kterése nejčastěji voĺı náhodně. Hraničńı př́ımka (rovina, ...) určená těmito vahami je samozřejměšpatně orientována. Teprve časem se vlivem adaptace vah podař́ı naj́ıt správný směr.Základńım principem je učeńı se z vlastńıch chyb. Jestliže perceptron odpověděl špatně napředložený vzor, upravujeme váhy (zvyšujeme nebo snižujeme) tak, aby se sńıžila chyba. Hod-nota, kterou modifikujeme váhy, je odvozena z velikosti chyby. Je to vlastně ”vzdálenost” mezidaným a správným výstupem, [Perceptron].

10 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

Obrázek 2.7: Struktura RBF śıtě

RBF

• Patř́ı mezi nejmladš́ı typy neuronových śıt́ı.• Často se použ́ıvá na regresi a predikci.• Jedná se o typ dopředné v́ıcevrstvé śıtě, se vstř́ıcným š́ı̌reńım signálu a učeńım s učitelem.

Jej́ı výhodou je zejména rychlost učeńı.

• Radiálńı funkce je určena svým středem a jej́ı hodnota záviśı na vzdálenosti argumentuod tohoto středu.

RBF je to tř́ıvrstvá śıt’, jej́ıž struktura je obdobná jako u tř́ıvrstvé śıtě typu backpropagation,ale přenosová funkce výstupńıch neuron̊u muśı být lineárńı, což nemuśı být pro śıt’ typu back-propagation pravda a přenosové funkce skrytých neuron̊u jsou tzv. Radial Basis Functions,odtud i název śıtě. Jejich charakteristickým znakem je, že bud’ monotónně klesaj́ı, nebo rostousměrem od svého středového bodu. Na následuj́ıćıch obrázćıch je ukázka struktury RBF śıtě(obrázek 2.7) a RBF funkce (obrázek 2.8).

Kromě vstupńı vrstvy, která slouž́ı jen pro předáńı hodnot, má RBF śıt’ vrstvu RBF (skrytávrstva) a vrstvu výstupńı tvořenou perceptrony. Mezi jednotlivými vrstvami se zpravidlapouž́ıvá úplné propojeńı. Definice RBF neuron̊u:

výpočet vnitřńıho potenciálu φ =√∑n

i=1(xi − ci)2

Jinými slovy: Vnitřńı potenciál se poč́ıtá jako euklidovská vzdálenost vstupńıho vektoru x odc dělenou š́ı̌rkou b.Pro RBF neurony se použ́ıvá Eukleidovská metrika, na rozd́ıl od perceptron̊u, kde se použ́ıváskalárńı součin. Vektor C = c1, ..., cn označujeme jako prototyp, protože reprezentuje jistoupodmnožinu vstupńıch dat ve tvaru shluku. Jako aktivačńı funkce se nejčastěji použ́ıvá Gaus-sova funkce a multikvadratická funkce, ale existuj́ı i jiné.

Učeńı neuron̊u RBF vrstvyTrénovaćı množinu tvoř́ı dvojice vstup-výstup. Učeńı RBF śıtě je rozděleno na dvě fáze. V prvńıfázi se urč́ı prototyp C a sigma pro každý RBF neuron. Tento proces prob́ıhá bez znalost́ı

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 11

Obrázek 2.8: Ukázka typických Radial Basis Function

funkčńıch hodnot nebo kategoríı. Použ́ıvaj́ı se algoritmy podobné algoritmům pro shlukovouanalýzu, nebo algoritmům učeńı Kohonenovy śıtě. Pro urychleńı této fáze lze využ́ıt také nea-daptivńıch metod, např. rovnoměrné, nebo náhodné rozložeńı střed̊u RBF neuron̊u po vstupńımprostoru.

Učeńı neuron̊u výstupńı vrstvyDruhá fáze učeńı má za úkol určit váhy výstupńıch neuron̊u. Vzhledem k charakteru výstupńıchneuron̊u, je možno použ́ıt metody nejmenš́ıch čtverc̊u, nebo gradientńıch algoritmů.

Použit́ı RBF śıtěPo naučeńı je śıt’ připravená k použit́ı na nových, zat́ım neznámých datech. Nový vstupńı vektornebude pravděpodobně stejný jako vektory trénovaćı množiny (přesněji řečeno, bod ve středuaktivačńı funkce může být posunut). Pravděpodobně bude částečně odpov́ıdat jen několik vahvektoru, a proto se uvedou v činnost odpov́ıdaj́ıćı skryté uzly, které se postupně měńı. Neuronbude aktivován jen tehdy, bude-li vstupńı vektor zařazen do jeho oblasti zájmu. Normálně jeaktivováno mnoho neuron̊u a jejich výstup je slučován dohromady ve výstupńıch uzlech. T́ımtozp̊usobem śıt’ interpoluje prostor mezi středy zájmových oblast́ı neuron̊u.

Obrázek 2.9 ukazuje př́ıklad trénované RBF. Jednotlivé aktivačńı funkce R1, R2, ... jsou zob-razeny jako křivky dvou vstupńıch funkćı I1 a I2. Vypoč́ıtaný model bude lokálńı (ve smyslu,že má velice malou vypov́ıdaćı schopnost o tom, jak vypadaj́ı funkce mimo zájmové oblastikonkrétńıho neuronu, popř. kde jsou jiná školená data). Každá aktivačńı funkce reprezentujeprávě jeden mı́stńı model školených dat, takže vnitřek zájmové oblasti odpov́ıdá konkrétńımuneuronu. Na druhé straně běžná v́ıcevrstvá śıt’ produkuje globálńı aproximaci, z toho vyplývá,že je každá zájmová oblast ovlivněna i ostatńımi trénovaćımi daty, které ve skutečnosti nemuśımı́t na danou oblast žádný vliv.

RBF śıt’ jako klasifikátorTo je př́ıpad, který použijeme na antropologická data. Zde můžeme využ́ıt jak spojitých, taknespojitých výstupńıch funkćı RBF neuron̊u. Nespojité zařazuj́ı vstupńı vektor do naučenémnožiny (shluku), spojité mohou informovat, do jaké mı́ry patř́ı vektor do této množiny.

12 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

Obrázek 2.9: Trénovaná RBF

Základńı pravidla pro stavbu śıtě jsou:

• Výstup RBF neuronu je napojen pouze na jeden výstupńı neuron

• Na výstupńı neuron může být napojeno v́ıce RBF neuron̊u.

• Pr̊unik sféry vlivu RBF neuron̊u náležej́ıćıch v́ıce r̊uzným kategoríım muśı být prázdný.

• RBF neurony téže kategorie muśı reprezentovat vzory dané kategorie s minimálńı chybou.

Pokud použ́ıváme pro klasifikaci RBF śıt’ se spojitými výstupńımi funkcemi RBF neuron̊u,muśı být váhy a práh výstupńıch neuron̊u nastaven tak, aby tyto neurony realizovaly prahovoulogickou funkci OR. Obvykle se RBF śıt’ uč́ı řádově rychleji, než obyčejná dopředná neuronováśıt’, ale RBF śıt’ je zpravidla pomaleǰśı při použit́ı větš́ıho počtu uzl̊u, podle [VSB web].

2.6 Shlukové metody

SOM

Dnes již mezi základńı typy neuronových śıt́ı, patř́ı také tzv. SOM = Self-Organizing Maps,neboli samoorganizuj́ıćı se mapy, častěji známé po svém ”stvořiteli” jako Kohonenovy mapy.Ty patř́ı do skupiny samouč́ıćıch se neuronových śıt́ı, tzn. śıt́ı s učeńım bez učitele, které kesvému nastavováńı nepotřebuj́ı ideálńı vzory. To znamená, že k učeńı śıtě stač́ı jen velká sku-pina reálných signál̊u, z nichž některé maj́ı určitou společnou vlastnost nebo naopak výraznéodlǐsnosti a již k nim nemuśı být přǐrazeny žádné ideálńı uč́ıćı signály nebo informace (target= ćılové hodnoty). Ty v př́ıpadě tzv. učeńı s učitelem udávaj́ı konečný ćılový stav, do kteréhose má śıt’ učeńım dostat. A právě jejich źıskáńı bývá často velkým problémem. Naopak u SOM(Kohonenovy mapy) nám např́ıklad stač́ı jen skupina vstupńıch signál̊u a během učeńı si śıt’již sama nalezne společné znaky a odlǐsnosti, podle kterých se bude ve své aktivńı činnostirozhodovat. A to je ta výhoda, která za cca 20 let od vzniku Kohonenových map, z nich udělalavelmi často využ́ıvanou a velmi obĺıbenou neuronovou śıt’.

Svoj́ı schopnost́ı samoorganizace a shlukováńı objekt̊u s podobnými vlastnostmi do skupin jsouKohonenovy mapy př́ımo předurčeny pro aplikace rozhodováńı, rozlǐsováńı a tř́ıděńı objekt̊u,signál̊u, značek apod. Častou aplikaćı je rozpoznáváńı řeči (např.přepis mluveného slova na

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 13

Obrázek 2.10: Struktura neuron̊u Kohonenovy mapy s v́ıtězným neuronem BMU (vstupńı vek-tor s hodnotami x1...xn, neuron s váhami mi = W )

napsané apod.) nebo přeložeńı psaného textu na tǐstěńı, či v mém př́ıpadě antropologická data.

Princip a strukturaZáklad tvoř́ı uspořádaná struktura neuron̊u, které se v tomto př́ıpadě daj́ı představit jako body(kroužky), kde ke každému př́ısluš́ı unikátńı vektor koeficient̊u označované jako váhy W (mi naobrázku 2.10). Nejčastěji má struktura formu dvourozměrné (k=2) čtvercové nebo obdélńıkovématice, hexagonálńıho útvaru nebo někdy i jednorozměrného vektoru (k=1).

Rozměr struktury (k) však nemá nic společného s počtem vah každého neuronu (bodu), tedydimenźı neuronu (n). Obvykle plat́ı, že k < n, stejně jako počet neuron̊u m < n. Naopak tvarstruktury uspořádáńı neuron̊u má vliv na učeńı mapy a počet vah je vždy shodný s počtemparametr̊u vstupńıch vzork̊u, hodnot nebo koeficient̊u vstupuj́ıćıho zpracovávaného signálu.Tvar uspořádáńı neuron̊u má vliv na volbu tzv. okoĺı neuronu R, které vymezuje jeho sousedy(sousedńı, nejbĺıže postavené neurony). V maticovém uspořádáńı neuron̊u (čtvercové nebo he-xagonálńı) je velikost okoĺı rovná počtu ”řad” neuron̊u od centrálńıho neuronu - viz obrázek2.11. Váhy každého neuronu naopak definuj́ı polohu neuronu v prostoru.

Princip učeńı SOMMatici neuron̊u se postupně předkládaj́ı vektory vstupńıho signálu (x ) tak, že se zvlášt’ po-rovnává rozd́ıl př́ıslušných hodnot vektoru vah (koeficient̊u w) každého neuronu s hodnotamivektoru vstupńıho signálu. K vyjádřeńı rozd́ılu se může využ́ıt r̊uzných algoritmů, ale nejčastějise dává přednost výpočtu euklidovské vzdálenosti D, tj. součet rozd́ıl̊u př́ıslušných hodnot:D = (x1 − w1)2 + (x2 − w2)2 + ..... + (xn − wn)2Výsledkem je tedy počet hodnot D, rovný počtu neuron̊u ve struktuře (např. 100 hodnot v ma-tici 10 x 10 neuron̊u). Následně se vybere jediný neuron s nejmenš́ım D a označ́ı se jako tzv. v́ıtěz(winner). Váhy tohoto neuronu totiž nejv́ıce ze všech odpov́ıdaj́ı hodnotám právě předloženéhosignálu. Při předkládáńı prvńı uč́ıćıho vstupńıho vektoru se jeho hodnoty porovnávaj́ı s náhodněvygenerovanými hodnotami vah (koeficient̊u) jednotlivých neuron̊u.Váhy W v́ıtězného neuronu se pak upravuj́ı (updatuj́ı), aby se co nejv́ıce přibĺıžily hodnotámprávě předloženého vstupńıho vektoru (x ). Využ́ıvá se vzorce:Winové = Wistaré + α(x − Wistaré) kde α je uč́ıćı koeficient vyjadřuj́ıćı rychlost učeńı(může nabývat hodnot 0 až 1, např. α = 0.6), Wi je vektor vah (koeficinet̊u) i-tého neuronuWi = [Wi1, Wi2, ....,Win] a x je vstupńı uč́ıćı vektor x = [x1, x2, ...xn].

14 KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT

Obrázek 2.11: Možné struktury uspořádáńı neuron̊u (*) s definićı okoĺı R v́ıtězného neuronu(#)

Při opětovném opakováńı dávky uč́ıćıch vektor̊u nebo postupným předkládáńım daľśıch novýchdávek se uč́ıćı koeficient obvykle snižuje. Spolu s v́ıtězným neuronem se měńı i ty sousedńı v de-finovaném okoĺı R (viz obrázek 2.11). Jejich váhy se upravuj́ı stejným zp̊usobem jako u v́ıtěze,pouze s t́ım rozd́ılem, že koeficient α je nahrazen koeficientem β, přičemž plat́ı α < β. Přiopětovném opakováńım dávky uč́ıćıch vektor̊u se může provádět i snižováńı hodnoty okoĺı Raž na R = 0, tzn. adaptuje se pouze v́ıtěz.

Ve výsledku by se mělo dosáhnout stavu, kdy v maticové struktuře neuron̊u vznikne několikvýznamných center, tzv. shluky, mezi nimiž se výrazně lǐśı hodnoty vah neuron̊u. Neurony,jejichž váhy během učeńı dosáhly nulových hodnot, se ze struktury mohou vyloučit. Početshluk̊u by měl být shodný s počtem odlǐsných vlastnost́ı nebo parametr̊u, které Kohonenovamapa našla v předložených dávkách uč́ıćıch vstupńıch vektor̊u. To také znamená, že funkčnostmapy a neuronových śıt́ı obecně, výrazně záviśı na složeńı signál̊u a informaćı v uč́ıćıch dávkách.

Pro jednodušš́ı kontrolu a přehledněǰśı dohled nad učeńım mapy se využ́ıvá grafického zob-razeńı shluk̊u, které vyjadřuje prostorové vztahy mezi neurony v prostoru vah. V diagramujsou váhové vektory (= neurony) zobrazeny jako černé body v dvojdimenzionálńım prostoru,které zároveň tvoř́ı centra shluk̊u. Černé čáry představuj́ı př́ımky spojuj́ıćı váhové vektory sou-sedńıch neuron̊u. Na obrázku 2.12 je ukázaná změna ”pozice” neuronu před a po adaptaci vahna vstupńı vektor (zelený bod).

Po naučeńı SOM se na vstup vždy přikládá analyzovaný neznámý vektor hodnot (zelený bod)podobného druhu, jako byly uč́ıćı vektory a opět výpočtem podobnosti-vzdálenosti od vek-tor̊u vah jednotlivých neuron̊u (černé body), se vybere ten v́ıtězný neuron, nejv́ıce podobnýhodnotám na vstupu. Ten již představuje určitou definovanou skupinu (shluk) a t́ım je známvýsledek. Ten představuje zařazeńı analyzovaných dat do některé skupiny či kategorie a t́ım ijejich pojmenováńı a nalezeńı jejich vlastnost́ı, [SOM].

U-maticePro zobrazeńı výsledk̊u metody SOM se využ́ıvá tzv u-matice. Ta zobrazuje neuronovou śıt’ s ba-revně vyjádřenou informaćı o tom, jak moc se daný neuron lǐśı od okolńıch ve svých vahách.

KAPITOLA 2. METODY PRO ANALÝZU ANTROPOLOGICKÝCH DAT 15

Obrázek 2.12: Př́ıklad adaptace vah neuronu v mapě rozložeńı shluk̊u ve dvojdimenzionálńımprostoru

Č́ım světleǰśı, t́ım je jim podobněǰśı. Světlé oblasti vymezené tmavš́ı hranićı tak představuj́ıshluky (clusters) neuron̊u s podobným referenčńım vektorem. Jako př́ıklad můžeme použ́ıtobrázek 2.13, kde vid́ıme jasně jeden takový velký shluk s nepř́ılǐs ostrou hranićı a asi bychomnašli i pár menš́ıch. V této u-matici každé druhé poĺıčko představuje neuron, mezi nimi jsouvyznačeny přechody k sousedńım neuron̊um, takže je obrázek informativněǰśı, než kdyby bylzhuštěný, jak se občas vyskytuje, a jedno poĺıčko představovalo jeden neuron. B́ılé a černétečky a č́ısla označuj́ı neurony, č́ısla jsou názvy, přidělené vektor̊um ve vstupńıch datech (má-livstupńı vektor 10 položek, je 11. sloupec dat brán jako jeho název).

Existuj́ı r̊uzné variace u-matice, snaž́ıćı se překonat některé jej́ı nevýhody nebo poskytuj́ıćıjinou informaci (např. p-matice, u*-matice).

Obrázek 2.13: U-matice pro śıt’ 10 x 10

16 KAPITOLA 3. PŘEDZPRACOVÁNÍ DAT - TEORETICKÁ ČÁST

3 Předzpracováńı dat - teoretická část

Źıskáváńı znalost́ı je proces, který se provád́ı v několika kroćıch. Tyto kroky se mohou provádětv iteraćıch. Jelikož máme data nejr̊uzněǰśıho druhu a ty často bývaj́ı tzv. zašumělá nebo nekon-zistentńı. Častým problémem pro dolováńı dat je chyběj́ıćı hodnota atributu. Tyto problémymohou vznikat vlivem lidského faktoru, ztrátou dat nebo integraćı z r̊uzných datových soubor̊u.Podstatným krokem v tomto procesu je proto čǐstěńı a integrace dat.

Čǐstěńı, integrace, výběr a transformace se souhrnně označuj́ı jako předzpracováńı dat. Čǐstěńıdat slouž́ı k odstraněńı zašuměných a nekonzistentńıch dat. Integrace dat je krokem, kterýspojuje data z r̊uzných zdroj̊u do jednoho zdroje. Transformace dat provád́ı transformaci data upravuje data tak, aby byla vhodná pro dolovaćı metody (např. normalizace hodnot můžezlepšit výsledek dolováńı). Výběr dat zmenšuje objem dat pro dolováńı, např́ıklad pomoćıagregace, shlukováńım, nebo odstraněńım nezaj́ımavých atribut̊u. Předzpracováńı dat můževýrazně zlepšit kvalitu vydolovaných vzor̊u a t́ım i výsledek dolováńı. Obecně plat́ı, že data,která chceme použ́ıt pro dolováńı, muśı co nejpřesněji modelovat realitu, kterou reprezentuj́ı,být konzistentńı, d̊uvěrná, aktuálńı, dostupná a prospěšná pro danou úlohu.Správné předzpracováńı dat je d̊uležité pro źıskáńı co nejlepš́ıch výsledk̊u a zab́ırá také velkémnožstv́ı času.

3.1 Čǐstěńı dat

Jedná se o odstraněńı problémů nekompletńıch, zašumělých nebo chyběj́ıćıch hodnot. Důvodemtěchto problémů může být porucha na př́ıstroji pro sběr dat, lidský faktor, chyba komunikačńıhokanálu apod. Úkolem čǐstěńı dat je doplněńı chyběj́ıćıch atribut̊u, vyhlazeńı zašumělých hodnot,odstraněńı extrémńıch hodnot a vyřešená konzistence. Tento proces neńı jednopr̊uchodový, aleiterativńı. Určitý krok čǐstěńı může mı́t za následek opakováńı některého předchoźıho kroku.Např́ıklad při odstraněńı nekonzistence, může vzniknout potřeba pro odstraněńı chyběj́ıćı hod-noty.

3.1.1 Nekompletńı data

Velmi častým problémem je chyběj́ıćı hodnota atributu, který však může reprezentovat d̊uležitéinformace pro proces dolováńı. Existuje několik metod pro ošetřeńı chyběj́ıćıch hodnot.

• Ignorováńı položky – tato metoda je vhodná pouze v př́ıpadě, pokud v prvku relacechyb́ı některé daľśı atributy (nelze odvodit chyběj́ıćı hodnotu atributu) nebo v př́ıpaděčǐstěńı dat pro klasifikaci.

• Manuálńı doplněńı chyběj́ıćı hodnoty – metoda by byla vhodná, ale většinou kv̊ulivelkému množstv́ı dat je prakticky nepoužitelná. Uživatel by rovněž musel mı́t znalosti,které by uplatnil při nahrazováńı.

• Automatické doplněńı globálńı konstantou – použ́ıvá se hodnota mimo rozsahplatných hodnot daného atributu (např. 0 nebo ∞ pro numerický atribut). Pokud byvýskyt této odlehlé hodnoty byl ńızký, algoritmus pro dolováńı j́ı může ignorovat, alev př́ıpadě častého výskytu může tato metoda negativně ovlivnit výsledek dolováńı. Algo-ritmus by mohl tuto konstantu brát za d̊uležitou a chybně ji interpretovat jako stěžejńı.

• Použit́ı pr̊uměrné hodnoty atributu – hodnota pro automatické doplňováńı sevypoč́ıtá jako pr̊uměr z hodnot atribut̊u v ostatńıch prvćıch.

KAPITOLA 3. PŘEDZPRACOVÁNÍ DAT - TEORETICKÁ ČÁST 17

• Použit́ı pr̊uměrné hodnoty n-tic stejné tř́ıdy – je použita pr̊uměrná hodnota atri-butu z relaćı, které patř́ı do stejné tř́ıdy. Např́ıklad v př́ıpadě tř́ıdy vzděláńı=“vysokoškolské“se použije pr̊uměrná hodnota atributu př́ıjem z pr̊uměru hodnot relaćı, které spadaj́ı dotéto tř́ıdy.

• Doplněńı nejpravděpodobněǰśı hodnotou – tato hodnota může být vypočtenapoužit́ım odvozovaćıch nástroj̊u jako je Bayesovská klasifikace, regrese apod. Jedná sevlastně o klasifikaci nebo predikci s doplňovaným atributem jako ćılem. Metoda se jev́ıjako nejlepš́ı, protože nejv́ıce zohledňuje okolńı informace, z nichž je doplňuj́ıćı hodnotapoč́ıtána.

3.1.2 Zašumělá data

Jedná se o náhodné chyby v datech. Důvod̊u pro zašuměné hodnoty může být v́ıce. Většinou jdeo chyby vzniklé poruchou na zař́ızeńı pro sběr dat, lidským faktorem, špatným ohodnoceńım,poruchou hardware nebo použit́ım r̊uzných formát̊u pro kódováńı. Techniky, které prováděj́ıvyhlazeńı dat, jsou uvedeny ńıže.

• Plněńı – vyhlazováńı numerických dat je prováděno tak, že setř́ıděná posloupnost zo-hledňuje hodnoty v bĺızkém okoĺı. Tato technika provád́ı lokálńı vyhlazeńı. Setř́ıděné hod-noty se rozděĺı do tzv. koš̊u stejné frekvence. Hodnoty v koš́ıch se pak nahrad́ı pr̊uměremkoše, mediánem koše nebo hraničńı hodnotou koše.

• Regrese – data se nahrazuj́ı hodnotami, které jsou dány regresńı křivkou. Lze použ́ıtlineárńı nebo v́ıcenásobnou lineárńı regresi.

• Rozděleńı do shluk̊u (tzv. shlukováńı) – nalezeńı odlehlých hodnot, které nelze zařaditdo žádného shluku. Intuitivně mohou být hodnoty, které spadnou mimo grupu, brányjako zbloudilé.

• Kombinovaná poč́ıtačová a ručńı kontrola - expertńı systém urč́ı potenciálńı od-lehlé hodnoty detekćı překročeńı určitého prahu. Ručńı kontrolou se z nich pak vyberouskutečné chybné hodnoty.

Metody pro odstraňováńı šumu z dat můžeme rovněž chápat i jako metody pro redukci dat.Lze je použ́ıt i pro diskretizaci hodnot. Pož́ıvá se metoda pro rozčleněńı na intervaly stejnéš́ı̌rky nebo rozčleněńı na intervaly stejné hloubky.

3.2 Integrace a transformace dat

Jedná se o spojeńı dat z několika nezávislých úložǐst’ do jednoho a vytvořeńı jednoho konzis-tentńıho zdroje. V př́ıpadě integrace dat jde o nalezeńı atribut̊u r̊uzných vstup̊u, které k soběpatř́ı. Např́ıklad atribut pro identifikaci zbož́ı může být v jedné databázi (datech) nazvánitem id v druhé jako iid. Tento problém se označuje jako konflikt schématu. Daľśı podstatnoučást́ı procesu integrace je odstraněńı redundance. To znamená odstraněńı dat, která jsou dupli-citńı ale i taková, která se daj́ı odvodit z jiných uložených dat. Redundance se daj́ı detekovatz metadat, ale v datech se může vyskytnout i silná korelace, která se detekuje tzv. korelačńıanalýzou. Daľśım problémem, s kterým se muśı integrace vypořádat, je konflikt hodnot, kdyjsou odpov́ıdaj́ıćı si hodnoty atribut̊u r̊uzné, a konflikt identifikace, kdy v r̊uzných úložǐst́ıch jeidentifikace objekt̊u r̊uzná (např. rodné č́ıslo a pořadové č́ıslo u osob). Ve fázi transformace sedata transformuj́ı tak, aby lépe vyhovovala dolovaćım metodám a charakteru dolovaćı úlohy.Operace, které můžou být zahrnuty ve fázi transformace:

18 KAPITOLA 3. PŘEDZPRACOVÁNÍ DAT - TEORETICKÁ ČÁST

Obrázek 3.1: Př́ıklad rozděleńı do shluk̊u

• Vyhlazeńı – odstraněńı šumu.• Agregace – aplikuj́ı se sumačńı nebo agregačńı funkce typické pro plněńı datového so-

boru. Obvykle se provád́ı při plněńı datové kostky pro analýzu na vyšš́ı úrovni abstrakcea slouž́ı rovněž jako redukce dat, např. denńı př́ıjmy sloučené, aby se mohly vypoč́ıtatměśıčńı a ročńı př́ıjmy.

• Generalizace – nahrazeńı hodnoty atributu jejich obecněǰśı hodnotou jako u hierarchiekoncept̊u, např. jednoduchý atribut jako je věk může být mapován na vyšš́ı úroveň jakonezletilý, dospělý...

• Normalizace dat – jde o transformaci hodnot tak, že spadaj́ı do určitého intervaluhodnot (typicky je to < 0.0, 1.0 >). Normalizace se provád́ı typicky u neuronových śıt́ı,shlukováńı a metody nejbližš́ıho souseda, protože by mohlo doj́ıt k negativńımu ovlivněńıvýsledku dolováńı. Normalizace většinou zabráńı tomu, aby atribut s velkým rozsahemhodnot překryl svým významem atributy s menš́ım rozsahem hodnot. Existuje celá řadametod pro normalizaci, ale nejčastěǰśı jsou min-max normalizace (lineárńı transformace),z-score (normalizace na základě pr̊uměru a odchylky) a dekadickou změnou měř́ıtka (po-sunut́ı desetinné čárky tak, aby obor hodnot ležel v požadovaném rozsahu).

3.3 Redukce dat

Jelikož je dolováńı nad velkým množstv́ım dat časově a výpočetně náročné, je žádoućı zdrojovádata vhodným zp̊usobem redukovat. Vhodným zp̊usobem rozumı́me tak, že informace obsaženáv datech se nezměńı nebo nezměńı se charakter dat a je zachována integrita dat. Použ́ıvá sezpravidla 5 technik pro redukci dat:

1. Agregace datové kostky – sumarizace p̊uvodńıch dat. Technika kde jsou operace apli-kované na data, tak aby se seskupila do několikarozměrné datové krychle.

2. Odstraněńı dimenze – provád́ı se, pokud je dimenze pro analýzu nepodstatná nebomálo podstatná. Kĺıčovým faktorem je správné zvoleńı množiny atribut̊u pro redukci. Jenutné znát doménu a význam uložených dat včetně závislost́ı.

KAPITOLA 3. PŘEDZPRACOVÁNÍ DAT - TEORETICKÁ ČÁST 19

3. Redukce počtu hodnot – data jsou nahrazena modelem a reprezentována parametry.

4. Komprese dat – ztrátová či bezztrátová komprese dat.

5. Diskretizace a použit́ı konceptuálńı hierarchie – hodnoty atribut̊u jsou nahrazenyhodnotami z interval̊u nebo hodnotami z nějaké konceptuálńı hierarchie. Redukuje sepočet r̊uzných hodnot atribut̊u.

Množina dat může obsahovat stovky atribut̊u, ze kterých je spousta nerelevantńıch nebo redun-dantńıch pro dobýváńı znalost́ı. Např. při klasifikaci zákazńık̊u, kteř́ı si nejsṕı̌se kouṕı novouplazmovou televizi, je atribut telefonńı č́ıslo nepodstatný na rozd́ıl od atribut̊u plat či věk.Vynecháńı relevantńıch atribut̊u nebo ponecháńı zbytečných může zp̊usobit zmateńı procesudobýváńı znalost́ı nebo jeho zpomaleńı.Redukce dimenze snižuje velikost dat odstraňováńım atribut̊u. Typicky se aplikuj́ı metodyvýběru podmnožiny atribut̊u. Ćılem je nalézt minimálńı podmnožinu atribut̊u takovou, žerozložeńı pravděpodobnost́ı tř́ıd je co nejbĺıže p̊uvodńımu obsazeńı atribut̊u. Sńıžeńı počtuatribut̊u také zjednodušuje pochopeńı nalezených vzor̊u.V množině d atribut̊u existuje d2 r̊uzných podmnožin. Hledáńı nejlepš́ı podmnožiny hrubousilou je časově náročné. Proto se použ́ıvaj́ı r̊uzné heuristiky, převážně na bázi hladových al-goritmů, tj. při prohledáváńı vyb́ıraj́ı podle nejlepš́ı možnosti v daném okamžiku. Strategíıje přijmout lokálně optimálńı krok ve snaze naj́ıt globálńı optimum. V praxi jsou tyto me-tody efektivńı. Kvalita atribut̊u se určuje statistickými testy, předpokládá se, že jsou nezávislé.Základńı heuristické metody jsou zobrazeny na obrázku 3.2

Obrázek 3.2: Metody výběru podmnožiny atribut̊u

1. Dopředný výběr: zač́ıná se s prázdnou množinou atribut̊u. V každém kroku se vlož́ınejlepš́ı atribut ze zbývaj́ıćıch v p̊uvodńı množině.

2. Zpětná eliminace: zač́ıná se s úplnou p̊uvodńı množinou atribut̊u. V každém kroku seodstrańı nejhorš́ı atribut z množiny.

3. Kombinovaný dopředný a zpětný běh: kombinace předchoźıch, kdy se v každémkroku přidá nejlepš́ı a odstrańı nejhorš́ı atribut.

4. Rozhodovaćı stromy: každý vnitřńı uzel stromu obsahuje test atributu, každá větevodpov́ıdá výsledku testu a každý list znamená výsledek predikce tř́ıdy. Atributy ve stromujsou redukovanou podmnožinou atribut̊u a ostatńı jsou irelevantńı.

20 KAPITOLA 3. PŘEDZPRACOVÁNÍ DAT - TEORETICKÁ ČÁST

3.3.1 Početńı redukce

Početńı redukce slouž́ı k sńıžeńı počtu dat volbou alternativńı formy reprezentace dat. Metodymohou být parametrické, kdy se data vyjádř́ı jejich modelem a uchovaj́ı se jen jeho parametry(př́ıpadně i odlehlé hodnoty). Neparametrické metody jsou histogramy, shlukováńı a vzorkováńı.

Regresńı metoda - V lineárńı regresńı metodě jsou data modelována, aby odpov́ıdala př́ımce.Podle rovnice y = ax + b je hodnota y předpov́ıdaná podle hodnoty x. Parametry a a b se urč́ımetodou nejmenš́ıch čtverc̊u, aby odchylka předpov́ıdané hodnoty od skutečné byla minimálńı.

Histogramy - Histogram atributu A rozděĺı data do disjunktńıch množin. Množiny jsou zob-razeny na vodorovné ose, výška odpov́ıdá pr̊uměrné četnosti prvk̊u v množině. Množiny mohoubýt i jednoprvkové.Zp̊usob rozděleńı hodnot atributu do množin může proběhnout několika zp̊usoby:

1. Konstantńı š́ı̌rka: velikost množiny je volena konstantně.

2. Konstantńı výška: množiny jsou voleny tak, aby četnost prvk̊u v každé množině bylapřibližně stejná.

3. V-optimálńı: pro daný počet množin je histogram volen tak, aby vážený součet p̊uvodńıchdat byl nejmenš́ı. Váha v množině je počet hodnot v ńı.

4. MaxDiff: uvažuj́ı se rozd́ıly mezi každým párem sousedńıch hodnot. Hranice množiny jevytvořena mezi každým párem, pro páry maj́ıćı β − 1 největš́ıch rozd́ıl̊u, β je uživatelskydefinovaná.

Shlukováńı - Metody shlukováńı rozčleňuj́ı seznam objekt̊u do skupin tak, aby v rámcijedné skupiny byly objekty podobné a odlǐsné od objekt̊u v jiné skupině. Podobnost od-pov́ıdá vzdálenosti objekt̊u v prostoru. Vlastnost́ı skupiny je pr̊uměr, který odpov́ıdá největš́ıvzdálenosti mezi dvěma objekty ve skupině, a vzdálenost od těžǐstě, která odpov́ıdá pr̊uměrnévzdálenosti objekt̊u od těžǐstě skupiny (pr̊uměrný objekt ve skupině).

Vzorkováńı - Umožňuje redukovat data výběrem náhodného vzorku p̊uvodńıch dat. Z velkéhoobjemu dat D obsahuj́ıćıho N položek můžeme vybrat vzorek několika zp̊usoby:

1. Náhodný výběr vzorku bez nahrazeńı: z množiny D se náhodně vybere n < N prvk̊u,kdy pravděpodobnost výběru každého je 1/N .

2. Náhodný výběr vzorku s nahrazeńım: podobné předchoźımu s t́ım, že prvky mohou býtvybrány několikrát.

3. Vzorek ze shluk̊u: pokud jsou položky v D uspořádány do M disjunktńıch množin, pakaplikaćı předchoźıch metod vybereme m < M skupin.

4. Rozvrstvený vzorek: pokud je D rozděleno do několika disjunktńıch vrstev (vrstvamůže být např. věková skupina u zákazńıka), pak je rozvrstvený vzorek źıskán aplikaćınáhodného výběru pro každou vrstvu. T́ımto máme zaručeno, že i málo početná vrstvabude zastoupena.

Výhodou metody vzorkováńı je, že časová složitost záviśı na n a nikoli na velikosti p̊uvodńıchdat N. Ostatńı metody redukce dat potřebuj́ı alespoň jeden pr̊uchod přes množinu D. Vzor-kováńı je přirozenou metodou redukce dat. Chybu můžeme snadno korigovat volbou velikostipočtu vzork̊u n.

KAPITOLA 3. PŘEDZPRACOVÁNÍ DAT - TEORETICKÁ ČÁST 21

3.4 Daľśı možné metody předzpracováńı

Představme si stručně ještě některé daľśı metodu předzpracováńı dat.

PCA Principal Component Analysis (česky analýza hlavńıch komponent) v sobě zahrnuje dvadruhy předzpracováńı. V prvńım kroku transformuje data do nového souřadného systémutak, že hodnoty na prvńı ose (hlavńı komponentě) maj́ı největš́ı rozptyl, hodnoty na druhéose maj́ı druhý největš́ı rozptyl, a tak dále. Nové souřadnice jsou vždy nějakou lineárńıkombinaćı souřadnic p̊uvodńıch a nemaj́ı žádný fyzikálńı význam. Druhý, volitelný krokspoč́ıvá v redukci počtu atribut̊u. Ten můžeme např́ıklad zvolit pevně, tedy tak, že poprvńım kroku vybereme pouze prvńıch k komponent. Druhou variantu představuje volbaproměnného počtu komponent na základě splněńı nějakého kritéria.

FastICA Jedná se o implementaci metody ICA (Independent Component Analysis, analýzanezávislých komponent), jej́ıž myšlenka je následuj́ıćı. Metoda předpokládá, že data, kterámáme, respektive jejich atributy, vznikly lineárńı kombinaćı jiných, vzájemně nezávislýchatribut̊u (nezávislých komponent). Algoritmus se snaž́ı naj́ıt zpětnou transformaci tak,aby dostal opět ”p̊uvodńı” nezávislé komponenty. Metoda, p̊uvodně vyvinutá hlavně prozpracováńı signálu, lze použ́ıt i pro jiná data než jen časové pr̊uběhy. Známa je např́ıkladukázka odstraněńı šumu z obrázku, ale i jiné.

Feature selection Takto jsou souhrnně označovány metody, které se ze souboru atributu snaž́ıvybrat ty, které jsou z hlediska struktury dat nejvýznamněǰśı, a ty nepodstatné vynechat.T́ım se ulehč́ı práce uč́ıćımu algoritmu, který se ”může soustředit” na podstatné atributy anezatěžovat se méně podstatnými. Úvodńı náhled do této problematiky přináš́ı např́ıklad[Guyon, Elisseeff, 03], podle [Zelenka, 07] .

22 KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ

4 Výsledky experiment̊u

V této kapitole budou postupně popsány jednotlivé metody (které byly popsány výše) spolus výsledky experiment̊u nad antropologickými daty.

4.1 Prediktivńı metody

4.1.1 GMDH

Výpočty pro odhad stář́ı kostry jsem prováděl v programu KnowledgeMiner 5 v rámci své ba-kalářské práce. Nebot’ je program určen pro platformu Mac, bylo zapotřeb́ı mı́t program spuštěnpod emulátorem, což nebyl problém a výpočty prob́ıhaly bez problémů. Všechny experimentybyly prováděny pro śıt’ GMDH, která je v tomto software ještě vylepšena o to, že neurony ne-musej́ı mı́t jenom 2 vstupy, ale i lichý počet, např́ıklad 1. Dále bylo použito vylepšeńı nazvanélayer-break-through, které znamená to, že jednotlivé neurony nemusej́ı být propojeny jenomv sousedńıch vrstvách, ale i v mezilehlých. Což je znázorněno na obrázku 4.1

Obrázek 4.1: Výsledný GMDH model v KnowledgeMiner softwaru za použit́ı vylepšeńı layer-break-trough

Experimenty byly prováděny na dvou množinách testovaćıch a trénovaćıch dat (train/test 1a train/test2), za účelem vyloučeńı nerovnoměrného rozložeńı hodnot v trénovaćı a testovaćımnožině. Jako výstupńı ukazatel pro úspěšnost odhadu stář́ı kostry byla zvolena modifikovanáhodnota RMS (Root mean squared error). Ta se poč́ıtá podle vzorce 4.1

RMS =1N

√√√√N∑

i=1

(y − d)2i (4.1)

Kde: N – počet použitých vzork̊u, y – výstupńı vypoč́ıtaná hodnota, d – skutečná hodnota

Výsledky práce se śıt́ı GMDH jsou vidět v tabulce 4.1. V této tabulce je vidět několik kon-figuraćı, s nimiž byly vytvářeny modely. Bylo vybráno 8 nejlepš́ıch konfiguraćı. Jednotlivékonfigurace jsou popsány v mé bakalářské práci [Novák, 06]. Stěžejńı jsou hodnoty chyby RMS.Bohužel z výsledk̊u je patrné, že chyba neńı zanedbatelná (pr̊uměrně kolem 0,68-0,69). Z tohoplyne, že data jsou velmi zašumělá, č́ımž zanáš́ı do predikce stář́ı chybu. Při procházeńı jednot-livých výsledk̊u predikce stář́ı jsem u některých měřeńı našel odchylku i 30 let.Nicméně je metoda GMDH k určováńı stář́ı dobrým nástrojem. Bohužel z antropologickýchdat nejsme schopni dostat lepš́ı výsledky v d̊usledku zanesených nepřesnost́ı.

KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ 23

Configuration Train 1 Test 1 Train 2 Test 2 Testavgconfig 1 0,45773 0,69570 0,46431 0,67458 0,68514config 2 0,47688 0,71613 0,46795 0,66152 0,68883config 3 0,47670 0,71094 0,46771 0,66193 0,68643config 4 0,46646 0,70330 0,46917 0,66177 0,68253config 5 0,53752 0,77992 0,55504 0,72760 0,75376config 6 0,45780 0,69291 0,46367 0,67290 0,68290config 7 0,45417 0,69027 0,46110 0,67421 0,68224config 8 0,44980 0,70599 0,45575 0,66131 0,68365

Tabulka 4.1: Určováńı věku kostry - RMS chyba GMDH model̊u

4.1.2 GAME

Tato metoda neuronových śıt́ı byla testována pomoćı stejnojmenného softwaru GAME. Ten bylvyvinut na naš́ı katedře Pavlem Kord́ıkem. Nyńı je program běžně použ́ıván a na jeho vývojise stále pracuje a pod́ıĺı se na něm celá řada lid́ı.

Výsledky testováńı provedené Pavlem Kord́ıkem jsou patrné z tabulky 4.2:

Model Train 1 Test 1 Train 2 Test 2 TestavgGAME 0,458 0,660 0,455 0,679 0,669GAME 0,458 0,659 0,455 0,679 0,669GMDH 0,454 0,690 0,461 0,674 0,682GMDH 0,449 0,705 0,455 0,661 0,683

Tabulka 4.2: Srovnáńı výsledk̊u GMDH a GAME

Zde jsou vybrány dva nejlepš́ı výsledky GMDH śıtě, spolu s dvěma nejlepš́ımi z GAME śıtě. Jepatrné, že rozd́ıly nejsou př́ılǐs veliké. To je dáno také d́ıky tomu, že KnowledgeMiner má v soběimplementovány pokročileǰśı funkce śıtě GMDH, které se v určitých ohledech podobaj́ı śıt́ımGAME. Nicméně o něco lépe dopadla śıt’ GAME. Výsledky jsou interpretovány opět pomoćıRMS, jako je tomu v předchoźı metodě. Je patrné, že i zde je chyba nezanedbatelná a odhado-vaný věk neńı př́ılǐs přesný. Nicméně to neznamená, že by metoda GAME nebyla vhodná, banaopak. Bohužel data nesou velkou nepřesnost.

Projevilo se zde i to, že nástroj GAME je v́ıce vědeckým a má mnohem větš́ı možnosti nastaveńıoproti programu KnowledgeMiner. Č́ımž lze také velmi zjemnit nastaveńı experiment̊u a t́ımje i zpřesnit. Proto jsou výsledky lepš́ı. Nicméně to sebou také nese nutnost znát podrobnějidanou problematiku, aby bylo dosaženo kvalitńıho nastaveńı.

Obě metody GMDH a GAME se ukázaly jako velmi kvalitńı nástroje k źıskáváńı znalost́ı z dat.GAME prokázal kvalitněǰśı výstupy a proto ho lze doporučit jako vhodného kandidáta při prácis lineárńı regreśı.

4.2 Klasifikačńı metody

V této sekci je mým ćılem shrnout a porovnat výsledky z jiných praćı, které se také zabývalyexperimenty s antropologickými daty, zhodnotit jednotlivé výsledky pro každou metodu a poté

24 KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ

Parametr LVQ1initialisation K-nearest neighbour evenlearning function linear decaylearning rate 0,25neurons 250training iterations 7600use voting falsewindow size -

Tabulka 4.3: Parametry śıtě LVQ1

všechny vzájemně porovnat a doporučit nejvhodněǰśı. Což je shrnuto a porovnáno v kapitoleZhodnoceńı výsledk̊u na straně 41.

Výsledky jednotlivých metod se daly dobře porovnávat, protože jsou stejně hodnoceny a bylopoužito rozděleńı ro stejných klasifikačńıch tř́ıd.

4.2.1 LVQ

Při testech provedených pomoćı LVQ1 na antropologických datech bylo použito rozděleńı donásleduj́ıćıch věkových kategoríı:

1. Původńı věkové kategorie, tj. věk úmrt́ı < 29, 30 − 39, 40 − 49, 50− 59, 60− 69 a > 70(T1 ).

2. Věkové kategorie < 29, 30− 49, > 50 (T2 ).3. Věkové kategorie < 29, 30− 59, > 60 (T3 ).

Uvažovat populaci pocházej́ıćı z Evropy:

• Celá populace.• Pouze populace pocházej́ıćı z Evropy, tedy tř́ıdy Port (Portugalci), Suis (Švýcaři), Spain

(Španělé), USAE (přistěhovalci do USA), Africaner (afrikánci - potomci holandskýchpřistěhovalc̊u žij́ıćı v Jižńı Africe).

Zkoumat pouze jedno pohlav́ı:

• Obě pohlav́ı.• Jen muži.• Jen ženy.

Celkem bylo použito 3 · 2 · 3 = 18 soubor̊u dat, které byly vygenerovány z p̊uvodńıch dat obsa-huj́ıćıch všechny atributy.

Experimenty byly provedeny pomoćı softwarového nástroje WEKA. Protože ten ale neobsahujealgoritmy pro neuronové śıtě typu LVQ, bylo třeba je doplnit formou plug-inu. Parametry všechśıtě byly vždy nastaveny tak, aby dávaly pro p̊uvodńı sadu dat co nejlepš́ı výsledky (nastaveńıje patrné z tabulky 4.3, tj. co největš́ı procento úspěšně ohodnocených testovaćıch dat. Dálebyla použita 10-ti foldová cross-validace.

KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ 25

Obrázek 4.2: LVQ - celkový přehled úspěšnosti ohodnoceńı

EvropanéKategorie obě pohlav́ı ženy muži obě pohlav́ı ženy muži

T1 38,4% 40,5% 35,8% 40,1% 46,6% 38,2%T2 68,6% 68,6% 65,8% 71,1% 71,5% 72,0%T3 69,6% 70,6% 65,3% 69,9% 73,3% 63,2%

Tabulka 4.4: LVQ1 - procentuálńı úspěšnost klasifikace

Výsledky experiment̊u jsou vidět z grafu správně ohodnocených instanćı 4.2. Ṕısmeno m v grafuznamená, že ve vstupńıch datech byli pouze muži, f jen ženy a e jen Evropané. Je zde pěkněvidět rozptyl správně zařazených jedinc̊u v rámci měřené skupiny. Dále si lze všimnout skokumezi určováńım hodnot do v́ıce menš́ıch skupin oproti menš́ımu počtu skupin. Rozd́ıl mezitř́ıdami T1 oproti T2 + T3.

Dále v tabulce 4.4 jsou shrnuty výsledky výpočt̊u. Jsou brány jako pr̊uměr z 5 měřeńı. Je patrné,že při rozděleńı do v́ıce věkových skupin odhad věku do správně skupiny neńı př́ılǐs přesný(38,4%). Pokud, ale sńıž́ıme počet skupin a t́ım velikost jednotlivých kategoríı rozš́ı̌ŕıme, odhadse zpřesńı. To je patrné u výsledk̊u skupin T2 a T3. Dále je vidět, že rozděleńı podle pohlav́ına muže a ženy nepřináš́ı př́ılǐsné zlepšeńı, i když u žen je klasifikace o pár procent přesněǰśı.Klasifikace pouze Evropan̊u přináš́ı již o něco patrněǰśı zlepšeńı oproti použitým celým dat̊um.Výsledky měřeńı podle [Augustýn, 07].

4.2.2 Perceptron

Experimenty byly prováděny opět v programu WEKA, na dvou druźıch v́ıcevrstvé śıtě per-ceptron, automaticky generované a minimálńı. Testy byly prováděny pomoćı cross-validation,množina vzorku se náhodně rozdělila do deseti stejně velkých skupin (Fold) a následně se po-stupně vyb́ırala jedna skupina a ta se použila jako uč́ıćı a ostatńı skupiny sloužily jako testovaćı.Tento postup se prováděl tak dlouho, dokud každá skupina nebyla v pozici uč́ıćı množiny. Každýtest byl proveden 6 krát a pokaždé byly vzorky rozděleny do skupin r̊uzně.

26 KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ

Vstupńı data byly rozděleny stejně jako u śıt́ı typu LVQ. Tedy na skupiny T1 - T3, rozděleńıpodle pohlav́ı a Evropany.

Parametry nastaveńı:

1. Automaticky generovaná śıt’ Parametry śıtě generoval automaticky pro každou vstupńımnožinu software WEKA. Parametry śıtě pro jednotlivé vstupńı množiny (vstupńı vrstva- skrytá vrstva - výstupńı vrstva) jsou vidět v tabulce 4.5

T1 21-13-6 T3 21-12-3T1e 16-11-6 T3e 16-9-3T1ef/T1em 15-10-6 T3ef/T3em 15-9-3T1f/T1m 20-13-6 T3f/T3m 20-11-3T2 21-12-3T2e 16-9-3T2ef/T2em 15-9-3T2f/T2m 20-11-3

Tabulka 4.5: Parametry automaticky generované śıtě

2. Minimálńı śıt’ Parametry śıtě vycházej́ı z automaticky generované śıtě, jen počet neu-ron̊u ve skryté vrstvě byl sńıžen na minimum. Tedy stejný jako počet neuron̊u ve výstupńıvrstvě. Parametry śıtě jsou v tabulce 4.6.

T1 21-6-6 T3 21-3-3T1e 16-6-6 T3e 16-3-3T1ef/T1em 15-6-6 T3ef/T3em 15-3-3T1f/T1m 20-6-6 T3f/T3m 20-3-3T2 21-3-3T2e 16-3-3T2ef/T2em 15-3-3T2f/T2m 20-3-3

Tabulka 4.6: Parametry minimálńı śıtě

Výsledky experimentu jsou vyhodnoceny pomoćı pr̊uměru šesti experiment̊u nad jedńımvstupńım souborem. Hodnoty jsou uvedeny v tabulce 4.7 a 4.11. Druhý zp̊usob je pomoćıgraf̊u 4.3 a 4.4, které nejen znázorňuj́ı pr̊uměrnou hodnotu, ale zároveň je možné vidět i rozptyljednotlivých hodnot.

EvropanéKategorie obě pohlav́ı ženy muži obě pohlav́ı ženy muži

T1 36,6% 36,2% 37,9% 38,5% 36,4% 42,3%T2 65,7% 65,4% 64,5% 69,5% 70,1% 68,0%T3 67,0% 64,8% 68,1% 67,7% 60,6% 71,7%

Tabulka 4.7: Pr̊uměrná úspěšnost klasifikace na automaticky generované śıti

Z experiment̊u je vidět, že pokud jsou data rozdělena do šesti věkových kategoríı, tak seúspěšnost klasifikace pohybuje kolem 40%. Situace se znatelně zlepš́ı, pokud data rozděĺıme

KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ 27

Obrázek 4.3: Rozptyl úspěšnosti klasifikace pomoćı automaticky generované śıtě

EvropanéKategorie obě pohlav́ı ženy muži obě pohlav́ı ženy muži

T1 37,4% 35,0% 38,6% 40,2% 35,2% 41,3%T2 66,0% 66,3% 66,4% 71,6% 70,8% 68,5%T3 67,6% 65,3% 69,8% 69,6% 62,9% 75,0%

Tabulka 4.8: Pr̊uměrná úspěšnost klasifikace na minimálńı śıti

pouze do tř́ı věkových kategoríı. V tomto př́ıpadě už se úspěšnost klasifikace pohybuje mezi60% a 70%. Také se ukázalo, že pokud použijeme jen populace pocházej́ıćı pouze z Evropy,úspěšnost klasifikace se nepatrně zvýš́ı (kolem 1 az. 5%). Rozděleńı na mužské a ženské po-hlav́ı přináš́ı nejednoznačné výsledky, v některých př́ıpadech se úspěšnost klasifikace zvýšila, av některých dokonce poklesla. Posledńım experimentem se śıt́ı perceptron byl vliv počtu neu-ron̊u ve skryté vrstvě na úspěšnost klasifikace a ukázalo se, že při sńıžeńı počtu neuron̊u sicev pr̊uměru úspěšnost nepatrně vzrostla, ale zato znatelně vzrostl rozptyl jednotlivých hodnot,[Prchĺık, 07]

Z experiment̊u je vidět, že dopadly hodně podobně jako śıt LVQ. A i závěr z tohoto vyhodnoceńıje, že určováńı do větš́ıho počtu menš́ıch věkových skupin je méně přesné než do méně s větš́ımrozpět́ım. Což je vcelku logický výsledek.Na jednu stranu je dobře, že testy dopadly podobně jako u předchoźı metody LVQ, protožesi tak vzájemně potvrzuj́ı výsledky. Na druhou stranu by bylo výhodněǰśı, kdyby některá siporadila s AD lépe a podala přesněǰśı určováńı do dané skupiny.

4.2.3 RBF

I zde byl použit program WEKA a stejné rozděleńı antropologických dat jako v předchoźıchdvou metodách. Zastoupeńı věkových tř́ıd pro skupinu T1 shrnuje tabulka 4.9.

Použitý simulátor Weka 3.4.11 má implementovánu normalizovanou Gaussovskou RBF śıt’ a

28 KAPITOLA 4. VÝSLEDKY EXPERIMENTŮ

Obrázek 4.4: Rozptyl úspěšnosti klasifikace pomoćı minimálńı śıtě

Tř́ıda 70Počet 115 168 189 176 149 156

Zastoupeńı 12,0% 18,6% 19,8% 18,4% 15,6% 16,4%

Tabulka 4.9: Zastoupeńı ve věkových tř́ıdách

použ́ıvá standardńı algoritmus K-means.Uživatel má možnost pro RBF śıt’ nastavit na následuj́ıćı parametry:

• numClusters n - Počet shluk̊u, které by měl vygenerovat algoritmus K-means. Početshluk̊u je třeba odhadnout. Př́ıklad klasifikace pro 2D prostor vstupńıch vektor̊u, kterýobsahuje dva shluky je na obrázku 4.5

• minStdDev σ – minimálńı standardńı odchylka f(x) pro shluky. Parametr σ ovlivňujeurčováńı shluk̊u. Velikost parametru má vliv na to jakým zp̊usobem se śıt’ bude uc