Edellytys: K lähin naapurit 
 

merkkijonojen käsittely c++:ssa

Johdanto

Oletetaan, että meille annetaan tietojoukko kohteista, joista jokaisella on numeerisesti arvostettuja ominaisuuksia (kuten Pituus Paino Ikä jne.). Jos ominaisuuksien määrä on n voimme esittää kohteita pisteinä an n -ulotteinen ruudukko. Kun uusi esine on annettu, voimme laskea etäisyyden tuotteesta jokaiseen sarjan muihin esineisiin. Valitsemme k lähimmät naapurit ja näemme mihin suurin osa näistä naapureista on luokiteltu. Luokittelemme uuden kohteen sinne.
Joten ongelmasta tulee kuinka voimme laskea kohteiden väliset etäisyydet. Ratkaisu tähän riippuu tietojoukosta. Jos arvot ovat todellisia, käytämme yleensä euklidista etäisyyttä. Jos arvot ovat kategorisia tai binaarisia, käytämme yleensä Hamming-etäisyyttä.
Algoritmi:  
 

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

Datan lukeminen

Olkoon syöttötiedostomme seuraavassa muodossa:
 

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

Jokainen kohde on rivi, ja 'Class'-kohdassa näemme, mihin kohde on luokiteltu. Ominaisuuden nimien alla olevat arvot ("Korkeus" jne.) ovat arvot, jotka kohteella on kyseiselle ominaisuudelle. Kaikki arvot ja ominaisuudet on erotettu pilkuilla.
Sijoita nämä tiedostot työhakemistoon data2 ja tiedot . Valitse yksi ja liitä sisältö sellaisenaan tekstitiedostoon nimeltä tiedot .
Luemme tiedostosta (nimeltään 'data.txt') ja jaamme syötteen riveillä:
 

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

Tiedoston ensimmäisellä rivillä on ominaisuuksien nimet, joiden lopussa on avainsana "Class". Haluamme tallentaa ominaisuuksien nimet luetteloon:
 

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

Sitten siirrymme itse tietojoukkoon. Tallennamme kohteet luetteloon nimeltä kohteita jonka elementit ovat sanakirjoja (yksi jokaista kohdetta kohden). Näihin sanakirjoihin avaimet ovat ominaisuuksien nimet sekä 'Luokka', joka sisältää alkioluokan. Lopuksi haluamme sekoittaa luettelossa olevat kohteet (tämä on turvatoimenpide, jos tavarat ovat oudossa järjestyksessä). 
 

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

Tietojen luokittelu

Kun tiedot on tallennettu kohteita Aloitamme nyt luokittelumme rakentamisen. Luokittelijalle luomme uuden funktion Luokitella . Se ottaa syötteenä kohteen, jonka haluamme luokitella tuoteluettelon ja k lähimpien naapureiden lukumäärä.
Jos k on suurempi kuin tietojoukon pituus, emme jatka luokittelua, koska meillä ei voi olla enemmän lähimpiä naapureita kuin tietojoukon kohteiden kokonaismäärä. (Vaihtoehtoisesti voisimme asettaa k:ksi kohteita pituus virheilmoituksen palauttamisen sijaan)
 

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

Haluamme laskea luokiteltavan esineen ja kaikkien harjoitussarjassa olevien kohteiden välisen etäisyyden lopuksi pitäen k lyhyimmät etäisyydet. Säilyttääksemme nykyiset lähimmät naapurit käytämme listaa nimeltä naapurit . Jokaisella vähiten elementillä on kaksi arvoa, joista yksi kertoo etäisyydestä luokiteltavasta kohteesta ja toinen luokasta, jossa naapuri on. Laskemme etäisyyden yleistetyn euklidisen kaavan avulla (for n mitat). Sitten valitsemme luokan, joka esiintyy suurimman osan ajasta naapurit ja se on meidän valintamme. Koodissa: 
 

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

Ulkoiset toiminnot, jotka meidän on toteutettava, ovat Euklidinen etäisyys Päivitä Naapurit LaskeNaapuriluokka ja FindMax .
 

Euklidisen etäisyyden löytäminen

kielet c

Yleinen euklidinen kaava kahdelle vektorille x ja y on tämä: 

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

Koodissa: 

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

Naapureita päivitetään

Meillä on naapuriluettelomme (jonka pitäisi olla korkeintaan pitkä k ) ja haluamme lisätä luetteloon kohteen tietyllä etäisyydellä. Ensin tarkistetaan onko naapurit on pituus k . Jos siinä on vähemmän, lisäämme tuotteen siihen etäisyydestä riippumatta (koska meidän on täytettävä luettelo k ennen kuin alamme hylätä kohteita). Jos ei, tarkistamme, onko tuotteella lyhyempi etäisyys kuin tuotteella, jonka enimmäisetäisyys on luettelossa. Jos tämä on totta, korvaamme tuotteen, jolla on enimmäisetäisyys, uudella tuotteella.
Löytääksemme enimmäisetäisyyden kohteen nopeammin, pidämme luettelon nousevassa järjestyksessä. Joten luettelon viimeisellä kohteella on enimmäisetäisyys. Korvaamme sen uudella tuotteella ja lajittelemme sen uudelleen.
Tämän prosessin nopeuttamiseksi voimme ottaa käyttöön lisäyslajittelun, jossa lisäämme uusia kohteita luetteloon ilman, että koko luetteloa tarvitsee lajitella. Tämän koodi on kuitenkin melko pitkä, ja vaikka se on yksinkertainen, se tukkii opetusohjelman. 
 

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; 

LaskeNaapuriluokka

Tässä lasketaan luokka, joka esiintyy useimmin naapurit . Tätä varten käytämme toista sanakirjaa nimeltä laskea jossa avaimet ovat luokkien nimiä naapurit . Jos avainta ei ole olemassa, lisäämme sen, muuten lisäämme sen arvoa. 
 

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

java listalaatikko

Syötämme tähän funktioon sanakirjan laskea rakennamme sisään LaskeNaapuriluokka ja palautamme sen 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; 

Johtopäätös

Näin tämä kNN-opetusohjelma on valmis.
Voit nyt luokitella uudet kohteet -asetuksen k kuten parhaaksi näet. Yleensä k:lle käytetään paritonta lukua, mutta se ei ole välttämätöntä. Luokittaaksesi uuden kohteen, sinun on luotava sanakirja, jossa on avaimet, ominaisuuksien nimet ja arvot, jotka kuvaavat kohdetta. Esimerkki luokittelusta:
 

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

Yllä olevan lähestymistavan täydellinen koodi on annettu alla: - 
 

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

Lähtö: 

0.9375

Tulos voi vaihdella koneesta toiseen. Koodi sisältää Fold Validation -toiminnon, mutta se ei liity algoritmiin, joka on siinä algoritmin tarkkuuden laskemiseksi.