Ближайший сосед Питона К.

Вступление:

Я хотел бы поблагодарить Онеля Харрисона за его объяснение о KNN, и следующее объяснение взято из его статьи, которую я бы рекомендовал вам прочитать, если вы хотите подробное объяснение KNN:

Алгоритм k-ближайших соседей (KNN) - это простой, легко реализуемый алгоритм контролируемого машинного обучения, который можно использовать для решения задач классификации и регрессии.

import numpy as np
import pygame
import sys
import time

WIDTH = 750
running = True
POINTS = 3000
NUMBER_OF_POINTS = 100
RED_RANGE = [[0,750],[0,450]]
GREEN_RANGE = [[0,450],[0,750]]
BLUE_RANGE = [[450,750],[0,750]]
STANDARD_DEVIATION_DIVISOR = 1
SPAM_NEW_GRIDS = True

WHITE = (255, 255, 255)
BLUE =     (0,0,128)
RED = (255,0,0)
GREEN = (0, 255, 0)
chars = {'R': RED,
         'G': GREEN,
         'B': BLUE}

pygame.init()
screen = pygame.display.set_mode((WIDTH, WIDTH))
screen.fill(WHITE)
pygame.display.set_caption("K's Nearest Neighbour")


def generate_starting_points(minimum, maximum, number_of_points):
    mean = (maximum + minimum) / 2
    standard_deviation = (maximum + minimum) / STANDARD_DEVIATION_DIVISOR
    points = np.array(np.random.normal(mean, standard_deviation, number_of_points))
    return points


def display_starting_grid(red, green, blue, points):
    redX = generate_starting_points(red[0][0], red[0][1], points)
    redY = generate_starting_points(red[1][0], red[1][1], points)
    red = np.stack((redX, redY), axis=-1)

    blueX = generate_starting_points(blue[0][0], blue[0][1], points)
    blueY = generate_starting_points(blue[1][0], blue[1][1], points)
    blue = np.stack((blueX, blueY), axis=-1)

    greenX = generate_starting_points(green[0][0], green[0][1], points)
    greenY = generate_starting_points(green[1][0], green[1][1], points)
    green = np.stack((greenX, greenY), axis=-1)
    return np.stack((red, green, blue))


def display(window, redArr, blueArr, greenArr):
    for point in redArr:
        pygame.draw.circle(window, RED, (point[0], point[1]), 1)
    for point in greenArr:
        pygame.draw.circle(window, GREEN, (point[0], point[1]), 1)
    for point in blueArr:
        pygame.draw.circle(window, BLUE, (point[0], point[1]), 1)


def connectLines(points, window, mouse):
    colors=np.array([ord(point[2]) for point in points])
    most_frequent_colour = chr(np.bincount(colors).argmax())
    for point in points:
        pygame.draw.line(window, chars.get(point[2]), mouse, point[1], 1)
    pygame.draw.circle(window, chars.get(most_frequent_colour), mouse_position, 8)


def KNN(mouse, points, window):
    #closest_points = [[sqrt(2*WIDTH**2),'NULL'] for _ in range(10)]
    closest_points = []
    for point in points[0]:
        distance = np.linalg.norm(mouse - point)
        value = np.array([distance, point, 'R'], dtype=object)
        closest_points.append(value)
    for point in points[1]:
        distance = np.linalg.norm(mouse - point)
        value = np.array([distance, point, 'G'], dtype=object)
        closest_points.append(value)
    for point in points[2]:
        distance = np.linalg.norm(mouse - point)
        value = np.array([distance, point, 'B'], dtype=object)
        closest_points.append(value)
    closest_points = sorted(closest_points, reverse=False, key= lambda x:x[0])[:NUMBER_OF_POINTS]
    connectLines(closest_points, window, mouse)


points = display_starting_grid(RED_RANGE, GREEN_RANGE, BLUE_RANGE, POINTS)
while running:
    start= time.time()
    screen.fill(WHITE)
    red, green, blue = points[0], points[1], points[2]
    display(screen, red, blue, green)
    mouse_position = np.array(pygame.mouse.get_pos())
    KNN(mouse_position, points, screen)
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
            pygame.quit()
            sys.exit()
    if SPAM_NEW_GRIDS:
        points = display_starting_grid(RED_RANGE, GREEN_RANGE, BLUE_RANGE, POINTS)
        print(time.time()- start)
    pygame.display.flip()

Алгоритм контролируемого машинного обучения (в отличие от алгоритма неконтролируемого машинного обучения) - это алгоритм, который полагается на помеченные входные данные для изучения функции, которая производит соответствующий вывод при получении новых немаркированных данных.

Алгоритмы машинного обучения с учителем используются для решения задач классификации или регрессии.

Проблема классификации имеет дискретное значение на выходе. Например, «любит ананас на пицце» и «не любит ананас на пицце» дискретны. Там нет никакого среднего. Вышеупомянутая аналогия с обучением ребенка распознавать свинью - еще один пример проблемы классификации.

Задача регрессии имеет действительное число (число с десятичной точкой) в качестве вывода. Например, мы могли бы использовать данные в таблице ниже, чтобы оценить чей-либо вес с учетом его роста.

Данные, используемые в регрессионном анализе, будут похожи на данные, показанные на изображении выше. У нас есть независимая переменная (или набор независимых переменных) и зависимая переменная (то, что мы пытаемся угадать с учетом наших независимых переменных). Например, мы могли бы сказать, что рост является независимой переменной, а вес - зависимой переменной.

Кроме того, каждая строка обычно называется примером, наблюдением или точкой данных, а каждый столбец (не включая метку / зависимую переменную) часто называется предиктором, измерением, независимой переменной или особенность.

Алгоритм неконтролируемого машинного обучения использует входные данные без каких-либо ярлыков - другими словами, учитель (ярлык) не сообщает ребенку (компьютеру), когда он прав или когда он сделал ошибку, чтобы он может самостоятельно исправить.

В отличие от обучения с учителем, которое пытается изучить функцию, которая позволит нам делать прогнозы на основе некоторых новых немаркированных данных, обучение без учителя пытается изучить базовую структуру данных, чтобы дать нам более глубокое понимание данных.

KNN:

Алгоритм KNN предполагает, что похожие вещи существуют в непосредственной близости. Другими словами, похожие вещи находятся рядом друг с другом. Поэтому в примере кода я использую встроенные функции np, чтобы попытаться получить код как можно быстрее.

Взгляните на код и прокомментируйте любые запросы, если они у вас есть!