© Institut biostatistiky a analýz
Analýza a klasifikace dat –
přednáška 4
RNDr. Eva Koriťáková, Ph.D.
Podzim 2018
Typy klasifikátorů – podle principu klasifikace
2Koriťáková: Analýza a klasifikace dat
• klasifikace pomocí diskriminačních funkcí:
– diskriminační funkce určují míru příslušnosti
k dané klasifikační třídě
– pro danou třídu má daná diskriminační
funkce nejvyšší hodnotu
• klasifikace pomocí vzdálenosti od etalonů klasif. tříd:
– etalon = reprezentativní objekt(y) klasifikační třídy
– počet etalonů klasif. třídy různý – od jednoho vzorku
(např. centroidu) po úplný výčet všech objektů dané
třídy (např. u klasif. pomocí metody průměrné vazby)
• klasifikace pomocí hranic v obrazovém prostoru:
– stanovení hranic (hraničních ploch) oddělujících
klasifikační třídy
x1
x2
?
x1
x2
?
0
1
2
3
4
5
6
7
4
6
8
10
12
14
0
0.05
x1x2
x2 x1
3Koriťáková: Analýza a klasifikace dat
Motivace
x1
x2
Hranice je nadplocha o rozměru o jedna menší než je rozměr prostoru
• ve 2-rozměrném prostoru je hranicí křivka (v lineárním případě přímka)
• v 3-rozměrném prostoru plocha (v lineárním případě rovina)
Hranice je tedy dána rovnicí: h 𝐱 = 𝐰 𝑇 𝐱 + w0 = 0
Výpočet hranice různými metodami (např. Fisherova LDA, SVM apod. – viz dále)
2-rozměrný prostor 3-rozměrný prostor
x1
x2
x3
Souvislost klasifikace pomocí diskriminačních funkcí
s klasifikací pomocí hranic
Koriťáková: Analýza a klasifikace dat
Hranice mezi dvěma sousedními třídami ω1 a ω2 je určena průmětem
průsečíku funkcí gr(x) a gs(x), definovaného rovnicí gr(x) = gs(x), do obrazového
prostoru, tzn.: h 𝐱 = g1(x) – g2(x) = 0
g(x)
g1(x) g2(x)
xxHw1 w2
hraniční bod
např. u Bayesova klasifikátoru: h 𝐱 = 𝑃 𝜔 𝐷|𝐱 − 𝑃 𝜔 𝐻|𝐱 = 0
Souvislost klasifikace podle minimální vzdálenosti
s klasifikací pomocí hranic
5Koriťáková: Analýza a klasifikace dat
• zařazení objektu x do té třídy, jejíž etalon má od bodu x minimální
vzdálenost – tzn. xxxxx 

sE
s
rEd min)(
• v případě dvou tříd reprezentovaných etalony x1E = (x11E, x12E) a x2E = (x21E,
x22E) ve dvoupříznakovém euklidovském prostoru je vzdálenost mezi
obrazem x = (x1,x2) a libovolným z obou etalonů definována:
• hledáme menší z obou vzdáleností, tj. mins=1,2v(xsE,x), tzn. mins=1,2v2(xsE,x) :
2
22
2
11 )x(x)x(x),(  EsEssEsEv xxxx
 
 ]2/)x(xxxx[x2xxmin
)x(x)x(xmin),(min),(min
2
2
2
12211
2
2
2
1
2
22
2
11
2
EsEsEsEs
s
EsEs
s
sE
s
sE
s
vv




xxxx
Souvislost klasifikace podle minimální vzdálenosti
s klasifikací pomocí hranic
6
• tato hraniční přímka mezi klasifikačními třídami je vždy kolmá na spojnici
obou etalonů a tuto spojnici půlí
• souvislost s klasifikací podle diskriminačních funkcí
• diskriminační kuželové plochy se protínají v parabole a její průmět do
obrazové roviny je přímka definovaná vztahem
x1(x11E - x21E ) + x2(x12E - x22E ) - (x2
12E + x2
11E - x2
21E - x2
22E )/2 = 0
Koriťáková: Analýza a klasifikace dat
7Koriťáková: Analýza a klasifikace dat
• Hranice mezi klasifikačními třídami jsou dány průmětem diskriminačních
funkcí do obrazového prostoru.
• Klasifikace podle minimální vzdálenosti definuje hranici, která je kolmá na
spojnici etalonů klasifikačních tříd a půlí ji.
• Princip klasifikace dle minimální vzdálenosti vede buď přímo, nebo
prostřednictvím využití metrik podobnosti k definici diskriminačních funkcí
a ty dle prvního ze zde uvedených pravidel k určení hranic mezi
klasifikačními třídami.
Souvislost jednotlivých principů klasifikace - shrnutí
8Koriťáková: Analýza a klasifikace dat
Lineární separabilita
lineárně separabilní
úloha
nelineárně
separabilní úloha
lineárně neseparabilní
úloha
lineárně separované
klasifikační třídy
x1
x2
x1
x2
x1
x2
a) b) c)
9Koriťáková: Analýza a klasifikace dat
1. zachováme původní obrazový prostor a zvolíme nelineární hranici:
Lineárně neseparabilní třídy – způsoby řešení
2. zobrazíme původní p-rozměrný obrazový prostor nelineární transformací
do nového m-rozměrného prostoru tak, aby v novém prostoru byly
klasifikační třídy lineárně separabilní
a) definovanou
obecně
b) složenou po částech
z lineárních úseků
10Koriťáková: Analýza a klasifikace dat
Lineárně neseparabilní třídy – souvislost klasifikace
dle minimální vzdálenosti s klasifikací pomocí hranic
Klasifikace podle minimální vzdálenosti s třídami reprezentovanými více
etalony je „ekvivalentní“ klasifikaci s po částech lineární hraniční plochou
11Koriťáková: Analýza a klasifikace dat
1. klasifikace „jedna versus zbytek“
R-1 hranice oddělí jednu klasifikační třídu od všech dalších
Klasifikace s více třídami
• problematickým úsekům se můžeme vyhnout použitím diskriminačních funkcí
(do r-té třídy ωr zařadíme obraz x za předpokladu, že gr(x) > gs(x) pro  r  s)
→ klasifikační hranice je průmět průsečíku gr(x) = gs(x) do obrazového prostoru
– takto definovaný klasifikační prostor je vždy spojitý a konvexní
2. klasifikace „jedna versus jedna“
R(R-1)/2 binárních hranic mezi každými dvěma třídami
12Koriťáková: Analýza a klasifikace dat
• Fisherova lineární diskriminace (FLDA)
• Algoritmus podpůrných vektorů
• Metoda nejmenších čtverců
• Perceptron
Metody stanovení klasifikačních hranic
13Koriťáková: Analýza a klasifikace dat
• Fisherova lineární diskriminace (FLDA)
• Algoritmus podpůrných vektorů
• Metoda nejmenších čtverců
• Perceptron
Metody stanovení klasifikačních hranic
14Koriťáková: Analýza a klasifikace dat
• jiný název: Fisherova lineární diskriminační analýza (FLDA)
• použití pro lineární klasifikaci
• princip: transformace do jednorozměrného prostoru tak, aby se třídy od
sebe maximálně oddělily
Fisherova lineární diskriminace
projekce 1
projekce2
x1
x2
pacienti
kontroly
centroid pacientů
centroid kontrol
• předpoklad: vícerozměrné normální rozdělení u jednotlivých skupin
15
• podstatou FLDA tedy projekce do 1-D prostoru tak, že chceme:
– maximalizovat vzdálenost skupin
– minimalizovat variabilitu uvnitř skupin
Fisherova lineární diskriminace – princip
projekce 1
projekce2
x1
x2
pacienti
kontroly
centroid pacientů
centroid kontrol
• Fisherovo diskriminační kritérium je tedy ve tvaru: J 𝐰 =
തy 𝐷 − തy 𝐻
2
s 𝐷
2
+ s 𝐻
2
kde s 𝐷
2
a s 𝐻
2
jsou rozptyly uvnitř třídy pacientů resp. kontrol po projekci do 1-D prostoru
a തy 𝐷 a തy 𝐻 jsou projekce centroidu třídy pacientů resp. kontrol
Koriťáková: Analýza a klasifikace dat
16Koriťáková: Analýza a klasifikace dat
Projekce do 1-D prostoru
x1
x2
yi
• bod 𝐱 𝑖 reprezentuje 𝑖-tý subjekt
• y𝑖 je projekce bodu 𝐱 𝑖
• 𝐰 je váhový vektor udávající směr 1-D prostoru
𝑦𝑖 = 𝐰T
𝐱 𝑖
17Koriťáková: Analýza a klasifikace dat
• projekce centroidů skupiny pacientů a kontrolních subjektů:
ത𝐱 𝐷 =
1
𝑛 𝐷
σ𝑖=1
𝑛 𝐷
x 𝑖1
1
𝑛 𝐷
σ𝑖=1
𝑛 𝐷
x 𝑖2 ⋯
1
𝑛 𝐷
σ𝑖=1
𝑛 𝐷
x 𝑖𝑝
ത𝐱 𝐻 =
1
𝑛 𝐻
σ𝑖=1
𝑛 𝐻
x 𝑖1
1
𝑛 𝐻
σ𝑖=1
𝑛 𝐻
x 𝑖2 ⋯
1
𝑛 𝐻
σ𝑖=1
𝑛 𝐻
x 𝑖𝑝
Projekce do 1-D prostoru
• výpočet rozptylu uvnitř třídy pacientů po projekci do 1-D prostoru:
• analogicky výpočet rozptylu uvnitř třídy kontrol po projekci do 1-D prostoru:
s 𝐻
2
= ⋯ = 𝐰T
𝐒 𝐻 𝐰
s 𝐷
2
=
1
𝑛 𝐷−1
σ𝑖=1
𝑛 𝐷
y𝑖 − തy 𝐷
2
=
1
𝑛 𝐷−1
σ𝑖=1
𝑛 𝐷
𝐰T
𝐱 𝑖 − 𝐰T ത𝐱 𝐷
2
=
1
𝑛 𝐷−1
σ𝑖=1
𝑛 𝐷
𝐰T
𝐱 𝑖 − ത𝐱 𝐷
2
= 𝐰T 1
𝑛 𝐷−1
σ𝑖=1
𝑛 𝐷
𝐱 𝑖 − ത𝐱 𝐷 𝐱 𝑖 − ത𝐱 𝐷
T 𝐰 = 𝐰T 𝐒 𝐷 𝐰
→ തy 𝐷 = 𝐰T ത𝐱 𝐷
→ തy 𝐻 = 𝐰T ത𝐱 𝐻
18Koriťáková: Analýza a klasifikace dat
• Fisherovo diskriminační kritérium: J 𝐰 =
ഥy 𝐷−ഥy 𝐻
2
s 𝐷
2 +s 𝐻
2
Fisherovo diskriminační kritérium – rozepsání
• rozepsání součtu rozptylů uvnitř jednotlivých tříd po transformaci do 1-D
prostoru (tzn. rozepsání jmenovatele Fisherova diskr. kritéria):
s 𝐷
2
+ s 𝐻
2
= 𝐰T 𝐒 𝐷 𝐰 + 𝐰T 𝐒 𝐻 𝐰 = 𝐰T 𝐒 𝐷 + 𝐒 𝐻 𝐰 = 𝐰T 𝐒 𝑊 𝐰,
kde 𝐒 𝑊 je suma čtverců variability uvnitř skupin a lze ji vypočítat jako: 𝐒 𝑊 = 𝐒 𝐷 + 𝐒 𝐻
v obecném případě (při nevyvážených počtech subjektů ve skupinách) –
vážená suma čtverců variability uvnitř skupin: 𝐒 𝑊 =
𝑛 𝐷−1 𝐒 𝐷+ 𝑛 𝐻−1 𝐒 𝐻
𝑛 𝐷+𝑛 𝐻−2
• rozepsání rozdílu centroidů promítnutých do 1-D prostoru (tzn. rozepsání
čitatele Fisherova diskr. kritéria):
തy 𝐷 − തy 𝐻
2
= 𝐰T ത𝐱 𝐷 − 𝐰T ത𝐱 𝐻
2
= 𝐰T ത𝐱 𝐷 − ത𝐱 𝐻
2
= 𝐰T ത𝐱 𝐷 − ത𝐱 𝐻 ത𝐱 𝐷 − ത𝐱 𝐻
T
𝐰 = 𝐰T
𝐒 𝐵 𝐰,
kde 𝐒 𝐵 je suma čtverců variability mezi skupinami
• Fisherovo diskr. kritérium lze tedy vyjádřit jako: J 𝐰 =
ഥy 𝐷−ഥy 𝐻
2
s 𝐷
2 +s 𝐻
2 =
𝐰T 𝐒 𝐵 𝐰
𝐰T 𝐒 𝑊 𝐰
19Koriťáková: Analýza a klasifikace dat
Fisherovo diskriminační kritérium – maximalizace
• Fisherovo diskriminační kritérium: J 𝐰 =
ഥy 𝐷−ഥy 𝐻
2
s 𝐷
2 +s 𝐻
2 =
𝐰T 𝐒 𝐵 𝐰
𝐰T 𝐒 𝑊 𝐰
• Chceme maximalizovat J 𝐰 , proto J 𝐰 zderivujeme a položíme výraz
roven 0:
𝜕
𝜕𝐰
J 𝐰 = 0
𝜕
𝜕𝐰
𝐰T 𝐒 𝐵 𝐰 𝐰T 𝐒 𝑊 𝐰 − 𝐰T 𝐒 𝐵 𝐰
𝜕
𝜕𝐰
𝐰T 𝐒 𝑊 𝐰
𝐰T 𝐒 𝑊 𝐰 2
= 0
𝟐𝐒 𝐵 𝐰 𝐰T 𝐒 𝑊 𝐰 − 𝐰T 𝐒 𝐵 𝐰 𝟐𝐒 𝑊 𝐰
𝐰T 𝐒 𝑊 𝐰 2
= 0
𝐰T 𝐒 𝐵 𝐰 𝐒 𝑊 𝐰 = 𝐰T 𝐒 𝑊 𝐰 𝐒 𝐵 𝐰
• u vektoru 𝐰 nás nezajímá jeho modul (tzn. velikost), jen jeho směr, proto
můžeme pominout skalární členy 𝐰T 𝐒 𝐵 𝐰 a 𝐰T 𝐒 𝑊 𝐰, čímž dostáváme:
𝐒 𝑊 𝐰 ~ 𝐒 𝐵 𝐰
20Koriťáková: Analýza a klasifikace dat
Fisherovo diskriminační kritérium – maximalizace
• protože 𝐒 𝐵 𝐰 = ത𝐱 𝐷 − ത𝐱 𝐻 ത𝐱 𝐷 − ത𝐱 𝐻
T 𝐰 = ത𝐱 𝐷 − ത𝐱 𝐻 ∙ 𝛼, kde 𝛼 je nějaký
skalár → 𝐒 𝐵 𝐰 má tedy směr ത𝐱 𝐷 − ത𝐱 𝐻 a jeho modul 𝛼 nás nezajímá, proto:
𝐒 𝑊 𝐰 ~ ത𝐱 𝐷 − ത𝐱 𝐻
• z čehož vypočteme váhový vektor 𝐰 jako: 𝐰 ~ 𝐒 𝑊
−1
ത𝐱 𝐷 − ത𝐱 𝐻
𝐒 𝑊 𝐰 ~ 𝐒 𝐵 𝐰
21
Fisherova LDA – výpočet hranice
projekce 1
projekce2
x1
x2
pacienti
kontroly
centroid pacientů
centroid kontrol
• hranice je dána: 𝐰 𝑻
𝐱 − ෤y = 0, kde ෤y je průmět hraničního bodu v 1-D
prostoru a lze ho vypočítat jako: ෤y =
ഥy 𝐷+ഥy 𝐻
2
• pokud chceme zařadit nový subjekt 𝐱0 do jedné z daných tříd, jeho průmět
do 1-D prostoru (y0 = 𝐰T 𝐱0) srovnáme s průmětem hraničního bodu ෤y:
 Pokud y0 < ෤y (přičemž തy 𝐻 < ෤y), subjekt zařadíme do skupiny kontrolních subjektů
 Pokud y0 > ෤y (přičemž തy 𝐻 < ෤y), subjekt zařadíme do skupiny pacientů
Koriťáková: Analýza a klasifikace dat
22Koriťáková: Analýza a klasifikace dat
Příklad
Příklad: Bylo provedeno měření objemu hipokampu a mozkových komor (v
cm3) u 3 pacientů se schizofrenií a 3 kontrol: 𝐗 𝐷 =
2 12
4 10
3 8
, 𝐗 𝐻 =
5 7
3 9
4 5
.
Určete, zda testovací subjekt 𝐱0 = 3,5 9 patří do skupiny pacientů či
kontrolních subjektů pomocí Fisherovy lineární diskriminace.
pacienti
kontroly
testovací subjekt
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objem hipokampu
Objemmozkovýchkomor
Příklad – řešení
23
𝐗 𝐷 =
2 12
4 10
3 8
, 𝐗 𝐻 =
5 7
3 9
4 5
𝐱0 = 3,5 9
ത𝐱 𝐷 = 3 10
ത𝐱 𝐻 = 4 7
𝐒 𝐷 = 𝐒 𝐻 =
1 −1
−1 4
Koriťáková: Analýza a klasifikace dat
-4 -2 0 2 4 6 8 10 12
0
2
4
6
8
10
12
x1
x2
pacienti
kontroly
testovací subjekt
centroid pacientů
centroid kontrol
24Koriťáková: Analýza a klasifikace dat
Příprava nových učebních materiálů
pro obor Matematická biologie
je podporována projektem OPVK
č. CZ.1.07/2.2.00/28.0043
„Interdisciplinární rozvoj studijního
oboru Matematická biologie“