Řešení příkladu - klasifikace testovacího subjektu podle minimální vzdálenosti: Postup: I) zvolení metriky pro výpočet vzdáleností dvou bodů II) zvolení metriky pro určení vzdálenosti mezi dvěma množinami bodů Předpoklad: budeme shlukovací algoritmy využívat jako neučící se algoritmy (klasifikátor natrénujeme na celé trénovací množině a pak už pouze klasifikujeme nové subjekty (např. už nepřepočítáváme centroid po zařazení každého nového subjektu či objektu apod.)) 1.1 Metoda k nejbližších sousedů + Euklidova metrika: Znázornění výpočtu vzdálenosti dvou bodů pomocí Euklidovy metriky je uvedeno na Obr. 1. Obr.1: Ilustrace výpočtu vzdálenosti dvou bodů pomocí Euklidovy metriky (vlevo) a znázornění klasifikace podle nejbližšího souseda (vpravo). Modře je vyznačena množina bodů, které mají od testovacího subjektu stejnou vzdálenost. Výpočet vzdáleností testovacího (nového) subjektu od všech subjektů z obou skupin: Seřazení vzdáleností: pro : nejbližší soused bodu je bod , protože je nejmenší → testovací subjekt bude zařazen do třídy kontrolních subjektů; lze rovněž zapsat jako: , kde , a , kde ; protože , testovací subjekt bude zařazen do třídy kontrolních subjektů pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 3 nejbližšími sousedy jsou 2 pacienti a 1 kontrolní subjekt pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 5 nejbližšími sousedy jsou 3 pacienti a 2 kontrolní subjekty pro : nelze rozhodnout Poznámka: je nutné volit liché Poznámka 2: závisí na volbě , kam subjekt zařadíme (tzn., pro různá se zařazení může lišit – např. v tomto případě pro subjekt zařazen do třídy kontrolních subjektů a pro a subjekt zařazen do třídy pacientů) 1.2 Metoda průměrné vazby + Euklidova metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. 1.3 Centroidová metoda + Euklidova metrika: – centroid pacientů – centroid kontrol Protože , testovací subjekt bude zařazen do třídy pacientů. Znázornění klasifikace testovacího subjektu pomocí centroidové metody, přičemž vzdálenosti testovacího subjektu od centroidů skupin jsou počítány pomocí Euklidovy metriky, je na Obr. 2. Centroidová metoda s využitím medoidu: Medoid (odvozen vizuálně – spočítal by se tak, že by se našel nejbližší bod k centroidu u dané skupiny nebo jako bod s nejmenší sumou vzdáleností od ostatních bodů) medoid pro pacienty: medoid pro kontroly: Protože , testovací subjekt bude zařazen do třídy pacientů. Obr. 2: Ilustrace klasifikace testovacího subjektu pomocí centroidové metody, přičemž vzdálenosti testovacího subjektu od centroidů skupin jsou počítány pomocí Euklidovy metriky. Je patrné, že subjekt bude zařazen do třídy pacientů, protože jeho Euklidova vzdálenost od centroidu pacientů je menší než od centroidu kontrol. 2.1 Metoda k nejbližších sousedů + Hammingova (manhattanská) metrika: Znázornění výpočtu vzdálenosti dvou bodů pomocí Hammingovy (manhattanské) metriky je uvedeno na Obr. 3. Výpočet vzdáleností testovacího (nového) subjektu od všech subjektů z obou skupin: Seřazení vzdáleností: pro : nejbližší soused bodu je bod , protože je nejmenší → testovací subjekt bude zařazen do třídy kontrolních subjektů pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 3 nejbližšími sousedy jsou 2 pacienti a 1 kontrolní subjekt pro : nelze rozhodnout pro : nelze rozhodnout pro : nelze rozhodnout Obr. 3: Ilustrace výpočtu vzdálenosti dvou bodů pomocí Hammingovy (manhattanské) metriky (vlevo) a znázornění klasifikace podle nejbližšího souseda (vpravo). Modře je vyznačena množina bodů, které mají od testovacího subjektu stejnou vzdálenost. 2.2 Metoda průměrné vazby + Hammingova (manhattanská) metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. 2.3 Centroidová metoda + Hammingova (manhattanská) metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. Znázornění klasifikace testovacího subjektu pomocí centroidové metody, přičemž vzdálenosti testovacího subjektu od centroidů skupin jsou počítány pomocí Hammingovy (manhattanské) metriky, je na Obr. 4. Centroidová metoda s využitím medoidu: Protože , testovací subjekt bude zařazen do třídy pacientů. Obr. 4: Ilustrace klasifikace testovacího subjektu pomocí centroidové metody, přičemž vzdálenosti testovacího subjektu od centroidů skupin jsou počítány pomocí Hammingovy (manhattanské) metriky. Je patrné, že subjekt bude zařazen do třídy pacientů, protože jeho Hammingova (manhattanská) vzdálenost od centroidu pacientů je menší než od centroidu kontrol. 3.1 Metoda k nejbližších sousedů + Čebyševova metrika: Výpočet vzdáleností testovacího (nového) subjektu od všech subjektů z obou skupin: Seřazení vzdáleností: pro : nejbližší soused bodu je bod , protože je nejmenší → testovací subjekt bude zařazen do třídy kontrolních subjektů pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 3 nejbližšími sousedy jsou 2 pacienti a 1 kontrolní subjekt pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 5 nejbližšími sousedy jsou 3 pacienti a 2 kontrolní subjekty pro : nelze rozhodnout 3.2 Metoda průměrné vazby + Čebyševova metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. 3.3 Centroidová metoda + Čebyševova metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. Centroidová metoda s využitím medoidu: Protože , testovací subjekt bude zařazen do třídy pacientů. 4.1 Metoda k nejbližších sousedů + Canberrská metrika: Výpočet vzdáleností testovacího (nového) subjektu od všech subjektů z obou skupin: Seřazení vzdáleností: pro : nejbližší soused bodu je bod , protože je nejmenší → testovací subjekt bude zařazen do třídy kontrolních subjektů pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 3 nejbližšími sousedy jsou 2 pacienti a 1 kontrolní subjekt pro : nelze rozhodnout pro : subjekt zařazen do třídy kontrolních subjektů, protože mezi 5 nejbližšími sousedy jsou 2 pacienti a 3 kontrolní subjekty pro : nelze rozhodnout 4.2 Metoda průměrné vazby + Canberrská metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. 4.3 Centroidová metoda + Canberrská metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. Centroidová metoda s využitím medoidu: Protože , testovací subjekt bude zařazen do třídy pacientů. 5.1 Metoda k nejbližších sousedů + Mahalanobisova metrika: Nejprve je potřeba vypočítat výběrové kovarianční matice pro třídu pacientů a kontrol, tzn. a (výpočet výběrových kovariančních matic lze nalézt ve Cvičení 1) a jejich inverzi její inverzi a . Výpočet vzdáleností testovacího (nového) subjektu od všech subjektů z obou skupin: Seřazení vzdáleností: pro : nejbližší soused bodu je bod , protože je nejmenší → testovací subjekt bude zařazen do třídy kontrolních subjektů pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 3 nejbližšími sousedy jsou 2 pacienti a 1 kontrolní subjekt pro : nelze rozhodnout pro : subjekt zařazen do třídy pacientů, protože mezi 5 nejbližšími sousedy jsou 3 pacienti a 2 kontrolní subjekty pro : nelze rozhodnout 5.2 Metoda průměrné vazby + Mahalanobisova metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. 5.3 Centroidová metoda + Mahalanobisova metrika: Protože , testovací subjekt bude zařazen do třídy pacientů. Centroidová metoda s využitím medoidu: Protože , testovací subjekt bude zařazen do třídy pacientů. Výsledky uspořádáme do tabulky: metrika Euklidova Hammingova Čebyševova Canberrská Mahalanobisova NN H H H H H 3-NN D D D D D 5-NN D - D H D GA D D D D D CE-centroid D D D D D CE-medoid D D D D D Je patrné, že výsledek klasifikace se může lišit při použití různých metrik vzdálenosti.