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

Question

KNN - это такой простой алгоритм, который легко реализовать:

# for each test datapoint in X_test:
#     calculate its distance from every points in X_train
#     find the top k most closest points  
#     take majority vote of the k neighbors and use that as prediction for this test data point

И все же я думаю, что сложность времени не достаточно хороша.Как оптимизируется алгоритм, когда он реализован в реальности?(например, какой трюк или структуру данных он использует?)

Answer 1

То, что вы описываете, является расчетом грубой силы kNN с O (size (X_test) * size (X_train) * d), где d - число измерений в векторах элементов.

Более эффективное использование решения пространственная индексация для помещения индекса в данные X_train.Как правило, это сокращает количество отдельных поисков до O (log (размер (X_train)) * d) или даже O (log (размер (X_train)) + d).

Общие пространственные индексы:

• кД-деревья (они часто используются, но плохо масштабируются с помощью 'd')
• R-деревья , такие как RStarTree
• Quadtrees (Обычно не эффективен для больших 'd', но, например, PH-Tree хорошо работает с d = 1000 и имеет отличные удалить /время вставки (отказ от ответственности, это моя собственная работа))
• BallTrees (я не очень много знаю о них)
• CoverTrees (Очень быстрый поиск для больших 'd', но длительное время наращивания

Есть также класс "приблизительных" NN поисков / запросов. Они корректно торгуют со скоростью, они могут пропустить несколькоБлижайшие соседи. Вы можете найти сравнение производительности и многочисленные реализации в python здесь .

Если вы ищете Java-реализации sКроме приведенных выше пространственных индексов, взгляните на моих реализаций .

Answer 2

Алгоритм k-ближайшего соседа отличается от других методов обучения тем, что из обучающих примеров не приводится никакой модели.Данные остаются такими, какие они есть;они просто хранятся в памяти.

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

вы также можете попробовать:

1. Повышение скорости k-NN за счет уменьшения количества обучающих документов
2. Улучшение k-NN за счет размера окрестности и функции подобия
3. Улучшение k-NN за счет расширенных структур хранения