ANALÝZA A KLASIFIKACE DAT

ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc.

INVESTICE ROZVOJE VZDĚLÁVÁNÍ © Institut DO biostatistiky a analýz

V. KLASIFIKACE PODLE MINIMÁLNÍ VZDÁLENOSTI

© Institut biostatistiky a analýz

PRINCIPY KLASIFIKACE ;

pomocí diskriminačních funkcí – funkcí, které určují míru příslušnosti k dané klasifikační třídě;

;

pomocí definice hranic mezi jednotlivými třídami a logických pravidel;

;

pomocí vzdálenosti od reprezentativních obrazů (etalonů) klasifikačních tříd;

;

pomocí ztotožnění s etalony;


PRINCIPY KLASIFIKACE ;

pomocí diskriminačních funkcí – funkcí, které určují míru příslušnosti k dané klasifikační třídě;

;

pomocí definice hranic mezi jednotlivými třídami a logických pravidel;

;

pomocí vzdálenosti od reprezentativních obrazů (etalonů) klasifikačních tříd;

;

pomocí ztotožnění s etalony;


METRIKA - VZDÁLENOST Metrika ρ na X je funkce ρ: X × X → R, kde R je množina reálných čísel, taková, že: ∃ρ0∈R: -∞ < ρ0 ≤ ρ(x,y) < +∞, ∀x,y ∈ X ρ(x,x) = ρ0, ∀x ∈ X a ρ(x,y) = ρ(y,x), ∀x,y ∈ X. (symetrie) Když dále ρ(x, y) = ρ0 když a jen když x = y (totožnost) a

ρ(x, z) ≤ ρ(x, y) + ρ(y, z), ∀x,y,z ∈ X. (Δ nerovnost)

Prostor X, ve kterém metrika ρ definována, nazýváme metrickým prostorem. Vzdálenost je hodnota určená podle metriky. © Institut biostatistiky a analýz

METRIKA PODOBNOSTI - PODOBNOST Metrická míra podobnosti s na X je funkce s: X × X → R, kde R je množina reálných čísel, taková, že: ∃s0∈R: -∞ < s(x,y) ≤ s0< +∞, ∀x,y ∈ X s(x,x) = s0, ∀x ∈ X a s(x,y) = s(y,x), ∀x,y ∈ X. (symetrie) Když dále s(x,y) = s0 když a jen když x = y (totožnost) a

s(x,y).s(y,z) ≤ [s(x,y) + s(y,z)].s(x,z), ∀x,y,z ∈ X.


MÍRY PODOBNOSTI VS. NEPODOBNOSTI Vzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. sij = 1/ρij sij = 1/(1+ ρij) sij = c - ρij, c ≥ max ρij, ∀i,j


MÍRY PODOBNOSTI VS. NEPODOBNOSTI Vzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. sij = 1/ρij s(x,y).s(y,z) ≤ [s(x,y) + s(y,z)].s(x,z), ∀x,y,z ∈ X

sij = 1/(1+ ρij) sij = c - ρij, c ≥ max ρij, ∀i,j



sij = 1/(1+ ρij) sij = c - ρij, c ≥ max ρij, ∀i,j



sij = 1/(1+ ρij) s(x,y).s(y,z) ≤ [s(x,y) + s(y,z) - s(x,y).s(y,z)].s(x,z), ∀x,y,z ∈ X

sij = c - ρij, c ≥ max ρij, ∀i,j



sij = 1/(1+ ρij) s(x,y).s(y,z) ≤ [s(x,y) + s(y,z) - s(x,y).s(y,z)].s(x,z), ∀x,y,z ∈ X

sij = c - ρij, c ≥ max ρij, ∀i,j s(x,z) ≥ s(x,y) + s(y,z) - c


TYPY MĚR VZDÁLENOSTI (PODOBNOSTI) ;

dle typu příznaků (numerické hodnoty, nominální či ordinální hodnoty, binární hodnoty);

;

dle objektů, jejichž vztah hodnotíme – obrazy (vektory), množiny obrazů (vektorů), rozdělení

;

deterministické (nepravděpodobnostní) vs. pravděpodobnostní míry


MÍRY VZDÁLENOSTI obecné poznámky: ;

výběr konkrétní metriky závisí na použití kritéria:

;

Î

optimální výsledky (klasifikační chyby, ztráta, …)

Î

výpočetní nároky

Î

charakter rozložení dat

obecně nelze doporučit vhodnou metriku pro určité standardní situace


NUMERICKÉ PŘÍZNAKY


EUKLIDOVA METRIKA metrika zřejmě s nejnázornější geometrickou interpretaci

⎡ ⎤ ρE ( x1, x 2 ) = ⎢∑ ( x1i − x 2i )2 ⎥ ⎣ i=1 ⎦ n

1/ 2

;

geometrickým místem bodů s toutéž Euklidovou vzdáleností od daného bodu je hyperkoule (kruh ve dvourozměrném prostoru);

;

dává větší důraz na větší rozdíly mezi souřadnicemi (žádoucí nebo nežádoucí? – volba i podle toho, jak chceme zdůrazňovat rozdíly mezi jednotlivými souřadnicemi)

;

čtverec euklidovské vzdálenosti (lépe se počítá) je stále mírou nepodobnosti, ale není metrikou © Institut biostatistiky a analýz

EUKLIDOVA METRIKA metrika zřejmě s nejnázornější geometrickou interpretaci

⎡ ⎤ ρE ( x1, x 2 ) = ⎢∑ ( x1i − x 2i )2 ⎥ ⎣ i=1 ⎦ n

;

1/ 2

Sokalova metrika 1/ 2

⎧ ρ ( x1, x 2 ) ⎫ ρS ( x1, x 2 ) = ⎨ ⎬ n ⎩ ⎭ 2 E


HAMMINGOVA METRIKA (metrika Manhattan, city-block m., taxi driver m.) n

ρH ( x1, x 2 ) = ∑ x1i − x 2i i=1


HAMMINGOVA METRIKA (metrika Manhattan, city-block m., taxi driver m.) n

ρH ( x1, x 2 ) = ∑ x1i − x 2i i=1

;

geometrickým místem bodů ve dvou rozměrném prostoru je kosočtverec;

;

nižší výpočetní nároky než E.m. ⇒ použití v úlohách s vysokou výpočetní pracností


MINKOVSKÉHO METRIKA

⎡ m⎤ ρM ( x1, x 2 ) = ⎢∑ x1i − x 2i ⎥ ⎣ i=1 ⎦ n

1/ m

;

zobecnění Euklidovy a Hammingovy metriky;

;

volba m záleží na míře důrazu – čím větší m, tím větší váha na velké rozdíly mezi příznaky, pro m→∞ metrika konverguje k Čebyševově metrice ρC ( x1, x 2 ) = lim ρM ( x1, x 2 ) m→∞


ČEBYŠEVOVA METRIKA

ρC ( x1, x 2 ) = max {x1i − x 2i } ∀i

;

používá se ve výpočetně kriticky náročných případech, kdy je pracnost výpočtu dle euklidovsky orientovaných metrik nepřijatelná;

;

geometrickým místem bodů s toutéž Čebyševovou vzdáleností od daného bodu je hyperkrychle (čtverec ve dvourozměrném prostoru)


SROVNÁNÍ GEOMETRICKÝCH MÍST


ČEBYŠEVOVA METRIKA ;

pokud je třeba použít „euklidovskou“ metriku, ale s nižší výpočetní pracností, používá se v první řadě Hammingova nebo Čebyševova metrika;

;

lepším přiblížením je kombinace obou metrik

ρ A ( x1, x 2 ) = max( 2ρH / 3; ρC ) (ve dvourozměrném prostoru tvoří geometrické místo bodů o téže vzdálenosti osmiúhelník)


KVADRATICKÁ VZDÁLENOST ρ2Q ( x1, x 2 ) = ( x1 − x 2 )T .Q.(x1 − x 2 ) ;

vhodný výběr matice Q je inverzní matice kovariance uvnitř množiny obrazů;

;

pak se to jmenuje Mahalanobisova metrika

[

−1

]

ρMA ( x1, x 2 ) = ( x1 − x 2 ) .K .(x1 − x 2 ) T

1/ 2


METRIKA CANBERRA n

x1i − x 2i

i=1

x1i + x 2i

ρCA ( x1, x 2 ) = ∑ ;

je vhodná pro proměnné s nezápornými hodnotami Î pokud

jsou obě hodnoty x1i a x2i nulové, potom předpokládáme, že hodnota zlomku je nulová;

Î je-li

jenom jedna hodnta nulová, pak je zlomek roven jedné, nezávile na velikosti druhé hodnoty;

Î někdy

se nulové hodnoty nahrazují malým kladným číslem (menším, než nejmenší naměřené hodnoty);


NELINEÁRNÍ VZDÁLENOST ⎧0 když ρE ( x1, x 2 ) < D ρN ( x1, x 2 ) = ⎨ ⎩H když ρE ( x1, x 2 ) ≥ D kde D je prahová hodnota a H je nějaká konstanta. Uvádí se, že dobrý výběr hodnot H a D by měl splňovat vztah H=

Γ(n / 2)

Dn πn když D splňuje nestrannost a konzistenční podmínku Parzenova odhadu, především DnN→∞ a D→0, když N→∞ (N je počet obrazů v množině)


ÚHLOVÁ VZDÁLENOST n

∑x i=1

n

1i

x 2i

n

∑x ∑x i=1

2 1i

i =1

2 2i

;

Úhlová vzdálenost (je to spíš míra podobnosti, než nepodobnosti) určuje úhel mezi jednotkovými vektory, které mají směr obou zkoumaných vektorů.

;

Vhodná v případě, pokud je informativní pouze relativní hodnota příznaků. © Institut biostatistiky a analýz

ÚHLOVÁ VZDÁLENOST n

∑x i=1

n

1i

x 2i

n

∑x ∑x i=1

2 1i

i =1

2 2i

co takhle korelační koeficient ?

;

Úhlová vzdálenost (je to spíš míra podobnosti, než nepodobnosti) určuje úhel mezi jednotkovými vektory, které mají směr obou zkoumaných vektorů.

;

Vhodná v případě, pokud je informativní pouze relativní hodnota příznaků. © Institut biostatistiky a analýz

NEPRAVDĚPODOBNOSTNÍ METRIKY nevýhody: ;

fyzikální nesmyslnost vytvářet kombinaci veličin s různým fyzikálním rozměrem

;

jsou-li příznakové veličiny zahrnovány do výsledné vzdálenosti se stejnými vahami, zvyšuje se vliv korelovaných veličin


NEPRAVDĚPODOBNOSTNÍ METRIKY možné odstranění (potlačení) nevýhod: vztažením k nějakému vyrovnávacímu faktoru, např. střední hodnotě, směrodatné odchylce, normě daného obrazu x=(x1, x2, …,xn)

x =

n

2 x ∑ i, i=1

rozpětí

Δi = max xij − min xij, j

j

resp. standardizací podle vztahu

uij =

x ij − x j σj

, i = 1,..., n; j = 1,..., K © Institut biostatistiky a analýz

NEPRAVDĚPODOBNOSTNÍ METRIKY možné odstranění (potlačení) nevýhod: ;

lze i subjektivně či na základě nějaké apriorní informace o úloze přiřadit každé příznakové proměnné váhový koeficient, např. váhovaná Minkovského metrika má tvar

⎡ m⎤ ρ WM ( x1, x 2 ) = ⎢∑ ai . x1i − x 2i ⎥ ⎣ i=1 ⎦ n

1/ m



váhování příznaků lze zapsat maticově ui = TC.xi, kde prvky transformační matice C jsou definovány jako cii = ai, pro i = 1, …, n cij = 0, pro i ≠ j

Za tohoto formalismu je Euklidova metrika definována vztahem

[

]

ρEW ( x1, x 2 ) = ( x1 − x 2 ) .C.C .( x1 − x 2 ) T

T

1/ 2



pokud jsou složky transformovaného obrazu dány lineární kombinací více složek původního obrazu, není ani matice C, ani matice C.TC čistě diagonální. Použijeme-li místo matice C.TC inverzní kovarianční matice K-1, pak definiční vztah pro váhovanou Euklidovu metriku je definičním vztahem pro Mahalanobisovu metriku

[

−1

]

ρE (u1,u2 ) = ρMA ( x1, x 2 ) = ( x1 − x 2 ) .K .(x1 − x 2 ) T

1/ 2



pokud jsou složky transformovaného obrazu dány lineární kombinací více složek původního obrazu, není ani matice C, ani matice C.TC čistě diagonální. Použijeme-li místo matice C.TC inverzní kovarianční matice K-1, pak definiční vztah pro váhovanou Euklidovu metriku je definičním vztahem pro Mahalanobisovu metriku

[

−1

]

ρE (u1,u2 ) = ρMA ( x1, x 2 ) = ( x1 − x 2 ) .K .(x1 − x 2 ) ;

T

1/ 2

Kovarianční matice dvou (náhodných) vektorů x=T(x1,…,xm) a y=T(y1,…,yn) je dána vztahem ;

K(x,y)=E((x-Ex).(y-Ey)T) = [cov(xi,yj)]m,n © Institut biostatistiky a analýz

NOMINÁLNÍ A ORDINÁLNÍ PROMĚNNÉ


NOMINÁLNÍ A ORDINÁLNÍ PROMĚNNÉ ;

Nominální proměnná je taková, o jejíž dvou hodnotách můžeme pouze říci, zda jsou stejné či různé (škola, fakulta, obor). Hodnotami mohou být texty (písmena), případně i číselné kódy. Lze u nich zjišťovat jen rozdělení četností, nemůžeme provádět aritmetické operace (sčítat apod.), výjimkou jsou binární proměnné (viz dále).

;

Ordinální (pořadová), u jejíž dvou hodnot můžeme navíc určit pořadí (úroveň spokojenosti, vzdělání). Jako hodnoty lze použít text, datum, číslo. Pro statistické analýzy (s výjimkou zjišťování četností) je třeba texty převést na čísla. S typem datum lze provádět jen některé výpočty, a to pouze v některých programových systémech.


NOMINÁLNÍ A ORDINÁLNÍ PROMĚNNÉ Nominální proměnné jsou často reprezentovány binárně kódem jedna z m. Vzdálenost mezi takovými obrazy je dána součtem příspěvků od jednotlivých proměnných V případě ordinálních proměnných vzdálenost mezi dvěma vektory nezávisí jednoduše na hodnotách proměnných. Pokud proměnná v jednom vektoru nabývá hodnoty m a v druhém hodnoty k (mm Hodnota δmk je velice závislá na řešeném problému. Př. rostlina s krátkými, dlouhými a velmi dlouhými plody. Samozřejmě chceme, aby vzdálenost mezi velmi dlouhým a krátkým plodem byla větší než mezi dlohým a krátkým plodem. To splňuje kódování 1,2,3, ale také 1,10,100. © Institut biostatistiky a analýz

BINÁRNÍ PROMĚNNÉ


BINÁRNÍ PROMĚNNÉ KOEFICIENTY ASOCIACE


KOEFICIENTY ASOCIACE ;

Koeficienty asociace jsou míry podobnosti mezi obrazy obsahujícími logické (binární, dichotomické) příznakové veličiny.

;

Ke zjištění podobnosti je třeba sledovat shodu či neshodu hodnot odpovídajících si příznaků ⇒ čtyři možné situace


KOEFICIENTY ASOCIACE A. u obou obrazů sledovaný jev nastal (oba odpovídající si příznaky mají hodnotu true) – pozitivní shoda; B. u obrazu xi jev nastal (xik = true), zatímco u obrazu xj nikoliv (xjk = false); C. u obrazu xi jev nenastal (xik = false), zatímco u obrazu xj ano (xjk = true); D. u obou obrazů sledovaný jev nenastal (oba odpovídající si příznaky mají hodnotu false) – negativní shoda; © Institut biostatistiky a analýz

KOEFICIENTY ASOCIACE



sledujeme, kolikrát pro všechny příznaky obrazů xi a xj nastaly případy shody a neshody Î A+D

celkový počet shod příznaků;

Î B+C

celkový počet neshod příznaků;

Î A+B+C+D

=n tj. počet příznaků obou obrazů

Na základě počtu zjištěných shod a neshod jsou definovány různé koeficienty asociace. Koeficienty asociace jsou míry podobnosti



Sokalův- Michenerův koeficient (koeficient jednoduché vazby) A +D sSM ( x i , x j ) = A +B+C+D

Problém je se hodnotou D – společná absence jevu – problém „double zero“. To, že někde něco není často nevede k větší podobnosti (ekologie), nebo naopak společná absence se špatně určuje (detekce určitých prvků v signálu). © Institut biostatistiky a analýz


Jaccardův (Tanimotův) koeficient A sJ ( x i , x j ) = A +B+C Î vůbec

neobsahuje člen D – masivní využití v ekologii

Î není

definován pro dvojice obrazů, které vykazují negativní shodu ve všech příznacích;



Diceův koeficient (Czekanowského)

2A 2A = sD ( x i , x j ) = 2 A + B + C ( A + B ) + ( A + C) v podstatě totéž jako Jaccardův koeficient, pouze koincidence má dvojnásobnou váhu



Russelův- Raoův koeficient A sRR ( x i , x j ) = A +B+C+D Asociační koeficienty zpravidla nabývají hodnot z intervalu 〈0,1〉. V případě R-R koeficientu je při srovnání dvou týchž obrazů hodnota sRR = 1 pouze když došlo u všech příznaků jen k pozitivní shodě.


KOEFICIENTY ASOCIACE Z koeficientů asociace, které vyjadřují míru podobnosti lze zpravidla odvodit koeficienty nepodobnosti dX (x i, x j ) = 1 − s x ( x i, x j ) V případě Jaccardova a Dicova koeficientu nepodobnosti je dodefinována hodnota i pro případy úplné negativní shody tak, že dJ(xi,xj) = dD(xi,xj) = 0 pro A = B = C = 0


KOEFICIENTY ASOCIACE Rogersův-Tanimotův koeficient A +D A +D sRT ( x i , x j ) = = A + D + 2.(B + C) (B + C) + ( A + B + C + D) ;

;

Hammanův koeficient A + D − (B + C) sH ( x i , x j ) = A +B+C+D Na rozdíl od všech předcházejících nabývá Hammanův koeficient hodnot z intervalu 〈-1,1〉, přičemž hodnoty -1 nabývá, pokud se příznaky neshodují ani jednou, 0 nabývá když je počet shod a neshod v rovnováze a +1 je v případě úplné shody mezi všemi příznaky. © Institut biostatistiky a analýz

KOEFICIENTY ASOCIACE Na základě četností A až D lze vytvářet také dříve uvedené míry: ;

Hammingova vzdálenost ρH ( x i , x j ) = B + C

;

Euklidova vzdálenost ρE ( x i , x j ) = B + C


KOEFICIENTY ASOCIACE Na základě četností A až D lze vytvářet také dříve uvedené míry: ;

Pearsonův korelační koeficient A.D − B.C sr ( x i , x j ) = ( A + B).(C + D).( A + C).(B + D)

;

kritérium shody χ2 s χ ( x i , x j ) = n.sr2 ( x i , x j )


PODOBNOST MEZI TŘÍDAMI ;

„podobnost“ jednoho obrazu s více obrazy jedné třídy (skupin, množin, shluků);

;

„podobnost“ obrazů dvou tříd (skupin, množin, shluků);

;

zavedeme funkci, která ke každé dvojici skupin obrazů (Ci, Cj) přiřazuje číslo D(Ci, Cj), které podobně jako míry podobnosti či nepodobnosti (metriky) jednotlivých obrazů musí splňovat minimálně podmínky: © Institut biostatistiky a analýz

PODOBNOST MEZI TŘÍDAMI PODMÍNKY ;

(S1)

D(Ci, Cj) ≥ 0

;

(S2)

D(Ci, Cj) = D(Cj, Ci)

;

(S3)

D(Ci, Ci) = maxi,jD(Ci, Cj)

(S3’)

(pro míry podobnosti) D(Ci, Ci) = 0 pro všechna i

;

(pro míry podobnosti)


METODA NEJBLIŽŠÍHO SOUSEDA ;

je-li d libovolná míra nepodobnosti (vzdálenosti) dvou obrazů a Ci a Cj jsou libovolné skupiny množiny obrazů {xi}, i=1,…,K, potom metoda nejbližšího souseda definuje mezi skupinami Ci a Cj vzdálenost

DNN (C i ,C i ) = min d( x p , x q ) x p ∈C i x q ∈C j

Pozn.: Při použití této metody se mohou vyskytovat v jednom shluku často i poměrně vzdálené obrazy. Tzn. metoda nejbližšího souseda může generovat shluky protáhlého tvaru.


METODA K NEJBLIŽŠÍCH SOUSEDŮ Je zobecněním metody nejbližšího souseda. Je definována vztahem k

DNNk (C i ,C i ) = min ∑ d( x p , x q ), x p ∈C i x q ∈C j

tj. vzdálenost dvou shluků je definována součtem k nejkratších vzdáleností mezi obrazy dvou skupin obrazů. Pozn.: Při shlukování metoda částečně potlačuje generování řetězcových struktur.


METODA NEJVZDÁLENĚJŠÍHO SOUSEDA ;

opačný princip než nejbližší sousedi

DFN (C i ,C i ) = max d( x p , x q ) Pozn.:

x p ∈C i x q ∈C j

Generování protáhlých struktur tato metoda potlačuje, naopak vede ke tvorbě nevelkých kompaktních shluků.

;

je možné i zobecnění pro více nejbližších sousedů k

DFNk (C i ,C i ) = max ∑ d( x p , x q ), x p ∈C i x q ∈C j


METODA CENTROIDNÍ ;

vychází z geometrického modelu v euklidovském n rozměrném prostoru a určuje vzdálenost dvou tříd jako čtverec Euklidovy vzdálenosti těžišť obou tříd. je-li těžiště třídy definováno jako střední hodnota z obrazů patřících do této třídy, tj. K

x rk = { x rk1, x rk 2 ,..., x rkn }, x ri = ∑ x rik , i = 1,..., n, k =1

pak

DC (C i ,C i ) = ρE2 ( x i , x j ), © Institut biostatistiky a analýz

METODA PRŮMĚRNÉ VAZBY ;

vzdálenost dvou tříd Ci a Cj je průměrná vzdálenost mezi všemi obrazy tříd Ci a Cj. Obsahuje-li shluk Ci P obrazů a Cj Q obrazů, pak jejich vzdálenost je definována vztahem

1 P Q DGA (C i ,C i ) = d( x p , x q ). ∑∑ PQ p=1 q=1 Pozn.: Metoda často vede k podobným výsledkům jako metoda nejvzdálenějšího souseda.


WARDOVA METODA ;

vzdálenost mezi třídami (shluky) je definována přírůstkem součtu čtverců odchylek mezi těžištěm a obrazy shluku vytvořeného z obou uvažovaných shluků Ci a Cj oproti součtu čtverců odchylek mezi obrazy a těžišti v obou shlucích Ci a Cj.


WARDOVA METODA ;

jsou-li x i a x j těžiště tříd Ci a Cj a x těžiště sjednocené množiny, pak Wardova vzdálenost obou shluků je definována výrazem

D W (C i ,C i ) =

∑

n

2 ( x x ) − − ∑ ik

x i ∈C i ∪C j k =1

n n ⎞ ⎛ 2 2 − ⎜ ∑ ∑ ( x ik − x ik ) + ∑∑ ( x ik − x ik ) ⎟. ⎟ ⎜ x ∈C k =1 x ∈ C k = 1 i j ⎠ ⎝ i i

Pozn.: Metoda má tendenci vytvářet shluky zhruba stejné velikosti, tedy odstraňovat shluky malé, resp. velké. © Institut biostatistiky a analýz

WARDOVA METODA


PRAVDĚPODOBNOSTNÍ METRIKY ;

používají kompletní informaci o struktuře klasifikačních tříd danou pomocí podmíněných hustot pravděpodobnosti p(x|ω1) a p(x|ω2);

;

metriky tohoto typu splňují následující podmínky: 1. J = 0, pokud jsou si hustoty pravděpodobnosti rovny, tj. p(x|ω1) = p(x|ω2); 2. J ≥ 0 3. J nabývá maxima, pokud jsou klasifikační třídy disjunktní, tj. p(x|ω1) = 0 a p(x|ω2) ≠ 0 a naopak.


PRAVDĚPODOBNOSTNÍ METRIKY základní myšlenka: ;

klasifikační chyba:

e=

{

1 1 − ∫ P(ω1 x ) − P(ω2 x ) .p( x )dx 2

}

integrál v tomto vztahu

JK = ∫ P(ω1 x ) − P(ω2 x ) .p( x )dx = = ∫ p( x ω1 ).P(ω1 ) − p( x ω2 ).P(ω2 ) dx

se nazývá Kolmogorovova variační vzdálenost

Chyba bude maximální, když integrand bude nulový, tj. když obě váhované funkce hustoty pravděpodobnosti budou totožné. Naopak chyba bude nulová, pokud se obě hustoty nebudou překrývat ⇒ čím větší vzdálenost mezi třídami, tím je menší chyba klasifikace a naopak.


PRAVDĚPODOBNOSTNÍ METRIKY Podobně jsou definovány další pravděpodobnostní míry vzdálenosti obecně vztahem J( x ) = ∫ f [p( x ωi ),P(ωi ),i = 1,2]dx

Chceme, aby J(x) byla nezáporná funkce, pro kterou je J(x)=0, když jsou obě hustoty pravděpodobnosti totožné a je maximální, když se obě hustoty nepřekrývají.


PRAVDĚPODOBNOSTNÍ METRIKY Chernoffova vzdálenost

JC = − ln ∫ p s ( x ω1 ).p1−s ( x ω2 )dx, Bhattacharyyova vzdálenost Divergence

s ∈ 0;1

JB = − ln ∫ p( x ω1 ).p( x ω2 ).dx

⎛ p( x ω1 ) ⎞ ⎟.dx JD = ∫ p( x ω1 ) − p( x ω2 ) . ln⎜ ⎜ p( x ω ) ⎟ 2 ⎠ ⎝ Patrickova-Fisherova vzdálenost

[

JPF =

]

∫ [p(x ω ) − p(x ω )]

¨2

1

2

.dx


PRAVDĚPODOBNOSTNÍ METRIKY resp. tzv. zprůměrněné verze, zahrnující i apriorní pravděpodobnost jednotlivých klasifikačních tříd zprůměrněná Chernoffova vzdálenost

JC = − ln ∫ [p( x ω1 )P(ω1 )] [p( x ω2 )P(ω2 )] dx, zprůměrněná Bhattacharyyova vzdálenost 1− s

s

s ∈ 0;1

JB = − ln ∫ p( x ω1 ).P(ω1 ).p( x ω2 )P(ω2 ).dx zprůměrněná divergence ⎛ p( x ω1 ).P(ω1 ) ⎞ ⎟.dx JD = ∫ p( x ω1 ).P(ω1 ) − p( x ω2P(ω2 )) . ln⎜ ⎜ p( x ω ).P(ω ) ⎟ 2 2 ⎠ ⎝ zprůměrněná Patrickova-Fisherova vzdálenost

[

JPF =

]

∫ [p(x ω ).P(ω ) − p(x ω ).P(ω )]

¨2

1

1

2

2

.dx


PRAVDĚPODOBNOSTNÍ METRIKY uvedené výrazy se liší zejména pracností výpočtu a vazbou k hodnotám chybné klasifikace. Tato vazba je vyjádřena hodnotami D(x) a H(x) – dolním a horním odhadem pravděpodobnosti chybného zařazení. HC ( x ) = min Jc (s) 0 ≤ s ≤1

HB ( x ) = JB

V případě, že známe dichotomické pravděpodobnostní míry a je třeba řešit problém klasifikace do více tříd, lze definovat kritérium, např. podle vztahu R

J( x ) = ∑

R

∑ P(ω ).P(ω ).J

r =1 q=r +1

r

q

rq

(x )


PRAVDĚPODOBNOSTNÍ METRIKY základní nevýhodou pravděpodobnostních metrik je požadavek na znalost hustot pravděpodobnosti a jejich integrace (numerické?) za určitých předpokladů o typu rozložení mohou být tyto vztahy integrovány analyticky


PRAVDĚPODOBNOSTNÍ METRIKY za předpokladu normálního rozložení (μi jsou střední hodnoty a Σi kovarianční matice) Chernoffova vzdálenost

⎞ Σs 1 1 ⎛⎜ T −1 ⎟, JC = s(1 − s)(μ2 − μ1 ) Σs (μ2 − μ1 ) + ln 1 − s s 2 2 ⎜ Σs Σs ⎟ ⎝ ⎠ kde Σ = (1-s).Σ + s.Σ s

1

s ∈ 0;1

2

Bhattacharyyova vzdálenost je pro s=0,5 Divergence 1 JD = (μ2 − μ1 )T (Σ1−1 + Σ2−1 )(μ2 − μ1 ) + Tr (Σ1−1Σ2 + Σ1Σ2−1 − 2I) 2 1 1 − Patrickova-Fisherova vzdálenost JPF = [ 2Σ1 2 + 2Σ2 ( 2π )

− 2 Σ1 + Σ2

−

1 2

−

1 2

−

⎧ 1 ⎫ −1 T . exp⎨− (μ2 − μ1 ) (Σ1 + Σ2 ) (μ2 − μ1 )⎬] ⎩ 2 ⎭ © Institut biostatistiky a analýz

PRAVDĚPODOBNOSTNÍ METRIKY pokud Σ1 = Σ2 = Σ, pak se vztahy pro Bhattacharyyovu a divergenční vzdálenost zjednoduší na JM = JD = 8JB = (μ2 − μ1 )T Σ −1(μ2 − μ1 ),

což je výraz pro Mahalanobisovu vzdálenost.


Příprava nových učebních materiálů oboru Matematická biologie je podporována projektem ESF č. CZ.1.07/2.2.00/07.0318

„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“

INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ © Institut biostatistiky a analýz

ANALÝZA A KLASIFIKACE DAT

Recommend Documents