Почему увеличение k уменьшает дисперсию kNN?

Мысли и теория

Почему увеличение k уменьшает дисперсию kNN?

Интуиция, доказательство и эмпирические результаты

Вместо того, чтобы писать общую статью о том, как работает kNN, я хотел четко объяснить, почему увеличение k уменьшает дисперсию. Это потому, что я сам изо всех сил пытался найти убедительные ответы в Интернете, и я видел, как многие люди задают этот вопрос. Хотя это знание далеко не обязательно для использования модели, я считаю, что фундаментальное понимание того, как модели ведут себя по отношению к различным данным, имеет решающее значение для интерпретации их результатов. Я надеюсь, что эта статья донесет это сообщение до вас и, самое главное, взбудоражит вас и побудит применить этот стиль мышления к другим проблемам!

Краткое освежение знаний о kNN и нотации

kNN — это алгоритм классификации (можно использовать и для регрессии! Подробнее об этом позже), который учится предсказывать принадлежность данной точки x_test к классу C, просматривая ее k ближайшие соседи (т.е. ближайшие к нему точки). Точка классифицируется как класс, наиболее часто встречающийся в множестве ближайших соседей. Интуитивно это представлено на рисунке ниже:

Чтобы быстро уточнить, в случае бинарного классификатора (то есть, когда у нас есть только 2 класса для прогнозирования), k должно быть нечетным, чтобы избежать неопределенных точек. Как показано в последнем примере выше с k = 4, вы можете оказаться в ситуации с равным количеством классов, и, таким образом, вы не сможете классифицировать свою точку. Конечно, есть способы решить эту проблему. Простое решение — просто случайным образом выбрать один из двух классов. В многоклассовом классификаторе k может быть только 1, если вы хотите получить определенный результат для каждой контрольной точки, как показано ниже:

Алгоритм kNN может быть формально записан как:

Где:

kNN — это непараметрическая модель, что означает отсутствие какого-либо «обучения». Это означает, что нет параметров, которые нужно найти с помощью задачи оптимизации. Мы указываем только гиперпараметр k, который определяет, как ведет себя наша модель.

Если что-то из этого вам незнакомо, я настоятельно рекомендую вам обновить свои знания о kNN. В Интернете есть много хороших статей, объясняющих, как работает алгоритм. Статья Онела Харрисона достаточно популярна и легкодоступна. Если вас интересует что-то более глубокое, то я бы посоветовал статью Кевина Закки.

Краткий обзор ошибок: систематическая ошибка, дисперсия и коэффициент Байеса.

Любая данная модель машинного обучения будет иметь следующие 3 ошибки.

Смещение: это ошибка, которую мы допускаем из-за предположений нашей модели.

Мы получаем эту ошибку, потому что мы делаем предположения в наших моделях, чтобы упростить анализ, и, таким образом, мы можем упустить фактическую основную тенденцию в данных. Лучше всего это показано на рисунке ниже:

Как правило, увеличение сложности модели уменьшает этот тип ошибки. Это связано с тем, что более простые модели игнорируют тренд, если тренд более сложный.

Дисперсия: это ошибка, которую мы допускаем из-за того, что наши прогнозы различаются в разных наборах данных.

Причина, по которой у нас есть эта ошибка, заключается в том, что наши данные никогда не отражают реальную популяцию. В результате, в зависимости от типа данных обучения/тестирования, которые мы получаем, наши прогнозы будут различаться. Я понимаю эту ошибку следующим образом: в какой степени мы изучаем шум в наших обучающих данных? то есть насколько мы запоминаем данные?

Как правило, увеличение сложности модели увеличивает этот тип ошибки, поскольку более сложные модели лучше запоминают локальные особенности/шумы.

Непреодолимый уровень ошибок. Это ошибка, присущая фактическим данным, которые у вас есть. Его нельзя уменьшить без изменения ваших данных.

Этот тип ошибки обычно возникает из-за внутреннего шума в нашем наборе данных, т. е. присущей случайности. Лучше всего это показано на графике ниже:

Если вы все еще запутались, получите монету. Мы знаем, что вероятность выпадения орла равна 0,5. Однако попробуйте бросить монету 4 раза и повторить этот эксперимент 4 раза. Всегда ли вы будете получать две решки (T) и две решки (H), как вы ожидаете?

Я просто сделал это и получил:

Эксперимент 1: TTHT
Эксперимент 2: THHT
Эксперимент 3: TTHH
Эксперимент 4: TTHT

Это не потому, что монета предвзята, а скорее из-за того, что подбрасыванию монеты присуща случайность. Вероятность выпадения орла сходится к 0,5 только тогда, когда количество наших подбрасываний монеты приближается к бесконечности. То же самое относится и к любым данным обучения, которые у нас есть.

В классификации у нас есть способ оценки минимальной ошибки для любой задачи классификации (аналог неустранимой ошибки). Это коэффициент байесовской ошибки.

Коэффициент байесовских ошибок:наименьшая возможная ошибка для любого классификатора случайного результата.

Его дают:

Сумма этих ошибок дает общую частоту ошибок модели.

Интуиция: почему увеличение k уменьшает дисперсию модели, но увеличивает смещение модели?

Чтобы показать это, давайте рассмотрим задачу классификации, которую вы, вероятно, уже видели:

Рассмотрим ту же задачу, но с шумом. Давайте посмотрим, что произойдет, если мы попытаемся классифицировать новые точки с k=1.

Рассмотрим теперь пример с k=3 и k=9.

Если мы возьмем предел, когда k приближается к размеру набора данных, мы получим модель, которая просто предсказывает класс, который чаще появляется в наборе данных (что на самом деле является ошибкой Байеса). Это модель с наибольшим смещением, но дисперсия равна 0 (поскольку наша ошибка не зависит от тестовых данных). Высокое смещение, потому что ему не удалось получить какую-либо локальную информацию о модели, но нулевое отклонение, потому что оно предсказывает одно и то же для любой новой точки данных.

Математическое доказательство использования kNN в качестве регрессионной модели

На самом деле мы можем математически показать, что увеличение k приводит к уменьшению дисперсии нашей модели, если рассматривать kNN как проблему регрессии. При этом наш предиктор становится функцией, определяющей непрерывные переменные:

Как и в случае с любой другой моделью, нас интересует минимизация ожидаемой ошибки E, где:

Мы можем расширить это, чтобы получить наше разложение смещения-дисперсии, например:

Смещение и дисперсия задаются как:

а последний член представляет собой фиксированное стандартное отклонение ошибок:

Если теперь мы рассмотрим нашу модель регрессионной модели kNN, мы сможем фактически определить выражения для смещения и дисперсии. Мы ограничиваем наш анализ заданной точкой, x_test.

Для смещения у нас есть:

Для дисперсии имеем:

В целом, мы получаем, что наш ожидаемый убыток следующий:

Мы можем очень ясно видеть, что по мере увеличения k, когда оно приближается к бесконечности (т. Е. Размеру набора данных), дисперсия модели стремится к 0. Неустранимая ошибка остается прежней. Хотя интуитивно мы ожидаем, что смещение будет увеличиваться, это нелегко показать математически. Однако использование предела k в той степени, в которой мы покрываем весь набор данных, означает, что наша регрессия kNN просто дает постоянное значение среднего (в частности, среднее значение всех точек, кроме точки, на которую мы смотрим). Таким образом, мы просто предсказываем постоянное значение и, таким образом, не собираем внутренней информации о базовой структуре наших данных, и поэтому наша систематическая ошибка будет высокой.

Эмпирические результаты: как k влияет на ошибку обобщения?

Я провел несколько экспериментов, чтобы увидеть, как выбор k влияет на ошибку обобщения. Вот такой сюжет у меня получился:

Это было выполнено для эксперимента с набором данных круга с m = 500 и test_size 20%.

Если мы посмотрим на график выше для значений k ниже 150, мы получим классическую кривую общей ошибки. Для малых значений k преобладает дисперсия, поэтому мы получаем высокую частоту ошибок. Для больших значений k наше смещение доминирует над высокой частотой ошибок.

Мы видим, что оптимальное значение k, которое дает минимальную ошибку, составляет около 27 (обратите внимание, что мы можем найти лучшее приближение, используя перекрестную проверку!).

Что действительно интересно на этом графике, так это тот факт, что ошибка почти стабилизируется для k > 150 примерно до 370. Хотя может показаться, что на заднем плане происходит что-то хитрое, этот результат на самом деле имеет смысл! Поскольку у нас есть проблема бинарной классификации и равные выборки из каждого класса, мы ожидаем, что для очень высоких значений k мы будем эффективно угадывать случайным образом между двумя классами, следовательно, частота ошибок 0,5!

Что любопытно, так это то, что примерно после 370 мы получаем увеличение частоты ошибок. Этому тоже есть объяснение, любезно предоставленное Каролис.

Это связано с тем, что функция train_test_split() случайным образом разбивает данные, и в результате баланс классов ни в тестовом, ни в тренировочном наборе не будет одинаковым. Когда наш классификатор имеет очень высокие значения k, он научится предсказывать класс, который чаще встречается в наборе поездов. В нашем тестовом наборе у нас будет дисбаланс классов в противоположном направлении, то есть класс, который реже встречается в наборе поездов, будет классом, который наиболее часто встречается в нашем тестовом наборе. Это отклонение приводит к увеличению ошибки и становится хуже, чем случайное предположение!

Чтобы показать это, можно определить среднюю частоту несбалансированного тестового набора, моделируя:

Средняя частота составила 0,540, как показано на графике!

Чтобы проверить теорию, я повторил эксперимент со стратифицированным train_test_split() (то есть гарантируя, что классы сбалансированы после разделения) и вуаля! Результаты соответствуют нашим ожиданиям!

Эмпирические результаты: как k влияет на границу решения?

Чтобы понять, что значит для модели «запоминать» шум (т. е. высокую дисперсию), я построил контурные графики для модели kNN при разных значениях k. Они ясно показывают границу решения.

Мы можем сравнить приведенные выше модели с фактическим набором обучающих данных.

Мы видим, что модель с k=25 лучше всего объясняет данные.

Эмпирические результаты: как m влияет на оптимальное значение k?

Я провел несколько экспериментов, чтобы определить влияние изменения размера набора данных m на оптимальное значение k.

Результаты были несколько интригующими, поэтому я хотел поделиться ими с вами:

Мы видим, что для набора данных make_circles() это увеличение почти линейно по m. Тот факт, что k увеличивается в результате увеличения m, имеет смысл, поскольку параметры данных (шум = 0,3 и коэффициент = 0,5) таковы, что при увеличении количества выборок будет огромная степень перекрытия.

В результате для меньших выборок нам нужно полагаться на локальные признаки для точных прогнозов и, следовательно, иметь меньшие значения k, но для больших нам потребуется более гладкая граница решения, чтобы гарантировать, что мы фиксируем тенденцию, а не генерируемый шум. от перекрытия.

С точки зрения того, почему эта зависимость является линейной, я могу только догадываться, что это потому, что мы линейно увеличиваем данные. Однако я не могу быть достаточно уверен в этом рассуждении.

Основные выводы

Модель kNN — это непараметрическая модель с гиперпараметром k.
Его производительность основана на общей ошибке, которая представляет собой сумму систематической ошибки, дисперсии и неустранимой ошибки.
Малые значения k запоминают шум и, таким образом, приводят к негладкой границе решения. Это увеличивает общую ошибку, в которой преобладает высокая дисперсия.
Большие значения k игнорируют лежащие в основе тенденции в данных (локальные особенности), что приводит к гладкому решению. граница. Это увеличивает общую ошибку, в которой преобладает высокое смещение.
Рассмотрение kNN как задачи регрессии позволяет вам математически показать приведенные выше результаты.
Оптимальное значение k — это то, которое балансирует между дисперсией и смещением. Это можно узнать с помощью перекрестной проверки. Если вы не знаете, с какого значения k начать анализ ваших данных, лучше всего начать с k = sqrt(m) или k = log(m).

Воспроизводимость

Если вы хотите воспроизвести результаты, загляните для этого на страницу GitHub. Если у вас есть какие-либо вопросы о каких-либо аспектах этого, пожалуйста, свяжитесь со мной!

Если вам действительно нравится моя работа и вы хотели бы поддержать меня, рассмотрите возможность использования моей реферальной ссылки, чтобы получить подписку на Medium.

Все изображения созданы автором, если не указано иное.

Почему увеличение k уменьшает дисперсию kNN?

Мысли и теория