Please enable JavaScript.
Coggle requires JavaScript to display documents.
CLASSIFICATION: kNN - Coggle Diagram
CLASSIFICATION: kNN
k NN
k elem più vicini ad x
DIstanza
uso metriche
d(x,x)=0
d(x,x°)> 0 x!=x°
d(x,x°)=d(x°,x)
d(x,x°) <= d(x,x°°)+d(x°°,x°)
distanza euclidea
Effetto di k
iperparametro
k piccolo rende all'over fitting
k grande tende all'under fitting
modelli complessi boundary irregolari (k piccolo)
modelli semplici boundary lisci (k grande)
Complessità
computare distanza O(N M)
N n° punti
M n° dimensioni
trovare i k più vicini
SORT
O(NlogN)
Smarter algorithm (k<<N)
O(N)
BRUTE APPROACH
O(KN)
Faster k NN
Organizzare dati in kd tree
Training
O (MNlogN) building Tree
O(MN) Store Tree
Inference
O(klogN)
kNN extension
modificare funzione di distanza
every p-norm
mahalanobis distance
Altre funzioni nel neighbourhood
MEDIA per la REGRESSIONE
Pesare computazione con la distanza
Problemi
kNN dipende dalla DIMENSIONALITA' di X (M)
RESCALE THE DATA
Standard Normalization
zi =(xi - mu i) / lambda i
COMPUTATA SUI DAT DI TRAIN
Min Max Normalization
z= (xi -min(xi)) / (max(xi)- min(xi))
Metric
NON LOSS
Accuracy
Quanto stiamo facendo bene
la media aggira tra 0 e 1
Matrice Confusione
Precision
TP/TP+FP
quanto siamo precisi nel predirre la classe
Recall
TP/ TP+FN
Quanti elementi veri riesco a predirre
OUTPUT
Regression Task
output quantitaivo
Classification Task
output qualitativo
n° etichette output discreto
vale ancora iid
VARABILI INPUT CATEGORICHE
ONE HOT ENCODING
tutte le categorie sono equidistanti
zi[k] = 1 se k= xi
0 altrimenti
classification task più simile ad una regression task
(posso calcolare 'media')