# Uczenie Maszynowe Projekt

###### tags: `UMA`

Jakub Strykowski, Jan Retkowski

<!-- ## :memo: Wymaganie Projektu:
Projekt Wstępny powinien zawierać:
1. opis projektu, wskazujący na zrozumienie problemu
2. precyzyjny opis algorytmów, które będą wykorzystane, wraz z przykładowymi obliczeniami (opcjonalnie)
3. plan eksperymentów, który może się zmienić - nie musi być ostateczny
4. dokładnie opisane zbiory danych, które będą używane do badań, należy określić jak zostanie wyłoniony i użyty zbiór trenujący.
5. Dokumentację wstępną należy wysłać mailem. -->

- Auto-generated Table of Content
[ToC]

### 1. Opis projektu
Projekt ma na celu projektu jest określanie jakości transmisji Quality of Transmission (QoT) w sieciach optycznych bazując na parametrze OSNR(ang. Optical Siganl to Noise Ratio, stosunek sygnału do szumu). Jest to ważne zagadnienie, ponieważ wpływa to na jakość światczenia usług. Topologia sieci oraz zapotrzebowania zostaną pobrane z strony http://sndlib.zib.de/home.action, gdzie w plikach wejściowych mamy podane ścieżki pomiędzy miastami.


Przyjmujemy w projekcie, że tłumienie w przewodzie optycznym wynosi 0.3 dB/km, moc początkową sygnału dobierzemy tak, aby dane w projecie były dobrą bazą do nauki modelu. Generujemy połączenie lub kanał opytyczny dla każdej pary Polskich miast, 12 węzłów, takich połączeń jest 66. Dla każdego zapotrzebowania generujemy ściezki, conajmniej 5. Znając dlugość ściężki jesteśmy w stanie wyliczyć OSNR w pięci zakresach. Każda ścieżka ma zostać skatalogowana do odpowiedzniego zakresu, w tym celu użyjemy algorytmów uczenia maszynowego.


Lista węzłów sieci, z podanymi koordynatami, które zostaną wykorzystane do policzenia odległości


Lista linków (połączeń pomiędzy węzłami). Każdy Link ma swoje Id, które jest wykorzystywane w przy alokacji.


Lista demans (żądania) opisuje wartości przepływu, które są potrzebne pomiędzy poszczególnymi miastami.


Lista dopuszczalnych ścieżek w zeleżności od Demand. Zawiera ona listę łączych dla poczszególnych demandów. Wybór optymalnej ścieżki jest problemem trudnym, więc zostanie w tym projekcie pominięty. Przyjmiemy twarde, założenie, że staramy się routować najkrótszą ścieżaką, nawet jak dla obciążenia sieci nie będzie to optymalne. Dzięki temu założeniu będzidziemy w stanie lepiej zobaczyć zależności związane z OSNR, który zależy dystansu.
### 2. Algorytmy

#### 1. Regresja logistyczna
Regresja logistyczna jest klasyfikatorem binarnym. W celu klasyfikacji wektory poddawane są transformcji linowej, następnie sprowadzane do zakresu [0, 1] przez transformację logistyczną, a na koniec klasyfikowane na podstawie progu. Trening odbywa się poprzez optymalizację funkcji logarytmicznej (log-likelihood) W przypadku, gdy istneją więcej niż 2 klasy, można zbudować wiele modeli binarnych i zastosować metodę rozstrzygania one-vs-all lub one-vs-one. Innym możliwym podejściem zastosowanie wielomianowej regresji logistycznej. W tym przypadku funkcją straty jest entropia krzyżowa. W celu przeciwdziałania przeuczaniu można dodatkowo zastosować regularyzację $l_1$ oraz $l_2$ podczas uczenia.

#### 2. Maszyna wektorów nośnych (SVM)

Maszyna wektorów nośnych jest klasyfikatorem binarnym. Trenowanie sprowadza się do maksymalizacji funkcji wyrażającej szerokość marginesu wyrażonego wzorem $\text{arg max}\; \frac{2}{||w||}$, gdzie $w$ to wektor prostopadły do hiperpłaszczyzny dzielądzej zbiory oraz $y_i(x_i \bullet w + b) \geq 1 - \xi_i$ i $\xi_i \geq 0$

Następnie można zastowować przekształcenia w celu ułatwienia dalszych obliczeń:
$\text{arg max}\; \frac{2}{||w||} \Rightarrow\text{arg min}\; ||w|| \Rightarrow \text{arg min}\; \frac{1}{2}||w||^2$

Dodatkowo by dozwolić na wykonywanie pomyłek, należy uwzględnić parametr $\xi$ reprezentujący wielkość owej pomyłki.
$\text{arg min}\; \frac{1}{2}||w||^2 + C \sum_{i=0}^{n} \xi_i$, gdzie $C$ to hiperparametr (czułość na pomyłki)

By rozwiązać problem optymalizacji z ograniczeniami należy zapisać powyższe wyrażenie z zastosowaniem mnożników Lagrange'a:
$L = \frac{1}{2}||w||^2 + C \sum_{i=0}^{n} \xi_i - \sum_{i=0}^{n} \alpha_i [y_i(x_i \bullet w + b) - 1 + \xi_i)] - \sum_{i=0}^{n} \lambda_i \xi_i$, gdzie $\alpha_i,\lambda_i \geq 0$

Rozwiązaniem jest punkt w którym pochodne cząstkowe lagrangianu przyjmują wartość 0
$\frac{\partial{L}}{\partial{w}} = w - \sum_{i=0}^{n} \alpha_i x_i y_i = 0 \Rightarrow w = \sum_{i=0}^{n} \alpha_i x_i y_i$ \
$\frac{\partial{L}}{\partial{b}} = -\sum_{i=0}^{n} \alpha_i y_i = 0 \Rightarrow \sum_{i=0}^{n} \alpha_i y_i = 0$ \
$\frac{\partial{L}}{\partial{\xi}} = \sum_{i=0}^{n} C - \sum_{i=0}^{n} \alpha_i - \sum_{i=0}^{n} \lambda_i = 0 => C - \alpha_i - \lambda_i = 0 \Rightarrow \lambda_i = C - \alpha_i$

Jako że $\alpha_i,\lambda_i \geq 0$, to $0 \leq C - \alpha_i \; \land 0 \leq \alpha_i \Rightarrow 0 \leq \alpha_i \leq C$

Po podstawieniu zmiennych postać lagrangianu wygląda następująco: \
$L = \frac{1}{2} \sum_{i=0}^{n} \alpha_i - \sum_{i=0}^{n} \sum_{j=0}^{n} \alpha_i \alpha_j y_i y_j x_i \bullet x_j$

Ostatnim krokiem wyprowadzenia jest zastosowanie funkcji $K(x_i, w) = \langle\ \phi(x_i), \phi(w)\rangle$, gdzie $\langle\ \phi(x_i), \phi(w)\rangle$, to produkt wewnętrzny wektrów po przeksztełceniu $\phi(x)$

$L = \frac{1}{2} \sum_{i=0}^{n} \alpha_i - \sum_{i=0}^{n} \sum_{j=0}^{n} \alpha_i \alpha_j y_i y_j K(x_i, x_j)$ \
$w = \sum_{i=0}^{n} \alpha_i \phi(x_i) y_i$ \
$b = \text{mean}( \ y_i - w \bullet x_k\ ) = \text{mean}( \ y_k - \sum_{i=0}^{n} \alpha_i y_i \langle\ \phi(x_i), \phi(x_k)\ \rangle\ )$

Taki lagrangian należy następnie zmaksymalizować stosując sie do wcześniej wyznaczonych ograniczeń. Wynik będzie ograniczeniem dolnym wcześniejszego problemu minimalizacji. Wektory $x_i$ dla których wartość mnożnika lagrange'a $\alpha_i \neq 0$ to poszukiwane wektory nośne.

By znacznie zmniejszyć złożoność obliczeniową możliwe jest wydajne liczenie wartości $\langle\ \phi(x_i), \phi(x_k)\rangle$ z wykorzystaniem **kernel trick**.

Dla danych linowo separowalnych stosuje się kernel linowy. W przeciwnym wypadku można zastosować kernel wielomianowy lub RBF.

W przypadku klasyfikacji więcej niż dwóch klas można stworzyć wiele modeli i zastosować schemat one-vs-all lub one-vs-one.

#### 3. Drzewo decyzyjne

Algorytm w każdej iteracji wybiera atrybut który najlepiej separuje klasy.
Ddzieje się to na podstawie wartości entropii oraz information-gain. Następnie dla każdej z wartości atrybutu generowana jest oddzielna gałąź drzewa. Jeśli wszystkie obserwacje na danej gałęzi należą do jednej klasy, to generowana jest liść drzewa z tą klasą. W przeciwnym wypadku, algorytm przechodzi do kolejnej iteracji. Dla atrybutów ciągłych może zostać zastosowane kubełkowanie. Po zbudowaniu drzewa można również zastosować przycinanie zbędnych węzłów.

#### 4. Las losowy

Klasyfikator ten jest zbudowany z wielu niezależnych drzew decyzyjnych. Każde z nich tworzy swoją predykcjię, a algorytm wybiera najczęściej występującą klasę. W celu zapewnienia jak największej niezależności drzew do trenowania każdego z nich używa się losowego podzbioru uczącego stosując losowanie ze zwracaniem (bootstrapping). Dodatkowo każde z drzew korzysta z innego losowego podzbioru atrybutów na podstawie których podejmuje decyzje.

#### 5. Naiwny klasyfikator Bayesa

Naiwny klasyfikator bayesowski oblicza prawdopodobieństwo wszystkich klas $y$ w zależności od wektora predyktorów $\bar{x} = (x_1, x_2, ... , x_n)$.
Prawdopodobieństwo to wyraża się wzorem

$P(y|x_1, x_2, ..., x_n) = \frac{P(x_1, x_2, ... , x_n | y) P(y)}{P(x_1, x_2,... , x_n)}$

Naiwnie zakładając, że predyktory są niezależne od siebie

$P(x_i | y, x_1, ..., x_{i-1}, x_{i+1}, ..., x_n) = P(x_i|y)$,

możliwe jest przejście do postaci

$P(y|x_1, x_2, ..., x_n) = \frac{P(y) \prod_{i=1}^n P(x_i|y)}{P(x_1, x_2,... , x_n)}$

Ponieważ $P(x_1, x_2,... , x_n)$ jest stałe dla danych zmiennych wejściowych, a dzielenie przez stałą nie wpływa na relatywne wartości prawdopodobieństw dla każdej z klas, to możliwe jest pominięcie tego elementu.

Reguła decyzyjna na podstawie której następuje klasyfikacja wyraża się wzorem:

$\hat{y} = \underset{y}{\operatorname{argmax}} P(y) \prod_{i=1}^n P(x_i|y)$

By zachować lepszą precyzję obliczeń dla małych prawdopodobieństw wzór można przekształcić na postać logarytmiczną:

$\hat{y} = \underset{y}{\operatorname{argmax}} \log(P(y)) + \sum_{i=1}^n \log(P(x_i|y))$

Dla zmiennych kategorycznych $P(x_i|y) = \frac{N_{yi} + \alpha}{N_y + \alpha n}$, gdzie

$N_{yi}$, to liczba występowania danej wartości zmiennej kategorycznej, \
$N_{y}$, to liczba występowania wszystkich wartości zmiennej kategorycznej,\
$n$, to liczba unikalnych wartości zmiennej kategorycznej, a \
$0 \leq \alpha \leq 1$, to hiperparametr wygładzenia laplace'a / lidtstone'a zapobiegający występowaniu wartośći prawdopodobieństw równych $0$.

Dla zmiennych numerycznych do wyliczenia $P(x_i|y)$ najczęściej stosuje się rozkład normalny:

$P(x_i|y) = \frac{1}{\sqrt{2\pi \sigma_y^2}} \cdot \exp(- \frac{(x_i - \mu_y)^2}{2\sigma_y^2} )$

lecz jeśli zajdzie taka potrzeba można zastosować również inny rozkład ciągły.

#### 6. k-Najbliższych sąsiadów (KNN)

Algorytm ten przechowuje dane uczące, a następnie klasyfikuje nowe wektory danych za podstawie podobieństwa ich podobieństwa do tych danych. Do liczenia podobieństwa (dystansu) można zastosować takie miary jak metryka euklidesowa, metryka manhattan, czy dystans kosinusowy. Parametr k określa jaka liczba najbliższych sąsiadów jest brana pod uwagę. Następnie klasa która najczęściej występuje wśród tych k sąsiadów przypisywana jest również do klasyfikowanego wektora. W celu ulepszenia algorytmu możliwe jest również zastosowanie ważenia głosów na podstawie odległości od klasyfikowanego wektora.

#### 7. Gradient Boosting

Metoda ta, podobnie jak las losowy tworzy zestaw klasyfikatorów (najczęściej drzew decyzyjnych), a następnie na ich podstawie wybiera najlepiej dopasowaną klasę. W tym przypadku jednak trenowanie modelu jest iteracyjne. W każdej iteracji model jest optymalizowany na podstawie gradientu.

### 3. Plan eksperymentu
Najpierw niezbędne będzie zdefiniowanie wszystkich ścieżek w sieci.
Następnie bazując na długośći ścieżek oszacowana zostanie wartość OSNR dla każdej z nich. Potem na podstawie wartości OSNR każdej ze ścieżek zostanie przypisana jej klasa jakości. Zbiór danych składający się z wartości OSNR (zmienna niezależna) i klas jakości (zmienna zależna) zostanie wykorzystany do uczenia po wcześniejszym podzieleniu go na podzbiory, by nie doszło do przeuczenia. W procesie uczenia mogą zostać wykorzystane dwie metody podziału. Jedna to podział na podzbiory testowy, treningowy oraz walidacyjny, a druga wydzielenie tylko zbiorów testowego i treningowego, a następnie zastosowanie k-krotnej walidacji krzyżowej w celu dynamicznego wyznaczania zbioru walidacyjnego. Po wydzieleniu zbiorów, do modelowania zastosowane zostaną wybrane algorytmy klasyfikacji dostępne w bibliotece `skleanrn`. Ich skuteczność zostanie porównana za pomocą macierzy pomyłek, krzywej ROC oraz wartości AUC.

### 4. Zbiory danych
Zbiory danych definujące sieci telefinormatyczne (polską i opcjonalnie niemiecką) zostaną pobrane ze strony SDNLIB
Podział na zbiory treningowy, walidacyjny i testowy odbędzie sę za pomocą losowego próbkowania oraz walidacji krzyżowej.

## Realizacja projektu

### Generowanie danych
Ważną częścią projektu było wygenerowanie zbiorów danych korzystając z http://sndlib.zib.de/home.action skorzystaliśmy z pliku network.xml parsujemy plik i wykorzystujemy struktury danych języka Python. Dokłady opis danych znajduje się w rozdziale 1. Opis projektu.


Loss per kilometr jest znaną stałą tłumienia w sieci optycznej.


Powołując się na publikację TŁUMIENIE ŚWIATŁA W OŚRODKACH OPTYCZNYCH - WEMiF http://www-old.wemif.pwr.wroc.pl z Politechniki Wrocławskiej twierdzi, że loss_per_km = 0.2.

Kolejnym ważnym parametrem jest moc szumów. Powołując się na pracę "Signalt-to-Noise Ratio Calculation for Fiber Opitcs Links" autorstwa K. Y. Lau (https://bit.ly/3QpiBEc). Wartość P_noise została wyznaczona za pomocą wzoru z literatury.

Reszta prametrów została dobrana na tak, aby unormować otrzymane wyniki. Korzystając z rekomendowanej literatury "Application of machine learning methods in provisioning of DWDM channels" Piotr Paziewski, Sławomir Sujecki, Stanisław Kozdrowski wiedzieliśmy na jakich pozimach ma być OSNR. Różnica między implenetacją, a literaturą wynika z założeń wzmacniania sygnału. W literaturze sygnał wzmacaniany był co 70 km. W implenetacji projektu założono wzmocninie w każdym węźle amplifier_gain (dB).Zakładamy dla uproszczenia, że moc szumów nie jest wzmacjniana. Jest to realtywnie trudne zadania na symulowanie rzeczywistego łącza. P_Signal wyjściowy jest wielokrotnie wyszy niż rzeczywisty. Również założenie 40 dB wzomcnienia może nie jest wykonalne w praktyce, ale może być użyteczne.

Po wygenerowaniu zbiór został podzielony na podzbiory testowy oraz treningowy w stosunku $33:67$

### Początkowe założenia

Początkowym założeniem projektu było klasyfikowanie do klas na podstawie wartości OSNR. Algorytymy zadziałały zaskakująco dobro. Powodem była prostota tego zadania,
które wymagało jedynie kubełkowania zmiennych do 5 klas bezpośrenio na podstawie wartości jednego atrybutu. W przypadku algorytmów klasyfikacji binarnej zastosowany został schemat one-vs-rest.

#### Eksperymenty

##### 5-krotna walidacja krzyżowa

Pierwszym etapem była 5-krotna walidacja krzyżowa na zbiorze treningowym.
Wyniki zostały przedstawione w poniższej tabeli

| Algorytm | Średnia celność ze wszystkich podziałów |
| -------- | -------- |
| Drzewo decyzyjne | $1.00$ |
| Las losowy | $1.00$ |
| SVM | $1.00$ |
| Regresja logistyczna| $0.99$ |
| KNN | $0.99$ |
| Gradient Boosting | $1.00$ |
| Naiwny Bayes | $0.99$ |

Jak widać wszystkie algorytmy otrzymały niemal perfekcyjne wyniki w okolicach $100$%.

##### Macierz pomyłek

Drugą miarą była macierz pomyłek wygenerowana na podstawie zbioru testowego.


Wszystkie algorytmy osiągneły bardzo dobre wyniki. Tylko dwie metody (Regresja logistyczna i naiwny Bayes) popełniły jakikolwiek błąd podczas klasyfikacji.

##### AUC pod krzywą ROC

Trzecią marą jest pole (AUC) pod krzywą ROC. Jako, że krzywą można rysować tylko dla zadań klasyfikacji binarnej, to pole liczymy jako średni wynik AUC liczony w schemacie one-vs-rest.


W tym przypadky sytuacja wygląda podobnie. Wszystkie metody osiągneły niemal perfekcyjną, czyli wynoszącą $1$ wartość AUC.

### Zmienione założenia
Po konsulatcji z prowadzącym, zasugerowao zmianę wekrotra danych. W drugiej wersji projektu zamiansy wartości ONSR, wektor danych składał się z długości trasy i liczby nodów pomiędzy krańcami ścieżki. W tej części projektu wyniki wyszły ciekawsze:


Widzimy na wykresie jak układają się klasy w zależności od ilości nodów oraz długości. Dane są liniowo separowalne.

#### Eksperymenty

##### 5-krotna walidacja krzyżowa

Pierwszym etapem była 5-krotna walidacja krzyżowa na zbiorze treningowym.
Wyniki zostały przedstawione w poniższej tabeli

| Algorytm | Średnia celność ze wszystkich podziałów |
| -------- | -------- |
| Drzewo decyzyjne | $0.92$ |
| Las losowy | $0.95$ |
| SVM | $0.90$ |
| Regresja logistyczna| $0.87$ |
| KNN | $0.70$ |
| Gradient Boosting | $0.90$ |
| Naiwny Bayes | $0.66$ |

Jak widać wszystkie algorytmy z wyjątkiem KNN oraz naiwnego klasyfikatora Bayesa poradziły sobie dość dobrze, osiągając wyniki w okolicach $90$%. Najlepszy okazał sią las losowy z celnością $95$%.

##### Macierz pomyłek

Drugą miarą była macierz pomyłek wygenerowana na podstawie zbioru testowego.


Jako, że w zbiorze występuje duża nadreprezentacja klas 1 oraz 5, to mniej odporne algorytmy bardzo źle radzą sobie z klasyfikowaniem klas 2-4. KNN i naiwny klasyfikator Bayesa poradziły sobie pod tym względem zdecydowanie najgorzej. Wynika to z mieszania się wyników OSNR pomiędzy trasami najkrótszymi, a trasami dłuższymi zwiększą ilością nodów. Przy poczynionych założeniach czasmi opłaca się routować trasą dłuższą z większą ilością wzmocnień po drodze. Ważne jest przypomnienie, że w rzeczywistości moc szumów również była by wzmacniania. Algorytmy jak DAP i DDAP optymalizują tak demandy, aby obciążenie całościowe sieci było jak najmniejsze. Z drugiej strony nasz algorytm nie miał na celu wybrania najoptymalniejszej ścieżki, a przewidywanie klasy dla danych pathów oraz demandu. Klasa była liczona dla wszystkich podanych ścieżek i demandów. Nasz algorytm mógłby pomóc algorytmowi rotującym ruch w podejmowniu optymalych decyzji.
Najlepsze wynikio trzymały drzewo decyzyjne, las losowy oraz SVM.

##### AUC pod krzywą ROC

Trzecią marą jest pole (AUC) pod krzywą ROC. Jako, że krzywą można rysować tylko dla zadań klasyfikacji binarnej, to pole liczymy jako średni wynik AUC liczony w schemacie one-vs-rest.


Tym razem drzewo decyzyjne, las losowy, SVM oraz gradient boosting okazały się najlepsze. SVM z jądrem liniowym działał dobrze, ponieważ dane są liniowo seprowalne. Pozostałe metody miały znacznie słabsze wyniki, a naiwny Bayes okazał się najgorszym wyborem. Taki stan rzeczy można wyjaśnić tym, że te cztery metody są znacznie bardziej złożone i lepiej radzą sobie gdy zależność w danych jest bardziej skomplikowana. Najgorzszy wynik naiwnego Bayesa jest spowodowny podobieństwem wartości klas krótkich i tras długich, często wzmanianych w nodach.