Forudsætning: K nærmeste naboer 
 

Indledning

Lad os sige, at vi får et datasæt af elementer, der hver har numerisk værdifulde funktioner (såsom højde og vægt alder osv.). Hvis antallet af funktioner er n vi kan repræsentere emnerne som punkter i en n -dimensionelt gitter. Givet en ny vare kan vi beregne afstanden fra varen til hver anden vare i sættet. Vi vælger k nærmeste naboer og vi ser hvor de fleste af disse naboer er klassificeret i. Vi klassificerer den nye vare der.
Så problemet bliver hvordan vi kan beregne afstanden mellem varer. Løsningen på dette afhænger af datasættet. Hvis værdierne er reelle, bruger vi normalt den euklidiske afstand. Hvis værdierne er kategoriske eller binære, bruger vi normalt Hamming-afstanden.
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

Læsning af data

hvad er linux-filsystemet

Lad vores inputfil 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 klassificeret i. Værdierne under funktionsnavnene ('Højde' osv.) er den værdi, varen har for den funktion. Alle værdier og funktioner er adskilt af kommaer.
Placer disse datafiler i arbejdsmappen data2 og data . Vælg en og indsæt indholdet som det er i en tekstfil med navnet data .
Vi læser fra filen (navngivet 'data.txt'), og vi opdeler inputtet efter linjer:
 

java brugerinput

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

Den første linje i filen indeholder funktionsnavnene med nøgleordet 'Klasse' i slutningen. Vi ønsker at gemme funktionsnavnene på 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 datasættet. Vi gemmer emnerne på en liste med navn genstande hvis elementer er ordbøger (en for hvert emne). Nøglerne til disse vareordbøger er funktionsnavnene plus 'Klasse' for at holde vareklassen. Til sidst vil vi blande emnerne på listen (dette er en sikkerhedsforanstaltning, hvis emnerne er i en mærkelig rækkefø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); 

Klassificering af data

Med data gemt i genstande vi begynder nu at bygge vores klassificering. Til klassificeringen vil vi oprette en ny funktion Klassificer . Det vil tage som input det element, vi ønsker at klassificere emnelisten og k antallet af de nærmeste naboer.
Hvis k er større end længden af ​​datasættet går vi ikke videre med klassificeringen, da vi ikke kan have flere nærmeste naboer end den samlede mængde af varer i datasættet. (Alternativt kunne vi indstille k som genstande længde i stedet for at returnere en fejlmeddelelse)
 

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

Vi ønsker at beregne afstanden mellem det emne, der skal klassificeres, og alle emnerne i træningssættet i sidste ende, idet vi holder k korteste afstande. For at beholde de nuværende nærmeste naboer bruger vi en liste kaldet naboer . Hvert element i det mindste har to værdier, en for afstanden fra det element, der skal klassificeres, og en anden for den klasse, naboen er i. Vi vil beregne afstanden via den generaliserede euklidiske formel (for n dimensioner). Så vælger vi den klasse, der optræder det meste af tiden naboer og det vil være vores valg. I kode: 
 

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 funktioner vi skal implementere er Euklidisk Afstand Opdater Naboer Beregn NaboerKlasse og FindMax .
 

At finde euklidisk afstand

Den generaliserede euklidiske formel 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 kode: 

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

Opdatering af naboer

Vi har vores naboliste (som højst bør have en længde på k ), og vi ønsker at tilføje et element til listen med en given afstand. Først vil vi tjekke om naboer have en længde på k . Hvis den har mindre, tilføjer vi varen til den uanset afstanden (som vi skal fylde listen op til k før vi begynder at afvise varer). Hvis ikke vil vi tjekke om varen har en kortere afstand end varen med max afstand på listen. Hvis det er sandt, erstatter vi varen med max afstand med den nye vare.
For at finde den maksimale afstand hurtigere vil vi holde listen sorteret i stigende rækkefølge. Så det sidste punkt på listen vil have den maksimale afstand. Vi erstatter den med en ny vare, og vi sorterer den igen.
For at fremskynde denne proces kan vi implementere en indsættelsessortering, hvor vi indsætter nye elementer i listen uden at skulle sortere hele listen. Koden til dette er dog temmelig lang, og selvom den er enkel, vil tutorialen 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; 

Beregn NaboerKlasse

Her vil vi beregne den klasse, der optræder oftest i naboer . Til det vil vi bruge en anden ordbog kaldet tælle hvor nøglerne er klassenavnene, der vises i naboer . Hvis en nøgle ikke eksisterer, tilføjer vi den, ellers øger vi dens værdi. 
 

sammensat primær nøgle

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

Vi vil indtaste ordbogen til denne funktion tælle vi bygger ind Beregn NaboerKlasse og vi vil returnere dens 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; 

Konklusion

Dermed er denne kNN-tutorial færdig.
Du kan nu klassificere nye elementer k som du finder passende. Normalt bruges et ulige tal for k, men det er ikke nødvendigt. For at klassificere et nyt emne skal du oprette en ordbog med tasterne funktionsnavnene og de værdier, der karakteriserer emnet. Et eksempel på klassificering:
 

hvad er f5 på tastaturet

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

Den komplette kode for ovenstående tilgang er givet 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() 

Produktion: 

0.9375

Outputtet kan variere fra maskine til maskine. Koden inkluderer en Fold Validation funktion, men den er ikke relateret til algoritmen, den er der til at beregne nøjagtigheden af ​​algoritmen.