Redukce dat pro data mining a neuronová síť...

I

České vysoké učení technické v Praze

Fakulta elektrotechnická

Diplomová práce

Redukce dat pro data mining a neuronová síť GAME

Bc. Helena Krkošková

Vedoucí práce: Ing. Miroslav Čepek

Studijní program: Elektrotechnika a informatika (magisterský), strukturovaný

Obor: Výpočetní technika – počítačové sítě a internet

květen 2009

ii

iii

Poděkování

Ráda bych poděkovala vedoucímu mé diplomové práce Ing. Miroslavu Čepkovi za podnětné

rady, čas strávený konzultacemi a jeho trpělivost. Také bych chtěla poděkovat kamarádce Jitce

Závadové, která byla vţdy skvělou kolegyní. V neposlední řadě bych ráda poděkovala své rodině za

veškerou podporu.

iv

Prohlášení

Prohlašuji, ţe jsem svou diplomovou práci vypracovala samostatně a pouţila jsem pouze

podklady uvedené v přiloţeném seznamu.

Nemám závaţný důvod proti uţití tohoto školního díla ve smyslu § 60 Zákona

č.121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně

některých zákonů (autorský zákon).

V Praze dne 22.5. 2009 ...............................................

v

vi

Abstract

Training of the GAME neural network is very time consuming task. Time required to create a

successful model increases with size of training set. This thesis investigates methods for data

reduction (data condensing). Presented methods reduce number of instances in training set and in

this way methods reduce time required to train GAME neural network and also reduces amount of

memory required during the training process. The important requirement set on condensing

methods is that reduced training set must produce a model with the same or similar accuracy as a

model created on the not reduced set.

Result of this work is implementation of selected methods for data condensing into data

preprocessing module of the FAKE GAME project. The implemented condensing methods were

tested using the GAME neural network and 1 – NN classifier on several real-world and artificial

datasets.

Abstrakt

Učení neuronové sítě GAME je časově velmi náročné. Čas potřebný k vytvoření modelu roste

s velikostí trénovací mnoţiny. Tato diplomová práce se zabývá metodami pro početní redukci dat,

které by problém s rostoucí mnoţinou dat měly odstranit. Jsou zkoumány algoritmy, které podstatně

zmenšují trénovací mnoţinu, čímţ sniţují paměťové nároky a čas potřebný k tvorbě modelu.

Důleţitý poţadavek na tyto metody je, aby model naučený na redukované mnoţině byl stejně

kvalitní jako model naučený na plné trénovací mnoţině.

Výsledkem této práce je implementace zvolených metod pro početní redukci dat do

předzpracovacího modulu projektu FAKE GAME. Úspěšnost implementovaných algoritmů je

testována na neuronové síti GAME a pomocí 1 – NN klasifikátoru na umělých a reálných datech.

vii

viii

Obsah

Seznam obrázků ........................................................................................................................................ xi

Seznam tabulek ....................................................................................................................................... xiii

Seznam pseudokódů ................................................................................................................................ xiv

Část I – Úvod............................................................................................................................................... 1

1. Struktura práce .............................................................................................................................. 1

Část II – Teoretický rozbor ....................................................................................................................... 3

2. Data Mining .................................................................................................................................... 3

2.1 Členění data miningových úloh ................................................................................................... 4

2.1.1 Klasifikace .............................................................................................................................. 4

2.2 Metodologie CRISP-DM ............................................................................................................. 5

3. Předzpracování dat ........................................................................................................................ 7

3.1 Redukce dat ................................................................................................................................. 8

3.1.1 Seskupení do data cube .......................................................................................................... 8

3.1.2 Redukce dimenze ................................................................................................................... 9

3.1.3 Komprese dat ........................................................................................................................ 10

3.1.4 Početní redukce dat .............................................................................................................. 10

3.1.5 Diskretizace dat a generovaných koncepčních hierarchií ..................................................... 11

4. Početní redukce dat...................................................................................................................... 12

4.1 Zaměření algoritmů početní redukce dat .................................................................................. 13

4.1.1 Reprezentace dat................................................................................................................... 13

4.1.2 Směr prohledávání ................................................................................................................ 13

4.1.3 Hraniční pozice vs. centrální pozice ..................................................................................... 15

4.1.4 Hodnotící strategie ............................................................................................................... 15

5. Testované klasifikátory ............................................................................................................... 16

5.1 Pravidlo nejbližšího souseda ..................................................................................................... 16

5.1.1 Algoritmus k – NN ............................................................................................................... 17

5.1.2 Slabé stránky k – NN............................................................................................................ 18

5.2 Neuronové sítě ........................................................................................................................... 19

5.2.1 Inspirace ............................................................................................................................... 19

5.2.2 Umělá neuronová síť ............................................................................................................ 20

5.2.3 Group Method of Data Handling (GMDH) .......................................................................... 20

ix

5.3 Group of Adaptive Models Evolution (GAME) ......................................................................... 21

5.3.1 Nevýhody GAME................................................................................................................. 22

5.3.2 Předzpracování dat v projektu FAKE GAME ...................................................................... 23

Část III – Implementované algoritmy ..................................................................................................... 24

6. Algoritmy početní redukce dat ................................................................................................... 24

6.1 Editační algoritmy ..................................................................................................................... 24

6.1.1 Editované pravidlo nejbliţšího souseda ............................................................................... 24

6.1.2 Editovací schéma All k – NN ............................................................................................... 26

6.2 Neadaptivní kondenzační algoritmy .......................................................................................... 27

6.2.1 Kondenzované pravidlo nejbliţšího souseda ........................................................................ 28

6.2.2 Redukované pravidlo nejbliţšího souseda ............................................................................ 30

6.2.3 Učící algoritmy zaloţené na instancích ................................................................................ 32

6.2.4 Dekrementální redukční optimalizační procedura ................................................................ 36

6.3 Adaptivní kondenzační algoritmy .............................................................................................. 39

6.3.1 Prototypy .............................................................................................................................. 39

6.3.2 Chenův algoritmus ............................................................................................................... 43

6.3.3 Redukce dělením prostoru .................................................................................................... 47

6.4 Vlastní experimentální redukce ................................................................................................. 52

6.4.1 MergeAllInstances................................................................................................................ 52

7. Implementace ............................................................................................................................... 54

7.1 Klasifikátor k - NN .................................................................................................................... 54

7.2 Integrace algoritmů do systému FAKE GAME ......................................................................... 54

Část IV – Testování .................................................................................................................................. 58

8. Testování implementovaných algoritmů .................................................................................... 58

8.1 Popis testovaných dat ................................................................................................................ 58

8.1.1 Umělá data............................................................................................................................ 58

8.1.2 Reálné databáze .................................................................................................................... 60

8.2 Metodika experimentů ............................................................................................................... 61

8.3 Redukce umělých dat ................................................................................................................. 62

8.3.1 Neadaptivní kondenzační algoritmy ..................................................................................... 62

8.3.2 Adaptivní kondenzační algoritmy ........................................................................................ 65

8.3.3 Srovnání algoritmů ............................................................................................................... 73

8.4 Redukce reálných dat ................................................................................................................ 77

8.4.1 Srovnání algoritmů ............................................................................................................... 77

x

8.5 Testování úspěšnosti algoritmu MergeAllInstances .................................................................. 83

8.5.1 MergeAllInstances................................................................................................................ 83

8.6 Testování vlivu na rozdělení dat................................................................................................ 86

8.7 Shrnutí dosažených výsledků ..................................................................................................... 88

Část V – Závěr .......................................................................................................................................... 90

9. Zhodnocení ................................................................................................................................... 90

9.1 Náměty pro budoucí práci ......................................................................................................... 90

Literatura a zdroje ................................................................................................................................... 92

A Seznam pouţitých zkratek .......................................................................................................... 94

B Výsledky redukce umělých dat ................................................................................................... 95

C Uţivatelská příručka .................................................................................................................. 101

D Pomocné skripty ......................................................................................................................... 106

E Obsah přiloţeného CD ............................................................................................................... 107

xi

Seznam obrázků

Obrázek 1: DM nástrojem KDD .................................................................................... 4

Obrázek 2: Učení s učitelem.......................................................................................... 5

Obrázek 3: Ţivotní cyklus CRISP – DM (převzato z [5]) .............................................. 6

Obrázek 4: Metody výběru podmnoţiny atributů (převzato z [4]) ................................. 9

Obrázek 5: Koncepční hierarchie atributu cena ( přezvato z [4]) ................................. 11

Obrázek 6: Kroky procesu početní redukce dat............................................................ 12

Obrázek 7: Klasifikace 1 – NN Obrázek 8: Klasifikace 3 – NN ............................. 17

Obrázek 9: Umělý neuron (převzato z [9]) .................................................................. 19

Obrázek 10: GMDH síť (převzato z [9]) ..................................................................... 20

Obrázek 11: Srovnání MIA GMDH síte se sítí GAME ................................................ 22

Obrázek 12: ENN redukce s k = 1 ............................................................................... 25



Obrázek 15: All k – NN s k = 3 ................................................................................... 26

Obrázek 16: CNN náhodný výběr instance .................................................................. 28

Obrázek 17: CNN klasifikační krok ............................................................................ 29

Obrázek 18: CNN splněna klasifikační podmínka ....................................................... 29

Obrázek 19: Původní mnoţina, CNN podmnoţina a RNN podmnoţina ....................... 31

Obrázek 20: Algoritmus Prototypy .............................................................................. 40

Obrázek 21: Chenův algoritmus, RSP1 algoritmus a RSP3 algoritmus ........................ 44

Obrázek 22: FAKE GAME Preprocessing dialog ........................................................ 55

Obrázek 23: Konfigurace IB3 algoritmu ...................................................................... 55

Obrázek 24: Class diagram modulu algoritmus Prototypy ........................................... 56

Obrázek 25: Uměle vytvořená data Zuby .................................................................... 59

Obrázek 26: Uměle vytvořená data Dvě E ................................................................... 59

Obrázek 27: Uměle vytvořená data Whirpool .............................................................. 60

Obrázek 28: Uměle vytvořená data Šachovnice ........................................................... 60

Obrázek 29: Algoritmus CNN na uměle vytvořených datech Zuby .............................. 63

Obrázek 30: Algoritmus CNN a RNN na uměle vytvořených datech Zuby .................. 63

xii

Obrázek 31: Algoritmus IB3 na umělých datech Zuby ................................................ 64

Obrázek 32: Algoritmus DROP3 na umělých datech Zuby .......................................... 65

Obrázek 33: Algoritmus Prototypy na umělých datech Zuby ....................................... 65

Obrázek 34: Chenův algoritmus na umělých datech Zuby ........................................... 66

Obrázek 35: Algoritmus RSP1 na umělých datech Zuby ............................................. 67

Obrázek 36: Algoritmus RSP1 a RSP3 na umělých datech Zuby ................................. 67

Obrázek 37: Původní data s normálním rozdělením ..................................................... 87

Obrázek 38: Data redukovaná algoritmem IB3 ............................................................ 87

Obrázek 39: Data redukovaná algoritmem CNN ......................................................... 87

Obrázek 40: Otevření Preprocessing dialogu ............................................................. 101

Obrázek 41: Ukázka vstupního formátu dat ............................................................... 102

Obrázek 42: Import vstupních dat ............................................................................. 102

Obrázek 43: Načtení trénovací mnoţiny dat .............................................................. 103

Obrázek 44: Otevření konfigurace Chenova algoritmu .............................................. 103

Obrázek 45: Konfigurační dialog Chenova algoritmu ................................................ 104

Obrázek 46: Export redukované mnoţiny dat ............................................................ 104

xiii

Seznam tabulek

Tabulka 1: Vliv editačních algoritmů na klasifikaci 1 – NN ........................................ 69

Tabulka 2: Vliv editačních algoritmů na neuronovou síť GAME ................................. 71

Tabulka 3: Porovnání algoritmů na umělých datech, 1 – NN klasifikátor..................... 73

Tabulka 4: Porovnání algoritmů na umělých datech, neuronová síť GAME ................. 75

Tabulka 5: Porovnání algoritmů na reálných datech, 1 – NN klasifikátor..................... 77

Tabulka 6: Porovnání algoritmů na reálných datech, neuronová síť GAME ................. 79

Tabulka 7: Neuronová síť GAME s alternativním nastavením ..................................... 82

Tabulka 8: Porovnání vlastního kondenzačního algoritmu, 1 – NN klasifikátor ........... 83

Tabulka 9: Porovnání vlastního kondenzačního algoritmu, neuronová síť GAME ....... 85

Tabulka 10: Porovnání statistických vlastností ............................................................ 87

xiv

Seznam pseudokódů

Pseudokód 1: Algoritmus k – NN ................................................................................ 17

Pseudokód 2: ENN algoritmus .................................................................................... 25

Pseudokód 3: Algoritmus All k – NN .......................................................................... 27

Pseudokód 4: Algoritmus CNN ................................................................................... 29

Pseudokód 5: Algoritmus RNN ................................................................................... 31

Pseudokód 6: Algoritmus IB3 ..................................................................................... 33

Pseudokód 7: Algoritmus DROP3 ............................................................................... 37

Pseudokód 8: Algoritmus Prototypy ............................................................................ 40

Pseudokód 9: Chenův algoritmus ................................................................................ 45

Pseudokód 10: Algoritmus RSP1 ................................................................................ 48

Pseudokód 11: Algoritmus RSP3 ................................................................................ 50

Pseudokód 12: Algoritmus MergeAllInstances ............................................................ 53

xv

Struktura práce

1

Část I – Úvod

V mnoha odvětvích počítačové vědy jako je například dobývání znalostí, rozpoznávání

vzorů či strojové učení, je velmi důleţitá fáze předzpracování dat. Jednotlivé kroky procesu

dobývání znalostí jsou různě časově náročné a mají odlišnou důleţitost pro úspěšné vyřešení

dané úlohy. Praktici v oboru uvádějí, ţe nejdůleţitější je fáze porozumění datům, která ovšem

zabírá pouhých 15% celkového času. Časově nejnáročnější je jiţ zmiňovaná fáze přípravy

dat, která zabírá 80% celkového času. Zbylých 5% celkového času zaberou vlastní analýzy.

V praxi je mnoţina zkoumaných dat obrovská. Komplexní analýza a dobývání znalostí

na obrovském mnoţství dat zabírá mnoho času a znemoţňuje efektivní činnost data

miningových algoritmů. Aplikované techniky redukce dat poskytují zredukovanou mnoţinu

dat, která ovšem zachovává integritu původních dat. To znamená, ţe učení modelů probíhá

podstatně kratší dobu, ovšem výsledky jsou prakticky stejné.

Narůstající mnoţství dat vede u data miningových metod k problémům. Proces učení

pak trvá příliš dlouho a větší mnoţství instancí v trénovací mnoţině není zárukou

kvalitnějšího modelu. Navíc za některých okolností můţe příliš mnoho instancí v trénovací

mnoţině zapříčinit selhání učícího algoritmu.

K vyřešení tohoto problému pouţívají tradiční metody právě početní redukci dat, tedy

odstranění některých instancí z trénovací mnoţiny.

Tato práce si klade za cíl prozkoumání metod pro početní redukci dat a následnou

implementaci vybraných metod do modulu předzpracování dat projektu FAKE GAME. U

implementovaných metod testuji klasifikační přesnost pomocí 1 – NN klasifikátoru a

neuronové sítě GAME. Metody testuji na klasifikátoru 1 – NN proto, ţe jej pouţívají autoři

zabývající se problematikou početní redukce dat. Také budu testovat, jak implementované

metody zachovávají statistické vlastnosti dat. Implementované metody testuji na vlastních

uměle vytvořených datech a na vybraných reálných problémech. V práci také vizualizuji

výsledné mnoţiny redukované implementovanými metodami na uměle vytvořených datech.

1. Struktura práce

Kapitola 1 Tuto kapitolu právě čtete. Obsahuje úvod a motivaci proč vlastně práce

vznikla.

Kapitola 2 Přináší teoretický úvod k filozofii data miningu. Dále pojednává o

klasifikaci a metodologii CRISP – DM.

Kapitola 3 Obsahuje základní informace o fázi předzpracování dat. Zaměřuje se na

krok redukce dat.

Kapitola 4 Zabývá se problematikou početní redukce dat. Popisuje zaměření

algoritmů početní redukce dat.

Struktura práce

2

Kapitola 5 Rozebírá pouţité klasifikátory. Implementovaný klasifikátor 1 – NN a

neuronovou síť GAME.

Kapitola 6 Detailně popisuje vybrané algoritmy početní redukce dat a mnou

navrţený algoritmus.

Kapitola 7 Obsahuje popis implementace modulů vybraných algoritmů do projektu

FAKE GAME a také popis implementace klasifikátoru 1 – NN.

Kapitola 8 V této kapitole testuji implementované algoritmy na uměle vytvořených

datech a vybraných reálných problémech. Je zde dokázáno, ţe práce měla smysl.

Kapitola 9 Závěrečná kapitola, která obsahuje zhodnocení celé práce a nápady na

budoucí pokračování a vylepšení.

Data Mining

3

Část II – Teoretický rozbor

Tato část se zabývá teoretickým úvodem do problematiky v procesu dolování dat.

Rozebírá redukční metody pouţívané pro předzpracování dat a zaměřuje se na početní redukci

dat. Dále věnuje pozornost pouţívaným klasifikátorům.

2. Data Mining

Jsme svědky prudkého rozvoje informačních technologií (např. internet, intranet, data

warehousing, atd.) a elektronických a optických médií. [1] K tomuto rozvoji patří také

exponenciální nárůst mnoţství dat. Přesto, ţe máme zmiňované velké mnoţství dat,

neznamená to, ţe jsme schopni z nich všechno zjistit. Databázový managementový systém

sice umoţňuje přístup k datům, ale nezajišťuje zisk ucelených analýz.

V této situaci se objevuje filozofie, obecně nazývaná Data Mining (dále jen DM),

vycházející z předpokladu, ţe ve velkých databázích jsou ukryty poznatky, které lze vyjádřit

jednoduchými tvrzeními, vyjadřujícími příčinné vztahy, závislosti, klasifikaci apod. Některé

takové poznatky mohou být nečekané a mohou vést k novým odhalením i objevům. Hovoří se

tedy o „objevování znalostí v databázích“ (anglicky Knowledge Discovery in Databases , dále

jen KDD). Pouţívání DM vede k zajímavým výsledkům v oblastech medicíny, financí a

ekonomiky, marketingu, demografie a také politologie.

Ačkoliv jsou pojmy DM a KDD jiţ dlouhou dobu obecně známé, nepanuje jednotný

názor na jejich obsah a neexistuje všeobecně přijímaná definice. Pro ilustraci uvádím

představy několika známých autorů v oblasti DM.

A. Zornse říká: „Data mining je multidisciplinární proces pro vývoj přesných

strategických a taktických modelů zaloţených na analýze velkého objemu hodnotných dat,

KDD je nástrojem DM“.

U. Fayyad sděluje: „Data Mining je netriviální proces identifikace pravdivých, dosud

neznámých, potenciálně vyuţitelných a naprosto srozumitelných vzorů v datech. DM je

nástrojem KDD“ viz Obrázek 1.

J. Mena uvádí: „Cílem DM je KDD. DM extrahuje skryté predikční kapacity dat.

Kaţdý statistický software lze povaţovat za nástroj KDD. Technologie DM přechází vývojem

automaticky k induktivní KDD.“

Data Mining

4

Data

Vzory

Transformovaná

dataPředzpracovaná

data

Cílová data

Selekce

Předzpracování

Transformace

Dolování dat

Interpretace

Vyhodnocení

Obrázek 1: DM nástrojem KDD

2.1 Členění data miningových úloh

V oblasti data miningu [2] se setkáme s celou řadou úloh, které jsou většinou děleny na

tyto následující 3 typy:

Klasifikace.

Regrese.

Shlukování.

Klasifikace – je jednou z nejtypičtějších úloh dolování dat. Podstatou klasifikační úlohy

je prozkoumání vlastností určité entity a rozhodnutí o jejím zařazení do předem definované

skupiny resp. třídy. Počet tříd je konečný a je předem znám.

Regrese – zatímco klasifikace pracuje s diskrétním výstupem, úlohy modelující spojitý

výstup obvykle označujeme jako regresní. Úkolem regrese je pro dané hodnoty vstupních

atributů odhadnout neznámou spojitou hodnotu cílového atributu.

Shlukování – spočívá v rozdělení pozorovaných dat do určitého počtu homogenních

skupin, tak aby si entity v nalezených skupinách byly co nejvíce podobné. Počet shluků můţe,

ale nemusí být dopředu určen. I kdyţ shlukování má blízko ke klasifikaci, k interpretaci

skupin dochází aţ po jejich vytvoření.

2.1.1 Klasifikace

Nejčastěji pouţívaným hlediskem, dle kterého můţeme klasifikační algoritmy dělit je

fakt, zda se při klasifikaci můţeme řídit nějakým vzorem (existuje „učitel“) nebo ne. Podle

toho rozlišujeme:

Učení s učitelem.

Učení bez učitele.

Učení s učitelem (Supervised learning) – metoda tvorby modelu pomocí trénovací mnoţiny

(učitele) T, která je kolekcí trénovacích vzorů nazvaných instance. Kaţdá instance má vstupy

Data Mining

5

a výstupní hodnotu – třídu. Metoda tvorby modelu, při které jsou známy výstupy pro instance

v trénovací mnoţině, se nazývá učení s učitelem. Při učení modelu s učitelem jsou data

z trénovací mnoţiny postupně předkládána modelu a jeho výstup je porovnáván s

poţadovaným výstupem. Pokud se skutečný a poţadovaný výstup liší, učící algoritmus upraví

parametry modelu tak, aby se příště výstup modelu blíţil poţadovanému výstupu. Viz

Obrázek 2.

Model

Učící

algoritmus vstupy výstupy

Trénovací množina

výstup

Obrázek 2: Učení s učitelem

Příkladem učení s učitelem mohou být algoritmy: Nearest Neighbour, Rozhodovací

stromy, Neuronové sítě typu Back propagation.

Učení bez učitele (Unsupervised learning) – metoda tvorby modelu, při které poţadované

výstupy modelu nejsou známy. Model sám hledá vztahy v trénovací mnoţině. Tento typ učení

se pouţívá pro shlukování. Při učení se vyhledávají podobné instance a seskupují se do shluků

podle podobnosti. Příkladem takového algoritmu je neuronová síť typu SOM nebo K-Means

algoritmus.

2.2 Metodologie CRISP-DM

S postupem doby začaly vznikat metodologie, které si kladou za cíl poskytnout

uţivatelům jednotný rámec pro řešení různých úloh z oblasti dobývání znalostí. [3] Tyto

metodologie umoţňují sdílet a přenášet zkušenosti z úspěšných projektů. Za některými

metodologiemi stojí producenti software (metoda „5A“ firmy SPSS nebo metodologie

SEMMA firmy SAS), jiné vznikají ve spolupráci výzkumných a komerčních institucí jako

„softwarově nezávislé“ (CRISP-DM).

Metodologie CRISP-DM (CRoss-Industry Standard Process for Data Mining) vznikla v

rámci výzkumného projektu Evropské komise. Cílem projektu je navrhnout univerzální

postup (tzv. standardní model procesu dobývání znalostí z databází), který bude pouţitelný v

nejrůznějších komerčních aplikacích. Vytvoření takovéto metodologie umoţní řešit rozsáhlé

úlohy dobývání znalostí rychleji, efektivněji, spolehlivěji a s niţšími náklady. Kromě návrhu

Data Mining

6

standardního postupu má CRISP-DM nabízet „průvodce“ potenciálními problémy a řešeními,

které se mohou vyskytnout v reálných aplikacích.

Ţivotní cyklus projektu dobývání znalostí je podle metodologie CRISP-DM tvořen šesti

fázemi viz Obrázek 3. Pořadí jednotlivých fází není pevně dáno. Výsledek dosaţený v jedné

fázi ovlivňuje volbu kroků následujících, často je třeba se k některým krokům a fázím vracet.

Vnější kruh na obrázku symbolizuje cyklickou povahu procesu dobývání znalostí z databází.

Obrázek 3: Ţivotní cyklus CRISP – DM (převzato z [5])

Porozumění problematice (Business understanding) je úvodní fáze zaměřená na

pochopení cílů projektu a poţadavků na řešení formulovaných z manaţerského hlediska. Tato

manaţerská formulace musí být převedena do zadání úlohy pro dobývání znalostí z databází.

Fáze porozumění datům (Data understanding) začíná prvotním sběrem dat. Následují

činnosti, které umoţní získat základní představu o datech, která jsou k dispozici (posouzení

kvality dat, první „vhled“ do dat, vytipování zajímavých podmnoţin záznamů v databázi…).

Obvykle se zjišťují různé deskriptivní charakteristiky dat (četnosti hodnot různých atributů,

průměrné hodnoty, minima, maxima apod.), s výhodou se vyuţívají i různé vizualizační

techniky.

Fáze předzpracování dat (Data preparation) zahrnuje činnosti, které vedou k vytvoření

datového souboru, který bude zpracováván jednotlivými analytickými metodami. Tato data by

tedy měla obsahovat údaje relevantní k dané úloze, a mít podobu, která je vyţadována

vlastními analytickými algoritmy.

Analytické metody pouţité ve fázi modelování (Modeling) zahrnují algoritmy pro

dobývání znalostí. Obvykle existuje řada různých metod pro řešení dané úlohy, je tedy třeba

vybrat ty nejvhodnější (doporučuje se pouţít více různých metod a jejich výsledky

kombinovat) a vhodně nastavit jejich parametry. Jde tedy opět o iterativní činnost (opakovaná

Předzpracování dat

7

aplikace algoritmů s různými parametry), navíc, pouţití analytických algoritmů můţe vést k

potřebě modifikovat data a tedy k návratu k datovým transformacím z předcházející fáze.

Ve fázi interpretace (Evaluation) se dosaţené výsledky vyhodnocují z pohledu

uţivatelů, tedy z pohledu zda byly splněny cíle formulované na počátku projektu.

Vytvořením vhodného modelu celý projekt obecně nekončí. Dokonce i v případě, ţe

řešenou úlohou byl „pouze“ popis dat, získané znalosti je třeba upravit do podoby pouţitelné

pro podporu rozhodování. Podle typu úlohy tedy využití (Deployment) výsledků můţe na

jedné straně znamenat prosté sepsání závěrečné zprávy, na straně druhé pak zavedení systému

pro automatickou klasifikaci nových případů.

Jednotlivé kroky procesu dobývání znalostí jsou různě časově náročné a mají i různou

důleţitost pro úspěšné vyřešení dané úlohy. Praktici v oboru uvádějí, ţe nejdůleţitější je fáze

porozumění datům (80 % významu, 20 % času) a časově nejnáročnější je fáze přípravy dat

(80 % času, 20 % významu). Překvapivě málo práce zaberou vlastní analýzy (5 % času, 2 %

významu).

3. Předzpracování dat

Tato diplomová práce se zabývá fází předzpracovávání dat. V DM je klíčovým

problémem kvalita dat. Jak jsem jiţ zmínila, v praxi bylo zjištěno, ţe aţ 80% času v procesu

DM je věnováno zkvalitňování dat. Příprava dat je tedy hlavním předmětem zkoumání.

Předzpracování dat je potřebné z mnoha důvodů.

Reálná surová data nemusí být kompletní, mohou chybět hodnoty atributů nebo celé

atributy jako takové, či obsahují pouze souhrnná data. [4] Data mohou být dále nekonzistentní

v důsledku různého kódování v odlišných reprezentacích, nebo ze stejného důvodu mohou

mít rozdílné pojmenování atributů. Objevit se mohou také data odlehlá mimo svůj daný

rozsah či nesmyslná data pro danou definici. Běţně se setkáváme se šumem, tj. chybami nebo

nepřesnostmi v datech.

Fázi předzpracování dat je moţno rozdělit do čtyř skupin:

Čištění dat.

Integrace dat.

Transformace dat.

Redukce dat.

Čištění dat – reálná data bývají často nekompletní, zašuměná a nekonzistentní. Čištění

dat se snaţí zaplnit chybějící hodnoty, zahladit šum, identifikovat odlehlé hodnoty a opravit

nekonzistence datech. Chybějící data mohou být způsobena kromě poruchy zaznamenávacího

zařízení také nekonzistencí s jinými daty a tudíţ smazána, nebo také tím, ţe na počátku

nemusela být povaţována za důleţitá.


8

Integrace dat – data do datového úloţiště mohou přicházet z různých zdrojů a to můţe

zapříčinit nekoherenci. Integrace zajišťuje sjednocení atributů s různým jménem, které mají

ovšem stejný význam. Také sjednocuje klíčová slova stejného významu, která jsou různě

pojmenovaná (urgentní, UG, …). Zajišťuje převedení dat do stejných jednotek. Zabraňuje tak

nekonzistenci a redundancím dat.

Transformace dat – data jsou transformována a sloučena do vhodné podoby k

budoucímu procesu dobývání znalostí. Zajišťuje normalizaci dat škálováním hodnot do

minimálních rozsahů. Vyhlazuje šum z dat a data agreguje. Generalizuje data, kdy surová data

nahrazuje vyššími koncepty pomocí koncepčních hierarchií.

Redukce dat – velké mnoţství dat sniţuje výkonnost a dělá analýzu sloţitější. Redukce

dat zajišťuje redukci velké mnoţiny dat na podstatně menší reprezentaci dat, která ovšem

přináší stejné výsledky analýzy. Podrobněji viz následující kapitola 3.1.

3.1 Redukce dat

V praxi je mnoţina zkoumaných dat obrovská. Komplexní analýza a dobývání znalostí

na značném mnoţství dat zabírá mnoho času a znemoţňuje efektivní činnost data

miningových algoritmů. Aplikované techniky redukce dat poskytují zredukovanou mnoţinu

dat, která ovšem zachovává integritu původních dat. To znamená, ţe učení modelů probíhá

kratší čas, ovšem výsledky jsou prakticky stejné.

Strategie redukce jsou následující:

1. Seskupení do data cube, kde jsou operace aplikované na data, tak aby se

seskupila do několikarozměrné datové krychle.

2. Redukce dimenze, kde jsou nerelevantní nebo redundantní atributy a dimenze

detekovány a odstraňovány.

3. Komprese dat, kde jsou kódovací mechanizmy pouţity na sníţení velikosti

mnoţiny dat.

4. Početní redukce, kde jsou data nahrazena zástupnými daty, jako např. adaptivní

modely (kdy je uloţen jeden model místo mnoţiny dat) nebo neadaptivní

modely (kdy je vybrána pouze určitá podmnoţina z původní mnoţiny dat)

5. Diskretizace a generace koncepční hierarchie, kde jsou surová data nahrazena

rozsahy nebo vyššími koncepčními úrovněmi.

3.1.1 Seskupení do data cube

Představme si příklad, kdy máme k dispozici souhrn trţeb za jednotlivá čtvrtletí v letech

2005 aţ 2007. Ovšem nás zajímají pouze celkové roční trţby místo čtvrtletních. Proto je

vhodné, data seskupit do ročních období. Výsledná data tak budou menší, ovšem bez ztráty

důleţité informace k analýze. Data cube obsahuje vícerozměrně seskupené informace. Kaţdá


9

buňka v prostoru obsahuje informaci odpovídající bodu v prostoru. Data cube poskytuje

rychlý přístup k seskupeným datům.

3.1.2 Redukce dimenze

Mnoţina dat můţe obsahovat stovky atributů, kdy většina z nich je v procesu dobývání

znalostí nerelevantní nebo redundantní. Např. při klasifikaci zákazníků, kteří si s vysokou

pravděpodobností koupí novou plazmovou televizi, je nepodstatný atribut telefonní číslo a

naopak atributy plat či věk jsou důleţité. Vynechání relevantních atributů nebo ponechání

zbytečných můţe způsobit zmatení procesu dobývání znalostí nebo jeho zpomalení.

Redukce dimenze sniţuje velikost dat odstraňováním atributů. Typicky se aplikují

metody výběru podmnoţiny atributů. Cílem je nalézt takovou minimální podmnoţinu

atributů, aby rozloţení pravděpodobností tříd bylo co nejblíţe původnímu obsazení atributů.

Sníţení počtu atributů také zjednodušuje pochopení nalezených vzorů.

V mnoţině d atributů existuje 2d různých podmnoţin. Hledání nejlepší podmnoţiny

hrubou silou je časově náročně. Proto se pouţívají různé heuristiky, převáţně na bázi

hladových algoritmů, které se při prohledávání rozhodují podle nejlepší moţnosti v daném

okamţiku. Strategií je přijmout lokálně optimální krok ve snaze najít globální optimum.

V praxi jsou tyto metody efektivní. Kvalita atributů se určuje statistickými testy, předpokládá

se, ţe jsou nezávislé.

Základní heuristické metody jsou zobrazeny na obrázku, viz

Obrázek 4.

Obrázek 4: Metody výběru podmnoţiny atributů (převzato z [4])

1. Dopředný výběr: začíná se s prázdnou mnoţinou atributů. V kaţdém kroku se vloţí

nejlepší atribut z atributů zbývajících v původní mnoţině.


10

2. Zpětná eliminace: začíná se s úplnou původní mnoţinou atributů. V kaţdém kroku se

odstraní nejhorší atribut z mnoţiny.

3. Kombinovaný dopředný a zpětný běh: kombinace předchozích, kdy se v kaţdém kroku

přidá nejlepší a odstraní nejhorší atribut.

4. Rozhodovací stromy: kaţdý vnitřní uzel stromu obsahuje test atributu, kaţdá větev

odpovídá výsledku testu a kaţdý list znamená výsledek predikce třídy. Atributy ve

stromu jsou redukovanou podmnoţinou atributů a ostatní jsou irelevantní.

3.1.3 Komprese dat

Komprese dat můţe být bezeztrátová, kdy jsou data komprimována bez jakékoli ztráty

informace, tak ztrátová, kdy můţeme původní data zrekonstruovat pouze přibliţně. Přestoţe

existují algoritmy pro bezeztrátovou kompresi na řetězcích, tak se pro omezenou moţnost

manipulace s daty příliš nepouţívají. Mezi populární ztrátové metody patří waveletová

transformace a analýza hlavních komponent.

Diskrétní waveletová transformace (DWT) je technika lineárního zpracování signálu,

kde při aplikaci na vektor D jej transformuje na odlišný vektor D0 waveletových koeficientů

stejné délky. Přestoţe nový vektor má stejnou délku, uţitečnost spočívá ve faktu, ţe

transformovaná data mohou být zkrácena. Zkomprimovaná aproximace původních dat můţe

být uchována uloţením pouze části waveletových koeficientů, např. koeficienty pod

specifikovaným prahem jsou vynulovány. DWT souvisí s diskrétní Fourierovou transformací,

oproti které dosahuje lepší ztrátové komprese.

Předpokládejme, ţe původní data obsahují N poloţek z k dimenzí. Analýza hlavních

komponent (PCA) hledá c k-rozměrných ortogonálních vektorů, které by nejlépe

reprezentovaly původní data, c << N. Původní data jsou tedy promítnuta do mnohem menšího

prostoru, tj. komprimována. PCA je tedy formou redukce dimenze. Nicméně oproti výběru

podmnoţiny atributů, která sníţí počet původních atributů, PCA vytváří alternativní mnoţinu

atributů, do které jsou původní data promítnuta.

3.1.4 Početní redukce dat

Početní redukce dat slouţí ke sníţení počtu dat volbou alternativní formy reprezentace

dat. Mnoţina dat je zastoupena malou mnoţinou instancí, která ovšem zachovává všechny

potřebné informace. Podrobněji viz další kapitola 4.

Existují dva základní přístupy pro početní redukci:

Neadaptivní (selektivní).

Adaptivní (generalizační).

Neadaptivní přístup vybírá podmnoţinu instancí z původní mnoţiny, která ji nejlépe

reprezentuje. Zaměřuje se na výběr instancí na úrovni rozhodovací hranice. V tomto přístupu

nikdy nedochází k modifikaci instancí.


11

Naproti tomu adaptivní přístup generuje nové reprezentanty, kteří nahrazují původní

mnoţinu. Odstraňuje tak hlavní nevýhodu neadaptivního přístupu, kdy není moţné ţádnou

instanci posunout na výhodnější pozici.

3.1.5 Diskretizace dat a generovaných koncepčních hierarchií

Techniky diskretizace dat slouţí k redukci hodnot atributů rozdělením jejich rozsahu do

intervalů. Jména intervalů pak mohou nahradit původní hodnoty. Mnoho diskretizačních

metod můţe být rekurzivně aplikováno a vytvořit hierarchický několikaúrovňový rozklad, tj.

koncepční hierarchii.

Koncepční hierarchie pro číselný atribut zapříčiní jeho diskretizaci. Nahrazují

nízkoúrovňové koncepty, jako např. číselné hodnoty atributu věk, vyššími koncepty, jako

teenager, dospělý, důchodce. Ačkoli se tímto ztratí detaily, generalizovaná data jsou

smysluplnější a snadněji interpretovatelná a dále potřebují měně prostoru k uloţení. Proces

dobývání znalostí bude potřebovat méně vstupně/výstupních operací a bude efektivnější.

Příklad koncepční hierarchie atributu cena, je ilustrován na obrázku viz

Obrázek 5. Pro daný atribut existuje více koncepčních hierarchií podle potřeby.

Obrázek 5: Koncepční hierarchie atributu cena (převzato z [4])

Některé metody tvorby koncepčních hierarchií pro číselná a diskrétní data:

1. Metoda přihrádek: podobně jako u čištění můţe slouţit i k diskretizaci. Např.

nahrazení hodnot uvnitř přihrádky průměrem nebo mediánem. Můţe být

aplikováno rekurzivně a vytvořit koncepční hierarchii.

2. Histogramy: rozdělení dat do intervalů je vlastně formou diskretizace.

Aplikace histogramu na jednotlivé intervaly vytvoří koncepční hierarchii.

3. Shlukování: kaţdá skupina při shlukování tvoří uzel koncepční hierarchie,

kaţdý uzel je na stejné úrovni. Kaţdá skupina pak můţe být dále rozdělena na

podskupiny a vytvořit niţší úrovně koncepční hierarchie.

4. Specifikace pro diskrétní data: systém nebo expert můţe určit pořadí atributů a

tím určit koncepční hierarchii. Např. pro atribut místo můţeme určit závislost

Početní redukce dat

12

ulice < město < kraj < země. Pro rozsáhlejší atributy lze hierarchii vypozorovat

na základě početních zastoupení pro jednotlivé hodnoty atributů (zemí je méně

neţ ulic, proto bude v hierarchii výše). Toto ovšem vyţaduje kontrolu, neboť' v

určitých případech můţe selhat, např. dnů v týdnu je méně neţ měsíců v roce,

ale v hierarchii by měl být den níţ.

4. Početní redukce dat

Jak jsem jiţ zmínila v předchozí kapitole, tato diplomová práce se zabývá fází

předzpracovávání dat v procesu dolování dat. Přičemţ se ve fázi předzpracovávání dat

zaměřuje na redukci dat, kdy vyuţívá strategii početní redukce dat.

Narůstající mnoţství dat vede u metod dolování dat k problémům. Proces učení pak trvá

příliš dlouho a větší mnoţství instancí v trénovací mnoţině není zárukou kvalitnějšího

modelu. Navíc za některých okolností můţe příliš mnoho instancí v trénovací mnoţině

zapříčinit selhání učícího algoritmu.

Problém s délkou učícího procesu je obzvláště dramatický v případě pouţití některého

z algoritmů zaloţeného na vzdálenostech, jako je např. Pravidlo nejbliţšího souseda (Nearest

Neighbour rule, dále jen NN) [Cover & Hart 1967; Dasarathy 1991]. Základní NN algoritmus

při klasifikaci jednoho testovacího vzorku musí projít všechny instance v trénovací mnoţině.

NN klasifikátor tudíţ ukládá všechny instance trénovací mnoţiny i s rušivými instancemi,

které mohou degradovat přesnost klasifikace.

K vyřešení tohoto problému pouţívají tradiční metody právě početní redukci dat, tedy

odstranění některých instancí z trénovací mnoţiny. Proces početní redukce dat se skládá

ze dvou po sobě jdoucích kroků – editování (editing) a kondenzace (condensing). [10]

Počáteční krok editování se zaměřuje na odstranění rušivých instancí a instancí, které leţí na

rozhodovací hranici. Odstraňuje tak všechny instance, které by mohly ohrozit přesnost

klasifikace. Následující krok kondenzace vybírá podmnoţinu instancí z původní trénovací

mnoţiny či generuje podmnoţinu nových reprezentantů tak, aby nedošlo k výrazné změně

klasifikační přesnosti. Sniţuje paměťové poţadavky a čas potřebný na vytvoření modelu či

klasifikaci trénovací mnoţiny.

Z obrázku viz Obrázek 6 je zřejmé, ţe krok editování pracuje s původní trénovací

mnoţinou TS a jeho výstupem je editovaná mnoţina (Edited Set ES). Editovaná mnoţina

slouţí jako vstup pro krok kondenzace, jehoţ výstupem je kondenzovaná mnoţina

(Condensed Set CS), která se pak vyuţívá v procesu klasifikace jako trénovací mnoţina.

Editování Kondenzace TS ES CS

Obrázek 6: Kroky procesu početní redukce dat


13

V této diplomové práci jsem zkoumala a následně implementovala dva základní

editovací algoritmy Wilson (1972) [12] a Tomek (1976) [13]. Další informace o algoritmech

pro editování si můţete přečíst v literatuře viz [11].

Algoritmy pro kondenzaci se dělí na dvě hlavní skupiny. Neadaptivní (selektivní)

skupinu algoritmů, které se zaměřují na výběr podmnoţiny originálních instancí z trénovací

mnoţiny. Např.: Hart (1968) [14], Gates (1972) [15], Tomek (1976) [13], Aha (1991) [16],

Dasarathy (1994) [17], Wilson & Martinez (1997) [18]. Adaptivní skupinu algoritmů, které

generují podmnoţinu nových reprezentantů. Např.: Chang (1974) [19], Chen & Jozwik

(1996) [20], Sánchez (2004) [21].

V této diplomové práci se zaměřuji na oba způsoby redukce dat. Neadaptivní algoritmy

zkoumané v mojí studii a následně implementované jsou Condensed Nearest Neighbours

(CNN – Hart), Reduce Nearest Neighbours (RNN – Gates), IB3 – (Aha), DROP3 – (Wilson

& Martinez). Adaptivní algoritmy zkoumané v mojí studii a následně implementované jsou

Prototypes (Chang), Chen’s algorithm (Chen & Jozwik), RSP1 (Sánchez), RSP3 (Sánchez).

4.1 Zaměření algoritmů početní redukce dat

Kaţdý algoritmus početní redukce dat se snaţí nalézt nejlepší strategii redukce. V této

kapitole popisuji nejdůleţitější body, na které se redukční algoritmy zaměřují. Jedná se o

reprezentaci dat, směr prohledávání, volba nejvhodnějších pozic instancí a také kritéria pro

porovnání odlišných redukčních strategií. [18]

4.1.1 Reprezentace dat

Jedním z důleţitých rozhodnutí v návrhu algoritmů pro početní redukci dat je volba, zda

zachovat podmnoţinu originálních instancí nebo instance modifikovat pouţitím nové

reprezentace.

Některé algoritmy [Salzberg (1991), Wettschereck & Dietterich (1995)] pouţívají

hyperkvádr (hyperrectangles) k reprezentaci kolekcí instancí. Dále mohou být instance

zastoupeny pravidly [Domingos (1995)], nebo prototypy, které jsou pouţity k reprezentaci

shluků instancí [Chang (1974)]. Instance se tak můţe vyskytnout v místě, kde se nenachází

ţádná instance v původní originální mnoţině.

Na druhé straně velké mnoţství algoritmů početní redukce dat usiluje o ponechání

podmnoţiny originálních instancí. Jedním problémem s pouţitím originálních instancí je fakt,

ţe instance není moţné přemístit na přesnou pozici, abychom mohli zajistit vyšší přesnost

klasifikace. Za to prototypy můţeme uměle konstruovat tak, aby mohly být umístěny přesně

tam, kde jsou potřebné. Podobně to platí i pro pravidla a hyperkvádry.

4.1.2 Směr prohledávání

Hledání podmnoţiny instancí z trénovací mnoţiny je moţné třemi způsoby:


14

Inkrementální prohledávání.

Dekrementální prohledávání.

Dávkové prohledávání.

Inkrementální prohledávání

Algoritmy s inkrementálním prohledáváním začínají s prázdnou podmnoţinou

redukovaných trénovacích dat (S) a postupně do ní přidávají instance z originální trénovací

mnoţiny (TS), které splňují všechna potřebná kritéria. U těchto algoritmů můţe být prvotní

uspořádání instancí velmi důleţité, poněvadţ první instance mají podstatně odlišnou

pravděpodobnost pro přidání do podmnoţiny S, neţ ty, které jsou přidány později. Proto se

většinou k instancím v originální trénovací mnoţině přistupuje náhodně. Některé

inkrementální algoritmy si ve finální redukované mnoţině neponechávají instance vybrané

v prvotním průchodu.

Hlavní výhodou inkrementálních algoritmů je, ţe jsou rychlejší a pouţívají méně paměti

během průchodu neţ neinkrementální algoritmy. Nevýhodou je citlivost inkrementálních

algoritmů na uspořádání prezentace instancí trénovací mnoţiny a také rozhodování s malým

počtem informací.

Dekrementální prohledávání

Algoritmy s dekrementálním prohledáváním začínají s kompletní původní trénovací

mnoţinou S = TS a poté se rozhodují, které instance je potřeba z mnoţiny S odstranit. Opět

platí, ţe uspořádání prezentace instancí v mnoţině S je důleţité, ale ne tak, jako u

inkrementálních algoritmů. Všechny trénovací instance jsou algoritmu přístupné jiţ od

začátku, a tak se algoritmus můţe rozhodnout, kterou instanci bude v daném kroku nejlepší

odstranit.

Nevýhodou dekrementálního prohledávání je vyšší výpočetní sloţitost neţ u

inkrementálního prohledávání.

Dávkové vyhledávání

Dalším způsobem jak aplikovat redukční schéma na trénovací mnoţinu je dávkové

vyhledávání. V tomto procesu se u kaţdé instance rozhoduje, zda splňuje kritéria k odstranění

a pokud ano, tak je označena pro pozdější odebrání. Aţ po kontrole všech instancí se odstraní

všechny instance, které jsou označeny. Tento postup však můţe způsobit vymizení celého

shluku, pokud poblíţ nejsou instance odlišné třídy.

Stejně jako dekrementální prohledávání má dávkové vyhledávání vyšší výpočetní

sloţitost neţ inkrementální vyhledávání.


15

4.1.3 Hraniční pozice vs. centrální pozice

Dalším kritériem, podle kterého můţeme algoritmy početní redukce dat rozlišovat, jsou

pozice instancí, které zanechávají. Mohou to být instance na hraničních pozicích, centrálních

pozicích či jiných pozicích.

Některé algoritmy se řídí základní intuicí, ţe „vnitřní“ instance neovlivňují rozhodovací

hranici tak, jako hraniční instance a proto je moţné je odstranit s relativně malým vlivem na

přesnost klasifikace.

Další algoritmy se naopak zaměřují na odstranění hraničních instancí. Soustředí se na

rušivé instance nebo instance, jejichţ sousedé patří do jiné třídy. Odstraňují tak hraniční

instance a vyhlazují tím rozhodovací hranici. Proto tyto algoritmy neodstraňují „vnitřní“

instance, které slouţí k určení rozhodovací hranice.

Protoţe vybírání vhodných hraničních bodů k určení rozhodovací hranice je velmi

náročné, některé algoritmy se snaţí získat instance na centrálních pozicích. Centrální instance

jsou instance, které jsou schopny klasifikovat správně všechny blízké sousední instance.

Tento postup můţe dramaticky ovlivnit rozhodovací hranice. Jednoduše řečeno, rozhodovací

hranice je umístěna mezi dvěma nejbliţšími instancemi různých tříd. Proto je potřeba

centrální instance vybírat pečlivě a zajistit tak správnou klasifikaci instancí v nejbliţším okolí.

4.1.4 Hodnotící strategie

K porovnání algoritmů početní redukce dat se nejčastěji pouţívá následujících čtyř

kritérií:

Redukce paměti.

Zvýšení rychlosti klasifikace.

Přesnost klasifikace.

Zrychlení učícího procesu.

Některé z těchto kritérií pro porovnání redukčních algoritmů vyuţívám také ve

své experimentální části viz kapitola 8.

Redukce paměti

Jedním z hlavních cílů početní redukce dat je sníţení paměťových poţadavků. Je

důleţité si uvědomit, ţe pouţití jiné reprezentace dat (např.: hyperkvádry, pravidla) můţe i při

sníţení počtu instancí poţadavek na paměť navýšit.

Zvýšení rychlosti klasifikace

Dalším hlavním cílem početní redukce dat je zrychlení klasifikačního procesu. Redukce

počtu uloţených instancí přináší odpovídající redukci času potřebného pro hledání potřebných

instancí a klasifikování vstupního vektoru. Opět je potřeba prověřit, zda při komplexní

reprezentaci dat není potřeba více porovnávání, či zda porovnávání netrvá příliš dlouho.

Testované klasifikátory

16

Přesnost klasifikace

Úspěšné algoritmy musí být ve většině případů schopné značně redukovat velikost

trénovací mnoţiny, ovšem bez významného sníţení přesnosti klasifikace. V některých

případech můţe být dokonce přesnost klasifikace redukcí instancí zvýšena, pokud jsou

odstraněny rušivé instance a je vyhlazena rozhodovací hranice.

Zrychlení učícího procesu

Urychlení učícího procesu není tolik důleţité v procesu klasifikace, protoţe učící proces

je pro danou instanci vykonán jen jednou. Avšak pokud učící fáze trvá příliš dlouho, můţe se

stát nepraktický pro skutečné aplikace.

5. Testované klasifikátory

Stěţejním úkolem této diplomové práce je implementace redukčních algoritmů pro

neuronovou síť GAME. Ovšem pro řádné porovnání a vyhodnocení redukčních algoritmů

jsem se rozhodla implementovat klasifikátor k – nejbliţších sousedů (k – Nearest Neighbours,

dále jen k – NN), který je pro tyto účely vhodnější. Navíc je často pouţíván v literatuře o

početní redukci dat, a tak jeho pouţitím získám moţnost srovnání výsledků mých redukčních

algoritmů s ostatními pracemi.

Jak jsem jiţ zmínila, tento klasifikátor ukládá všechny instance trénovací mnoţiny a

navíc při testování jedné instance musí vypočítat vzdálenost ke všem trénovacím instancím.

Tudíţ má vysokou paměťovou i výpočetní sloţitost, které je potřeba sníţit.

5.1 Pravidlo nejbližšího souseda

Jedním ze způsobů, jak klasifikovat vzor do odpovídající třídy, je pravidlo nejbliţšího

souseda (Nearest neighbor rule, dále jen NN). Jedná se o velmi přímočarou metodu. Ve

většině případů poskytuje celkem uspokojivé výsledky, které poslouţí k srovnání redukčních

algoritmů. [6]

Při klasifikaci neznámého vzoru x se vypočítá jeho vzdálenost od všech reprezentantů

ze všech tříd. Vzor x je pak zařazen do třídy, která odpovídá nejbliţšímu reprezentantovi

(resp. je nejčastěji zastoupena mezi nejbliţšími reprezentanty). Vhodná metrika můţe

výsledek klasifikace výrazně zlepšit. Nejobvyklejší je pouţití Euklidovské metriky.

Mezi nejznámější metriky patří Euklidovská vzdálenost. Pro dva n-dimenzionální

příznakové vektory x = (x1,…, xn) a y = (y1,…,yn) je Euklidovská vzdálenost definována

vztahem:

𝑥 − 𝑦 = 𝑥1 − 𝑦1 2 + … + 𝑥𝑛 − 𝑦𝑛 2

Na základě této metriky je nalezen nejbliţší reprezentant 𝑦𝑖 𝑌𝑖 pro kterého platí:


17

𝑥 − 𝑦𝑖 ≤ 𝑥 − 𝑦 pro všechna y Y

a neznámý vzor x je klasifikován do třídy i.

5.1.1 Algoritmus k – NN

Jde o metodu pro učení s učitelem, kdy se klasifikují prvky reprezentované

vícedimenzionálními vektory do dvou nebo více tříd. Pro kaţdou třídu můţe být z trénovací

mnoţiny vybráno i více reprezentantů. Jejich počet můţe záviset na velikosti celé trénovací

mnoţiny, apriorní pravděpodobností dané třídy nebo procentuálním zastoupení vzorů z dané

třídy v trénovací mnoţině. Typicky se volí stejný počet reprezentantů pro všechny třídy.

Vybrány by měly být ty vzory, které danou třídu nejlépe charakterizují. Pokud je k = 1, jde o

speciální zjednodušený případ, pravidlo nejbliţšího souseda.

Pro klasifikaci neznámého vzoru x je nutné vypočítat jeho vzdálenost od všech

reprezentantů v příznakovém prostoru. V této souvislosti se nejčastěji uplatňuje jiţ zmíněná

Euklidovská metrika. Dále je potřeba najít k nejbliţších reprezentantů. Neznámý vzor x je

klasifikován do té třídy, která je nejvíce zastoupena mezi k nejbliţšími reprezentanty.

Podrobněji viz Pseudokód 1.

Na obrázku viz Obrázek 7 je zobrazena klasifikace pomocí zjednodušeného případu,

kdy k = 1, tzv. pravidlo nejbliţšího souseda. Na obrázku viz Obrázek 8 můţeme sledovat

klasifikaci k – NN algoritmem s parametrem k = 3.

X

? =

X

? =

Obrázek 7: Klasifikace 1 – NN Obrázek 8: Klasifikace 3 – NN

Pseudokód 1: Algoritmus k – NN

Význam použitých proměnných

n[#class(množina TS)] - pole n o velikosti dle počtu tříd z původní

trénovací množiny TS, které slouží k čítání zastoupení jednotlivých tříd k

nejbližších sousedů

k - počet nejbližších sousedů, dle kterých testovanou instanci

klasifikujeme


18

classes – seznam všech tříd které jsou zastoupeny v množině TS

Popisy použitých datových struktur

V množině TS pro každou instanci t:

t.d - vzdálenost instance k testované instanci

Význam použitých funkcí

vstup() – vrací vstup definovaný uživatelem

vzdalenost(instance x, instance y) – vrací euklidovskou vzdálenost instancí

x, y ( (xi − yi)2)n

i=1

sort(množina X) – vrací seřazenou množinu X vzestupně podle x.d (vzdálenost

k testované instanci)

dalsiN(množina X) – vrací další nejbližší instanci k instanci x z množiny X

class(instance x) – vrací třídu instance x

#class(množina X) - vrací celkový počet tříd zastoupených v množině X

maxclass(pole X[]) - vrací nejzastoupenější třídu z pole X (index políčka s

nejvyšším obsahem). V případě, že je takových tříd více, vybere z nich

náhodně

// Načte počet nejbližších sousedů k

1. k = vstup()

// Vypočítá vzdálenosti všech reprezentantů y od neznámého vzoru x

2. for all y from TS

y.de = vzdalenost(x,y)

// Setřídí reprezentanty vzestupně podle vzdálenosti

3. sort(TS)

// Inicializuje pole n o velikosti dle počtu tříd

// v trénovací množině TS

4. n[#class(TS)]

// Postupně inkrementuje proměnnou k od 1 do k

5. for k from 1..k {

// Pro všechny třídy ze seznamu tříd

// (všechny indexy pole n)

for all c from classes {

// vyzkouší zda se třída rovná třídě souseda

if (c == class(dalsiN(TS)) {

// a případně zvýší počet zástupců této třídy

// mezi k nejbližšími sousedy

n[c] = n[c] + 1

}

}

}

// Nalezne nejzastoupenější třídu mezi sousedy

// V případě, že je takových tříd více

// vybere z nich náhodně

6. i = maxclass(n[])

7. return i

5.1.2 Slabé stránky k – NN

Algoritmus k – NN ukládá všechny trénovací instance. Učí se velmi rychle, protoţe

trénovací mnoţinu dat pouze čte a trénovací instance dále nezpracovává. Avšak ukládání

všech trénovacích instancí znamená značné paměťové nároky. Navíc musí prohledávat

všechny dostupné instance ke klasifikaci vstupního vektoru, a tak klasifikace trvá příliš

dlouho. [7]


19

Při ukládání všech instancí trénovací mnoţiny jsou uloţeny také rušivé nebo

„zašuměné“ instance, které mohou sníţit přesnost klasifikace. Rušivé instance jsou instance,

které byly při přípravě trénovací mnoţiny zařazeny do špatné třídy. Další skupinou rušivých

instancí jsou odlehlé instance.

Techniky jako jsou KD-stromy [Sproull (1991)] a projekce [Papadimitriou & Bentley

(1980)] dokáţí redukovat čas potřebný k nalezení nejbliţších sousedů vstupního vektoru, ale

nejsou schopné redukovat paměťové poţadavky nebo vyřešit problém ukládání rušivých

instancí.

5.2 Neuronové sítě

Neuronové sítě jsou výkonná metoda, která se pouţívá k modelování vztahu mezi

vícerozměrnou vstupní proměnnou x a vícerozměrnou výstupní proměnnou y. Umělou

neuronovou síť lze obecně povaţovat za nelineární regresní model, který lze vyjádřit síťovou

strukturou. Neuronové sítě řeší problémy a úkoly nejen v technologické praxi, ale také ve

výzkumu, marketingových analýzách, Data Mining, KDD a podobně. [8]

5.2.1 Inspirace

Umělé neuronové sítě jsou inspirovány biologickým mozkem. Nové poznatky nám

pomáhají při modelování přírodních systému. Neuronové sítě jsou pouţívány pro svou

schopnost učit se na omezené mnoţině (vstupu a výstupu) a generalizovat, tedy dávat správné

výsledky také u vstupů, u kterých neznáme výstupy. [9]

Obrázek 9: Umělý neuron (převzato z [9])

Umělé neuronové sítě jsou inspirovány neuronovými sítěmi v přírodě. Základním

stavebním kamenem umělé i biologické neuronové sítě je neuron. Umělý stejně jako

biologický neuron má tři části: dendrity, soma a axon. Dendrity jsou vstupy a kaţdý neuron

jich má několik. Dendrity poskytují neuronu vstupní signály, které jsou v těle neuronu (soma)

sečteny a podle výsledného signálu a prahové funkce je vyslán signál na výstup neuronu

(axon). Neuron má pouze jeden výstup (axon), který se dále větví a je napojen přes synapse

na další neurony. Synapse se dělí na dva druhy. Excitační synapse zvyšují hodnotu signálu a

inhibiční, které naopak sniţují hodnotu signálu. Míra, o kolik se hodnota signálu zvýší nebo

sníţí, se liší u kaţdé synapse.


20

5.2.2 Umělá neuronová síť

Neuronová síť vzniká ve fázi, které se říká trénovací. V této fázi máme k dispozici

mnoţinu trénovacích dat, která se skládá z vektoru vstupních hodnot a výstupní hodnoty.

Počet vstupů sítě odpovídá dimenzi vektoru z mnoţiny trénovacích dat. Tyto vektory jsou síti

postupně předkládány. Podle odezvy sítě jsou upravovány parametry neuronové sítě tak, aby

výstup sítě co nejvíce odpovídal očekávané hodnotě.

Výhodou umělých neuronových sítí je jejich schopnost generalizovat. Po naučení je síť

schopná reagovat i na vstupní vektory, které jí nebyly předloţeny v trénovací fázi. Vnitřní

struktura sítě se dělí na vrstvy. První vstupní vrstva slouţí pouze k distribuci vstupních hodnot

do další skryté vrstvy. Skrytých vrstev muţe být libovolný počet.

Mezi jednotlivými vrstvami existuje propojení. Kaţdý neuron předchozí vrstvy je

propojen s neurony následující vrstvy. To s jakou významností bude propojení přispívat do

neuronu, je dáno váhou, která je nastavována v učící fázi. Za poslední skrytou vrstvou je

vrstva výstupní, která reprezentuje výstup neuronové sítě.

Obrázek 10: GMDH síť (převzato z [9])

5.2.3 Group Method of Data Handling (GMDH)

Neuronové sítě typu GMDH jsou sítě, které jsou vytvářeny indukcí. Na rozdíl od sítí,

které pouţívají algoritmus Backpropagation, struktura sítě typu GMDH není předem známá a

vzniká aţ ve fázi učení. Síť typu GMDH vychází z několika základních stavebních jednotek,


21

které během fáze učení kombinuje a snaţí se vytvořit model nejlépe odpovídající trénovací

mnoţině dat.

Tvorba sítě začíná z minimální formy a staví se po vrstvách. Při tvorbě kaţdé vrstvy se

nejprve vygenerují neurony. Vţdy se vygeneruje tolik neuronů, kolik je moţných kombinací

výstupů z neuronů v předchozí vrstvě. Pro omezení počtu kombinací mohou mít neurony jen

omezený počet vstupů (typicky 2).

Všechny neurony realizují stejnou přenosovou funkci. Přenosová funkce je většinou

polynom a jednotlivé neurony se liší vstupy a koeficienty polynomů. Po vygenerování nové

vrstvy následuje optimalizace koeficientů tak, aby neuron dosahoval co nejmenší chyby na

trénovací mnoţině. Poslední fáze tvorby vrstvy je výběr neuronů. Všechny vytvořené neurony

jsou otestovány na validační mnoţině a neurony s nejmenší chybou jsou ponechány. Ostatní

neurony jsou smazány. Takto vytvořená nová vrstva je „zmraţena“ a dále se jiţ nemění. Učící

algoritmus pak pokračuje tvorbou nové vrstvy.

Nové vrstvy se přidávají, dokud chyba nejlepšího neuronu přesahuje zadanou hranici.

Dalším moţným kritériem na zastavení tvorby dalších vrstev je zastavení poklesu chyby

nejlepšího neuronu.

Výše popsaný postup se nazývá MIA (Multilayered Iterative Algorithm) GMDH. Další

variantou je COMBI (Combinatorial) GMDH. Neurony této sítě obsahují různé typy

polynomů a v rámci učení se zkouší různé typy polynomů.

Další informace lze najít například v [24].

5.3 Group of Adaptive Models Evolution (GAME)

Metoda GAME vylepšuje neuronovou síť typu GMDH. Dokáţe generovat přesnější

modely pro větší mnoţství dat. Hlavním přínosem metody GAME je její schopnost generovat

skupiny samoadaptujících se modelů podle charakteru a komplexnosti zadaných dat.

Induktivní model neuronové sítě roste do takové velikosti, aby byl schopen zadanou úlohu

vyrešit s poţadovanou přesností. Model se skládá z jednotek (neuronů), které nejlépe

modelují vnitřní vztahy v datech. Jednotky mohou realizovat velké mnoţství přenosových

funkcí a učící algoritmus pak můţe vybírat ty jednotky, které nejlépe odpovídají datům.

Působ tvorby sítě typu GAME je podobný jako u GMDH. Ale jak je vidět na obrázku

TODO síť typu GAME má více stupňů volnosti neţ síť typu GMDH (jednotky s různým

počtem vstupů, propojení mezi vrstvami v síti). S rostoucí dimenzí zadaných dat je nemoţné

bez další heuristiky vyhledat v obrovském stavovém prostoru různých modelů správnou

topologii. Metoda GAME v sobě zahrnuje genetický algoritmus, který vyvíjí optimální

strukturu modelu. Dalšími vylepšeními jsou:

• Několik typů jednotek (neuronů), které souteţí o přeţití v modelu.

• Rostoucí sloţitost modelu.

• Propojení mezi vrstvami.


22

• Generování skupiny modelů, které zvyšují věrohodnost odezvy modelu.

• Genetický algoritmus pro vytváření optimální topologie modelů.

• Metoda niching, která umoţňuje zachování méně přesných, ale zajímavých neuronů.

Obrázek 11: Srovnání MIA GMDH sítě se sítí GAME (převzato z [9])

Metoda GAME generuje na mnoţině učících dat modely s podobnou přesností. Modely

jsou testovány na náhodných podmnoţinách mnoţiny učících dat. Modely se skládají z

podobných typů jednotek (neuronů) a mají podobnou sloţitost. Je velice obtíţné zvolit jen

jeden nejlepší model, protoţe modely jsou si velice podobné. Proto vzniká skupina

(ensemble) modelů.

5.3.1 Nevýhody GAME

Metoda GAME dosahuje dobrých výsledků a často překonává jiné klasifikační

algoritmy. Má ale i slabé stránky. Největší nevýhoda je značná výpočetní náročnost tvorby

sítě. Další nevýhodou je nedeterministická metoda tvorby GAME modelu. Díky náhodné

inicializaci a genetickému algoritmu, kaţdý model dosahuje jiných výsledků. Pro ověření

získaných výsledků je třeba vytvořit několik modelů, coţ dále zvyšuje čas potřebný k tvorbě

modelu.

V průběhu učení jednotlivých neuronů v síti, dochází k automatické redukci dat, pokud

je trénovací mnoţina příliš velká. Pro kaţdý neuron se pak vytvoří nová redukovaná mnoţina

náhodně vybraných instancí. Tyto vybrané instance jsou pak pouţity při učení daného


23

neuronu. Protoţe jsou instance vybírány náhodně, je u velkých trénovacích mnoţin, značné

riziko, ţe budou zvoleny nevhodné instance. Trénování na nevhodně zvolených instancích

pak vede k zvětšování počtu vrstev v síti a vzrůstu její sloţitosti. Nevhodně zvolené instance

mohou dokonce vést k neschopnosti konkrétního modelu se správně naučit.

5.3.2 Předzpracování dat v projektu FAKE GAME

Neuronová síť GAME je implementována v projektu FAKE GAME. Součástí

implementace neuronové sítě v projektu FAKE GAME je také modul věnující se

předzpracování dat. Modul implementuje základní skupiny metod pro předzpracování dat.

Kaţdá skupina obsahuje několik různých předzpracovacích metod. Celkem je v současnosti

implementováno přes 40 předzpracovacích metod z následujících oblastí:

Import z různých formátů včetně MS Office XLS.

Export do různých formátů – např. Weka, MS Excel.

Normalizace dat – například lineární, soft-max, z-score.

Nahrazování chybějících hodnot – základní metody pro náhradu konstantou,

střední hodnotou apod.

Diskretizace.

Jednoduché metody pro redukci dat.

Shlukování.

Mnoţení dat v minoritní třídě.

Jednotlivé metody jsou implementovány ve formě pluginů, implementujících

jednoduché rozhraní.

V současné době je implementováno několik jednoduchých metod pro početní redukci

dat. Dvě neadaptivní metody – nazvané „Random data reducer“ a „Leave-out neighbours“.

První z metod náhodně vyřazuje instance z trénovací mnoţiny. Druhá najde počet instancí,

které jsou blíţe neţ předem zadaná vzdálenost a ponechá jen instance, které mají největší

počet sousedů, ostatní zahazuje.

Dále dvě adaptivní metody početní redukce dat – „KD-Tree cell replacer“ a „KMeans

data replacer“. První metoda nad daty vytvoří KD-strom a instance v kaţdé buňce KD-stromu

nahradí jejich centroidem. Druhá metoda „KMeans data replacer“ vyuţívá K-Means

algoritmu. V původních datech se najdou pozice předem zadaného počtu centroidů a tyto

centroidy jsou pouţity jako nová trénovací mnoţina.

Algoritmy početní redukce dat

24

Část III – Implementované algoritmy

V této části jsou detailně popsány všechny implementované redukční metody a jejich

následná integrace do projektu FAKE GAME.

6. Algoritmy početní redukce dat

Početní redukce dat, která slouţí k odstranění některých instancí z trénovací mnoţiny,

se skládá ze dvou po sobě jdoucích kroků – editování a kondenzace. Zatímco v kroku

editování jsou odstraněny instance degradující klasifikaci, v kroku kondenzace jsou

odstraněny instance, které jsou nadbytečné.

Ve své práci se zaměřuji hlavně na kondenzační algoritmy, které zajišťují sníţení

paměťových poţadavků a čas potřebný na vytvoření modelu či klasifikaci trénovací mnoţiny.

Kondenzační algoritmy se dělí na dvě skupiny. Neadaptivní algoritmy, které vybírají

podmnoţinu instancí z původní trénovací mnoţiny a adaptivní algoritmy, které generují

podmnoţinu nových reprezentantů.

V této kapitole popisuji všechny algoritmy, které jsem implementovala do GAME.

Jedná se o 4 neadaptivní algoritmy (CNN, RNN, IB3, DROP3) a 4 adaptivní algoritmy

(Prototype, Chen, RSP1, RSP3). Dále jsem implementovala vlastní algoritmus, který je

neadaptivní a nazvala jsem ji MergeAllInstances.

Pro správnou funkčnost některých kondenzačních algoritmů a pro úplnost procesu

početní redukce dat jsem implementovala také dva základní editační algoritmy.

6.1 Editační algoritmy

Editační algoritmy slouţí k předzpracování trénovací mnoţiny pro následnou

kondenzační fázi. Zaměřují se na „vyčištění dat“, kdy odstraňují všechny rušivé instance

(instance, které jsou s vysokou pravděpodobností jen šum v záznamu dat) a dále instance

velmi blízko rozhodovací hranice, protoţe na této úrovni mohou způsobovat špatnou

klasifikaci intancí. Primárním cílem editačních algoritmů je odstranění všech instancí, které

by mohly ohrozit klasifikační přesnost.

6.1.1 Editované pravidlo nejbližšího souseda

Wilson představil v roce 1972 první algoritmus pro editování, který pojmenoval

Editované pravidlo nejbliţšího souseda (Edited Nearest Neighbor Rule, dále jen ENN). Jedná

se o dávkový algoritmus, který odstraňuje instance aţ po prozkoumání všech instancí původní

trénovací mnoţiny TS. [12]


25

Wilson vyuţil faktu, ţe klasifikátor k – NN, kde k > 1, podává lepší výsledky neţ

klasifikátor 1 – NN, protoţe dokáţe odfiltrovat rušivé instance. Algoritmus ENN vyuţívá

klasifikátoru k – NN pro určení nejvíce zastoupené třídy k sousedů v TS mnoţině k dané

instanci. Typicky se pouţívá k = 3. Postupně jednotlivé instance z TS mnoţiny klasifikuje k –

NN s pouţitím trénovací mnoţiny TS bez testované instance, a pokud jejich třída neodpovídá

majoritně zastoupené třídě k sousedů, je instance označena k odstranění. Po klasifikaci všech

instancí, jsou instance označené k odstranění odebrány. Podrobněji viz Pseudokód 2.

ENN algoritmus odstraňuje z trénovací mnoţiny všechny rušivé instance a instance

leţící přímo na rozhodovací hranici. Na obrázcích viz Obrázek 12 a Obrázek 13 můţeme

pozorovat zřejmý rozdíl redukce algoritmem ENN s parametrem k = 1 a parametrem k = 3.

Označené instance budou odstraněny.

Obrázek 12: ENN redukce s k = 1 Obrázek 13: ENN redukce s k = 3

Pseudokód 2: ENN algoritmus

Popisy použitých proměnných

TS – původní trénovací množina

R – výsledná redukovaná množina instancí

k – počet hledaných nejbližších sousedů


kNN(instance t, množina X, int k) – nalezne k instanci t k nejbližších

sousedů z množiny X. Pokud je většina z k nejbližších sousedů z množiny X

ohodnocena stejnou třídou jako instance t vrací TRUE, jinak vrací FALSE.


//Počáteční inicializace

1. k = vstup()

R = Ø

//Pro všechny instance t z původní trénovací množiny TS

2. for all t from TS {

//dočasně odstraní instanci t z původní trénovací množiny TS

TS = TS - t

// a nalezne k instanci t k nejbližších sousedů z množiny TS.

// pokud je většina z k nejbližších sousedů ohodnocena stejnou třídou

// jako instance t

if (kNN(t,TS,k) == TRUE) {


26

// přidá instanci t do finální redukované množiny

R = R + t

}

// instanci t vrátí zpět do původní trénovací množiny TS

TS = TS + t

//Vrátí výslednou redukovanou množinu

3. return R

6.1.2 Editovací schéma All k – NN

V roce 1976 vymyslel I. Tomek rozšíření algoritmu ENN, které nazval Editovací

schéma All k – NN. Primárním cílem tohoto algoritmu bylo rozšíření pouţitelnosti ENN

algoritmu na libovolnou trénovací mnoţinu TS. Opět vyuţívá dávkové strategie, kdy

odstraňuje instance aţ po prozkoumání všech instancí původní TS mnoţiny. [13]

Algoritmus opět vyuţívá k – NN klasifikátoru. V tomto algoritmu se nepouţívá jen

jeden k – NN klasifikátor, ale jejich skupina s počtem sousedů v rozmezí 1…k. Všechny

instance z mnoţiny TS jsou klasifikovány skupinou klasifikátorů bez testované instance.

Pokud třída instance neodpovídá v libovolné iteraci i majoritní třídě sousedů, je instance

označena k odstranění. Po klasifikaci všech instancí, jsou instance označené k odstranění

odebrány. Podrobněji viz Pseudokód 3.

All k – NN algoritmus tak odstraňuje podstatně více rušivých instancí neţ ENN

algoritmus, ale na druhé straně také více sniţuje klasifikační přesnost. Z obrázků viz Obrázek

14 a Obrázek 15 můţeme sledovat rozdíl mezi algoritmy ENN a All k – NN s nastaveným

parametrem k = 3. Instance označené budou z původní trénovací mnoţiny odstraněny.

Obrázek 14: ENN redukce s k = 3 Obrázek 15: All k – NN s k = 3


27

Pseudokód 3: Algoritmus All k – NN




k – počet hledaných nejbližších sousedů

delete – příznak zda je možné instanci přidat do výsledné redukované

množiny


kNN(instance t,množina X, int k) – nalezne k instanci t k nejbližších

sousedů z množiny X. Pokud je většina z k nejbližších sousedů z množiny X

ohodnocena stejnou třídou jako instance t vrací TRUE, jinak vrací FALSE.


//Počáteční inicializace

1. k = vstup()

R = Ø

delete = FALSE

// Pro všechny instance t z původní trénovací množiny TS


// dočasně odstraní instanci t z původní trénovací množiny TS

TS = TS - t

// Provede iteraci proměnné k od 1 až do k

for all k from 1..k {

// a nalezne k nejbližších sousedů k instanci t z množiny TS.

// Pokud není většina z k nejbližších sousedů ohodnocena

// stejnou třídou jako instance t

if (kNN(t, TS, k) == FALSE) {

//nastaví příznak, že instance nebude přidána do výsledné

// redukované množiny R

delete = TRUE

}

}

// Pokud je instance t ohodnocena svými sousedy správně ve všech

// iteracích k přidá ji do výsledné redukované množiny R

if (delete == FALSE) {

R = R + t

}

// instanci t vrátí zpět do původní trénovací množiny TS

TS = TS + t

// vynuluje příznak

delete = FALSE

}

3. //Vrací výslednou redukovanou množinu

return R

6.2 Neadaptivní kondenzační algoritmy

Hlavním úkolem kondenzačních algoritmů je získání značně redukované mnoţiny, ale

bez významného sníţení klasifikační přesnosti. Neadaptivní kondenzační algoritmy tento úkol

řeší selekcí některých instancí z původní trénovací mnoţiny. Instance vybírají velmi

důmyslně tak, aby instance leţící v oblasti dané třídy byly opravdu klasifikovány touto třídou.

Zásadou neadaptivních kondenzačních algoritmů je, ţe nikdy instance nemodifikují. [23][25]


28

6.2.1 Kondenzované pravidlo nejbližšího souseda

Kondenzované pravidlo nejbliţšího souseda (Condensed Nearest Neighbor Rule, dále

jen CNN) je prvním neadaptivním algoritmem pro početní redukci dat. Původně byl

zamýšlený pouze pro klasifikátor 1 – NN. Vymyslel jej v roce 1968 P. E. Hart. Je zaloţen na

myšlence, ţe čím více jsou instance od rozhodovací hranice vzdálené, tím méně jsou potřebné

a ţe pokud je instance svým nejbliţším sousedem špatně ohodnocena, tak s vysokou

pravděpodobností leţí poblíţ rozhodovací hranice. CNN je typickým představitelem

inkrementálních algoritmů, tudíţ je závislý na uspořádání vstupní trénovací mnoţiny TS. [14]

Algoritmus hledá podmnoţinu S trénovací mnoţiny TS tak, aby pro všechny instance

TS byl nejbliţší soused v podmnoţině S klasifikován stejnou třídou. Tento způsob je

konzistentní (všechny instance v mnoţině TS jsou podmnoţinou S ohodnoceny správně),

ovšem nezaručuje minimálnost podmnoţiny S. Záleţí na uspořádání instancí vstupní TS

mnoţiny. Při rozdílném uspořádání instancí vstupní TS mnoţiny je sice výsledná podmnoţina

S stále konzistentní, ale můţe mít jiný počet instancí.

Algoritmus začíná náhodným výběrem jedné instance v TS, kterou přesune do prázdné

podmnoţiny S, viz Obrázek 16. Pak kaţdou instanci v TS mnoţině, která je špatně

klasifikována podmnoţinou S, přesune do mnoţiny S viz Obrázek 17, čímţ zajistí, ţe bude

klasifikována správně. Tento proces opakuje aţ do doby, kdy nejsou ţádné instance v TS

špatně klasifikovány podmnoţinou S viz Obrázek 18. Podrobněji viz Pseudokód 4.

Obrázek 16: CNN náhodný výběr instance


29

1.

3.

2.

4.

5.

7. 6.

Obrázek 17: CNN klasifikační krok

1.

3. 2.

Obrázek 18: CNN splněna klasifikační podmínka

Tento algoritmus je obzvláště citlivý na rušivé instance, protoţe rušivé instance jsou

obvykle jiné třídy neţ jejich sousedé a proto jsou uloţeny do výsledné podmnoţiny S. Díky

tomu má tento algoritmus dva velké nedostatky.

Prvním nedostatkem je, ţe paměťová sloţitost není dostatečně redukována, protoţe je

ponechávána většina rušivých instancí a navíc musí být ponechávány nerušivé instance, které

jsou poblíţ instancí rušivých.

Druhým problémem je nízká přesnost klasifikace způsobená taktéţ rušivými

instancemi. Zatímco nerušivé instance jsou redukovány, rušivé instance jsou většinou

ponechány. Proto je vhodné vstupní TS nejprve editovat pouţitím některého z editačních

algoritmů.

Pseudokód 4: Algoritmus CNN




změna – příznak, zda došlo v předchozím kroku ke změně



30

1NN(instance x,množina X) – klasifikuje instanci x z testovací množiny

pomocí klasifikátoru 1-NN s použitím trénovací množiny X. V případě, že je

instance x klasifikována správně, vrátí TRUE. Jinak vrátí FALSE.

random(množina X)- vrátí náhodně vybranou instanci z množiny X

// Počáteční inicializace

1. R = Ø, změna = FALSE

// Náhodně vybere instanci x z původní trénovací množiny TS

2. x = Random(TS)

// a vloží jej do prázdné množiny R

3. R = R + x

// Pro všechny instance t v trénovací množině TS provede klasifikaci

// pomocí metody 1 - NN, kde jako trénovací množinu použije množinu R.


// Pokud instance není správně klasifikována, tak jí vloží do množiny

R

if (1NN(t, R) == 0){

R = R + t

// a nastaví příznak, že došlo ke změně

změna = TRUE

}

}

// Pokud došlo v předchozím kroku ke změně R množiny znovu opakuje

// předchozí krok

5. if (změna == TRUE) {

změna = FALSE

Pokračuj bodem 4

}

// Vrací výslednou redukovanou množinu R

6. return R

6.2.2 Redukované pravidlo nejbližšího souseda

Hlavním důvodem proč CNN algoritmus neponechává vţdy minimální počet instancí je,

ţe v prvních krocích algoritmu jsou přidány instance, které se v pozdějších krocích, díky

přidání dalších instancí, mohou stát redundantní. Řešení tohoto problému představil v roce

1972 G. W. Gates. Algoritmus, který rozšiřuje algoritmus CNN, pojmenoval Redukované

pravidlo nejbliţšího souseda (Reduce Nearest Neighbor Rule, dále jen RNN). [15]

RNN algoritmus nejprve získá zredukovanou mnoţinu TCNN pouţitím CNN algoritmu

a následně tuto mnoţinu dekrementálně redukuje. Díky pouţití inkrementálního CNN

algoritmu je ovšem závislý na uspořádání vstupní mnoţiny instancí.

Algoritmus v první fázi zredukuje trénovací mnoţinu TS pouţitím CNN algoritmu a

získanou zredukovanou mnoţinu TCNN si zkopíruje do finální redukované mnoţiny TRNN.

Pak se kaţdou instanci z TRNN mnoţiny pokusí odebrat a pokud jsou všechny instance

původní TS mnoţiny 1 – NN klasifikátorem s trénovací mnoţinou TRNN bez dané instance

klasifikovány správně, pokračuje zpracováváním další instance z mnoţiny TRNN. V opačném

případě ji vrátí zpět do TRNN mnoţiny. Podrobněji viz Pseudokód 5.

Na obrázku viz Obrázek 19 a je naznačena původní trénovací mnoţina, která je

zredukována nejprve CNN algoritmem viz Obrázek 19 b a následně je zobrazena redukovaná

mnoţina aplikováním RNN algoritmu viz Obrázek 19 c.


31

a b c

Obrázek 19: Původní mnoţina, CNN podmnoţina a RNN podmnoţina

Zajímavá je jistě otázka, zda získaná redukovaná mnoţina TRNN je minimální

podmnoţinou TS mnoţiny. Je zřejmé, ţe TRNN mnoţina je podmnoţinou mnoţiny TCNN.

Tudíţ pokud TCNN neobsahuje minimální podmnoţinu TS, nemůţe být obsaţena ani v

mnoţině TRNN. To je způsobeno inkrementálností CNN algoritmu, díky níţ je výsledná

redukovaná mnoţina závislá na uspořádání vstupní trénovací mnoţiny.

Pokud však TCNN obsahuje minimální podmnoţinu TS, RNN algoritmus získá

minimální konzistentní podmnoţinu mnoţiny TS.

RNN algoritmus má v porovnání s CNN algoritmem vyšší výpočetní sloţitost, ale vţdy

nám zajistí získání podmnoţiny mnoţiny TCNN a tak více sniţuje paměťové poţadavky a

urychluje klasifikační proces či učící proces.

Pseudokód 5: Algoritmus RNN


T – původní trénovací množina

TCNN - zredukovaná původní trénovací množina T použitím CNN algoritmu (Hart)

TRNN - výsledná redukovaná množina instancí klasifikace – pokud jsou všechny instance původní trénovací množiny

klasifikovány správně, vrací TRUE, jinak vrací FALSE.


1NN(instance x,množina X) – klasifikuje instanci x z testovací množiny

pomocí klasifikátoru 1 - NN s použitím trénovací množiny X. V případě, že

je instance x klasifikována správně, vrací TRUE. Jinak vrací FALSE.

hart(množina X) – vrací redukovanou množinu X použitím CNN (Hartova)

algoritmu


// Zredukuje původní trénovací množinu použitím CNN algoritmu (Hart).

1. TCNN = hart(T)

// Zkopíruje zredukovanou množinu TCNN do množiny TRNN.

2. TRNN = TCNN

// Pro všechny instance c z množiny TCNN

3. for all c from TCNN {

// se pokusí instanci c odebrat.

TRNN = TRNN – c


32

// Nastaví příznak správnosti klasifikace na TRUE.

klasifikace = TRUE

// Pro všechny instance t z původní trénovací množiny T

for all t from T{

// Testuje, zda je instance t klasifikována klasifikátorem

// 1 - NN s použitím původní trénovací množiny TRNN(bez prvku c)

// správně. Pokud není, nastaví příznak klasifikace na FALSE.

if (1NN(t, TRNN) == FALSE){ klasifikace = FALSE

}

}

// Pokud nejsou všechny instance z původní trénovací množiny T

// klasifikovány správně množinou TRNN (bez prvku c), přidá instanci c

// zpět do množiny TRNN.

if (klasifikace == FALSE){

TRNN = TRNN + c }

}

4. // Množina TRNN obsahuje konzistentní podmnožinu množiny TCNN TRNN TCNN

// Vrací výslednou redukovanou množinu TRNN

return TRNN

6.2.3 Učící algoritmy založené na instancích

V roce 1991 prezentoval D. W. Aha sérii učících algoritmů (IB1, IB2, IB3) zaloţených

na instancích (Instance – Based learning algorithm, dále jen IBL). Tyto algoritmy byly

navrţeny pro značnou redukci počtu trénovacích instancí bez ztráty přesnosti. [16]

IB1 (Instance Based learning algorithm 1) je velmi jednoduchý algoritmus podobný

1 - NN klasifikátoru a pouţívaný jako základ pro ostatní IBL algoritmy.

IB2 (Instance Based learning algorithm 2) je inkrementální algoritmus. Je velmi

podobný CNN algoritmu, vybírá pouze instance, které nejsou správně klasifikovány. Narozdíl

od CNN algoritmu provádí pouze jeden průchod přes všechny trénovací instance a tak

nezaručuje, ţe získaná redukovaná mnoţina bude konzistentní s původní trénovací mnoţinou.

Zanechává instance poblíţ rozhodovací hranice a eliminuje vnitřní instance, které jsou

obklopeny instancemi stejné třídy. IB2 algoritmus má stejné nedostatky jako CNN

algoritmus. Ukládá redundantní instance a je citlivý na rušivé instance.

IB3 (Instance Based learning algorithm 3) je dalším inkrementálním algoritmem, který

odstraňuje problém IB2 algoritmu, ukládání rušivých instancí. Zanechává pouze přijatelné

špatně klasifikované instance. Vyuţívá strategie ,,počkej a uvidíš” k určení instancí, které jsou

důleţité pro klasifikaci a k odstranění instancí, které jsou s vysokou pravděpodobností rušivé.

Instance je povaţována za přijatelnou, pokud je její spodní hranice přesnosti statisticky

podstatně vyšší (většinou pouţívána 90% úroveň spolehlivosti) neţ horní hranice odhadu

početního zastoupení její třídy v původní trénovací mnoţině. Na druhé straně instance je

odstraněna pokud je její spodní hranice přesnosti statisticky podstatne niţší (většinou


33

pouţívána 70% úroveň nespolehlivosti) neţ spodní hranice odhadu početního zastoupení její

třídy v původní trénovací mnoţině.

Rovnice pro určení horní a dolní hranice pro danou úroveň spolehlivosti vypadá

následovně:

𝜉 +𝑧2

2𝑛 ∓ 𝑧 (𝜉 1 − 𝜉

𝑛 +𝑧2

4𝑛2 )

1 +𝑧2

𝑛

kde 𝜉 je v případě určení hranic přesnosti instance správnost záznamu a v případě určení

hranic odhadu početního zastoupení její třídy odhad zastoupení instancí této třídy v původní

trénovací mnoţině. Proměnná z je úroveň spolehlivosti (většinou pro určení hranic přesnosti

0.9 a pro určení hranic odhadu početního zastoupení třídy instance 0.7), n je počet instancí

dané třídy, které jiţ byly zpracovány. Podrobněji viz Pseudokód 6.

Tímto postupem IB3 algoritmus redukuje více instancí neţ IB2 algoritmus a navíc

zachovává vyšší klasifikační přesnost. Nevýhodou IB3 algoritmu je citlivost na počet

irelevantních atributů pouţitých k popisu instancí. S narůstajícím počtem atributů rostou jeho

paměťové nároky exponenciálně. Proto je vhodné před pouţitím algoritmu IB3 pouţít

algoritmy na výběr reprezentativních atributů.

Pseudokód 6: Algoritmus IB3



S – pomocná množina

B – výsledná redukovaná množina platných instancí B S

MH - horní mez spolehlivosti

ML - dolní mez spolehlivosti

n[#class(množina TS)] - pole n o velikosti dle počtu tříd z původní

trénovací množiny TS, které slouží k čítání zastoupení instancí

jednotlivých tříd v množině S

p[#class(množina TS)] – pole p o velikosti dle počtu tříd v původní

trénovací množině, které slouží k odhadu zastoupení jednotlivých tříd v

původní trénovací množině

n - postupně inkrementovaný počet instancí z původní trénovací množiny,

které již byly zpracovány

random - procentuální počet instancí, které je potřeba náhodně vybrat při

počáteční inicializaci z původní trénovací množiny. Parametr je v rozmezí

0..1

randomlist - seznam náhodně vybraných instancí z původní trénovací množiny

classes – seznam všech tříd které jsou zastoupeny v množině TS


V množině S pro každou instanci s:

s.a - správnost záznamu (pravděpodobnost správné klasifikace při výběru

instance s)

s.podobnost - podobnost instance s k testované instanci

s.b - platnost záznamu (pokud je instance s přijatelná s.b = 1, jinak

s.b = 0)

s.u - počet updatů dané instance


34


getRandomList(množina X, int p) - vrací seznam instancí, které byly dle

zadaného procentuálního počtu p náhodně vybrány z množiny X

maxPodobnost(množina B) – vrací instanci z množiny B, která má největší

podobnost

class(instance x) – vrací třídu instance x

#class(množina X) - vrací celkový počet tříd zastoupených v množině X

podobnost(instance x, instance y) – vrací záporně ohodnocenou euklidovu

vzdálenost mezi instancemi x a y, přes všechny jejich atributy

(− (xi − yi)2)n

i=1

random(množina X)- vrací náhodně vybranou instanci z množiny X


allClasses(množina X) – vrací seznam všech tříd, které jsou v množině X

zastoupeny


1. S = Ø, B = Ø

// Načte horní mez spolehlivosti MH a spodní mez spolehlivosti ML

MH = vstup()

ML = vstup()

// Načte procentuální zastoupení množiny TS v množinách B a S

random = vstup()

// Vytvoří pole n a pole p o velikosti počtu tříd v původní trénovací

množině TS

n[#class(TS)]

p[#class(TS)]

classes = allclasses(TS)

// Náhodně vybere vzorky z původní trénovací množiny TS

2. randomlist = getrandomlist(TS,random)

// Pro všechny náhodně vybrané instance

3. for all s from randomlist {

//Vložení náhodně vybraného vzorku s do množiny S

S = S + s

// Počáteční nastavení hodnot pro instanci s

// Správnost instance

s.a=1

// Platnost instance

s.b=1

// Počet updatů instance

s.u=1

// Přidání instance do množiny platných záznamů

B = B + s

// Procentuální zastoupení jednotlivých tříd prvků z trénovací množiny

n[class(s)] = n[class(s)] + 1

// Postupně inkrementovaný počet prvků z původní trénovací množiny

n = n + 1

// Odhad pravděpodobnosti zastoupení jednotlivých tříd v množině S

dle postupného procházení množiny TS

p[class(s)] = n[class(s)] / n

}


4. for all t from TS

// Pro všechny instance s z množiny S

4.1 for all s from S{

// vypočte funkci podobnosti

s.podobnost = podobnost(s,t)

}

// Pokud množina platných záznamů B není prázdná, kde B={B|s.b = 1}

4.2 if (B != Ø)

// nalezne nejpodobnější instanci ymax k instanci t z množiny B.

ymax = maxpodobnost(B)

}


35

// Jinak vybere náhodnou instanci z množiny S.

4.3 else {

ymax = random(S)

}

// Pokud třída(t) = třída(ymax) přeskočí následující krok

4.4 if (class(t) == class(ymax)) {

Pokračuj bodem 4.6

}

// Jinak přidá vzorek t do množiny S a do množiny B a nastaví

// potřebné hodnoty

4.5 else {

S = S + t

B = B + t

t.a = 1

t.b = 1

t.u = 1

}

// Nastaví odhad pravděpodobnosti zastoupení jednotlivých tříd a

// celkové počty

4.6 for all c from classes {

if (c == class(t)) {

p[c]=(n[c]+1)/(n+1)

}

else {

p[c]=n[c]/(n+1)

}

n(class(t)) = n(class(t)) + 1

n = n + 1

}

// Pro všechny instance y z množiny S, které jsou stejně

// podobné k instanci t nebo podobnější než ymax proveď

4.7 for all y from S {

if (y.podobnost >= ymax.podobnost){

// Pokud třída(y)=třída(t)

if (class(y) == class(t)){

// aktualizuje hodnotu správnosti záznamu

y.a = (y.a*y.u+1)/(y.u+1) //zvýšení

}

// Jinak když třída(y) ≠ třída(x)

else {

//aktualizuje hodnotu správnosti záznamu

y.a = (y.a*y.u)/(y.u+1) //snížení

}

// Aktualizuje počet updatů dané instance

y.u = y.u+1

// Statisticky určí platnost záznamu dané instance

p = p[class(y)]

a = y.a

z = MH

ξ = a

n = y.u

[LMHa,HMHa]=ξ+

z2

2n ∓ z (

ξ 1-ξ

n+

z2

4n2 )

1+z2

n

z = MH

ξ = p

n = n[class(y)]

[LMLp,HMLp]=ξ+

z2

2n ∓ z (

ξ 1-ξ

n+

z2

4n2 )

1+z2

n


36

// Pokud LMHa > HMHp y.b=1 instance y je platná pro další zpracování

if (LMHa > HMHp) {

y.b = 1

B = B + y

}

//Jinak y.b = 0 instance y není platná

else {

y.b = 0

B = B – y

}

// Statisticky určí, které instance je třeba odstranit

z = ML

ξ = a

n = y.u

[LMLa,HMLa]=ξ+

z2

2n ∓ z (

ξ 1-ξ

n+z2

4n2 )

1+z2

n

z = ML

ξ = p

n = n[class(y)]

LMLp,HMLp]=ξ+

z2

2n ∓ z (

ξ 1-ξ

n+

z2

4n2 )

1+z2

n

// Odstraní instance nesplňující spodní mez spolehlivosti

if (HMLa < LMLp){

S = S - y

B = B - y

}

}

// Vrací redukovanou množinu B (všechny platné instance )

5. return B

6.2.4 Dekrementální redukční optimalizační procedura

V letech 1997 a 1998 představili D. Wilson a T. Martinez rodinu algoritmů (DROP1,

DROP2, DROP3) nazvaných Dekrementální redukční optimalizační procedura (Decremental

Reduction Optimization Procedure, dále jen DROP), které byly dříve představeny pod jmény

RT1 – RT3. [18]

Algoritmy vyuţívají pro kaţdou instanci dva pomocné seznamy. Seznam k nejbliţších

sousedních instancí a seznam asociovaných instancí (instance, které danou instanci mají ve

svém seznamu k nejbliţších sousedních instancí). Parametr k se většinou volí nízké liché celé

číslo jako 1, 3 nebo 5. Jiţ z názvu je zřejmé, ţe se jedná o dekrementální algoritmy. Začínají s

úplnou trénovací mnoţinou a postupně z ní odebírají instance. Instance je odstraněna, pokud

je více či stejně asociovaných instancí klasifikováno správně bez této instance.

DROP1 je nejjednodušším členem rodiny algoritmů, který odstraňuje instanci v případě

splnění zmiňovaného pravidla. A po kaţdém odstranění aktualizuje seznamy asociovaných

prvků a nejbliţších sousedů. Tento algoritmus odstraňuje rušivé instance, protoţe rušivé

instance mají většinou asociované instance jiné třídy a tak jsou s vysokou pravděpodobností

bez této instance klasifikovány správně. Ovšem s odstraňováním rušivých instancí mohou

nastat komplikace. Rušivé instance mají téměř vţdy asociované instance rozdílné třídy a jsou

v trénovací mnoţině minoritně zastoupeny. Avšak pokud jsou asociované instance rušivých


37

instancí algoritmem odstraňovány, zastoupení rušivých instancí v trénovací mnoţině se můţe

rapidně zvyšovat. Pokud by většina sousedů rušivé instance byla odstraněna dříve neţ

samotná rušivá instance, je moţné, ţe instance nebude odstraněna, protoţe do jejího

ohodnocení budou zasahovat instance velmi vzdálené, které mohou být stejné třídy jako

rušivá instance.

DROP2 algoritmus řeší problém algoritmu DROP1 s odstraňováním rušivých instancí.

Pouţívá stejný postup jako algoritmus DROP1, ale instanci, která je určena k odstranění

neodstraňuje sousedním instancím z jejich seznamu asociovaných instancí. Kaţdá instance

tak můţe mít v seznamu asociovaných instancí instance, které jsou jiţ odstraněny, ale které

mohou pomoci ke správnému odstranění rušivých instancí. Další změnou oproti DROP1

algoritmu je počáteční uspořádání instancí podle vzdálenosti k nejbliţšímu protivníkovi

(nejbliţší soused k instanci, který je ohodnocen jinou třídy neţ instance). Kdy jsou instance

více vzdálené od rozhodovací hranice odstraňovány přednostně, coţ zvyšuje šance na

ponechání intancí poblíţ rozhodovací hranice.

Problémem řazení instancí v algoritmu DROP2 je, ţe rušivé instance mohou být taktéţ

poblíţ rozhodovací hranice. To můţe drasticky změnit uspořádání redukovaných instancí.

Poté mohou být poblíţ rozhodovací hranice odstraněny nesprávné instance.

DROP3 je hybridní algoritmus, který kombinuje editační algoritmus ENN s algoritmem

DROP2. Nejprve ENN algoritmus odstraní rušivé instance a instance poblíţ rozhodovací

hranice čímţ jemně „vyhladí“ rozhodovací hranici. Tím je vyřešen problém algoritmu

DROP2, kdy mohou rušivé instance blízko rozhodovací hranice značně ovlivnit prvotní

uspořádání instancí pro předpokládanou redukci. Pak opět instance sestupně seřadí podle

vzdálenosti k nejbliţší instanci jiné třídy a aplikuje stejný postup jako algoritmus DROP2.


Pseudokód 7: Algoritmus DROP3



TW – odfiltrovaná množina (bez ustřelených hodnot) TS použitím Wilsonova

algoritmu

TWS – seřazená množina TW vzestupně podle vzdálenosti k nejbližšímu

protivníkovi

with - počet asociovaných instancí k instanci i, správně ohodnocených s

instancí i, k+1 nejbližšími sousedy

without - počet asociovaných instancí k instanci i, správně ohodnocených

bez instance i, k nejbližšími sousedy

novy - pomocná instance


V množině TS pro každou instanci t:

t.seznamN[] - seznam sousedních prvků (k+1 nejbližších instancí)

t.seznamA[] - seznam asociovaných prvků (prvků, které mají instanci t v

seznamu sousedních prvků (t ∈ a.seznamN) t.de - Eulerova vzdálenost k nejbližšímu protivníkovi (nejbližší instanci k

instanci t, která je jiné třídy než instance t)


38


wilson(množina M) – odfiltruje ustřelené hodnoty z množiny M použitím

Wilsonova algoritmu

najdiSousedy(instance x, množina X, int počet) – nalezne dle zadaného počtu

seznam nejbližších sousedů k instanci x z množiny X


najdiProtivnika(instance x, množina X) – nalezne nejbližšího souseda k

instanci x v množině X, který je jiné třídy než instance x


x, y ( (xi − yi)2)n

i=1

sort(množina X) – vrací seřazenou množinu X vzestupně podle de (vzdálenost

k nejbližšímu protivníkovi)

dalsiN(instance x, množina X, seznam N) – nalezne další nejbližší instanci

k instanci x z množiny X, která ještě není v seznamu N

klasifikace(instance t, seznamN) – pokud většina instancí ze seznamu

seznamN má stejnou třídu jako instance t vrací TRUE. Jinak vrací FALSE.

// Načte počet nejbližších sousedů k

1. k = vstup()

// Odfiltruje ustřelené hodnoty použitím Wilsonova algoritmu v TS množině

2. TW = wilson(TS)

// Pro všechny instance t v množině TW

3. for all t from TW {

// najde k instanci t k+1 nejbližších sousedů z množiny TW a

// uloží je do seznamuN

t.seznamN = najdiSousedy(t, TW, k+1)

// Pro všechny prvky ze seznamuS

for all n from t.seznamN {

// nastaví příznak, že t je jeho asociovaný prvek

n.seznamA = n.seznamA + t

}

// Nalezne nejbližšího soupeře (instance s jinou třídou) z množiny

// TW a urči k němu vzdálenost

t.de = vzdalenost(t, najdiProtivnika(t,TW))

}

// Podle vzdálenosti k soupeřovi seřadí instance v množině TW sestupně

4. TWS = sort(TW)

// Pro každou instanci t v množině TWS

5. for all t from TWS {

// inicializuje proměnné with a without

with = 0

without = 0

// Pro všechny asociované instance a k instanci t

for all a from t.seznamA {

// určí počet asociovaných instancí k instanci t, které jsou

// pomocí k+1NN (zahrnují t) klasifikovány správně

if (klasifikace(t, a.seznamN) == TRUE) {

with = with+1

}

// určí počet asociovaných instancí k instanci t, které jsou

// pomocí kNN klasifikovány správně, když neobsahují mezi

// sousedy instanci t

if (klasifikace(t, a.seznamN - t) == TRUE) {

without = without+1

}

}

// Pokud je více či stejně asociovaných instancí bez instance t

// klasifikováno správně

if (without >= with) {

// odstraní instanci t z množiny TWS

TWS = TWS - t

// Pro všechny asociované instance a k instanci t ze seznamuA


39

for all a from t.seznamA {

// odstraní instanci t ze seznamu nejbližších sousedů

a.seznamN = a.seznamN - t

// a nalezne nového nejbližšího souseda k instanci a z množiny TWS

novy = dalsiN(a, TWS, a.seznamN)

// přidá jej do seznamuN

a.seznamN = a.seznamN + nový

// Novému nalezenému sousedovi nastaví příznak, že je jeho asoc.

// prvek

novy.seznamA = seznamA + a

}

// Pro všechny sousední instance n k instanci t

}

}

// Vrací redukovanou množinu TWS

6. return TWS

6.3 Adaptivní kondenzační algoritmy

V předchozí kapitole jsem přestavila všechny implementované neadaptivní kondenzační

algoritmy. Druhá skupina kondenzačních algoritmů se nazývá adaptivní. Jedná se o algoritmy,

které vytvářejí redukovanou mnoţinu generováním nových prototypů, které nahrazují

původní instance. Největší výhoda této techniky je moţnost umísťovat generované prototypy

na pozice, kde jsou nejvíce potřebné.

6.3.1 Prototypy

V roce 1974 představil C. L. Chang jeden z prvních adaptivních kondenzačních

algoritmů pro početní redukci dat, který nazval Prototypy (Prototypes). Jedná se o

dekrementální algoritmus, který se snaţí spojovat všechny dvojice nejbliţších instancí stejné

třídy do jednoho prototypu, který je umístěn mezi nimi. Instance jsou spojeny, pokud jejich

spojení nesniţuje klasifikaci původní trénovací mnoţiny. [19]

Algoritmus začíná s úplnou trénovací mnoţinou viz Obrázek 20 b, kde všechny instance

nazývá prototypy. Na obrázku viz Obrázek 20 a je znázorněna původní trénovací mnoţina TS,

která se v dalších krocích pouţívá jako testovací mnoţina. Na počátku tedy 1-NN klasifikátor

klasifikuje správně všechny instance trénovací mnoţiny. Dále algoritmus vyhledá prototypy,

které jsou nejbliţší a navíc mají stejnou třídy, coţ jsou na viz Obrázek 20 b prototypy A a B a

pokusí se je spojit. (vytvoří nový prototyp, který vznikne zprůměrováním všech atributů obou

prototypů). Vznikne tak prototyp H viz Obrázek 20 c. I s novým prototypem H je TS mnoţina

klasifikována správně. Podobně se dále spojí prototypy H a C a vznikne nový prototyp I viz

Obrázek 20 e. Spojí se prototypy F a G a vznikne prototyp J viz Obrázek 20 e. A finálně se

spojí prototypy D a E a vznikne nový prototyp K viz Obrázek 20 f. Avšak kdybychom

pokračovali spojením prototypů I a J, některé instance z TS mnoţiny by byly klasifikovány

špatně. Proto proces spojování končí a na obrázku f je výsledná redukovaná mnoţina.



40

a)

b)

c)

d)

e)

f)

A B C

E

F GD

H C

E

F G

D

I

I

I

D

D J

JK

E

E F G

Obrázek 20: Algoritmus Prototypy

Tato metoda dosahuje dobrých výsledků, i kdyţ je velmi citlivá na jeden či více

irelevantních atributů pouţitých k popisu instancí. Proto je vhodné pouţívat algoritmy pro

redukci irelevantních atributů. Dále je algoritmus výpočetně hodně náročný, protoţe je v

kaţdé iteraci potřeba vypočítat dvě sousední nejbliţší instance. Bez vhodné optimalizace je

pro reálná data s počtem instancí vyšším neţ 10000 nepouţitelný.

Pseudokód 8: Algoritmus Prototypy

Popisy použitý proměnných


A – množina do které se přesunují „redukované“ body z množiny B, na konci

obsahuje finální redukovanou množinu prvků

B – na začátku úplná trénovací množina, v dalších cyklech kopie A množiny

C – seznam všech tříd, které mohou nabývat instance z množiny TS

MERGE - počet spojených instancí p* v jednom cyklu

p, q – pomocné testované instance


V množině T pro každou instanci t:

t.Nt nejbližší soused z množin A a B

t.bt vzdálenost instance t v TS k nejbližší instanci z množin A a B, která

má jinou třídu než instance t

t.wt vzdálenost instance t v TS k nejbližší instanci z množin A a B, která

má stejnou třídu jako instance t

t.wt' dočasná zkušební vzdálenost wt

t.bt' dočasná zkušební vzdálenost bt

V množině A pro každou instanci a:

a.Na nejbližší soused k instance a z množiny B

a.Dab Euklidova vzdálenost instance a k jejímu nejbližšímu sousedovi z

množiny B a.Na


41


najdiSouseda(instance x, množina X) – nalezne nejbližšího souseda k

instanci x z množiny X

najdiSouseda(instance x,množina X,třída c) – nalezne nejbližšího souseda k

instanci x, z množiny X, který je třídy c

class(bod a) – vrací třídu bodu a

random(množina X)- vrací náhodně vybranou instanci z množiny X

allClasses(množina X) – vrací seznam všech tříd, které jsou v množině X

zastoupeny

najdiProtivnika(instance x, množina X) – nalezne nejbližšího souseda k

instanci x v množině X, který je jiné třídy než instance x

minDab(množina X) – nalezne v množině X instanci s nejnižší vzdáleností k

nejbližšímu soused z množiny B x.Dab

merge(x, y) - vrací novou instanci, kde pro všechny atributy instance x a

instance y vypočítá průměrnou hodnotu. Třída instance je rovna třídě

instancí class(x) = class(y)


x, y ( (xi − yi)2)n

i=1

//Prvotní inicializace

1. A = Ø

B = Ø

C = allClasses(TS)

// Pro všechny body t v původní trénovací množině TS


// nastaví jako nejbližšího souseda Nt sebe samého

t.Nt = t

// nastaví vzdálenost wt k nejbližšímu sousedovi Nt na 0

t.wt = 0

// nalezne nejbližšího soupeře (prvek s jinou třídou) z množiny TS

// a určí k němu vzdálenost

t.bt = vzdalenost(t, najdiProtivnika(t,TS))

}

// Zkopíruje instance původní trénovací množiny TS do množiny B, T->B

3. B = T

// Náhodně vybere instanci b z množiny B

4. b = random(B)

// Přesune instanci b z množiny B do množiny A

5. A = A + b

B = B - b

// Inicializuje čítač spojených instancí

6. MERGE = 0

// Pokud je množina B prázdná

7. if (B == Ø)

//a pokud je počet spojených instancí roven 0

if (MERGE == 0)

Pokračuj bodem 12

// došlo-li alespoň k jednomu spojení instancí

else {

// Přesune instance z množiny A do množiny B A->B

B = A

A = Ø

Pokračuj bodem 4

}

8. //Pro všechny instance a z množiny A

for all a from A {

// nalezne nejbližšího souseda Na z množiny B

a.Na = najdiSouseda(a,B)

// uloží si vzdálenost Dab k nejbližšímu sousedu Na

a.Dab = vzdalenost(a, Na)

}


42

// Nalezne v množině A instanci p s nejmenší Dab

9. p = minDab(A)

// Uloží si nejbližšího souseda Na k instanci p z množiny B do bodu q

10. q = p.Na

// Pokud jsou instance p a q stejné třídy

11. if (class(p) == class(q)) {

//spojí tyto dvě instance – aritmetický průměr všech atributů

//a vytvoří novou instanci p*

p* = merge(p,q)

//třída instance p* je stejná jako třída prvků p a q

class(*p) = class(p) = class(q)

//Pro všechny instance t z původní trénovací množiny TS

for all t from TS {

//nastaví dočasné zkušební vzdálenosti wt' a bt'

t.wt' = wt

t.bt' = bt

//pokud má instance t stejnou třídu jako nový vytvořený p*

if (class(t) = class(p*)) {

// a pokud ani p ani q nejsou jeho nejbližším sousedem Nt

if (t.Nt != p and t.Nt != q){

//ověří zda u instance t nedojde ke změně wt

if (vzdalenost(t,p*) < t.wt){

t.wt' = vzdalenost(t, p*)

}

}

// pokud p nebo q jsou nejbližším sousedem k instanci t

else {

// určí novou wt', najde nejbližšího souseda se

//stejnou třídou z množin A a B, vyjma instancí p a q,

//kdy do hledání zahrne i instanci p*

t.wt'=vzdalenost(najdiSouseda(t,A-p+B-q+p*, class(p*)))

}

}

// pokud má instance t jinou třídu než vytvořená instance p*

else {

//a pokud ani p ani q nejsou nejbližším sousedem Nt

if (t.Nt != p and t.Nt != q){

//ověří zda u instance t nedojde ke změně bt

if (vzdalenost(t, p*) < t.bt) {

t.bt' = vzdalenost(t, p*)

}

}

//pokud p nebo q jsou nejbližším sousedem k bodu t

else {

// určí novou bt', najde nejbližšího souseda s rozdílnou

// třídou z množin A a B, vyjma instancí p a q, a zahrň do

// hledání i instanci p*

t.bt' = t.bt' = vzdalenost(t, najdiProtivnika(t, A-p+B-q+p*))

}

// Ověří, zda nám spojená instance neohrozí klasifikaci

}

if (t.wt < t.bt and t.wt' >= t.bt') {

// přesune instanci q z množiny B do množiny A

A = A + q

B = B – q

Pokračuj bodem 7

}

}

// Instance p a q je možné spojit, novou instanci p* přidá do množiny A

// a odstraní prvky p i q

A = A - p + p*

B = B – q


43

// zvýší čítač spojených prvků

MERGE = MERGE + 1


for all t from TS {

// nastaví nové vzdálenosti a nového nebližšího souseda

t.wt = t.wt'

t.bt = t.bt'

t.Nt = najdiSouseda(t,A+B)

}

Pokračuj bodem 7

}

// Pokud dvě nejbližší instance nejsou stejné třídy

else {

// Přesune prvek q z množiny B do množiny A

A = A + q

B = B - q

Pokračuj bodem 7

}


12. return A

6.3.2 Chenův algoritmus

Všechny zmiňované algoritmy pro početní redukci dat neumoţňovaly kontrolu velikosti

výsledné redukované mnoţiny. Velikost výsledné redukované mnoţiny můţe být zajímavá

pro situace, kdy hlavním cílem není pouze redukce výpočetní sloţitosti, ale také vysoká

rychlost klasifikátoru. V roce 1996 představili C. H. Chen a A. Józwik adaptivní kondenzační

algoritmus nazvaný Chenův algoritmus, který umoţňuje nastavení poţadované velikosti

výsledné redukované mnoţiny. [20]

V tomto algoritmu Chen představuje myšlenku průměru trénovací mnoţiny. Průměr

trénovací mnoţiny TS je vzdálenost mezi dvěma nejvzdálenějšími instancemi. Základní

strategií je postupné rozdělování původní TS mnoţiny do podmnoţin, kdy se k rozdělení

vybírá podmnoţina s největším průměrem. Tento postup se opakuje, dokud počet podmnoţin

není roven poţadované velikosti redukované mnoţiny. Poté je kaţdá výsledná podmnoţina

nahrazena novým prototypem. Nový reprezentant je umístěn jako centroid všech instancí v

dané podmnoţině a je klasifikován třídou, která je v podmnoţině nejvíce zastoupena.


Rozdělování podmnoţiny s největším průměrem je postaveno na myšlence, ţe

podmnoţina s největším průměrem pravděpodobně obsahuje nejvíce instancí a tudíţ můţeme

dosáhnout největší redukce.


44

C[1] C[2]

C[2]

C[2]

C[2]

C[2]

C[1]

C[1]

C[1]

C[1]

C[3]

C[3]

C[3]

C[3]

C[5]

C[5]

C[4]

C[4]

C[4]C[6]

1.

2.

3.

4.

5.

Chen

RSP1

RSP3

a)

b)

c)

d)

e)

Obrázek 21: Chenův algoritmus, RSP1 algoritmus a RSP3 algoritmus

Na obrázku viz Obrázek 21 je znázorněn základní princip Chenova algoritmu. Ukázka

je zaloţena na trénovací mnoţině s devíti instancemi rozdělenými do dvou tříd v

jednorozměrném prostoru. Budeme poţadovat redukovanou mnoţinu o velikosti 6 instancí.

V prvním kroku je potřeba vyhledat dvě nejvzdálenější instance (na obrázku jsou

zvýrazněny). Dále je potřeba mnoţinu rozdělit dle pravidel:

D1 = { p ∈Є D, d(p, p1) ≤ d(p, p2) }

D2 = { p ∈ D, d(p, p2) < d(p, p1) }


45

Hranice rozdělení je naznačena čárkovanou čarou označenou číslem 1. V dalším kroku se v

obou získaných podmnoţinách opět určuje průměr a podmnoţina s větším průměrem se dále

rozděluje. Hranice rozdělení je opět vyznačena čárkovanou čarou, ale označena 2. Takto se

postupuje dále, dokud počet podmnoţin není roven 6. V posledním kroku je ze všech instancí

jednotlivých podmnoţin vypočítán centroid klasifikovaný nejpočetněji zastoupenou třídou v

dané podmnoţině.

Hlavní výhoda Chenova algoritmu oproti ostatním algoritmům je zřejmá. Díky

moţnému nastavení velikosti redukované mnoţiny umoţňuje získat adekvátní vyváţení mezi

výpočetními potřebami a poţadovanou klasifikací.

Problémem Chenova algoritmu je citlivost na nevyváţená data, kde instance jedné třídy

jsou méně zastoupeny v TS mnoţině. V této situaci mohou být instance minoritní třídy při

redukci odstraněny díky způsobu určování nových reprezentantů.

Pseudokód 9: Chenův algoritmus



R – výsledná redukovaná množina

D, D1, D2 – pomocné množiny instancí

I1, I2, I - pomocné množiny množin

nd – požadovaný počet instancí z původní trénovací množiny

nc – aktuální počet podmnožin trénovací množiny

C[] – pole podmnožin trénovací množiny

i – číslo podmnožiny, kterou rozdělujeme

p1,p2 – nejvzdálenější body v dané množině

instance - pomocná instance

Popisy použitých funkcí


nejvzdalenejsiBody(množina X) – v množině X nalezne 2 nejvzdálenější

instance p1, p2

viceTrid(množina X) – pokud nejsou v množině X instance pouze jediné třídy

vrací TRUE, jinak vrací FALSE

nejvetsiPrumer(množina[] X, množina I) – ze všech množin v poli množin X,

které jsou také v množině množin I vybere množinu, která má největší

vzdálenost mezi 2 nejvzdálenějšími instancemi a vrací index na tuto množinu

v poli množin X

centroid(množina X) – vytvoří novou instanci, kde pro všechny instance

množiny X a všechny jejich atributy vypočítá průměrnou hodnotu. Třída

instance je rovna třídě, která je v množině X nejvíce zastoupená a v

případě rovnosti se rozhodne náhodně.


x, y ( (xi − yi)2)n

i=1

//FIX ME vzdalenost() i se vzorcem

// Prvotní inicializace

// Načte požadovanou velikost výsledné redukované množiny

1. nd = vstup()

// Nastaví aktuální počet podmnožin trénovací množiny, které zastupují

// výsledné instance

nc = 1

// Nastaví číslo podmnožiny, kterou budeme rozdělovat

i = 1

// Nastaví pomocné množiny

D1 = Ø


46

D2 = Ø

I1 = Ø

I2 = Ø

// Zkopíruje kompletní trénovací množinu do pole podmnožin trénovací

// množiny

2. C[i] = TS

// Zkopíruje kompletní trénovací množinu do pomocné množiny D

D = TS

// Nalezne dvě nejvzdálenější instance p1 a p2 v množině D

3. [p1,p2] = nejvzdalenejsiBody(D)

// Rozdělí množinu D na dvě podmnožiny D1 a D2 dle pravidel:

// D1 = {pЄD, d(p,p1) <= d(p,p2)}

// D2 = {pЄD, d(p,p2) < d(p,p1)}

// kdy v podmnožině D1 jsou všechny instance p z množiny D, které jsou

// blíže k instanci p1 než k instanci p2 nebo mají stejnou

// vzdálenost k instanci p1 jako mají k instanci p2. V podmnožině D2 jsou

// všechny ostatní instance

4. for all p from D {

if (vzdalenost(p, p1) <= vzdalenost(p,p2)) {

D1 = D1 + p

}

else {

D2 = D2 + p

}

}

// Inkrementuje celkový počet podmnožin trénovací množiny

5. nc = nc + 1

// Rozdělení podmnožiny D

// Přepíše původní podmnožinu D podmnožinou D1

6. C[i] = D1

// Vytvoří v poli podmnožin novou podmnožinu a uloží do ní podmnožinu D2

C[nc] = D2

// Do množiny I1 uloží všechny podmnožiny C z pole C[x]), které obsahují

// instance alespoň dvou různých tříd

7. for all C from C[] {

if (vicetrid(C) == TRUE) {

I1 = I1 + C

}

// Množina I2 obsahuje všechny ostatní podmnožiny z pole C[x]

else {

I2 = I2 + C

}

// Pokud množina I1 podmnožin C není prázdná pokračuje v dalších krocích

// právě s ní

8. if (I1 != Ø) {

I = I1

}

// Pokud množina I1 podmnožin C je prázdná pokračuje v dalších krocích s

//množinou I2 podmnožin C

else {

I = I2

}

// Najdi takové j, že platí vzdalenost(Q1(j), Q2(j)) = maxvzdalenost(Q1(i),

// Q2(i)) pro i Є I

// Jedná se o nalezení indexu j podmnožiny C[j], která má největší průměr

// ze všech množin, které se nachází v množině množin I

9. j = nejvetsiPrumer(C[],I)

// Do množiny D se kterou bude případně dále pokračovat, uloží nalezenou

// podmnožinu s největším průměrem

D = C[j]

// V množině D nalezne dvě nejvzdálenější instance pro případné další

//zpracovávání

[p1,p2] = nejvzdalenejsiBody(D)


47

// Pro možnost přepsání nalezené podmnožiny C(j) v případně dalších

// krocích

i = j

// Vynuluje pomocné množiny

I1 = Ø

I2 = Ø

D1 = Ø

D2 = Ø

// Proces opakuje, dokud není počet získaných podmnožin roven zadanému

// počtu instancí nd

10. if (nc < nd) {

Pokračuj bodem 4

}

else {

Pokračuj bodem 11

}

//Pro všechny získané podmnmožiny C z pole podmnožin C[x]


//vypočítá novou instanci - centroid ze všech instancí v podmnožině C

instance = centroid(C)

//a tuto novou instanci přidá do výsledné redukované množiny R

R = R + instance

}

12. // Vrací výslednou redukovanou množinu R

return R

6.3.3 Redukce dělením prostoru

V roce 2004 představil J. S. Sánchez rodinu algoritmů nazvaných Redukce dělením

prostoru (Reduction by Space Partition), které vychází z Chenova algoritmu. Pouţívají také

průměr trénovací mnoţiny TS a odstraňují hlavní nedostatek Chenova algoritmu, citlivost na

nevyváţená data. [21]

RSP1 je prvním algoritmem představený Sánchezem a soustředí se hlavně na vylepšení

citlivosti na nevyváţená data Chenova algoritmu. Počáteční kroky jsou stejné jako u Chenova

algoritmu, mění aţ poslední krok nahrazování získaných podmnoţin novým prototypem.

Rozděluje tedy původní trénovací mnoţinu na podmnoţiny, dokud není počet podmnoţin

roven poţadovanému počtu instancí v redukované mnoţině. Rozděluje vţdy podmnoţinu,

která má největší průměr. Ve finálním kroku ovšem nenahrazuje celou podmnoţinu jedním

novým prototypem, ale tolika prototypy, kolik je v podmnoţině zastoupeno tříd. Pro všechny

instance jedné třídy v podmnoţině vypočítá centroid zvlášť. Tímto způsobem získá c nových

prototypů pro kaţdou podmnoţinu, kde c je počet různých tříd v podmnoţině. Na obrázku viz

Obrázek 21 je názorně zobrazen rozdíl v posledním kroku Chenova algoritmu a RSP1

algoritmu. Podrobněji viz Pseudokód 10.

Je zřejmé, ţe u této redukční techniky není moţné přesně určit velikost redukované

mnoţiny. Na druhé straně jsme schopni určit interval, ve kterém se můţe velikost redukované

mnoţiny S pohybovat:

b ≤ S ≤ b*m


48

Kde b je zadaný počet potřebné velikosti redukované mnoţiny a m je počet tříd v TS

mnoţině.

Je důleţité poznamenat, ţe vytvořením centroidu pro kaţdou třídu zvlášť není

rozhodovací hranice zachovávána tak dobře jako u Chenova algoritmu. Na druhé straně tato

heuristika zaručuje, ţe ve výsledné redukované mnoţině budou zastoupeny všechny třídy.

Druhý algoritmus představený Sánchezem je algoritmus RSP2. Zatímco předchozí

algoritmus rozděloval podmnoţinu s největším průměrem, kde předpokládal, ţe dosáhne

největší redukce, RSP2 algoritmus rozděluje podmnoţinu s největším stupněm překrývání.

Vychází z teorie, ţe instance stejné třídy by měly být co nejblíţe a instance ostatních tříd by

měly být od nich co nejvíce vzdáleny. Proto je vhodnější rozdělit podmnoţinu s nejvyšším

stupněm překrývání kvůli instancím rozdílných tříd.

Stupeň překrývání je poměr průměrné vzdálenosti mezi instancemi patřících do různých

tříd a průměrem vzdálenosti mezi instancemi, které jsou stejné třídy.

Stejně jako algoritmus RSP1 pro všechny instance jedné třídy v podmnoţině vypočítá

centroid zvlášť.

Třetím algoritmem je RSP3. Algoritmus RSP3 rozděluje TS mnoţinu aţ do doby,

dokud nejsou všechny podmnoţiny homogenní. Pak opět pro jednotlivé podmnoţiny vypočítá

ze všech instancí centroid. homogenní podmnoţina, je podmnoţina, kde jsou všechny

instance ohodnoceny stejnou třídou. Snaţí se tak získat podmnoţiny, které odpovídají

shlukům instancí stejné třídy. V tomto algoritmu tedy není moţné určovat finální velikost

redukované mnoţiny. Na obrázku viz Obrázek 21 můţeme vidět rozdělení TS mnoţiny na

homogenní podmnoţiny. Podrobněji viz Pseudokód 11.

RSP3 můţe vyuţívat jak rozdělovací kritérium dle největšího průměru, tak rozdělení

podle nejvyššího stupně překrývání. Způsob rozdělování není důleţitý, neboť všechny

heterogenní podmnoţiny jsou ve finále rozděleny.

Počet nových prototypů generovaných touto metodou bude zřejmě podstatně vyšší, neţ

u předchozích dvou metod. Obzvláště, pokud jsou v původní TS mnoţině rušivé instance.

Proto je dobré nejprve na vstupní TS mnoţinu aplikovat některý z editačních algoritmů.

Pseudokód 10: Algoritmus RSP1





I1, I2, I - pomocné množiny množin




i – číslo podmnožiny, kterou rozdělujeme

p1,p2 – nejvzdálenější instance v dané množině





49

nejvzdalenejsiInst(množina X) – v množině X nalezne 2 nejvzdálenější

instance p1, p2

viceTrid(množina X) – pokud nejsou v množině X instance pouze jediné třídy





v poli množin X


x, y ( (xi − yi)2)n

i=1

centroidProVsechnyTridy(C) - vrací pole nově vytvořených instancí.

V podmnožině C pro všechny třídy v ní zastoupené vypočítá průměrnou hodnotu

pro všechy prvky této třídy.


// Načte požadovanou velikost výsledné redukované množiny

1. nd = vstup()


výsledné instance

nc = 1

// Nastaví číslo podmnožiny, kterou budeme rozdělovat

i = 1


D1 = Ø

D2 = Ø

I1 = Ø

I2 = Ø


množiny

2. C[i] = TS


D = TS

// Nalezne dvě nejvzdálenější instance p1 a p2 v množině D

3. [p1,p2] = nejvzdalenejsiInst(D)


// D1 = {pЄD, d(p,p1) <= d(p,p2)}

// D2 = {pЄD, d(p,p2) < d(p,p1)}


blíže k instanci p1 než k instanci p2 nebo mají stejnou

// vzdálenost k instanci p1 jako mají k instanci p2. V podmnožině D2 jsou

všechny ostatní instance

4. for all p from D {

if (vzdalenost(p, p1) <= vzdalenost(p, p2)) {

D1 = D1 + p

}

else {

D2 = D2 + p

}

}


5. nc = nc + 1



6. C[i] = D1

// Vytvoří v poli podmnožin novou podmnožinu a uloží do ní podmnožinu D2

C[nc] = D2


instance alespoň dvou různých tříd


if (viceTrid(C) == TRUE) {

I1 = I1 + C

}


50

// Množina I2 obsahuje všechny ostatní podmnožiny z pole C[x]

else {

I2 = I2 + C

}

// Pokud množina I1 podmnožin C není prázdná pokračuje v dalších krocích

právě s ní

8. if (I1 != Ø) {

I = I1

}

// Pokud množina I1 podmnožin C je prázdná pokračuje v dalších krocích

s množinou I2 podmnožin C

else {

I = I2

}

// Najdi takové j, že platí vzdalenost(Q1(j), Q2(j)) = maxvzdalenost(Q1(i),

Q2(i)) pro i Є I

// Jedná se o nalezení indexu j podmnožiny C[j], která má největší průměr

ze všech množin, které se nachází v množině množin I

9. j = nejvetsiPrumer(C[],I)

// Do množiny D se kterou bude případně dále pokračovat, uloží nalezenou

podmnožinu s největším průměrem

D = C[j]


zpracovávání

[p1,p2]= nejvzdalenejsiInst(D)

// Pro možnost přepsání nalezené podmnožiny C(j) v případně dalších

krocích

i = j


I1 = Ø

I2 = Ø

D1 = Ø

D2 = Ø

//Proces opakuje, dokud není počet získaných podmnožin roven zadanému počtu

instancí nd

10. if (nc < nd) {

Pokračuj bodem 4

}

else {

Pokračuj bodem 11

}

// Pro všechny získané podmnožiny C z pole podmnožin C[x]


// uloží do pole instancí centroidy vypočítané pro každou třídu

// zastoupenou v podmnožině C zvlášť

instance[] = centroidProVsechnyTridy(C)

// přidáme nově nalezené instance do redukované množiny R

R = R + instance[]

}

12. // Vrací výslednou redukovanou množinu R

return R

Pseudokód 11: Algoritmus RSP3

Algoritmus RSP3





51


I1 - pomocná množina podmnožin




p1,p2 – nejvzdálenější body v dané množině


j - číslo podmnožiny, kterou rozdělujeme



nejvzdalenejsiInst (množina X) – v množině X nalezne 2 nejvzdálenější

instance p1, p2

vicetrid(množina X) – pokud nejsou v množině X instance pouze jediné třídy





v poli množin X

centroid(množina X) – vytvoří novou instanci, kde pro všechny instance

množiny X a všechny jejich atributy vypočítá průměrnou hodnotu. Třída

instance je rovna třídě, která je v množině X nejvíce zastoupená a v

případě rovnosti se rozhodne náhodně.

centroidProVsechnyTridy(C) - vrací pole nově vytvořených instancí. V

podmnožině C pro všechny třídy v ní zastoupené vypočítá průměrnou hodnotu

pro všechny prvky této třídy.


x, y ( (xi − yi)2)n

i=1



výsledné instance

1. nc = 1


D1 = Ø

D2 = Ø

// Číslo

j = 1


množiny

2. C[j] = TS


D = TS


instance alespoň dvou různých tříd



I1 = I1 + C

}

}

// Dokud množina I1 není prázdná

4. while (I1 != Ø) {

// Najdi takové j, že platí:

// vzdálenost(Q1(j), Q2(j)) = maxvzdalenost(Q1(i), Q2(i)) pro i Є I1

// Jedná se o nalezení indexu j podmnožiny C[j], která má největší

// průměr ze všech množin, které se nachází v množině množin I1

j = nejvetsiPrumer(C[],I1)

// Do množiny D se kterou bude případně dále pokračovat, uloží

// nalezenou podmnožinu s největším průměrem

D = C[j]


// zpracovávání

[p1,p2] = nejvzdalenejsiInst(D)


52


// D1 = {pЄD, d(p,p1) <= d(p,p2)}

// D2 = {pЄD, d(p,p2) < d(p,p1)}


// blíže k instanci p1 než k instanci p2 nebo mají stejnou

// vzdálenost k instanci p1 jako mají k instanci p2. V podmnožině D2

//jsou všechny ostatní instance

for all p from D {

if (vzdalenost(p,p1) <= vzdalenost(p,p2)) {

D1 = D1 + p

}

else {

D2 = D2 + p

}

}


nc = nc + 1



C[j] = D1

// Vytvoří v poli podmnožin novou podmnožinu

// a uloží do ní podmnožinu D2

C[nc] = D2

// Do množiny I1 uloží všechny podmnožiny C z pole C[x]), které

// obsahují instance alespoň dvou různých tříd

I1 = Ø

for all C from C[] {


I1 = I1 + C

}

}


D1 = Ø

D2 = Ø

}

// Pro všechny získané podmnmožiny C z pole podmnožin C[x]


// uloží do pole instancí centroidy vypočítané pro každou třídu

// zastoupenou v podmnožině C zvlášť

instance[] = centroidProVsechnyTridy(C)

R = R + instance[]

}


6. return R

6.4 Vlastní experimentální redukce

6.4.1 MergeAllInstances

Při zkoumání jednotlivých algoritmů a počátečním testování přesnosti klasifikace

1 – NN klasifikátoru a neuronové sítě GAME jsem se rozhodla vytvořit vlastní

experimentální algoritmus. Tento algoritmus jsem pojmenovala MergeAllInstances.

Algoritmus je postaven na všech zkoumaných neadaptivních algoritmech, tj.: CNN, RNN,

IB3 a DROP3.


53

Algoritmus vychází z faktu, ţe zmiňované algoritmy rapidně sniţují velikost původní

trénovací mnoţiny, coţ se bohuţel odráţí na přesnosti obou klasifikátorů. Navíc se kaţdý z

algoritmů zaměřuje na redukci instancí leţících poblíţ rozhodovací hranice, či vnitřních

instancí specifickým způsobem. Proto jsem se rozhodla všechny instance z redukovaných

mnoţin získaných jednotlivými algoritmy spojit do jedné výsledné redukované mnoţiny.


Pečlivého čtenáře zřejmě napadne myšlenka, proč společně s algoritmem CNN

pouţívám i algoritmus RNN. Kdyţ RNN algoritmus získává podmnoţinu mnoţiny instancí

CNN algoritmu. RNN algoritmus jsem přidala do svého algoritmu, protoţe díky náhodnému

výběru instance v počáteční fázi CNN algoritmu můţe RNN získat jinou výslednou

redukovanou mnoţinu instancí.

Pseudokód 12: Algoritmus MergeAllInstances

Algoritmus MergeAllInstances


TS - původní trénovací množina

množinaR - výsledná redukovaná množina instancí

seznamR - pomocný seznam redukovaných instancí

k1, k2, k3, mh, ml - pomocné proměnné, které slouží jako vstupní parametry

k jednotlivým redukčním algoritmům



hartReduce(int k, množina X) - vrací seznam redukovaných instancí množiny

TS pomocí CNN redukčního algoritmu

rnnReduce(int k, množina X) - vrací seznam redukovaných instancí množiny TS

pomocí RNN redukčního algoritmu

drop3Reduce(int k, množina X) - vrací seznam redukovaných instancí množiny

TS pomocí DROP3 redukčního algoritmu

ib3Reduce(double mh, double ml, double randomPart, množina X) - vrací

seznam redukovaných instancí množiny TS pomocí IB3 redukčního algoritmu


1. množinaR = Ø

k1 = vstup()

k2 = vstup()

k3 = vstup()

mh = vstup()

ml = vstup()

randomPart()

// Trénovací množinu TS zredukuje použitím CNN algorimu

2. seznamR = hartReduce(k1, TS)

// Získaný seznam redukovaných instancí přidá

// do množiny všech redukovaných instancí

3. přidej(množinaR, seznamR)

// Trénovací množinu TS zredukuje použitím RNN algorimu

4. seznamR = rnnReduce(k2, TS)

// Získaný seznam redukovaných instancí x přidá


// Pokud se již instance x v množině nachází nepřidá ji


// Trénovací množinu TS zredukuje použitím DROP3 algoritmu

6. seznamR = drop3Reduce(k3, TS)


Implementace

54




// Trénovací množinu TS zredukuje použitím IB3 algoritmu

8. seznamR = ib3Reduce(mh, ml, randomPart, TS)





// Vrací získanou redukovanou množinu

10. return množinaR

7. Implementace

V rámci této práce byl implementován klasifikátor k – NN. Dále byly do modulu pro

předzpracování dat projektu FAKE GAME implementovány 2 editační metody (ENN,

All k – NN) a kondenzační metody (CNN, ENN, DROP3, IB3, Prototypy, Chen, RSP1,

RSP3).

7.1 Klasifikátor k - NN

Protoţe většina autorů literatury početní redukce dat testuje kvalitu kondenzačních

algoritmů prostřednictvím klasifikátoru 1 – NN, rozhodla jsem se, ţe tento klasifikátor také

pouţiji. I kdyţ ke klasifikaci pouţívám pouze zjednodušený případ klasifikátoru 1 – NN,

rozhodla jsem se implementovat obecný klasifikátor k – NN, neboť jej vyuţívají také některé

implementované algoritmy (ENN, All k – NN) k vlastní činnosti. Speciální případ

klasifikátoru 1 – NN jsem optimalizovala, aby proces klasifikace neobsahoval nadbytečné

kroky.

V případě, ţe se jedná o speciální případ, kdy k = 1, je proces řazení instancí dle

euklidovské vzdálenosti vynechán. Nejbliţší soused ke všem instancím je hledán jiţ v kroku

výpočtu vzdálenosti vůči ostatním instancím.

Zdrojový kód implementovaného algoritmu k – NN je uloţen na přiloţeném CD viz

příloha E Obsah přiloţeného CD.

7.2 Integrace algoritmů do systému FAKE GAME

Součástí prostředí FAKE GAME je modul Preprocessing dialog viz Obrázek 22.

Pomocí tohoto modulu můţe uţivatel importovat i exportovat data a aplikovat na ně metody

pro předzpracování dat. Dialog pro předzpracování dat obsahuje dosud implementované

metody, jako je například podpora pro normalizaci dat, diskretizaci a clusterování dat. Dále je

součástí např. Random Data Reducer (náhodné odebrání některých instancí) či Noise Adder

(náhodný generátor instancí – datového šumu) a některé další.

Implementace

55

Obrázek 22: FAKE GAME Preprocessing dialog

Načtená data jsou uloţena v datovém úloţišti, nad kterým jednotlivé algoritmy pracují.

Uţivatel pak můţe vybrat, který algoritmus spustí a nad jakou částí dat. Jednotlivé algoritmy

lze spouštět opakovaně a libovolně je kombinovat.

Algoritmy lze před vlastním spuštěním konfigurovat a je tak moţné upravit chování

algoritmu viz Obrázek 23. Výsledná zpracovaná a upravená data lze exportovat do různých

formátů (CSV, XLS, Weka) pro pouţití v jiných aplikacích.

Obrázek 23: Konfigurace IB3 algoritmu

Implementace

56

Kaţdá nová metoda musí implementovat Java rozhraní Preprocessor, které obsahuje

deklarace základních metod jako je init(PreprocessingStorage storage) – inicializace

reference přístupu k datovému úloţišti, run() – vlastní běh algoritmu. Základní třída

BasePreprocessor, která zmíněné rozhraní implementuje, viz Obrázek 24, obsahuje název a

stručný popis algoritmu zobrazovaný v dialogu. Taktéţ zajišťuje přístup k nastavené

konfiguraci pomocí instance k některému z potomků třídy BasePreprocessorConfig.

Potomek třídy BasePreprocessorConfig, na obrázku viz Obrázek 24 pro algoritmus

Chang se jedná o třídu ChangReduceConfig, deklaruje jména a datové typy (integer, double)

konfiguračních parametrů, včetně jejich moţných rozsahů.

Obrázek 24: Class diagram modulu algoritmus Prototypy

Pro účely implementace algoritmů popsaných v této práci jsem vytvořila potomka třídy

BasePreprocessor, kterého jsem nazvala CondensingReduceProprocessor. Tento potomek

slouţí k sjednocení přístupu k datovému úloţišti prostředí FAKE GAME. Před voláním

redukčního algoritmu převede všechny instance z datového úloţiště na jednu kolekci

NDInstance, jenţ je hlavním vstupním parametrem kaţdého z implementovaných algoritmů.

Po provedení algoritmu vrací upravenou kolekci NDInstance zpět do datového úloţiště.

Konkrétní algoritmus implementuje potomek třídy CondensingReducePreprocessor,

na obrázku viz Obrázek 24 například ChangReduce, který v metodě run obsahuje volání

vlastní funkce redukčního algoritmu. Z důvodu větší přehlednosti zdrojového kódu jsem

funkční kód kaţdého algoritmu (postavený na pseudokódech v kapitole 6) umístila do

speciální třídy pojmenované dle názvu algoritmu a umístila jej do vlastní Java package (např.

Chang. ChangAlgorithm).

Implementace

57

Třída NDInstance představuje právě jednu instanci dat. Obsahuje vektor dat a

klasifikační třídu, do které data patří. Třída implementuje algoritmy často vyuţívanou metodu

výpočtu Euklidovské vzdálenosti vůči jiné NDInstance a jednoduchou metodu pro porovnání

dvou tříd NDInstance. Některé z algoritmů (např. Chang, IB3, DROP3) rozšiřují NDInstance

vlastními potomky (ChangInstance, IBInstance, DROP3Instance) o další metody pro práci

s instancemi. Jedná se např. o nalezení nejbliţšího oponenta v kolekci jiných instancí nebo

operaci sjednocení instancí, kdy se vytvoří aritmetický průměr všech atributů a vytvoří nová

instance a mnohé další.

Aby bylo moţné naimplementovaný algoritmus zobrazit ve stromu nabízených metod

Preprocessing dialogu, bylo nutné v konfiguračním souboru units.cfg přidat názvy potomků

rozhraní Preprocesor a tím uţivateli aplikace zaregistrovat novou metodu.

Všechny nově vytvořené algoritmy jsou v Preprocessing dialogu umístěny v podstromu

Data reduction. Spuštění algoritmu nad daty se provede jejich vybráním a stisknutím tlačítka

Run.

Zdrojové kódy implementovaných algoritmů jsou k dispozici k nahlédnutí na

přiloţeném CD viz příloha E Obsah přiloţeného CD či v aktuální verzi projektu FAKE

GAME viz [27].

Testování implementovaných algoritmů

58

Část IV – Testování

Tato část je věnována testování všech implementovaných algoritmů a zhodnocení jejich

klasifikační, redukční i statistické kvality.

8. Testování implementovaných algoritmů

Kvalitu implementovaných redukčních algoritmů testuji na uměle vytvořených datech

(Zuby, Dvě E, Whirpool, Šachovnice) a na vybraných reálných problémech (Ecoli,

Mandarinky, Glass, Ionosphere, EKG). Na uměle vytvořených datech Dvě E popisuji změny

rozhodovací hranice trénovací mnoţiny dat po aplikaci jednotlivých kondenzačních

algoritmů. Nejprve testuji vliv implementovaných editačních algoritmů na funkčnost

algoritmů kondenzačních na uměle vytvořených datech. Jednotlivé algoritmy porovnávám

podle dosaţené klasifikační přesnosti, redukčního stupně a času potřebného k vytvoření

modelu. Hodnotím vlastní experimentální algoritmus. V poslední řadě testuji změny

statistických vlastnosti dat po aplikaci redukčních algoritmů. K testování pouţívám

klasifikátoru 1 – NN a neuronové sítě GAME.

8.1 Popis testovaných dat

8.1.1 Umělá data

K vytvoření umělých dat jsem vyuţila nástroj vytvořený v Matlabu, který jsem získala

od svého vedoucího diplomové práce. Pomocí něj jsem vytvořila 5 různých umělých dat.

Instance v těchto datech jsou dvojrozměrné a jsou klasifikovány jednou ze dvou tříd. Pro

rozlišení je budu označovat A (instance fialové) a B (instance zelené).

Zuby – tyto data jsem vytvořila, protoţe je pouţívá řada autorů kondenzačních algoritmů. Je

tedy moţné porovnat mé výsledky s výsledky jiných autorů. Data obsahují celkem 450

instancí a kaţdá třída je v ní zastoupena se stejnou pravděpodobností, tudíţ 225 instancí třídy

A a 225 instancí třídy B. Data jsou zobrazena na obrázku viz

Obrázek 25.


59

Obrázek 25: Uměle vytvořená data Zuby

Dvě E – tato data jsou obměnou předchozích dat Zuby ovšem se sloţitější rozhodovací

hranicí. Pouţila jsem je právě z důvodu sloţitější rozhodovací hranice a z toho vyplývajících

větších nároků na klasifikační algoritmus a správně utvořenou trénovací mnoţinu. Data jsou

zobrazena na obrázku viz Obrázek 26.

Obrázek 26: Uměle vytvořená data Dvě E

Whirpool – data jsou velmi zjednodušenou verzí známé databáze spirála. Databáze spirála je

pouţívána jako kvalitní testovací úloha. Proto jsem se rozhodla tuto úlohu zjednodušit a

vyzkoušet na ní zdatnost algoritmů pro početní redukci dat. Data mají celkem 244 instancí a

kaţdá třída je v nich zastoupená se stejnou pravděpodobností, tudíţ 122 instancí třídy A a 122

instancí třídy B. Databáze je zobrazena na obrázku viz Obrázek 27.


60

Obrázek 27: Uměle vytvořená data Whirpool

Šachovnice – data Šachovnice jsem vytvořila, abych ověřila schopnost algoritmů redukovat

data s velmi sloţitou rozhodovací hranicí. Databáze má celkem 856 instancí a kaţdá třída je

v ní zastoupena se stejnou pravděpodobností, tudíţ 428 instancí třídy A a 428 instancí třídy B.

Data jsou zobrazena na obrázku viz Obrázek 28.

Obrázek 28: Uměle vytvořená data Šachovnice

8.1.2 Reálné databáze

Ecoli – dataset reprezentuje soubor proteinů. Jednotlivé molekuly jsou popsány celkem

8 atributy. Atributy popisují vlastnosti proteinu. Cílem je určit, ze které části buňky proteiny

pocházejí (např. buněčná stěna, cytoplasma, vnitřní membrány,...).

Ionosphere – data pochází z radarové stanice Goose Bay. Stanice měří radarové

odrazy z atmosféry pomocí 32 sloţek. Cílem měření je zachytit volné elektrony v ionosféře.

Výsledkem klasifikace jsou dvě třídy odrazů. První třída odrazů (pojmenované Good) jsou

odrazy od volných elektronů. Druhá třída (pojmenovaná "Bad") se neodrazila a proletěla do

vesmíru.


61

Glass – data popisující různé typy skla. 7 vstupními atributů obsahuje zastoupení prvků

ve skle (Magnesium, Křemík, Barium,...). Cílem je určit jakého původu je sklo (Okenní sklo,

autosklo, nádoby,...)

EKG – data reprezentují EKG záznamy srdečních stahů. EKG záznam je rozdělen na

jednotlivé stahy a stahy jsou popsány 6 parametry pouţívanými v medicíně (např. vzdálenosti

a amplitudy jednotlivých vln). Cílem je klasifikace stahů na normální (zdravé) a ventrikulární

(indikující onemocnění srdce).

Mandarinky – tato data pochází z Hort Research z Nového Zélandu a popisují

mnoţství vody zkonzumované mandarinkovým stromem. 9 vstupních proměnných popisuje

parametry prostředí, jako například teplota, vlhkost, mnoţství slunečního svitu. Výstupem je,

jiţ zmíněné, mnoţství vody zkonzumované mandarinkovým stromem. Protoţe se původně

jedná o regresní problém, výstupní hodnoty jsem diskretizovala do 5 tříd.

Data Ecoli, Ionosphere a Glass jsem získala z veřejné internetové databáze UCI

Machine Learning Repository. Data EKG a Mandarinky jsem získala od vedoucího a

oponenta mé práce.

8.2 Metodika experimentů

V této části popíši metodiku, kterou budu pouţívat při získávání výsledků. Nejprve

originální data rozdělím na trénovací a testovací část. Do trénovací mnoţiny náhodně zvolím

75% instancí z originálních dat a zbylých 25% pouţiji pro testování. Trénovací mnoţinu budu

upravovat implementovanými redukčními algoritmy a poté ji budu pouţívat k tvorbě

jednotlivých modelů. Naopak testovací mnoţinu jiţ nebudu upravovat a budu pouţívat

pokaţdé stejnou, abych získala srovnatelné výsledky. Všechny výsledky, z k – NN

klasifikátoru i ze sítě GAME, tedy budou získány na testovacích datech.

Při tvorbě neuronové sítě GAME hraje značnou roli náhoda. Proto jsem se rozhodla,

postavit 20 modelů pro kaţdou třídu a takto zajistit, konzistenci výsledků sítě GAME.

V dalších částech měřím čas potřebný k vytvoření sítě. Tento čas se měří jen z doby

tvorby sítě, čili neměřím dobu strávenou nahráváním dat ani čas potřebný k vyhodnocení

testovací mnoţiny. Měřím čas spotřebovaný procesem, neměl by tudíţ být ovlivněn během

jiných procesů. Protoţe tvorba sítě GAME netrvá vţdy stejně, rozhodla jsem se uvádět

průměrný čas potřebný k tvorbě jednoho modelu. Časy byly měřeny na jednom počítači

s procesorem Core Duo na 2,13 GHz.


62

Pro výpočet klasifikační úspěšnosti neuronové sítě GAME budu pouţívat standardní

postup implementovaný v této síti. Při vyhodnocení instance se vypočítají výstupní hodnoty

všech vytvořených modelů. Model s největší výstupní hodnotou je zvolen vítězem. Instance je

zařazena do třídy, kterou reprezentuje vítězný model. Klasifikační úspěšnost na testovací

mnoţině pak získám oklasifikováním všech instancí v této mnoţině.

8.3 Redukce umělých dat

Pro předvedení funkčnosti jednotlivých algoritmů na uměle vytvořených datech jsem

zvolila data Zuby viz kapitola 8.1.1. Obdobná data pouţívá většina autorů [14] [19]. K

vizualizaci změny rozhodovací hranice na datech Zuby, jsem upravila applet [26], který

k vykreslení rozhodovací hranice mezi instancemi dvou tříd pouţívá metody Gabrielův graf.

Funkčnost redukčních algoritmů na ostatních uvedených umělých datech, jsou zobrazeny

v příloze B Výsledky redukce umělých dat

Testovací a trénovací data jsem vyrobila rozdělením dat prezentovaných v předchozí

kapitole. Do trénovací mnoţiny jsem náhodně vybrala 75% dat z původních dat. Zbylých

25% dat jsem pouţila pro testovací mnoţinu. Všechny výsledky prezentované v dalších

částech mé práce jsou získány z testovací mnoţiny.

8.3.1 Neadaptivní kondenzační algoritmy

CNN algoritmus

CNN algoritmus se zaměřuje na ukládání instancí leţících blízko rozhodovací hranice.

Instance, které jsou příliš vzdálené od rozhodovací hranice, neukládá. Jinými slovy, zahazuje

instance, které jsou správně klasifikovány svými sousedy. To je dobře vidět na obrázku viz

Obrázek 29. Instance kolem rozhodovací hranice jsou ponechány a dobře hranici vyznačují,

zatím co téměř všechny ostatní instance jsou smazány.

Algoritmus CNN má jeden parametr a to počet nejbliţších sousedů, kteří se pouţijí při

zjišťování, zda instance bude správně klasifikována. Tento parametr jsem nastavila na 1.


63

Obrázek 29: Algoritmus CNN na uměle vytvořených datech Zuby

RNN Algoritmus

Odstraňuje problém redundantních instancí CNN algoritmu, kdy instance, které jednou

přidáme, jiţ není moţné odebrat. Podmnoţinu získanou CNN algoritmem ještě jednou

redukuje, ale tak aby redukovaná mnoţina zůstala konzistentní. Zachovává tedy také instance

poblíţ rozhodovací hranice a instance, které jsou od ní hodně vzdálené, neukládá. To je opět

dobře vidět na obrázku viz Obrázek 30. Navíc, jak je také dobře vidět na obrázku viz Obrázek

30, ţe RNN algoritmus na rozdíl od CNN algoritmu, odstranil některé instance u rozhodovací

hranice, vedle nichţ poblíţ leţela sousední instance stejné třídy. Tím je rozhodovací hranice

méně přesná. Na druhé straně RNN algoritmus odstranil všechny odlehlé instance.

RNN algoritmus má opět jeden parametr. A to počet nejbliţších sousedů, kteří budou

pouţiti v první fázi algoritmu. Tento počet je opět nastaven na 1.

Obrázek 30: Algoritmus CNN a RNN na uměle vytvořených datech Zuby

IB3 Algoritmus

Vychází z IB2 algoritmu, který se velmi podobá CNN algoritmu, ale není konzistentní.

Rušivé instance rozpoznává pomocí statistického vzorce, dle nastavených mezí spolehlivosti.

Redukovaná data na obrázku viz Obrázek 31 jsou získána s pouţitím doporučených mezí

spolehlivosti 70% a 90% a nastavením prvotního náhodného výběru dat z mnoţiny na 20%


64

původních instancí. Jak je vidět, instance A třídy jsou zastoupeny více a tyto instance kopírují

původní rozhodovací hranici. Instance třídy B jsou zastoupeny méně a jsou rozloţeny dál od

rozhodovací hranice. Tato nevyváţenost je způsobena nedeterministickým výběrem instancí z

původní trénovací mnoţiny na počátku algoritmu.

Jak jsem jiţ zmínila – tato metoda má 3 parametry. Dva jsou meze spolehlivosti, které

jsem v implementaci nazvala “Majority low” a “Majority high”. Tyto meze jsem nechala

nastavené na 0,7 a 0,9. Poslední parametr je prvotní náhodný výběr, v mé implementaci

nazvaný “Random part”, který jsem nastavila na 0,2.

Obrázek 31: Algoritmus IB3 na umělých datech Zuby

DROP3

DROP3 algoritmus, jako jediný z testovaných algoritmů, implicitně vyuţívá editačního

algoritmu ENN. Díky němu DROP3 redukuje trénovací mnoţinu, ze které jsou odfiltrovány

rušivé instance a instance velmi blízko rozhodovací hranice. DROP3 odstraňuje všechny

instance, jejichţ odebrání neohrozí klasifikaci většiny okolních instancí. Navíc se nejprve

zaměřuje na odstranění instancí, které jsou vzdálenější od rozhodovací hranice, čímţ zvyšuje

šance na ponechání instancím poblíţ rozhodovací hranice.

Všechny tyto vlastnosti jsou ilustrovány na obrázku viz Obrázek 32. Velké mnoţství

instancí poblíţ rozhodovací hranice je ponecháno a naopak všechny instance vzdálenější od

rozhodovací hranice jsou odstraněny. Díky pouţití editovacího ENN algoritmu instance leţící

v těsné blízkosti rozhodovací hranice jsou odstraněny a rozhodovací hranice je tak pěkně

vyhlazená.

DROP3 má opět jeden parametr, počet nejbliţších sousedů kteří se mají pouţít při

rozhodování o zachování instance. Pro tento parametr jsem zvolila hodnotu 3.


65

Obrázek 32: Algoritmus DROP3 na umělých datech Zuby

8.3.2 Adaptivní kondenzační algoritmy

Prototypy

Algoritmus Prototypy se nezaměřuje pouze na zachovávání instancí poblíţ rozhodovací

hranice, ale snaţí se taktéţ zachovat strategicky výhodné instance vnitřní, jak je vidět na

obrázku viz Obrázek 33: Algoritmus Prototypy na umělých datech Zuby. Redukovaná

mnoţina ovšem jiţ není podmnoţinou mnoţiny trénovací, ale je tvořena novými prototypy.

Prototypy vznikají spojením dvojice nejbliţších instancí, které jsou stejné třídy tak, ţe jsou

umístěny ve středu jejich vzdálenosti. Díky tomu jiţ rozhodovací hranice není pevně

vymezená instancemi, jako tomu bylo u předešlých neadaptivních algoritmů.

Algoritmus Prototypy nemá ţádné nastavitelné parametry.

Obrázek 33: Algoritmus Prototypy na umělých datech Zuby

Chen

Chenův algoritmus se snaţí v kaţdém kroku redukovat oblast, kde můţe dosáhnout

největší redukce. Vyuţívá přitom myšlenky, ţe nejvíce instancí je v oblasti, která je největší. I

tento algoritmus také věnuje pozornost zachovávání strategicky výhodných vnitřních instancí.


66

Noví reprezentanti vznikají jako centroidy všech instancí v dané podmnoţině a jsou

klasifikovány třídou, která je v podmnoţině nejvíce zastoupena. Díky tomu je rozhodovací

hranice podstatně změněna viz Obrázek 34.

Všechny zmiňované algoritmy pro početní redukci dat neumoţňovaly kontrolu velikosti

výsledné redukované mnoţiny. Ovšem Chenův algoritmus tuto moţnost nabízí. Proto je při

kaţdém testování potřeba nastavit poţadovanou velikost výsledné redukované mnoţiny. U

jednotlivých dat vyznačuji, jakou velikost jsem zvolila. Velikost jsem zkoušela nastavovat a

vybírala takovou, abych dosáhla vyšší klasifikační přesnosti neţ je u plné trénovací mnoţiny.

Na datech Zuby jsem nastavila velikost redukované mnoţiny na 60.

Obrázek 34: Chenův algoritmus na umělých datech Zuby

RSP1

Algoritmus RSP1 vychází z Chenova algoritmu, kdy vylepšuje jeho nedostatek, citlivost

na nevyváţená data. Tato vlastnost se ale v testovaných datech nevyskytuje. Liší se pouze

v poslední fázi Chenova algoritmu. Nezanechává pouze jednoho nového reprezentanta pro

celou podmnoţinu, ale vytváří centroidy pro instance všech tříd zastoupených v podmnoţině

zvlášť.

Na obrázku viz Obrázek 35 je dobře vidět, ţe díky vytvoření centroidu pro kaţdou třídu

zvlášť je sice zachováno více instancí u rozhodovací hranice, ale rozhodovací hranice je více

nepřesná, neţ u Chenova algoritmu.

RSP1 algoritmus nabízí moţnost zadání přibliţné velikosti výsledné redukované

mnoţiny. U jednotlivých dat vyznačuji, jakou velikost jsem zvolila. Velikost jsem vybírala

stejnou jako u Chenova algoritmu.

Na databázi Zuby jsem tedy opět nastavila velikost redukované mnoţiny na 60.


67

Obrázek 35: Algoritmus RSP1 na umělých datech Zuby

RSP3

Algoritmus RSP3 rozděluje mnoţinu trénovacích dat na oblasti obsahující instance

stejné třídy. Není jiţ tedy moţné nastavovat poţadovanou velikost výsledné redukované

mnoţiny. Stejně jako RSP1 algoritmus v poslední fázi, ze získaných oblastí vypočítá pro

instance všech tříd centroid zvlášť.

Z ilustrace viz Obrázek 36 s redukovanou mnoţinou pouţitím RSP1 algoritmu

(uprostřed) a redukovanou mnoţinou pouţitím RSP3 algoritmu je zřejmé, ţe oba algoritmy

zanechávají nejvíce instancí u rozhodovací hranice. To je způsobeno vytvářením centroidu

pro kaţdou třídu zvlášť. Dále je vidět, ţe algoritmus RSP3 se kvůli poţadavku homogenity

všech oblastí, nedokáţe dobře vyrovnat s instancemi leţícími velmi blízko rozhodovací

hranice. Poblíţ rozhodovací hranice tak zachovává i redundantní instance.

Algoritmus RSP3 nemá ţádné nastavitelné parametry.

Obrázek 36: Algoritmus RSP1 a RSP3 na umělých datech Zuby

I kdyţ se ve své diplomové práci zaměřuji na krok kondenzace v celkovém procesu

početní redukce dat, rozhodla jsem se implementovat 2 editační algoritmy. Editační algoritmy


68

slouţí pro předzpracovávání dat pro algoritmy kondenzační. Odstraňují šumové instance a

instance leţící velmi blízko rozhodovací hranice.

Implementovala jsem algoritmy ENN a All k – NN. Oba tyto algoritmy jsou zaloţeny

na podobném principu, pouţití klasifikátoru k – NN. All k – NN algoritmus vychází

z algoritmu ENN a byl vytvořen k získání kvalitnější editované mnoţiny, neţ poskytuje ENN

algoritmus. I kdyţ All k – NN algoritmus odstraňuje více rušivých instancí neţ ENN

algoritmus, bohuţel sniţuje také klasifikační přesnost. Proto zjišťuji, jak editovaná mnoţina

získaná pouţitím ENN algoritmu a All k – NN algoritmu ovlivňuje jednotlivé kondenzační

algoritmy.

Vliv implementovaných editačních algoritmů na funkčnost kondenzačních algoritmů

testuji klasifikátorem 1 – NN a neuronovou sítí GAME na vytvořených umělých datech (data

Zuby, Dvě E, Šachovnice a Whirpool). Parametr k jsem u obou algoritmů po krátkém

testování a dle doporučení z literatury věnující pozornost editačním algoritmům [11] nastavila

na 3. Do testování vlivu editačních algoritmů na přesnost klasifikace algoritmů

kondenzačních nezahrnuji algoritmus DROP3, protoţe implicitně jiţ pouţívá ENN

algoritmus.

Výsledky 1 – NN klasifikace

U klasifikátoru 1 – NN testuji přesnost klasifikace (v tabulce viz Tabulka 1 sloupce

Acc[%]) a zaznamenala jsem také redukční stupeň velikosti trénovacích dat (v tabulce viz

Tabulka 1 sloupce Size[%]). Testovala jsem vliv editačních algoritmů na klasifikaci úplné –

neredukované trénovací mnoţiny. Kondenzační algoritmy jsem zkoušela na needitovaných

trénovacích datech (v tabulce viz Tabulka 1 řádky noise) a na editovaných datech s pouţitím

ENN a All k – NN algoritmu viz Tabulka 1.

Výsledky testování vlivu editačních algoritmů na klasifikaci testovací mnoţiny (Full)

potvrzují zmíněný vztah ENN algoritmu a algoritmu All k – NN. Dále ukazují, ţe obě

editované mnoţiny mohou mít stejné výsledky. Na datech Šachovnice sice algoritmus All k –

NN redukuje o 72% více dat neţ algoritmus ENN, ale na druhé straně ENN algoritmus

dosahuje lepší klasifikační přesnosti, která je dokonce lepší neţ u pouţití původní trénovací

mnoţiny. Podobně je tomu i u dat Zuby, kde sice ENN algoritmus dosahuje lepší přesnosti

neţ All k – NN algoritmus, ale tato přesnost není vyšší neţ u pouţití plné trénovací mnoţiny.

Nejlepších výsledků dosáhl All k-NN algoritmus na datech Whirpool, kdy zachovává stejnou

klasifikační přesnost jako plná trénovací mnoţina i editovaná mnoţina pouţitím ENN

algoritmu, ale trénovací mnoţinu redukuje o 4,6%. Výsledky na datech Dvě E jsou pro oba

algoritmy stejné.


69

Tabulka 1: Vliv editačních algoritmů na klasifikaci 1 – NN

Algoritmus / Data

Zuby Dvě E Šachovnice Whirpool

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Full

Noise 92,5 0,0 100,0 0,0 96,0 0,00 98,8 0,0

ENN 91,8 5,3 100,0 1,2 96,3 5,0 98,8 4,5

All-kNN 89,8 7,7 100,0 1,2 96,0 8,6 98,8 4,6

CNN

Noise 92,5 86,4 100,0 86,5 91,7 82,1 95,3 84,7

ENN 90,5 92,0 97,7 87,4 92,4 86,7 100,0 89,7

All-kNN 92,5 93,1 96,6 86,8 92,4 88,1 97,6 91,7

RNN

Noise 94,5 87,8 98,8 87,1 92,0 86,0 97,6 88,4

ENN 89,1 93,3 98,8 90,0 57,3 89,8 97,6 91,

All-kNN 93,2 94,0 98,8 89,0 55,0 91,1 97,6 93,0

IB3

Noise 79,0 89,3 95,5 83,6 87,0 83,9 94,1 86,8

ENN 88,5 80,7 87,6 81,9 90,2 76,9 95,3 81,4

All-kNN 90,5 81,3 94,3 82,3 92,0 79,0 98,8 78,6

Prototypy

Noise 93,9 86,4 95,5 85,5 92,7 83,0 95,3 84,7

ENN 91,2 88,0 97,7 86,5 93,1 84,8 95,3 86,8

All-kNN 91,8 91,1 98,8 87,4 93,1 86,7 96,5 88,8

Chen

Noise 93,2 86,7 93,2 83,9 89,1 83,6 94,1 83,5

ENN 93,9 86,9 94,3 84,2 44,9 83,7 96,5 83,9

All-kNN 93,2 86,9 94,3 84,2 50,5 83,7 96,5 83,9

RSP1

Noise 92,5 84,9 100,0 77,4 90,2 80,8 94,1 81,8

ENN 93,9 86,9 100,00 78,46 47,19 83,78 93,0 83,9

All-kNN 93,2 86,9 100,00 78,46 47,19 83,78 94,1 83,9

RSP3

Noise 93,2 83,5 100,00 76,21 90,61 80,28 93,0 81,0

ENN 93,9 87,1 100,00 77,49 47,19 84,36 93,0 86,8

All-kNN 93,2 88,4 100,00 77,49 46,07 86,70 94,1 87,2

CNN algoritmus dosahuje na datech Zuby a Šachovnice nejlepších výsledků se vstupní

mnoţinou editovanou pouţitím All k – NN algoritmu, kdy má oproti ostatním vstupním

mnoţinám nejvyšší přesnost a redukční stupeň. Na datech Dvě E nejvyšší přesnosti

klasifikace dosahuje algoritmus CNN pouţitím plné trénovací mnoţiny. Algoritmus si

v porovnání s ostatními algoritmy vedl nejlépe s daty Whirpool, kdy jako jediný s editovanou

vstupní mnoţinou algoritmem ENN získal 100% klasifikaci. Ovšem vyšší redukce dat na

datech Whirpool dosáhl s pouţitím All k – NN algoritmu, kde má taky přesnost klasifikace

velmi dobrou, vyšší neţ u pouţití plné trénovací mnoţiny.

U RNN algoritmu jiţ nejsou získané výsledky s pouţitím editačních algoritmů tak

dobré, jako tomu bylo u CNN algoritmu. Na datech Zuby dosahuje sice o 1,25% niţší

přesnosti s pouţitím předzpracování All k – NN algoritmu neţ s původní trénovací mnoţinou,

ale na druhou stranu o 7,8 % lepší redukci. U dat Dvě E a Whirpool je zachována stejná


70

klasifikační přesnost u všech vstupních mnoţin. Nejvyššího redukčního stupně na datech Dvě

E dosahuje RNN algoritmus s editovanou mnoţinou pouţitím ENN algoritmu. A u dat

Whirpool dosahuje nejvyššího redukčního stupně s editačním algoritmem All k – NN.

Nejhůře dopadlo pouţití editačních algoritmů na datech Šachovnice. Editované vstupní

mnoţiny sníţily úspěšnost klasifikace z původních 92% na cca 56%.

IB3 algoritmus s pouţitím editovaných vstupní dat All k – NN algoritmem na datech

Zuby, Šachovnice a Whirpool dosahuje sice vyšší klasifikační přesnosti neţ při pouţitím

úplné trénovací mnoţiny, ale dosahuje poměrně nízké redukce dat. Na datech Dvě E dosahuje

algoritmus IB3 lepší klasifikační přesnosti s pouţitím původní trénovací mnoţiny.

S editovanou vstupní mnoţinou získanou pouţitím ENN algoritmu má IB3 algoritmus dobré

výsledky na datech Whirpool, klasifikační přesnost má sice niţší neţ s pouţitím vstupních dat

editovaných All k – NN algoritmem, ale má vyšší redukční rate.

Prototypy algoritmus dosahuje na všech datech nejlepších výsledků v přesnosti

klasifikace i v dosaţeném redukčním stupni s pouţitím editované mnoţiny pomocí All k –

NN algoritmu.

Chenův algoritmus na datech Zuby má nejvyšší klasifikační přesnost i redukční rate

s pouţitím předzpracovaných dat ENN algoritmem. Na datech Dvě E a Whirpool dosahuje

s oběma editovanými mnoţinami stejných výsledků, které jsou lepší neţ výsledky s pouţitím

úplné trénovací mnoţiny. Se sloţitou rozhodovací hranicí dat Šachovnice si Chenův

algoritmus při pouţití editované trénovací mnoţiny nedokázal poradit. Jeho klasifikační

přesnost se sníţila na cca 48%, coţ je nedostatečné.

RSP1 algoritmus má na datech Zuby nejlepší výsledky s pouţitím ENN editované

mnoţiny. Na datech Whirpool má zase nejlepší výsledky s pouţitím All k – NN editované

mnoţiny. Stejné klasifikační přesnosti a redukčního stupně, které jsou lepší neţ při pouţití

úplné trénovací mnoţiny, dosahuje na datech Dvě E s pouţitím obou editovacích algoritmů.

Taktéţ dosahuje velmi špatných výsledků na datech Šachovnice při pouţití editované

mnoţiny.

RSP3 algoritmus na datech Zuby dosahuje nejvyšší přesnosti s pouţitím editovaných

dat ENN algoritmem, ale lepší redukční rate má s editovanými daty All k – NN algoritmem.

Stejně jako RSP1 na datech Dvě E mají editované mnoţiny totoţnou klasifikační přesnost a

redukční stupeň, které jsou lepší neţ při pouţití úplné trénovací mnoţiny. Na datech Whirpool

vychází nejlépe pouţití editačního algoritmu All k – NN. S daty Šachovnice si bohuţel

s editovanou vstupní mnoţinou taktéţ nedokázal poradit.

Výsledky neuronové sítě GAME

U sítě GAME testuji přesnost klasifikace (v tabulce viz Tabulka 2 sloupce Acc[%]) a

také čas potřebný k vytvoření modelu s danými daty měřený v milisekundách (v tabulce x

sloupce Time[ms]).


71

Testovala jsem opět vliv editačních algoritmů na klasifikaci úplné trénovací mnoţiny.

Kondenzační algoritmy jsem zkoušela na needitovaných trénovacích datech (v tabulce viz

Tabulka 2 řádky noise) a na editovaných datech s pouţitím ENN a All k – NN algoritmu viz

Tabulka 2.

Tabulka 2: Vliv editačních algoritmů na neuronovou síť GAME

Algoritmus / Data

Zuby Dvě E Šachovnice Whirpool

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Full

Noise 91,8 43520 74,1 26147 81,2 90728 84,1 26150

ENN 91,2 36435 77,5 25636 86,6 88720 94,2 22798

All k-NN 90,5 38536 78,6 22356 82,3 82231 96,5 23720

CNN

Noise 56,7 6433 94,4 4970 50,9 6167 82,5 5346

ENN 67,5 4761 85,4 3514 49,5 5254 82,6 2896

All-kNN 73,6 2588 89,9 3617 50,1 5621 81,4 1963

RNN

Noise 49,3 7624 97,7 3829 55,9 5636 74,4 3377

ENN 85,8 3100 94,3 3753 51,6 5384 76,7 1821

All-kNN 68,2 2353 98,8 3613 58,1 5159 74,4 1375

IB3

Noise 72,9 3524 69,6 6366 74,4 19548 89,5 3053

ENN 82,4 8226 69,6 7101 76,1 36239 95,5 5768

All-kNN 82,4 8511 75,2 5805 71,4 34686 84,9 5647

Prototypy

Noise 78,3 5695 95,5 4907 72,5 11207 91,8 4214

ENN 87,8 5932 92,1 5764 61,7 7072 91,9 3944

All-kNN 83,7 4265 83,1 4413 63,1 7978 90,7 2793

Chen

Noise 77 6206 84,2 5431 64,3 14379 76,7 5173

ENN 87,1 6031 82 4918 70 14038 89,5 4610

All-kNN 84,4 5946 79,7 5314 71,5 11459 87,2 3955

RSP1

Noise 84,5 7199 92,1 8833 73,6 19357 83,7 6146

ENN 85,1 6284 86,5 7556 66 15430 93 4826

All-kNN 83,7 6123 98,8 8929 71,1 14108 91,8 4631

RSP3

Noise 81,7 8715 97,7 8808 62,8 26803 75,6 5577

ENN 84,4 7463 93,2 7935 61,7 10109 87,2 3997

All-kNN 85,8 6123 95,5 8780 68,2 9161 86 3226

Výsledky testování vlivu editačních algoritmů na klasifikaci testovací mnoţiny (Full)

neuronové sítě GAME opět potvrzují zmíněný vztah ENN algoritmu a algoritmu All k – NN.

Téměř na všech datech je vidět, ţe algoritmus All k – NN sice redukuje trénovací mnoţinu

dat více neţ algoritmus ENN, čímţ je čas potřebný na vytvoření modelu kratší, ale má niţší

klasifikaci neţ algoritmus ENN. Přesnost s pouţitím ENN algoritmu je u většiny dat dokonce

lepší neţ u pouţití původní trénovací mnoţiny. Pouze na datech Dvě E algoritmus All k-NN

dosahuje nejen nejlepšího času pro vytvoření modelu, ale také nejvyšší klasifikační přesnosti.

U CNN algoritmu je na datech Zuby je jasně vidět jeho problém při pouţití needitované

vstupní mnoţiny. Při pouţití editovaných dat algoritmem All k – NN klasifikační přesnost


72

vzrostla o 17,1% a navíc je síť vybudována cca 2,5 krát rychleji. Na datech Dvě E vychází

nejvyšší klasifikační přesnost s pouţitím editované mnoţiny All k – NN algoritmem, ale

nejlepší čas pro vytvoření sítě dosahuje CNN algoritmus s editovanou mnoţinou ENN

algoritmem. Data Šachovnice není schopen algoritmus CNN zredukovat ani s jednou vstupní

mnoţinou tak, aby se neuronová síť GAME byla schopná dobře naučit. Na datech Whirpool

má CNN algoritmus největší úspěch s editovanou mnoţinou pomocí ENN algoritmu.

RNN algoritmus podobně jako CNN algoritmus na datech Zuby ukazuje svoji slabou

stránku. Neschopnost správné redukce některých dat, ze kterých nejsou odebrány rušivé a

hraniční instance. Na datech Whirpool dosahuje neuronová síť GAME vyšší přesnosti

s pouţitím editovaných dat ENN algoritmem, ale rychleji se učí s editovanými daty All k –

NN algoritmem, se kterými dosahuje stejné klasifikační přesnosti jako s pouţitím úplné

trénovací mnoţiny. Data Šachovnice není algoritmus RNN také schopen přiměřeně

zredukovat, coţ vychází jiţ z faktu, ţe RNN algoritmus získává pouze podmnoţinu instancí

získaných CNN algoritmem. Data Dvě E algoritmus CNN jednoznačně redukuje nejlépe

s pouţitím editovaných dat All k – NN algoritmem.

IB3 algoritmus dosahuje na datech Zuby, Šachovnice a Whirpool nejpřesnější

klasifikace s pouţitím editovaných dat algoritmem ENN, ale čas potřebný na vytvoření

modelu je podstatně niţší při pouţití úplné trénovací mnoţiny. Na datech Dvě je nejúspěšnější

s editovanou vstupní mnoţinou pouţitím All k – NN algoritmu.

Algoritmus Prototypy je neuronovou sítí GAME klasifikován na datech Zuby a

Whirpool nejlépe s pouţitím editované mnoţiny ENN algoritmem, ale nejkratší doby pro

vytváření modelu dosahuje na těchto datech s editovanou mnoţinou All k – NN algoritmem.

Na datech Šachovnice má nejvyšší klasifikační přesnost při pouţití původních trénovacích

dat, ale nejrychleji je model sítě vytvořen s pouţitím editovaných dat All k – NN algoritmem.

U dat Dvě E dopadl nejlépe s pouţitím původní trénovací mnoţiny, i kdyţ byl rychlejší

s mnoţinou editovanou algoritmem All k – NN.

Chenův algoritmus na datech Zuby a Whirpool má nejlepší klasifikaci pro vstupní

editovanou mnoţinu ENN algoritmem, ale nejrychleji je síť postavena s pouţitím editované

mnoţiny All k – NN algoritmem. U dat Dvě E je redukovaná mnoţina Chenovým algoritmem

nejlépe klasifikována pouţitím úplné trénovací mnoţiny a nejrychleji je model vytvořen

s pouţitím editované mnoţiny algoritmem ENN. Redukovaná data Šachovnice jsou nejlépe

ohodnocena s předzpracováním editačním algoritmem All k – NN.

RSP1 algoritmus na datech Zuby a Whirpool má nejpřesnější klasifikaci s pouţitím

editované mnoţiny ENN algoritmem, ale nejrychleji je model vystaven s pouţitím editované

mnoţiny algoritmem All k – NN. U dat Dvě E má největší klasifikační přesnost s pouţitím

editovaných dat All k – NN algoritmem, ale nejrychlejší je s pouţitím editovaných dat ENN

algoritmem. Na datech Šachovnice je RSP1 algoritmus nejúspěšnější při pouţití editované

trénovací mnoţiny All k – NN algoritmem, kdy přesnost je sice o 2,5% niţší neţ u pouţití

úplných trénovacích dat, ale doba vytvoření modelu je o 23% kratší.


73

Zredukovaná data Zuby a Šachovnice algoritmem RSP3 jsou nepřesněji klasifikována

s pouţitím editované vstupní mnoţiny All k – NN algoritmem, kdy je také model sítě

postaven nejrychleji. Na Dvě E datech dosahuje algoritmus RSP3 nejvyšší klasifikace

s pouţitím původní trénovací mnoţiny, ale nejrychleji je model vybudován s pouţitím

editované mnoţiny ENN algoritmem.

Výběr editačních algoritmů

Z výsledků získaných pouţitím 1 – NN klasifikátoru a neuronové sítě GAME vychází,

ţe pro všechny zkoumané algoritmy je ve většině případů výrazně lepší pouţít editovanou

vstupní trénovací mnoţinu. Z porovnání vlivu editačních algoritmů na kvalitu kondenzačních

algoritmů na všech vytvořených umělých datech jsem se rozhodla pro jednotlivé algoritmy

zvolit nejvhodnější editační algoritmus.

Algoritmy CNN, RNN, Prototypy a RSP3 budu dále testovat a porovnávat jejich

výsledky na umělých a reálných datech s pouţitím trénovací mnoţiny předzpracované

algoritmem All k – NN. Ostatní algoritmy IB3, Chen a RSP1 budu dále testovat a porovnávat

jejich výsledky na umělých a reálných datech s pouţitím trénovací mnoţiny předzpracované

algoritmem ENN.

8.3.3 Srovnání algoritmů

1 – NN klasifikátor

Pro porovnání všech kondenzačních implementovaných algoritmů vycházím z

následující tabulky viz Tabulka 3, ve které jsou výsledky implementovaných algoritmů se

vstupní editovanou mnoţinou zvolenou v předchozí kapitole (sloupec Editace). Opět jsem u

klasifikátoru 1 – NN porovnávala vlastnosti přesnost klasifikace (sloupec Acc[%]) a redukční

stupeň (sloupec Size[%]) u jednotlivých, uměle vytvořených, trénovacích mnoţin, kdy jako

první uvádím výsledky úplné trénovací mnoţiny (Full data).

Tabulka 3: Porovnání algoritmů na umělých datech, 1 – NN klasifikátor

Data Zuby Dvě E Šachovnice Whirpool

Algoritmy Editace Acc

[%] Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Full data --- 92,6 0,0 100,0 0,0 96,0 0,0 98,8 0,0

CNN AllKNN 92,6 93,1 96,6 86,8 92,4 88,1 97,7 91,8

RNN AllKNN 93,2 94,0 98,9 89,1 55,1 91,1 97,7 93,0

IB3 ENN 88,5 80,7 87,6 82,0 90,3 76,9 95,3 81,5

DROP3 ENN 98,0 75,8 97,7 62,3 97,0 61,8 99,2 73,3

Prototypy AllKNN 91,9 91,1 98,9 87,5 93,1 86,7 96,5 88,9

Chen ENN 93,9 86,9 94,4 84,2 44,9 83,8 96,5 84,0

RSP1 ENN 93,9 86,9 100,0 84,2 47,2 83,8 93,0 84,0

RSP3 AllKNN 93,2 88,5 100,0 77,5 46,1 86,7 94,2 87,2


74

U algoritmů Chen a RSP1 jsem pro jednotlivá data nastavila následující velikost

výsledné mnoţiny:

Zuby 60

Dvě E 50

Šachovnice 140

Whirpool 40

Z naměřených výsledků viz Tabulka 3 je vidět, ţe na datech Zuby byl jednoznačně

nejúspěšnější algoritmus DROP3. Klasifikační přesnost 1 – NN klasifikátoru je s pouţitím

jeho redukované mnoţiny o 5,4% vyšší neţ přesnost s pouţitím původní neredukované

mnoţiny, jejíţ velikost je ale o 75,8 % větší neţ velikost zredukované mnoţiny DROP3

algoritmem. Dalšími algoritmy, které dosáhly vysoké přesnosti, jsou algoritmy Chen a RSP1.

Jejich přesnost je zajištěna nastavením počtu instancí výsledné redukované mnoţiny a je na

datech Zuby totoţná. Algoritmy RSP3 a RNN dosahují taktéţ vyšší klasifikační přesnosti neţ

při pouţití původní trénovací mnoţiny, přičemţ RNN algoritmus ponechává nejmenší

redukovanou mnoţinu, pouze 6% instancí původní trénovací mnoţiny. Stejné klasifikační

přesnosti jako je přesnost s neredukovanou trénovací mnoţinou dosáhl CNN algoritmus, který

ji redukuje o 93,1%. Niţší přesnost mají redukované mnoţiny pouţitím algoritmu IB3 o 4,1%

a algoritmu Prototypy o 0,7%.

S daty Dvě E si nejlépe vedl algoritmus RSP1 s nastaveným redukčním stupněm na

84,2%. Dosáhl 100% klasifikační přesnosti, které je dosaţeno i s pouţitím původní trénovací

mnoţiny. Algoritmus RSP3 také zachovává 100% klasifikační přesnost, ale jeho redukční rate

je 77,5 %. Slušné klasifikační přesnosti 98,9% dosáhly algoritmy RNN a Prototypy, kdy RNN

algoritmus opět ponechává ze všech algoritmů nejmenší redukovanou mnoţinu, pouze 10,9%

instancí původní redukované mnoţiny. Nejniţší klasifikační přesnost má na datech Dvě E

redukovaná mnoţina pouţitím algoritmu IB3, která je 87,6%.

Se sloţitou rozhodovací hranicí dat Šachovnice jiţ měly některé redukční algoritmy

značné problémy. Nejvyšší klasifikační přesnosti dosáhl algoritmus DROP3 a je o 1% vyšší

neţ klasifikační přesnost s pouţitím původní trénovací mnoţiny. DROP3 algoritmus ovšem

trénovací data redukuje ze všech algoritmů nejméně – o 61,8%. S daty si rozumně poradily i

algoritmy CNN, IB3 a Prototypy. I kdyţ je jejich klasifikační přesnost niţší neţ při pouţití

úplné trénovací mnoţiny, pohybuje se stále nad hranicí 90%. Algoritmus RNN a algoritmy

zaloţené na rozdělování mnoţiny na oblasti RSP1, RSP3 a Chen bohuţel sníţily klasifikační

přesnost 1 – NN klasifikátoru k pouhým 50%.

Na datech Whirpool si překvapivě vedly všechny redukční metody dobře, i kdyţ vyšší

klasifikační přesnosti, neţ je přesnost neredukovaných dat 98,8% dosáhnul pouze algoritmus

IB3, který tuto přesnost zvýšil na 99,2%. Algoritmy CNN a RNN měly stejnou klasifikační

přesnosti 97,7%, kdy algoritmus RNN zredukoval původní mnoţinu o 1,2 % více neţ

algoritmus CNN. Nejniţší přesnosti 93% dosáhnul algoritmus RSP1 s nastaveným redukčním

stupněm na 84%.


75

Nejlepších výsledků v přesnosti klasifikace 1 – NN klasifikátoru na umělých datech

dosáhl neadaptivní algoritmus DROP3. Sice na datech Dvě E sníţil klasifikační přesnost

s úplnou trénovací mnoţinou o 2,3%, ale u ostatních dat vţdy klasifikační přesnost zvýšil.

Jeho redukční rate se pohybuje okolo 70%. Vynikajících výsledků také dosáhly na datech,

která nemají příliš komplikovanou rozhodovací hranici, regulovatelné adaptivní algoritmy

Chen a RSP1 a adaptivní algoritmus RSP3. Metodu CNN je výhodné pouţít na libovolnou

uměle vytvořenou trénovací mnoţinu, klasifikační přesnost příliš nesniţuje a její redukční

stupeň se pohybuje okolo 90%. Metoda RNN získává lepší klasifikační přesnosti a vyššího

redukčního stupně neţ metoda CNN, ale s daty se sloţitou rozhodovací hranicí si poradit

nedokázala. Adaptivní algoritmus Prototypy dokázal na všech datech zachovat vyšší

klasifikační přesnost neţ 91%, ale nikdy nedosáhl stejné, ani vyšší klasifikační přesnosti, jaká

byla získána s pouţitím neredukované trénovací mnoţiny. Poslední metoda IB3 podávala na

většině dat nejhorší výsledky, ale i na datech Šachovnice její klasifikační přesnost nebyla

niţší neţ 87,6%.

Neuronová síť GAME

Pro porovnání všech implementovaných algoritmů vycházím z následující tabulky viz

Tabulka 4, ve které jsou výsledky implementovaných algoritmů na vytvořených umělých

datech se vstupní editovanou mnoţinou zvolenou v předchozí kapitole (sloupec Editace). U

Neuronové sítě GAME jsem porovnávala vlastnosti přesnost klasifikace (sloupec Acc[%]) a

čas potřebný na vytvoření modelu (sloupec Time[%]), kdy jako první uvádím výsledky

s pouţitím úplné trénovací mnoţiny (Full data).

Tabulka 4: Porovnání algoritmů na umělých datech, neuronová síť GAME


Algoritmy Editace Acc [%]

Time [ms]

Acc [%] Time [ms]

Acc [%] Time [ms]

Acc [%] Time [ms]

Full data --- 91,8 43520 74,1 26147 81,2 90728 84,1 26150

CNN AllKNN 73,6 2588 89,9 3617 50,1 5621 81,4 1963

RNN AllKNN 68,2 2353 98,8 3753 58,1 5159 74,4 1375

IB3 ENN 82,4 8226 69,6 7101 76,1 36239 95,5 5768

DROP3 ENN 82,4 15216 98,9 12285 69,3 23333 96,5 6855

Prototypy AllKNN 83,7 4265 83,1 4413 63,1 7978 90,7 2793

Chen ENN 87,1 6031 82 4918 70 14038 89,5 4610

RSP1 ENN 85,1 6284 86,5 7556 66 15430 93 4826

RSP3 AllKNN 85,8 6123 95,5 8780 68,2 9161 86 3226

U algoritmů Chen a RSP1 jsem pro jednotlivá data nastavila stejnou velikost výsledné

mnoţiny, jako jsem nastavila u testování klasifikátoru 1 – NN viz výše.

V tabulce viz Tabulka 4 na datech Zuby můţeme sledovat, ţe redukční metody jsou při

klasifikaci neuronovou sítí GAME méně úspěšné neţ u klasifikace 1 – NN klasifikátorem.

Nejvyšší klasifikační přesnosti dosahuje GAME s pouţitím původní trénovací mnoţiny,


76

ovšem vybudování modelu sítě trvá nejdéle. Z redukčních algoritmů nejvyšší klasifikační

přesnosti dosahuje Chenův algoritmus, a jeho klasifikace je o 4,7% niţší neţ je přesnost

klasifikace s pouţitím úplné trénovací mnoţiny, ale model sítě je s redukovanou mnoţinou

vytvořen 7 krát rychleji. Klasifikace vyšší neţ 85% dosáhla GAME s pouţitím algoritmů,

které jsou postaveny na stejném principu jako Chen, tudíţ algoritmů RSP1 a RSP2. Algoritmy

DROP3, Prototypy a IB3 mají klasifikační přesnost nad 80%. Nejhůře dopadly algoritmy

CNN a RNN, kdy CNN algoritmus dosahuje 73,6% úspěšnosti a RNN algoritmus pouze

68,2%.

Na druhé straně na datech Dvě E redukční metody při klasifikaci neuronovou sítí

GAME měly lepší výsledky, neţ při klasifikaci 1 – NN klasifikátorem. Aţ na algoritmus IB3

byly všechny pouţité redukční metody ohodnoceny GAME sítí lépe, neţ při pouţití úplné

trénovací mnoţiny. Nejlépe uspěl algoritmus DROP3, který klasifikační přesnost oproti

klasifikaci s původní neredukovanou trénovací mnoţinou zvýšil o 24%, přičemţ sníţil dobu

potřebnou pro vybudování modelu sítě o 53%. Klasifikační přesnosti o 0,1% niţší dosáhl

algoritmus RNN, u kterého navíc výstavba modelu sítě trvala jen 14,35% času, který

potřebovala síť GAME s pouţitím úplné trénovací mnoţiny. Vysoké klasifikační přesnosti

(95,5%) dosáhl algoritmus RSP3, který také trojnásobně zrychlil proces učení. CNN

algoritmus byl ohodnocen téměř 90% úspěšností. Algoritmy Prototypy, Chen a RSP1 udrţují

klasifikační mez nad 80%. Nejhůře dopadl jiţ zmiňovaný algoritmus IB3, který dosáhl pouhé

69,6% přesnosti.

I v hodnocení neuronové sítě GAME se projevily značné problémy některých

redukčních algoritmů se sloţitou rozhodovací hranicí dat Šachovnice. Opět ani jeden

z pouţitých algoritmů nezvyšuje klasifikační přesnost sítě GAME s pouţitím neredukovaných

dat. Nejhorší klasifikační přesnost na těchto datech má algoritmus CNN, pouze 50,1%.

Překvapivě nejlepšího výsledku dosáhl algoritmus IB3 jehoţ úspěšnost je o 5,1% niţší neţ při

pouţití úplné trénovací mnoţiny, ale model sítě je postaven 2,5 krát rychleji. Klasifikační

přesnosti ostatních algoritmů se pohybují od 60 – 70%.

Na datech Whirpool je opět většina redukčních algoritmů velmi úspěšná. Pouze

algoritmy CNN a RNN dosahují niţší přesnosti neţ je získána pouţitím úplné trénovací

mnoţiny. Jejich klasifikační přesnost ovšem není niţší neţ 74,4%. GAME nejpřesněji

klasifikuje opět s pouţitím redukované mnoţiny algoritmem DROP3, kdy je přesnost rovna

96,5%. Dobu učení zrychluje 3,8 krát. O 1% niţší klasifikace dosahuje algoritmus IB3, kdy je

proces budování sítě 4,5 krát rychlejší neţ při pouţití úplné redukované mnoţiny. Přesnosti

vyšší neţ 90% dosahuje také algoritmus RSP1. Algoritmus Chen je úspěšnější o 5,4% neţ při

pouţití plné trénovací mnoţiny a algoritmus RSP3 má lepší klasifikaci o 1,9%.

Nejlepších výsledků v přesnosti klasifikace neuronové sítě GAME na umělých datech

dosáhl algoritmus DROP3. Nebyl sice tolik úspěšný jako při klasifikaci 1 – NN

klasifikátorem, ale na datech Dvě E a Whirpool dosáhl nejvyšší klasifikační přesnosti. Dále

byl úspěšný algoritmus IB3, který na datech Zuby a Whirpool dosahoval vysoké přesnosti a

na datech Šachy se sloţitou rozhodovací hranicí byl nejpřesnější. Dobré klasifikační přesnosti


77

dosáhly také všechny neadaptivní algoritmy Prototypy, Chen, RSP1 a RSP3. Za to adaptivní

algoritmy CNN a RNN nedosahovaly dobrých výsledků na ţádných umělých datech kromě

dat Dvě E.

8.4 Redukce reálných dat

K ověření pouţitelnosti implementovaných algoritmů na reálných datech jsem zvolila

dataset proteinů Ecoli, který má ze všech reálných mnoţin nejvíce tříd (8), data k měření

radarových odrazů Ionosphere, která se vyznačují vysokým počtem atributů, EKG záznamy

srdečních stahů, data Mandarinky popisující mnoţství vody zkonzumované mandarinkovým

stromem a data Glass, která slouţí k popisu typů skel. Podrobnější popis pouţitých reálných

dat naleznete v kapitole 8.1.2.

Testovací a trénovací data jsem získala stejným způsobem jako v případě reálných dat.

Do trénovací mnoţiny jsem náhodně vybrala 75% dat z původních dat. Zbylých 25% dat jsem

pouţila pro testovací mnoţinu.

8.4.1 Srovnání algoritmů

1 – NN klasifikátor


Tabulka 5, ve které jsou výsledky implementovaných algoritmů na reálných datech se

vstupní editovanou mnoţinou zvolenou v předchozí kapitole (sloupec Editace). Opět jsem u

klasifikátoru 1 – NN porovnávala vlastnosti přesnost klasifikace (sloupec Acc[%]) a redukční

stupeň (sloupec Size[%]) jednotlivých trénovacích mnoţin, kdy jako první uvádím výsledky

úplné trénovací mnoţiny (Full data).

Tabulka 5: Porovnání algoritmů na reálných datech, 1 – NN klasifikátor

Data Ecoli EKG Glass Ionosphere Mandarinky

Algoritmy Editace

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Full data --- 84,0 0,0 96,7 0,0 72,1 0,0 82,9 0,0 89,8 0,0

CNN AllKNN 84,0 90,8 96,2 97,3 72,1 89,5 79,2 94,0 56,2 91,9

RNN AllKNN 84,0 93,8 96,1 98,0 72,1 89,5 75,6 96,6 64,3 93,0

IB3 ENN 84,0 88,1 95,9 83,5 75,4 82,3 84,1 82, 67,0 80,8

DROP3 ENN 84,0 84,6 94,9 94,9 77,0 74,5 82,9 89,9 63,0 83,8

Prototypy AllKNN 81,3 90,4 99,7 91,5 65,5 86,2 81,7 87,7 63,8 92,5

Chen ENN 89,3 77,0 96,2 88,9 73,7 60,7 86,5 79,5 68,5 64,9

RSP1 ENN 89,3 77,0 96,2 88,9 72,1 60,7 86,5 79,5 68,5 64,9

RSP3 AllKNN 88,0 88,5 96,1 96,1 73,7 81,0 85,3 86,2 62,8 91,0


78

U algoritmů Chen a RSP1 jsem pro jednotlivá reálná data nastavila následující velikost


Ecoli 60

EKG 550

Glass 60

Ionosphere 55

Mandarinky 1100

S daty Ecoli si nejlépe poradily adaptivní algoritmy. Algoritmy RSP1 a Chen dosáhly

nejvyšší klasifikační přesnosti, která je o 5,3% vyšší neţ při klasifikaci s pouţitím úplné

trénovací mnoţiny, díky nastavení poměrně nízkého redukčního stupně. Algoritmus RSP3,

který taktéţ rozděluje data na oblasti jako algoritmy RSP1 a Chen, také nezůstal po zadu a

dosahuje klasifikační přesnosti jen o 1,3 % niţší, ale jeho redukční stupeň je 88%. Poslední

adaptivní algoritmus Prototypy má sice nejniţší klasifikační přesnost ze všech

implementovaných algoritmů, ale její sníţení není příliš markantní. Všechny neadaptivní

algoritmy dosáhly stejné klasifikační přesnosti, která je rovna klasifikační přesnosti dosaţené

s pouţitím původní trénovací mnoţiny. Jejich redukční rate se pohybuje od 84,6% do 93,8%

velikosti původní trénovací mnoţiny.

U dat Ecoli byl nejúspěšnější algoritmus Prototypy, jehoţ klasifikační přesnost byla o

3% vyšší neţ při klasifikování s úplnou trénovací mnoţinou. Redukované mnoţiny metodami

Chen, RSP1 a CNN dosáhly stejné klasifikační přesnosti, která je o 0,5% niţší neţ při pouţití

neredukovaných dat. CNN algoritmus navíc původní mnoţinu zredukoval o 97,3%.

Klasifikační úspěšnost o 0,1% horší mají algoritmy RNN a RSP3, kdy RNN algoritmus

zredukoval původní data ze všech nejvíce. Jeho redukční stupeň je 98% původní velikosti.

Nejméně úspěšné byly algoritmy DROP3 a IB3, ale jejich klasifikační přesnost neklesla pod

94,9%.

Na datech Glass selhal pouze algoritmus Prototypy, který dosáhl klasifikace o 6,6%

niţší neţ při pouţití úplné trénovací mnoţiny. Nejvyšší klasifikační přesnost má algoritmus

DROP3, který přesnost s pouţitím neredukované trénovací mnoţiny zlepšuje o 4,9%. Dobré

klasifikační přesnosti dosáhl také algoritmus IB3. Jeho přesnost je o 3,3% vyšší neţ přesnost

s původní mnoţinou dat. Algoritmy Chen a RSP3 taktéţ vylepšuji klasifikační přesnost

s úplnou trénovací mnoţinou a to o 1,6%. Algoritmy RSP1, CNN a RNN zachovávají stejnou

klasifikační přesnost jaké je dosaţeno s pouţitím neredukovaných dat, kdy algoritmus RNN a

CNN redukují původní mnoţinu nejvíce, zanechávají pouze 9,5%.

S vysokým počtem atributů u dat Ionosphere, si nejlépe poradily algoritmy Chen a

RSP1. Je to opět díky nastavenému nízkému redukčnímu stupni. Tyto algoritmy klasifikační

úspěšnost s pouţitím původní mnoţiny vylepšují o 3,6%. Algoritmus RSP3 také vylepšuje

klasifikační přesnost oproti neredukovaným datům a to o 2,8%. Úspěšný je také algoritmus

IB3, který je v klasifikaci o 1,2% horší neţ algoritmus RSP3. Pouţitím redukované mnoţiny

algoritmem DROP3 dosahuje klasifikátor 1 – NN stejné přesnosti jako s úplnou mnoţinou,


79

přičemţ algoritmus DROP3 redukuje trénovací mnoţinu o 89,9%. Niţší klasifikační přesnosti

dosahují algoritmy CNN, RNN a Prototypy, která ovšem neklesá pod 75,6%.

Na datech Mandarinky nedosahuje ani jeden z implementovaných redukčních algoritmů

uspokojivých výsledků. Nejlepší klasifikační přesnosti dosáhly algoritmy Chen a RSP1. Jejich

přesnost je však o 21,3% niţší neţ při pouţití neredukované trénovací mnoţiny. O 1,5% horší

klasifikační přesnosti neţ algoritmy Chen a RSP1 dosáhl algoritmus IB3, který původní

mnoţinu redukuje o 80,8%. Algoritmy RSP3, DROP3 a RNN zachovávají klasifikační

přesnost vyšší neţ 62,8%. Algoritmus CNN dosahuje pouhých 56,2% klasifikační přesnosti.

Nejlepších výsledků na všech reálných datech bylo dosaţeno s pouţitím

regulovatelných adaptivních algoritmů Chen a RSP1, které měly na všech datech dobrou

klasifikační přesnost, i kdyţ na úkor redukčního stupně. Algoritmus RSP3, který sice není

regulovatelný, ale je postaven na podobném principu jako algoritmy Chen a RSP1, také

dosahoval na všech reálných datech vynikajících výsledků. Dále byl úspěšný algoritmus IB3,

který pouze na datech EKG a Mandarinky nebyl 1 – NN klasifikátorem ohodnocen lépe, neţ

při pouţití úplné trénovací mnoţiny. Algoritmus DROP3 dosahoval nepatrně niţší

klasifikační přesnosti na datech Ecoli, EKG, Ionosphere a Mandarinky neţ algoritmus IB3.

Na datech Glass byl ze všech algoritmů nejúspěšnější. Algoritmus Prototypy dosahoval

dobrých výsledků na datech EKG, Ionosphere a Ecoli. Algoritmy CNN a RNN si dobře vedly

s daty Ecoli, EKG a Glass, příliš mnoho atributů u dat Ionosphere nebyly schopny dostatečně

zpracovat.



Tabulka 6, ve které jsou výsledky implementovaných algoritmů na reálných datech se

vstupní editovanou mnoţinou zvolenou v předchozí kapitole (sloupec Editace). U Neuronové

sítě GAME jsem porovnávala vlastnosti přesnost klasifikace (sloupec Acc[%]) a čas potřebný

na vytvoření modelu (sloupec Time[%]), kdy jako první uvádím výsledky s pouţitím úplné

trénovací mnoţiny (Full data).

Tabulka 6: Porovnání algoritmů na reálných datech, neuronová síť GAME

Data Ecoli EKG Glass Ionosphere Mandarinky

Algoritmy Editace

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Acc [%]

Time [ms]

Full data --- 85,3 59363 93,7 259051 44,2 46935 90,2 27481 59,0 419336

CNN AllKNN 86,7 4881 93,7 16409 47,5 2687 46,3 1256 43,1 53191

RNN AllKNN 82,6 3036 87,0 13188 37,7 2820 73,1 777 50,0 57125

IB3 ENN 66,7 5563 93,9 54482 39,3 6525 86,5 2341 61,3 100564

DROP3 ENN 76,0 10360 88,3 31672 47,5 6061 84,1 966 48,7 103886

Prototypy AllKNN 82,7 4618 93,3 29175 37,7 4310 64,6 2078 55,0 59740

Chen ENN 88,0 12232 93,7 38590 52,5 14762 82,9 3105 61,4 147646

RSP1 ENN 84,0 12217 93,9 36780 47,5 15673 86,5 3117 61,0 150102

RSP3 AllKNN 81,3 5116 92,5 24124 19,6 12399 84,1 1971 54,0 70278


80


mnoţiny, jako jsem nastavila u testování klasifikátoru 1 – NN na reálných datech viz výše.

V tabulce viz Tabulka 6 u dat Ecoli je patrné ţe nejlepší klasifikační přesnosti dosáhl

algoritmus Chen, díky niţšímu redukčnímu stupni. Zvyšuje klasifikační přesnost sítě Game o

2,7% oproti pouţití úplné trénovací mnoţiny. Lepšího výsledku ovšem dosáhl algoritmus

CNN, který zvyšuje klasifikační přesnost proti neredukovaným datům o 1,4%, ale čas

potřebný na výstavbu sítě sniţuje o 91,78%. Algoritmus RNN tento čas sniţuje ještě více, ale

má také niţší klasifikační přesnost. Algoritmy RSP3, Chen, RSP1 a Prototypy mají niţší

klasifikační přesnost neţ je dosaţena s pouţitím neredukované trénovací mnoţiny, ale je vyšší

neţ 81,3%. Redukovaná mnoţina algoritmem DROP3 byla neuronovou sítí klasifikována se

76% úspěšností. Nejhůře dopadl algoritmus IB3, který má klasifikační přesnost 66,7%.

Naproti tomu IB3 algoritmus na datech EKG dosahuje nejlepší klasifikační přesnosti,

která je o 0,2% lepší neţ při pouţití neredukovaných dat a sniţuje čas potřebný na

vybudování modelu sítě o 78,9%. Stejné klasifikační přesnosti dosáhl algoritmus RSP1, který

čas potřebný na vybudování modelu sítě sniţuje o 85,8%. Stejné klasifikační přesnosti jako je

při pouţití původní trénovací mnoţiny dosáhly algoritmy CNN a Chen. CNN algoritmus opět

dosáhnul vysoké početní redukce dat, kdy zanechal pouhých 6,3% původních dat. Neuronová

síť GAME s mnoţinou redukovanou algoritmem RSP3 byla o 1,8% méně úspěšná neţ při

pouţití úplné trénovací mnoţiny. Algoritmy RNN a DROP3 mají niţší klasifikační přesnost,

která ovšem není niţší neţ 87%.

Data Glass jsou neuronovou sítí GAME klasifikována s nízkou přesností, která je

s pouţitím úplné trénovací mnoţiny rovna 44,2%. Tato přesnost s pouţitím 1 – NN

klasifikátoru byla podstatně vyšší a to 72,1%. Na datech Glass dosahuje opět nejlepší

klasifikační přesnosti algoritmus Chen, který původní klasifikační přesnost zvyšuje o 11,3% a

čas potřebný na vybudování sítě sniţuje o 68,6%. Algoritmy CNN, DROP3 a RSP1 dosahují

stejné klasifikační přesnosti, která je o 3,3% vyšší neţ při pouţití úplné trénovací mnoţiny.

IB3 algoritmus dosahuje klasifikační přesnosti o 4,9% niţší neţ neredukovaná data. Nízké

klasifikační přesnosti dosahují algoritmy RNN a Prototypy. Nejhůře ovšem dopadl adaptivní

algoritmus RSP3, jehoţ redukovaná mnoţina je správně ohodnocena pouze v 19,6% případů.

Po redukci dat Ionosphere s vysokým počtem atributů neuronová síť nedosáhla ani

s jednou redukovanou trénovací mnoţinou stejné nebo vyšší klasifikační přesnosti jako

s pouţitím úplné trénovací mnoţiny. Nejvyšší klasifikační přesnosti dosáhly algoritmy RSP1

a IB3 a je o 3,7% horší neţ při pouţití původních dat. Na druhé straně tyto algoritmy opět

rapidně zrychlují proces vytváření modelu sítě. Algoritmy DROP3 a RSP3 dosáhly o 2,4%

niţší klasifikační přesnosti neţ algoritmy RSP1 a IB3. Klasifikační přesnosti 82,9% dosáhl

Chenův algoritmus. Zajímavé jistě je, ţe RNN algoritmus dosáhnul klasifikační přesnosti

73,1% a algoritmus CNN, který dopadl ze všech implementovaných metod nejhůře,

klasifikační přesnosti pouhých 46,3%. Můţe to být zapříčiněno náhodným výběrem instance


81

u CNN algoritmu, kdy RNN algoritmus můţe zpracovávat jinou konzistentní mnoţinu.

Algoritmus Prototypy taktéţ dosáhl nízké klasifikační přesnosti 64,6%.

Na datech Mandarinky byly s pouţitím neuronové sítě GAME redukované mnoţiny

ohodnoceny lépe neţ s pouţitím 1 – NN klasifikátoru. Velký podíl na tom nese fakt, ţe data

Mandarinky jsou neuronovou sítí GAME klasifikována s nízkou přesností, která je s pouţitím

úplné trénovací mnoţiny rovna pouhým 59%. Nejvyšší klasifikační přesnosti dosáhl

algoritmus Chen. Jeho úspěšnost je o 2% vyšší neţ s pouţitím neredukovaných dat. Jen o

0,1% niţší úspěšnost má algoritmus IB3, který původní čas na vybudování sítě sniţuje o 76%.

Posledním algoritmem, jehoţ redukovaná mnoţina má vyšší přesnost neţ mnoţina původní,

je algoritmus RSP1. Algoritmy RSP3, Prototypy a RNN mají klasifikační přesnost vyšší neţ

50%. Algoritmy DROP3 a CNN dopadly nejhůře. Jejich klasifikační přesnost je vyšší neţ

43,4%.

Nejlepších výsledků na všech reálných datech bylo při klasifikaci neuronovou sítí

GAME dosaţeno s pouţitím regulovatelných adaptivních algoritmů Chen a RSP1 stejně jako

u klasifikátoru 1 – NN. Tyto algoritmy měly na všech datech dobrou klasifikační přesnost, i

kdyţ na úkor redukčního stupně. Algoritmus RSP3, zaloţený na podobném principu,

dosahoval na datech Glass a Mandarinky velmi špatných výsledků. Na ostatních datech si

vedl o něco hůře neţ algoritmy Chen a RSP1. Pouţití IB3 algoritmu nedopadlo dobře na

datech Ecoli a Glass, ale algoritmus dosáhl nejvyšší klasifikace ze všech na datech EKG,

Ionosphere a Mandarinky. Redukovaná mnoţina CNN algoritmem nebyla dobře klasifikována

na datech Ionoshpere a Mandarinky. Opět se ukazuje, ţe je CNN algoritmus citlivý na velké

mnoţství atributů. RNN algoritmus dosahuje horších výsledků neţ CNN algoritmus, jen na

datech Ionosphere byla jeho redukovaná mnoţina dat znatelně lepší. Algoritmus DROP3

nedosahoval na většině dat převratných výsledků. Jen na datech Glass byla jeho redukovaná

mnoţina klasifikována lépe neţ původní trénovací mnoţina. Redukovaná mnoţina

algoritmem Prototypy nebyla klasifikována stejně či lépe neţ úplná trénovací mnoţina na

ţádných datech, stejně jako redukovaná mnoţina algoritmem RNN.

Neuronová síť GAME s alternativním nastavením

Při učení jednotlivých neuronů v neuronové síti GAME se nemusí pouţívat celá

trénovací mnoţina. Pokud je trénovací mnoţina příliš velká, z časových důvodů se pro

trénování kaţdého neuronu znovu náhodně vybere předem daný počet instancí z trénovací

mnoţiny a pouţijí se pro učení neuronu. Ve standardní konfiguraci, která byla pouţita

v předchozích částech, je velikost trénovací mnoţiny pro jednotlivé neurony nastavena na 200

instancí. Toto nastavení bylo pouţito z časových důvodů. Pro ilustraci jsem ale provedla

jeden experiment s neomezenou velikostí trénovací mnoţiny pro jednotlivé neurony, ostatní

nastavení jsem nechala stejná. Pro tento experiment jsem si vybrala data s největším počtem

instancí – EKG, kde budou rozdíly nejlépe vidět.


82

Tabulka 7: Neuronová síť GAME s alternativním nastavením

EKG Data Alternativní nastavení

Původní nastavení Změna času

Algoritmy Editace Počet instancí

Acc [%]

Time [ms]

Acc [%]

Time [ms]

[%]

Full data --- 5000 94,2 403124 93,7 259051 155,6

CNN AllKNN 135 93,4 15437 93,7 16409 94

RNN AllKNN 95 87 12081 87 13188 91,6

IB3 ENN 824 94 74882 93,9 54482 137,4

DROP3 ENN 255 88,4 31596 88,3 31672 99,8

Prototypy AllKNN 427 93,5 43560 93,3 29175 149,3

Chen ENN 550 93,7 57026 93,7 38590 147,8

RSP1 ENN 550 93,8 47085 93,9 36780 128

RSP3 AllKNN 197 93,8 25954 92,5 24124 107,6

Z výsledků viz Tabulka 7 je vidět, ţe přesnosti modelů se téměř neliší. Čili změna

velikosti trénovací mnoţiny pro jeden neuron se nijak neprojeví na přesnosti.

Naproti tomu změna doby potřebné k vytvoření modelů je v některých případech

značná. U kondenzačních metod RNN, CNN, DROP3 a RSP3 opět nejsou ţádné podstatné

změny. Největší změna je vidět u kondenzační metody RNN, kde došlo ke zkrácení

průměrného času potřebného k postavení sítě o 8,6%. U ostatních kondenzačních metod jsou

změny ještě menší. Tyto změny jsou způsobeny náhodným procesem tvorby sítě a jsou na

hranici statistické rozlišitelnosti.

U trénovacích mnoţin redukovaných ostatními kondenzačními algoritmy jsou ale

změny daleko výraznější. Nejmenší změna času je u algoritmu RSP1, kde došlo k nárůstu

času potřebného k tvorbě sítě o 28%. U kondenzačního algoritmu IB3 se v novém nastavení

čas prodlouţil o 37% původního času. Mnoţiny redukované kondenzačními algoritmy Chen a

Prototypy potřebují k vytvoření sítě o polovinu delší čas, neţ v původním nastavení. Dle

očekávání je největší nárůst u plné trénovací mnoţiny – konkrétně na 155,6% původního

času.

Důvodem pro tyto výsledky je fakt, ţe kondenzační algoritmy RNN, CNN, DROP3 a

RSP3 produkují trénovací mnoţiny, které obsahují méně neţ 200 instancí (nebo o málo více)

a nastavení maximální velikosti trénovací mnoţiny pro jeden neuron se neprojeví. Ostatní

kondenzační algoritmy ponechávají v trénovací mnoţině více instancí. V původním nastavení

se pak při učení jednotlivých neuronů automaticky vybere pouze část instancí a učení je pak

rychlejší. V alternativním nastavení k automatickému výběru nedochází a učení pak trvá déle.

Poněkud mě překvapuje, ţe učení s plnou trénovací mnoţinou se prodlouţilo jen o 55%, tedy

stejně jako mnohem menší, kondenzované, mnoţiny. Pro tento fakt, ale nemám vysvětlení.


83

8.5 Testování úspěšnosti algoritmu MergeAllInstances

Při testování úspěšnosti jednotlivých algoritmů klasifikátorem 1 – NN a nerunovou sítí

GAME jsem se rozhodla navrhnout vlastní redukční algoritmus. Vyšla jsem z faktu, ţe

implementované kondenzační algoritmy sice markantně redukují velikost trénovací mnoţiny,

ale ne vţdy dokáţí zaručit stejnou či lepší klasifikační přesnost, které je dosaţeno

s neredukovanými daty. Zkusila jsem tedy nad původní trénovací mnoţinou spustit všechny

neadaptivní algoritmy (CNN, RNN, IB3 a DROP3), kdy si kaţdý z nich nejprve trénovací

mnoţinu upraví zvoleným editačním algoritmem viz kapitola x, a získané redukované

mnoţiny jednotlivých algoritmů spojit do jedné výsledné redukované mnoţiny. Tímto

způsobem sice sniţuji redukční stupeň, ale očekávám zajištění vyšší klasifikační přesnosti na

většině dat.

U jednotlivých algoritmů jsem nastavila stejné parametry, jako jsem pouţila při jejich

testování. Parametr počet nejbliţších sousedů u algoritmu CNN a RNN jsem nastavila na 1.

U algoritmu IB3 jsem meze spolehlivosti nastavila na 0,7 a 0,9 a prvotní náhodný výběr na

0,2. Počet nejbliţších sousedů u algoritmu DROP3 jsem nastavila na 3.

8.5.1 MergeAllInstances

Klasifikátor 1 – NN

Pro porovnání výsledků vlastního algoritmu s výsledky všech implementovaných

kondenzačních algoritmů vycházím z následující tabulky viz Tabulka 8. Algoritmy testuji na

uměle vytvořených datech. Zvolené editační algoritmy jsou opět vypsány ve sloupci Editace.

U klasifikátoru 1 – NN porovnám vlastnosti přesnost klasifikace (sloupec Acc[%]) a redukční

stupeň (sloupec Size[%]) jednotlivých trénovacích mnoţin, kdy jako první uvádím výsledky

úplné trénovací mnoţiny (Full data).

Tabulka 8: Porovnání vlastního kondenzačního algoritmu, 1 – NN klasifikátor



Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Acc [%]

Size [%]

Full data --- 92,6 0,0 100,0 0,0 96,0 0,0 98,8 0,0

CNN AllKNN 92,6 93,1 96,6 86,8 92,4 88,1 97,7 91,8

RNN AllKNN 93,2 94,0 98,9 89,1 55,1 91,1 97,7 93,0

IB3 ENN 88,5 80,7 87,6 82,0 90,3 76,9 95,3 81,5

DROP3 ENN 98,0 75,8 97,7 62,3 97,0 61,8 99,2 73,3

Prototypy AllKNN 91,9 91,1 98,9 87,5 93,1 86,7 96,5 88,9

Chen ENN 93,9 86,9 94,4 84,2 44,9 83,8 96,5 84,0

RSP1 ENN 93,9 86,9 100,0 78,5 47,2 83,8 93,0 84,0

RSP3 AllKNN 93,2 88,5 100,0 77,5 46,1 86,7 94,2 87,2

MergeAll --- 97,8 72,5 99,7 53,2 96,8 59,8 99,2 65,0


84

U algoritmů Chen a RSP1 jsem pro jednotlivá data nastavila následující velikost


Zuby 60

Dvě E 50

Šachovnice 140

Whirpool 40

Na datech Zuby algoritmus MergeAllInstances dosahuje velmi dobré klasifikační

přesnosti, která je o 5,2% vyšší neţ při pouţití úplné trénovací mnoţiny. Více úspěšný je

ovšem algoritmus DROP3, který má klasifikační přesnost o 0,2% vyšší. MergeAllInstances

ponechává ze všech pouţitých redukčních algoritmů největší mnoţinu, redukuje o 75,5%.

Na datech Dvě E byl algoritmus MergeAllInstances také úspěšný. Jeho klasifikační

přesnost je 99,7% coţ je o 0,3% méně neţ při pouţití původní trénovací mnoţiny. Redukční

stupeň má poměrně nízký pouze 53,2%. Podotýkám, ţe algoritmy RSP1 a RSP3 dosáhly

klasifikační přesnosti 100% a navíc redukovaly přes 77,5% původních dat. Na druhé straně

klasifikační přesnost MergeAllInstances jen na datech Dvě E vyšší neţ přesnost DROP3

algoritmu.

Na datech Šachovnice má algoritmus MergeAllInstances také vyšší klasifikační

přesnost neţ při pouţití úplných dat a to o 0,8%. Redukční rate má 59,8%. Redukovaná

mnoţina algoritmem DROP3 je při klasifikaci 1 – NN algoritmem opět úspěšnější, ale pouze

o 0,2%. Navíc redukuje o 2% více dat.

Na datech Whirpool má algoritmus MergeAllInstances nejlepší úspěch. Dosahuje

nejvyšší klasifikační přesnosti. Stejné klasifikační přesnosti dosáhl i algoritmus DROP3, který

ale opět redukuje větší počet instancí a to o 8,3% více neţ algoritmus MergeAllInstances.

Vlastní algoritmus MergeAllInstances sice nedosahuje na všech datech nejlepší

klasifikační přesnosti, ale byl úspěšný na všech datech. Jen na datech Dvě E nedosáhl stejné

či vyšší klasifikační přesnosti, která byla dosaţena s pouţitím úplné trénovací mnoţiny.

Hlavní nevýhodou MergeAllInstances algoritmu oproti ostatním redukčním metodám je, ţe

redukuje s nejniţším redukčním stupněm.


Pro porovnání výsledků vlastního algoritmu s výsledky všech implementovaných

kondenzačních algoritmů vycházím z následující tabulky viz Tabulka 9. U Neuronové sítě

GAME jsem porovnávala vlastnosti přesnost klasifikace (sloupec Acc[%]) a čas potřebný na

vytvoření modelu (sloupec Time[%]), kdy jako první uvádím výsledky s pouţitím úplné

trénovací mnoţiny (Full data).


85

Tabulka 9: Porovnání vlastního kondenzačního algoritmu, neuronová síť GAME



Time [ms]

Acc [%] Time [ms]

Acc [%] Time [ms]

Acc [%] Time [ms]

Full data --- 91,8 43520 74,1 26147 81,2 90728 84,1 26150

CNN AllKNN 73,6 2588 89,9 3617 50,1 5621 81,4 1963

RNN AllKNN 68,2 2353 98,8 3753 58,1 5159 74,4 1375

IB3 ENN 82,4 8226 69,6 7101 76,1 36239 95,5 5768

DROP3 ENN 82,4 15216 98,9 12285 69,3 23333 96,5 6855

Prototypy AllKNN 83,7 4265 83,1 4413 63,1 7978 90,7 2793

Chen ENN 87,1 6031 82 4918 70,0 14038 89,5 4610

RSP1 ENN 85,1 6284 86,5 7556 66,0 15430 93,0 4826

RSP3 AllKNN 85,8 6123 95,5 8780 68,2 9161 86,0 3226

MergeAll --- 83,8 14530 97,8 19396 73,6 24966 98,8 10425


mnoţiny, jako jsem nastavila u testování klasifikátoru 1 – NN na uměle vytvořených datech

viz výše.

Na datech Zuby algoritmus MergeAllInstances s pouţitím neuronové sítě GAME

nedosahuje tak dobrých výsledků jako s klasifikátorem 1 – NN. Jeho klasifikační přesnost je

niţší neţ klasifikační přesnost s pouţitím úplné trénovací mnoţiny. Ovšem zvyšuje nejvyšší

klasifikační přesnost dosaţenou neadaptivními algoritmy o 1,4%. Adaptivní algoritmy Chen,

RSP1 a RSP3 byly na datech Zuby úspěšnější. Čas na vybudování sítě je s pouţitím

MergeAllInstances algoritmu třikrát rychlejší neţ s pouţitím úplných dat.

U dat Dvě E dosahuje o 23,7% vyšší klasifikační přesnosti oproti pouţití původní

mnoţiny. Vyšší klasifikační přesnosti dosáhly neadaptivní algoritmy DROP3 a RNN.

S redukovanou trénovací mnoţinou MergeAllInstances algoritmem je proces učení urychlen

pouze 1,4 krát. Za to redukovaná trénovací mnoţina algoritmem RNN urychluje učící proces

Navíc algoritmus MergeAllInstances urychluje budování sítě 7 krát.

Na datech Šachovnice se sloţitou rozhodovací hranicí dosáhl MergeAllInstances

algoritmus výborného výsledku. Sice je jeho klasifikační přesnost o 7,6% niţší neţ s pouţitím

úplné trénovací mnoţiny dat, ale je to druhá nejvyšší klasifikační přesnost dosaţená

s pouţitím redukovaných dat. Nejvyšší klasifikační přesnosti dosáhl algoritmus IB3, jehoţ

přesnost je o 2,5% vyšší neţ přesnost MergeAllInstances algoritmu. Neuronové síti GAME

však trvalo vytvoření sítě delší dobu s redukovanou mnoţinou IB3 algoritmu neţ

s redukovanou mnoţinou algoritmu MergeAllInstances.

Na datech Whirpool dosáhl MergeAllInstances algoritmus nejvyšší klasifikační

přesnosti, která je o 14,7% vyšší neţ při učení s neredukovanou trénovací mnoţinou. Čas na

vybudování sítě zkracuje MergeAllInstances algoritmus 2,5 krát. Algoritmus IB3, který

dosahuje klasifikační přesnosti o 3,3% niţší, zkracuje čas učícího procesu 4,5 krát.


86

Z výsledků neuronové sítě na uměle vytvořených datech taktéţ vyplývá, ţe

MergeAllInstances algoritmus sice na všech datech dosahuje dobré klasifikační přesnosti, ale

oproti ostatním redukčním algoritmům je jeho redukovaná mnoţina větší a tudíţ tolik

nezkracuje proces výstavby sítě.

8.6 Testování vlivu na rozdělení dat

V této části popisuji vliv redukčních metod na statistické vlastnosti dat. K tomu jsem si

vygenerovala speciální data se zadanými statistickými vlastnostmi. Pro jednoduchost jsem

pouţila dvě třídy dvou dimenzionálních dat vygenerovaných s normálním rozdělením, viz

Obrázek 37. Toto rozdělení jsem zvolila také proto, ţe mohu pouţít dobře známé statistické

testy pro normální rozdělení. V datech musí být přítomny dvě třídy, protoţe redukční metody

vyţadují přítomnost alespoň dvou různých tříd. Rozhodla jsem se testovat shodu střední

hodnoty a rozptylu originálních a redukovaných dat. Nulová hypotéza tedy bude shoda

středních hodnot.

𝐻0: 𝜇𝑋 = 𝜇𝑌

Pro shodu střední hodnoty pouţívám test o shodě středních hodnot výběrů normálního

rozdělení, bez známých rozptylů, neboť předpokládám, ţe redukční metody mohou změnit

rozptyl. Tabulka 10 obsahuje p-hodnoty statistiky. Čím je tato hodnota menší, tím jsou střední

hodnoty výběrů podobnější. Hladinu významnosti jsem zvolila 𝛼 = 5%. Protoţe počet stupňů

volnosti je u všech testovaných dvojic zhruba stejný a relativně vysoký, zvolila jsem kvantyl

odpovídající hodnotě statistiky s nekonečně mnoha stupni volnosti 𝑡0,975 (+∞) = 1,96.

V tabulce viz Tabulka 10 jsou p-hodnoty jednotlivých testů. Tučně jsem označila

metody, u kterých zamítám nulovou hypotézu a mohu konstatovat, ţe střední hodnoty se liší.

Střední hodnoty se liší zejména v ose X. Obrázek 39 ilustruje na mnoţině redukované

algoritmem CNN, důvody tohoto výsledku. Redukční algoritmy redukují instance daleko od

rozhodovací hranice a tedy zejména instance, vzdálené po ose X, čímţ značně posouvají

střední hodnotu směrem k rozhodovací hranici. Protoţe rozhodovací hranice je rovnoběţná

s osou Y, jsou instance v této ose redukovány rovnoměrně a k ţádnému většímu posunu

nedochází. Ještě bych chtěla upozornit na redukční algoritmus IB3, jehoţ výsledek je

zobrazen na obrázku viz Obrázek 38 a který dobře zachovává statistické vlastnosti.

V dolní části tabulky jsou uvedeny výsledky editačních algoritmů, které ale nejsou příliš

překvapivé. Z dat vypouštějí zejména šumové instance, kterých ovšem v těchto datech není

mnoho a proto nemohou střední hodnotu příliš ovlivnit.

Výsledky pro test shody rozptylů jsem opět pouţila standardní test shody rozptylu

výběrů z normálního rozdělení. Výsledky testování shody rozptylu ukazují stejné závěry a

mají stejné příčiny jako výsledky testování střední hodnoty a bylo by zbytečné je zde uvádět.


87

Tabulka 10: Porovnání statistických vlastností

Obrázek 37: Původní data s normálním rozdělením Obrázek 38: Data redukovaná algoritmem IB3

Obrázek 39: Data redukovaná algoritmem CNN

Osa X Osa Y

Třída 1 Třída 2 Třída 1 Třída 2

CNN 6,2 -7,5 -1,1 -1,6

RNN 6,1 -6,2 -1,3 -0,7

IB3 -0,1 0,4 1,1 1,7

DROP3 5,4 -5,4 0,1 -0,8

Prototypy 5,6 -5,1 0,2 -0,2

Chen 0,5 -2,8 0,4 -0,7

RSP1 0,5 -2,7 0,4 -0,6

RSP3 6,5 -6,1 0,3 0,1

Editační algoritmy

ENN -0,2 0,4 0 0,1

All KNN -0,1 0,5 0 0,1


88

8.7 Shrnutí dosažených výsledků

Před porovnáváním implementovaných algoritmů jsem na uměle vytvořených datech

testovala vliv editačních algoritmů na klasifikační přesnost algoritmů kondenzačních.

K testování klasifikace kondenzovaných mnoţin jsem pouţila 1 – NN klasifikátor, na kterém

správnost kondenzačních algoritmů porovnává většina autorů, a neuronovou síť GAME, pro

kterou jsem všechny zmiňované algoritmy implementovala. Zjistila jsem, ţe na většině uměle

vytvořených dat vykazovaly všechny kondenzační algoritmy lepších výsledků s pouţitím

editované trénovací mnoţiny, neţ s pouţitím původní trénovací mnoţiny. Pro kaţdý

kondenzační algoritmus jsem zvolila editační algoritmus, se kterým dosahoval nejlepších

výsledků.

K porovnání vlivu implementovaných algoritmů na klasifikaci 1 – NN klasifikátoru a

neuronové sítě GAME jsem pouţila uměle vytvořená data a data reálná. Všechny

kondenzační algoritmy, mimo algoritmu DROP3, který ve vlastní implementaci pouţívá

editační algoritmus ENN, testuji na editované mnoţině zvoleným editačním algoritmem.

Implementované kondenzační algoritmy byly na uměle vytvořených datech lépe

ohodnoceny klasifikátorem 1 – NN. Kdy na všech datech alespoň některý z kondenzačních

algoritmů dosahoval stejné nebo vyšší klasifikační přesnosti neţ byla dosaţena s pouţitím

neredukované mnoţiny. Klasifikační přesnosti stejné či vyšší neţ při pouţití neredukované

trénovací mnoţiny na neuronové síti GAME nedosáhly na datech Zuby a Šachovnice ţádné

kondenzační algoritmy.

Na umělých datech dosáhnul u obou klasifikátorů největšího úspěchu algoritmus

DROP3. Niţší klasifikační přesnost, neţ při pouţití původních dat, měl pouze na datech Dvě

E a Whirpool. Přitom nejméně zredukoval 74,5% původních dat a tudíţ značně urychlil

proces učení neuronové sítě GAME. Vynikajících výsledků dosáhly také u obou klasifikátorů

adaptivní regulovatelné algoritmy Chen a RSP1 a adaptivní algoritmus RSP3. Jejichţ

redukční rate je okolo 80% velikosti původní mnoţiny. Všechny tyto redukční metody měly

značné problémy s daty Šachovnice, kdy jejich redukované mnoţiny nebyly pro klasifikátoru

pouţitelné. Algoritmus IB3 taktéţ dosáhl podobných výsledků u obou klasifikátorů. Nízkou

klasifikační přesnost měl na datech Zuby a Dvě E. Rozdílné výsledky na obou klasifikátorech

měl algoritmus Prototypy. Zatímco u 1 – NN klasifikátoru jeho klasifikační přesnost neklesla

pod 93,1%, na neuronové síti neuspěl na datech Dvě E a Šachovnice. Ke klasifikačnímu

rozporu dochází také při pouţití algoritmů CNN a RNN. U klasifikátoru 1 – NN jsou mnoţiny

redukované CNN a RNN algoritmem ohodnoceny na všech datech lépe neţ 91%. Neuronová

síť s redukovanými mnoţinami algoritmy RNN a CNN dosáhla dobrých výsledků jen na

datech Dvě E.

Implementované kondenzační algoritmy měly na reálných datech podobnou úspěšnost

při klasifikaci 1 – NN klasifikátorem a neuronovou sítí GAME. Klasifikátor 1 – NN měl

největší potíţe s kondenzovanými mnoţinami na datech Mandarinky a neuronová sítě měla

problémy s kondenzovanými mnoţinami na datech s vysokým počtem atributů Ionosphere.


89

Na reálných datech měly největší úspěch regulovatelné algoritmy Chen a RSP1 a to u

obou klasifikačních metod. Jistě na tom hraje roli správná volba redukčního stupně, který je u

některých dat potřeba volit aţ o 20% niţší neţ dosahují ostatní kondenzační algoritmy. I

v tomto případě je však vyšší neţ 60%. Algoritmus RSP3 dosahoval s pouţitím 1 – NN

klasifikátoru také vysoké přesnosti na všech datech kromě dat Mandarinky. U neuronové sítě

jeho klasifikační přesnost byla dobrá, ale měl špatné výsledky na datech Glass a Mandarinky.

Algoritmus IB3 také nezůstal pozadu a jeho hodnocení 1 – NN klasifikátorem je vyjma dat

Mandarinky také velmi slušné. Za to při klasifikaci neuronovou sítí GAME dosáhl velmi

špatných výsledků na datech Ecoli a Glass. Algoritmus Prototypy má taktéţ na obou

klasifikátorech dobré hodnocení. I kdyţ stejné nebo vyšší klasifikační přesnosti, neţ je

získána s pouţitím úplné trénovací mnoţiny, dosáhl pouze u klasifikátoru 1 – NN na datech

EKG. Výsledky algoritmu DROP3 jsou o proti pouţití kondenzačních algoritmů na uměle

vytvořených datech podstatně horší. Výborné klasifikační přesnosti u obou klasifikátorů

dosahuje pouze na datech Glass a Ionosphere. Na ostatních datech je jeho klasifikační

přesnost v porovnání s ostatními algoritmy průměrná. CNN a RNN algoritmy měly při

hodnocení oběma klasifikátory problémy s daty Ionosphere a Mandarinky, jinak dosahovaly

vysoké klasifikační přesnosti. Algoritmus RNN měl téměř na všech datech vyšší redukční

stupeň, ale jeho klasifikační přesnost byla niţší.

Dále jsem testovala na umělých datech vlastní algoritmus MergeAllInstances. Tento

algoritmus dosahoval sice na všech datech s pouţitím obou klasifikačních metod vysoké

klasifikační přesnosti, ale oproti ostatním redukčním algoritmům je jeho redukovaná mnoţina

větší a tudíţ tolik nezkracuje proces výstavby sítě.

Experiment se statistickým vyhodnocením výsledků ukazuje, ţe většina redukčních

metod nezachovává statistické vlastnosti. Důvodem je, ţe kondenzační metody většinou

zanechávají instance blízko rozhodovací hranice. Tím potlačují instance leţící dál od

rozhodovací hranice a mění tak statistické vlastnosti – například pro normální rozdělení

střední hodnotu a rozptyl.

Zhodnocení

90

Část V – Závěr

Poslední část, která obsahuje zhodnocení výsledků této práce. Její přínosy a nápady na

budoucí pokračování a vylepšení.

9. Zhodnocení

Podstatnou část práce jsem věnovala redukční části fáze předzpracování dat v procesu

dobývání znalostí. Konkrétně problematice aplikovaných technik početní redukce dat. Tyto

metody zmenšují počet instancí v trénovací mnoţině, ale při tom zachovávají integritu

původních dat. Sníţení počtu instancí původních dat sniţuje pamětové poţadavky a rapidně

zvyšuje rychlost učícího procesu a klasifikace, přičemţ zachovává či dokonce vylepšuje

přesnost klasifikace.

V teoretické části jsem prozkoumala problematiku data miningové úlohy klasifikace

s narůstajícím mnoţstvím dat. Pozornost jsem věnovala klasifikátoru 1 – NN, který ke

klasifikaci pouţívá úplnou trénovací mnoţinu. Dále jsem se zabývala neuronovou sítí GAME.

V další části jsem představila metody početní redukce dat pouţívané v obou po sobě jdoucích

krocích redukce – editaci a kondenzaci. Editační metody se zaměřují na odstranění instancí,

které mohou ohrozit přesnost klasifikace. Metody kondenzační odstraňující instance, které

neovlivňují výslednou rozhodovací hranici. Přičemţ větší pozornost jsem věnovala

algoritmům kondenzačním, které sniţují paměťové poţadavky a čas potřebný na vytvoření

modelu či klasifikaci trénovací mnoţiny.

V rámci své práce jsem do projektu FAKE GAME implementovala 4 neadaptivní

algoritmy (CNN, RNN, IB3, DROP3) a 4 adaptivní algoritmy (Prototypy, Chen, RSP1,

RSP3). Dále jsem navrhla a do projektu FAKE GAME implementovala vlastní neadaptivní

algoritmus, nazvaný MergeAllInstances. Také jsem implementovala 2 editační algoritmy

(ENN, All k – NN), které jsou nezbytné pro správnou funkčnost kondenzačních algoritmů.

Pro testování správnosti a efektivnosti mnou implementovaných metod jsem zvolila 10

různých dat. Nejprve jsem své metody testovala na 4 umělých datech, která jsem vytvořila.

Dále jsem pouţila 6 vybraných reálných problémů. Mnou navrţený kondenzační algoritmus

jsem z časových důvodů testovala pouze na umělých datech.

K porovnání klasifikační přesnosti jednotlivých algoritmů jsem pouţila dva klasifátory

1 – NN a neuronovou síť GAME. U neuronové sítě jsem, kromě přesnosti výsledné sítě,

sledovala čas potřebný k vybudování sítě.

Při testování vlivu editačních algoritmů na funkčnost kondenzačních algoritmů jsem

zjistila, ţe všechny kondenzační algoritmy dosahují lepších výsledků s pouţitím editované

mnoţiny. Proto jsem pro kaţdou kondenzační metodu vybrala nejvhodnější editační metodu.

V dalším testování jsem pak jiţ pouţívala kondenzační metody jen s vybranou editační

metodou.

Zhodnocení

91

Mé výsledky ukazují, ţe nejlepších výsledků na reálných i umělých datech dosahovaly

algoritmy Chen a RSP1 se zvolenou editační metodou ENN. U těchto algoritmů je navíc

moţné ovlivnit velikost výsledné redukované mnoţiny. Ve většině případů, při pouţití

mnoţin redukovaných těmito algoritmy, oba klasifikátory dosahovaly vyšší přesnosti na

testovacích datech, neţ jaká byla dosaţena při pouţití původní trénovací mnoţiny. Navíc obě

redukční metody podstatně sníţily čas potřebný k vytvoření modelu sítě. Mnou navrţený

algoritmus AllMergeInstances na většině umělých dat dosahoval velmi dobré klasifikační

přesnosti, ale oproti ostastním redukčním metodám byla výsledná mnoţina větší.

Také jsem prozkoumala, jak kondenzační metody zachovávají statistické vlastnosti

redukovaných mnoţin. Pro tento test jsem vygenerovala speciální data s normálním

rozdělením a známými statistickými vlastnostmi. Normální rozdělění jsem zvolila kvůli

pouţití známých statistických testů.

V tomto experimentu jsem zjistila, ţe většina redukčních metod nezachovává statistické

vlastnosti. Důvodem je strategie kondenzačních algoritmů, tj. zachovávání instancí blízko

rozhodovací hranice. Instance vzdálenější jsou potlačeny a díky tomuto nerovnoměrnému

zahazování instancí se měmí statistické vlastnosti dat.

Všechny cíle definované v zadání práce jsem splnila. Nad rámec zadání jsem

implementovala klasifikátor 1 – NN, který jsem pouţila k porovnání kvality redukčních

algoritmů, stejně jako jej pouţívá většina autorů. Dále jsem navrhla, implementovala a

otestovala vlastní redukční algoritmus nazvaný MergeAllInstances.

9.1 Náměty pro budoucí práci

V budoucnu by jistě bylo dobré prozkoumat větší mnoţství editačních algoritmů, které

slouţí k filtrování rušivých instancí a instancí leţících na rozhodovací hranici. Tyto algoritmy

implementovat a otestovat jejich vliv na všechny implementované kondenzační algoritmy.

Dále by bylo dobré otestovat vlastní algoritmus AllMergeInstances také na reálných

problémech a vyzkoušet různé permutace s neadaptivními algoritmy, které pouţívá.

Literatura a zdroje

92

Literatura a zdroje

[1] KUBKA, Karel. Data Mining moţnosti a pouţití. Informační systémy pro výrobu.

2002.

[2] ZELEN, Jindřich. Java Data Mining (JDM).

[http://nb.vse.cz/~zelenyj/it380/eseje/xneba01/JDMPrace.htm]. 2005.

[3] BERKA, Petr. Proces dobývání znalostí.

[http://euromise.vse.cz/kdd/index.php?page=proceskdd]. Aplikace systému KDD.

2001.

[4] PAVLÍČEK, Miloslav. Modul pro automatické předzpracování dat. Diplomová práce.

České vysoké učení technické v Praze. 2008.

[5] CRISP Data mining industry standard. [http://www.crisp-dm.org/]. 2003.

[6] VALA, Tomáš. Rozpoznání SPZ z jednoho snímku. Diplomová práce. Univerzita

Karlova v Praze. 2006.

[7] WILSON, D. Randall, MARTINEZ, R. Tony. An integrated instance-Based learning

algorithm. Computational Intelligence. 2000.

[8] TRILOBYTE. Neuronová síť.

[http://www.trilobyte.cz/QC-Expert/Neuronova-sit.html]. Statistical software. 2009.

[9] SAIDL, Jan. Vizualizace jako nástroj studia chování modelu přírodních systémů. In

Diplomová práce. České vysoké učení technické v Praze. 2006.

[10] LOZANO, M. Tereza. Data Reduction Techniques in Classification Processes. PhD.

Thesis. Universitat Jaume I, Castellón. 2007.

[11] SÁNCHEZ, J. S., BARANDELA, R., and FERRI, F. J. On Filtering the Training

Prototypes in Nearest Neighbour Classification. CCIA. 2002.

[12] WILSON, D.L. Asymptotic Properties Of Nearest Neighbor Rules Using Edited Data.

IEEE Transactions on Systems. Man and Cybernetics. 1972.

[13] TOMEK, IVAN. An Experiment With The Edited Nearest-Neighbor Rule. IEEE

Transactions on Systems. Man and Cybernetics. 1976.

[14] HART, P.E. The Condensed Nearest Neighbour Rule. IEEE Transactions on

Information Theory. 1968.

[15] GATES, G.W. The Reduced Nearest Neighbour Rule. IEEE Transactions on

Information Theory. 1972.

[16] AHA, D.W., KIBLER, D., ALBERT, M.K. Instance-Based Learning Algorithms.

Machine Learning. 1991.

Literatura a zdroje

93

[17] DASARATHY, B.V. Minimal Consistent Set (MCS) Identification for Optimal

Nearest Neighbor Decision Systems Design. IEEE Transactions on Systems. Man and

Cybernetics. 1994.

[18] WILSON, D. R., MARTINEZ, T.R. Reduction Techniques For Instance-Based

Learning Algorithms. Machine Learning. 2000.

[19] CHANG, Chin-Liang. Finding Prototypes For Nearest Neighbor Classifiers. IEEE

Transactions on Computers. 1974.

[20] CHEN, C. H., JOZWIK, Adam. A sample set condensation algorithm for the class

sensitive artificial neural network. 1996.

[21] SÁNCHEZ, J. S. High training set size reduction by space partitioning and prototype

abstraction. 2003.

[22] WILSON, D. Randall, MARTINEZ, R. Tony. Reductions Techniques for Instance-

Based Learning Algorithms. 2000.

[23] VICTOR, José. Ship noise classification. Dissertation. New University of Lisbon.

2002

[24] ŠNOREK, Miroslav. Neuronové sítě a neuropočítače. Vydavatelství ČVUT. 2002.

[25] FRENI, Biagio. MARCIALIS, Gian Luca. ROLI, Fabio. Template Selection by

Editing Algorithms: A Case Study in Face Recognition. University of Cagliari. 2008.

[26] SAVCHENKO, Sergei. Applications of Proximity Graphs.

[http://cgm.cs.mcgill.ca/~godfried/teaching/projects.pr.98/sergei/project.html]. Pattern

Recognition. 1998.

[27] Projekt FAKE GAME na sourceforge. [http://sourceforge.net/projects/fakegame/].

Seznam pouţitých zkratek

94

A Seznam použitých zkratek

CNN Condensed Nearest Neighbor Rule

CRISP – DM CRoss-Industry Standard Process for Data Mining

CS Condensed Set

CSV Comma Separated Values

DM Data Mining

DROP3 Decremental Reduction Optimization Procedure 3

ENN Edited Nearest Neighbor Rule

ES Edited Set

GAME Group of Adaptive Models Evolution

GMDH Group Method of Data Handling

IB3 Instance Based learning algorithm 3

k – NN k – Nearest Neighbours

KDD Knowledge Discovery in Databases

RNN Reduce Nearest Neighbor Rule

RSP1 Reduction by Space Partition 1

RSP3 Reduction by Space Partition 3

TS Trénovací mnoţina

Výsledky redukce umělých dat

95

B Výsledky redukce umělých dat

Data Dvě E


96


97

Data Šachovnice


98


99

Data Whirpool


100

Uţivatelská příručka

101

C Uživatelská příručka

Moduly algoritmů početní redukce dat nalezneme v projektu FAKE GAME, který je dostupný

ke staţení viz [27]. Na webu projektu FAKE GAME také nalezneme informace, jakým způsobem

stáhnout nejnovější verzi a jak ji nainstalovat.

Po spuštění aplikace FAKE GAME je potřeba v hlavním okně otevřít dialog pro předzpracování dat.

V menu data vybereme poloţku Preprocessing Dialog viz Obrázek 40.

Obrázek 40: Otevření Preprocessing dialogu

V Preprocessing dialogu je potřeba nejdříve načíst trénovací mnoţinu dat, kterou chceme

redukovat. Vstupní formát dat pro projekt FAKE GAME je zaloţen na textovém souboru s

tabulátorem oddělenými hodnotami. Na první řádce je seznam vstupních a výstupních atributů.

Jména výstupních atributů musí začínat znakem vykřičník (!). Na dalších řádcích následují hodnoty

jednotlivých instancí - na jednom řádku jedna instance. Ukázka vstupního formátu dat viz Obrázek

41. Vybereme metodu Load Raw Data v sekci Imports a stiskneme tlačítko Run viz Obrázek 42.


102

Obrázek 41: Ukázka vstupního formátu dat

Obrázek 42: Import vstupních dat

V okně Open nalezneme soubor s trénovací mnoţinou dat a kliknutím na tlačítko Open tato

data načteme viz Obrázek 43. Ještě je potřeba potvrdit, ţe první řádek obsahuje názvy atributů a

tříd.


103

Obrázek 43: Načtení trénovací mnoţiny dat

Nyní otevřeme sekci Data reduction ve které vidíme seznam všech implementovaných

kondenzačních a editačních algoritmů. Podotýkám, ţe jediný implementovaný algoritmus, který na

první pohled nemůţeme vidět, je algoritmus RSP1. Ten se spouští změnou parametru useRSP1 na

TRUE u algoritmu Chen. Nastavení parametrů a spuštění metody RSP1 si názorně předvedeme.

Pro nastavení konfigurace algoritmu Chen je potřeba označit metodu Chen a kliknout na

tlačítko Configure viz Obrázek 44.

Obrázek 44: Otevření konfigurace Chenova algoritmu


104

Zobrazí se nám Konfigurační dialog. Poţadovaný parametr můţeme měnit dvojklikem. My

nastavíme proměnnou useRSP1 na TRUE a potvrdíme tlačítkem OK viz Obrázek 45. Dále je u

metody RSP1 moţné nastavit přibliţný počet instancí (condensationSize) z původní trénovací

mnoţiny, které chceme zachovat.

Obrázek 45: Konfigurační dialog Chenova algoritmu

Pak uţ jen stačí kliknout na tlačítko Run a trénovací mnoţina je zredukována. Uloţit

redukovanou mnoţinu můţeme v sekci exports metodou Save RAW Data viz Obrázek 46. Opět po

stisknutí tlačítka Run vybereme cestu k souboru, do kterého bude redukovaná mnoţina uloţena.

Obrázek 46: Export redukované mnoţiny dat


105

Na trénovací mnoţinu je moţné nejprve aplikovat některý z implementovaných editačních

algoritmů a následně aplikovat některý z kondenzačních algoritmů.

Pomocné skripty

106

D Pomocné skripty

Zde prezentuji skripty implementované v Matlabu a interpretu příkazů Bash, které jsem pouţila

v mé diplomové práci.

Skripty pro Matlab pouţité pro vizualizaci umělých dat

plotAllData.m skript, který nalezne všechna data v aktuálním adresáři a spustí na kaţdá

data skript plotAndSave.

plotAndSave.m načte data ze zadaného souboru a spustí skript plotData.

plotData.m ze zadaných dat vytvoří XY graf a uloţí jej jako obrázek ve formátu PNG.

readData.m načte data z textového souboru a vrátí matici vstupních dat a vektor tříd,

do kterých patří jednotlivé instance.

Skripty pro Matlab pouţité pro výpočet statistických vlastností umělých dat

testDatasets.m skript, který vypočítá test shody střední hodnoty mezi původními,

neredukovanými, daty a všemi daty v aktuálním adresáři.

readData.m načte data z textového souboru a vrátí matici vstupních dat a vektor tříd,

do kterých patří jednotlivé instance.

Skripty pro Bash

compute.sh

skript pouţitý pro spouštění tvorby neuronové sítě GAME. Pro pouţití je

třeba nastavit proměnnou datasetName na jméno dat (např. DvěE nebo

Šachovnice) a do definice for cyklu vypsat všechny varianty, které se mají

spustit.

collect.sh skript pouţitý pro sběr výsledků neuronové sítě GAME. Skript nalezne

všechny soubory s výsledky sítě na testovacích datech a výsledky uloţí do

jediného souboru jménem accuacy.txt.

Obsah přiloţeného CD

107

E Obsah přiloženého CD

Na přiloţeném CD se nachází tyto soubory:

|-- src/ - zdrojové kódy

| |

| |-- fakegame/ - zdrojové kódy projektu FAKE GAME s moduly pro redukci dat

| |

| |-- kNN/ - zdrojové kódy klasifikátoru k-NN

|

|-- jar/ - přeložená verze projektu FAKE GAME

|

|-- skripty/ - skripty použité při řešení diplomové práce

|

|-- test/ - soubory použité při testování modulů

| |

| |-- testovaci/ - testovací množiny umělých i reálných dat

| |

| |-- trenovaci/ - trénovací množiny umělých i reálných dat

|

|-- text/ - text diplomové práce

|-- krkosh1_dip.pdf - text diplomové práce v pdf formátu

Návod k ovládání modulů naleznete v příloze C Uţivatelská příručka

Date post:	24-Sep-2020
Category:	Documents
Upload:	others
View:	3 times
Download:	0 times

Redukce dat pro data mining a neuronová síť...

Documents