11. k Nearest Neighbors

Todo

Zrobić aby wykorzystywało szablon _template.rst

11.1. Jak działa algorytm “K najbliższych sąsiadów”

Algorytm polega na:

  1. porównaniu wartości zmiennych objaśniających dla obserwacji C z wartościami tych zmiennych dla każdej obserwacji w zbiorze uczącym.
  2. wyborze k (ustalona z góry liczba) najbliższych do C obserwacji ze zbioru uczącego.
  3. uśrednieniu wartości zmiennej objaśnianej dla wybranych obserwacji, w wyniku czego uzyskujemy prognozę.
../_images/k-nearest-neighbors-territory.png

Fig. 11.1. Predykcja obszaru przynależności w algorytmie “K najbliższych sąsiadów”.

11.2. Przykład praktyczny

11.2.1. Jak to działa na przykładzie Iris

  1. Mamy zbiór 150 obserwacji Iris

  2. Wyobraź sobie, że mamy określić nową Iris, która jeszcze nie została zaobserwowana i opisana.

  3. Wybieramy wartość k

  4. Poszukujemy k obserwacji, które są najbliższe nieznanemu gatunkowi Iris.

  5. Użyj najczęściej pojawiającej się wartości z “k najbliższych sąsiadów” jako wartość dla nieznanego Iris.

    • tzn. jeżeli np. dla k=5 (czyli wśród 5 najbliżyszch Irisów) było 3 Iris Setosa, i po jednym z innych gatunków
    • to naszemu nieznanemu gatunkowi przypiszemy Iris Setosa.
  6. Najczęściej stosuje się algorytm Eukleidesa do wyznaczania odległości, ale można również i inne algorytmy.

11.2.2. Wykorzystanie sklearn.neighbors.KNeighborsClassifier

from sklearn import datasets
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier


iris = datasets.load_iris()

# Split dataset into test and training set in half
features_train, features_test, labels_train, labels_test = train_test_split(iris.data, iris.target, test_size=0.25)

# Create classifier
model = KNeighborsClassifier()

# Train classifier using training data
model.fit(features_train, labels_train)

# Predict
predictions = model.predict(features_test)

# How accurate was classifier on testing set
output = accuracy_score(labels_test, predictions)
print(output)
# Output: 0.947368421053

Note

Because of some variation for each run, it might give different results.

11.2.3. Własna implementacja

from scipy.spatial import distance
from sklearn import datasets
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split


class NearestNeighborClassifier:
    def fit(self, features, labels):
        self.features_train = features
        self.labels_train = labels

    def predict(self, features_test):
        predictions = []

        for row in features_test:
            label = self.closest(row)
            predictions.append(label)

        return predictions

    def closest(self, row):
        best_dist = distance.euclidean(row, self.features_train[0])
        best_index = 0

        for i in range(0, len(self.features_train)):
            dist = distance.euclidean(row, self.features_train[i])
            if dist < best_dist:
                best_dist = dist
                best_index = i

        return self.labels_train[best_index]


iris = datasets.load_iris()

# Split dataset into test and training set in half
features_train, features_test, labels_train, labels_test = train_test_split(iris.data, iris.target, test_size=0.5)

# Create classifier
model = NearestNeighborClassifier()

# Train classifier using training data
model.fit(features_train, labels_train)

# Predict
predictions = model.predict(features_test)

# How accurate was classifier on testing set
output = accuracy_score(labels_test, predictions)
print(output)
# Output: 0.96

Note

Because of some variation for each run, it might give different results.

11.3. Określanie przynależności do zbioru

../_images/k-nearest-neighbors-membership.png

Fig. 11.2. Przynależność do zbioru

11.4. Wyznaczanie odległości

../_images/k-nearest-neighbors-euclidean-distance.png

Fig. 11.3. Wyliczanie odległości w celu oszacowania przynależności do zbioru. Zwróć uwagę, że bez względu na ilość wymiarów wzór się niewiele różni.

11.5. Zalety i wady

11.5.1. Zalety

  • Relatywnie prosty
  • Dobrze działa dla niektórych problemów

11.5.2. Wady

  • Wolny i zasobożerny (musi iterować dla każdej predykcji)
  • Brak możliwości ważenia features

11.6. Zadania kontrolne

11.6.1. Pima Indians Diabetes problem

Dla Pima Indians Diabetes wykonaj analizę algorytmem KNN z biblioteki sklearn.

11.6.2. Płeć

Napisz własną implementacje k Nearest Neighbors, która dla danych:

Gender Height Weight Foot Size
male 6.00 180 12
male 5.92 190 11
male 5.58 170 12
male 5.92 165 10
female 5.00 100 6
female 5.50 150 8
female 5.42 130 7
female 5.75 150 9

Odpowie na pytanie jaką płeć ma osoba o parametrach:

  • Height: 6
  • Weight: 130
  • Foot Size: 8
  • Jaki jest najlepszy parametr k dla tego zadania?

  • Która z cech ma najwięszy wpływ?

  • Czy algorytm lepiej działa z:

    • normalizacją i skalownaiem?
    • bez normalizacji i skalowania?
    • tylko z normalizacją?
    • tylko skalowaniem?
Podpowiedź:
  • preprocessing.LabelEncoder()
  • ExtraTreesClassifier() i .feature_importances_
  • preprocessing.normalize(features)
  • preprocessing.scale(features)