Резюме:В этой статье кратко представлена основная идея алгоритма ближайшего соседа и конкретная реализация Python, а также проанализированы его преимущества, недостатки и область применения, которая подходит для понимания и практики новичками.
Первокурсники идут в школу, и новости о том, что некоторые университеты назначают соседей по комнате на основе интересов, захватывают заголовки, что связано с применением алгоритмов машинного обучения. Кроме того, после поступления в колледж первокурсники могут присоединиться как минимум к нескольким студенческим организациям или обществам. Общества делятся на разные категории в соответствии с интересами студентов, так как же определить эти категории или различить разницу между различными организациями? Я уверен, что если бы вы спросили людей, которые управляют этими обществами, они бы не сказали, что их общества такие же, как и любые другие, но в какой-то степени похожи. Например, Ассоциация родного города и Ассоциация выпускников средней школы ведут одинаковый образ жизни; Футбольный клуб и Ассоциация бадминтона разделяют одинаковые интересы в спорте; Ассоциация инноваций в области науки и технологий и Клуб предпринимательства имеют схожие интересы. Может быть, позвольте вам измерить, что эти общества или организации делают или как они работают, и вы сможете определить, какие общества представляют для вас интерес. Но есть алгоритм, который может помочь вам принимать лучшие решения, и это алгоритм k-ближайших. Neighbours (NN), в этой статье студенческое сообщество будет использовать студенческое сообщество для объяснения некоторых концепций алгоритма k-NN, который, возможно, является самым простым алгоритмом машинного обучения, а построенная модель содержит только сохраненный набор обучающих данных. Алгоритм делает прогнозы о новых точках данных, находя ближайшую точку данных в обучающем наборе данных — его «ближайшего соседа».
Принцип работы
В своей простейшей версии алгоритм k-NN рассматривает только одного ближайшего соседа, который является ближайшей точкой обучающих данных для точки, которую мы хотим предсказать. Затем прогнозируемый результат является выходом для этой точки обучения. На следующем рисунке показана классификация построенного набора данных.
Как видно из графика, мы добавили три новые точки данных, обозначенные звездочками. Для каждой из трех точек мы пометили ближайшую точку в обучающем наборе, а прогнозируемый результат алгоритма ближайшего соседа — это помеченная точка (обозначенная крестиком).
Точно так же, вместо того, чтобы рассматривать только одного ближайшего соседа, мы также можем рассмотреть любое количество k соседей. Отсюда и название алгоритма k-NN. При рассмотрении нескольких соседей мы используем голосование для присвоения меток. Это означает, что для каждой контрольной точки мы подсчитываем, сколько соседей принадлежит классу 0 и сколько соседей принадлежит классу 1. Затем мы подсчитываем, какая категория этих соседей имеет большую долю, чтобы определить, к какой категории относится предсказанная точка: другими словами, меньшинство подчиняется большинству. В следующем примере используются 5 ближайших соседей:
Опять же, прогнозы представлены скрещенными цветами. Как видно из графика, прогноз для новой точки данных в верхнем левом углу не такой, как если бы мы использовали только одного ближайшего соседа.
Хотя на этом рисунке показана проблема только для бинарной классификации, этот метод можно применять к наборам данных с любым количеством классов. Для задач с множественной классификацией также вычислите, к каким классам принадлежат k соседей, выполните количественную статистику и выберите класс с наибольшим числом в качестве результата прогнозирования.
Scratch реализует алгоритм k-NN
Вот псевдокод алгоритма k-NN для классификации одной точки данных (назовем ее точкой A): Для каждой точки в наборе данных:
- Сначала вычислите расстояние между точкой А и текущей точкой;
- Затем отсортируйте расстояния в порядке возрастания;
- Далее ближайшая точка как k ближайших соседей A;
- После этого найти подавляющее большинство классов у этих соседей;
- Наконец, верните подавляющее большинство классов в качестве нашего прогноза для класса A;
Код реализации Python выглядит следующим образом:
def knnclassify(A, dataset, labels, k):
datasetSize = dataset.shape[0]
# 计算A点和当前点之间的距离
diffMat = tile(A, (datasetSize, 1)) - dataset
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# 按照增序对距离排序
sortedDistIndices = distances.argsort()
# 选出距离最小的k个点
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndices[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 对这些点所处的类别按照频次排序
sortedClassCount = sorted(classCount.iteritem(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
Давайте углубимся в код выше:
- Функция knnclassify принимает 4 входных параметра: входной вектор для классификации, называемый A, полная матрица обучающих примеров, называемая dataSet, вектор меток, называемый labels, и k — количество ближайших соседей, используемых при голосовании.
- Вычислите расстояние между A и текущей точкой, используя евклидово расстояние.
- Сортировать расстояния в увеличении порядка.
- Выберите K последних расстояний от него, чтобы проголосовать за класс A.
- После этого возьмите словарь classCount и разбейте его на список кортежей, затем отсортируйте кортежи по пункту 2 в кортеже. Поскольку порядок сортировки обратный, мы выбираем от большего к меньшему (устанавливаем обратный).
- Наконец, верните наиболее часто встречающуюся метку класса.
Scikit-Learn реализует алгоритм k-NN
Scikit-Learn — это набор инструментов для машинного обучения, который объединяет множество алгоритмов машинного обучения. Теперь давайте посмотрим, как реализовать алгоритм kNN с помощью Scikit-learn. код показывает, как показано ниже:
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
# 导入iris数据集
iris = datasets.load_iris()
X = iris.data
y = iris.target
# 将其按照一定的比例划分为训练集和测试集（random_state=0 保证每次运行分割得到一样的训练集和测试集）
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
# 设定邻居个数
clf = KNeighborsClassifier(n_neighbors=5)
# 拟合训练数据
clf.fit(X_train, y_train)
# 对测试集进行预测
predictions = clf.predict(X_test)
print("Test set predictions: {}".format(predictions))
# 评估模型性能
accuracy = clf.score(X_test, y_test)
print("Test set accuracy: {:.2f}".format(accuracy))
Давайте посмотрим на приведенный выше код:
- Во-первых, генерировать наборы данных IRIS;
- Затем разделите данные на обучение и тестовые наборы для оценки эффективности обобщения;
- После этого укажите количество соседей (k) равным 5;
- Затем используйте обучающий набор, чтобы соответствовать классификатору;
- Чтобы сделать прогнозы на тестовых данных, для каждой точки данных в тестовом наборе используйте этот метод, чтобы вычислить ближайших соседей в обучающем наборе и найти в нем наиболее часто встречающийся класс;
- Наконец, оцените способность модели к обобщению, вызвав функцию оценки с тестовыми данными и тестовыми метками;
После запуска модели точность тестового набора составляет 97 %, что означает, что модель правильно предсказывает класс для 97 % выборок в тестовом наборе данных;
плюсы и минусы
Как правило, классификаторы k-NN имеют два важных параметра: количество соседей и способ расчета расстояния между точками данных.
- На практике обычно хорошо работает небольшое количество из 3 или 5 соседей. Конечно, этот параметр следует регулировать в зависимости от конкретной ситуации;
- Выбор правильного метода измерения расстояния может быть трудным. Как правило, используется евклидово расстояние, и евклидово расстояние хорошо работает во многих случаях;
Одной из сильных сторон k-NN является то, что модель очень проста для понимания и часто обеспечивает достойную производительность без обширной настройки параметров. Использование этого алгоритма является хорошим базовым подходом перед рассмотрением более продвинутых методов. Создание модели k-NN обычно происходит быстрее, но когда обучающая выборка очень велика (количество признаков или количество выборок), время прогнозирования будет очень большим. Кроме того, предварительная обработка данных очень важна при использовании алгоритма k-NN. Этот метод обычно плохо работает с наборами данных со многими функциями (сотнями и более), и особенно плохо работает с наборами данных, где большинство функций в большинстве случаев равны 0 (так называемые разреженные наборы данных).
в заключении
Алгоритм k-NN — это простой и эффективный метод классификации данных.Это алгоритм машинного обучения, основанный на обучении экземпляров.Он должен выполнять алгоритм машинного обучения через экземпляры данных, и алгоритм должен нести полный набор данных. Для больших наборов данных требуется много места для хранения. Кроме того, также необходимо рассчитать расстояние между каждой точкой данных в базе данных и точкой прогноза, что является хлопотным и требует много времени. Еще одним недостатком является то, что алгоритм k-NN не дает вам представления о базовой структуре данных, о том, как именно выглядит «среднее» или «пример» каждого класса.
Поэтому, хотя алгоритм k-NN прост для понимания, он редко используется на практике из-за низкой скорости прогнозирования и неспособности решать многофункциональные задачи.
использованная литература
- Машинное обучение Питера Харрингтона (2012)
- Введение в машинное обучение с помощью Python, Сара Гвидо-Андреас Мюллер (2016 г.)
Выше приведен перевод сСообщество Alibaba Cloud YunqiОрганизация переводов.
Ссылка на перевод
Оригинальное название статьи «k-Ближайшие соседи: кто рядом с вами», переведенное Haitang, под редакцией Uncle_LLD.
В статье упрощенный перевод, более подробное содержание,Пожалуйста, просмотрите исходный текст.
Для получения более технических галантерейных товаров, пожалуйста, обратите внимание на номер организации Yunqi Community Zhihu:Сообщество Alibaba Cloud Yunqi
Эта статья является оригинальным контентом сообщества Yunqi и не может быть воспроизведена без разрешения.