SHARE
TWEET

Untitled

a guest Apr 24th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # --------------------------------------------------------------------------
  2. # ------------  Metody Systemowe i Decyzyjne w Informatyce  ----------------
  3. # --------------------------------------------------------------------------
  4. #  Zadanie 2: k-NN i Naive Bayes
  5. #  autorzy: A. Gonczarek, J. Kaczmar, S. Zareba, P. Dąbrowski
  6. #  2019
  7. # --------------------------------------------------------------------------
  8.  
  9. import numpy as np
  10.  
  11. def hamming_distance(X, X_train):
  12.     """
  13.    Zwróć odległość Hamminga dla obiektów ze zbioru *X* od obiektów z *X_train*.
  14.  
  15.    :param X: zbiór porównywanych obiektów N1xD
  16.    :param X_train: zbiór obiektów do których porównujemy N2xD
  17.    :return: macierz odległości pomiędzy obiektami z "X" i "X_train" N1xN2
  18.    """
  19.     x = X.toarray().astype(int)
  20.     x_train_tran = np.transpose(X_train.toarray()).astype(int)
  21.     return np.array(x.shape[1] - (x @ x_train_tran) - ((1 - x) @ (1 - x_train_tran)))
  22.  
  23. def sort_train_labels_knn(Dist, y):
  24.     """
  25.     Posortuj etykiety klas danych treningowych *y* względem prawdopodobieństw
  26.     zawartych w macierzy *Dist*.
  27.  
  28.     :param Dist: macierz odległości pomiędzy obiektami z "X" i "X_train" N1xN2
  29.     :param y: wektor etykiet o długości N2
  30.     :return: macierz etykiet klas posortowana względem wartości podobieństw
  31.         odpowiadającego wiersza macierzy Dist N1xN2
  32.  
  33.     Do sortowania użyj algorytmu mergesort.
  34.     """
  35.     matrix = np.ones(shape=(np.shape(Dist)))
  36.     i=0
  37.     for i in range(Dist.shape[0]):
  38.         matrix[i] = y[np.argsort(Dist[i],-1,'mergesort')]
  39.         i+=1
  40.     return matrix
  41.  
  42. def p_y_x_knn(y, k):
  43.     """
  44.     Wyznacz rozkład prawdopodobieństwa p(y|x) każdej z klas dla obiektów
  45.     ze zbioru testowego wykorzystując klasyfikator KNN wyuczony na danych
  46.     treningowych.
  47.  
  48.     :param y: macierz posortowanych etykiet dla danych treningowych N1xN2
  49.     :param k: liczba najbliższych sasiadow dla KNN
  50.     :return: macierz prawdopodobieństw p(y|x) dla obiektów z "X" N1xM
  51.     """
  52.     maks = max([ max(verse.astype(int)) for verse in y ]).astype(int)
  53.     matrix = np.empty(shape=(y.shape[0],maks+1))
  54.     for i in range(y.shape[0]):
  55.         temp = np.bincount((y[i,:k]).astype(int),weights=None,minlength=(maks+1)) / k
  56.         matrix[i] = temp
  57.     return matrix
  58.  
  59. def classification_error(p_y_x, y_true):
  60.     """
  61.     Wyznacz błąd klasyfikacji.
  62.  
  63.     :param p_y_x: macierz przewidywanych prawdopodobieństw - każdy wiersz
  64.         macierzy reprezentuje rozkład p(y|x) NxM
  65.     :param y_true: zbiór rzeczywistych etykiet klas 1xN
  66.     :return: błąd klasyfikacji
  67.     """
  68.     licznik = 0
  69.     for v in range(p_y_x.shape[0]):
  70.         ML=-1
  71.         MLIndex = -1
  72.         for i in range(p_y_x.shape[1]):
  73.             if(p_y_x[v,i]>=ML):
  74.                 ML=p_y_x[v,i]
  75.                 MLIndex=i
  76.         if(MLIndex != y_true[v]):
  77.             licznik+=1
  78.     wynik = licznik/y_true.shape[0]
  79.     return wynik
  80.  
  81. def model_selection_knn(X_val, X_train, y_val, y_train, k_values):
  82.     """
  83.     Wylicz błąd dla różnych wartości *k*. Dokonaj selekcji modelu KNN
  84.     wyznaczając najlepszą wartość *k*, tj. taką, dla której wartość błędu jest
  85.     najniższa.
  86.  
  87.     :param X_val: zbiór danych walidacyjnych N1xD
  88.     :param X_train: zbiór danych treningowych N2xD
  89.     :param y_val: etykiety klas dla danych walidacyjnych 1xN1
  90.     :param y_train: etykiety klas dla danych treningowych 1xN2
  91.     :param k_values: wartości parametru k, które mają zostać sprawdzone
  92.     :return: krotka (best_error, best_k, errors), gdzie "best_error" to
  93.         najniższy osiągnięty błąd, "best_k" to "k" dla którego błąd był
  94.         najniższy, a "errors" - lista wartości błędów dla kolejnych
  95.         "k" z "k_values"
  96.     """
  97.     errors = []
  98.     best_error_index = 0
  99.     best_error = 10000
  100.     i=0
  101.     for k in k_values:
  102.         new_error=classification_error(p_y_x_knn(sort_train_labels_knn(hamming_distance(X_val,X_train),y_train),k),y_val)
  103.         if(new_error<best_error):
  104.                best_error = new_error
  105.                best_error_index = i
  106.         i+=1
  107.         errors.append(new_error)
  108.     return (best_error, k_values[best_error_index], errors)
  109.  
  110. def estimate_a_priori_nb(y_train):
  111.     """
  112.     Wyznacz rozkład a priori p(y) każdej z klas dla obiektów ze zbioru
  113.     treningowego.
  114.  
  115.     :param y_train: etykiety dla danych treningowych 1xN
  116.     :return: wektor prawdopodobieństw a priori p(y) 1xM
  117.     """
  118.     maks = max(y_train)+1
  119.     matrix = np.zeros(shape=(maks,))
  120.     for el in y_train:
  121.         matrix[el]+=1
  122.     return np.divide(matrix,y_train.shape[0])
  123.  
  124. def estimate_p_x_y_nb(X_train, y_train, a, b):
  125.     """
  126.     Wyznacz rozkład prawdopodobieństwa p(x|y) zakładając, że *x* przyjmuje
  127.     wartości binarne i że elementy *x* są od siebie niezależne.
  128.  
  129.     :param X_train: dane treningowe NxD
  130.     :param y_train: etykiety klas dla danych treningowych 1xN
  131.     :param a: parametr "a" rozkładu Beta
  132.     :param b: parametr "b" rozkładu Beta
  133.     :return: macierz prawdopodobieństw p(x|y) dla obiektów z "X_train" MxD.
  134.     """
  135.     maks = max(y_train)+1
  136.     matrix = np.zeros(shape = (maks,X_train.shape[1]))
  137.     noOfKOcc = np.zeros(shape = (maks,))
  138.     for i in range(X_train.shape[0]):
  139.         matrix[y_train[i]]+=X_train[i]
  140.         noOfKOcc[y_train[i]]+=1
  141.     for i in range(maks):
  142.         matrix[i] = np.divide(matrix[i]+a-1,noOfKOcc[i]+a+b-2)
  143.     return matrix
  144.  
  145. def p_y_x_nb(p_y, p_x_1_y, X):
  146.     """
  147.     Wyznacz rozkład prawdopodobieństwa p(y|x) dla każdej z klas z wykorzystaniem
  148.     klasyfikatora Naiwnego Bayesa.
  149.  
  150.     :param p_y: wektor prawdopodobieństw a priori 1xM
  151.     :param p_x_1_y: rozkład prawdopodobieństw p(x=1|y) MxD
  152.     :param X: dane dla których beda wyznaczone prawdopodobieństwa, macierz NxD
  153.     :return: macierz prawdopodobieństw p(y|x) dla obiektów z "X" NxM
  154.     """
  155.     X = X.toarray()
  156.     p_x_0_y = 1 - p_x_1_y
  157.     res = []
  158.     for verseX in X:
  159.         true = p_x_1_y ** verseX
  160.         false = p_x_0_y ** (1-verseX)
  161.         part_res = np.prod(true * false, axis=1) * p_y
  162.         sum = np.sum(part_res)
  163.         res.append(part_res / sum)
  164.     return np.array(res)
  165.  
  166. def model_selection_nb(X_train, X_val, y_train, y_val, a_values, b_values):
  167.     """
  168.     :param Xtrain: zbior danych treningowych N2xD
  169.     :param Xval: zbior danych walidacyjnych N1xD
  170.     :param ytrain: etykiety klas dla danych treningowych 1xN2
  171.     :param yval: etykiety klas dla danych walidacyjnych 1xN1
  172.     :param a_values: lista parametrow a do sprawdzenia
  173.     :param b_values: lista parametrow b do sprawdzenia
  174.     :return: funkcja wykonuje selekcje modelu Naive Bayes - wybiera najlepsze wartosci parametrow a i b. Funkcja zwraca
  175.     krotke (error_best, best_a, best_b, errors) gdzie best_error to najnizszy
  176.     osiagniety blad, best_a - a dla ktorego blad byl najnizszy, best_b - b dla ktorego blad byl najnizszy,
  177.     errors - macierz wartosci bledow dla wszystkich par (a,b)
  178.     """
  179.     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]
  180.     sorted_errors_indices = np.argsort(errors)
  181.     best_error = errors[ sorted_errors_indices[0] ]
  182.     best_a = a_values[ (sorted_errors_indices[0] / len(b_values)).astype(int) ]
  183.     best_b = b_values[ (sorted_errors_indices[0] % len(b_values)).astype(int) ]
  184.     errors = np.array(errors).reshape(np.sqrt(len(errors)).astype(int),np.sqrt(len(errors)).astype(int))
  185.     return (best_error, best_a, best_b, errors)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top