如何提高knn算法的效率

Question

我要写一个函数，用knn算法对点进行分类。 因此，列车数据集最多有20000个点。我们必须将这个集合分成5个子集，并用k在1到200之间的算法对每个子集中的每个点进行分类 然后用最佳k值对5000点的测试数据集进行分类。 给出的数据最多可以有20个维度。 不允许使用python的kdtree或knn算法

我用了一个kd树来加速算法，但是它仍然需要10分钟 我尝试实现kd-tree迭代，但速度较慢。你知道吗

def kNN_search(x, k, node, level, sucher):
dim = x.shape[0]
r = level % dim
distance = np.linalg.norm(x - node.point[1:])

if node.point[0] >= k:
    for j in range(0, k):
        if distance >= sucher.best_distance[j]:
            if j == 0:
                break
            else:
                sucher.best_point[0:(j - 1), :] = sucher.best_point[1:j,      :]
                sucher.best_point[j - 1, :] = node.point

                sucher.best_distance[0:(j - 1)] = sucher.best_distance[1:j]
                sucher.best_distance[j - 1] = distance
                break
    if distance < sucher.best_distance[k - 1]:
        sucher.best_point[0:(k - 1), :] = sucher.best_point[1:k, :]
        sucher.best_point[k - 1, :] = node.point

        sucher.best_distance[0:(k - 1)] = sucher.best_distance[1:k]
        sucher.best_distance[k - 1] = distance
if x[r] <= node.point[r + 1]:  # Zuerst wird die Seite auf der x liegt untersucht
    if x[r] - sucher.best_distance[0] <= node.point[
                r + 1] and node.left != None:  # Aber nur falls überhaupt bessere Punkte in den jeweiligen Kasten liegen können
        kNN_search(x, k, node.left, level + 1, sucher)
    if x[r] + sucher.best_distance[0] > node.point[r + 1] and node.right != None:
        kNN_search(x, k, node.right, level + 1, sucher)
else:
    if x[r] + sucher.best_distance[0] > node.point[r + 1] and node.right != None:
        kNN_search(x, k, node.right, level + 1, sucher)
    if x[r] - sucher.best_distance[0] <= node.point[r + 1] and node.left != None:
        kNN_search(x, k, node.left, level + 1, sucher)

我需要更快的算法。如果有人有主意就好了