7.1. K Nearest Neighbors¶

7.1.1. Jak działa algorytm "K najbliższych sąsiadów"¶

Algorytm polega na:

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

../../_images/k-nearest-neighbors-territory.png — Figure 7.11. Predykcja obszaru przynależności w algorytmie "K najbliższych sąsiadów".¶

7.1.2. Przykład praktyczny¶

7.1.3. Jak to działa na przykładzie Iris¶

Mamy zbiór 150 obserwacji Iris
Wyobraź sobie, że mamy określić nową Iris, która jeszcze nie została zaobserwowana i opisana.
Wybieramy wartość \(k\)
Poszukujemy \(k\) obserwacji, które są najbliższe nieznanemu gatunkowi Iris.
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ższych Iris) było 3 Iris Setosa, i po jednym z innych gatunków
- to naszemu nieznanemu gatunkowi przypiszemy Iris Setosa.
Najczęściej stosuje się algorytm Euklidesa do wyznaczania odległości, ale można również i inne algorytmy.

7.1.4. 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
result = accuracy_score(labels_test, predictions)
print(result)
# Output: 0.947368421053

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

7.1.5. 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
result = accuracy_score(labels_test, predictions)
print(result)
# Output: 0.96

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

7.1.6. Określanie przynależności do zbioru¶

../../_images/k-nearest-neighbors-membership.png — Figure 7.12. Przynależność do zbioru¶

7.1.7. Wyznaczanie odległości¶

../../_images/k-nearest-neighbors-euclidean-distance.png — Figure 7.13. 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.¶

7.1.8. Zalety i wady¶

7.1.9. Zalety¶

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

7.1.10. Wady¶

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

7.1.11. Assignments¶

7.1.11.1. Pima Indians Diabetes problem¶

Assignment: Pima Indians Diabetes problem
Complexity: medium
Lines of code: 15 lines
Time: 13 min

English:

TODO: English Translation X. Run doctests - all must succeed

Polish:

Dla Pima Indians Diabetes wykonaj analizę algorytmem KNN z biblioteki sklearn.
Uruchom doctesty - wszystkie muszą się powieść

7.1.11.2. Płeć¶

Assignment: Płeć
Complexity: easy
Lines of code: 15 lines
Time: 13 min