Цель
В этой главе мы поймем принципы алгоритма k ближайших соседей (kNN).
теория
kNN — один из самых простых алгоритмов классификации, доступных для обучения с учителем. Идея состоит в том, чтобы искать в пространстве признаков ближайших соседей тестовых данных. Мы изучим его с изображением ниже.
На изображении две семьи, синие квадраты и красные треугольники. мы звоним каждомусвоего рода. Их дома отображаются на карте города, которую мы называем пространственным пространством.(Вы можете думать о пространстве признаков как о пространстве, на которое проецируются все данные. Например, рассмотрим двумерное координатное пространство. Каждые данные имеют две функции, координаты x и y. Вы можете представить эти данные в двумерном координатном пространстве, справа "Теперь предположим, что если у вас есть три функции, вам нужно трехмерное пространство; теперь рассмотрим N функций, вам нужно N-мерное пространство, верно? Это N-мерное пространство является его пространством функций. В нашем изображении вы можете думать о нем как о двухмерном случае. имеет две функции).
Новый участник теперь входит в город и создает новый дом, показанный зеленым кругом. Его следует добавить в одну из этих сине-красных семей. Мы называем этот процессКлассификация. Что мы делаем? Поскольку мы имеем дело с kNN, применим этот алгоритм.
Один из способов — проверить, кто его ближайший сосед. Из изображения видно, что это семейство красных треугольников. Поэтому он также добавлен в красный треугольник. Этот метод называется «ближайший сосед”, так как классификация зависит только от ближайших соседей.
Но это проблематично. Красный треугольник может быть ближайшим. Но что делать, если рядом много синих квадратиков? Тогда синие квадраты имеют больший вес в регионе, чем красные треугольники. Так что просто проверить ближайший недостаточно. Вместо этого мы исследуем некоторые семейства k-ближайших соседей. Тогда, независимо от того, у кого будет большинство, новая выборка принадлежит этой семье. На нашем изображении возьмем k=3, 3 ближайших семейства. У него два красных и один синий (есть два равноудаленных синих, но поскольку k = 3, мы берем только один из них), поэтому он снова должен присоединиться к красному семейству. Но что, если мы возьмем k=7? Затем у него 5 синих семей и 2 красных семьи. Очень хороший! ! Теперь он должен присоединиться к синему клану. Таким образом, все они меняются в зависимости от значения k. Более интересно, что, если k=4? У него 2 красных соседа и 2 синих соседа. Это гладко! Так что лучше сделать k нечетным числом. Поскольку классификация зависит от k ближайших соседей, метод называетсяk-ближайшие соседи.
Кроме того, в kNN мы рассматриваем k соседей, но придаем всем равный вес, верно? Это справедливо? Например, возьмем случай k=4 в качестве примера. Мы говорим, что ничья. Обратите внимание, однако, что два красных цвета ближе к нему, чем два других синих. Поэтому он больше должен быть добавлен к красному. Так как же мы объясним это математически? Мы придаем каждой семье некоторый вес в зависимости от их расстояния от новичка. У тех, кто рядом с ним, вес увеличивается, а у тех, кто дальше от него, вес уменьшается. Затем мы добавляем общий вес каждой семьи отдельно. Тот, кто наберет наибольший общий вес, новый образец принадлежит к этому семейству. это называетсяmodified kNN.
Итак, какие важные вещи вы видите здесь?
- Вам нужна информация обо всех домах в городе, верно? Потому что нам нужно проверить расстояние новой выборки до всех существующих домов, чтобы найти ближайших соседей. Если домов и хозяйств много, памяти требуется много, и времени на расчеты требуется больше.
- Времени на какое-либо обучение или подготовку практически не остается.
Теперь давайте посмотрим на это в OpenCV.
kNN в OpenCV
Как и выше, мы сделаем здесь простой пример с двумя семействами (классами). Затем в следующей главе мы сделаем лучший пример.
Итак, здесь мы помечаем красную серию какClass-0(отсюда обозначено 0), обозначая синюю серию какClass-1(обозначено цифрой 1). Мы создаем 25 семейств или 25 обучающих данных и помечаем их как класс 0 или класс 1. Все это мы делаем с помощью генератора случайных чисел в Numpy.
Затем мы построим его с помощью Matplotlib. Красные серии показаны в виде красных треугольников, а синие серии показаны в виде синих квадратов.
import cv2 as cv
import numpy as np
import matplotlib.pyplot as plt
# 包含(x,y)值的25个已知/训练数据的特征集
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
# 用数字0和1分别标记红色或蓝色
responses = np.random.randint(0,2,(25,1)).astype(np.float32)
# 取红色族并绘图
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')
# 取蓝色族并绘图
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
plt.show()
Вы получите что-то похожее на наше первое изображение. Поскольку вы используете генератор случайных чисел, при каждом запуске кода вы будете получать разные данные.
Затем запустите алгоритм kNN и передайте trainData и ответы для обучения kNN (он строит дерево поиска).
Затем мы внесем новый образец в семейство и классифицируем его с помощью kNN в OpenCV. Прежде чем приступить к kNN, нам нужно иметь представление о тестовых данных (новых выборочных данных). Наши данные должны быть массивом чисел с плавающей запятой размером $number\ of\ testdata\times number\ of\ features$. Затем мы находим только что добавленного ближайшего соседа. Мы можем указать, сколько соседей мы хотим. он возвращает:
- Ярлыки, данные новым образцам, зависят от теории kNN, которую мы видели ранее. Если вы хотите использовать алгоритм «ближайшего соседа», просто укажите k=1, где k — количество соседей.
- k-метки ближайших соседей.
- Измерьте соответствующее расстояние нового дополнения до каждого ближайшего соседа.
Итак, давайте посмотрим, как это работает. Новые образцы отмечены зеленым цветом.
newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
knn = cv.ml.KNearest_create()
knn.train(trainData, cv.ml.ROW_SAMPLE, responses)
ret, results, neighbours ,dist = knn.findNearest(newcomer, 3)
print( "result: {}\n".format(results) )
print( "neighbours: {}\n".format(neighbours) )
print( "distance: {}\n".format(dist) )
plt.show()
Я получил следующий результат:
result: [[ 1.]]
neighbours: [[ 1. 1. 1.]]
distance: [[ 53. 58. 61.]]
В нем говорится, что у нашего нового образца есть 3 ближайших соседа, все из семейства Блю. Поэтому он помечен как голубая семья. Это видно из рисунка ниже:
Если у вас много данных, вы можете передать их в виде массива. Соответствующие результаты также получаются в виде массива.
# 10个新加入样本
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
ret, results,neighbours,dist = knn.findNearest(newcomer, 3)
# 结果包含10个标签
Дополнительные ресурсы
- Примечания NPTEL по распознаванию образов, глава 11
Упражнение
Сводная станция блога о технологиях искусственного интеллекта Panchuang:docs.panchuang.net
Официальная китайская учебная станция PyTorch:pytorch.panchuang.net
Официальная китайская документация OpenCV:woshicver.com