# --------------------------------------------------------------------------
# ------------  Metody Systemowe i Decyzyjne w Informatyce  ----------------
# --------------------------------------------------------------------------
#  Zadanie 2: k-NN i Naive Bayes
#  autorzy: A. Gonczarek, J. Kaczmar, S. Zareba, P. Dąbrowski
#  2019
# --------------------------------------------------------------------------

import numpy as np

def hamming_distance(X, X_train):
    """
   Zwróć odległość Hamminga dla obiektów ze zbioru *X* od obiektów z *X_train*.

   :param X: zbiór porównywanych obiektów N1xD
   :param X_train: zbiór obiektów do których porównujemy N2xD
   :return: macierz odległości pomiędzy obiektami z "X" i "X_train" N1xN2
   """
    x = X.toarray().astype(int)
    x_train_tran = np.transpose(X_train.toarray()).astype(int)
    return np.array(x.shape[1] - (x @ x_train_tran) - ((1 - x) @ (1 - x_train_tran)))

def sort_train_labels_knn(Dist, y):
    """
    Posortuj etykiety klas danych treningowych *y* względem prawdopodobieństw
    zawartych w macierzy *Dist*.

    :param Dist: macierz odległości pomiędzy obiektami z "X" i "X_train" N1xN2
    :param y: wektor etykiet o długości N2
    :return: macierz etykiet klas posortowana względem wartości podobieństw
        odpowiadającego wiersza macierzy Dist N1xN2

    Do sortowania użyj algorytmu mergesort.
    """
    matrix = np.ones(shape=(np.shape(Dist)))
    i=0
    for i in range(Dist.shape[0]):
        matrix[i] = y[np.argsort(Dist[i],-1,'mergesort')]
        i+=1
    return matrix

def p_y_x_knn(y, k):
    """
    Wyznacz rozkład prawdopodobieństwa p(y|x) każdej z klas dla obiektów
    ze zbioru testowego wykorzystując klasyfikator KNN wyuczony na danych
    treningowych.

    :param y: macierz posortowanych etykiet dla danych treningowych N1xN2
    :param k: liczba najbliższych sasiadow dla KNN
    :return: macierz prawdopodobieństw p(y|x) dla obiektów z "X" N1xM
    """
    maks = max([ max(verse.astype(int)) for verse in y ]).astype(int)
    matrix = np.empty(shape=(y.shape[0],maks+1))
    for i in range(y.shape[0]):
        temp = np.bincount((y[i,:k]).astype(int),weights=None,minlength=(maks+1)) / k
        matrix[i] = temp
    return matrix

def classification_error(p_y_x, y_true):
    """
    Wyznacz błąd klasyfikacji.

    :param p_y_x: macierz przewidywanych prawdopodobieństw - każdy wiersz
        macierzy reprezentuje rozkład p(y|x) NxM
    :param y_true: zbiór rzeczywistych etykiet klas 1xN
    :return: błąd klasyfikacji
    """
    licznik = 0
    for v in range(p_y_x.shape[0]):
        ML=-1
        MLIndex = -1
        for i in range(p_y_x.shape[1]):
            if(p_y_x[v,i]>=ML):
                ML=p_y_x[v,i]
                MLIndex=i
        if(MLIndex != y_true[v]):
            licznik+=1
    wynik = licznik/y_true.shape[0]
    return wynik

def model_selection_knn(X_val, X_train, y_val, y_train, k_values):
    """
    Wylicz błąd dla różnych wartości *k*. Dokonaj selekcji modelu KNN
    wyznaczając najlepszą wartość *k*, tj. taką, dla której wartość błędu jest
    najniższa.

    :param X_val: zbiór danych walidacyjnych N1xD
    :param X_train: zbiór danych treningowych N2xD
    :param y_val: etykiety klas dla danych walidacyjnych 1xN1
    :param y_train: etykiety klas dla danych treningowych 1xN2
    :param k_values: wartości parametru k, które mają zostać sprawdzone
    :return: krotka (best_error, best_k, errors), gdzie "best_error" to
        najniższy osiągnięty błąd, "best_k" to "k" dla którego błąd był
        najniższy, a "errors" - lista wartości błędów dla kolejnych
        "k" z "k_values"
    """
    errors = []
    best_error_index = 0
    best_error = 10000
    i=0
    for k in k_values:
        new_error=classification_error(p_y_x_knn(sort_train_labels_knn(hamming_distance(X_val,X_train),y_train),k),y_val)
        if(new_error<best_error):
               best_error = new_error
               best_error_index = i
        i+=1
        errors.append(new_error)
    return (best_error, k_values[best_error_index], errors)

def estimate_a_priori_nb(y_train):
    """
    Wyznacz rozkład a priori p(y) każdej z klas dla obiektów ze zbioru
    treningowego.

    :param y_train: etykiety dla danych treningowych 1xN
    :return: wektor prawdopodobieństw a priori p(y) 1xM
    """
    maks = max(y_train)+1
    matrix = np.zeros(shape=(maks,))
    for el in y_train:
        matrix[el]+=1
    return np.divide(matrix,y_train.shape[0])

def estimate_p_x_y_nb(X_train, y_train, a, b):
    """
    Wyznacz rozkład prawdopodobieństwa p(x|y) zakładając, że *x* przyjmuje
    wartości binarne i że elementy *x* są od siebie niezależne.

    :param X_train: dane treningowe NxD
    :param y_train: etykiety klas dla danych treningowych 1xN
    :param a: parametr "a" rozkładu Beta
    :param b: parametr "b" rozkładu Beta
    :return: macierz prawdopodobieństw p(x|y) dla obiektów z "X_train" MxD.
    """
    maks = max(y_train)+1
    matrix = np.zeros(shape = (maks,X_train.shape[1]))
    noOfKOcc = np.zeros(shape = (maks,))
    for i in range(X_train.shape[0]):
        matrix[y_train[i]]+=X_train[i]
        noOfKOcc[y_train[i]]+=1
    for i in range(maks):
        matrix[i] = np.divide(matrix[i]+a-1,noOfKOcc[i]+a+b-2)
    return matrix

def p_y_x_nb(p_y, p_x_1_y, X):
    """
    Wyznacz rozkład prawdopodobieństwa p(y|x) dla każdej z klas z wykorzystaniem
    klasyfikatora Naiwnego Bayesa.

    :param p_y: wektor prawdopodobieństw a priori 1xM
    :param p_x_1_y: rozkład prawdopodobieństw p(x=1|y) MxD
    :param X: dane dla których beda wyznaczone prawdopodobieństwa, macierz NxD
    :return: macierz prawdopodobieństw p(y|x) dla obiektów z "X" NxM
    """
    X = X.toarray()
    p_x_0_y = 1 - p_x_1_y
    res = []
    for verseX in X:
        true = p_x_1_y ** verseX
        false = p_x_0_y ** (1-verseX)
        part_res = np.prod(true * false, axis=1) * p_y
        sum = np.sum(part_res)
        res.append(part_res / sum)
    return np.array(res)

def model_selection_nb(X_train, X_val, y_train, y_val, a_values, b_values):
    """
    :param Xtrain: zbior danych treningowych N2xD
    :param Xval: zbior danych walidacyjnych N1xD
    :param ytrain: etykiety klas dla danych treningowych 1xN2
    :param yval: etykiety klas dla danych walidacyjnych 1xN1
    :param a_values: lista parametrow a do sprawdzenia
    :param b_values: lista parametrow b do sprawdzenia
    :return: funkcja wykonuje selekcje modelu Naive Bayes - wybiera najlepsze wartosci parametrow a i b. Funkcja zwraca
    krotke (error_best, best_a, best_b, errors) gdzie best_error to najnizszy
    osiagniety blad, best_a - a dla ktorego blad byl najnizszy, best_b - b dla ktorego blad byl najnizszy,
    errors - macierz wartosci bledow dla wszystkich par (a,b)
    """
    errors = [ classification_error( p_y_x_nb( estimate_a_priori_nb( y_train ), estimate_p_x_y_nb( X_train, y_train, a, b ), X_val ), y_val ) for a in a_values for b in b_values]
    sorted_errors_indices = np.argsort(errors)
    best_error = errors[ sorted_errors_indices[0] ]
    best_a = a_values[ (sorted_errors_indices[0] / len(b_values)).astype(int) ]
    best_b = b_values[ (sorted_errors_indices[0] % len(b_values)).astype(int) ]
    errors = np.array(errors).reshape(np.sqrt(len(errors)).astype(int),np.sqrt(len(errors)).astype(int))
    return (best_error, best_a, best_b, errors)