Scikit Learn - Ближайшие соседи по K (KNN)

Эта глава поможет вам понять методы ближайшего соседа в Sklearn.

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

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

Основной принцип методов ближайшего соседа -

  • Чтобы найти заранее определенное количество обучающих выборок на расстоянии от новой точки данных

  • Предскажите метку из этого количества обучающих выборок.

Здесь количество выборок может быть определяемой пользователем константой, как при обучении K-ближайшего соседа, или изменяться в зависимости от локальной плотности точки, как при обучении соседа на основе радиуса.

Модуль sklearn.neighbors

Scikit-learn имеют sklearn.neighborsмодуль, который обеспечивает функциональность как для неконтролируемых, так и для контролируемых методов обучения на основе соседей. В качестве входных данных классы в этом модуле могут обрабатывать либо массивы NumPy, либоscipy.sparse матрицы.

Типы алгоритмов

Различные типы алгоритмов, которые могут использоваться в реализации методов на основе соседей, следующие:

Грубая сила

Вычисление расстояний между всеми парами точек в наборе данных методом перебора обеспечивает наиболее простую реализацию поиска соседей. Математически для N образцов в D измерениях метод грубой силы масштабируется как0[DN2]

Для небольших выборок данных этот алгоритм может быть очень полезным, но он становится невозможным по мере роста количества выборок. Поиск соседей методом грубой силы можно включить, введя ключевое словоalgorithm=’brute’.

KD Tree

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

Преимущества

Ниже приведены некоторые преимущества алгоритма дерева KD.

Construction is fast - Поскольку разбиение выполняется только по осям данных, KD-дерево строится очень быстро.

Less distance computations- Этот алгоритм требует очень меньшего количества вычислений расстояния для определения ближайшего соседа точки запроса. Это займет всего лишь[ ()] вычисления расстояния.

Недостатки

Fast for only low-dimensional neighbor searches- Это очень быстро для низкоразмерных (D <20) поисков соседей, но по мере роста D становится неэффективным. Поскольку разбиение выполняется только по осям данных,

Поиск соседей по дереву KD можно включить, написав ключевое слово algorithm=’kd_tree’.

Мяч дерево

Поскольку мы знаем, что KD Tree неэффективно в высших измерениях, поэтому для устранения этой неэффективности KD Tree была разработана структура данных Ball tree. Математически он рекурсивно делит данные на узлы, определяемые центроидом C и радиусом r, таким образом, чтобы каждая точка в узле лежала внутри гипер-сферы, определяемой центроидомC и радиус r. Он использует неравенство треугольника, приведенное ниже, что уменьшает количество точек-кандидатов для поиска соседей.

$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$

Преимущества

Ниже приведены некоторые преимущества алгоритма Ball Tree:

Efficient on highly structured data - Поскольку шаровое дерево разбивает данные на серию вложенных гипер-сфер, оно эффективно для сильно структурированных данных.

Out-performs KD-tree - Дерево шаров превосходит дерево KD в больших измерениях, потому что оно имеет сферическую геометрию узлов дерева шаров.

Недостатки

Costly - Разделение данных на ряд вложенных гипер-сфер делает его создание очень дорогостоящим.

Поиск соседей по шаровому дереву можно включить, написав ключевое слово algorithm=’ball_tree’.

Алгоритм выбора ближайших соседей

Выбор оптимального алгоритма для данного набора данных зависит от следующих факторов:

Количество образцов (N) и размерность (D)

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

  • Время запроса алгоритма грубой силы растет как O [DN].

  • Время запроса алгоритма дерева Болла растет как O [D log (N)].

  • Время запроса алгоритма дерева KD изменяется с D странным образом, который очень трудно охарактеризовать. Когда D <20, стоимость составляет O [D log (N)], и этот алгоритм очень эффективен. С другой стороны, это неэффективно в случае, когда D> 20, потому что стоимость увеличивается почти до O [DN].

Структура данных

Другой фактор, влияющий на производительность этих алгоритмов, - это внутренняя размерность данных или их разреженность. Это связано с тем, что это может сильно повлиять на время запроса алгоритмов дерева Болла и дерева КД. В то время как время запроса алгоритма грубой силы не зависит от структуры данных. Как правило, алгоритмы Ball tree и KD tree обеспечивают более быстрое время запроса при внедрении в более разреженные данные с меньшей внутренней размерностью.

Количество соседей (k)

Число соседей (k), запрошенных для точки запроса, влияет на время запроса алгоритмов дерева Болла и дерева KD. Время их запроса сокращается по мере увеличения числа соседей (k). В то время как время запроса грубой силы не зависит от значения k.

Количество точек запроса

Поскольку им требуется этап построения, алгоритмы KD-дерева и Ball tree будут эффективны при большом количестве точек запроса. С другой стороны, при меньшем количестве точек запроса алгоритм грубой силы работает лучше, чем алгоритмы дерева КД и дерева Болла.