为什么自定义度量的KNN很慢

Question

我处理的数据集包含大约200k个对象。每个对象都有4个特征。用欧氏度规对它们进行K近邻(KNN)分类。进程大约在20秒内完成。

最近我有一个使用自定义指标的理由。可能会有更好的结果。我已经实现了自定义度量，KNN的工作时间已经超过了一个小时。我没有等到它完成。

我认为这个问题的一个原因是我的度量标准。我用return 1代替我的代码。KNN仍然工作了一个多小时。我假设一个原因是算法球树，但KNN与它和欧几里得度量在大约20秒内工作。

现在我不知道怎么了。我使用Python 3和sklearn 0.17.1。这里的流程不能用自定义度量完成。我也尝试了算法brute，但它有同样的效果。scikit-learn升级和降级没有影响。在Python 2上通过自定义度量实现分类也没有积极的影响。我在Cython上实现了这个度量(只返回1)，它有同样的效果。

def custom_metric(x: np.ndarray, y: np.ndarray) -> float:
    return 1
clf = KNeighborsClassifier(n_jobs=1, metric=custom_metric)
clf.fit(X, Y)

我可以使用自定义度量来提高KNN的分类过程吗?

对不起，如果我的英语不清楚

Answer 1

Sklearn经过优化，并使用cython和几个进程尽可能快地运行。编写纯python代码，特别是当它被多次调用时，是导致代码变慢的原因。我建议您使用cython编写自定义度量。这里有一个教程可以参考:https://blog.sicara.com/https-medium-com-redaboumahdi-speed-sklearn-algorithms-custom-metrics-using-cython-de92e5a325c

Answer 2

正如@ r da Boumahdi正确指出的那样，原因是使用了python定义的自定义度量。这是这里讨论的一个已知问题。在讨论结束时，它以"wontfix"结束。因此，建议的唯一解决方案是在python中编写自定义度量，以避免GIL在使用python度量时变慢。

Answer 3

1. 您可以使用numba。它提供了比cython更快的运行时间(很可能是因为我不太了解cython，这是零努力)
为什么KNN默认这么快?因为它使用KD-tree。然而，由于某些原因，我们不能将KD-tree与自定义度量一起使用，所以它选择了暴力方法。我试着手动设置，但没有用。但是'ball-tree'工作得很好，而且它使算法更快。

我使用了一个具有~5k训练行、~20个特征和~1k行用于推理(验证)的数据集。我比较了以下内容:

1. scipy correlation函数https://github.com/scipy/scipy/blob/v1.10.0/scipy/spatial/distance.py#L577-L624

2. numba:

import numba
from numba import jit
@jit(nopython=True)
def corr_numba(u,v):
    umu = np.average(u)
    vmu = np.average(v)
    u = u - umu
    v = v - vmu
    uv = np.average(u*v)
    uu = np.average(np.square(u))
    vv = np.average(np.square(v))
    dist = 1.0 - uv / np.sqrt(uu*vv)
    return dist
corr_numba(np.array([0,1,1]), np.array([1,0,0])) # 2.0

cython(我没有尝试优化它，所以它不是最好的版本可能)

%%cython --annotate
import numpy as np
from libc.math cimport sin, cos, acos, exp, sqrt, fabs, M_PI
def corr(double[:] u, double[:] v):
    cdef u_sum = 0
    cdef v_sum = 0
    cdef uv_sum = 0
    cdef uu_sum = 0
    cdef vv_sum = 0
    cdef n_elems = u.shape[0]
    
    
    for i in range(n_elems):
        u_sum += u[i]
        v_sum += v[i]
        
    u_sum = u_sum / n_elems
    v_sum = v_sum / n_elems
    
    for i in range(n_elems):
        uv_sum += (u[i]-u_sum)*(v[i]-v_sum)
        uu_sum += (u[i]-u_sum)*(u[i]-u_sum)
        vv_sum += (v[i]-v_sum)*(v[i]-v_sum)
        
    uv_sum = uv_sum / n_elems
    vv_sum = vv_sum / n_elems
    uu_sum = uu_sum / n_elems
    
    dist = 1.0 - uv_sum / sqrt(uu_sum*vv_sum)
    return dist
corr(np.array([0.,1,1]), np.array([1.,0,0])) # 2.0

结果:

1. no ball tree:

metric <function correlation at 0x7f8b2373d7e0> 0.934, train_time: 0.001, infer_time: 182.970
metric CPUDispatcher(<function corr_numba at 0x7f8b1a028af0>) 0.934, train_time: 0.001, infer_time: 6.239
metric <built-in function corr> 0.934, train_time: 0.001, infer_time: 32.485

球树

metric <function correlation at 0x7f8b2373d7e0> 0.935, train_time: 1.252, infer_time: 80.716
metric CPUDispatcher(<function corr_numba at 0x7f8b1a028af0>) 0.935, train_time: 0.049, infer_time: 2.336
metric <built-in function corr> 0.935, train_time: 0.249, infer_time: 12.725