Būtina sąlyga: K arčiausiai kaimynai 
 

Įvadas

cobol programavimas

Tarkime, kad mums pateikiamas duomenų rinkinys elementų, kurių kiekvienas turi skaitines savybes (pvz., ūgis, svoris, amžius ir kt.). Jei funkcijų skaičius yra n elementus galime pavaizduoti kaip taškus an n - matmenų tinklelis. Atsižvelgdami į naują prekę, galime apskaičiuoti atstumą nuo prekės iki visų kitų rinkinio elementų. Mes pasirenkame k artimiausi kaimynai ir mes matome, kur dauguma šių kaimynų yra klasifikuojami. Ten klasifikuojame naują elementą.
Taigi problema tampa kaip galime apskaičiuoti atstumus tarp daiktų. Šios problemos sprendimas priklauso nuo duomenų rinkinio. Jei reikšmės yra tikros, dažniausiai naudojame Euklido atstumą. Jei reikšmės yra kategorinės arba dvejetainės, dažniausiai naudojame Hamingo atstumą.
Algoritmas:  
 

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

Duomenų skaitymas

Tegul mūsų įvesties failas yra tokio formato:
 

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

Kiekvienas elementas yra eilutė, o skiltyje „Klasė“ matome, kur elementas yra klasifikuojamas. Reikšmės po objektų pavadinimais („Aukštis“ ir tt) yra tos funkcijos elemento reikšmė. Visos reikšmės ir savybės atskiriamos kableliais.
Įdėkite šiuos duomenų failus į darbo katalogą duomenys2 ir duomenis . Pasirinkite vieną ir įklijuokite turinį tokį, koks yra, į tekstinį failą pavadinimu duomenis .
Perskaitysime iš failo (pavadinto „data.txt“) ir įvestį padalinsime eilutėmis:
 

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

Pirmoje failo eilutėje yra objektų pavadinimai, kurių pabaigoje yra raktinis žodis „Klasė“. Mes norime išsaugoti funkcijų pavadinimus sąraše:
 

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

Tada pereiname prie paties duomenų rinkinio. Elementus išsaugosime sąraše pavadinimu daiktų kurių elementai yra žodynai (po vieną kiekvienam elementui). Šių elementų žodynų raktai yra elementų pavadinimai ir „Klasė“, kad būtų nurodyta elemento klasė. Galų gale norime sumaišyti sąraše esančius elementus (tai yra saugos priemonė, jei daiktai yra keista tvarka). 
 

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

Duomenų klasifikavimas

Su duomenimis, saugomais į daiktų dabar pradedame kurti savo klasifikatorių. Klasifikatoriui sukursime naują funkciją Klasifikuoti . Kaip įvestis bus elementas, kurį norime klasifikuoti prekių sąraše ir k artimiausių kaimynų skaičius.
Jeigu k yra didesnis nei duomenų rinkinio ilgis, mes nevykdome klasifikavimo, nes negalime turėti daugiau artimiausių kaimynų nei bendras elementų kiekis duomenų rinkinyje. (arba galime nustatyti k kaip daiktų ilgio, o ne grąžinti klaidos pranešimą)
 

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

Mes norime apskaičiuoti atstumą tarp klasifikuojamo elemento ir visų mokymo rinkinio elementų, galų gale išlaikant k trumpiausius atstumus. Norėdami išlaikyti esamus artimiausius kaimynus, naudojame sąrašą pavadinimu kaimynai . Kiekvienas mažiausiai elementas turi dvi reikšmes: vieną atstumą nuo klasifikuojamo elemento, o kitą – klasei, kurioje yra kaimynas. Apskaičiuosime atstumą pagal apibendrintą Euklido formulę (skirta n matmenys). Tada mes pasirinksime klasę, kuri rodoma dažniausiai kaimynai ir tai bus mūsų pasirinkimas. Kode: 
 

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

Išorinės funkcijos, kurias turime įgyvendinti, yra Euklido atstumas Atnaujinti kaimynus ApskaičiuokiteKaimynų klasę ir FindMax .
 

Euklido atstumo radimas

Apibendrinta dviejų vektorių x ir y Euklido formulė yra tokia: 

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

Kode: 

Java duomenų tipai

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

Kaimynų atnaujinimas

Turime savo kaimynų sąrašą (kuris turėtų būti ilgiausias k ) ir norime į sąrašą įtraukti elementą su nurodytu atstumu. Pirmiausia patikrinsime, ar kaimynai turėti ilgį k . Jei jo yra mažiau, mes pridedame prie jo prekę, neatsižvelgdami į atstumą (nes turime užpildyti sąrašą iki k prieš pradėdami atmesti elementus). Jei ne, patikrinsime, ar prekė turi trumpesnį atstumą nei prekė, kurios atstumas yra didžiausias sąraše. Jei tai tiesa, mes pakeisime prekę su maksimaliu atstumu nauja preke.
Norėdami greičiau rasti didžiausio atstumo elementą, sąrašą liksime surūšiuoti didėjimo tvarka. Taigi paskutinis sąrašo elementas turės didžiausią atstumą. Pakeisime jį nauja preke ir vėl rūšiuosime.
Norėdami pagreitinti šį procesą, galime įdiegti įterpimo rūšiavimą, kai į sąrašą įterpiame naujus elementus nerūšiuodami viso sąrašo. Kodas šiam tikslui yra gana ilgas ir, nors ir paprastas, užblokuos mokymo programą. 
 

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; 

ApskaičiuokiteKaimynų klasę

Čia apskaičiuosime klasę, kuri pasirodo dažniausiai kaimynai . Tam naudosime kitą žodyną skaičiuoti kur klavišai yra klasių pavadinimai kaimynai . Jei rakto nėra, mes jį pridėsime, kitaip padidinsime jo vertę. 
 

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

Į šią funkciją įvesime žodyną skaičiuoti statome ApskaičiuokiteKaimynų klasę ir mes grąžinsime jo 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; 

Išvada

Tuo ši kNN pamoka baigta.
Dabar galite klasifikuoti naujų elementų nustatymą k kaip tau atrodo tinkama. Paprastai k naudojamas nelyginis skaičius, bet tai nėra būtina. Norėdami klasifikuoti naują elementą, turite sukurti žodyną su raktais, elementų pavadinimais ir elementą apibūdinančiomis reikšmėmis. Klasifikavimo pavyzdys:
 

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

Visas pirmiau minėto metodo kodas pateikiamas žemiau: 
 

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

Išvestis: 

0.9375

Išeiga gali skirtis priklausomai nuo mašinos. Kode yra lankstymo patvirtinimo funkcija, tačiau ji nesusijusi su algoritmu, kuris yra skirtas algoritmo tikslumui apskaičiuoti.