Klasifikace (umělá inteligence)

Klasifikace je ve strojovém učení a statistice druh problému, kde je cílem zařadit nový vzorek do jedné nebo více kategorií na základě množiny trénovacích dat, která obsahuje vzorky, jejichž kategorie je známa. K tomu máme k dispozici trénovací množinu obsahující pozorování (data, instance), pro která jsou kategorie správně určeny. Jednotlivá pozorování jsou analyzována do množiny kvantifikovatelných vlastností, známých jako nezávislé proměnné, rysy, fíčury (features) apod. Tyto vlastnosti mohou být kategoriální (např. „A“, „B“, „AB“ nebo „O“ pro krevní skupiny), ordinální (např. „velký“, „střední“ nebo „malý“), celočíselné (např. počet výskytů slova v emailu) anebo reálné (např. měření krevního tlaku). Některé algoritmy pracují pouze s diskrétními hodnotami a požadují, aby se celočíselná nebo reálná data diskretizovala, tj. převedla se na kategorie obsahující podobná pozorování (např. „méně než 5“, „mezi 5 a 10“, „víc než 10“). Jako příklad problému klasifikace je přiřazení emailu do třídy „spam“ nebo „ne-spam“ anebo přiřazeni diagnózy danému pacientovi, podle jeho pozorovaných charakteristik (pohlaví, věk, krevní tlak, přítomnost nebo absence určitých symptomů, …)

Algoritmus, který implementuje klasifikaci, se nazývá klasifikátor. Tento termín se používá také pro matematickou funkci, která je implementována algoritmem, a zobrazuje vstupní data na třídy.

V terminologii strojového učení je klasifikace považována za metodu učení s učitelem, to jest učení, při kterém je známá trénovací množina správně klasifikovaných příkladů. Analogická metoda v učení bez učitele je známá jako klastrování a spočívá ve spojování dat do kategorií podle nějaké míry vnitřní podobnosti (např. odvozené ze vzdálenosti mezi instancemi, které jsou považovány za vektory ve vícedimenzionálním vektorovém prostoru).

Terminologie není jednotná a liší se ve statistice a strojovém učení, případně v různých aplikačních oblastech.

Přehled

má příbuzné problémy
má různá vstupní data
má různá výstupní data, tj. třídy
používá bayesovský přístup
používá fíčury
nejjednodušší jsou lineární klasifikátory
ale je i spousta dalších a lepších
je to nutné vyhodnocovat: ROC křivka, …
používá se …

Druhy

Binární klasifikace klasifikuje do dvou tříd, někdy nazývaných pozitivní příklady a negativní příklady. Je to základní a nejjednodušší úloha.
Diskrétní klasifikace zařazuje příklady do několika tříd, obecně víc než dvou (multi-class).
Fasetová klasifikace přiřazuje ke každému příkladu obecně víc tříd dle různých aspektů. Například k blogovému příspěvku několik klíčových slov (hashtag)
Jednotřídní klasifikace dostává příklady pouze z jedné (pozitivní) třídy a má určit outliery (odlehlé hodnoty) neboli anomálie. Používá se pro detekci anomálií a detekci novinek. Obvykle se předpokládá, že většina dat je normální a anomálie jsou řídké. Tato úloha je podobná binární klasifikaci, kde četnosti jednotlivých tříd jsou nevyvážené.
Fuzzy klasifikace určuje pravděpodobnost příslušnosti k jednotlivým třídám. Některé návazné algoritmy dokážou tuto informaci využít. Rozdíl (spíš podíl, bayesovsky) v pravděpodobnostech je možné brát jako vyjádření (sebe)jistoty klasifikátoru. Když je příklad blízko rozhodovací hranice, jsou pravděpodobnosti skoro stejné a klasifikátor nedokáže jednoznačně pozorování zatřídit.

Konkrétní praktické úlohy mohou formálně spadat do některého výše uvedeného druhu, ale mohou mít další vlastnosti, které je činí obtížnými z jiných důvodů, a případně je vhodné používat jiné, specializované algoritmy. Například binární klasifikace je základní úloha získávání informací (information retrieval), kdy máme určit, zda dokument je relevantní nebo nerelevantní, ale počet atributů dokumentu odpovídá počtu slov (dané slovo je/není v dokumentu) a je typicky velký.

Příbuzné úlohy jsou například ranking pozorování, tj. určování pořadí. Rozpoznávaní vzorů je také příbuzná úloha binární (pro jeden vzor) nebo diskrétní klasifikace (pro několik vzorů), ale liší se tím, že vzor je často lokální a netýká se celého příkladu. Hledání tváře na obrázku je příklad tohoto druhu.

Algoritmy

Pro různé druhy klasifikace jsou různé algoritmy. Algoritmy pro binární klasifikaci se dají použít pro řešení pokročilejších úloh.

Pro binární klasifikaci se používají rozhodovací stromy, perceptron v několika variantách, k-NN a další.

Pokročilé metody spočívají v kombinaci několika klasifikátorů. (náhodný les …)

Nejjednodušší klasifikátor je pro lineárně oddělitelné množiny pozitivních a negativních příkladů. Ale vstupní data typicky obsahují chyby neboli šum a pak tento jednoduchý přístup není použitelný.

Celkové schéma přístupu je, že se nejdříve naučí (natrénuje) klasifikátor na základě trénovacích dat. Hotový klasifikátor se pak používá pro klasifikaci nových dat.

Komplikace vyžadující speciální přístup a algoritmy jsou, když je příkladů mnoho (miliony) nebo naopak málo nebo když je rysů mnoho, případně jsou závislé. Pokud vybraný algoritmus data nezvládá, použije se předzpracování dat, kterému je věnována podkapitola.

Vstupní data

Nejčastější podoba dat je seznam rysů, kde každý rys má daný typ hodnot. Rysy podle typů hodnot se principiálně dělí na diskrétní a spojité, které obvykle potřebují jiný přístup při učení a případně jiné algoritmy. Pokud algoritmus dovoluje zpracovat jen určitý typ rysů, je možné hodnoty převést případně se ztrátou informace, viz předzpracování.

V případě úlohy klasifikace a učení s učitelem má každý vstupní příklad určen výslednou kategorii jako hodnotu jednoho z rysů.

Jiné možnosti než učení s učitelem jsou polosupervizované učení a transdukce (ve strojovém učení). Tyto metody dokáží využít i data, pro která nejsou určeny výsledné kategorie – takových dat je obvykle víc, obvykle je lacinější je získat a z hlediska výsledné kategorie nejsou zašuměna (když se experti určující kategorii neshodli).

Typy vstupních dat

V úvodu. A taky strukturované a hierarchické, případně metadata.

Předzpracování dat

Surová data získaná z databází není vhodné použít přímo.

Předzpracování může identifikovat a vyloučit outliery, doplnit chybějící hodnoty, sjednotit zápis a formu příkladů (například kalendářní data jsou různorodá) apod. Spojitá data můžeme zdiskrétnit (rozdělit na několik intervalů, je několik metod) nebo naopak, pokud to algoritmus vyžaduje.

Další předzpracování může vybrat podmnožinu dat, pokud je dataset velký. Kromě do očí bijícího náhodného výběru můžeme chtít vybrat příklady typické nebo je pokrýt reprezentativně, což může znamenat například zachování poměru tříd nebo zachování zajímavých či typických příkladů.

Předzpracování může vybrat atributy v rámci výběru rysů anebo může atributy přidat pomocí extrakce rysů. První přístup se typicky používá, pokud je atributů mnoho, či jsou závislé a nerelevantní. Druhý přístup se používá, pokud jsou jednotlivé atributy nevhodné pro další zpracování a potřebujeme jejich kombinace. Některé metody klasifikace totiž z principu nebo kvůli jednoduchosti zpracovávají atributy samostatně.

Další druh transformací jsou globální transformace. Číselná data v nějakém metrickém (pod)prostoru můžeme rotovat, natáhnout, centrovat … Používané techniky jsou latentní sémantické indexování (LSI), analýza hlavních komponent (PCA) a další. Například pro klasifikaci pomocí support vector machines (SVM) se doporučuje atributy standardizovat, aby měly střední hodnotu 0 a standardní odchylku 1.

Měření

Je známo mnoho měr kvality klasifikátoru. Už byla vzpomínána ROC křivka. Měření se provádí na nových, nepoužitých datech, tzv. testovacích.

Obecně, různé chyby mohou mít různou cenu. Pro binární klasifikátory cena chyby pro falešná pozitiva a falešná negativa (nazývaných taky chyba prvního druhu a chyba druhého druhu) může být různá. Pro obecné třídy cena chyby může být odvozena z podobnosti tříd; čím jsou třídy podobnější, tím je penalizace za chybu menší.

Reference

V tomto článku byl použit překlad textu z článku Statistical classification na anglické Wikipedii.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu klasifikace na Wikimedia Commons