Warunek wstępny: Najbliższy K sąsiedzi 
 

lista jako tablica

Wstęp

Załóżmy, że otrzymaliśmy zestaw danych obejmujący elementy, z których każdy ma cechy o wartościach liczbowych (takie jak wzrost, waga, wiek itp.). Jeśli liczba funkcji wynosi N możemy reprezentować elementy jako punkty w an N -siatka wymiarowa. Biorąc pod uwagę nowy element, możemy obliczyć odległość od elementu do każdego innego elementu w zestawie. Wybieramy k najbliższych sąsiadów i widzimy, gdzie sklasyfikowana jest większość tych sąsiadów. Tam klasyfikujemy nowy przedmiot.
Więc pojawia się problem jak obliczyć odległości pomiędzy elementami. Rozwiązanie tego zależy od zbioru danych. Jeśli wartości są rzeczywiste, zwykle używamy odległości euklidesowej. Jeśli wartości są kategoryczne lub binarne, zwykle używamy odległości Hamminga.
Algorytm:  
 

Given a new item: 1. Find distances between new item and all other items 2. Pick k shorter distances 3. Pick the most common class in these k distances 4. That class is where we will classify the new item

Odczyt danych

Niech nasz plik wejściowy będzie miał następujący format:
 

Height Weight Age Class 1.70 65 20 Programmer 1.90 85 33 Builder 1.78 76 31 Builder 1.73 74 24 Programmer 1.81 75 35 Builder 1.73 70 75 Scientist 1.80 71 63 Scientist 1.75 69 25 Programmer

Każdy element jest linią, a w sekcji „Klasa” widzimy, do której pozycji jest on zaklasyfikowany. Wartości pod nazwami funkcji („Wysokość” itp.) określają wartość danej cechy, jaką ma dany przedmiot. Wszystkie wartości i cechy oddziela się przecinkami.
Umieść te pliki danych w katalogu roboczym dane2 I dane . Wybierz jeden i wklej zawartość w niezmienionej postaci do pliku tekstowego o nazwie dane .
Będziemy czytać z pliku (o nazwie „data.txt”) i dzielimy dane wejściowe liniami:
 

f = open('data.txt' 'r'); lines = f.read().splitlines(); f.close();

Pierwsza linia pliku zawiera nazwy funkcji ze słowem kluczowym „Class” na końcu. Chcemy przechowywać nazwy funkcji na liście:
 

śpij spokojnie

# Split the first line by commas # remove the first element and # save the rest into a list. The # list now holds the feature # names of the data set. features = lines[0].split(' ')[:-1];

Następnie przechodzimy do samego zbioru danych. Zapisujemy elementy na liście o nazwie rzeczy których elementami są słowniki (po jednym dla każdej pozycji). Kluczami do tych słowników elementów są nazwy funkcji oraz słowo „Klasa” przechowujące klasę elementu. Na koniec chcemy przetasować pozycje na liście (jest to środek bezpieczeństwa na wypadek, gdyby pozycje były ułożone w dziwnej kolejności). 
 

items = []; for i in range(1 len(lines)): line = lines[i].split(' '); itemFeatures = {'Class' : line[-1]}; # Iterate through the features for j in range(len(features)): # Get the feature at index j f = features[j]; # The first item in the line # is the class skip it v = float(line[j]); # Add feature to dict itemFeatures[f] = v; # Append temp dict to items items.append(itemFeatures); shuffle(items); 

Klasyfikacja danych

Z danymi zapisanymi w rzeczy teraz zaczynamy budować nasz klasyfikator. Dla klasyfikatora utworzymy nową funkcję Klasyfikować . Jako dane wejściowe zostanie pobrany element, który chcemy sklasyfikować na liście elementów k liczba najbliższych sąsiadów.
Jeśli k jest większa niż długość zbioru danych, nie kontynuujemy klasyfikacji, ponieważ nie możemy mieć więcej najbliższych sąsiadów niż całkowita liczba elementów w zbiorze danych. (alternatywnie możemy ustawić k jako rzeczy długość zamiast zwracać komunikat o błędzie)
 

if(k > len(Items)): # k is larger than list # length abort return 'k larger than list length';

Chcemy obliczyć odległość pomiędzy klasyfikowanym przedmiotem a wszystkimi elementami zbioru szkoleniowego, na koniec zachowując k najkrótsze odległości. Aby zachować aktualnych najbliższych sąsiadów, używamy listy o nazwie sąsiedzi . Każdy element przynajmniej posiada dwie wartości, jedną dla odległości od klasyfikowanego elementu, a drugą dla klasy, do której należy sąsiad. Odległość obliczymy za pomocą uogólnionego wzoru euklidesowego (np. N wymiary). Następnie wybierzemy klasę, która pojawia się najczęściej sąsiedzi i to będzie nasz wybór. W kodzie: 
 

def Classify(nItem k Items): if(k > len(Items)): # k is larger than list # length abort return 'k larger than list length'; # Hold nearest neighbors. # First item is distance  # second class neighbors = []; for item in Items: # Find Euclidean Distance distance = EuclideanDistance(nItem item); # Update neighbors either adding # the current item in neighbors  # or not. neighbors = UpdateNeighbors(neighbors item distance k); # Count the number of each # class in neighbors count = CalculateNeighborsClass(neighbors k); # Find the max in count aka the # class with the most appearances. return FindMax(count); 

Funkcje zewnętrzne, które musimy wdrożyć, to Odległość euklidesowa Aktualizuj Sąsiedzi Oblicz klasę sąsiadów I ZnajdźMax .
 

Znajdowanie odległości euklidesowej

Uogólniony wzór euklidesowy na dwa wektory x i y jest następujący: 

distance = sqrt{(x_{1}-y_{1})^2 + (x_{2}-y_{2})^2 + ... + (x_{n}-y_{n})^2}

W kodzie: 

def EuclideanDistance(x y): # The sum of the squared  # differences of the elements S = 0; for key in x.keys(): S += math.pow(x[key]-y[key] 2); # The square root of the sum return math.sqrt(S); 

Aktualizacja sąsiadów

Mamy listę naszych sąsiadów (która powinna mieć co najwyżej długość k ) i chcemy dodać do listy pozycję z podaną odległością. Najpierw sprawdzimy, czy sąsiedzi mieć długość k . Jeżeli ma mniej to dodajemy do niego element bez względu na odległość (bo musimy zapełnić listę do k zanim zaczniemy odrzucać produkty). Jeśli nie, sprawdzimy, czy pozycja ma krótszą odległość niż pozycja z maksymalną odległością na liście. Jeśli to prawda, zastąpimy przedmiot o maksymalnej odległości nowym przedmiotem.
Aby szybciej znaleźć element maksymalnej odległości, lista będzie posortowana w kolejności rosnącej. Zatem ostatni element na liście będzie miał maksymalną odległość. Zastąpimy go nowym przedmiotem i ponownie go posortujemy.
Aby przyspieszyć ten proces, możemy wdrożyć sortowanie przez wstawianie, podczas którego wstawiamy nowe pozycje na listę bez konieczności sortowania całej listy. Kod tego jest jednak dość długi i chociaż prosty, zagłusza samouczek. 
 

c++ int na ciąg

def UpdateNeighbors(neighbors item distance k): if(len(neighbors) > distance): # If yes replace the last # element with new item neighbors[-1] = [distance item['Class']]; neighbors = sorted(neighbors); return neighbors; 

Oblicz klasę sąsiadów

wartość ciągu

Tutaj obliczymy klasę, która pojawia się najczęściej sąsiedzi . W tym celu użyjemy innego słownika o nazwie liczyć gdzie klucze to nazwy klas występujące w sąsiedzi . Jeśli klucz nie istnieje, dodamy go, w przeciwnym razie zwiększymy jego wartość. 
 

def CalculateNeighborsClass(neighbors k): count = {}; for i in range(k): if(neighbors[i][1] not in count): # The class at the ith index # is not in the count dict. # Initialize it to 1. count[neighbors[i][1]] = 1; else: # Found another item of class  # c[i]. Increment its counter. count[neighbors[i][1]] += 1; return count; 

ZnajdźMax

Do tej funkcji wprowadzimy słownik liczyć wbudowujemy się Oblicz klasę sąsiadów i zwrócimy jego max.
 

def FindMax(countList): # Hold the max maximum = -1; # Hold the classification classification = ''; for key in countList.keys(): if(countList[key] > maximum): maximum = countList[key]; classification = key; return classification maximum; 

Wniosek

Na tym ten samouczek kNN jest zakończony.
Możesz teraz klasyfikować ustawienia nowych elementów k według własnego uznania. Zwykle dla k używana jest liczba nieparzysta, ale nie jest to konieczne. Aby sklasyfikować nowy przedmiot należy utworzyć słownik zawierający klucze zawierające nazwy cech i wartości charakteryzujące dany przedmiot. Przykład klasyfikacji:
 

newItem = {'Height' : 1.74 'Weight' : 67 'Age' : 22}; print Classify(newItem 3 items);

Pełny kod powyższego podejścia podano poniżej: - 
 

# Python Program to illustrate # KNN algorithm # For pow and sqrt import math from random import shuffle ###_Reading_### def ReadData(fileName): # Read the file splitting by lines f = open(fileName 'r') lines = f.read().splitlines() f.close() # Split the first line by commas  # remove the first element and save # the rest into a list. The list  # holds the feature names of the  # data set. features = lines[0].split(' ')[:-1] items = [] for i in range(1 len(lines)): line = lines[i].split(' ') itemFeatures = {'Class': line[-1]} for j in range(len(features)): # Get the feature at index j f = features[j] # Convert feature value to float v = float(line[j]) # Add feature value to dict itemFeatures[f] = v items.append(itemFeatures) shuffle(items) return items ###_Auxiliary Function_### def EuclideanDistance(x y): # The sum of the squared differences # of the elements S = 0 for key in x.keys(): S += math.pow(x[key] - y[key] 2) # The square root of the sum return math.sqrt(S) def CalculateNeighborsClass(neighbors k): count = {} for i in range(k): if neighbors[i][1] not in count: # The class at the ith index is # not in the count dict.  # Initialize it to 1. count[neighbors[i][1]] = 1 else: # Found another item of class  # c[i]. Increment its counter. count[neighbors[i][1]] += 1 return count def FindMax(Dict): # Find max in dictionary return  # max value and max index maximum = -1 classification = '' for key in Dict.keys(): if Dict[key] > maximum: maximum = Dict[key] classification = key return (classification maximum) ###_Core Functions_### def Classify(nItem k Items): # Hold nearest neighbours. First item # is distance second class neighbors = [] for item in Items: # Find Euclidean Distance distance = EuclideanDistance(nItem item) # Update neighbors either adding the # current item in neighbors or not. neighbors = UpdateNeighbors(neighbors item distance k) # Count the number of each class  # in neighbors count = CalculateNeighborsClass(neighbors k) # Find the max in count aka the # class with the most appearances return FindMax(count) def UpdateNeighbors(neighbors item distance k ): if len(neighbors) < k: # List is not full add  # new item and sort neighbors.append([distance item['Class']]) neighbors = sorted(neighbors) else: # List is full Check if new  # item should be entered if neighbors[-1][0] > distance: # If yes replace the  # last element with new item neighbors[-1] = [distance item['Class']] neighbors = sorted(neighbors) return neighbors ###_Evaluation Functions_### def K_FoldValidation(K k Items): if K > len(Items): return -1 # The number of correct classifications correct = 0 # The total number of classifications total = len(Items) * (K - 1) # The length of a fold l = int(len(Items) / K) for i in range(K): # Split data into training set # and test set trainingSet = Items[i * l:(i + 1) * l] testSet = Items[:i * l] + Items[(i + 1) * l:] for item in testSet: itemClass = item['Class'] itemFeatures = {} # Get feature values for key in item: if key != 'Class': # If key isn't 'Class' add  # it to itemFeatures itemFeatures[key] = item[key] # Categorize item based on # its feature values guess = Classify(itemFeatures k trainingSet)[0] if guess == itemClass: # Guessed correctly correct += 1 accuracy = correct / float(total) return accuracy def Evaluate(K k items iterations): # Run algorithm the number of # iterations pick average accuracy = 0 for i in range(iterations): shuffle(items) accuracy += K_FoldValidation(K k items) print accuracy / float(iterations) ###_Main_### def main(): items = ReadData('data.txt') Evaluate(5 5 items 100) if __name__ == '__main__': main() 

Wyjście: 

0.9375

Wydajność może się różnić w zależności od maszyny. Kod zawiera funkcję Fold Validation, ale nie jest ona powiązana z algorytmem służącym do obliczania dokładności algorytmu.