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

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

Первый имеет только два возможных класса (или метки) для данных: 0 или 1, True или False и так далее. Это можно использовать, например, чтобы определить, является ли электронное письмо спамом или нет, определить, есть ли у пациента болезнь или нет, и т. д. Один из самых известных примеров — определение того, будет ли человек на борту «Титаника» я пережил затопление.

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

Сегодня мы поговорим о конкретном классификаторе: классификаторе K-ближайших соседей (KNN). Это также можно использовать для регрессии, но мы пока не собираемся туда. Его можно использовать как для бинарной классификации, так и для мультикласса.

Хорошо, но как эта работа?

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

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

И обобщенная формула манхэттенского расстояния задается как:

Где в обоих случаях p и q — это точки, расстояние между которыми мы хотим вычислить, а n — количество точек. Оба широко используются в области машинного обучения, наряду с расстоянием Минковского, которое объединяет оба (разница заключается только в используемом экспоненциальном значении: 2 в евклидовом, 1 в манхэттенском, но оно может быть больше, так как выбрано пользователем).

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

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

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

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

У нас есть свои наборы данных, но алгоритм не увидит разноцветные шарики и не сможет ничего определить, глядя только на нашу конечную цель: цвет. Итак, как компьютер будет обрабатывать эти данные? В сыром виде. Допустим, наш набор данных мяча состоит из четырех атрибутов и цели (в нашем случае — цвета). По алгоритму это примерно так:

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

Итак, вычисляем расстояние между первой строкой и той, где цель отсутствует:

  • Сначала суммируем все разности, возводя их в квадрат, по формуле:

(0–2)² + (5–7)² + (15–13)² + (20–15)² = 4 + 4 + 4 + 25 = 37

  • Затем вычисляем квадратный корень из результата:

√37 = 6,09 (округление в большую сторону).

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

К концу расчета расстояний у нас будет вектор с такими расстояниями:

[6.09, 40.36, 4.47, 68.43]

Теперь предположим, что мы хотим рассмотреть только трех соседей из четырех, которые у нас есть (K = 3). Мы сортируем этот вектор расстояния и берем три первых значения:

[4.47, 6.09, 40.36]

Теперь, глядя на классификацию каждого соседа, который мы решили рассмотреть в нашем анализе, мы имеем, соответственно:

[Y, Y, R]

Выбирая среди них самую популярную классификацию, получаем, что наши новые данные, скорее всего, желтый шар!

Конечно, это самый простой пример, который вы найдете, но он точно описывает, как работает классификатор KNN. Чтобы еще лучше понять, как это работает, давайте реализуем алгоритм шаг за шагом, используя Python. А не ___ ли нам?

Первое, что я сделал, это создал образец набора данных для тестирования нашего кода. Я решил создать для простоты, но вы можете использовать готовую базу данных. Для этого я использовал метод make_blobs из библиотеки sklearn.datasets.

# Generating a sample of data to test the algorithms
X, y = make_blobs(n_samples = 500, 
                  n_features = 2, 
                  centers = 4,
                  cluster_std = 1.5, 
                  random_state = 4)

Этот набор данных имеет только два атрибута (для облегчения кодирования) и четыре разных класса. Это выборка числовых данных. Распределение данных можно увидеть ниже:

Затем мы собираемся разделить наш набор данных на наборы для обучения и тестирования в пропорции 70–30.

# Splitting the dataset into train and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.3)

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

Сначала евклидово расстояние:

# Defining the function to cauculate the Euclidean Distance
def euclidean_distance(train_attr1, train_attr2, test_attr1, test_attr2):
    distance = ((train_attr1 - test_attr1)**2 + (train_attr2 - test_attr2)**2)**0.5
    return distance

Тогда Манхэттенское расстояние:

# Defining the function to cauculate the Euclidean Distance
def manhattan_distance(train_attr1, train_attr2, test_attr1, test_attr2):
    distance = abs(train_attr1 - test_attr1) + abs(train_attr2 - test_attr2)
    return distance

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

# Calculate the chosen metric for distance
if distance_type == 'M' or distance_type == 'm':
    distance = manhattan_distance(X_train[j][k], X_train[j][k+1], X_test[i][k], X_test[i][k+1])
    distances.append(distance)
else:
     distance = euclidean_distance(X_train[j][k], X_train[j][k+1], X_test[i][k], X_test[i][k+1])
     distances.append(distance)

После этого мы создадим список с каждым расстоянием до каждой точки в нашем наборе поездов и соответствующим классом:

# Get the distances with the classification of the train set, to verify the right classification for the data
for l in range(0, len(distances)):
    neighboors.append([distances[l], y_train[l]])

Затем мы собираемся отсортировать список расстояний и классов (на основе расстояния, конечно) и взять первые значения «К», проверив среди них самый популярный класс (обратите внимание, что значение «К» выбрано пользователем):

# Sort the distances to get the first k ones
neighboors.sort(key = lambda x: x[0])

# Verify, among the first k distances, which classification is the most popular
classification = mode(neighboors[:k_neighboors][1])

И, наконец, мы собираемся хранить классификацию в виде списка:

# Get this classification into the predictions list
y_pred.append(classification)

Этот процесс выполняется для каждой строки в нашем тестовом наборе, сравнивая их с каждой строкой в ​​нашем наборе Train. Поэтому весь этот код вставляется в какие-то циклы.

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

# Fuction to calculate the score of the algorithm, its success rate
def hits_matches(y_pred, y_test):
    hits = 0
    for i in range(0,len(y_pred)):
        if y_pred[i] == y_test[i]:
            hits = hits + 1
            
    match = hits/len(y_pred)
    return match

С оценкой модели вы можете сравнить полученные результаты с выходными данными встроенного алгоритма классификатора KNN, представленного в библиотеке Scikit-Learn.

Некоторые заключительные соображения:

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

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

Вы можете проверить полный проект на моей странице Github: KNN — Реализация Python.

Ну вот и все на сегодня! Дайте мне знать, если я помог вам. Пока!