Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность.
?Основные понятия
Алгоритм k-ближайших соседей (KNN) представляет собойОсновные методы классификации и регрессии
Алгоритм k-ближайших соседей, то есть, учитывая набор обучающих данных, для нового входного экземпляра находит k экземпляров, ближайших к экземпляру в наборе обучающих данных, и большинство из k экземпляров принадлежат определенному классу, и входной экземпляр Classify в этот класс (аналогично идее меньшинства, подчиняющегося большинству)
- Если k=3, 3 ближайшие точки зеленой точки — это 2 маленьких красных треугольника и 1 маленький синий квадрат,меньшинство подчиняется большинству, на основе статистического метода определяется, что классифицируемая зеленая точка относится к категории красного треугольника.
- Если k=5, 5 ближайших соседей зеленой точки — это 2 красных треугольника и 3 синих квадрата, илименьшинство подчиняется большинству, на основе статистических методов определяется, что классифицируемые зеленые точки относятся к классу синих квадратов.
Следовательно, как видно из приведенного выше примера, основная идея алгоритма k-ближайших соседей такова:Классифицируйте новую точку, пока вы найдете k ближайших к ней экземпляров, какая категория принадлежит к какой категории больше всего.
?Выбор значения k
?значение k слишком мало
Если значение k слишком мало, общая модель усложнится, и легко произойдет переоснащение.
Так называемая переобучение заключается в том, что уровень точности очень высок на тренировочном наборе, но уровень точности на тестовом наборе низок.
Предположим, у нас есть обучающие данные и точки, которые нужно классифицировать, как показано ниже:
На картинке выше есть два типа: одна — черная точка, другая — синий прямоугольник, а теперь мы собираемся классифицировать красный пятиугольник.
Когда k=1, легко увидеть, что пятиугольник находится ближе всего к черной точке, тогда по идее алгоритма k-ближайших соседей мы окончательно определяем, что классифицируемый пятиугольник принадлежит черной точке.
Если k слишком мало,Мы можем легко узнать шум? очень легко определить категорию шума, игнорируя при этом реальное распределение данных. На приведенном выше рисунке, если k больше, например, k=8, и включен синий прямоугольник, мы можем легко получить правильную классификацию, которая должна быть синим прямоугольником.
?Значение k слишком велико
Если значение k слишком велико, (разные) обучающие экземпляры, которые находятся далеко от входного экземпляра, также будут играть роль в прогнозировании, что приведет к ошибкам прогнозирования. Увеличение значения k означает, что общая модель становится проще.
Когда k=n (n — количество обучающих выборок), то независимо от входного экземпляра будет просто предсказано, что он принадлежит к классу с наибольшим количеством обучающих экземпляров. В этот момент модель становится очень простой,Это эквивалентно тому, что модель вообще не обучается.?, и напрямую возьмите обучающие данные для подсчета каждой категории данных, а затем найдите самую большую.
В приведенном выше примере есть черные точки 9 и синие прямоугольники 7. Если k = 16 (количество отсчетов = 9 + 7), то согласно идее алгоритма k ближайших соседей, вывод состоит в том, что красный пятиугольник принадлежит Черным точкам, явно неправильно ?
На данный момент модель слишком проста и полностью игнорирует множество полезной информации в экземпляре обучающих данных, что нежелательно.
Значение k не может быть ни слишком большим, ни слишком маленьким.Выбор нашего значения k,Этот диапазон лучше всего находится между границами красного круга на изображении ниже.,Как показано ниже
?Как вообще в многомерных функциях мы выбираем значение k?
Согласно книге доктора Ли Ханга, мы обычно выбираем меньшее значение и обычно применяем метод перекрестной проверки для выбора оптимального значения k.
Перекрестная проверка
Основная идея метода перекрестной проверки состоит в том, чтобы попробовать несколько возможных k один за другим, а затем выбрать k с лучшим эффектом.
Наиболее часто используемая перекрестная проверкаS-кратная перекрестная проверка, Методы, как показано ниже:
Сначала случайным образом разделите заданные данные на S непересекающихся подмножеств одинакового размера, затем используйте данные S-1 подмножеств для обучения модели, используйте оставшиеся подмножества для проверки модели и сравните этот процесс с возможным S. Эти выборки повторяются. , и, наконец, выбирается модель с наименьшей средней ошибкой теста в оценках S.
Другой распространенный подход — установить k равным квадратному корню из числа экземпляров обучающего набора.
♠ Мера расстояния
Как упоминалось выше, алгоритм k-ближайших соседей должен найти экземпляр в наборе обучающих данных сближайший соседСуществует k экземпляров , и большинство из этих k экземпляров принадлежат определенному классу, и мы говорим, к какому классу принадлежит точка предсказания.
Как измеряется ближайший сосед в определении ❓ Как узнать, кто находится ближе всего к контрольной точке. Здесь представлены несколько показателей расстояния.
У нас могут быть следующие меры:
В практических приложениях выбор функции расстояния должен определяться в соответствии с характеристиками данных и потребностями анализа.Ближайшие соседи, определяемые различными показателями расстояния, различны.Как правило, выбирается евклидово расстояние p=2.
♣ Нормализация функций
Первый пример выглядит следующим образом: я использую рост человека (см) и размер ноги (размер) в качестве значений признаков, а категория — мужская или женская. Имеется 5 обучающих выборок, распределение следующее:
A[(172,42),мужчина] B[(178,43),мужчина] C[(165,36),женщина] D[(177,42),мужчина] E[(160,35),женщина]
Легко видеть, что функция высоты первого измерения примерно в 4 раза больше, чем функция кода ноги второго измерения, тогда, когда выполняется измерение расстояния,Мы будем склоняться к признакам первого измерения.. Это приводит к тому, что две функции не являются одинаково важными, что в конечном итоге может привести к неправильным расчетам расстояния и, следовательно, к неверным прогнозам.
Например, теперь есть тестовая выборка F (167, 43), давайте предскажем, мужчина он или женщина, для предсказания возьмем k=3.
Затем мы используем евклидово расстояние для расчета евклидова расстояния между F и обучающей выборкой, а затем берем ближайшие три.Большинство категорий являются нашими окончательными результатами.Расчет выглядит следующим образом:
Из расчета можно получить, что самые последние первые три выборки - это C, D и E соответственно, затем C, E - женщины, D - мужчины, и женщин больше, чем мужчин. Результат нашего прогнозаженский.
Таким образом, возникает вопрос: вероятность того, что у женщины размер ноги 43, намного меньше, чем вероятность того, что у мужчины размер ноги 43, так почему же алгоритм все еще предсказывает, что F — женщина? Это связано с различными размерами признаков, что приводит к тому, что значение роста гораздо больше, чем значение размера стопы, что не является объективным. Итак, мы должны сделать каждую функцию одинаково важной!
Формула нормализации выглядит следующим образом:
? Правила принятия решения о классификации
Правилом принятия решения о классификации в методе k ближайших соседей часто является голосование по большинству, то есть класс входного экземпляра определяется классом большинства в обучающих экземплярах k ближайших соседей входного экземпляра.
Правила голосования по большинству объясняются следующим образом:
Если функция потерь для классификации представляет собой функцию потерь 0-1, функция классификации имеет вид:
Тогда вероятность неправильной классификации:
Другими словами, текущими типами кандидатов являются c1, c2, ....cj, какой из них я выбираю, может сделать наш эмпирический риск наименьшим (экспериментальный риск — это значение ошибки обучающих данных с точки зрения непрофессионала)
?Сводка
1️⃣ Метод k-ближайших соседей — это базовый и простой метод классификации и регрессии. Процесс метода k-ближайших соседей таков: если теперь у нас есть набор данных, когда дан новый экземпляр, самый простой и грубый метод - вычислить расстояние между ним и всеми точками, а затем найти k ближайших соседей, и, наконец, проголосовать большинством голосов.Правило определяет класс, к которому принадлежит данный экземпляр.
2️⃣ Модель k-ближайших соседей соответствует разделу пространства признаков на основе обучающего набора данных. В методе k-ближайших соседей, когда определяются обучающий набор, метрика расстояния, значение k и правило принятия решения о классификации, результат определяется однозначно.
3️⃣ Три элемента метода k-ближайших соседей: мера расстояния, выбор значения k и решающее правило классификации. Обычно используемыми метриками расстояния являются евклидово расстояние и более общее расстояние Lp. При малом значении k модель k ближайших соседей сложнее, при большом значении k модель k ближайших соседей проще. Выбор значения k отражает компромисс между ошибкой аппроксимации и ошибкой оценки, и оптимальное значение k обычно выбирается перекрестной проверкой. Обычно используемое правило принятия решения о классификации - это голосование большинством, что соответствует минимизации эмпирического риска.
? Примеры кода
Включая простой пример алгоритма knn, реализацию knn классификации радужной оболочки, построение дерева kd и поиск по дереву kd и т. д., все в ?git ee.com/new-month-pro…?
Использованная литература:Узнайте об алгоритме k-ближайших соседей (KNN) в одной статье -- Yi Zhen