Forutsetning: K nærmeste naboer 
 

Introduksjon

La oss si at vi får et datasett med elementer som hver har numerisk verdsatte funksjoner (som høyde og vekt alder osv.). Hvis antallet funksjoner er n vi kan representere elementene som punkter i en n -dimensjonalt rutenett. Gitt en ny vare kan vi beregne avstanden fra varen til annenhver vare i settet. Vi velger k nærmeste naboer og vi ser hvor de fleste av disse naboene er klassifisert i. Vi klassifiserer den nye varen der.
Så problemet blir hvordan vi kan beregne avstandene mellom varer. Løsningen på dette avhenger av datasettet. Hvis verdiene er reelle bruker vi vanligvis den euklidiske avstanden. Hvis verdiene er kategoriske eller binære, bruker vi vanligvis Hamming-avstanden.
Algoritme:  
 

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

Lese data

gimp hvordan velge bort

La vår inndatafil være i følgende 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

Hver vare er en linje og under 'Klasse' ser vi hvor varen er klassifisert i. Verdiene under funksjonsnavnene ('Høyde' osv.) er verdien varen har for den funksjonen. Alle verdiene og funksjonene er atskilt med komma.
Plasser disse datafilene i arbeidskatalogen data2 og data . Velg en og lim inn innholdet som det er i en tekstfil med navnet data .
Vi vil lese fra filen (kalt 'data.txt') og vi deler inndataene etter linjer:
 

java brukerinndata

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

Den første linjen i filen inneholder funksjonsnavnene med nøkkelordet 'Klasse' på slutten. Vi ønsker å lagre funksjonsnavnene i en liste:
 

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

Så går vi videre til selve datasettet. Vi vil lagre elementene i en liste med navn gjenstander hvis elementer er ordbøker (en for hvert element). Nøklene til disse vareordbøkene er funksjonsnavnene pluss 'Klasse' for å holde vareklassen. Til slutt ønsker vi å blande elementene i listen (dette er et sikkerhetstiltak i tilfelle varene er i en merkelig rekkefølge). 
 

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

Klassifisering av data

Med dataene lagret i gjenstander vi begynner nå å bygge klassifisereren vår. For klassifikatoren vil vi lage en ny funksjon Klassifisere . Det vil ta som input elementet vi ønsker å klassifisere varelisten og k antall nærmeste naboer.
Hvis k er større enn lengden på datasettet går vi ikke videre med klassifiseringen da vi ikke kan ha flere nærmeste naboer enn den totale mengden elementer i datasettet. (Alternativt kan vi sette k som gjenstander lengde i stedet for å returnere en feilmelding)
 

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

Vi ønsker å beregne avstanden mellom elementet som skal klassifiseres og alle elementene i treningssettet til slutt, mens vi holder k korteste avstander. For å beholde de nåværende nærmeste naboene bruker vi en liste som heter naboer . Hvert element i det minste har to verdier en for avstanden fra elementet som skal klassifiseres og en annen for klassen naboen er i. Vi vil beregne avstand via den generaliserte euklidiske formelen (for n dimensjoner). Da velger vi klassen som dukker opp mesteparten av tiden i naboer og det vil være vårt valg. I koden: 
 

liste streng java

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

De eksterne funksjonene vi må implementere er Euklidisk avstand Oppdater naboer BeregnNaboerKlasse og Finn Maks .
 

Finne euklidisk avstand

Den generaliserte euklidiske formelen for to vektorer x og y er denne: 

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

I koden: 

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

Oppdaterer naboer

Vi har vår naboliste (som maksimalt bør ha en lengde på k ) og vi ønsker å legge til et element i listen med en gitt avstand. Først skal vi sjekke om naboer ha en lengde på k . Hvis den har mindre, legger vi varen til den uavhengig av avstanden (som vi må fylle listen opp til k før vi begynner å avvise varer). Hvis ikke vil vi sjekke om varen har kortere avstand enn varen med maks avstand i listen. Hvis det stemmer, vil vi erstatte varen med maks avstand med den nye varen.
For å finne den maksimale avstanden raskere vil vi holde listen sortert i stigende rekkefølge. Så det siste elementet på listen vil ha maks avstand. Vi vil erstatte den med en ny vare og vi vil sortere den på nytt.
For å fremskynde denne prosessen kan vi implementere en innsettingssortering der vi setter inn nye elementer i listen uten å måtte sortere hele listen. Koden for dette er imidlertid ganske lang, og selv om den er enkel, vil opplæringen gå ned. 
 

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; 

BeregnNaboerKlasse

Her skal vi beregne den klassen som dukker opp oftest i naboer . Til det vil vi bruke en annen ordbok kalt telle der nøklene er klassenavnene som vises i naboer . Hvis en nøkkel ikke eksisterer, legger vi den til, ellers øker vi verdien. 
 

java variabel variabel

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; 

Finn Maks

Vi vil legge inn ordboken til denne funksjonen telle vi bygger inn BeregnNaboerKlasse og vi vil returnere maks.
 

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; 

Konklusjon

Dermed er denne kNN-opplæringen ferdig.
Du kan nå klassifisere nye elementer k slik du synes det passer. Vanligvis brukes et oddetall for k, men det er ikke nødvendig. For å klassifisere et nytt element må du lage en ordbok med tastene funksjonsnavnene og verdiene som karakteriserer elementet. Et eksempel på klassifisering:
 

c# eksempelkode

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

Den fullstendige koden for tilnærmingen ovenfor er gitt nedenfor: - 
 

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

Produksjon: 

0.9375

Utgangen kan variere fra maskin til maskin. Koden inkluderer en Fold Validation-funksjon, men den er ikke relatert til algoritmen den er der for å beregne nøyaktigheten til algoritmen.