Nödvändig förutsättning: K närmast grannar 
 

Introduktion

Säg att vi får en datamängd med artiklar som var och en har numeriskt värderade funktioner (som höjd vikt ålder etc). Om antalet funktioner är n vi kan representera objekten som punkter i en n -dimensionellt rutnät. Med ett nytt föremål kan vi beräkna avståndet från föremålet till vartannat föremål i uppsättningen. Vi väljer k närmaste grannar och vi ser var de flesta av dessa grannar är klassificerade i. Vi klassificerar den nya varan där.
Så problemet blir hur vi kan beräkna avstånden mellan föremålen. Lösningen på detta beror på datamängden. Om värdena är verkliga använder vi vanligtvis det euklidiska avståndet. Om värdena är kategoriska eller binära använder vi vanligtvis Hamming-avståndet.
Algoritm:  
 

strängjämförelse java

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

Läser data

Låt vår indatafil ha följande 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

Varje föremål är en rad och under 'Klass' ser vi var föremålet är klassificerat i. Värdena under egenskapsnamnen ('Höjd' etc.) är värdet som föremålet har för den egenskapen. Alla värden och funktioner är separerade med kommatecken.
Placera dessa datafiler i arbetskatalogen data2 och data . Välj en och klistra in innehållet som det är i en textfil med namnet data .
Vi läser från filen (som heter 'data.txt') och vi delar upp inmatningen efter rader:
 

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

Den första raden i filen innehåller funktionsnamnen med nyckelordet "Klass" i slutet. Vi vill lagra funktionsnamnen i en lista:
 

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

Sedan går vi vidare till själva datamängden. Vi kommer att spara objekten i en lista med namnet föremål vars element är ordböcker (en för varje objekt). Nycklarna till dessa objektordböcker är funktionsnamnen plus 'Klass' för att hålla objektklassen. I slutändan vill vi blanda artiklarna i listan (detta är en säkerhetsåtgärd om objekten är i en konstig ordning). 
 

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

Klassificering av data

Med data lagrad i föremål vi börjar nu bygga vår klassificerare. För klassificeraren kommer vi att skapa en ny funktion Klassificera . Det kommer att ta som indata objektet vi vill klassificera objektlistan och k antalet närmaste grannar.
Om k är större än längden på datamängden går vi inte vidare med klassificeringen då vi inte kan ha fler närmaste grannar än den totala mängden artiklar i datamängden. (Alternativt kan vi ställa in k som föremål längd istället för att returnera ett felmeddelande)
 

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

Vi vill beräkna avståndet mellan föremålet som ska klassificeras och alla föremål i träningsuppsättningen i slutändan med bibehållen k kortaste avstånden. För att behålla de nuvarande närmaste grannarna använder vi en lista som heter grannar . Varje element i det minsta har två värden, ett för avståndet från objektet som ska klassificeras och ett annat för klassen grannen är i. Vi kommer att beräkna avståndet via den generaliserade euklidiska formeln (för n mått). Sedan väljer vi den klass som dyker upp mest hela tiden grannar och det kommer att vara vårt val. I koden: 
 

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 externa funktionerna vi behöver implementera är Euklidiskt avstånd Uppdatera grannar Beräkna GrannarKlass och Hitta Max .
 

Att hitta euklidiskt avstånd

Den generaliserade euklidiska formeln för två vektorer x och y är denna: 

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

I koden: 

vårens moln

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

Uppdaterar grannar

Vi har vår grannlista (som högst bör ha en längd på k ) och vi vill lägga till ett objekt i listan med ett givet avstånd. Först ska vi kontrollera om grannar har en längd på k . Om den har mindre lägger vi till varan till den oavsett avstånd (som vi behöver fylla listan upp till k innan vi börjar avvisa föremål). Om inte kommer vi att kontrollera om artikeln har ett kortare avstånd än artikeln med maxavstånd i listan. Om det är sant kommer vi att ersätta artikeln med maxavstånd med den nya artikeln.
För att snabbare hitta posten för maxavstånd kommer vi att hålla listan sorterad i stigande ordning. Så det sista objektet i listan kommer att ha maxavståndet. Vi kommer att ersätta den med en ny vara och vi kommer att sortera den igen.
För att påskynda denna process kan vi implementera en infogningssortering där vi infogar nya objekt i listan utan att behöva sortera hela listan. Koden för detta är dock ganska lång och även om den är enkel kommer handledningen att försvinna. 
 

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; 

Beräkna GrannarKlass

Här kommer vi att räkna ut den klass som förekommer oftast i grannar . För det kommer vi att använda en annan ordbok som heter räkna där nycklarna är klassnamnen som visas i grannar . Om en nyckel inte finns lägger vi till den annars ökar vi dess värde. 
 

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; 

Hitta Max

Vi kommer att mata in ordboken till denna funktion räkna vi bygger in Beräkna GrannarKlass och vi kommer att returnera dess 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; 

Slutsats

Med det är denna kNN-tutorial klar.
Du kan nu klassificera nya objektinställningar k som du tycker passar. Vanligtvis för k används ett udda tal men det är inte nödvändigt. För att klassificera ett nytt objekt måste du skapa en ordbok med nycklar funktionsnamnen och de värden som kännetecknar objektet. Ett exempel på klassificering:
 

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

Den fullständiga koden för ovanstående tillvägagångssätt ges nedan: - 
 

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

Produktion: 

0.9375

Effekten kan variera från maskin till maskin. Koden innehåller en Fold Validation-funktion men den är inte relaterad till algoritmen den finns där för att beräkna algoritmens noggrannhet.