K-Ближайшие соседи находят все связи

Question

В настоящее время я использую sklearn для вычисления всех k-ближайших соседей из набора данных. Скажем, k = 10. Проблема, с которой я столкнулся, заключается в том, что sklearn вернет только 10 ближайших соседей и ни одну из других точек данных, которые могут связать 10-й ближайший сосед по расстоянию. Мне было интересно, есть ли эффективный способ найти какие-либо другие точки, которые могут связать k-го ближайшего соседа с точки зрения расстояния?

Answer 1

Теоретически, все точки в наборе могут быть связаны, что делает проблему другой. В самом деле, о K ближайших соседях можно сообщить за время O(Log N + K) при отсутствии связей, тогда как связи могут подразумевать K = O(N) принятие любого решения O(N).

На практике, если координаты целые, связи будут редким явлением, если только проблема не имеет специальной структуры. А в плавающей точке связи практически невозможны.

ИМО, обработка связей убьет эффективность, без пользы.