Klasifikace s chybějícími hodnotami atributu Problém chybějících hodnot V praxi může dojít k situaci, že v některých instancích nejsou vždy k dispozici hodnoty některých atributů - např. u některých pacientů nemusí být znám výsledek určitého vyšetření a u některých ano; příčinou může být ztráta dat nebo neexistence měření dané veličiny pro zkoumanou instanci, apod. Pokud daný atribut hraje roli v klasifikaci (tj. je relevantní z konkrétního hlediska řešené úlohy), pak příslušný test (třeba v rozhodovacím stromu nebo pravidle) neposkytne výsledek a instanci nelze zařadit do žádné kategorie. Je-li instance trénovacím příkladem, nelze ji pak k trénování použít. Uvedený nedostatek lze řešit různými způsoby: během trénování mohou být neúplné příklady prostě vyřazeny, nebo se vyřadí u všech trénovacích instancí ty atributy, u nichž občas chybí hodnota. Zmíněné postupy mají nedostatky v tom, že buď snižují počet trénovacích příkladů (což nemusí vadit tehdy, když je dat více než dostatečné množství - praxe ale obvykle nedisponuje nadbytečným množstvím, spíše naopak) nebo jsou násilně vyřazeny některé relevantní proměnné (a tím je popis instancí neúplný). To obvykle vede k vyšší klasifikační chybě, respektive k nepoužitelnosti klasifikátoru. Jiná řešení místo vyřazování instancí nebo atributů dávají přednost umělému doplňování chybějících hodnot. Takové doplnění může stanovit např. nejpravděpodobnější hodnotu na základě analýzy disponibilních dat v instancích (včetně zkoumání vzájemných závislostí mezi různými atributy) nebo prostřednictvím rozložení hodnot daného atributu, aj. Obecně nelze říci, která z metod je vhodnější a která ne, protože empirické testy na nejrůznějších datech ukázaly, že výsledek závisí silně na konkrétních okolnostech (množství dat, jejich typ, rozložení hodnot...) a zatímco některá metoda může často selhávat, v řadě případů zase dává dobré výsledky ve srovnání s ostatními postupy. Příklad řešení použitého u algoritmu c4.5/c5/See5 Generátor rozhodovacích stromů c4.5 (a jeho komerční následník c5/See5, jehož demonstrační verzi lze získat na URL uvedené v [1]), který je založen na minimalizaci entropie výběrem relevantních atributů do testovacích uzlů stromu, vychází z využití určitých metod pro trénovací data a jiných pro klasifikovaná data. Přístup Australana J. Rosse Quinlana, autora c4.5/c5/See5, dává velmi dobré výsledky pro řadu nejrůznějších dat, ale samozřejmě neposkytuje absolutní záruku bezchybného fungování ve všech případech; navíc nevylučuje alternativní řešení, která rovněž poskytují (i když také ne vždy) dobré výsledky. Zde je stručně popsán Quinlanův přístup [2] jednak proto, že je jako součást příslušného software široce využíván a dále proto, že vhodně ilustruje jeden z možných přístupů, od něhož lze v praxi očekávat většinou úspěch (s tím, že ovšem nezaručuje vždy nejlepší dosažitelný výsledek a není záruka neselhání). Trénovací příklady Zde je použit pravděpodobnostní (váhový) přístup. Vychází se z toho, že trénovací příklad t e T s danou (známou) klasifikací cje přiřazen do podmnožiny T-v tj. pravděpodobnost (váha) p náležení t do třídy Ti je 1, do ostatních tříd je p = 0. Není-li známa hodnota některého relevantního atributu trénovacího příkladu, nelze stanovit výsledek testu této hodnoty - na výsledku testu záleží např. stanovení entropie, neboli u c4.5 zisku informace vzniklého rozdělením nehomogenní (pod)-množiny na podmnožiny homogennější. Výsledky testů tedy stanovují cestu n-ár-ním stromem k výslednému listu, a nelze-li v určitém uzlu stanovit exaktně kudy dál, pak jsou do nějaké míry možné všechny další cesty z daného uzlu. Jinak řečeno, vektor hodnot atributů s některými hodnotami neznámými může ukazovat do více tříd (místo do jediné, což je cílem klasifikace). Otázka je, do jaké míry zkoumaný případ náleží do každé z tříd přicházejících do úvahy. Jednotlivé cesty z daného testovacího uzlu do těchto tříd dostanou váhy odvozené z pravděpodobnosti náležení zkoumaného případu do příslušných tříd. Před stanovením výpočtu vah jednotlivých hran z testovacího uzlu si zaveďme podrobněji pojem informační zisk. Zde v principu jde o množství informace poskytované nějakým atributem. Při konstrukci stromu je vhodné jako testy vybrat ty atributy, které poskytují co největší zisk informace, tj. původní nehomogenní množina dat je testy rozdělena na řadu homogénnej sich (ideálně zcela homogenních) podmnožin zastupujících nakonec (v listech stromu) jednotlivé klasifikační třídy. C4.5 využívá míru informace založenou na teorii Shannona a Weavera z r. 1949. Informační zisk C4.5 zavádí pro konstrukci stromu tzv. kritérium informačního zisku (information gain criterion) založené na výběru testu vhodného atributu (pozn.: algoritmus c4.5 používá heuristický přístup). Předpokládejme, že je možný test s n výstupy (tj. z testovacího uzlu vychází n hran). Daná nehomogenní množina T obsahující vektory hodnot atributů (tj. příklady) je tedy dělena na pokud možno homogennější podmnožiny Tu T2, T3, ..., Tn. Vyhodnocení kvality testu nepoužívá další dělení potenciálně vzniklých Tt, k dispozici je pouze rozložení tříd v T a vzniklé podmnožiny Tt. Je zapotřebí zjistit, který test (na který atribut a na jaké jeho hodno- ty) v daném miste stromu vede k nejlepším výsledkům. Dale bude použito následující značení: S ... libovolná množina příkladů, \S\ ... počet příkladů v S, freq(Cit S) ... počet příkladů z S náležejících do třídy C,. Náhodný výběr příkladu z S a jeho prohlášení za člena třídy C- má pravděpodobnost freqiC^S) takže poskytovaná informace má hodnotu -log2 fjřeq{C},S)^ bitů. V I" I J (Pozn.: 1 bit je schopen poskytnout informaci ano/ne; protože se používají bity, má logaritmus základ 2.) Ke zjištění míry očekávané informace, kterou podávají zprávy o tom, že určité příklady náležejí do určitých tříd, je nutno sečíst informační přínosy přes jednotlivé třídy vzhledem k jejich četnostem v S (k je počet tříd): í -&•„„(r