В настоящее время я внедряю дерево kd с нуля в python и применяю к нему алгоритм knn. Я построил дерево и у меня есть алгоритм для поиска 1-nn, но я не уверен, как его использовать, чтобы получить k-ближайших соседей. Я нахожу ближайших соседей, сравнивая каждый узел с правильным атрибутом, а затем перемещаясь вниз по соответствующему дочернему узлу / стороне узла. После завершения этого узла я делаю технику сокращения и выясняю, стоит ли смотреть на другого потомка узла, чтобы увидеть, получу ли я лучшее расстояние (более близкий сосед). Я прочитал в Интернете, что я могу просто сохранить k-лучшие расстояния в максимальную кучу, и тогда это даст мне k-ближайших соседей. Я реализовал это, но я обнаружил, что это некорректно, может быть, я делаю это неправильно. Это подводит меня к моему вопросу.
Скажем, мой k огромен, k = n, где n - количество элементов или узлов в дереве. Если я пройду дерево до ближайшего соседа и сохраню все лучшие расстояния на этом пути, мой алгоритм не будет проходить через все узлы дерева. Он выберет лучший путь, чтобы добраться до ближайшего узла, и при сокращении он будет пренебрегать узлами, поэтому он не сможет посещать k узлов, если k = n. Поэтому моя максимальная куча будет иметь только наилучшие расстояния из числа пройденных мною узлов, и я не смогу пройти через k узлов, поэтому у нее не будет k-ближайших соседей. Как мне бороться с этой проблемой? Или есть другой способ, я делаю что-то не так?
** Я знаю, что использование большого k с деревом kd не лучшая практика, но мне было поручено обеспечить точность всех k из k = 1 до k = n.