В этой статье я привел основные сведения о методе классификации k-ближайших соседей. Рассказываю все в своем стиле. Теоретические моменты и простая реализация.

Содержание: что это за метод, идея этого метода, как классифицировать (регрессировать) новые объекты, масштабирование признаков, как его можно применять, реализация.

Введение

Рассмотрим классификацию с помощью KNN. KNN относится к алгоритмам обучения с учителем, который можно использовать для решения задач классификации и регрессии. Он классифицирует данные или предсказывает их принадлежность к классам на основе близости к другим объектам в исходном наборе данных.

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

Если рассматриваемый объект находится рядом с другими объектами определенного класса, то рассматриваемому объекту присваивается этот класс. Этот метод классификации является основой для метода кластеризации К-средних.

Классификация — это разделение данных на классы на основе размеченных данных (с учителем). Сначала учитель как бы говорит, к какому классу относятся различные объекты, а потом ученик должен сказать, к какому классу относятся новые объекты, которые учитель не показывал. Нужно сказать ученику, на основе скольких близко похожих объектов нужно классифицировать новый объект (на основе k близко похожих).

Формулировка задачи

Пусть есть некоторый набор данных, состоящий из n наблюдений (объектов), i=1,...,n, m — число признаков, для каждого из которых задан класс , k=1,...,p, p — число классов, к которому относится этот объект. На основе этих данных можно сформировать исходный набор пар, на основе которого можно произвести классификацию новых объектов, которых нет в исходном наборе.

Идея алгоритма KNN. Первым шагом является выбор количества ближайших соседей k, которые будут использоваться для определения того, к какой категории отнести рассматриваемую точку данных.

Затем вычисляется расстояние, чаще всего евклидово расстояние, между новой точкой данных и всеми точками в обучающем наборе данных.

Берутся k ближайших точек (соседей) к данной точке по вычисленному расстоянию.

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

Классификация новых объектов

Сначала нужно подготовить данные, привести их в удобный для работы вид. Нужно сделать набор данных, на основе которого будут производиться расчеты с новыми точками данных. По факту эта модель не нуждается в обучении, она просто работает на основе исходного набора данных.

Выбираются k ближайших объектов (соседей) из исходной выборки, где k — параметр, задаваемый заранее. Модель просто запоминает векторы признаков наблюдений и их соответствующие метки классов. Модели подается новый, не классифицированный объект, она вычисляет расстояние между этим объектом и всеми объектами в обучающей выборке. Класс нового объекта определяется как класс, который наиболее часто встречается среди этих k ближайших точек (объектов). Нужно просто посчитать наибольшее число одинаковых классов.

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

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

Евклидово расстояние между двумя точками вычисляется по этой формуле:

d — функция расстояния (distance), a и b — точки данных (объекты, векторы признаков), и - элементы векторов (признаки), m — количество признаков в векторе (количество координат).

На рисунке изображена плоскость с набором точек, в центре круга — новая точка, для которой необходимо определить класс. Нужно посчитать расстояние до всех других точек и выбрать k точек, которые находятся ближе всего. Если k = 2, то будут выбраны точки с номерами 1 и 2, если k = 3, то будут выбраны точки с номерами 1, 2 и 3, и так далее. Для определения класса нужно посчитать количество точек для каждого класса из выбранных точек, наибольшее число классов будет являться ответом модели. Если число классов одинаковое, то нужно увеличить или уменьшить число k, а лучше оценить класс новой точки на разном числе k, например для k = 3, 5, 7 или другие значения.

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

Также есть взвешенный способ, он учитывает не только количество соседей, но и их удаленность от нового значения. Это может улучшить точность прогнозов, особенно в случаях, когда ближайшие соседи не равнозначны. В прогнозе участвует значение расстояний до точек. Это может быть, например, вычисление суммы расстояний до каждой точки каждого класса или умножение числа точек каждого класса на сумму расстояний.

Применение KNN

KNN тесно связан с концепциями близости и сходства, которые также важны в кластеризации. Его широкое применение в различных задачах машинного обучения делает его мощным инструментом в арсенале специалистов по машинному обучению. Понимание KNN служит основой для понимания метода кластеризации K-means.

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

KNN может применяться в онлайн-обучении, когда данные поступают динамическим потоком и быстро устаревают. Однако для этого могут быть необходимы специальные подходы для ускорения вычислений.

Для увеличения производительности, особенно при работе с большими объемами данных, можно использовать более продвинутые методы, такие как бинарные деревья (BallTree, KDTree), которые позволяют ускорить поиск ближайших соседей.

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

Недостатком является высокая вычислительная сложность при больших объемах данных и чувствительность к выбору метрики расстояния и параметра k — количества ближайших точек.

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

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

Подготовка данных

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

Различные характеристики объектов могут обладать разным диапазоном значений. Если величина одного признака будет маленькой, например, от 0.01 до 0.05, а величина другого признака будет от 10 до 50, то это будет сильно влиять на величину расстояния между векторами признаков — признаки с большими диапазонами значений будут сильно влиять на оценку расстояния.

Минимакс-масштабирование — преобразование данных в диапазоне от 0 до 1, минимальное и максимальное масштабируемые значения соответствуют 0 и 1:

— список всех j-х признаков по всем объектам, j=1,…,m, m — число признаков, min и max — минимальное и максимальное значение j-го признака по всем объектам в наборе данных, — j-й признак i-го объекта.

Z-масштабирование — масштабирование на основе среднего значения и стандартного отклонения (см. линейная регрессия).

Создание набора данных

Делаем искусственный набор данных и копируем получившиеся точки в другой файл.

from random import randint
from matplotlib import pyplot as plt

def class_point_data_points(n_samples, class_point, noise=1):
    def offset_point():
        offset_x = randint(-100 * noise, noise * 100) / 100
        offset_y = randint(-100 * noise, noise * 100) / 100
        x = class_point[0] + offset_x
        y = class_point[1] + offset_y
        return x, y

    points = [offset_point() for _ in range(n_samples)]
    x_list = [points[i][0] for i in range(n_samples)]
    y_list = [points[i][1] for i in range(n_samples)]

    return x_list, y_list


x1_list, y1_list = class_point_data_points(n_samples=10, class_point=(1, 1), noise=0.9)
x2_list, y2_list = class_point_data_points(n_samples=7, class_point=(4, 2.5), noise=2.5)

print(x1_list, y1_list)
print(x2_list, y2_list)

plt.scatter(x=x1_list, y=y1_list, color='red')
plt.scatter(x=x2_list, y=y2_list, color='green')
plt.show()

Простая реализация

Делаем набор данных, каждый элемент состоит из трех элементов: координата 1, координата 2 и метка класса.

x1 = [1.34, 1.16, 1.54, 0.46, 1.8, 1.86, 0.7, 0.52, 1.24, 1.32]
y1 = [1.8, 1.33, 1.37, 1.71, 0.68, 0.29, 1.3, 0.25, 1.07, 0.25]
x2 = [5.0, 5.88, 3.69, 2.61, 4.66, 2.09, 4.82]
y2 = [0.14, 0.61, 4.37, 1.74, 3.3, 2.98, 4.25]

points_class1 = [(x1[i], y1[i], 'c1') for i in range(len(x1))]
points_class2 = [(x2[i], y2[i], 'c2') for i in range(len(x2))]

features_num = 2

labels = ['c1', 'c2']

Указываем для каждой точки ее принадлежность к определенному классу «c1» или «c2» и создаем список всех меток классов.

Делаем функцию для вычисления евклидова расстояния до каждой точки от рассматриваемой новой.

def euclidian_dinstance(points, new_point):
    distances = []

    for point in points:
        point_distance = 0

        for i in range(features_num):
            point_distance += (new_point[i] - point[i]) ** 2

        distances.append((point_distance, point[2]))  # расстояние до точки и ее класс

    return distances

Эта функция возвращает список расстояний до всех точек и метки их классов. Метку класса нужно запоминать для того, чтобы потом ее использовать для идентификации класса у этих расстояний.

Далее делаем функцию для нахождения минимального расстояния в списке расстояний.

def get_min_item(distances):  # найти минимальный элемент
    min_dist, min_item_idx, min_item_label = 1000000, 0, 'c1'

    for idx, dist in enumerate(distances):
        if dist[0] < min_dist:
            min_dist = dist[0]
            min_item_label = dist[1]
            min_item_idx = idx

    return min_item_idx, min_item_label

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

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

def knn(points, new_point, k):
    distances, min_labels = euclidian_dinstance(points, new_point), []

    for _ in range(k):
        min_item_idx, min_item_label = get_min_item(distances)
        distances.pop(min_item_idx)  # убрать из списка минимальное значение
        min_labels.append(min_item_label)

    label_score = {label: 0 for label in labels}

    for label in min_labels:
        label_score[label] += 1

    max_score, max_label = 0, 'c1'

    for label, score in label_score.items():
        if score > max_score:
            max_score = score
            max_label = label

    return max_label

Сначала вычисляем расстояния до всех точек. Потом узнаем метки классов до k ближайших точек, записываем метки класса k ближайших точек в список min_labels. Делаем словарь label_score и считаем количество каждой метки. Потом вычисляем метку с максимальным значением меток класса и возвращаем из функции рассчитанную метку класса.

Теперь определяем метку класса для новой точки.

print(knn(points=points_class1+points_class2, new_point=(4, 2), k=3))  # c2

Улучшение кода

Сделаем класс для модели KNN и сделаем написанный алгоритм более удобным в использовании. В методе init делаем копию набора данных.

class KNN:
    def __init__(self, points, labels):
        self.points, self.labels = points[:], labels[:]

Внутри класса делаем метод для вычисления расстояния до каждой точки. Нижнее подчеркивание в начале названия метода означает, что этот метод является приватным, то есть его не нужно использовать извне.

def _euclidean_dinstance_(self, new_point):
    distances = []
    
    for point in self.points:
        point_distance = 0
    
        for i in range(2):
            point_distance += (new_point[i] - point[i]) ** 2
    
        distances.append(point_distance)
    
    return distances

Далее делаем метод для вычисления индекса минимального элемента.

def _get_min_item_idx_(self, distances):  # найти индекс минимального элемента
    min_dist, min_item_idx = 1000000, 0
    
    for idx, dist in enumerate(distances):
        if dist < min_dist:
            min_dist = dist
            min_item_idx = idx
    
    return min_item_idx

И основной метод для классификации новой точки.

def predict(self, new_point, k):
    distances = self._euclidean_dinstance_(new_point)
    labels = self.labels[:]  # скорировать список меток
    label_score = {label: 0 for label in labels}
    
    for _ in range(k):
        min_item_idx = self._get_min_item_idx_(distances)
        distances.pop(min_item_idx)
        label = labels.pop(min_item_idx)
        label_score[label] += 1
    
    max_score, max_label = 0, 'c1'
    
    for label, score in label_score.items():
        if score > max_score:
            max_score = score
            max_label = label
    
    return max_label

На вход передается новая точка и количество ближайших соседей. Вычисляется расстояние до всех точек в исходном наборе данных, делается копия списка меток и словарь для подсчета числа точек каждого класса поблизости. Вычисляем индекс минимального расстояния, удаляем элемент с этим индексом из списков меток и расстояний, получаем значение метки и увеличиваем число для данной метки. Затем просто вычисляем метку с максимальным числом.

Далее немного изменяем подготовку данных и смотрим что получилось.

points = [(x1[i], y1[i]) for i in range(len(x1))]
points += [(x2[i], y2[i]) for i in range(len(x2))]
labels = ['c1' for i in range(len(x1))]
labels += ['c2' for i in range(len(x2))]

knn = KNN(points, labels)
print(knn.predict(new_point=(4, 2), k=10))
print(knn.predict(new_point=(0.6, 0.5), k=10))

output:
c1
c2

Модель работает для обоих классов.

Задачи для самостоятельного решения

• Разобраться, как решать задачу регрессии на основе метода KNN;

• Попробовать разные метрики расстояния и разное число k;

• Сделать набор данных для большего числа признаков и сделать модель для этих данных.

Заключение

Мы рассмотрели что представляет собой метод KNN и как его можно применять. Сделали модель KNN с нуля и убедились, что все работает верно, так, как было описано в теоретической части. Сначала мы сделали искусственный набор данных, подготовили его для работы с ним. Потом мы сделали пробную реализацию модели KNN, она получилась не очень удобной для использования. Затем мы сделали более удобную версию кода для использования и улучшили код, написанный ранее. В результате получилось так, что все работает как было задумано.

Ссылка на папку с кодом из этой статьи на ГитХабе.