Технология заметок интеллектуального анализа данных - Глава 5 Алгоритм классификации KNN

Создайте классификатор из мер относительного расстояния

Среди них наиболее представительным является алгоритм KNN.

Ссылка: «Принципы статистического обучения Ли Ханга»

1. Введение в алгоритм KNN

набор данных: $T={[(x_1,y_1),(x_2,y_2),...,(x_n,y_n)]}$

в $x_i \in \mathcal{X} \in \mathbb{R}^n$ вектор признаков экземпляра, $y_i \in \mathcal{Y}=[c_1,c_2,...,c_N]$ это класс экземпляра, $i=1,2,...,N$

Вывод: Пример $x$ класс, к которому принадлежит $y$ .

По заданному вектору расстояний в обучающей выборке $T$ найдено с $x$ ближайшийkточки, охватывающие это $k$ точка $x$ окрестности $N_k(x)$ ;
существует $N_k(x)$ в соответствии с классификационными правилами принятия решений $x$ категория $y$ ;

Модель

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

В пространстве признаков для каждой точки обучающего экземпляра $x$ , и все точки ближе к этой точке, чем другие точки, образуют область, называемую ячейкой (ce11). Каждая точка тренировочного экземпляра имеет единицу измерения, а единицы всех точек тренировочного экземпляра составляют часть пространства признаков. Метод ближайшего соседа будет примером $x_i$ тип $y$ , так как все точки в его ячейке ярлык класса. Таким образом определяется класс точек экземпляра для каждой единицы.

мера расстояния

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

Обычно используется евклидово расстояние, конечно, есть и $L_p$ расстояние и расстояние Минковского.

Выбор значения k

Выбор значения k может оказать существенное влияние на результаты метода k ближайших соседей.

Если вы выберете маленькое значение k, это эквивалентно построению прогнозов с обучающими примерами в меньшей окрестности, ошибка аппроксимации «обучения» будет уменьшена, и будут использоваться только обучающие примеры, которые ближе к входному примеру. Работа. Но недостатком является то, что ошибка оценки «обучения» будет увеличиваться, а результат прогнозирования будет очень чувствительным к соседним точкам экземпляра.Если соседние точки экземпляра окажутся шумом, прогноз будет неверным. Другими словами, уменьшение значения k означает, что общая модель усложняется и возникает вероятность переобучения.

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

В приложениях значение k обычно принимает относительно небольшое значение. Перекрестная проверка обычно используется для выбора оптимального значения k.

Правила классификации

Правило классификации KNN:меньшинство подчиняется большинствуправило

Функция потерь представляет собой функцию потерь 0-1, а правила классификации таковы:

f:R^n \rightarrow {c_1,c_2,...,c_k}

Затем для набора соседних k точек обучающего экземпляра $N$ , частота ошибок (ошибок классификации):

\frac{1}{k} \sum_{x_i \in N_k(x)}I(y_i \neq c_j) = 1-\frac{1}{k} \sum_{x_i \in N_k(x)}I(y_i =c_j)

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

кд дерево

При реализации KNN основное внимание уделяется тому, как выполнить быстрый поиск ближайших соседей по K для обучающих данных.Если размер пространства признаков велик или емкость обучающих данных велика, то хранение данных является большой проблемой. Самый простой метод реализации KNN — линейное сканирование, в то время, когда набор данных большой, расчет занимает очень много времени. Для повышения эффективности этого поиска используется специальная структура для хранения обучающих данных — дерево kd (дерево kd). kd-дерево — это древовидная структура данных, в которой хранятся точки в k-мерном пространстве для быстрого поиска. По сути, kd-дерево — это бинарное дерево, которое представляет собой разделение k-мерного пространства.