Реализация и обзор метода К-ближайших соседей

Written on 21 Апреля 2011.

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

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

Наиболее легким способом разрешения этого является использование метода К-ближайших соседей.

Алгоритм K-ближайших соседей (KNN) является частью той науки, которая используется во многих приложениях в области глубинного анализа данных, статистического распознавания образов и т.д.

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

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

Также можно использовать Евклидово расстояние и другие меры, такие как расстояние Манхэттена.

Алгоритм выполнения алгоритма K-ближайших соседей состоит в:

   1. Определении параметра K = заблаговременное число ближайших соседей. Этот параметр вы устанавливаете сами.
   2. Расчет расстояния между экземпляром запроса и всеми пробными экземплярами. Вы можете использовать любой алгоритм расстояния
   3. Сортировка расстояний для всех пробных экземпляров и определение ближайшего соседа, основываясь на K минимальном расстоянии.
   4. Поскольку это управляемое обучение, вам необходимо получить все категории ваших пробных данных для сортируемого значения, которое попадает под K
   5. Использование большинства ближайших соседей в качестве значения для прогнозов.

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

Основы

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

Использование кода

Далее следует пример данных, который используется в качестве пробного. Управляемое обучение требует от вас знания того, какая "категория" представлена какими данными, и наоборот, к каким данным принадлежат категории. В пределах проекта нашими категориям и являются оценки за курсы в виде букв A,A-,B+,B,B-,C,F.

//----Пробный набор--------
double[] StudentA = new double[] { 9, 32, 65.1 };   //Финальная оценка A
double[] StudentB = new double[] { 12, 65, 86.1 };  //Финальная оценка A-
double[] StudentC = new double[] { 19, 54, 45.1 };  //Финальная оценка C
//------------------------

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

//Расположите пробный набор в List для последующего вызова

List<double[]> TrainingSet = new List<double[]>();
TrainingSet.Add(StudentA);
TrainingSet.Add(StudentB);
TrainingSet.Add(StudentC);
//------------------------

Следующий код получает атрибуты нового студента и располагает их в качестве требуемых данных для сравнения с каждым студентом в пробных данных.

 //------Новый студент (Student)------- 
//Получение данных из формы для новой оценки студента
List<double> newPlayer = new List<double>();
 newPlayer.Add(Convert.ToDouble(TextBox1.Text));
 newPlayer.Add(Convert.ToDouble(TextBox2.Text));
 newPlayer.Add(Convert.ToDouble(TextBox3.Text));

//метрика расстояний получает массив типа double
double[] newSudent = (double[])newPlayer.ToArray();
 //------------------------

Наконец, пробные данные (каждый студент) сравниваются с запрашиваемыми данными на основании расстояния между каждыми из них. Это означает, что вы получите минимальное расстояние запрашиваемых данных по каждому атрибуту студентов. К примеру, студент A и новый студент, затем студент B и новый студент

 //сравнение со всеми студентами
double distance = 0.0;
 for (int i = 0; i < TrainingSet.Count; i++)
{
  Response.Write("<hr/>");
  //Проверка вычисления Эвклидового расстояния между двумя точками данных
  distance = KNNs.EuclideanDistance(newSudent, TrainingSet[i]);
  Response.Write("<br/>Эвклидово расстояние нового студента: " + distance);
  distance = KNNs.ChebyshevDistance(newSudent, TrainingSet[i]);
  Response.Write("<br/>Расстояние Чебышева нового студента: " + distance);
  distance = KNNs.ManhattanDistance(newSudent, TrainingSet[i]);
  Response.Write("<br/>Расстояние Манхэттена нового студента: " + distance);
 }

Кратчайшее расстояние является категорией, в которую попадут ваши пробные данные на основе K. Это означает, что если у вас K=2 , то вы выбираете 2 кратчайших расстояния и сравниваете категории.

Преимущества

Стойкие и зашумленные данные (особенно, если мы используем инверсированный квадрат взвешенного расстояния в качестве “расстояния”)
Эффективно в случае, если пробные данные велики в объеме

Недостатки

Необходимо определить значение параметра K (число ближайших соседей)
В случае с обучением на основе расстояния не совсем ясно, какой тип расстояния использовать и какие атрибуты использовать для производства наилучших результатов. Стоит ли использовать все атрибуты или выборочные?
Затраты в производительности велики, поскольку нам необходимо вычислить расстояния между каждым экземпляром и всеми пробными экземплярами. Некоторая индексация (к примеру, дерево K-D) может помочь в снижении данных затрат

< Назад

форум разработчиков