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 будут эффективны при большом количестве точек запроса. С другой стороны, при меньшем количестве точек запроса алгоритм грубой силы работает лучше, чем алгоритмы дерева КД и дерева Болла.