Я специалист по данным со страстью к письму. И что может быть лучше, чем объединить мои увлечения. Так что тут ничего!

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

  1. Немного истории КНН
  2. Его геометрическая интуиция и идеология алгоритма
  3. Метрики расстояния
  4. Значение K и поверхности принятия решений

Краткая история KNN

«В статистике алгоритм k ближайших соседей (k-NN) — это непараметрический метод обучения с учителем, впервые разработанный Эвелин Фикс и Джозефом Ходжесом в 1951 году, а затем расширенный Томасом Кавером. Он используется для классификации и регрессии». (Википедия).

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

Геометрическая интуиция и идеология

Предположим, у нас есть набор данных D, содержащий {xi, yi}, где xi ∈ ℝ и yi ∈ {0,1}. Эти данные являются репрезентативными для простой бинарной классификации. Возьмем точку xq, принадлежащую D, и попытаемся предсказать, к какому классу она принадлежит.

  1. Наш KNN сначала рассчитает все расстояния от xq до любой другой точки в нашем наборе данных и сохранит их.
  2. Затем он выберет верхние K расстояний и применит правило большинства к этим классам и назначит основной класс нашему xq.
  3. Точно так же, если бы это была проблема регрессии, где yi ∈ ℝ, она выбрала бы верхние K расстояний и вычислила среднее или медиану (устойчивую к выбросам) целевых переменных.
  4. Это один из самых простых и ранних алгоритмов как для классификации, так и для регрессии. Для многоклассовой классификации мы можем использовать метод One Vs All, так как он может предсказать, принадлежит ли точка данных классу 1 или нет. Однако существуют и другие мощные алгоритмы для многоклассовой классификации.

Метрики расстояния

Существуют различные меры расстояния, которые вы можете выбрать при обучении KNN. Некоторые из них:

1.Евклидово расстояние: предположим, что для точки x1 мы выбираем две функции f1,f2, чтобы представить ее на двумерной плоскости. (x11,x12) и аналогично для точки x2 это будет (x21,x22). Евклидово расстояние — это кратчайшее расстояние между любыми двумя точками. Математически представлено как евклидово расстояние = √((x21 — x11)² + (x22 — x12)²)

2. Манхэттенское расстояние: это норма вектора расстояния (x1–x2), представляющая собой сумму абсолютных расстояний по обеим осям. Манхэттенское расстояние = |x21 — x11| + |x22 — x12|

3. Расстояние Минковского: это более общая форма измерения расстояний. На самом деле оба приведенных выше термина являются частными случаями расстояния Минковского. Расстояние Минковского = (Σ|i=1 до d| |xi — yi|^p)^(1/p), где: d — количество измерений (признаков) в данных. xi и yi — соответствующие значения признаков двух точек x1 и x2 в i-м измерении. p — параметр, определяющий порядок расстояния Минковского. При p=1 оно становится манхэттенским расстоянием, а при p=2 — евклидовым расстоянием. Для других положительных постоянных значений p он представляет собой расстояние Минковского порядка p.

4. Расстояние Хэмминга (булев вектор): когда есть два вектора, каждый из которых содержит различные элементы либо 0, либо 1, мы вычисляем его как 1 единицу, если элементы в одном и том же индексе не совпадают. Пример: x1=[1,0,0,1] и x2=[1,0,0,0], тогда расстояние Хэмминга будет равно 1. Это обычно используется в AGTC Генного кода/Последовательности.

5. Косинусное сходство и косинусное расстояние:

Косинусное расстояние:
Для двух ненулевых векторов A и B в d-мерном пространстве косинусное расстояние вычисляется следующим образом:

Косинусное расстояние = 1 — (A · B) / (||A|| * ||B||)

где:
- A · B представляет скалярное произведение векторов A и B.
- ||A|| представляет евклидову норму (величину) вектора A.
- ||B|| представляет евклидову норму (величину) вектора B.

Косинусное расстояние находится в диапазоне от 0 до 2, где 0 означает, что векторы идентичны, а 2 означает, что они полностью ортогональны (полностью не похожи). Чем меньше косинусное расстояние, тем более похожи векторы.

Косинусное подобие:
Для двух ненулевых векторов A и B в d-мерном пространстве косинусное подобие вычисляется следующим образом:

Подобие косинусов = (A · B) / (||A|| * ||B||)

где:
- A · B представляет скалярное произведение векторов A и B.
- ||A|| представляет евклидову норму (величину) вектора A.
- ||B|| представляет евклидову норму (величину) вектора B.

Косинусное сходство находится в диапазоне от -1 до 1, где 1 означает, что векторы указывают в одном направлении (полное сходство), 0 означает, что они ортогональны (отсутствие подобия), а -1 означает, что они указывают в противоположных направлениях (полное различие). ). Чем больше косинусное сходство, тем более похожи векторы.

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

Euc-расстояние(A,B)**2 = 2[(1-cos(угол)] = 2[cos-расстояние(A,B)]

Если x1,x2 единичные векторы, cos(angle)=x1.x2

Поверхности принятия решений:

Поверхности решений — это кривые/поверхности, которые отделяют один класс от другого. Они могут быть 2D, 3D, nD и т. д. Чем выше значение K, тем плавнее кривая. Кроме того, поверхности решений и значение K также учитывают переоснащение и недообучение.

Более подробная информация будет в следующем блоге. Оставайтесь с нами, чтобы узнать больше.