рекомендации

четверг, 8 февраля 2018 г.

Упрощенное введение в алгоритм k-ближайших соседей

  
За четыре года моей карьеры в аналитике среди моделей, которые я строил, более 80% были моделями классификации, и всего лишь 15-20% моделями регрессии. Эти отношения могут быть более или менее обобщены по всей отрасли. Причиной смещения к классификационным моделям является то, что большинство аналитических проблем связано с принятием решения. В этой статье мы поговорим о широко используемом методе классификации, называемом методом  k-ближайших соседей (KNN). Основное внимание будет сосредоточено на том, как работает алгоритм и как входной параметр влияет на результаты прогнозирования. 
  
Когда нужно использовать алгоритм KNN? 
  
KNN может использоваться как для задач классификации, так и для регрессии. Однако чаще он широко используется в задачах классификации. Чтобы оценить любую методику, мы обычно рассматриваем 3 важных аспекта: 
  
1. Простота интерпретации вывода 
2. Время вычислений 
3. Предсказательная мощность 
  
Рассмотрим сравнительную характеристику нескольких алгоритмов: 

 
  
Алгоритм KNN часто выбирают из-за простоты интерпретации результатов его работы, а также быстроты работы. 
  
Как работает алгоритм KNN? 
  
Давайте рассмотрим простой пример, чтобы понять этот алгоритм. Ниже приводится распределение красных кружков (RC) и зеленых квадратов (GS): 

 
  
Вы намерены найти, к какому классу принадлежит голубая звезда (BS).  K - это количество ближайших соседей, которых мы будем учитывать при классификации. Скажем, K = 3. Следовательно, теперь мы наносим на график точку BS, и рисуем круг с центром в BS, такой величины, чтобы включить только три ближайшие точки данных. Процесс показан на следующей диаграмме: 

 


Три ближайших точки к BS -  все RC. Следовательно, с большой долей вероятности мы можем сказать, что BS должна принадлежать классу RC. Здесь выбор очевиден, поскольку все три голоса от ближайших соседей отданы RC.  В этом алгоритме очень важен выбор параметра К. Как его правильно выбрать? 
  
Сначала попробуем понять, как именно величина K влияет на алгоритм. В нашем примере все 6 обучающих наблюдений остаются постоянными, и при заданном значении K мы можем определить границы каждого класса. Эти границы будут отделять RC от GS. Ниже приведены различные границы, разделяющие два класса, при разных значениях K. 
  
  
 
  
Можно заметить, что граница становится более гладкой с увеличением значения K. При увеличении K до бесконечности все точки станут синими или красными, в зависимости от того, точек какого цвета больше. Для оценки эффективности нашей модели нам нужны частоты ошибок обучения и проверки при различных значениях K. Ниже приведена кривая для частоты ошибок обучения в зависимости от величины K: 
  
 
  
Как вы можете видеть, частота ошибок для обучающей выборки при K=1 всегда равна нулю. Это происходит потому, что ближайшая точка к любой точке данных при обучении - это она сама. Следовательно, при K=1 прогноз всегда точен. Если бы кривая ошибок проверки была бы аналогична, идеальным выбором было бы K=1. Ниже приведена кривая ошибок проверки в зависимости от величины K: 
  
 
  
Здесь все выглядит более понятным. При K=1 мы переобучаемся. Следовательно, частота ошибок изначально уменьшается и достигает минимума. После точки минимума, она затем снова увеличивается с ростом K. Для получения оптимального значения K, вы можете выделить из исходного набора данных обучающую и проверочную выборки. После этого постройте кривую ошибок проверки, чтобы получить оптимальное значение K. Это значение K должно использоваться для всех прогнозов на данном наборе данных. 
  
Заключение 
  
Алгоритм KNN является одним из простейших алгоритмов классификации. При этом он вполне конкурентоспособен. Алгоритм KNN также может использоваться для задач регрессии. Единственным отличием от рассмотренной методологии будет использование средних от ближайших соседей. KNN можно закодировать в одной строке на R. 

Комментариев нет:

Отправить комментарий