Математические основы kNN

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

Математическая часть классификатора.

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

Вектор – это направленный отрезок в пространстве(на плоскости). У вектора есть две характеристики: длина и направление, но мы будем рассматривать вектора немного по-другому. Ниже представлена декартова система координат, всем знакомая ещё со школы. На этой двумерной системе координат отмечен вектор А, с координатами x и y. x – расстояние откладываемое по оси OX, аналогично y - расстояние откладываемое по оси OY. Таким образом, у вектора есть две координаты которые указывают конец вектора. Начало вектора находиться в нулевой системы координат. При условии если начало вектора будет в нулевой точке системы координат, то длинна вектора считается по формуле |a| = .

 

Теперь рассмотрим две точки в декартовой системе координат. Точка А(α1, β1) и В(α2, β2) α – координаты точек по оси OX, β – координаты точек по оси OY. Нам нужно найти расстояние между этими 2-я точками. Голубым цветом нарисован вектор длинна которого будет равна расстоянию между точками А и В. Каким образом это связано с нейронными сетями и классификатором? – спросите Вы меня, скажу сразу в математике всегда так, Вы должны абстрагироваться и понять суть метода, а не заучить формулы, только тогда Вы научитесь «прикладывать» математику к жизненным задачам, дальше поймёте зачем мы вычисляли расстояние между точками. Итак, в предыдущем случае начало вектора было в нулевой точке и мы легко могли посчитать его длину. В этом случае что нам мешает перенести систему координат в точку В(α2, β2)? Ничего,  другой вопрос как это сделать. Поочерёдно из каждой координаты по оси OY вычтем β2 , тем самым мы «приподнимем» систему координат вверх, координата β2 при это занулиться. Теперь повторим действия для координат по оси OX, этим действием мы пододвинем систему координат вправо. Координата α2 занулиться и точка В будет совпадать с нулевой точкой системы координат. Теперь по формуле приведённой выше можно легко посчитать расстояние между этими двумя точками. Можно было привести готовую формулу сразу, но тогда Вы не поняли бы суть. Формула по которой можно посчитать расстояние между 2-я точками в двумерной системе координат:  . При работе с классификатором маловероятно то, что Вы будете работать всего лишь с 2-я измерениями. Поэтому стоит привести формулу для расчета расстояния в многомерной системе координат:  , где n это количество измерений.

 

 

Основная идея метода классификации k-ближайших соседей.

 Теперь, зная математическую основу классификатора, мы можем перейти к детальному рассмотрению самого алгоритма.

Метрические классификаторы применяются для распознавания образов, они определяют степень «сходства» между различными объектами. Применяются, когда, либо сложно, либо мы не можем сформировать достаточно «хорошее» признаковое описание объектов. Фактически мы используем сырые данные, которые по нашему мнению содержат в себе информацию об объекте, но оснований так считать нет.

Идейная составляющая метрических классификаторов основывается на том, что похожие объекты очень часто находятся «рядом», т.е. на близком расстоянии друг от друга. Для тех кто хочет почитать более строгое основание рекомендую ознакомиться с гипотезой компактности. Рассмотрим, как мы, с человеческой точки зрения, определяем сходство между объектами. Например, как мы распознаём своих знакомых и друзей: мы запоминаем общие черты лица, цвет волос, цвет глаз, голос, походку, стиль одежды и другие признаки. Тех, кого мы видим очень часто, мы просто полностью запоминаем, набор признаков наиболее полон, кого видим реже, запоминаем только общие признаки без деталей. Когда мы получаем информацию от органов восприятия, мы сравниваем её с информацией в памяти, если находиться «схожий» объект в памяти, из памяти сразу же приходит название этого объекта или имя, или все ассоциированные (связанные) с этим объектом воспоминания (информация в памяти). Схожий объект именно по информации, полученной от органов восприятия. Рассмотрим, выше сказанное, на абстрактном примере, который покажет работу метрического классификатора. У нас есть 3 объекта, у каждого из них 2 координаты. Каждый из трёх объектов был замечен (запечатлён в памяти) 5 раз. Чёрным цветом обозначена точку координаты, которой мы знаем, но к какому объекту принадлежит эта точка нужно определить.

Объект 1

Объект 2

Объект 3

Неопределённый Объект

X

Y

X

Y

X

Y

X

Y

0,3

0,1

0,7

0,8

0,1

0,8

0,25

0,5

0,5

0,2

0,9

0,75

0,2

0,9

 

0,5

0,1

0,85

0,9

0,3

0,7

 

0,4

0,1

0,55

0,65

0,1

0,9

 

0,35

0,1

0,65

0,75

0,1

0,5

 

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

Объект 1

 

Объект 2

 

Объект 3

 

X

Y

Метрика

X

Y

Метрика

X

Y

Метрика

0,3

0,1

0,403113

0,7

0,8

0,540833

0,1

0,8

0,33541

0,5

0,2

0,390512

0,9

0,75

0,696419

0,2

0,9

0,403113

0,5

0,1

0,471699

0,85

0,9

0,72111

0,3

0,7

0,206155

0,4

0,1

0,4272

0,55

0,65

0,33541

0,1

0,9

0,4272

0,35

0,1

0,412311

0,65

0,75

0,471699

0,1

0,5

0,15

Ближайшие соседи

 

0,1

0,5

0,15

Объект 3

 

0,3

0,7

0,206155

Объект 3

 

0,1

0,8

0,33541

Объект 3

 

0,55

0,65

0,33541

Объект 2

 

 

 Из 4 соседей 3 принадлежат одному объекту под №3, одна точка принадлежит объекту 2. Степень схожести неопределённого объекта с объектом 3 равна 0,75(3/4), следовательно, точка, скорее всего, принадлежит объекту 3. Максимально значение схожести 1, минимальное 0. Количество координат можно увеличивать, тогда классификация может быть точнее, это зависит от того насколько новую и качественную информацию Вы будете подавать в качестве измерений объектов.

Плюсы и минусы алгоритма.

+      Важным преимуществом этого алгоритма является то, что обучение заключается в запоминании обучающей выборки.

+      Простота реализации и возможность вводить дополнительные параметры настройки.

+      Прецедентная логика работы алгоритма хорошо понятна экспертам в предметных областях(медицина, биометрия, юриспруденция).

-      Приходиться хранить обучающую выборку целиком. Не эффективный расход памяти.

-      Большое количество операций при классификации образов. Как следствие работа с большими выборками занимает намного больше времени, в сравнении с традиционными НС.

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

Средняя: 4 (4 оценок)
Tradexperts.ru в социальной сети вконтакте Tradexperts.ru в социальной сети Google+ Tradexperts.ru в социальной сети Facebook Tradexperts.ru в социальной сети Twitter Tradexperts.ru на Youtube