6  Diskrimininatívne metódy klasifikácie

6.1 Úvod

  • Predpovedanie kvalitatívnej (kategoriálnej) náhodnej premennej sa nazýva klasifikácia.
  • Použitie bežnej (napr. lineárnej) regresie na modelovanie kvalitatívnej odozvy má príliš veľa nevýhod, najmä:
    • konverzia viachodnotovej kvalit. na kvantitatívnu vnúti poradie jej hodnotám,
    • ordinálnej premennej sa konverziou vnúti vzdialenosť medzi hodnotami,
    • binárna premenná sa síce dá zmysluplne reprezentovať hodnotami \{0,1\}, čo sú extrémy pravdepodobnosti, no lineárnou regresiou by vznikli aj predpovede menšie ako 0 a väčšie ako 1.
  • V tomto predmete preberieme metódy klasifikácie založené na modelovaní rozdelenia pravdepodobnosti. Ostatné metódy sú skôr náplňou voliteľného predmetu Hĺbková analýza údajov a strojové učenie v 2.ročníku I-MPM.
  • Pravdepodobnostné klasifikátory sa delia na dve skupiny modelov:
    • diskriminatívne – pomocou podmienenej pravdepodobnosti (napr. logistická regresia, k-najbližších susedov)
    • generatívne – pomocou združeného rozdelenia a Bayesovej vety (napr. lineárna/kvadratická diskriminačná analýza, naivný bayesovský klasifikátor)

6.2 Logistická regresia

6.2.1 Modelovanie pravdepodobnosti

  • Logistickou regresiou modelujeme pravdepodobnosť, že binárna odozva Y (nech \mathcal H(Y)=\{c_1,c_2\}) nadobudne jednu z dvoch hodnôt, teda napríklad Pr[Y=c_1|X].
  • Konkrétne, ak Y je typ prevodovky, hodnota c_1 predstavuje triedu manuálnych prevodoviek a X napr. hmotnosť vozidla.
  • Pri praktickom riešení binárnej klasifikačnej úlohy sa premenná Y prekóduje na zástupnú premennú Y'=\mathbf{1}_{c_1}(Y).
  • Označme pravdepodobnosť ako funkciu p(x)\equiv Pr(Y=c_1|X=x).
  • Štandardne potom predpoveď p(x)>0.5 znamená zatriedenie bodu x do skupiny c_1.
  • Modelovanie p pomocou lineárnej funkcie p(x)= b_1 + b_2x je možné, ale zároveň nevýhodné, pretože vedie k neinterpretovateľným hodnotám.
Príklad (autá)
  • Modelujme vzťah medzi typom prevodovky (odozva) a hmotnosťou vozidla (prediktor) na základe súboru pozorovaní mtcars pomocou lineárnej regresie.
Kód
plot(am ~ wt, mtcars, pch=20, xlim = c(1,6), ylim = c(-0.3,1.3))
lm(am ~ wt, mtcars) |> abline(reg = _, col = 4, lwd = 2)
legend("topright", 
       legend = c("data", "y=1.5-0.35x"),
       pch=c(20,NA), lty=c(0,1), col=c(1,4), lwd = c(NA,2)
  )

6.2.2 Transformácia

  • Riešením je transformovať priamku (lineárnu funkciu) tak, aby sa zmestila do [0,1]:
    1. Aplikovaním exponenciálnej funkcie získame dolné ohraničenie.
    2. Hyperbolickou funkciou f(x)=\frac{x}{x+1} na intervale (0,\infty) dostaneme žiadané ohraničenie (0,1).
  • Pravdepodobnosť je tak vyjadrená tzv. logistickou funkciou p(x) = \frac{e^{b_1 + b_2x}}{1 + e^{b_1 + b_2x}}
  • Platí p\left(-\frac{b_1}{b_2}\right)=0.5 (prah klasifikácie) a s rastúcim |b_2| je prechod cez prah strmší. Konkrétne, po zderivovaní p(x) a úprave dostaneme (so značením \dot{p}=dp/dx) \dot{p}(x) = p(x)\frac{b_2}{1+e^{b_1+b_2x}} takže v bode polovičnej pravdepodobnosti bude smernica dotyčnice \dot{p}\left(-\frac{b_1}{b_2}\right) = \frac{b_2}{4}.
Príklad (autá)
  • Teraz rovnaký vzťah medzi prevodovkou a hmotnosťou vyjadrime pomocou logistickej funkcie so zvolenými hodnotami parametrov.
Kód
plot(am ~ wt, mtcars, pch=20, xlim = c(1,6), ylim = c(-0.3,1.3))
plot(function(x) exp(15-5*x)/(1+exp(15-5*x)), from = 1, to = 6, add=T, col = 4, lwd=2)
abline(h = 0.5, lty="dashed")
abline(a = 15/4+1/2, b=-5/4, lty="dotted", col = 4)
abline(v = 15/5, lty="dotted", col = 4)
legend("topright", 
       legend = c("data", expression(paste(b[1]==15,", ", b[2]==-5))),
       pch=c(20,NA), lty=c(0,1), col=c(1,4), lwd = c(NA,2)
  )

  • Prah klasifikácie (rozhodovacia hranica) pre polovičnú pravdepodobnosť je bode wt=-15/(-5)=3 a dotyčnica v tom bode má sklon \dot{p}(3)=-5/4.

6.2.3 Šanca

  • Vydelením pravdepodobnosti jej doplnkom dostaneme tzv. šancu (odds), čo je hodnota v intervale [0,\infty). Je známa najmä zo stávkovania.
  • Napr. pravdepodobnosť 0.2 zodpovedá šanci \frac{0.2}{1-0.2}=1/4, čiže iba 1 auto s manuálnou prevodovkou ku 4 autám s automatikou.
  • Logaritmus šance (log odds, logit) je lineárnou funkciou argumentu x, \begin{split} \frac{p(x)}{1-p(x)} &= e^{b_1 + b_2x} \\ \ln\left(\frac{p(x)}{1-p(x)}\right) &= b_1 + b_2x \end{split}
  • To znamená, že
    • zvýšenie x o 1 zmení šancu e^{b_2}-násobne,
    • zmena v pravdepodobnosti závisí už aj od hodnoty x (na rozdiel od klasickej lineárnej regresie),
    • ak b_2>0, potom p(x) je rastúca funkcia (a naopak).

6.2.4 Odhad parametrov

  • Odhad parametrov b_1,b_2 by sa dal urobiť nelineárnou metódou najmenších štvorcov, ale lepšie štatistické vlastnosti má všeobecnejšia metóda – metóda maximálnej vierohodnosti.
  • Vierohodnostná funkcia \begin{split} L(b_1,b_2) &= \prod_{i=1}^n Pr(Y'=y'_i|X=x_i) \\ &= \prod_{i=1}^n p(x_i)^{y'_i}\big(1-p(x_i)\big)^{1-y'_i} \\ &= \prod_{i:y'_i=1} p(x_i) \prod_{i:y'_i=0}\big(1-p(x_i)\big) \end{split} vychádza z hustoty Bernouliho rozdelenia (špeciálny prípad binomického, pre jediný pokus).
  • Pri klasických modeloch sa vierohodnostná funkcia zlogaritmuje, derivácie podľa parametrov položia nule a rieši sústava rovníc. Žiaľ tu presné riešenie nedokážeme explicitne vyjadriť, preto sa v takých prípadoch hľadá približné riešenie pomocou Newtonovej metódy: začne štartovacími hodnotami parametrov a podľa veľkosti a smeru gradientu sa pohybuje po povrchu log-vierohodnostnej funkcie.
  • V kontexte logistickej regresie je tento postup rovnaký ako iteračné použitie váženej metódy najmenších štvorcov (iteratively re-weighted least sqares):
    1. Definujme logit funkciu g(p)\equiv\log\frac{p}{1-p}, potom
      • model je v tvare g\big(p(x)\big)=b_1+b_2x,
      • pravdepodobnosť p(x)=g^{-1}(b_1+b_2x) a
      • rozdelenie odozvy Y'|X\sim Binom\Big(1, p(x)\Big) s varianciou V(p)=p(x)\big(1-p(x)\big).
    2. Zdalo by sa, že môžeme priamo urobiť lineárnu regresiu g(Y') podľa X, samozrejme váženú, pretože rozptyl je premenlivý. Problém však je, že g(0)=-\infty a g(1)=\infty.
      Obídeme to Taylorovým rozvojom \begin{split} g(y')\approx z &= g(p) + (y'-p)\dot{g}(p)\\ &= b_1 + b_2 x + (y'-p)\dot{g}(p) \end{split} kde Z sa stane našou pseudo-odozvou. Pritom, ak sú parametre správne, potom platí E[Y'|X=x]=p takže (y'-p) by mal byť šum s nulovou strednou hodnotou avšak s premenlivým rozptylom var[Z|X=x]=var[(Y'-p)\dot{g}(p)|X=x]=\big(\dot{g}(p)\big)^2V(p). Na odhad b_1,b_2 je teda nutné použiť váženú MNŠ.
    3. Iteračný cyklus začína použitím štartovacích hodnôt b_1,b_2 na výpočet hodnôt pseudo-odozvy z_i a ich váh. Tie vzápätí použije na výpočet presnejších hodnôt b_1,b_2 atď.
Príklad (autá)
  • Rovnaký príklad s hmotnosťou wt a typom prevodovky am:
Kód
fit <- glm(am ~ wt, mtcars, family = "binomial")
fit

Call:  glm(formula = am ~ wt, family = "binomial", data = mtcars)

Coefficients:
(Intercept)           wt  
     12.040       -4.024  

Degrees of Freedom: 31 Total (i.e. Null);  30 Residual
Null Deviance:      43.23 
Residual Deviance: 19.18    AIC: 23.18
Kód
xgrid <- seq(1,6,0.1)
plot(am ~ wt, mtcars, pch=20)
lines(xgrid, 
      predict(fit, newdata = data.frame(wt = xgrid), type = "response"), 
      col = 4, lwd = 2)
legend("topright", 
       legend = c("data", expression(paste(b[1]==12,", ", b[2]==-4))),
       pch=c(20,NA), lty=c(0,1), col=c(1,4), lwd = c(NA,2)
  )

  • Výstup funkcie glm obsahuje tzv. null deviance a residual deviance.
    • (Reziduálna) deviancia D je rozdiel medzi log-vierohodnostnými funkciami saturovaného modelu (dokonale priliehajúceho k dátam) a odhadnutého modelu. A keďže likelihood funkcia saturovaného modelu sa rovná jednej, jej logaritmus je nulový, potom residual deviance D = -2 \log L(\hat{b}_1, \hat{b}_2) je vždy väčšia ako nula, nanajvýš rovná nule (ak je model dokonalý).
    • Naproti tomu null deviance je referenčnou hodnotou zodpovedajúcou základnému modelu (bez prediktorov) D_0 = -2 \log L(\hat{b}_1|b_2=0).
    • Násobok 2 zabezpečuje deviancii (asymptoticky) \chi^2 rozdelenie pravdepodobnosti.
  • Akaikeho inf. kritérium AIC je iba miera vychádzajúca z deviancie a penalizujúca zložitejšie modely, AIC = D + 2k, kde k je počet parametrov modelu, v poslednom príklade k=2. Preferujeme model s čo najnižším AIC.

6.2.5 Multinomická logistická regresia

  • Logistická regresia sa dá použiť aj na klasifikovanie odozvy do viac ako dvoch tried. Jedna z tried pritom môže byť zvolená ako referenčná.
  • Ak za referenčnú zvolíme poslednú zo všetkých K tried, potom pre k=1,\ldots,K-1 platí \begin{split} Pr[Y=c_k|X=x] &= \frac{e^{b_{k1} + b_{k2}x}}{1 + \sum_{l=1}^{K-1}e^{b_{l1} + b_{l2}x}}, \\ Pr[Y=c_K|X=x] &= \frac{1}{1 + \sum_{l=1}^{K-1}e^{b_{l1} + b_{l2}x}}, \end{split} čiže \log\left(\frac{Pr[Y=c_k|X=x]}{Pr[Y=c_K|X=x]}\right) = b_{k1} + b_{k2}x, log-šanca medzi ktorýmkoľvek párom tried je lineárnou funkciou prediktoru X. Interpretácia je viazaná na voľbu referenčnej triedy.
  • Alternatívna formulácia, tzv. softmax, nepoužíva referenčnú triedu: \begin{split} Pr[Y=c_k|X=x] &= \frac{e^{b_{k1} + b_{k2}x}}{ \sum_{l=1}^{K}e^{b_{l1} + b_{l2}x}} \qquad \text{pre}\quad k\in\{1,\ldots, K\}, \\ \log\left(\frac{Pr[Y=c_{k_1}|X=x]}{Pr[Y=c_{k_2}|X=x]}\right) &= (b_{k_11}-b_{k_11}) + (b_{k_12}-b_{k_22})x \qquad \text{pre}\quad k_1,k_2\in\{1,\ldots, K\}. \end{split}
Príklad (kosatce)
  • Na základe datasetu iris klasifikujme druh (Species) kosatca podľa šírky korunného lupienku kvetu (Petal.Width).
Kód
# odhad
fit <- nnet::multinom(Species ~ Petal.Width, data = iris, trace = FALSE)

# rozdelenie údajov
ggplot(iris) + aes(x = Petal.Width, y = Species) + 
  geom_boxplot(varwidth = T)

Kód
# súhrn modelu
fit
Call:
nnet::multinom(formula = Species ~ Petal.Width, data = iris, 
    trace = FALSE)

Coefficients:
           (Intercept) Petal.Width
versicolor   -24.08868    31.44849
virginica    -45.20657    44.39249

Residual Deviance: 33.44131 
AIC: 41.44131 
Kód
# zobrazenie pravdepodobností
predict(fit, type = "probs") |> 
  as.data.frame() |> 
  transform(Petal.Width = iris$Petal.Width) |> 
  tidyr::pivot_longer(cols = -Petal.Width, names_to = "Species", values_to = "Prob") |> 
  ggplot() + aes(x = Petal.Width, y = Prob, color = Species, group = Species) + 
  geom_line()

Kód
# klasifikácia
iris |> 
  transform(fit = predict(fit, type = "class")) |> 
  ggplot() + aes(x = Petal.Width) +
  geom_point(aes(y = Species)) + 
  geom_line(aes(y = fit), color = 4, lwd = 1)

6.2.6 Ordinálna logistická regresia

  • Iným názvom aj ordered logit alebo proportional odds logistic regression je ďalším rozšírením logistickej regresie (klasifikácie na tri a viac tried) a využíva zoradenosť úrovní kvalitatívnej odozvy.
  • Oproti multinomickej tak ordinálna LR modeluje šancu, že odozva nadobudne nanajvýš určitú hodnotu oproti tomu, že nadobudne vyššie hodnoty, \log\left(\frac{Pr[Y\leq c_k|X=x]}{Pr[Y>c_k|X=x]}\right) = b_{k1}-b_2x, \qquad \text{pre}\quad k=1,\ldots, K-1
  • Každý z K-1 log-podielov má v lineárnom modeli svoj absolútny člen b_{k1}, avšak parameter pri X si zdieľajú (na rozdiel od MLR). Vďaka tomu je model pomerne jednoduchý (v komplikovanejších prípadoch je však možné použiť zovšeobecnený OLR model).
  • Parametrizácia so znamienkom mínus má význam pre zachovanie štandardnej interpretácie parametra stojaceho pri prediktore.
Príklad (autá)
  • Modelujeme rozdelenie ordinálnej odozvy cyl pomocou prediktoru disp.
Kód
fit <- mtcars |>  
  dplyr::mutate(cyl = ordered(cyl, c("4","6","8"))) |>  
  MASS::polr(cyl ~ disp, data=_)
Warning: glm.fit: fitted probabilities numerically 0 or 1 occurred
Kód
fit
Call:
MASS::polr(formula = cyl ~ disp, data = dplyr::mutate(mtcars, 
    cyl = ordered(cyl, c("4", "6", "8"))))

Coefficients:
     disp 
0.4443344 

Intercepts:
     4|6      6|8 
 64.9643 118.0268 

Residual Deviance: 3.924663 
AIC: 9.924663 
Warning: did not converge as iteration limit reached
  • Kladná hodnota parametra značí, že cyl je rastúcou funkciou prediktoru disp. Konkrétne, s nárastom zdvihového objemu o 1 jednotku (inch3) sa šanca nižších tried voči vyšším zmení (e^{-0.444}=0.6)-násobne, čiže klesne.
  • Skonštruujme predpoveď počtu valcov pre motor so zdvihovým objemom 150 inch3: \begin{split} logit\big(Pr[cyl\leq 4|disp=150]\big) &= 65.0 - 0.444\cdot150 = -1.6 \\ Pr[cyl\leq 4|disp=150] &= \frac{e^{-1.6}}{1+e^{-1.6}} = 0.168 \\ Pr[cyl\leq 6|disp=150] &= \frac{e^{118.0-0.444\cdot150}}{1+e^{118.0-0.444\cdot150}} \approx 1 \end{split} potom pravdepodobnosti jednotlivých tried \begin{split} Pr[cyl = 4|disp=150] &= Pr[cyl \leq 4|disp=150] = 0.168 \\ Pr[cyl = 6|disp=150] &= Pr[cyl \leq 6|disp=150] - Pr[cyl \leq 4|disp=150] = 0.832 \\ Pr[cyl = 8|disp=150] &= 1 - Pr[cyl \leq 6|disp=150] \approx 0 \end{split} takže E[cyl|disp=150]=6 valcov.
Kód
xnew <- seq(min(mtcars$disp), max(mtcars$disp), length.out = 100)
layout(rbind(1,2), heights = c(5,3))
old <- par(oma=c(3, 3, 3, 3), mar=c(1, 4, 0, 0))

plot(cyl ~ disp, mtcars, axes=F, pch=20)
lines(x = xnew, 
      y = as.numeric(as.character(predict(fit, newdata = list(disp = xnew)))), 
      col = 4, lwd=2)
legend("right", c("data","model"), lty=c(NA,1), lwd=c(NA,2), col=c(1,4), pch = c(20,NA))
axis(2); par(mar=c(4, 4, 0, 0))
matplot(xnew, predict(fit, newdata = list(disp = xnew), type = "p"),
        xlab = "disp", ylab = "pravdep.", type= "l", lty = 2, axes = F)
legend("right", c("Pr[Y=4]","Pr[Y=6]","Pr[Y=8]"), lty=2, col=1:3, bty="n")
axis(1); axis(2)

Kód
layout(rbind(1))
par(old)

6.3 k-najbližších susedov

  • Neparametrickou alternatívou ku logistickej regresii v diskriminatívnom prístupe ku klasifikačnej úlohe je metóda \kappa-najbližších susedov (kNN), ktorú poznáme už z regresnej úlohy.
  • Nech \mathcal{N}_\kappa je množina indexov \kappa pozorovaní (trénovacej vzorky), ktoré sa nachádzajú v najbližšom okolí bodu x v zmysle euklidovskej vzdialenosti.
  • kNN klasifikátor odhaduje podmienenú pravdepodobnosť triedy c_j ako podiel počtu bodov v okolí x, ktorých hodnota odozvy je rovná c_j, čiže Pr[Y=c_j|X=x]=\frac1\kappa\sum_{i\in\mathcal{N}_{\kappa}}I(y_i=c_j)
  • Zatriedenie do skupiny sa potom vykoná klasicky, podľa najvyššej pravdepodobnosti.
Ilustrácia (\kappa-najbližších susedov)
  • Príklad s dvomi prediktormi, dvomi triedami a tromi susedmi: zeleným kruhom je znázornené okolie bodu x, čiernou krivkou rozhodovacia hranica medzi modrou a žltou triedou.
  • Pretože sa príslušnosť do množiny susedov \mathcal{N}_\kappa meria euklidovskou vzdialenosťou, musia byť pre p\geq2 hodnoty prediktorov normované (štandardizované, t.j. centrované s jednotkovým rozptylom).
  • Flexibilita modelu klesá s rastom počtu susedov.
Ilustrácia (počet susedov)
  • Na nasledujúcom ilustračnom obrázku vľavo je \kappa=1, v pravo \kappa=100, fialovou prerušovanou čiarou je znázornená najlepšia (tzv. Bayesova) rozhodovacia hranica.

  • Často používaným pravidlom pre ad-hoc voľbu počtu susedov je \kappa\approx\sqrt{n}. Ku ešte menšej testovacej chybe modelu vedú rôzne metódy resamplingu ako napr. dobre známa krížová validácia.
Príklad (autá)

Jeden prediktor, dve triedy, dataset mtcars.

Kód
# Funkcia na výpočet podmienených pravdepodobností:
knn.prob <- Vectorize(
  FUN = function(x, vx, vy, k) {
    x |> (`-`)(vx) |> abs() |> sort(index.return=T) |> getElement("ix") |> head(k) |> (`[`)(x=vy, i=_) |> mean()
    },
  vectorize.args = "x"
)
# použitie: knn.prob(6, mtcars$wt, mtcars$am, k=5)

# klasifikácia a výpočet pravdepodobností: 
pred <- data.frame(wt = seq(1,6,0.01)) |>
  transform(
    clas = class::knn(train = cbind(mtcars$wt),  # prediktory (ako matica plánu)
                      test = cbind(wt),  # nové hodnoty prediktorov
                      cl = as.factor(mtcars$am),  # odozva (triedy)
                      k = 5   # počet susedov, floor(sqrt(nrow(mtcars)))
                      ) |> as.character() |> as.numeric(),  # factor to number
    prob = knn.prob(wt, vx = mtcars$wt, vy = mtcars$am, k = 5)
  )

# zobrazenie:
ggplot(mtcars) + aes(x = wt) + geom_point(aes(y = am)) +
  geom_line(aes(y = prob), data = pred, color = 4) + 
  ggtitle("Pravdepodobnosť") +
  ylim(-0.1, 1.1)
ggplot(mtcars) + aes(x = wt) + geom_point(aes(y = am)) +
  geom_line(aes(y = clas), data = pred, color = 4) + 
  ggtitle("Klasifikácia") +
  ylim(-0.1, 1.1)

Príklad (kosatce)
  • Dva prediktory a tri triedy na datasete iris.
  • Tentokrát použijeme sofistikovanejšie nástroje – z balíka caret.
Kód
# trénovanie (k=9 zvolené pomocou resamplingu)
fit <- caret::train(Species ~ Petal.Length + Petal.Width, data = iris, 
             method = "knn",
             preProcess = c("center", "scale")
             )
# predpovede a zobrazenie
xgrid <- expand.grid(Petal.Length = seq(0.8,7.2,0.05), 
                     Petal.Width = seq(0,2.7,0.05))
fit |> 
  predict(newdata = xgrid, "prob") |> 
  cbind(xgrid) |> 
  dplyr::select(-setosa, -virginica) |> 
  dplyr::rename(prob_versicolor = versicolor) |> 
  ggplot() + aes(x = Petal.Length, y = Petal.Width) +
  geom_contour_filled(aes(z = prob_versicolor, colour = prob_versicolor), alpha = 0.5) +
  geom_point(aes(shape = Species), data = iris) + ggtitle("Pravdepodobnosť pre versicolor")
fit |> 
  predict(newdata = xgrid, "raw") |> 
  cbind(Species = _, xgrid) |> 
  ggplot() + aes(x = Petal.Length, y = Petal.Width) +
  geom_tile(aes(fill = Species), alpha = 0.3) +
  geom_point(aes(color = Species), data = iris) + 
  ggtitle("Klasifikácia")