K-NN, машинное обучение, классификация
Популярным подходом машинного обучения для классификации и регрессии является метод K-ближайших соседей (KNN). Поиск k обучающих примеров, наиболее близких к конкретному тестовому примеру, и создание прогноза на основе их среднего целевого значения или класса большинства — вот как работает этот простой метод, основанный на экземплярах. На производительность алгоритма KNN может существенно повлиять выбор k и метрики расстояния, используемые для сравнения сходства экземпляров.
Как работает КНН
Расстояние между каждым обучающим примером и тестовым примером сначала определяется алгоритмом KNN. Производительность алгоритма зависит от метрики расстояния, используемой для сравнения сходства выборок. Метод KNN выбирает k обучающих примеров, которые наиболее похожи на тестовый пример после определения расстояний. Когда возникает проблема классификации, алгоритм определяет метку класса тестового примера путем суммирования меток классов его k ближайших соседей. Есть новая точка данных, которую мы хотим классифицировать, как вы можете видеть на изображении. Мы сравниваем рассчитанные расстояния между каждым из обучающих примеров и тестовым примером, а затем определяем класс на основе большинства k примеров. При решении проблемы регрессии алгоритм вычисляет целевое значение тестового примера путем усреднения целевых значений k ближайших соседей. Большее k приведет к более гладкой границе решения и уменьшит влияние выбросов, но также увеличит риск переобучения данных. Кроме того, ошибка поезда и ошибка теста приведут к плохому результату. Меньшее значение k приведет к выраженной границе решения и увеличит риск недообучения данных. Кроме того, ошибка поезда будет хорошей, а ошибка теста приведет к плохому состоянию.
Измерение расстояний в KNN
Производительность алгоритма KNN сильно зависит от используемой метрики расстояния. В KNN есть несколько наиболее популярных мер расстояния, которые можно использовать. Поэтому мы рассмотрим самые популярные меры расстояния.
Евклидово расстояние
Мерой расстояния, наиболее часто используемой в KNN, является евклидово расстояние. В многомерном пространстве он вычисляет кратчайшее расстояние по прямой линии между двумя примерами. Ниже приводится формула для евклидова расстояния между примерами p и q:
где:
- p_1 и p_2 - это набор первой точки данных,
- q_1 и q_2 — набор второй точки данных,
- d — расстояние между этими точками
Манхэттен Расстояние
Другой популярной метрикой расстояния в KNN является манхэттенское расстояние, обычно называемое расстоянием такси. Он вычисляет сумму абсолютных разностей размеров двух корпусов. Манхэттенское расстояние между двумя примерами p и q вычисляется следующим образом:
где:
- N - количество измерений,
- p_i — значение точки данных для i-го образца,
- q_i — значение точки данных для i-го образца,
- Σ обозначает сумму по всем наблюдениям,
- d — расстояние между этими точками.
Расстояние Минковского
Манхэттенское и евклидово расстояния обобщаются расстоянием Минковского. Ниже приводится формула для расстояния Минковского с параметром p между двумя примерами, p и q:
При p=2 расстояние Минковского эквивалентно евклидову расстоянию, а при p=1 оно эквивалентно манхэттенскому расстоянию.
Определившись со всей необходимой терминологией, можно переходить к реализации на языке программирования Python.
import numpy as np
from sortedcontainers import SortedList
from future.utils import iteritems
k = 3
def classify_new_points(test_points):
y = np.zeros(len(test_points))
for i, x in enumerate(test_points): # test points
mem = SortedList(load = k) # stores (distance, class) tuples
for j, xt in enumerate(training_points): #train points
diff = x - xt #calculating the distance
d = diff.dot(diff) #calculating the distance
if len(mem) < k: #checking if there are k points to compare if not just add
mem.add( (d, true_label[j]) )
else:
if d < mem[-1][0]: #checking the max added distance and compare with calculated
del mem[-1] #deleting the max number
mem.add( (d, true_label[j]) ) #add distance and class of data point
# getting the value of majority class
votes = {}
for _, v in sl:
votes[v] = votes.get(v,0) + 1
max_votes = 0
max_votes_class = -1
for v,count in iteritems(votes): #calculating the votes
if count > max_votes:
max_votes = count
max_votes_class = v
y[i] = max_votes_class
return y #return class
Другой способ реализации этого метода классификации — использовать библиотеку sklearn, что еще больше упрощает его реализацию.
from sklearn.neighbors import KNeighborsClassifier k = 3 neigh = KNeighborsClassifier(n_neighbors=k) neigh.fit(X, y) neigh.predict([[X]])
Более сложные модели K-NN будут рассмотрены в следующей статье. Такие модели, как KD Trees и Ball Trees, будут освещены (будут опубликованы).
Если вам понравилась статья, не забудьте подписаться на мои новые статьи.
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .
Заинтересованы в масштабировании запуска вашего программного обеспечения? Ознакомьтесь с разделом Схема.
