Алгоритм KNN, также известный как алгоритм классификации K-ближайших соседей.
Алгоритм K-NN проверяет новую запись данных, сравнивая ее со значениями, представленными в предоставленном наборе данных, состоящем из различных классов или категорий. Оценивая его близость или сходство с определенным диапазоном (K) соседних точек данных, алгоритм относит новые данные к классу или категории в наборе данных.
Ниже приведены шаги, которые необходимо выполнить для алгоритма KNN.
Шаг 1. Подготовьте набор данных с различными категориями или классами.
Шаг 2. Определите значение K.
K — это не что иное, как квадратный корень из общего количества записей в наборе данных. K не должно делиться на количество категорий, существующих в наборе данных, и K всегда должно быть нечетным.
Шаг 3. Определите данные запроса
Шаг 4. Рассчитайте расстояние между точкой запроса и каждым элементом набора данных и сохраните его в списке.
Шаг 5. Отсортируйте список
Шаг 6. Выберите из списка первые K элементов.
Шаг 7: Определяем режим категорий верхних K элементов, который и будет нашим ответом.
Давайте возьмем в качестве примера две группы точек, такие как красная группа и зеленая группа, у нас есть точка запроса, и нам нужно определить, к какой группе принадлежит эта группа.
Зеленая группа
[(2,3), (1,2), (1,4), (2,4), (1,3), (3,2), (3.5,1), (1,3.5), (0.5,1.5)]
Красная группа
[(6,3), (5,2), (4,4), (3.5,4.5), (5,4), (6,3), (5,3)]
Точка запроса
(3.5,3.5)
def myFunc(a):
return a[1]
a=[(2,3),(1,2),(1,4),(2,4),(1,3),(3,2),(3.5,1),(1,3.5),(0.5,1.5)]
b=[(6,3),(5,2),(4,4),(3.5,4.5),(5,4),(6,3),(5,3)]
n=int((len(a)+len(b))**0.5)
if n%2==0: n+=1
print("N for the following data sets is:",n)
c=(3.5,3.5)
print("Data Set (A):",a)
print("Data Set (B):",b)
print("Query Point (C):",c)
frequencyList=[]
for i in a: frequencyList.append(('A',((c[0]-i[0])**2+(c[1]-i[1])**2)**0.5))
for i in b: frequencyList.append(('B',((c[0]-i[0])**2+(c[1]-i[1])**2)**0.5))
frequencyList.sort(key=myFunc)
frequencyList=frequencyList[:n]
print(frequencyList)
ans=None
aa=0
bb=0
for i in frequencyList:
if i[0]=='A':aa+=1
if i[0]=='B':bb+=1
if aa>bb: ans='A'
else: ans='B'
print()
print(f"{c} belongs to {ans} group")
Мы ясно видим, что есть 5 ближайших точек, из которых 3 принадлежат красной (A) группе и 2 принадлежат зеленой (B) группе, таким образом, ответ A
