Как ускорить работу классификатора knn?

Это откорректированный технический перевод, сохраняющий основной смысл.

K - Ближайшие соседи (kNN) — это простой алгоритм ML для классификации и регрессии. Scikit-learn предлагает обе версии с очень простым API, что делает его популярным в курсах по машинному обучению. Есть одна проблема с ним — он довольно медленный! 

Можно заставить его работать с большими наборами данных с помощью библиотеки faiss.

===================================

Алгоритм kNN должен найти ближайших соседей в обучающей выборке для классифицируемой выборки. По мере увеличения размерности (количества признаков) данных время, необходимое для поиска ближайших соседей, увеличивается очень быстро. Чтобы ускорить прогнозирование, на этапе обучения (метод .fit()) классификаторы kNN создают структуры данных, чтобы упорядочить набор обучающих данных, что поможет при поиске ближайших соседей.

Реализация классификатора kNN с помощью faiss

Отличительной особенностью faiss является то, что в нем есть инструкции по установке и сборке (документы по установке), а также отличная документация с примерами (документы по началу работы). После установки мы можем написать собственно классификатор. Код довольно прост, так как мы просто имитируем API Scikit-learn.

Здесь есть несколько интересных элементов:

Атрибут index содержит структуру данных, созданную faiss для ускорения поиска ближайшего соседа

данные, которые мы помещаем в индекс, должны быть типа Numpy float32 . Здесь мы используем IndexFlatL2, который является простейшим точным поиском ближайшего соседа с евклидовым расстоянием (нормой L2), очень похожим на KNeighborsClassifier, используемый по умолчанию в Scikit-learn; Вы также можете использовать другие метрики (документы метрик) и типы индексов (документы индексов), например. грамм. для приблизительного поиска ближайшего соседа

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

индексы, возвращаемые .search(), представляют собой двумерную матрицу, где n-я строка содержит индексы k ближайших соседей; с self.y[indices] мы превращаем эти индексы в классы ближайших соседей, поэтому мы знаем голоса для каждой выборки

np.argmax(np.bincount(x)) возвращает наиболее популярное число из массива x, который является предсказанным классом; мы делаем это для каждой строки, т.е. е. для каждого образца, который мы должны классифицировать

Источник https://towardsdatascience.com/make-knn-300-times-faster-than-scikit-learns-in-20-lines-5e29d74e76bb