Метод k-ближайших соседей - метрический алгоритм для автоматической классификации объектов или регрессии.
В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди k соседей данного элемента, классы которых уже известны. В случае использования метода для регрессии, объекту присваивается среднее значение по k ближайшим к нему объектам, значения которых уже известны.
Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию расстояния.
Рис. 1 Определение класса красной точки при k = 5
При создании k-nn модели необходимо выбрать и настроить несколько параметров для обеспечения высокопроизводительной работы
Количество соседей
Увеличение k будет иметь тенденцию сглаживать границы классов и избегать переобучения, при этом существует риск неправильно определения объекта, лежащего на границах, что видно на Рис. 1. Не существует единственного значения k, которое подходило бы для каждого отдельного набора данных. Однако для моделей классификации, особенно если есть только два класса, для k обычно выбирается нечетное число. Это сделано для того, чтобы алгоритм никогда не сталкивался с ничьей: например, он смотрит на ближайшие четыре точки и обнаруживает, что две из них относятся к синей категории, а две - к красной.
Функция расстояния
Существуют разные способы измерить, насколько «близки» две точки друг к другу, и различия между этими методами могут стать значительными в более высоких измерениях. Чаще всего используется Евклидово расстояние, вычисляемое с помощью теоремы Пифагора. Другой способ — это Манхэттенское расстояние, согласно этой метрике, расстояние между двумя точками равно сумме модулей разностей их координат. В общем смысле, это формы расстояния Минковского, формула которого такова:
Где при p = 1 получаем Манхэттенское расстояние, при p = 2 - Евклидово.
Нормализация
Разные атрибуты могут иметь разный диапазон представленных значений в выборке (например атрибут А представлен в диапазоне от 0.1 до 0.5, а атрибут Б представлен в диапазоне от 1000 до 5000), то значения дистанции могут сильно зависеть от атрибутов с большими диапазонами. Поэтому данные обычно подлежат нормализации. Обычно используют два основных способа нормализации данных:
Минимакс, где все значения будут лежать в диапазоне от 0 до 1:
Z-нормализация, где s среднеквадратичное отклонение и диапазон равен (-3s,3s):
Пример работы
Результат работы алгоритма будет представлен на примере задачи предсказания выживания пассажиров на корабле Титаник.
Листинг 1. Программа предсказания выживания
def distance(a,b):
d = 0
d += abs(a['Pclass'] - b['Pclass']) * 10
d += (a['Sex'] != b['Sex']) * 80
d += abs(a['Age'] - b['Age'])
d += abs(a['SibSp'] - b['SibSp'])
d += abs(a['Parch'] - b['Parch'])
d += abs(a['Fare'] - b['Fare']) / 10
d += a['Embarked'] != b['Embarked']
return d
def myKNeighborsClassifier(learnData, K, passengerIndexForPrediction):
dists = np.zeros((learnData.shape[0] - 1, 2))
i = 0
for idx, row in learnData.iterrows():
if idx != passengerIndexForPrediction:
dists[i][0] = distance(learnData.loc[passengerIndexForPrediction,],row)
dists[i][1] = row['Survived']
i += 1
dists = sorted(dists, key = lambda pair: pair[0])
prediction = 0
for i in range(K):
prediction += dists[i][1]
prediction /= K
return round(prediction)
accuracy = 0
for idx, row in tqdm.tqdm(data.iterrows(), total=len(data)):
accuracy += row['Survived'] == myKNeighborsClassifier(data, 3, idx)
print(accuracy/data.shape[0])
Реализованная модель предсказывает выживание с точностью 82.7 %. В функции distance можно увидеть, что проведена нормализация к диапазону [0;100] при этом наиболее важные атрибуты, обеспечивающие разницу в классах, это пол и класс билета.
Вывод
Алгоритм k-ближайших соседей быстр и прост в реализации, также выбор параметров не занимает много времени и не требует никаких компьютерных вычислений. Минусом является то, что само прогнозирование протекает очень долго поскольку для того, чтобы предсказать результат для нового значения, ему потребуется пройтись по всем точкам в обучающем наборе, чтобы найти ближайшие. Поэтому для больших наборов данных алгоритм может быть относительно медленным по сравнению с другими.