Я программирую алгоритм kNN и хотел бы знать следующее:
Тай-брейки:
- Что произойдет, если в голосовании большинства нет явного победителя? Например, все k ближайших соседей принадлежат к разным классам, или для k = 4 есть 2 соседа из класса A и 2 соседа из класса B?
- Что происходит, если невозможно точно определить k ближайших соседей, потому что есть больше соседей, которые имеют одинаковое расстояние? Например, для списка расстояний
(x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2)было бы невозможно определить k = 3 или k = 4 ближайших соседей, поскольку все 3-5-й соседи имеют одинаковое расстояние.
Вес:
- Я прочитал, что хорошо взвесить k-ближайших соседей, прежде чем выбирать класс победы. Как это работает? Т.е. как взвешиваются соседи и как определяется класс?
Варианты большинства голосов:
- Существуют ли другие правила / стратегии для определения победного класса, кроме большинства голосов?
k-nearest-neighbour
weights
ties
Флетчер Дюран
источник
источник
При выполнении kNN вам нужно помнить одну вещь, а именно, что это не строго математически производный алгоритм, а простой классификатор / регрессор, основанный на одной интуиции - основная функция не сильно меняется, когда аргументы не меняются много. Или, другими словами, основная функция локально почти постоянна. С этим допущением вы можете оценить значение базовой функции в любой заданной точке с помощью (возможно, взвешенного) среднего значения ближайших k точек.
Имея это в виду, вы можете понять, что нет четкого императива в отношении того, что делать, если в голосовании большинства нет явного победителя. Вы можете либо всегда использовать нечетное k, либо использовать некоторое инъективное взвешивание.
В случае, если соседи с 3 по 5 находятся на одинаковом расстоянии от интересующей вас точки, вы можете либо использовать только две, либо использовать все 5. Опять-таки, имейте в виду, что kNN - это не какой-то алгоритм, полученный из сложного математического анализа, а просто простая интуиция. Вам решать, как вы хотите справиться с этими особыми случаями.
Также в этом году была опубликована прекрасная статья Самори Кпотуфе и Абдеслама Булариаса о том, как NIPS касается правильного определения веса. Их общая интуиция заключается в том, что основная функция изменяется по-разному в разных направлениях (т. Е. Ее различные частные производные имеют разную величину), поэтому было бы целесообразно в некотором смысле изменить метрики / весовые коэффициенты в соответствии с этой интуицией. Они утверждают, что этот прием обычно улучшает производительность kNN и регрессии ядра, и я думаю, что у них даже есть некоторые теоретические результаты, подтверждающие это утверждение (хотя я не уверен, что на самом деле утверждают эти теоретические результаты, у меня не было времени на это через всю бумагу пока). Бумагу можно бесплатно загрузить с их сайтов или после поиска в Google «Градиентные веса помогают непараметрическим регрессорам».
Теперь вы, вероятно, захотите узнать, как вы можете найти правильные k, метрику, взвешивание, действие, которое нужно выполнить, когда есть розыгрыши и так далее. Печально то, что после некоторого глубокого размышления, в принципе, трудно найти правильные гиперпараметры, вам, вероятно, нужно будет протестировать разные группы гиперпараметров и посмотреть, какие из них хорошо работают на некотором наборе валидации. Если у вас есть некоторые вычислительные ресурсы, и вы хотите автоматически получить правильные параметры при хорошем наборе гиперпараметров, недавно появилась идея (которая мне очень нравится) использовать гауссовские процессы для оптимизации без производных в этой настройке.
Позвольте мне уточнить - нахождение набора гиперпараметров (т. Е. Минимизирующих ошибку в данных валидации) может рассматриваться как проблема оптимизации. К сожалению, в этой настройке мы не можем получить градиент функции, которую мы пытаемся оптимизировать (что мы обычно хотим сделать, выполнить градиентный спуск или некоторые более продвинутые методы). Гауссовские процессы могут использоваться в этой настройке для нахождения наборов гиперпараметров, которые имеют большие шансы, работать лучше, чем лучшие, которые мы нашли до настоящего момента. Следовательно, вы можете итеративно запустить алгоритм с некоторым набором гиперпараметров, а затем спросить гауссовский процесс, для каких из них лучше всего попробовать следующий, попробовать эти и так далее.
За подробностями обращайтесь к статье «Практическая байесовская оптимизация алгоритмов машинного обучения» Джаспера Снока, Хьюго Ларошелла и Райана П. Адамса (которую также можно найти на их веб-сайтах или в Google).
источник
Что касается этой части связи, лучшей базовой идеей для связей, как правило, является случайный разрыв, поэтому выбираем случайный класс из всех, выигравших голосование, и случайным образом выбираем подмножество связанных объектов, достаточно большое для заполнения k.
Такое решение подчеркивает тот факт, что это патологические случаи, которые просто не дают достаточно информации для принятия решения в режиме кНН. Кстати, если они являются общими для ваших данных, может быть, вы должны попробовать более дифференцирующее расстояние?
источник
Один из возможных способов - заставить алгоритм автоматически увеличивать или уменьшать k, пока вы не получите явного победителя.
источник