Как это работает

Что такое KNN?

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

Как это работает?

KNN довольно прост, представьте, что у вас есть данные о цветных шарах:

  • Фиолетовые шары;
  • Желтые шары;
  • И мяч, который вы не знаете, фиолетовый он или желтый, но у вас есть все данные об этом цвете (кроме цветовой метки).

Итак, как вы собираетесь узнать цвет мяча? Представьте, что вам нравится машина, у которой есть только характеристики (данные) мяча, но нет окончательной маркировки. Как вы хотите узнать цвет мяча (последняя метка / ваш класс)?

Замечания: Предположим, что данные с номером 1 (и меткой R) относятся к фиолетовым шарам, а данные с номером 2 (и меткой A) относятся к желтым шарам, это просто для облегчения объяснения, в будущих статьях мы будет работать с реальными данными.

Каждая строка относится к шару, и каждый столбец относится к характеристике шара, в последнем столбце у нас есть класс (цвет) каждого из шаров:

  • R - ›фиолетовый;
  • A - ›желтый

У нас есть 5 мячей (5 строк), каждый с вашей классификацией, вы можете попытаться определить цвет нового мяча (в случае класса) из N способов, один из этих N способов - сравнить характеристики этого нового мяча со всеми другие, и посмотрите, как он выглядит больше всего, если данные (характеристики) этого нового шара (вы не знаете правильный класс) аналогичны данным желтых шаров, тогда цвет нового шара будет желтый, если данные в новом шаре больше похожи на данные пурпурного, чем желтого, тогда цвет нового шара пурпурный, он выглядит так просто, и это почти то, что делает Knn, но в самом сложном способ.

В случае с KNN, действительно, он не «сравнивает» новые (несекретные) данные со всеми остальными, на самом деле он выполняет математический расчет, чтобы измерить расстояние между данными, чтобы сделать классификацию (это почти то же самое). Это вычисление, о котором я говорю, может быть любым другим вычислением, измеряющим расстояние между двумя точками, например: Евклидовым, Манхэттенским, Минковским, Взвешенным ...

Действия, выполняемые KNN:

1 - получить несекретные данные;

2 - Измерьте расстояние (евклидово, манхэттенское, по Минковскому или взвешенное) от новых данных до всех других данных, которые уже классифицированы;

3 - Получает K (K - параметр, который вы задаете) меньших расстояний;

4 - Проверьте список классов, у которых было самое короткое расстояние, и подсчитайте количество каждого класса, который появляется;

5 - Принимает за правильный класс класс, который появлялся чаще всего;

6 - классифицирует новые данные по классу, взятому на шаге 5;

Ниже у нас есть изображение со всем процессом, о котором мы говорим в этой статье, у вас есть несекретные данные (красным цветом), а все остальные ваши данные уже классифицированы (желтый и фиолетовый), каждый с вашим классом (A или B). Таким образом, вы вычисляете расстояния ваших новых данных со всеми остальными, чтобы узнать, какие из них имеют наименьшее расстояние, поэтому вы получаете 3 (или 6) ближайших данных и проверяете, какой класс появляется больше всего, в случае изображения ниже, самые близкие данные к новым данным - это те, которые находятся внутри первого круга (внутри круга), а внутри этого круга есть 3 других данных (уже отмеченных желтым цветом), мы проверим, какой класс там преобладает, посмотрите, это фиолетовый, потому что есть 2 фиолетовых шара и только 1 желтый, оооочень эти новые данные, которые раньше не были классифицированы, теперь они будут классифицированы как фиолетовые.

Расчет расстояния:

Вычислить расстояние между двумя точками (ваша новая выборка и все данные, которые у вас есть в вашем наборе данных) очень просто, как было сказано ранее, есть несколько способов получить это значение, в этой статье мы будем использовать евклидово расстояние.

Формула евклидова расстояния похожа на изображение ниже:

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

Используя эту формулу, вы будете проверять расстояние между 1 точкой (ваш несекретный образец) и 1 другой точкой в ​​вашем наборе данных (1 другими уже засекреченными данными), одна за другой во всем вашем наборе данных, тем меньше будет результат этого расчета. аналогично между этими двумя данными. И да, вы будете запускать этот расчет столько раз, пока не запустите его для всех данных, когда вы это сделаете, у вас будет массив (давайте использовать массив в качестве примера) с результатом) ваших неклассифицированных данных для другие данные уже засекречены.

Хорошо давай сделаем это! Это просто, но читайте медленно, в основном вы:

  • Получите каждую характеристику из вашего набора данных;
  • Вычтите каждую, например, (строка 1, столбец 5) - (строка 1, столбец 5) = X… (строка 1, столбец 13) - (строка 1, столбец 13) = Z;
  • После вычитания всех столбцов вы получите все результаты и просуммируете их X + Y + Z…;
  • Таким образом, вы получите квадратный корень из суммы;

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

В этом примере у нас есть 5 данных (строк), каждый образец (данные / строка) имеет ваши атрибуты (характеристики), давайте ПРЕДСТАВЬТЕ, что все это изображения, каждая строка будет изображением, а каждый столбец будет быть пикселем изображения.

Итак, давайте начнем с того, что объяснили выше.

Давайте возьмем первую строку, которая представляет собой данные, которые мы хотим классифицировать, и давайте измерим евклидово расстояние до строки 2.

1 - Вычитание

Давайте вычтем каждый атрибут (столбец) из строки 1 с атрибутами из строки 2, например:

(1–2) = -1

2 - Возведение в степень:

После того, как вы вычли столбец 1 из строки 1 и столбец 1 из строки 2, мы получим квадратный корень, поэтому числа результатов всегда будут положительными, например:

(1–2)² = (-1)²
(-1)² = 1

3 - Сумма

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

(1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² + 
(1–2)² = 8

Обратите внимание, что у нас есть 8 столбцов атрибутов, как в строке 1, так и в строке 2, и мы выполнили шаг 2 для каждого атрибута набора данных, поэтому наш окончательный результат был 8, но почему 8? Поскольку каждый раз, когда мы запускаем шаг 2, результат давал 1, по «совпадению» у нас одни и те же данные во всех столбцах, а результат (1–2) ² равен 1, я использовал эти значения для упрощения математических расчетов. , но нет, эти атрибуты не обязательно должны быть одним и тем же номером, позже мы увидим это лучше при реализации кода с этим алгоритмом.

4 - квадратный корень:

После выполнения шага 3 мы получим квадратный корень из суммы вычитаний. На шаге 3 результат был 8, поэтому возьмем квадратный корень из числа 8:

√8 = 2,83 ou 8^(½) = 2,83

Большой! Теперь у вас есть евклидово расстояние от строки 1 до строки 2, посмотрите, это было не так сложно, вы могли бы сделать это на простой бумаге!

Теперь вам нужно сделать это только для всех строк набора данных, от строки 1 до всех других строк, когда вы это сделаете, у вас будет евклидово расстояние от строки 1 до всех других строк, затем вы отсортируете его, чтобы получить «k ”(Например, k = 3) наименьшие расстояния, чтобы вы проверили, какой класс появляется чаще всего, класс, который появляется чаще всего, будет классом, который вы будете использовать для классификации строки 1 (которая не была классифицирована ранее).

Все просто, правда? В следующих статьях мы начнем реализовывать этот алгоритм в GO! Но не волнуйтесь, синтаксис Go настолько прост, что вы будете следовать руководству и применять его на своем языке.

ТКС!