Condiție preliminară: K cel mai apropiat vecinii 
 

Introducere

Să presupunem că ni se oferă un set de date de articole, fiecare având caracteristici evaluate numeric (cum ar fi Înălțimea Greutatea Vârsta etc.). Dacă numărul caracteristicilor este n putem reprezenta elementele ca puncte într-un n -grilă dimensională. Având în vedere un articol nou, putem calcula distanța de la articol la orice alt element din set. Alegem k cei mai apropiați vecini și vedem unde sunt clasificați cei mai mulți dintre acești vecini. Clasificăm noul element acolo.
Deci problema devine cum putem calcula distanțele dintre elemente. Soluția la aceasta depinde de setul de date. Dacă valorile sunt reale, folosim de obicei distanța euclidiană. Dacă valorile sunt categorice sau binare, folosim de obicei distanța Hamming.
Algoritm:  
 

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

Citirea datelor

Fișierul nostru de intrare să fie în următorul format:
 

top 10 hentai

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

Fiecare articol este o linie și sub „Clasă” vedem unde este clasificat elementul. Valorile de sub numele caracteristicilor („Înălțime” etc.) sunt valoarea pe care o are elementul pentru acea caracteristică. Toate valorile și caracteristicile sunt separate prin virgule.
Plasați aceste fișiere de date în directorul de lucru date2 şi date . Alegeți unul și inserați conținutul așa cum este într-un fișier text numit date .
Vom citi din fișier (numit „data.txt”) și vom împărți intrarea pe rânduri:
 

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

Prima linie a fișierului conține numele caracteristicilor cu cuvântul cheie „Class” la sfârșit. Dorim să stocăm numele caracteristicilor într-o listă:
 

bharti jha

# 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];

Apoi trecem la setul de date în sine. Vom salva articolele într-o listă numită articole ale căror elemente sunt dicționare (câte unul pentru fiecare articol). Cheile acestor dicționare de articole sunt numele caracteristicilor plus „Clasă” pentru a menține clasa de articole. În final, vrem să amestecăm articolele din listă (aceasta este o măsură de siguranță în cazul în care articolele sunt într-o ordine ciudată). 
 

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); 

Clasificarea datelor

Cu datele stocate în articole acum începem să construim clasificatorul nostru. Pentru clasificator vom crea o nouă funcție Clasifica . Va lua ca intrare elementul pe care vrem sa-l clasificam in lista de articole si k numărul celor mai apropiați vecini.
Dacă k este mai mare decât lungimea setului de date, nu continuăm cu clasificarea, deoarece nu putem avea mai mulți vecini apropiați decât cantitatea totală de articole din setul de date. (în mod alternativ, am putea seta k drept articole lungime în loc să returneze un mesaj de eroare)
 

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

Dorim să calculăm distanța dintre elementul de clasificat și toate articolele din setul de antrenament în final, păstrând k cele mai scurte distante. Pentru a păstra cei mai apropiați vecini actuali folosim o listă numită vecinii . Fiecare element are cel puțin două valori, una pentru distanța de la elementul de clasificat și alta pentru clasa în care se află vecinul. Vom calcula distanța prin formula euclidiană generalizată (pentru n dimensiuni). Apoi vom alege clasa care apare de cele mai multe ori în vecinii și asta va fi alegerea noastră. În cod: 
 

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); 

Funcțiile externe pe care trebuie să le implementăm sunt EuclidianDistance Actualizați Vecinii Calculate NeighborsClass şi FindMax .
 

Găsirea distanței euclidiene

Formula euclidiană generalizată pentru doi vectori x și y este următoarea: 

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

În cod: 

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); 

Actualizarea vecinilor

Avem lista vecinilor noștri (care ar trebui să aibă cel mult o lungime de k ) și dorim să adăugăm un articol la listă cu o anumită distanță. Mai întâi vom verifica dacă vecinii au o lungime de k . Dacă are mai puțin, adăugăm elementul la el, indiferent de distanță (deoarece trebuie să umplem lista până la k înainte de a începe să respingem articole). Dacă nu, vom verifica dacă articolul are o distanță mai mică decât articolul cu distanța maximă din listă. Dacă este adevărat, vom înlocui articolul cu distanța maximă cu noul articol.
Pentru a găsi mai rapid elementul distanță maximă, vom păstra lista sortată în ordine crescătoare. Deci ultimul element din listă va avea distanța maximă. Îl vom înlocui cu un articol nou și îl vom sorta din nou.
Pentru a accelera acest proces, putem implementa un Insertion Sort în care inserăm elemente noi în listă fără a fi nevoie să sortăm întreaga listă. Codul pentru aceasta este totuși destul de lung și, deși simplu, va bloca tutorialul. 
 

listbox java

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; 

Calculate NeighborsClass

Aici vom calcula clasa în care apare cel mai des vecinii . Pentru asta vom folosi un alt dicționar numit conta unde cheile sunt numele claselor care apar vecinii . Dacă o cheie nu există, o vom adăuga, altfel îi vom incrementa valoarea. 
 

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; 

FindMax

Vom introduce în această funcție dicționarul conta construim în Calculate NeighborsClass si ii vom returna 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; 

Concluzie

teoria arborilor și grafurilor

Cu asta, acest tutorial kNN este terminat.
Acum puteți clasifica setarea articolelor noi k dupa cum crezi tu de cuviinta. De obicei, pentru k se folosește un număr impar, dar nu este necesar. Pentru a clasifica un articol nou trebuie să creați un dicționar cu chei, numele caracteristicilor și valorile care caracterizează elementul. Un exemplu de clasificare:
 

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

Codul complet al abordării de mai sus este prezentat mai jos: - 
 

# 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() 

Ieșire: 

0.9375

Ieșirea poate varia de la o mașină la alta. Codul include o funcție de validare Fold, dar nu are legătură cu algoritmul, acesta este acolo pentru a calcula acuratețea algoritmului.