Voorwaarde: K dichtstbijzijnde buren 
 

Invoering

Stel dat we een dataset krijgen van items die elk numeriek gewaardeerde kenmerken hebben (zoals lengte, gewicht, leeftijd, enz.). Als het aantal functies is N we kunnen de items weergeven als punten in an N -dimensionaal raster. Bij een nieuw item kunnen we de afstand berekenen van het item tot elk ander item in de set. Wij kiezen de k dichtstbijzijnde buren en we zien waar de meeste van deze buren in zijn ingedeeld. Daar classificeren we het nieuwe item.
Het probleem wordt dus hoe we de afstanden tussen items kunnen berekenen. De oplossing hiervoor is afhankelijk van de dataset. Als de waarden reëel zijn, gebruiken we meestal de Euclidische afstand. Als de waarden categorisch of binair zijn, gebruiken we meestal de Hamming-afstand.
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

Gegevens lezen

Laat ons invoerbestand het volgende formaat hebben:
 

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

Elk item is een regel en onder 'Klasse' zien we waar het item in is ingedeeld. De waarden onder de kenmerknamen ('Hoogte' etc.) zijn de waarde die het item voor dat kenmerk heeft. Alle waarden en functies worden gescheiden door komma's.
Plaats deze gegevensbestanden in de werkmap gegevens2 En gegevens . Kies er een en plak de inhoud zoals deze is in een tekstbestand met de naam gegevens .
We lezen uit het bestand (genaamd 'data.txt') en we splitsen de invoer op in regels:
 

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

De eerste regel van het bestand bevat de functienamen met aan het einde het trefwoord 'Klasse'. We willen de functienamen in een lijst opslaan:
 

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

Vervolgens gaan we verder met de dataset zelf. We slaan de items op in een lijst met de naam artikelen waarvan de elementen woordenboeken zijn (één voor elk item). De sleutels tot deze itemwoordenboeken zijn de functienamen plus 'Klasse' om de itemklasse vast te houden. Uiteindelijk willen we de items in de lijst in willekeurige volgorde afspelen (dit is een veiligheidsmaatregel voor het geval de items in een vreemde volgorde staan). 
 

nummer om Java te stringen

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

Het classificeren van de gegevens

Met de gegevens opgeslagen in artikelen we beginnen nu met het bouwen van onze classificator. Voor de classificator zullen we een nieuwe functie maken Classificeren . Als invoer wordt het item gebruikt dat we in de itemlijst willen classificeren k het nummer van de dichtstbijzijnde buren.
Als k groter is dan de lengte van de dataset, gaan we niet verder met classificeren, omdat we niet meer naaste buren kunnen hebben dan het totale aantal items in de dataset. (Als alternatief kunnen we k instellen als de artikelen lengte in plaats van een foutmelding te retourneren)
 

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

We willen de afstand berekenen tussen het te classificeren item en alle items in de trainingsset, waarbij we uiteindelijk de afstand behouden k kortste afstanden. Om de huidige dichtstbijzijnde buren bij te houden gebruiken we een lijst genaamd buren . Elk element bevat op zijn minst twee waarden: één voor de afstand tot het te classificeren item en één voor de klasse waarin de buurman zich bevindt. We zullen de afstand berekenen via de gegeneraliseerde Euclidische formule (voor N afmetingen). Vervolgens kiezen we de klasse die het meeste voorkomt buren en dat zal onze keuze zijn. In code: 
 

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 externe functies die we moeten implementeren zijn: Euclidische afstand Update Buren Bereken BurenKlasse En ZoekMax .
 

Euclidische afstand vinden

De gegeneraliseerde Euclidische formule voor twee vectoren x en y is deze: 

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

In code: 

herhaal de kaart-Java

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

Buren bijwerken

We hebben onze burenlijst (die maximaal een lengte mag hebben van k ) en we willen een item met een bepaalde afstand aan de lijst toevoegen. Eerst zullen we controleren of buren een lengte hebben van k . Als er minder is, voegen we het item eraan toe, ongeacht de afstand (omdat we de lijst moeten vullen tot k voordat we artikelen gaan afwijzen). Indien dit niet het geval is, controleren wij of het artikel een kortere afstand heeft dan het artikel met de maximale afstand in de lijst. Als dat waar is, vervangen we het artikel met de maximale afstand door het nieuwe artikel.
Om het item met de maximale afstand sneller te vinden, houden we de lijst in oplopende volgorde gesorteerd. Het laatste item in de lijst heeft dus de maximale afstand. Wij vervangen het door een nieuw artikel en sorteren het opnieuw.
Om dit proces te versnellen, kunnen we een invoegsortering implementeren, waarbij we nieuwe items in de lijst invoegen zonder de hele lijst te hoeven sorteren. De code hiervoor is echter vrij lang en hoewel eenvoudig, zal de tutorial vastlopen. 
 

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; 

Bereken BurenKlasse

Hier berekenen we de klasse die het vaakst voorkomt buren . Daarvoor zullen we een ander woordenboek gebruiken, genaamd graaf waarbij de sleutels de klassennamen zijn die voorkomen buren . Als een sleutel niet bestaat, zullen we deze toevoegen, anders verhogen we de waarde ervan. 
 

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; 

ZoekMax

We zullen het woordenboek in deze functie invoeren graaf wij bouwen in Bereken BurenKlasse en we zullen het maximum teruggeven.
 

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; 

Conclusie

Daarmee is deze kNN-tutorial klaar.
U kunt nu de instelling voor nieuwe items classificeren k zoals u wilt. Meestal wordt voor k een oneven getal gebruikt, maar dat is niet nodig. Om een ​​nieuw item te classificeren moet u een woordenboek maken met daarin de functienamen en de waarden die het item karakteriseren. Een voorbeeld van classificatie:
 

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

De volledige code van de bovenstaande aanpak wordt hieronder gegeven: - 
 

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

Uitgang: 

0.9375

De output kan variëren van machine tot machine. De code bevat een Fold Validation-functie, maar deze is niet gerelateerd aan het algoritme, maar is bedoeld voor het berekenen van de nauwkeurigheid van het algoritme.