\(k\) најближих сусједа (\(kNN\))
k-најближих сусједа (енг. k-nearest neighbors algorithm) представља непараметарски метод који се користи за класификацију и регресију. У оба случаја, улаз се састоји од \(k\) најближих тест примјера у функцији простора. Излаз зависи од тога да ли се \(kNN\) користио за класификацију или регресију:
У \(kNN\) класификацији, излаз је члан класе. Објекат се класификује гласовима већине својих суседа, тако да објекат буде распоређен у класу најчешћу међу својим \(k\) најближим сусједима (\(k\) је позитиван цијели број, најчешће мали број). Ако је \(k = 1\), онда се објекат једноставно додељује класи тог једног најближег суседа.
У \(kNN\) регресији, излаз представља вриједност објекта. Ова вриједност представља просјек вриједности његових \(k\) најближих сусједа.
\(kNN\) алгоритам је најједноставнији од свих алгоритама машинског учења.
Додјела тежине доприносима сусједа може бити од користи и за класификацију и за регресију, тако да ближи сусједи доприносе просјеку више у односу на оне удаљеније. На примјер, честа шема доделе је таква да се сваком од сусједа додели тежина од \(1/d\), гдје \(d\) представља растојање од сусједа.
Сусједи се узимају из скупа објеката за које је класа (за \(kNN\) класификацију) или вриједност објекта (за \(kNN\) регресију) позната. Ово се може посматрати као тест скуп за алгоритам иако експлицитни тест кораци нису неопходни.
Мана \(kNN\) алгоритма је та што је осјетљив на локалне структуре података. Алгоритам нема ништа заједничко и не треба га мијешати са кластеризацијом методом к-средњих вриједности, што је друга популарна техника машинског учења.
\(kNN\) алгоритам
Тест примјери су вектори у мултидимензионалној функцији простора, гдје сваки има класну ознаку. Тест фаза алгоритма састоји се у складиштењу будућих вектора и класних ознака тест примјера.
У фази класификације, \(k\) је константа дефинисана од стране корисника, а неозначени вектор (упит или тест примјер) се класификује додјелом ознаке која је најучесталија међу \(k\) тест примјерима најближим датом упиту.
Најчешће се користи Еуклидово растојање за непрекидне променљиве. За дискретне променљиве, нпр. за класификацију текста, користи се другачија техника, као што је на примјер функција раздаљине засноване на преклапању (или Хамингово растојање). У контексту експресије гена микрочип података, \(kNN\) се користи у вези са коефицијентима као што су Пирсон и Спирман.
Стандардно, нека је дато \(X=(x_1,x_2,...,x_n)\) и \(Y=(y_1,y_2,...,y_n)\). Нека \(Y\) има свега \(C\) класа. Опет је циљ наћи одговарајућу оцјену за \[P\{Y=j|X\}=p_j(X), \quad \forall j\in \{1,2,...,C\}.\]
Прије свега фиксирамо број \(k\) и то ће бити баш број сусједа које ћемо посматрати. Након тога за сваки вектор \(x\) и за сваку класу оцјењујемо \(p_j(x)\) на сљедећи начин: \[p_j(x) = \frac{1}{k}\sum_{i=1}^nI\{x_i \in S^k_X\},\] гдје је \(S^k_X\) - скуп најближих у односу на задату метрику \(k\) тачака међу датим у скупу \(X\) одабраној тачки \(x\), која може а и не мора да буде у почетном скупу \(X\).
На крају за дату тачку \(x\) се одабере она класа која је имала највећу вјероватноћу \(p_j(x)\).
Примјер \(kNN\) класификације.
Тест примјер (зелени круг) треба да буде класификован или као прва класа плавих квадрата или као друга класа црвених троуглова. Ако је \(k = 3\) (пуна линија круга), онда је додjељен другој класи јер се унутар унутрашњег круга налазе \(2\) троугла и само један квадрат. Ако је \(k = 5\) (испрекидана линија круга), онда је додјељен првој класи (\(3\) квадрата у односу на \(2\) троугла унутар спољашњег круга).
Примјећујемо да поред зависности од локалне структуре података, \(kNN\) класификатор директно зависи и од параметра k. Стога постоје сљедећи потенцијални проблеми:
- Није јединствена највећа вјероватноћа.
Нпр: имамо \(3\) класе укупно и одабран параметар \(k\) и некој тачки \(x\) је у скупу \(S^k_X\) тачно по један представник из сваке класе.
- Ако је \(k\) превелики број онда свака нова тачка, гдје год да се налазила, сликаће се у исту класу.
Нпр: уколико је дато \(n=100\) тачака и двије могуће класе, с тим да из прве класе имамо \(62\) тачке. Ако је \(k\geq 77\) свака нова тачка ће бити класификована као да је из прве класе.
- Ако је \(k\) премали број, може се много тога опет пореметити због тачака које можда “штрче”.
Нпр: имамо такву слику да су сви из исте класе груписани у некој области, али имамо у тој области једну тачку која је из друге области. Тада за \(k=1\) свака тачка довољно близу баш те неочекиване тачке биће одмах класификована као припадник друге класе.
Примјер 1. У бази \(iris\) налазе се подаци о димензији круничних и чашичних листића за \(3\) различите врсте цвијета љубичице. Подијелити податке на тренинг и тест скуп и извршити одговарајућу класификацију цвјетова.
df <- data(iris)
head(iris) ## Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1 5.1 3.5 1.4 0.2 setosa
## 2 4.9 3.0 1.4 0.2 setosa
## 3 4.7 3.2 1.3 0.2 setosa
## 4 4.6 3.1 1.5 0.2 setosa
## 5 5.0 3.6 1.4 0.2 setosa
## 6 5.4 3.9 1.7 0.4 setosalibrary("caTools")
# Splitting data into train and test data
split <- sample.split(iris, SplitRatio = 0.7)
train_cl <- subset(iris, split == "TRUE")
test_cl <- subset(iris, split == "FALSE")# Feature Scaling
train_scale <- scale(train_cl[, 1:4])
test_scale <- scale(test_cl[, 1:4])library(class)
# Fitting KNN Model to training dataset
classifier_knn <- knn(train = train_scale,
test = test_scale,
cl = train_cl$Species,
k = 1)
classifier_knn## [1] setosa setosa setosa setosa setosa setosa
## [7] setosa setosa setosa setosa setosa setosa
## [13] setosa setosa setosa setosa setosa setosa
## [19] setosa setosa versicolor virginica versicolor versicolor
## [25] versicolor versicolor versicolor versicolor virginica versicolor
## [31] versicolor versicolor versicolor versicolor versicolor versicolor
## [37] versicolor versicolor versicolor versicolor virginica virginica
## [43] virginica virginica virginica virginica virginica versicolor
## [49] virginica virginica virginica virginica virginica versicolor
## [55] virginica virginica virginica virginica virginica virginica
## Levels: setosa versicolor virginica# Confusiin Matrix
cm <- table(test_cl$Species, classifier_knn)
cm## classifier_knn
## setosa versicolor virginica
## setosa 20 0 0
## versicolor 0 18 2
## virginica 0 2 18# Model Evaluation - Choosing K
# Calculate out of Sample error
misClassError <- mean(classifier_knn != test_cl$Species)
print(paste('Accuracy =', 1-misClassError))## [1] "Accuracy = 0.933333333333333"# K = 3
classifier_knn <- knn(train = train_scale,
test = test_scale,
cl = train_cl$Species,
k = 3)
misClassError <- mean(classifier_knn != test_cl$Species)
print(paste('Accuracy =', 1-misClassError))## [1] "Accuracy = 0.933333333333333"# K = 5
classifier_knn <- knn(train = train_scale,
test = test_scale,
cl = train_cl$Species,
k = 5)
misClassError <- mean(classifier_knn != test_cl$Species)
print(paste('Accuracy =', 1-misClassError))## [1] "Accuracy = 0.95"# K = 7
classifier_knn <- knn(train = train_scale,
test = test_scale,
cl = train_cl$Species,
k = 7)
misClassError <- mean(classifier_knn != test_cl$Species)
print(paste('Accuracy =', 1-misClassError))## [1] "Accuracy = 0.966666666666667"# K = 15
classifier_knn <- knn(train = train_scale,
test = test_scale,
cl = train_cl$Species,
k = 15)
misClassError <- mean(classifier_knn != test_cl$Species)
print(paste('Accuracy =', 1-misClassError))## [1] "Accuracy = 0.983333333333333"# K = 19
classifier_knn <- knn(train = train_scale,
test = test_scale,
cl = train_cl$Species,
k = 19)
misClassError <- mean(classifier_knn != test_cl$Species)
print(paste('Accuracy =', 1-misClassError))## [1] "Accuracy = 0.966666666666667"Линеарна дискриминаторна анализа (ЛДА)
Линеарна дискриминаторна анализа је још једна статистичка техника класификације објеката у међусобно различите класе. Нека је опет дато \(X=(x_1,x_2,...,x_n)\) и \(Y=(y_1,y_2,...,y_n)\). Нека \(Y\) има свега \(C\) класа. До сада смо тражили начине да оцијенимо директно сљедећи израз \(P\{Y=j|X\}=p_j(X)\). А можемо то да одрадимо примјеном Бајесове формуле \[P(A|B) = \frac{P(A)P(B|A)}{P(B)},\] гдје ћемо да ставимо \(A=\{Y=j\}\), \(B=\{X=x\}\). Самим тим на крају имамо да је потребно оцијенити све што се јавља са десне стране једнакости \[P\{Y=j|X=x\} = \frac{P\{Y=j\}P\{X=x|Y=j\}}{\sum_{u=1}^C P\{Y=u\}P\{X=x|Y=u\}}.\]
Увешћемо ознаке \(f_j(x) = P\{X=x|Y=j\}\) - неки облик функције густине и \(\pi_j=P\{Y=j\}\) априорне вјероватноће припадања класама. Оцјене за \(\pi_j\) заправо неће бити толико компликоване, јер директно из података можемо да израчунамо \[\hat{\pi}_j = \frac{\sum_{i=1}^n I\{y_i=j\}}{n}, \quad \forall j \in \{1,2,...,C\}.\]
Док за \(f_j(\cdot)\) неће бити толико лако без неких додатних претпоставки. И баш ту долази до суштине Линеарне дискриминаторне анализе - претпостављамо да је \[f_j(\cdot) \sim \mathcal{N}(\mu_j,\sigma_j^2), \quad \forall j \in \{1,2,...,C\}, \] и уз то \(\sigma_1=\sigma_2=...=\sigma_C=\sigma\). Баш због претходне једнакости дисперзија по класама ова метода има у називу “линеарна”. Имамо \[p_j(x) = \frac{\pi_j \frac{1}{\sqrt{2\pi\sigma^2}}\exp{\left(-\frac{1}{2\sigma^2}(x-\mu_j)^2 \right)} }{\sum_{u=1}^C \pi_u\frac{1}{\sqrt{2\pi\sigma^2}}\exp{\left(-\frac{1}{2\sigma^2}(x-\mu_u)^2 \right)} },\] гдје је од непознатих параметара остало само оцијенити \(\sigma\) и \(\mu_j\), \(\forall j\).
Не заборавимо да ћемо и овдје да класификујемо према највећој вјероватноћи \(p_j(\cdot)\). Именилац је увијек исти, стога га можемо игнорисати при оцјењивању, разломак са коријеном се скрати и примијенимо логаритамску функцију на бројиоцу \[z_j(x) = \log (\pi_j) - \frac{(x-\mu_j)^2}{2\sigma^2} = \log (\pi_j) - \frac{x^2-2x\mu_j+\mu_j^2}{2\sigma^2}.\]
Такође, можемо обратити пажњу да ће за сваку класу \(j\) члан \(\frac{x^2}{2\sigma^2}\) бити исти па и њега можемо избацити из разматрања којој класи припада. Тиме на крају добијамо да ћемо класу да бирамо према \[z_j^*(x)= \frac{x\mu_j}{\sigma^2}-\frac{\mu_j^2}{2\sigma^2}+\log (\pi_j).\]
И даље је остало оцијенити параметре. ЛДА метода предлаже сљедеће оцјене параметара:
\[\hat{\mu_j}=\frac{1}{\sum_{i=1}^n I\{y_i=j\}}\sum_{i=1}^n x_i\cdot I\{y_i=j\}, \quad \forall j\in\{1,2,...,C\},\] \[\hat{\sigma}^2 = \frac{1}{n-C}\sum_{u=1}^C\sum_{i=1}^n (x_i-\hat{\mu}_j)^2 \cdot I\{y_i=u\},\] \[\hat{\pi}_j = \frac{\sum_{i=1}^n I\{y_i=j\}}{n}, \quad \forall j \in \{1,2,...,C\},\] \[\hat{z}_j^*(x) = \frac{x\hat{\mu}_j}{\hat{\sigma}^2}-\frac{\hat{\mu}_j^2}{2\hat{\sigma}^2}+\log (\hat{\pi}_j).\]
Све што смо раније извели за ЛДА важи само у случају једног предиктора. У случају да их је више, идеја остаје иста само, као и увијек, значајно се компликује технички дио. Претпоставка о расподјели постаје вишедимензиона нормална са истом коваријационом матрицом по свим класама, али са различитим векторима за параметре средње вриједности.
Квадратна дискриминаторна анализа (КДА)
Квадратна дискриминаторна анализа има исту структуру и претпоставке као и ЛДА до на тачно једну претпоставку мање, а то је баш претпоставка о једнакости дисперзија по класама. У КДА то више не мора да постоји као услов.
Упоређивање метода
Логистичка регресија и ЛДА генерално дјелују поприлично различито, али чак и њихове границе су често веома “блиске”. Како оба на излазу дају границе у облику правих.
КДА за разлику од њих већ може да да и “заобљене” линије као границе за класе.
У случају да имамо нормалност података по класама најбоље је користити ЛДА и КДА. У супротном логистичка или \(kNN\) ће давати боље резултате.
\(kNN\) је изузетно нелинеарна метода (у смислу границе коју генерише) и значајно се разлику од других наведених.
Примјер 2. У бази \(Smarket\) (пакет \(ISLR\)) налазе се подаци о дневном поврату за \(S\&P\) \(500\) акције у периоду између 2001. и 2005. године. Упоредити претходно дефинисане методе за класификацију.
library(ISLR)
library(MASS) #(sadrzi funkcije za "lda" i "qda")
library(class) #(sadrzi funkciju za "knn")
attach(Smarket)
names(Smarket)## [1] "Year" "Lag1" "Lag2" "Lag3" "Lag4" "Lag5"
## [7] "Volume" "Today" "Direction"Погледајмо најприје резултате Линеарне дискриминаторне анализе (ЛДА).
# Poziv u slucaju LDA, se skoro pa ne razlikuje od poziva
# koji smo koristili u funkcijama lm() i glm().
model.lda = lda(Direction ~ Lag1 + Lag2, subset = Year<2005)# S tim sto vise ovde summary(model) ne vraca to sto bismo mi ocekivali.
summary(model.lda)## Length Class Mode
## prior 2 -none- numeric
## counts 2 -none- numeric
## means 4 -none- numeric
## scaling 2 -none- numeric
## lev 2 -none- character
## svd 1 -none- numeric
## N 1 -none- numeric
## call 3 -none- call
## terms 3 terms call
## xlevels 0 -none- list# Najslicniji izlaz dobijamo ako bas pozovemo "model.lda"
model.lda## Call:
## lda(Direction ~ Lag1 + Lag2, subset = Year < 2005)
##
## Prior probabilities of groups:
## Down Up
## 0.491984 0.508016
##
## Group means:
## Lag1 Lag2
## Down 0.04279022 0.03389409
## Up -0.03954635 -0.03132544
##
## Coefficients of linear discriminants:
## LD1
## Lag1 -0.6420190
## Lag2 -0.5135293# Funkcija predict funkcionise skroz identicno kao i ranije.
lda.pred = predict(model.lda, Smarket[Year == 2005, ])# I vidimo da je u ovom slucaju oko 56% dobrih procena.
table(lda.pred$class, Smarket[Year == 2005, ]$Direction)##
## Down Up
## Down 35 35
## Up 76 106mean(lda.pred$class == Smarket[Year == 2005, ]$Direction)## [1] 0.5595238plot(model.lda)
# Slicno pokrecemo za QDA - kvadratnu diskriminatornu analizu.
model.qda = qda(Direction ~ I(Lag1) + I(Lag2), subset = Year<2005)
summary(model.qda)## Length Class Mode
## prior 2 -none- numeric
## counts 2 -none- numeric
## means 4 -none- numeric
## scaling 8 -none- numeric
## ldet 2 -none- numeric
## lev 2 -none- character
## N 1 -none- numeric
## call 3 -none- call
## terms 3 terms call
## xlevels 0 -none- listmodel.qda## Call:
## qda(Direction ~ I(Lag1) + I(Lag2), subset = Year < 2005)
##
## Prior probabilities of groups:
## Down Up
## 0.491984 0.508016
##
## Group means:
## I(Lag1) I(Lag2)
## Down 0.04279022 0.03389409
## Up -0.03954635 -0.03132544qda.pred = predict(model.qda, Smarket[Year == 2005, ])# I vidimo da je ovde dosta bolje sto se predikcija tice,
# cak 60% je pogodjeno tacno, sto je veliki
# uspjeh racunajuci da procjenjujemo kretanje cijena na berzi.
table(qda.pred$class, Smarket[Year == 2005, ]$Direction)##
## Down Up
## Down 30 20
## Up 81 121mean(qda.pred$class == Smarket[Year == 2005, ]$Direction)## [1] 0.5992063# KNN - k najblizih susjeda
# Za nju nam je potrebno prvo da napravimo odgovarajuce matrice.
# Matrica koja sadrzi skup za poducavanje u odgovarajucim prediktorima (lag1 i lag2).
obucavanje.X = cbind(Lag1, Lag2)[Year < 2005, ]
# Matrica koja sadrzi kontrolni skup u odgovarajucim prediktorima.
kontrolni.X = cbind(Lag1, Lag2)[Year == 2005, ]
# Kategorije koje postoje u skupu za obucavanje.
obucavanje.dir = Direction[Year < 2005]
kontrolni.dir = Direction[Year == 2005]
# I sam broj k - koliko najblizih susjeda gledamo.
k = 1# Metodom "probaj pa sta ispadne" mozemo da vidimo da se najbolji rezultat dobije za vrednost k=2, 56% je pogodjeno tacno.
# ali to je i dalje slabije od QDA metode, tako da mozemo da zakljucimo da u slucaju ovog problema najbolju ocjenu
# je dala metoda kvadratne diskrimatorne analize.
model.knn = knn(obucavanje.X, kontrolni.X, obucavanje.dir, k=2)
plot(model.knn)
summary(model.knn)## Down Up
## 119 133mean(model.knn == Smarket[Year == 2005,]$Direction)## [1] 0.5238095table(model.knn, Smarket[Year == 2005,]$Direction)##
## model.knn Down Up
## Down 55 64
## Up 56 77Примјер 3. Претпоставимо да посматрана обиљежја имају сљедеће расподјеле:
\[X_{green} = \mathcal{N} \left( \pmatrix{0.5\\-0.5}, \Sigma\right), \quad X_{red} = \mathcal{N} \left( \pmatrix{-2\\0.7}, \Sigma\right),\] гдје је \[\Sigma = \pmatrix{1 & 0.5\\ 0.5 & 1}.\] Генерисати узорак са претходним својствима, подијелити податке на тренинг и тест скуп и извршити класификацију помоћу ЛДА методе.
library(MASS)
library(ggplot2)
library(grid)
library(gridExtra)# Generate Bivariate Normal Data
set.seed(12345)
bvn=function(m1,m2,sigma1,sigma2,n1,n2){
d1 <- mvrnorm(n1, mu = m1, Sigma = sigma1 )
d2 <- mvrnorm(n2, mu = m2, Sigma = sigma2 )
d=rbind(d1,d2)
colnames(d)=c("X1","X2")
d=data.frame(d)
d$group=c(rep("Red",n1),rep("Green",n2))
list(data = d)
}
m_1 <- c(0.5, -0.5) # mean of the first group
m_2 <- c(-2, 0.7) # mean of the second group
sigma_1 <- matrix(c(1,0.5,0.5,1), nrow=2) # covariance matrix
# The training dataset
data_lda = bvn(m_1,m_2,sigma_1,sigma_1,n1=1500,n2=2000)$data
head(data_lda, 3)## X1 X2 group
## 1 1.0943941 -0.08022845 Red
## 2 1.4497239 -0.22089273 Red
## 3 0.1516277 -0.34094657 Red# Generate Test Dataset
test_lda = bvn(m_1,m_2,sigma_1,sigma_1,n1=100,n2=100)$data
# Scatter Plot of the Generated Dataset
p1=ggplot(data_lda, aes(x=X1, y=X2)) +
geom_point(aes(colour = group)) +
ggtitle("Dataset for LDA")
p1
# LDA
m_lda=lda(group~X1+X2, data=data_lda)
m_lda## Call:
## lda(group ~ X1 + X2, data = data_lda)
##
## Prior probabilities of groups:
## Green Red
## 0.5714286 0.4285714
##
## Group means:
## X1 X2
## Green -1.9873353 0.6966975
## Red 0.5254939 -0.4972749
##
## Coefficients of linear discriminants:
## LD1
## X1 1.1111290
## X2 -0.8491722# The Confusion Matrix
m_lda.pred=predict(m_lda,test_lda)
table(true=test_lda$group, pred=m_lda.pred$class)## pred
## true Green Red
## Green 99 1
## Red 5 95Задаци за самосталан рад
Задатак 1. Генерисати узорак са сљедећим расподјелама:
\[X_{green} = \mathcal{N} \left( \pmatrix{-2\\0.7}, \Sigma_1\right), \quad X_{red} = \mathcal{N} \left( \pmatrix{0.5\\-0.5}, \Sigma_2\right),\] гдје је \[\Sigma_1 = \pmatrix{1 & 0.5\\ 0.5 & 1}, \quad \Sigma_1 = \pmatrix{0.8 & -0.7\\ -0.7 & 0.8}.\] Подијелити податке на тренинг и тест скуп и извршити класификацију.
Задатак 2. У бази \(BreastCancer\) (пакет \(mlbench\)) налазе се подаци о резултатима тумора који је класификован као бенигни или малигни. Подијелити податке на тренинг и тест скуп и извршити класификацију.