Algoritam k-najbližih suseda
Ova sveska prati lekciju o algoritmu k-najbližih suseda.
Izvrši donju ćeliju i učitaj biblioteke koje će nam biti potrebne u daljem radu.
In [9]:
import numpy as np
from matplotlib import pyplot as plt
Prvo ćemo obraditi podatke. Promenljiva ` instance ` prdstavlja sve instance u skupu podataka. U prvom redu su navedene plave instance, a u drugim crvene. Navedena je posebno i zelena instanca koju treba klasifikovati.
In [10]:
instances = [
(-0.25, 0, 1), (-2.5, 2, 1), (-1.5, 1.5, 1), (-2.5, 0.5, 1), (-2.5, 2, 1), (-2.5, 4, 1), (0.5, 3, 1), # blue
(-1.5, 3.5, 0), (1, 3.5, 0), (3, 3, 0), (0.5, 0.25, 0), (0.75, -0.5, 0) #red
]
green_instance = (0, 0)Sledeća funkcija će nam pomoći da prikažemo susedstvo zelene instance određeno izborom broja ` k `.
In [11]:
def show_neighborhood(k, instances=instances, green_instance=green_instance):
# set up the plot panel
fig, ax = plt.subplots()
ax.set_aspect(1)
ax.set_axis_off()
fig.set_size_inches(5, 5)
# display instances
for instance in instances:
# determine color and shape for each instance
color = 'red' if instance[2] == 0 else 'blue'
shape = '^' if instance[2] == 0 else 's'
ax.scatter(instance[0], instance[1], color=color, marker=shape)
# display the green instance
ax.scatter(green_instance[0], green_instance[1], color='green')
# calculate the distance from the green instance to all instances in the set
distances = np.array([np.sqrt(instance[0]**2 + instance[1]**2) for instance in instances])
# determine the k-th distance
k_distance = np.sort(distances)[k-1]
# draw a circle around the green instance with a radius corresponding to the observed distance
r = k_distance + 0.05
circle = plt.Circle((green_instance[0], green_instance[1]), r, color='gray', linestyle='--', fill=False)
ax.add_patch(circle)
# finally, display the neighborhood
plt.show()
Sada možeš da odabereš vrednost broja k pomeranjem slajdera, a potom i iscrtaš susedstvo i odlučiš o tome kojoj klasi pripada zelena instanca. Da bi iscrtao susedstvo moraš da izvršiš ćeliju.
In [12]:
k = 3 # @param {type:"slider", min:1, max:12, step:1}
show_neighborhood(k)
Sledeća ćelija sadrži funkciju koja klasifikuje novu instancu na osnovu zadatih instanci koristeći algoritma k-najbližih suseda. Nakon što razmisiliš kojoj klasi pripada instanca, možeš da proveriš svoj zaključak izvršavanjem ove funckije.
In [13]:
def euclidean_distance(instance1, instance2):
return np.sqrt((instance1[0]-instance2[0])**2 + (instance1[1]-instance2[1])**2)
In [14]:
def kNN(k, instances, new_instance, classes={0: 'red', 1: 'blue'}):
# first, calculate the distances between the new instance and all instances in the dataset
distances = [euclidean_distance(instance, new_instance) for instance in instances]
# then sort the distances, extract the k smallest ones and the corresponding instances
# declare them as neighbors
neighbors = np.argsort(distances)[0:k]
# then read the labels of the neighbors and count them
neighbor_labels = [instances[neighbor][2] for neighbor in neighbors]
label_counts = np.bincount(neighbor_labels)
# the label of the new instance will be the label of the most frequent neighbor
label = np.argmax(label_counts)
return classes[label]
In [15]:
kNN(3, instances, green_instance)
Out[15]:
'red'
Completion requirements:
- Make a submission