import numpy as np
import pandas as pd
import mlutils
import matplotlib.pyplot as plt
%pylab inline

"""
Explanation: Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva  
Strojno učenje 2019/2020
http://www.fer.unizg.hr/predmet/su

Laboratorijska vježba 3: Stroj potpornih vektora i algoritam k-najbližih susjeda
Verzija: 0.4
Zadnji put ažurirano: 27. rujna 2019.
(c) 2015-2019 Jan Šnajder, Domagoj Alagić  
Objavljeno: 30. rujna 2019.
Rok za predaju: 2. prosinca 2019. u 07:00h

Upute
Treća laboratorijska vježba sastoji se od sedam zadataka. U nastavku slijedite upute navedene u ćelijama s tekstom. Rješavanje vježbe svodi se na dopunjavanje ove bilježnice: umetanja ćelije ili više njih ispod teksta zadatka, pisanja odgovarajućeg kôda te evaluiranja ćelija. 
Osigurajte da u potpunosti razumijete kôd koji ste napisali. Kod predaje vježbe, morate biti u stanju na zahtjev asistenta (ili demonstratora) preinačiti i ponovno evaluirati Vaš kôd. Nadalje, morate razumjeti teorijske osnove onoga što radite, u okvirima onoga što smo obradili na predavanju. Ispod nekih zadataka možete naći i pitanja koja služe kao smjernice za bolje razumijevanje gradiva (nemojte pisati odgovore na pitanja u bilježnicu). Stoga se nemojte ograničiti samo na to da riješite zadatak, nego slobodno eksperimentirajte. To upravo i jest svrha ovih vježbi.
Vježbe trebate raditi samostalno. Možete se konzultirati s drugima o načelnom načinu rješavanja, ali u konačnici morate sami odraditi vježbu. U protivnome vježba nema smisla.
End of explanation
"""


from sklearn.svm import SVC

seven_X = np.array([[2,1], [2,3], [1,2], [3,2], [5,2], [5,4], [6,3]])
seven_y = np.array([1, 1, 1, 1, -1, -1, -1])

# Vaš kôd ovdje

"""
Explanation: 1. Klasifikator stroja potpornih vektora (SVM)
(a)
Upoznajte se s razredom svm.SVC, koja ustvari implementira sučelje prema implementaciji libsvm. Primijenite model SVC s linearnom jezgrenom funkcijom (tj. bez preslikavanja primjera u prostor značajki) na skup podataka seven (dan niže) s $N=7$ primjera. Ispišite koeficijente $w_0$ i $\mathbf{w}$. Ispišite dualne koeficijente i potporne vektore. Završno, koristeći funkciju mlutils.plot_2d_svc_problem iscrtajte podatke, decizijsku granicu i marginu. Funkcija prima podatke, oznake i klasifikator (objekt klase SVC). 
Izračunajte širinu dobivene margine (prisjetite se geometrije linearnih modela).
End of explanation
"""


from sklearn.metrics import hinge_loss

# Vaš kôd ovdje

"""
Explanation: Q: Koliko iznosi širina margine i zašto?
Q: Koji primjeri su potporni vektori i zašto?
(b)
Definirajte funkciju hinge(model, x, y) koja izračunava gubitak zglobnice modela SVM na primjeru x. Izračunajte gubitke modela naučenog na skupu seven za primjere $\mathbf{x}^{(2)}=(3,2)$ i $\mathbf{x}^{(1)}=(3.5,2)$ koji su označeni pozitivno ($y=1$) te za $\mathbf{x}^{(3)}=(4,2)$ koji je označen negativno ($y=-1$). Također, izračunajte prosječni gubitak SVM-a na skupu seven. Uvjerite se da je rezultat identičan onome koji biste dobili primjenom ugrađene funkcije metrics.hinge_loss.
End of explanation
"""


from sklearn.metrics import accuracy_score

outlier_X = np.append(seven_X, [[12,8]], axis=0)
outlier_y = np.append(seven_y, -1)

unsep_X = np.append(seven_X, [[2,2]], axis=0)
unsep_y = np.append(seven_y, -1)

# Vaš kôd ovdje

"""
Explanation: (c)
Vratit ćemo se na skupove podataka outlier ($N=8$) i unsep ($N=8$) iz prošle laboratorijske vježbe (dani niže) i pogledati kako se model SVM-a nosi s njima. Naučite ugrađeni model SVM-a (s linearnom jezgrom) na ovim podatcima i iscrtajte decizijsku granicu (skupa s marginom). Također ispišite točnost modela korištenjem funkcije metrics.accuracy_score.
End of explanation
"""


# Vaš kôd ovdje

"""
Explanation: Q: Kako stršeća vrijednost utječe na SVM?
Q: Kako se linearan SVM nosi s linearno neodvojivim skupom podataka?
2. Nelinearan SVM
Ovaj zadatak pokazat će kako odabir jezgre utječe na kapacitet SVM-a. Na skupu unsep iz prošlog zadatka trenirajte tri modela SVM-a s različitim jezgrenim funkcijama: linearnom, polinomijalnom i radijalnom baznom (RBF) funkcijom. Varirajte hiperparametar $C$ po vrijednostima $C\in{10^{-2},1,10^2}$, dok za ostale hiperparametre (stupanj polinoma za polinomijalnu jezgru odnosno hiperparametar $\gamma$ za jezgru RBF) koristite podrazumijevane vrijednosti. Prikažite granice između klasa (i margine) na grafikonu organiziranome u polje $3x3$, gdje su stupci različite jezgre, a retci različite vrijednosti parametra $C$.
End of explanation
"""


from sklearn.metrics import accuracy_score, zero_one_loss

def grid_search(X_train, X_validate, y_train, y_validate, c_range=(0,5), g_range=(0,5), error_surface=False):
    pass

"""
Explanation: 3. Optimizacija hiperparametara SVM-a
Pored hiperparametra $C$, model SVM s jezgrenom funkcijom RBF ima i dodatni hiperparametar $\gamma=\frac{1}{2\sigma^2}$ (preciznost). Taj parametar također određuje složenost modela: velika vrijednost za $\gamma$ znači da će RBF biti uska, primjeri će biti preslikani u prostor u kojem su (prema skalarnome produktu) međusobno vrlo različiti, što će rezultirati složenijim modelima. Obrnuto, mala vrijednost za $\gamma$ znači da će RBF biti široka, primjeri će biti međusobno sličniji, što će rezultirati jednostavnijim modelima. To ujedno znači da, ako odabremo veći $\gamma$, trebamo jače regularizirati model, tj. trebamo odabrati manji $C$, kako bismo spriječili prenaučenost. Zbog toga je potrebno zajednički optimirati hiperparametre $C$ i $\gamma$, što se tipično radi iscrpnim pretraživanjem po rešetci (engl. grid search). Ovakav pristup primjenjuje se kod svih modela koji sadrže više od jednog hiperparametra.
(a)
Definirajte funkciju 

grid_search(X_train, X_validate, y_train, y_validate, c_range=(c1,c2), g_range=(g1,g2), error_surface=False) 

koja optimizira parametre $C$ i $\gamma$ pretraživanjem po rešetci. Funkcija treba pretražiti hiperparametre $C\in{2^{c_1},2^{c_1+1},\dots,2^{c_2}}$ i $\gamma\in{2^{g_1},2^{g_1+1},\dots,2^{g_2}}$. Funkcija treba vratiti optimalne hiperparametre $(C^,\gamma^)$, tj. one za koje na skupu za provjeru model ostvaruju najmanju pogrešku. Dodatno, ako je surface=True, funkcija treba vratiti matrice (tipa ndarray) pogreške modela (očekivanje gubitka 0-1) na skupu za učenje i skupu za provjeru. Svaka je matrica dimenzija $(c_2-c_1+1)\times(g_2-g_1+1)$ (retci odgovaraju različitim vrijednostima za $C$, a stupci različitim vrijednostima za $\gamma$).
End of explanation
"""


from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split

# Vaš kôd ovdje

"""
Explanation: (b)
Pomoću funkcije datasets.make_classification generirajte dva skupa podataka od $N=200$ primjera: jedan s $n=2$ dimenzije i drugi s $n=100$ dimenzija. Primjeri neka dolaze iz dviju klasa, s time da svakoj klasi odgovaraju dvije grupe (n_clusters_per_class=2), kako bi problem bio nešto složeniji, tj. nelinearniji. Neka sve značajke budu informativne. Podijelite skup primjera na skup za učenje i skup za ispitivanje u omjeru 1:1.
Na oba skupa optimirajte SVM s jezgrenom funkcijom RBF, u rešetci $C\in{2^{-5},2^{-4},\dots,2^{15}}$ i $\gamma\in{2^{-15},2^{-14},\dots,2^{3}}$. Prikažite površinu pogreške modela na skupu za učenje i skupu za provjeru, i to na oba skupa podataka (ukupno četiri grafikona) te ispišite optimalne kombinacije hiperparametara. Za prikaz površine pogreške modela možete koristiti funkciju mlutils.plot_error_surface.
End of explanation
"""


from sklearn.datasets import make_classification

X, y = make_classification(n_samples=500,n_features=2,n_classes=2,n_redundant=0,n_clusters_per_class=1, random_state=69)
X[:,1] = X[:,1]*100+1000
X[0,1] = 3000

mlutils.plot_2d_svc_problem(X, y)

"""
Explanation: Q: Razlikuje li se površina pogreške na skupu za učenje i skupu za ispitivanje? Zašto?
Q: U prikazu površine pogreške, koji dio površine odgovara prenaučenosti, a koji podnaučenosti? Zašto?
Q: Kako broj dimenzija $n$ utječe na površinu pogreške, odnosno na optimalne hiperparametre $(C^, \gamma^)$?
Q: Preporuka je da povećanje vrijednosti za $\gamma$ treba biti popraćeno smanjenjem vrijednosti za $C$. Govore li vaši rezultati u prilog toj preporuci? Obrazložite.  
4. Utjecaj standardizacije značajki kod SVM-a
U prvoj laboratorijskoj vježbi smo pokazali kako značajke različitih skala mogu onemogućiti interpretaciju naučenog modela linearne regresije. Međutim, ovaj problem javlja se kod mnogih modela pa je tako skoro uvijek bitno prije treniranja skalirati značajke, kako bi se spriječilo da značajke s većim numeričkim rasponima dominiraju nad onima s manjim numeričkim rasponima. To vrijedi i za SVM, kod kojega skaliranje nerijetko može znatno poboljšati rezultate. Svrha ovog zadataka jest eksperimentalno utvrditi utjecaj skaliranja značajki na točnost SVM-a.
Generirat ćemo dvoklasni skup od $N=500$ primjera s $n=2$ značajke, tako da je dimenzija $x_1$ većeg iznosa i većeg raspona od dimenzije $x_0$, te ćemo dodati jedan primjer koji vrijednošću značajke $x_1$ odskače od ostalih primjera:
End of explanation
"""


# Vaš kôd ovdje

"""
Explanation: (a)
Proučite funkciju za iscrtavanje histograma hist. Prikažite histograme vrijednosti značajki $x_0$ i $x_1$ (ovdje i u sljedećim zadatcima koristite bins=50).
End of explanation
"""


from sklearn.preprocessing import MinMaxScaler

# Vaš kôd ovdje

"""
Explanation: (b)
Proučite razred preprocessing.MinMaxScaler. Prikažite histograme vrijednosti značajki $x_0$ i $x_1$ ako su iste skalirane min-max skaliranjem (ukupno dva histograma).
End of explanation
"""


from sklearn.preprocessing import StandardScaler

# Vaš kôd ovdje

"""
Explanation: Q: Kako radi ovo skaliranje? <br>
Q: Dobiveni histogrami su vrlo slični. U čemu je razlika? <br>
(c)
Proučite razred preprocessing.StandardScaler. Prikažite histograme vrijednosti značajki $x_0$ i $x_1$ ako su iste skalirane standardnim skaliranjem (ukupno dva histograma).
End of explanation
"""


# Vaš kôd ovdje

"""
Explanation: Q: Kako radi ovo skaliranje? <br>
Q: Dobiveni histogrami su vrlo slični. U čemu je razlika? <br>
(d)
Podijelite skup primjera na skup za učenje i skup za ispitivanje u omjeru 1:1. Trenirajte SVM s jezgrenom funkcijom RBF na skupu za učenje i ispitajte točnost modela na skupu za ispitivanje, koristeći tri varijante gornjeg skupa: neskalirane značajke, standardizirane značajke i min-max skaliranje. Koristite podrazumijevane vrijednosti za $C$ i $\gamma$. Izmjerite točnost svakog od triju modela na skupu za učenje i skupu za ispitivanje. Ponovite postupak više puta (npr. 30) te uprosječite rezultate (u svakom ponavljanju generirajte podatke kao što je dano na početku ovog zadatka).
NB: Na skupu za učenje treba najprije izračunati parametre skaliranja te zatim primijeniti skaliranje (funkcija fit_transform), dok na skupu za ispitivanje treba samo primijeniti skaliranje s parametrima koji su dobiveni na skupu za učenje (funkcija transform).
End of explanation
"""


from numpy.linalg import norm
from bisect import insort

class KNN:
    def __init__(self, n_neighbors=3):
        # Vaš kôd ovdje
        pass
        
    def fit(self, X_train, y_train):
        # Vaš kôd ovdje
        pass
        
    def predict(self, X_test):
        # Vaš kôd ovdje
        pass

"""
Explanation: Q: Jesu li rezultati očekivani? Obrazložite. <br>
Q: Bi li bilo dobro kada bismo funkciju fit_transform primijenili na cijelom skupu podataka? Zašto? Bi li bilo dobro kada bismo tu funkciju primijenili zasebno na skupu za učenje i zasebno na skupu za ispitivanje? Zašto?
5. Algoritam k-najbližih susjeda
U ovom zadatku promatrat ćemo jednostavan klasifikacijski model imena algoritam k-najbližih susjeda. Najprije ćete ga samostalno isprogramirati kako biste se detaljno upoznali s radom ovog modela, a zatim ćete prijeći na analizu njegovih hiperparametara (koristeći ugrađeni razred, radi efikasnosti).
(a)
Implementirajte klasu KNN, koja implementira algoritam $k$ najbližih susjeda. Neobavezan parametar konstruktora jest broj susjeda n_neighbours ($k$), čija je podrazumijevana vrijednost 3. Definirajte metode fit(X, y) i predict(X), koje služe za učenje modela odnosno predikciju. Kao mjeru udaljenosti koristite euklidsku udaljenost (numpy.linalg.norm; pripazite na parametar axis). Nije potrebno implementirati nikakvu težinsku funkciju.
End of explanation
"""


from sklearn.datasets import make_classification
X_art, y_art = make_classification(n_samples=100, n_features=2, n_classes=2, 
                                   n_redundant=0, n_clusters_per_class=2,
                                   random_state=69)
mlutils.plot_2d_clf_problem(X_art, y_art)

from sklearn.neighbors import KNeighborsClassifier

# Vaš kôd ovdje

"""
Explanation: (b)
Kako biste se uvjerili da je Vaša implementacija ispravna, usporedite ju s onom u razredu neighbors.KNeighborsClassifier. Budući da spomenuti razred koristi razne optimizacijske trikove pri pronalasku najboljih susjeda, obavezno postavite parametar algorithm=brute, jer bi se u protivnom moglo dogoditi da Vam se predikcije razlikuju. Usporedite modele na danom (umjetnom) skupu podataka (prisjetite se kako se uspoređuju polja; numpy.all).
End of explanation
"""


# Vaš kôd ovdje

"""
Explanation: 6. Analiza algoritma k-najbližih susjeda
Algoritam k-nn ima hiperparametar $k$ (broj susjeda). Taj hiperparametar izravno utječe na složenost algoritma, pa je stoga izrazito važno dobro odabrati njegovu vrijednost. Kao i kod mnogih drugih algoritama, tako i kod algoritma k-nn optimalna vrijednost hiperametra $k$ ovisi o konkretnom problemu, uključivo broju primjera $N$, broju značajki (dimenzija) $n$ te broju klasa $K$. 
Kako bismo dobili pouzdanije rezultate, potrebno je neke od eksperimenata ponoviti na različitim skupovima podataka i zatim uprosječiti dobivene vrijednosti pogrešaka. Koristite funkciju: mlutils.knn_eval koja trenira i ispituje model k-najbližih susjeda na ukupno n_instances primjera, i to tako da za svaku vrijednost hiperparametra iz zadanog intervala k_range ponovi n_trials mjerenja, generirajući za svako od njih nov skup podataka i dijeleći ga na skup za učenje i skup za ispitivanje. Udio skupa za ispitivanje definiran je parametrom test_size. Povratna vrijednost funkcije jest četvorka (ks, best_k, train_errors, test_errors). Vrijednost best_k je optimalna vrijednost hiperparametra $k$ (vrijednost za koju je pogreška na skupu za ispitivanje najmanja). Vrijednosti train_errors i test_errors  liste su pogrešaka na skupu za učenja odnosno skupu za testiranje za sve razmatrane vrijednosti hiperparametra $k$, dok ks upravo pohranjuje sve razmatrane vrijednosti hiperparametra $k$.
(a)
Na podatcima iz zadatka 5, pomoću funkcije mlutils.plot_2d_clf_problem iscrtajte prostor primjera i područja koja odgovaraju prvoj odnosno drugoj klasi. Ponovite ovo za $k\in[1, 5, 20, 100]$. 
NB: Implementacija algoritma KNeighborsClassifier iz paketa scikit-learn vjerojatno će raditi brže od Vaše implementacije, pa u preostalim eksperimentima koristite nju.
End of explanation
"""


# Vaš kôd ovdje

"""
Explanation: Q: Kako $k$ utječe na izgled granice između klasa?
Q: Kako se algoritam ponaša u ekstremnim situacijama: $k=1$ i $k=100$?
(b)
Pomoću funkcije mlutils.knn_eval, iscrtajte pogreške učenja i ispitivanja kao funkcije hiperparametra $k\in{1,\dots,20}$, za $N={100, 250, 750}$ primjera. Načinite 3 zasebna grafikona. Za svaki ispišite optimalnu vrijednost hiperparametra $k$ (najlakše kao naslov grafikona; vidi plt.title).
End of explanation
"""


# Vaš kôd ovdje

"""
Explanation: Q: Kako se mijenja optimalna vrijednost hiperparametra $k$ s obzirom na broj primjera $N$? Zašto?
Q: Kojem području odgovara prenaučenost, a kojem podnaučenost modela? Zašto?
Q: Je li uvijek moguće doseći pogrešku od 0 na skupu za učenje?
(c)
Kako bismo provjerili u kojoj je mjeri algoritam k-najbližih susjeda osjetljiv na prisustvo nebitnih značajki, možemo iskoristiti funkciju datasets.make_classification kako bismo generirali skup primjera kojemu su neke od značajki nebitne. Naime, parametar n_informative određuje broj bitnih značajki, dok parametar n_features određuje ukupan broj značajki. Ako je n_features &gt; n_informative, onda će neke od značajki biti nebitne. Umjesto da izravno upotrijebimo funkciju make_classification, upotrijebit ćemo funkciju mlutils.knn_eval, koja samo preuzime ove parametre, ali nam omogućuje pouzdanije procjene.
Koristite funkciju mlutils.knn_eval na dva načina. U oba koristite $N=1000$ primjera, $n=10$ značajki i $K=5$ klasa, ali za prvi neka su svih 10 značajki bitne, a za drugi neka je bitno samo 5 od 10 značajki. Ispišite pogreške učenja i ispitivanja za oba modela za optimalnu vrijednost $k$ (vrijednost za koju je ispitna pogreška najmanja).
End of explanation
"""


from sklearn.metrics.pairwise import pairwise_distances

# Vaš kôd ovdje

"""
Explanation: Q: Je li algoritam k-najbližih susjeda osjetljiv na nebitne značajke? Zašto?
Q: Je li ovaj problem izražen i kod ostalih modela koje smo dosad radili (npr. logistička regresija)?
Q: Kako bi se model k-najbližih susjeda ponašao na skupu podataka sa značajkama različitih skala? Detaljno pojasnite.
7. "Prokletstvo dimenzionalnosti"
"Prokletstvo dimenzionalnosti" zbirni je naziv za niz fenomena povezanih s visokodimenzijskim prostorima. Ti fenomeni, koji se uglavnom protive našoj intuiciji, u većini slučajeva dovode do toga da se s porastom broja dimenzija (značajki) smanjenje točnost modela.
Općenito, povećanje dimenzija dovodi do toga da sve točke u ulaznome prostoru postaju (u smislu euklidske udaljenosti) sve udaljenije jedne od drugih te se, posljedično, gube razlike u udaljenostima između točaka. Eksperimentalno ćemo provjeriti da je to doista slučaj. Proučite funkciju metrics.pairwise_distances. Generirajte 100 slučajnih vektora u različitim dimenzijama $n\in[1,2,\ldots,50]$ dimenzija te izračunajte prosječnu euklidsku udaljenost između svih parova tih vektora. Za generiranje slučajnih vektora koristite funkciju numpy.random.random. Na istom grafu skicirajte i krivulju za prosječne kosinusne udaljenosti (parametar metric).
End of explanation
"""


