README.md

вернуться к оглавлению

Глава 10. Алгоритм k ближайших соседей

Используется для работы с большими наборами данных.

1. Извлечение признаков - каждый элемент набора данных приводится к некоторому
   набору признаков, каждый признак оценивается. Например, у фруктов можно извлекать
   признаки Размера и Цвета.
2. Расположение элементов на графике (мерность по количеству признаков) в соответствии
   со значением признаков. Например, грейпфруты - большие и красные, а апельсины - маленькие
   и желтые, они будут собираться в разных частях графика.
3. Решение задачи классификации - есть некоторая точка с определенными признаками.
   Нужно определить, чем она является (Апельсин или Грейпфрут?). Точка размещается на графике,
   для нее находятся k ближайших точек (определение ближайших точек может проводиться
   по разным алгоритмам). Если среди них больше апельсинов, то вероятно целевая точка - апельсин.
   

ПОСТРОЕНИЕ РЕКОМЕНДАТЕЛЬНОЙ СИСТЕМЫ

1. При регистрации пользователи оценивают фильмы разных жанров.
   Таким образом, они преобразуются к набору признаков (Комедия - 5, Ужасы - 1),
   и теперь их можно разместить на графике.
   
2. Чтобы порекомендовать какой-нибудь фильм одному пользователю, мы берем
   k ближайших к нему людей на графике и смотрим, что понравилось им.

РАССЧЕТ РАССТОЯНИЯ МЕЖДУ ТОЧКАМИ

Формула Пифагора

Точка А(a1, b1, c1) и Точка B(a2, b2, c2):

√ _{((a1 - a2)² + (b1 - b2)² + (c1 - c2)²)}

Сумма векторов.

Близость косинусов

Метрика близости косинусов не измеряет расстояние между двумя векторами.
Вместо этого она сравнивает углы двух векторов.

ИЗВЛЕЧЕНИЕ ПРИЗНАКОВ

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

Признаки должны иметь значение для той задачи, которую мы решаем. Также они не
должны содержать смещения (то есть быть равномерно распределены -
не оценивать пользователей только по комедиям).

КЛАССИФИКАЦИЯ

Распределение по категориям.

РЕГРЕССИЯ

Прогнозирование чего-либо в числовом выражении.

Алгоритм ближайших k соседей может также применяться для решения задачи регрессии

• например, прогнозирование оценки пользователя конкретному фильму.

ЗНАКОМСТВО С МАШИННЫМ ОБУЧЕНИЕМ

РАСПОЗНАВАНИЕ ТЕКСТА

OCR (Optical Character Recogition) - оптическое распознавание текста.
Алгоритм также основывается на алгоритме ближайших соседей.

• Перебираются различные изображения символов.
• У них извлекаются определенные признаки (кривые, линии, точки,
  кружочки в определенных позициях).
• Для нового изображения также извлекаются признаки и по алгоритму
  ближайших соседей делается вывод, какой символ оно представляет.

ПОСТРОЕНИЕ СПАМ-ФИЛЬТРА

Наивный классификатор Байеса

В тренировочном наборе данных - сообщения, отмеченные как спам и как не-спам.
Алгоритм вычисляет характерные для спама слова.