Когда я должен выйти за пределы k ближайшего соседа

9

Для многих проектов машинного обучения мы начинаем с классификатора k Nearest Neighbor. Это идеальный начальный классификатор, поскольку у нас обычно достаточно времени для расчета всех расстояний, а количество параметров ограничено (k, метрика расстояния и весовые коэффициенты).

Однако это часто приводит к тому, что мы придерживаемся классификатора knn, поскольку в дальнейшем в проекте нет места для переключения на другой классификатор. Что было бы хорошей причиной, чтобы попробовать новый классификатор. Очевидными являются ограничения памяти и времени, но есть ли случаи, когда другой классификатор может реально повысить точность?


источник
Это чисто академическое или будет использоваться в промышленности?
Доктор Роб Ланг,
1
Большинство наших приложений развернуто в отрасли (поэтому проблемы с

Ответы:

3

k-NN обобщает в очень ограничительном смысле. Он просто использует гладкость априоров (или допущение непрерывности). Это предположение подразумевает, что шаблоны, близкие в пространстве признаков, скорее всего, принадлежат к одному и тому же классу. K-NN не может восстановить функциональную закономерность в распределении паттернов.

Таким образом, он требует репрезентативных обучающих выборок, которые могут быть чрезвычайно большими, особенно в случае пространств пространственных объектов с большими размерами. Хуже того, эти образцы могут быть недоступны. Следовательно, он не может выучить инварианты. Если шаблоны могут подвергаться некоторым преобразованиям без изменения их меток, а обучающая выборка не содержит шаблонов, преобразованных всеми допустимыми способами, k-NN никогда не распознает преобразованные шаблоны, которые не были представлены во время обучения. Это верно, например, для смещенных или повернутых изображений, если они не представлены в некоторой инвариантной форме перед запуском k-NN. k-NN не может даже абстрагироваться от несущественных особенностей.

Еще один несколько искусственный пример. Представьте, что паттерн, принадлежащий разным классам, периодически распределяется (например, в соответствии с синусом - если он меньше 0, то паттерны принадлежат одному классу, а он больше, чем паттерны принадлежат другому классу). Тренировочный набор конечен. Таким образом, он будет расположен в конечной области. За пределами этого региона ошибка распознавания будет 50%. Можно представить логистическую регрессию с периодическими базисными функциями, которые в этом случае будут работать намного лучше. Другие методы смогут изучить другие закономерности в распределении шаблонов и хорошо их экстраполировать.

Итак, если кто-то подозревает, что доступный набор данных не является репрезентативным, и должна быть достигнута инвариантность к некоторым преобразованиям шаблонов, то это тот случай, когда нужно выйти за пределы k-NN.


источник
Спасибо за ваш ответ (и спасибо BartoszKP за попытку улучшить его). Это правда, что knn не может найти шаблоны, которые требуют преобразования (если вы не начнете использовать странную (и неправильную) метрику расстояния). Это хорошая причина, чтобы попробовать другой классификатор, я думаю, тогда svm - очевидный выбор. Я не достаточно знаком с svm, чтобы сказать, но не требует ли он конкретных знаний о шаблоне, который вы ищете для определения ядра?
Да. Выбор ядра будет зависеть от паттернов. Ядро Гаусса будет иметь свойства, аналогичные методу k-NN. Другие стандартные ядра могут показаться неуместными. Однако, по крайней мере, можно попробовать их использовать.
Как следует из @ Necro0x0Der, любое улучшение по этим направлениям будет зависеть от закономерности (в примере с синусами, периодичности), которая является естественной для параметризации. То есть параметризация (выбор ядра) определяет структуру (фактически метрику) пространства представления. Если вы можете каким-то образом определить (возможно, с помощью догадок) некоторую подходящую структуру, то попробуйте параметризовать шаблон соответствующим образом. Обратите внимание, что, в конце концов, это позволяет вашему классификатору легко находить определенные типы соответствующих функций.
3

Если вы будете ограничены вычислительной сложностью, то деревья решений (Quinal, 1986) сложно превзойти (особенно, когда среда предлагает прямое преобразование модели DT в набор ifоператоров - например, Accord.NET ).

Для данных больших размеров понятие расстояния, на котором основан k-NN, становится бесполезным (Kriegel, Kröger, Zimek, 2009) (также: статья в Википедии ). Поэтому другие классификаторы, такие как SVM (Corter, Vapnik, 1995) или Random Forests (Breiman, 2001) , могут работать лучше.

Ссылки:

BartoszKP
источник
Конечно, большой размер не является фиксированным пределом, в большинстве случаев наши функции достаточно выразительны, чтобы работать на расстоянии. Конечно, это может быть важным моментом. Возможно, мне следовало уточнить с примером. Скажем, у нас есть классификатор с точностью 93%, это приемлемо, но теперь мы можем либо попытаться улучшить классификатор, либо найти новые функции. Все зависит от новых возможных функций и данных, но я искал рекомендации по этому решению.
@Rhand Мне кажется, что это решение на уровне управления проектом. Если текущее решение приемлемо, зачем возиться с ним? Это пустая трата времени. Если это не приемлемо, определите более точно, что вы хотите улучшить (скорость, точность и т. Д.).
BartoszKP
Дело не только в управлении проектами, вопрос в том, как добиться максимальной точности (это в моем вопросе) и в каком направлении выбрать лучшее. Вы предлагаете svm и случайный лес, потому что размерность может быть слишком высокой, это одна из возможностей, с которой я мог бы поэкспериментировать, чтобы увидеть, улучшается ли точность, и именно такой ответ я искал.
Ну, с другой стороны, это очень широкий вопрос. Нет общих правил, согласно которым классификатор X лучше, чем Y. Вам следует просто попробовать определенное количество классификаторов, а затем выполнить перекрестную проверку для выбора модели, например.
BartoszKP
3

КНН полезен для больших выборок данных

Однако его недостатки:

  1. Смещено по значению k.
  2. Сложность вычислений
  3. Ограничение памяти
  4. Быть обученным ленивым алгоритмом обучения
  5. Легко одурачить нерелевантными атрибутами.
  6. Точность прогноза может быстро ухудшиться при увеличении количества атрибутов.

Обычно это эффективно только в том случае, если данные об обучении велики, а обучение очень быстрое.

Iancovici
источник
Я не смотрю на кластеризацию, но на классификацию
@ Вот, пожалуйста, спасибо за заметку iliasfl
Iancovici