python - 为什么 'kd_tree' 比 'brute' 花费更多时间？

Question

我正在使用 sklearn 对 knn 进行基准测试。这是系统信息。

系统信息

• Intel(R) Xeon(R) L5640(6 核 12 个同级)；
• Ubuntu 18.04、Python 3.7.3、numpy 1.16.4、sklearn 0.21.2；
• 没有任何其他作业/任务占用 CPU 核心。

数据集

基准测试正在 sklearn MNIST 上运行，有 1797 个样本、10 个类、8*8 维和 17 个特征。

此示例图像中的每个方 block 代表一个像素，总共 8*8 维。每个像素的范围是 0 到 16。

代码

这是代码。

片段_1:

n_neighbors=5; n_jobs=1; algorithm = 'brute'
model = KNeighborsClassifier(n_neighbors=n_neighbors, n_jobs=n_jobs, algorithm = algorithm)
model.fit(trainData, trainLabels)
predictions = model.predict(testData)

大约需要0.1秒

片段_2:

n_neighbors=5; n_jobs=1; algorithm = 'kd_tree'
model = KNeighborsClassifier(n_neighbors=n_neighbors, n_jobs=n_jobs, algorithm = algorithm)
model.fit(trainData, trainLabels)
predictions = model.predict(testData)

大约需要0.2秒

我多次重复基准测试，无论我先运行哪一个，snippet_1 总是比 snippet_2 快 2 倍。

问题

为什么“kd_tree”比“brute”花费更多时间？

我知道“维数诅咒”，因为 doc说得很清楚，我问的是为什么？

Answer 1

答案似乎与模型相关的维度有关。维数诅咒也被称为维数诅咒。当涉及到 15/20(有点指数)以上的维度时，KD 树的扩展性非常差，而蛮力似乎遵循更线性的模式。当在 GPU 上运行时，对于更高的维度，暴力破解确实可以更快。另一位研究人员在这里发现了类似的问题:Comparison search time between K-D tree and Brute-force