7. Příprava dat Příprava (předzpracování) dat je nejobtížnější a časově nejnáročnější krok celého procesu dobývání znalostí z databází. Současně je to ale krok, který má klíčový význam pro úspěch dané aplikace. Je to ta část práce, která (spolu s krokem porozumění problému) vyžaduje největší podíl spolupráce s expertem z dané aplikační oblasti. Skoro lze říci, že problémy se získáním „těch správných“ dat pro učící se systémy jsou podobné problémům se získáváním znalostí u systémů expertních. Cíl předzpracování je obvykle dvojí: •
vybrat (nebo vytvořit) z dostupných dat ty údaje, které jsou relevantní pro zvolenou úlohu dobývání znalostí,
•
reprezentovat tyto údaje v podobě, která je vhodná pro zpracování zvoleným algoritmem.
Zatímco první cíl úzce souvisí s porozuměním problému i s porozuměním datům (a je tedy závislý na aplikační oblasti), druhý cíl (přizpůsobit data uvažovanému algoritmu) je relativně aplikačně nezávislý. Tato kapitola se z pochopitelných důvodů zaměřuje na druhý cíl, tedy na otázku, jak uzpůsobit data pro jednotlivé analytické procedury. Z tohoto důvodu je kapitola zařazena (v rozporu s časovým sledem procesu KDD) až za popis jednotlivých algoritmů. Při předzpracování potřebujeme znát (a tedy z hlediska knihy popsat) požadavky jednotlivých metod na podobu vstupních dat. Často může podoba dat vést k volbě metody. Přidržíme se přitom podoby, která je společná většině dříve popsaných algoritmů; reprezentaci dat pomocí jedné datové tabulky, zachycující hodnoty atributů objektů. To bude tedy cílový stav, ke kterému se budeme propracovávat při řešení dále uvedených problémů. Prostředkem k dosažení tohoto cíle budou různé metody transformace, selekce a tvorby atributů a objektů. Některé z dílčích postupů předzpracování jsme měli možnost již poznat; to jsou ty postupy, které jsou integrovány do analytických algoritmů. Zde se k nim vrátíme v širších souvislostech celé fáze předzpracování dat.
7.1
Jiná než relační data
Kromě dat uchovávaných v relačních tabulkách, u kterých nezáleží na pořadí objektů (objekty jsou navzájem nezávislé) můžeme v řadě oblastí narazit na data s určitou strukturou. K takovým datům patří •
časová data (např. časové řady kurzů akcií)
•
prostorová data (např. geografické informační systémy)
•
strukturální data (např. chemické sloučeniny)
Na opačné straně stojí naopak data nestrukturovaná, například texty. Problematice textů se věnuje samostatná kapitola.
1
Časová data jsou obvykle tvořena hodnotami téže veličiny (nebo více veličin) zaznamenávaných v různých okamžicích. Veličinou (typicky numerickou) může být kurz ceny akcií, spotřeba elektrické energie, výsledek laboratorního testu v nemocnici, transakce na účtu v bance nebo sekvence navštívených webových stránek (tzv. clickstream). Údaje tedy mohou být zaznamenávány jak v ekvidistantních časových intervalech (denní kurzy akcií1) nebo v libovolných okamžicích (návštěvy u lékaře). Obvyklou úlohou pro časová data je predikce budoucí hodnoty veličiny (např. kurzu akcií) na základě hodnot zjištěných v minulosti. Tomu odpovídá i způsob předzpracování který jsme již viděli v kapitole o neuronových sítích2. Z časové řady (Obr. 1) se postupně vybírá úsek dané délky tak, že jeho „začátek“ představuje hodnoty vstupních atributů a jeho „konec“ hodnoty cílového atributu (Obr. 2). Jiným příkladem použití (a předzpracování) časově závislých dat je situace, kdy tato data představují jen dílčí informace popisující složitější objekt. Příkladem může být úloha diagnostikování choroby mimo jiné (ale nikoliv pouze) na základě opakovaných vyšetření. Pak se sekvence výsledků téhož laboratorního testu chápe (ve vztahu k pacientovi) jako relace n:1 (viz dále).
y(t)
t0 t1 t2 t3 t4 t5 t6 t7
...
t
Obr. 1 Původní časová řada
vstupy y(t0) y(t1) y(t2) y(t3) y(t1) y(t2) y(t3) y(t4) y(t2) y(t3) y(t4) y(t5) ...
výstup y(t4) y(t5) y(t6)
Obr. 2 Časová řada po transformaci
V případě prostorových dat hraje mezi jednotlivými objekty roli implicitní relace sousednosti. Obvykle předpokládáme že hodnoty atributů u „sousedních“ objektů nebudou příliš odlišné. Většina analytických metod nedokáže tuto vazbu mezi objekty vzít do úvahy. Spíše se tedy použije při interpretaci, nebo jako dodatečné požadavky na nalezené znalosti.
1
Modernější přístup zaznamenávání dat z burzy jsou tzv. ticková (vysokofrekvenční) data. Tato data jsou zaznamenávána neekvidistantně, v okamžiku, kdy dojde k nějaké výraznější změně. Příklad analýzy takových dat lze nalézt v [Pecen a kol, 1994].
2
Jiné způsoby transformace časových řad jako např. Fourierova transformace (reprezentace časové řady ve frekvenční oblasti) nebo waveletová transformace (reprezentace časové řady pomocí skokových funkcí) přesahují rámec této knihy.
2
Příklad strukturálních dat můžeme nalézt v souvislosti s predikcí karcinogenních chemických látek 3. Pro reprezentaci organických sloučenin se používá několik způsobů. Jedná-li se např. o sloučeninu dle Obr. 3, můžeme jí zapsat pomocí tzv. SMILE kódů “ClC(Cl)Cl“ nebo jako soubor faktů v Prologu (Obr. 4). Druhá reprezentace přímo napovídá použít metody induktivního logického programování, je ale samozřejmě možný i její převod na hodnoty atributů (pak jde o problém konstrukce nových atributů a problém více vzájemně propojených tabulek). Cl Cl
C
H
Cl
Obr. 3 Příklad chemické sloučeniny
atom('TR000','TR000_1'). element('TR000_1',cl). atom('TR000','TR000_2'). element('TR000_2',c). atom('TR000','TR000_3'). element('TR000_3',cl). atom('TR000','TR000_4'). element('TR000_4',cl). atom('TR000','TR000_5'). element('TR000_5',h). bond('TR000','TR000_1_2'). connected('TR000_1','TR000_2','TR000_1_2'). connected('TR000_2','TR000_1','TR000_1_2'). bond_type('TR000_1_2',-). bond('TR000','TR000_2_3'). connected('TR000_2','TR000_3','TR000_2_3'). connected('TR000_3','TR000_2','TR000_2_3'). bond_type('TR000_2_3',-). bond('TR000','TR000_2_4'). connected('TR000_2','TR000_4','TR000_2_4'). connected('TR000_4','TR000_2','TR000_2_4'). bond_type('TR000_2_4',-). bond('TR000','TR000_2_5'). connected('TR000_2','TR000_5','TR000_2_5'). connected('TR000_5','TR000_2','TR000_2_5'). bond_type('TR000_2_5',-). Obr. 4 Reprezentace chemické sloučeniny v Prologu 3
Jedná se o úlohu navrženou pro Discovery Challenge ECML 2001. Šlo o klasifikaci látek do 4 tříd (úrovní karcinogenity) na základě jejich struktury. Podrobnější informace byly k dispozici na http://www.informatik.uni-freiburg.de/~ml/ptc/. Jiné příklady lze nalézt ve sborníku [Suzuki, 2000]. Zde šlo mimo jiné o hledání vztahů mezi podstrukturami metodami vycházejícími z algoritmu apriori.
3
7.2
Více vzájemně propojených tabulek
S výjimkou metod induktivního logického programování (ILP) potřebujeme pracovat s jednou datovou tabulkou. Operace, která umožní z jedné nebo více relací (tabulek) vytvořit relaci (tabulku) novou se v relační algebře nazývá spojení (join). Tato operace musí brát do úvahy různý typ vztahů mezi entitami ve spojovaných tabulkách. Základními typy vztahů z hlediska kardinality jsou vztah 1:1, vztah 1:n (n:1) a vztah n:m. Vztah 1:1 znamená, že jedna entita první relace je svázána s jednou entitou druhé relace. Příkladem může být relace klient(id_klienta, příjmení, jméno) a relace trvalé_bydliště(id_bydliště, id_klienta, ulice, město). Spojení těchto dvou relací do jedné je velice jednoduché, nová relace bude obsahovat sloupce (atributy) z obou původních relací, počet řádků bude (pro uvedené relace) odpovídat počtu řádků v první relaci 4. Vztah 1:n (resp. n:1) znamená, že jedna entita jedné relace je svázána s více entitami druhé relace. Příkladem může být dvojce relací účet(id_účtu, datum_založení, četnost_výpisů), trvalé_ příkazy(id_příkazu, id_účtu, částka, bankovní_spojení), nebo dvojce relací účet(id_účtu, datum_založení, četnost_výpisů), transakce(id_transakce, id_účtu, datum, částka, typ_ transakce). V tomto případě bude nová tabulka obsahovat nové atributy pro agregované hodnoty získané z n opakování údajů (trvalých příkazů, transakcí), vztahujících se k entitě na straně 1 (účtu) vztahu mezi relacemi Těmito agregovanými hodnotami (atributy) bývají (podle typu původních atributů): •
pro numerické atributy (např. částka): součet, minimum, maximum, průměr, …
•
pro kategoriální atributy (např. typ_transakce): počet různých hodnot, výskyt konkrétní hodnoty, majoritní hodnota, …
Počet řádků v nové tabulce pak bude odpovídat počtu řádků v relaci na straně „1“ (tedy např. počtu účtů). Vztah n:m znamená že několika entitám z první relace odpovídá jedna entita z druhé relace a současně několika entitám druhé relace odpovídá jedna entita první relace. Příkladem může být relace klient a relace účet; jeden klient může mít přístup k více účtům, k jednomu účtu může mít přístup více klientů. Vztah n:m se obvykle vyjadřuje pomocí další relace (pro náš případ relace dispoziční_práva) která je s původními relacemi svázána vztahem 1:n resp 1:m. Při spojování těchto tabulek budeme opět vytvářet nové atributy pro agregované hodnoty. Typ agregovaných hodnot i počet řádků ve výsledné tabulce ale bude záviset na volbě úlohy. Podle toho, zda chceme zkoumat klienty nebo účty zvolíme jednu relaci za hlavní (primární) a spojení budeme provádět vzhledem k ní. Převedeme tedy vztah n:m podle úlohy na vztah 1:m nebo n:1.
7.3
Odvozené atributy
Z atributů přítomných v původních datech lze samozřejmě vytvářet odvozené atributy. Někdy tvorbu nových atributů vyžaduje způsob předzpracování (např. atributy pro agregované hodnoty při spojování relací), jindy tvorba atributů plyne z doménových znalostí (např. převod rodného čísla klienta na věk a pohlaví). Opět se tedy jedná o operaci, kdy je třeba úzce spolupracovat s expertem.
4
Pokud k některému klientovi neexistují údaje o adrese, bude nová relace obsahovat chybějící hodnoty.
4
7.4
Příliš mnoho objektů
V reálných úlohách se setkáváme s databázemi, které obsahují desítky a stovky tisíc objektů, zvláštností nejsou ani ještě větší počty. V případě algoritmů pracujících v inkrementálním režimu žádný problém nevzniká. Jiné je to v případě algoritmů pracujících v dávkovém režimu, které předpokládají zpracování celých (trénovacích) dat naráz v operační paměti. Pro řešení tohoto problému se nabízí: •
použít jen určitý vzorek (sample) vybraný z celých dat 5,
•
použít takový způsob uložení dat, který by umožnil přístup ke všem objektům, aniž by je celé ukládal do operační paměti,
•
vytvořit více modelů na základě podmnožin objektů a modely poté zkombinovat.
Při výběru určitého vzorku se opět vynořuje otázka reprezentativnosti dat. Požadujeme totiž, aby vybrané objekty co nejlépe vystihovaly celá data6. Shodu vzorku s celými daty můžeme vyhodnocovat např. na základě shody rozdělení hodnot atributů ve vybraném vzorku i v celých datech. V praxi se často spokojíme s tím, že tuto shodu zjišťujeme pouze pro cílový atribut určující zařazení objektů do tříd. Pak je na místě dostatečně veliký náhodný výběr. Výjimku z tohoto požadavku představuje situace, kdy jsou třídy v původních datech nevyvážené. Je-li např. v celých datech podíl objektů jedné třídy 95% a objektů druhé třídy 5%, bude mít většina analytických algoritmů tendenci preferovat majoritní třídu. Nalezené znalosti by tedy měly podobu defaultu “každý objekt patří do majoritní třídy”. Často nás ale zajímají znalosti týkající se té druhé třídy. V takovém případě musíme buď vzít do úvahy různé ceny za různý typ chybného rozhodnutí 7, nebo musíme upravit trénovací data do takové podoby, kdy jedna třída nebude dominovat té druhé. Ve druhém případu budeme tedy vybírat příklady různých tříd s různou pravděpodobností (resp. vážit příklady různých tříd různými vahami) 8. Při výběru objektů do trénovací množiny se samozřejmě můžeme řídit i dalšími dodatečnými informacemi: můžeme např. vybírat typické příklady, nebo naopak atypické příklady, pouze příklady bez chybějících hodnot apod. Jistou variantou vzorkování je i křížová validace, při které se z dat opakovaně vybere jen určitá část pro trénování a jiná část pro testování (viz kapitola o evaluaci). Zde můžeme tento princip použít tak, že vytvoříme různé modely na základě různých vzorků, a pro vlastní klasifikaci použijeme model nejlepší. Příklad efektivnějšího uložení rozsáhlých dat najdeme např. v systému SPRINT pro paralelizaci vytváření rozhodovacích stromů z rozsáhlých databází [Shafer a kol, 1996]. Tento systém pracuje se samostatným souborem pro každý atribut. Záznam v souboru j je tvořen trojicí [index_objektu, hodnota_atributu_j, hodnota_cílového_atributu], záznamy jsou navíc uspořádány podle hodnoty atributu j. Tato reprezentace umožní snadno nalézt nejvhodnější větvící atribut, případně provést binarizaci atributu. Jiným příkladem je metoda GUHA, která používá tzv. karty veličin, což jsou bitové řetězce kódující zda objekt splňuje nějaký cedent [Hájek a kol.,1983]. Kombinování klasifikátorů jako způsob, jak vyřešit problém s velkým počtem objektů uvádí Chan a Stolfo [Chan, Stolfo, 1995]. Trénovací množinu lze náhodně rozdělit na N vzájemně disjunktních podmnožin. Z každé podmnožiny se vytvoří samostatný model (v uvedeném případě) rozhodovací strom. Jednotlivé stromy pak hlasují o zařazení neznámého příkladu.
5
Tato operace se v relační algebře nazývá selekce.
6
Pro úplné pokrytí prostoru atributů bychom pro n binárních atributů potřebovali 2 různých objektů.
7
Podstatně horší chybou (chybou s větší cenou) bude chybné zařazení minoritního příkladu do majoritní třídy.
8
Extrémní variantou tohoto přístupu je použít všechny příklady minoritní třídy a doplnit je náhodně vybranými příklady majoritní třídy tak, aby podíl obou tříd ve trénovacích datech byl stejný.
n
5
7.5
Příliš mnoho atributů
V reálných úlohách se setkáváme s databázemi, které obsahují desítky a stovky atributů. Ne všechny z nich jsou samozřejmě relevantní pro zamýšlenou analýzu, takže stojíme před otázkou redukce tohoto počtu. Odpověď lze hledat u experta (který může vědět, které atributy jsou pro danou úlohu relevantní), nebo v automatických metodách, které nabízejí následující dva způsoby: •
transformaci, kdy z existujících atributů vytvoříme menší počet atributů nových,
•
selekci, kdy z existujících atributů vybereme jen ty nejdůležitější 9.
Otázka redukce dimenzionality je dobře známa z oblasti rozpoznávání obrazů 10. Pro transformaci atributů se zde používá např. Karhounen Loevův rozvoj, faktorová analýza nebo analýza hlavních komponent. Tyto metody předpokládají použití výhradně numerických atributů. Základem všech uvedených metod je reprezentace objektů pomocí hodnot nových atributů, které vzniknou jako lineární kombinace atributů původních. Jistou nevýhodou těchto metod tedy je skutečnost, že potřebujeme znát (měřit) hodnoty všech původních atributů. Nové, transformované atributy navíc nemusí mít srozumitelnou interpretaci, což může být v konkrétní úloze na závadu. Při (automatizované) selekci atributů obvykle hledáme ty atributy, které nejlépe přispějí ke klasifikaci objektů do tříd. K tomuto problému můžeme přistoupit dvojím způsobem. Buď pro každý atribut spočítat nějakou charakteristiku vyjadřující vhodnost atributu pro klasifikaci (tento přístup bývá nazýván metoda filtru – filter approach), nebo použít nějaký algoritmus strojového učení pro vytvoření modelu z (pod)množiny atributů a vyhodnotit model (tento přístup bývá nazýván metoda obálky – wrapper approach). Pro metodu filtru lze použít kritéria používaná pro volbu atributu pro větvení rozhodovacího stromu (entropii nebo informační zisk), vzájemnou informaci nebo χ2 test. Tato kritéria vycházejí z kontingenční tabulky. Podobu tabulky pro (vstupní) atribut A a cílový atribut C ukazuje Obr. 5. C(v1)
C(v2)
……….
C(vS)
∑
A(v1)
a11
a12
……….
a1S
r1
A(v2)
a21
a22
……….
a2S
r2
:
:
:
:
:
:
:
:
:
:
A(vR)
aR1
aR2
……….
aRS
rR
∑
s1
s2
……….
sS
n
Obr. 5 Kontingenční tabulka pro atribut A a třídu C
kde 9
akl je četnost (frekvence) kombinace (A(vk) ∧ (C(vl))
V anglicky psané literatuře se požívá termín feature selection. V relační algebře se tento typ operace nazývá projekce.
10
6
Rozpoznávání obrazů (pattern recognition) je relativně samostatná oblast umělé inteligence, řešící úlohy klasifikace tak jak jsou popsány v této knize: Na základě trénovací množiny se hledá obecný popis tříd. Každý objekt je reprezentován numerickým vektorem příznaků (feature vector), modely používané pro klasifikaci tedy reprezentují znalosti o třídách v podobě diskriminačních funkcí nebo etalonů.
a
S
rk = ∑akl , l=1
R
sl = ∑akl ,
R
S
n = ∑ ∑ akl .
a
k=1
k=1 l=1
Uvedené četnosti lze použít pro odhad pravděpodobností: akl P(A(vk)∧C(vl)) = n ,
rk P(A(vk)) = n
sl P(C(vl)) = n
a
Příslušná kritéria jsou pak 1.
χ2 (čím větší hodnota, tím lépe) R
χ = 2
S
∑∑
(a kl − e kl )2 e kl
k =1 l =1
2.
2
entropie H(A) (čím menší hodnota, tím lépe) R
H(A) =
∑ k =1
3.
r s ⎞ ⎛ a − k l⎟ R S ⎜ kl n ⎠ = n × ∑∑ ⎝ rk s l k =1 l =1
rk H(A(v k )) , n
H(A(v k )) = -
kde
S
a kl
∑r
log
l
l =1
a kl rl
informační míra závislosti ID(A,C) (čím větší hodnota, tím lépe)
ID(A, C) =
MI(A, C) = H(C)
MI(A, C) sl s log l n l =1 n S
∑
,
kde vzájemná informace MI(A,C) je R
MI(A, C) =
P(A(v k ) ∧ C(v l )) P(A(v k ) ∧ C(v l )) log = P(A(v k )) P(C(v l ) l =1 S
∑∑ k =1
=
1 n
R
S
∑∑ a k =1 l =1
kl
log
R
S
k =1
l =1
∑∑
a kl a kl log n = rk s l n n n
n a kl . rk s l
Atributy lze uspořádat podle hodnoty kritéria; pak můžeme vybrat jen určitý počet těch nejlepších. Lze postupovat „zdola nahoru“ – tedy přidáváním atributů, nebo „shora dolů“ – tedy odstraňováním atributů z původní množiny všech atributů. Nevýhodou uvedeného způsobu selekce je, že posuzuje každý atribut zvlášť a nezachycuje současný vliv více atributů na správnost klasifikace. Vhodnější 11, ale výpočetně náročnější je místo pro jeden atribut (tedy pro všechny hodnoty tohoto atributu) počítat hodnotu kritéria pro množinu atributů (tedy pro všechny kombinace hodnot těchto atributů). Algoritmus pro selekci atributů pak bude vytvářet množiny atributů a počítat pro ně hodnoty kriteria. Podobně jako v případě individuálního posuzování 11
Není totiž pravda, že atributy, které jsou samy o sobě nejlepší (ve smyslu uvažovaného kriteria) vytvoří i nejlepší množinu.
7
jednotlivých atributů A i při posuzování množin atributů lze tyto množiny vytvářet v zásadě dvojím způsobem: „shora dolů“ (odstraňováním atributů; tzv. zpětná selekce), nebo „zdola nahoru“ (přidáním atributů; tzv. přímá selekce). Jádrem algoritmu selekce je tedy prohledávání prostoru všech podmnožin původní množiny atributů. Volba prohledávací strategie může být doplněna o určení počtu atributů, které se odstraní resp. přidají v daném kroku (jeden atribut, pevný počet atributů, proměnný počet atributů). Obšírně je tato problematika popsána v [Pudil, 2001] resp. [Pudil a kol., 1994]. Pudil uvádí různé metody výběru množiny atributů: přímá selekce s pevným počtem atributů, zpětná selekce s pevným počtem atributů, kombinovaná přímá a zpětná selekce s pevným počtem atributů, přímá selekce s proměnným počtem atributů, zpětná selekce s proměnným počtem atributů, adaptivní přímá selekce, adaptivní zpětná selekce. Ve všech případech používá jako kritérium pro hodnocení aktuální množiny informační míru závislosti. Pro množinu d atributů má toto kritérium podobu
ID((A 1 ,..., A d ), C) =
MI((A 1 ,..., A d ), C) , H(C)
kde
MI((A 1 ,..., A d ), C) =
∑ ∑ P(A ( v 1
1k
) ∧ ... ∧ A d ( v dk ) ∧ C(v l )) log
(A 1 .... A d ) C
P(A 1 ( v 1k ) ∧ ... ∧ A d ( v dk ) ∧ C(v l )) P(A 1 ( v 1k ) ∧ ... ∧ A d ( v dk )) P(C(v l ))
a
H(C) = -
S
sl
sl
∑ n log n
.
l=1
Je-li selekce atributů založena na přidávání atributů, v daném kroku se k již vybrané množině atributů A1 přidá taková množina atributů A2, že12 ID((A1 ∪ A2),C) = maxx ID((A1 ∪ Ax2),C). Je-li selekce atributů založena na odstraňování atributů, v daném kroku se z uvažované množiny atributů A1 odstraní taková množina atributů A2, že ID((A1 \ A2),C) = maxx ID((A1 \ Ax2),C).
Jiným příkladem, jak vybírat množiny atributů, je metoda obálky, která využívá (hrubé) výpočetní síly současných počítačů [John a kol, 1994]. Z množiny všech použitelných atributů se opakovaně vybírá určitá část a ta se pak použije pro popis objektů v trénovací i testovací množině. Pro každou trénovací množinu se vytvoří jeden model, který bude otestován na testovacích datech téže struktury atributů. Z takto vytvořených modelů se pak použije ten nejlepší13 – volba modelu zároveň určí relevantní atributy. Metodu obálky lze použít „zdola nahorů“ (začít od modelů vytvořených pro jednotlivé atributy a atributy postupně přidávat), „shora dolů“ (začít od modelu vtvořeného pro původní množinu atributů a atributy postupně odstraňovat), nebo pro náhodný způsob výběru podmnožiny atributů.
12
Místo informační míry závíslosti je možné použít i jiné dříve uvedené kritérium.
13
Kritériem kvality modelu je správnost klasifikace na testovacích datech.
8
7.6
Numerické atributy
Jako jisté omezení některých algoritmů dobývání znalostí se může jevit to, že pracují pouze s kategoriálními daty. Numerické atributy tedy nejprve musíme diskretizovat (rozdělit na intervaly). Někdy se diskretizace provádí v průběhu práce algoritmu 14, jindy se provádí ve fázi předzpracování dat. Diskretizace často závisí na povaze řešeného problému; na znalostech, které teprve hledáme. Je-li k dispozici expert, je lépe mu tuto diskretizaci přenechat. Existují ale i metody umožňující provádět diskretizaci automaticky. K nejjednodušším metodám patří diskretizace na předem zadaný počet ekvidistantních nebo ekvifrekventních intervalů. V prvním případě se obor hodnot numerického atributu rozdělí na stejně dlouhé intervaly (Obr. 6); stačí tedy znát jen rozsah hodnot. Ve druhém případě se obor hodnot rozdělí na intervaly, které obsahují (zhruba) stejný počet objektů (Obr. 7); tady už potřebujeme znát počty výskytu jednotlivých hodnot. V obou případech se ale numerický atribut diskretizuje bez využití informací o hodnotách jiných atributů. Jiné metody využívají při diskretizaci informací o příslušnosti objektů k různým třídám15 (Obr. 8). K nejznámějším patří algoritmus Fayyada a Iraniho [Fayyad, Irani, 1993]. Jejich přístup zobecňuje binarizaci (rozdělení hodnot numerického atributu A do dvou intervalů) používanou systémy CART nebo ID3 16 na diskretizaci do více intervalů. Schéma algoritmu je uvedeno na Obr. 9. Algoritmus rekursivně (postupem shora dolů) binarizuje aktuální interval tak, že bere do úvahy jednotlivé dělící body 17 a stanovuje: •
zda se má interval dále rozdělit,
•
pokud ano, tak který dělící bod použít
Kritérium pro toto rozhodnutí vychází z entropie. Podobně jako při tvorbě rozhodovacích stromů se zjišťuje informační zisk, v tomto případě tedy přínos rozdělení daného intervalu Int pro klasifikaci: Zisk(AInt,θ) = H(A(Int)) - H(Aθ) Entropie H(A(Int)) se tentokrát vztahuje k intervalu před binarizací, entropie H(Aθ) se vztahuje k intervalu po binarizaci, tedy T
H(A(Int)) = -
∑ t =1
n t ( A(Int)) n ( A(Int)) log t , n(A(Int)) n(A(Int))
n(A(<θ)) n(A(>θ)) H(Aθ) = n(A(Int)) H(A(<θ)) + n(A(Int)) H(A(v>θ)) přičemž n(A(Int)) je počet příkladů, které mají hodnotu atributu A z intervalu Int (případný index t označuje příklady třídy t ) a n(A(<θ)) (resp. n(A>θ)) ) je počet příkladů, jejichž hodnota atributu A je z intervalu Int a je menší (resp. větší) než θ. H(A(<θ)) (resp. H(A>θ))) je pak entropie pro příklady jejichž hodnota atributu A je z intervalu Int a je menší (resp. větší) než θ.
14
Práci s numerickými atributy v tomto smyslu jsme se věnovali v kapitolách o rozhodovacích stromech i rozhodovacích pravidlech.
15
To se samozřejmě týká klasifikačních úloh, kdy je tato informace dostupná.
16
Jde o algoritmy pro tvorbu rozhodovacích stromů popsané na jiném místě.
17
Dělící bod je obecně hodnota, ležící mezi dvěma po sobě následujícími hodnotami numerického atributu, které jsou obsaženy v datech. Pro n různých hodnot atributu A tedy existuje n-1 dělících bodů. Oba autoři ale ukázali, že stačí brát do úvahy pouze takové dělící body (tzv. hraniční), které od sebe oddělují objekty patřící do různých tříd.
9
Obr. 6 Ekvidistantní intervaly
Obr. 7 Ekvifrekvenční intervaly
Obr. 8 Diskretizace vzhledem k třídám
Interval Int lze obvykle binarizovat podle více dělících bodů. Výše uvedené kritérium informačního zisku umožňuje nalézt ten nejvhodnější. O tom, zda se interval podle tohoto dělícího bodu skutečně rozdělí pak rozhoduje kritérium, které autoři odvodili s použitím principu minimální deskripční délky (MDL). K binarizaci aktuálního intervalu Int dojde, jestliže Zisk(AInt,θ) >
log2(n(A(Int))-1) ∆A(Int, θ) + n(A(Int)) , n(A(Int))
kde ∆A(Int, θ) = log2(3k – 2) – (k∗H(A(Int)) – k1 ∗ H(A(<θ)) – k2 ∗ H(A(>θ)),
10
přičemž k je počet různých tříd pro objekty spadající do intervalu Int, k1 je počet různých tříd pro objekty v intervalu Int<θ a k2 je počet různých tříd pro interval Int>θ [Fayyad, Irani, 1993].
Algoritmus Fayyad, Irani 1. uspořádej trénovací data vzestupně podle hodnoty diskretizovaného atributu 2. rekurzivně binarizuj aktuální interval Int tak, že 2.1. najdi nejvhodnější dělící bod θ a urči pro něj Zisk(AInt,θ) log2(n-1) ∆A (Int, θ) 2.2. je-li Zisk(AInt,θ) > + n n 2.2.1. rozděl interval Int na intervaly Int<θ a Int>θ 2.2.2. pokračuj v rekurzi Obr. 9 Algoritmus Fayyada a Iraniho
Jiný způsob diskretizace je popsán v [Lee, Shin, 1994]. Tentokrát se jedná o diskretizaci “zdola nahoru” založenou na postupném spojování hodnot numerického atributu do předem zadaného počtu výsledných intervalů. Autoři se opět inspirovali v teorii informace; při posuzování intervalů se měří (pomocí tzv. Hellingerovy divergence) rozdíl mezi množstvím informace v celých datech a množstvím informace v intervalu:
∑(
E(Int) = [
p(Classt) - p(Classt|Int) )2 ]1/2
t
Podobně se vyhodnocuje informace spojená s dělícím bodem θ, oddělujícím dva intervaly:
∑(
E(θ) = [
p(Classt |A(<θ)) -
p(Classt |A(>θ))
)2 ]1/2
t
V obou vzorcích nt p(Classt) = n
a
nt(Int) p(Classt|Int) = n(Int) .
Na rozdíl od předcházejícího algoritmu se tentokrát daty prochází opakovaně. Při každém průchodu se spojí dvojice intervalů oddělených od sebe dělícím bodem s nejmenší hodnotou E(θ) (Obr. 10). Algoritmus Lee, Shin Inicializace 1. uspořádej trénovací data vzestupně podle hodnoty diskretizovaného atributu 2. pro každý dělící bod θi = (ai + ai+1)/2 2.1. vytvoř interval Inti = [θi, θi+1] 2.2. spočítej E(Inti) a E(θi) Hlavní cyklus 1. dokud není dosažen požadovaný počet intervalů 1.1. najdi θmin takové, že E(θmin) = mini E(θi) 1.2. vytvoř interval Intmin = [θmin-1, θmin] ∪[θmin, θmin+1] 1.3. spočítej E(Intmin), E(θmin-1) a E(θmin+1) Obr. 10 Algoritmus Leeho a Shina
11
Možnost diskretizovat numerické atributy nabízí i systém KEX [Berka, 1993]. Algoritmus pro diskretizaci je zde úzce spojen s algoritmem pro tvorbu báze znalostí. Numerický atribut se diskretizuje s přihlédnutím k tomu, jak se do báze znalostí zařazují jednotlivá pravidla. Cílem je diskretizace, která povede k vytvoření pravidel A(Int) ⇒ Class Budeme se tedy snažit vytvářet takové intervaly A(Int), aby se P(Class|A(Int)) signifikantně lišilo od P(Class). Každý interval A(Int) je dán svou dolní a horní mezí DMez a HMez. Algoritmus je uveden na Obr. 11. Opět se jedná o postup zdola nahoru (spojováním), tentokrát se ale předem nezadává počet intervalů. Diskretizace pro KEX Hlavní cyklus: 1. vytvoř uspořádaný seznam hodnot uvažovaného atributu; 2. pro každou hodnotu
2.1. spočítej četnosti výskytu objektů s touto hodnotou pro jednotlivé třídy; 2.2. přiřaď kód třídy každé hodnotě procedurou ASSIGN;
3. vytvoř intervaly hodnot procedurou INTERVAL; ASSIGN: pokud pro danou hodnotu všechny objekty patří do stejné třídy, pak přiřaď hodnotě kód této třídy; jinak pokud pro danou hodnotu veličiny se rozdělení objektů do tříd signifikantně liší (na základě χ2 testu) od apriorního rozdělení tříd, pak přiřaď hodnotě kód nejčetnější třídy, jinak přiřaď hodnotě kód "?"; INTERVAL: 3.1. pokud sekvence hodnot má stejný kód třídy, pak vytvoř interval z těchto hodnot; 3.2. pro každý interval INTi pokud interval INTi patří do třídy "?" pak pokud jeho sousední intervaly INTi-1, INTi+1 patří do téže třídy 3.2.1. vytvoř interval spojením INTi-1 ∪ INTi ∪ INTi+1 3.2.2. jinak vytvoř interval buď spojením INTi-1 ∪ INTi nebo spojením INTi ∪ INTi+1 podle výsledku χ2 testu 3.3. vytvoř spojité pokrytí definičního intervalu veličiny DMEZi := HMEZi-1 Obr. 11 Algoritmus diskretizace v systému KEX
Činnost algoritmu si ukážeme na následujícím příkladu diskretizace atributu „number of years working at current company“ z dat o půjčkách 18. Apriorní rozdělení cílových tříd je uvedeno v Tab. 1. Při diskretizaci se tedy bude brát do úvahy apriorní pravděpodobnost P(+)=0.68. třída půjčka(+) půjčka(-)
abs. četnost 85 40
rel. četnost 0.68 0.32
Tab. 1 Apriorní rozdělení tříd
18
Jedná se o data Japan Credit z kolekce datových souborů používaných pro testování algoritmů strojového učení. Tato kolekce je uložena na Kalifornské universitě v Irvine (UCI ) a je přístupná po Internetu [Murphy, Aha, 1994].
12
Nejprve je vytvořen uspořádaný seznam hodnot veličin a každé hodnotě je procedurou ASSIGN přiřazen kód cílové třídy na základě četností objektů s touto hodnotou pro jednotlivé třídy (Tab. 2); v případě „sporných“ hodnot se použije χ2 test. Procedurou INTERVAL jsou pak vytvořeny intervaly spojením sekvencí hodnot téže třídy (krok 3.1 – viz. Tab. 3). V následujícím kroku 3.2 se zařazují sporné případy; je-li interval třídy ? „uzavřen“ mezi stejnými intervaly, přiřadí se do tohoto intervalu (krok 3.2.1 – Tab. 4), je-li interval třídy ? „uzavřen“ mezi různými intervaly, přiřadí se k jednomu z nich podle hodnoty χ2 (krok 3.2.2 – Tab. 5).
Hodnota n(půjčka( +)) n(půjčka( -)) 0.00 3 13 1.00 10 10 2.00 8 10 3.00 6 1 4.00 2 0 5.00 10 4 6.00 3 0 7.00 6 0 8.00 1 0 9.00 3 0 10.00 3 0 11.00 3 0 12.00 1 1 13.00 6 0 14.00 1 0 15.00 3 0 18.00 2 0 20.00 5 0 25.00 4 0 27.00 1 0 30.00 1 1 35.00 1 0 37.00 1 0
třída ? ? + ? + + + + + + ? + + + + + + + ? + +
Tab. 2 Třída pro jednotlivé hodnoty
DMez 0.00 1.00 2.00 3.00 4.00 5.00 6.00 12.00 13.00 30.00 35.00
HMez n(půjčka( +)) n(půjčka( -)) 0.00 3 13 1.00 10 10 2.00 8 10 3.00 6 1 4.00 2 0 5.00 10 4 11.00 19 0 12.00 1 1 27.00 22 0 30.00 1 1 37.00 2 0
třída ? ? + ? + ? + ? +
Tab. 3 Intervaly ze sekvencí hodnot téže třídy
13
DMez 0.00 3.00 4.00
HMez n(půjčka( +)) n(půjčka( -)) 2.00 21 33 3.00 6 1 37.00 57 6
třída ? +
Tab. 4 Zařazení „vnořených“ sporných intervalů
DMez 0.00 4.00
HMez n(půjčka( +)) n(půjčka( -)) 3.00 27 34 37.00 57 6
třída +
Tab. 5 Zařazení "hraničních" sporných intervalů
Na závěr jsou vytvořeny výsledné intervaly, které pokryjí celý definiční obor veličiny: hodnota =< 3.00, 3.00 < hodnota Uvedený způsob diskretizace může vést k vytvoření značně velkého počtu kategorií v případě, že se pro po sobě jdoucí hodnoty střídají přiřazení objektů ke třídám. Proto se v kroku 3.1 zařazují málo četné intervaly do třídy "?" 19 . Algoritmus má zajímavou modifikaci umožňující vytvářet fuzzy intervaly [Bruha, Berka, 2000]. Na rozdíl od ostrých hranic – dělících bodů jsou v případě fuzzy intervalů hranice „neostré”. V algoritmu diskretizace pro systém KEX to znamená novou proceduru INTERVAL (Obr. 12). Největší změna je v kroku 3.2.2 a 3.3, kde je vytvářena hranice mezi intervaly. INTERVAL: 3.2. pokud má sekvence hodnot stejný kód třídy, pak vytvoř interval z těchto hodnot (s charakteristickou funkcí rovnou 1 v celém intervalu) 3.3. pro každý interval INTi pokud interval INTi patří do třídy "?" pak pokud jeho sousední intervaly INTi-1, INTi+1 patří do téže třídy 3.3.1. vytvoř interval spojením INTi-1 ∪ INTi ∪ INTi+1 (s charakteristickou funkcí rovnou 1 v celém intervalu) 3.3.2. jinak vytvoř jeden interval spojením INTi-1 ∪ INTi tak, že charakteristická funkce je rovna 1 v interalu [DMezi-1, HMezi-1] x - DMezi a rovna HMez - DMez pro x v intervalu [DMezi ,HMezi] i i a druhý interval spojením INTi ∪ INTi+1 tak, že charakteristická funkce je rovna 1 v interalu [DMezi+1, HMezi+1] DMezi - x a rovna HMez - DMez pro x v intervalu [DMezi ,HMezi] i i 3.4. vytvoř spojité pokrytí definičního intervalu veličiny shodně s krokem 3.2.2 (mezery mezi intervaly jsou chápány jako interval třídy "?") Obr. 12 Fuzzy diskretizace
19
Minimální počet objektů v intervalu je jeden ze vstupních parametrů algoritmu.
14
Obr. 13 Fuzzy intervaly
Budeme-li postupovat podle uvedené modifikace, můžeme z jedné numerické hodnoty získat dvě diskretizované hodnoty tak, že součet odpovídajících charakteristických funkcí bude rovný jedné. To ve svých důsledcích vede ke vzniku „částečných“ objektů, které mají váhu (vyjadřující jejich zastoupení v datech) menší než 1. Obr. 13 ukazuje tuto situaci na příkladu atributu teplota, který (pro hodnotu 36.9oC) vede k vytvoření dvou objektů [Bruha, Berka, 2000]:
[ ... vlasy = černé, teplota = 36.9, ... ]
[ ... vlasy = černé, teplota = nízká, ...] µ(teplota) = 0.8
[... vlasy = černé, teplota = vysoká, ...] µ(teplota) = 0.2
Váha „částečného“ objektu je dána součinem hodnot charakteristických funkcí všech atributů 20: w(obj) = ∏i µ(xi) Součet vah všech částečných objektů, které odpovídají témuž objektu v původních datech je roven 1.
Provedením diskretizace numerického atributu samozřejmě ztrácíme nějakou informaci. Objekty, které měly původně různé hodnoty numerického atributu, mohou mít stejné hodnoty diskretizovaného atributu. V krajním případě mohou v důsledku diskretizace dva původně různé objekty splynout do jednoho. Pokud oba původně různé objekty patří do různých tříd, po diskretizaci mezi nimi systém nebude umět rozlišit, zařadí je tedy do téže třídy a tím se dopustí chyby. Zhorší se tedy maximální možná správnost klasifikace 21. Takto vyjádřenou ztrátu způsobenou diskretizací můžeme předem odhadnout. Můžeme vyjít z maximální možné úspěšnosti predikce podle diskretizovaného atributu před a po diskretizaci. Lze zjistit počet kontradikcí 22 daných (pouze) nediskretizovaným atributem a počet kontradikcí daných atributem po diskretizaci. Dříve uvedený vztah nám pak umožní spočítat minimální počet chyb při klasifikaci a tím i maximální možnou správnost klasifikace.
20
V případě kategoriálního atributu xi je charakteristická funkce µ(xi) = 1.
21
A pravděpodobně i správnost skutečná.
22
Kontradikcí myslíme situaci, kdy objekty se stejnými hodnotami vstupních atributů patří do různých tříd.
15
Pro náš ukázkový příklad diskretizace atributu „number of years working atcurrent company“ je minimální chyba při klasifikaci podle tohoto atributu před diskretizací 28 3 + 10 + 8 + 1 + 4 + 1 + 1 = 125 = 22.4% 125 a minimální chyba při klasifikaci podle diskretizovaného atributu 33 27+ 6 125 = 125 = 26.4% Maximální možná správnost klasifikace je pak 77.6% pro numerický atribut a 73.6% pro atribut diskretizovaný. Ztrátu způsobenou diskretizací lze tedy v našem případě vyjádřit jako zhoršení maximální možné správnosti klasifikace podle diskretizovaného atributu o 4% ve srovnání s klasifikací podle atributu nediskretizovaného. Obdobně je možno rovněž zjistit maximální možnou správnost pro celá data před a po diskretizaci. Pro náš případ kreditních dat je v obou případech max. možná správnost rovna 100%. Tedy, v tomto případě diskretizace nezpůsobila žádnou ztrátu informace potřebné pro tvorbu modelu. Experimenty prováděné na dalších datech 23 ukazují, že ztráta způsobená diskretizací je obvykle velmi malá (Tab. 6). Vedlejším důsledkem diskretizace je snížení počtu různých objektů. Řada dříve rozdílných hodnot totiž padne do stejného intervalu. To dokumentuje rovněž Tab. 6 ([Berka, Bruha, 1998a]). Diskretizace numerických atributů tedy může přispět k objevení jistých pravidelností v datech.
data japan credit australian credit iris pima indian diabetes
Původní data Diskretizovaná data počet objektů max. úspěšnost počet objektů max. úspěšnost 125 100% 117 100% 690 100% 663 99% 147 100% 35 98% 768 100% 538 95%
Tab. 6 Vliv diskretizace na počet objektů a maximální možnou správnost klasifikace
7.7
Kategoriální atributy
Chceme-li použít algoritmy, které používají numerické vstupy (např. neuronové sítě), musíme hodnoty kategoriálních atributů zakódovat pomocí čísel. V případě binárních atributů to mohou být např. hodnoty 0, 1 nebo –1, 1, v případě ordinálních atributů to může být pořadové číslo hodnoty, v případě nominálních atributů pak v zásadě libovolné číslo. V případě algoritmů, které pracují přímo s kategoriálními atributy (např. symbolické metody), žádné úpravy obvykle neprovádíme. Výjimku tvoří případ, kdy kategoriální atribut nabývá příliš velkého počtu hodnot 24. Pak přichází na řadu seskupování hodnot. Opět lze vyjít z doménových znalostí experta 25, nebo lze hodnoty seskupovat na základě charakteristik spočítaných v rámci trénovacích dat. 23
Opět se jednalo o data z UCI.
24
Příkladem takovéhoto atributu může být například označení zboží (při analýze nákupního košíku), nebo kód profese v sociodemografické databázi.
25
Může se např. jednat o hierarchii hodnot, tak jak je uvedeno v kapitole o asociačních pravidlech a v kapitole o rozhodovacích pravidlech.
16
Takovéto seskupování lze provádět při tvorbě modelu (viz např. algoritmus CHAID pro tvorbu rozhodovacích stromů), nebo v rámci předzpracování dat. Jako příklad předzpracování uvedeme algoritmus seskupování hodnot svázaný se systémem KEX [Berka, Bruha, 1998b]. Algoritmus pro seskupování je odvozen z výše uvedeného algoritmu pro diskretizaci. Cílem je tedy vytvořit skupiny A(Grp) takové, aby se P(Class|A(Grp)) signifikantně lišilo od P(Class). Algoritmus seskupování hodnot je uveden na . Na rozdíl od algoritmu diskretizace (Obr. 11) se při seskupování vytvoří tolik skupin, kolik je různých tříd plus jedna skupina navíc, označená "?" (Obr. 14).
Seskupování pro KEX Hlavní cyklus: 1. vytvoř uspořádaný seznam hodnot uvažovaného atributu 2. pro každou hodnotu
2.1. spočítej četnosti výskytu objektů s touto hodnotou pro jednotlivé třídy 2.2. přiřaď kód třídy každé hodnotě procedurou ASSIGN
3. vytvoř intervaly hodnot procedurou GROUP ASSIGN: pokud pro danou hodnotu všechny objekty patří do stejné třídy, pak přiřaď hodnotě kód této třídy jinak pokud se pro danou hodnotu veličiny rozdělení objektů do tříd signifikantně liší (na základě χ2 testu) od apriorního rozdělení tříd pak přiřaď hodnotě kód nejčetnější třídy, jinak přiřaď hodnotě kód "?" GROUP: vytvoř skupinu z těch hodnot, které mají přiřazen kód stejné třídy Obr. 14 Algoritmus seskupování v systému KEX
7.8
Chybějící hodnoty
Otázkou práce s chybějícími hodnotami jsme se již zabývali. Připomeňme tedy již dříve uvedené způsoby: 1) ignorovat objekt s nějakou chybějící hodnotou, 2) nahradit chybějící hodnotu novou hodnotou „nevím“, 3) nahradit chybějící hodnotu některou z existujících hodnot atributu a sice: a) nejčetnější hodnotou, b) proporcionálním podílem všech hodnot, c) libovolnou hodnotou.
Zajímavou alternativou je použít pro doplnění chybějící hodnoty některý z algoritmů pro modelování; atribut s chybějícími hodnotami se považuje za cílový atribut, pro trénování a testování se použijí objekty se známou hodnotou tohoto atributu – a chybějící hodnoty se doplní na základě modelu.
17
7.9
Závěr
S příchodem reálných aplikací metod strojového učení se postupně začíná přesouvat pozornost odborníků na dobývání znalostí od algoritmů pro modelování k algoritmům pro předzpracování a přípravu dat. Dokladem této skutečnosti může být i výzkumný projekt 5. rámcového programu EU MiningMart (IST-1999-11993), který si klade za cíl vytvořit uživatelsky přívětivé prostředí pro používání algoritmů z této oblasti [Saitta a kol., 2000].
Literatrura: [Berka, 1993] Berka,P.: Discretization of numerical attributes for Knowledge EXplorer. Výzkumná zpráva, Praha, LISP-93-03, 1993, 11s. [Berka, Bruha, 1998a] Berka,P. - Bruha,I.: Empirical comparison of various discretization procedures. Int. J. of Pattern Recognition and Artificial Intelligence Vol. 12 No. 7 (1998) 1017-1032. [Berka, Bruha, 1998b] Berka,P. - Bruha,I.: Discretization and Grouping: Preprocessing Steps for Data Mining. In: (Zytkow, Quafafou eds.) Proc. Principles of Data Mining and Knowledge Discovery PKDD'98, LNAI 1510, Springer, 1998, 239-245. [Bruha, Berka, 2000] Bruha,I. - Berka,P.: Discretization and Fuzzification of Numerical Attributes in AttributeBased Learning. In: Szcepaniak,P.S. - Lisboa,P.J.G. - Kacprzyk,J.: Fuzzy Systems in Medicine. Springer. 2000. ISBN 3-7908-1263-3. [Bruha, Kočková, 1994] Bruha,I. – Kočková,S.: A support for decision making: Cost-sensitive learning system. Artificial Intelligence in Medicine, 6 (1994), 67-82. [Dietterich, 1997] Dietterich T.: Machine-learning research: four current directions. AI Magazine, winter 1997, 97-136. [Fayyad, Irani, 1993] [Fayyad,U. - Irani,K.: Multi-interval discretization of continuous-valued attributes for classification learning. In: Proc. 13th Joint Conf. of Artificial Intelligence IJCAI’93, 1993, 1022-1027. [Hájek a kol.,1983] Hájek,P. – Havránek,T. – Chytil,M.K.: Metoda GUHA. Automatická tvorba hypotéz. Academia, 1983. [Chan, Stolfo, 1995] Chan,P.K. – Stolfo,S.J.: Learning arbiter and combiner trees from partitioned data for scaling machine learning. In: Proc. 1st Int. Conf. on Knowledge Discovery and Data Mining. AAAI Press, 1995 39-44. [John a kol, 1994] John,G. – Kohavi,R. – Pfleger,K.: Irrelevant features and the subset selection problem. In: Proc. 11th Int. Conf. on Machine Learning, Morgan Kaufmann, 1994, 121-129. [Kietz a kol., 2000] Kietz,J.U. - Zücker,R. - Vaduva,A.: Mining Mart: Combining Case-Based-Reasoning and Multi-Strategy Learning into a Framework to reuse KDD-Application. In: Proc. 5th Int. Workshop on Multistrategy Learning MSL2000, 2000. [Lee, Shin, 1994] Lee,C. – Shin,D.: A context-sensitive discretization of numeric attributes for classification learning. In: (Cohn, ed.) Proc: 11th European Conf. on Artificial Intelligence ECAI’94, John Wiley, 1994, 428432. [Murphy, Aha, 1994] Murphy,P. - Aha,D.: UCI Repository of Machine Learning Databases. University of California Irvine, Dept. Of Information and Computer Science, 1994. [Pecen a kol., 1994] Pecen,L. - Pelikán,E. – Beran,H.: Short-term foreign exchange rate forecasting from high frequency data. In: Proc. International Workshop on Neural Networks in the Capital Markets, Pasadena, CALTECH, USA, 1994. [Pudil, 2001] Pudil,P.: Methodology and Advances in Feature Selection for Statistical Pattern Recognition, Disertace DrSc, UTIA AV ČR, Praha, 2001
18
[Pudil a kol., 1994] Pudil,P. – Novovičová,J. – Kittler,J.: Floating search methods in feature selection. Pattern Recognition Letters, 15, 1994, 1119-1125. [Saitta a kol., 2000] Saitta,L. -Kietz,J.U. - Beccari,G.: Specification of Pre-Processing Operators Requirements. Deliverable, D1.1, IST Project MiningMart, IST-1999-11993, 2000. [Shafer a kol, 1996] Shafer,J. – Agrawal,R. – Mehta,M.: SPRINT: a scalable parallel classifier for data mining. In: Proc. 22th Very Large Databases Conference VLDB, Morgan Kaufmann, 1996, 544-555. [Suzuki, 2000] Suzuki,E. (editor): Proc. Int. Wshop of KDD Challenge on Real-world Data. 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining PAKDD-2000, Kyoto, 2000.
19
