Előfeltétel: K legközelebbi szomszédok 
 

Bevezetés

Tegyük fel, hogy kapunk egy adathalmazt olyan tételekből, amelyek mindegyike számszerűen értékelt tulajdonságokkal rendelkezik (például Magasság Súly Életkor stb.). Ha a jellemzők száma az n pontokként ábrázolhatjuk az elemeket an n -dimenziós rács. Adott egy új elem, ki tudjuk számítani a távolságot az elemtől a készletben lévő összes többi elemtől. Kiválasztjuk a k a legközelebbi szomszédok, és látjuk, hogy ezeknek a szomszédoknak a többsége hova van besorolva. Oda soroljuk az új elemet.
Tehát a probléma válik hogyan tudjuk kiszámítani az elemek közötti távolságokat. Ennek megoldása az adatkészlettől függ. Ha az értékek valósak, akkor általában az euklideszi távolságot használjuk. Ha az értékek kategoriálisak vagy binárisak, általában a Hamming-távolságot használjuk.
Algoritmus:  
 

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

Adatok olvasása

Legyen a bemeneti fájlunk a következő formátumban:
 

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

Minden elem egy sor, és az 'Osztály' alatt láthatjuk, hogy az elem hova van besorolva. A jellemzők neve alatti értékek ('Magasság' stb.) az elemnek az adott tulajdonsághoz tartozó értékei. Az összes érték és jellemző vesszővel van elválasztva.
Helyezze ezeket az adatfájlokat a munkakönyvtárba adatok2 és adat . Válasszon egyet, és illessze be a tartalmat a jelenlegi állapotában egy szöveges fájlba adat .
Beolvasunk a fájlból (amelynek neve 'data.txt'), és a bemenetet sorokra osztjuk:
 

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

A fájl első sora tartalmazza a tereptárgyneveket, a végén a „Class” kulcsszóval. A funkcióneveket egy listában szeretnénk tárolni:
 

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

Ezután áttérünk magára az adathalmazra. nevű listába mentjük az elemeket tételeket melynek elemei szótárak (minden tételhez egy). Ezen elemszótárak kulcsai a jellemzők nevei, valamint az „Osztály” az elemosztályt hordozó. A végén összekeverjük a listán szereplő elemeket (ez biztonsági intézkedés arra az esetre, ha a tételek furcsa sorrendben vannak). 
 

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

Az adatok osztályozása

A tárolt adatokkal tételeket most kezdjük el építeni az osztályozónkat. Az osztályozóhoz egy új függvényt hozunk létre Osztályozás . Bemenetként azt az elemet fogja beírni, amelyet be szeretnénk sorolni a tétellistába, és k a legközelebbi szomszédok száma.
Ha k nagyobb, mint az adathalmaz hossza, nem folytatjuk az osztályozást, mivel nem lehet több legközelebbi szomszédunk, mint az adathalmaz összes elemszáma. (Alternatív megoldásként beállíthatjuk a k-t a tételeket hosszúság a hibaüzenet visszaadása helyett)
 

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

Ki akarjuk számolni a távolságot a besorolandó tétel és a képzési készlet összes eleme között, végül megtartva a k legrövidebb távolságok. A jelenlegi legközelebbi szomszédok megtartásához egy listát használunk szomszédok . A legkisebb elem minden eleme két értékkel rendelkezik, az egyik a besorolandó elemtől való távolságra, a másik pedig a szomszéd osztályára. A távolságot az általánosított euklideszi képlet alapján számítjuk ki (a n méretek). Ezután kiválasztjuk azt az osztályt, amelyik legtöbbször megjelenik szomszédok és ez lesz a mi választásunk. Kódban: 
 

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

Azok a külső funkciók, amelyeket megvalósítanunk kell Euklideszi Távolság Frissítse a szomszédokat CalculateNeighborsClass és FindMax .
 

Euklideszi távolság keresése

Az általánosított euklideszi képlet két x és y vektorra a következő: 

java a szünethez

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

Kódban: 

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

Szomszédok frissítése

Megvan a szomszédok listája (amelynek legfeljebb hosszúnak kell lennie k ), és egy adott távolságú elemet szeretnénk hozzáadni a listához. Először ellenőrizzük, hogy szomszédok hossza van k . Ha kevesebb van benne, akkor a távolságtól függetlenül hozzáadjuk a tételt (hiszen a listát ki kell töltenünk k mielőtt elkezdenénk elutasítani a tételeket). Ha nem, akkor ellenőrizzük, hogy a tétel távolsága rövidebb-e, mint a listában szereplő maximális távolsággal rendelkező tétel. Ha ez igaz, akkor a maximális távolságú elemet kicseréljük az új elemre.
A maximális távolság elem gyorsabb megtalálása érdekében a listát növekvő sorrendben rendezzük. Tehát a lista utolsó eleme lesz a maximális távolság. Kicseréljük egy új elemre, és újra válogatjuk.
Ennek a folyamatnak a felgyorsítása érdekében beillesztési rendezést valósíthatunk meg, ahol új elemeket szúrunk be a listába anélkül, hogy a teljes listát kellene rendezni. Ennek a kódja azonban meglehetősen hosszú, és bár az egyszerű, az oktatóanyagot leállítja. 
 

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; 

CalculateNeighborsClass

Itt kiszámoljuk a leggyakrabban megjelenő osztályt szomszédok . Ehhez egy másik szótárt fogunk használni gróf ahol a kulcsok a benne szereplő osztálynevek szomszédok . Ha egy kulcs nem létezik, hozzáadjuk, ellenkező esetben növeljük az értékét. 
 

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

Ehhez a függvényhez beírjuk a szótárat gróf beépítjük CalculateNeighborsClass és visszaadjuk a 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; 

Következtetés

Ezzel ez a kNN oktatóanyag véget ért.
Most már besorolhatja az új elemek beállítását k ahogy jónak látja. Általában k esetén páratlan számot használnak, de ez nem szükséges. Egy új elem besorolásához létre kell hozni egy szótárt, amely tartalmazza a kulcsokat, a jellemzők neveit és az elemet jellemző értékeket. Példa az osztályozásra:
 

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

A fenti megközelítés teljes kódja az alábbiakban található: - 
 

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

Kimenet: 

0.9375

A kimenet gépenként változhat. A kód tartalmaz egy Fold Validation függvényt, de nem kapcsolódik az algoritmushoz, hanem az algoritmus pontosságának kiszámítására szolgál.