使用numpy的k最近邻分类器

我试图实现我自己的kNN分类器。我已经成功地实现了某些东西，但它是慢得令人难以置信......使用numpy的k最近邻分类器

def euclidean_distance(X_train, X_test): 
    """ 
    Create list of all euclidean distances between the given 
    feature vector and all other feature vectors in the training set 
    """ 
    return [np.linalg.norm(X - X_test) for X in X_train] 

def k_nearest(X, Y, k): 
    """ 
    Get the indices of the nearest feature vectors and return a 
    list of their classes 
    """ 
    idx = np.argpartition(X, k) 
    return np.take(Y, idx[:k]) 

def predict(X_test): 
    """ 
    For each feature vector get its predicted class 
    """ 
    distance_list = [euclidean_distance(X_train, X) for X in X_test] 
    return np.array([Counter(k_nearest(distances, Y_train, k)).most_common()[0][0] for distances in distance_list])

其中（例如）

X = [[ 1.96701284 6.05526865] 
    [ 1.43021202 9.17058291]] 

Y = [ 1. 0.]

显然，这将是更快，如果我没有使用任何的循环，但我不知道如何让它在没有它们的情况下工作。有没有办法可以做到这一点，而不使用循环/列表解析？

来源

2017-03-16 user5368737

什么'X_train'？ – Divakar

@Divakar将'X'分成训练集和测试集。想象一下，“X”实际上是200行'x，y'值，而不是2行。然后它被分成'X_train'和'X_test'。 – user5368737

这里有一个量化的方法 -

from scipy.spatial.distance import cdist 
from scipy.stats import mode 

dists = cdist(X_train, X) 
idx = np.argpartition(dists, k, axis=0)[:k] 
nearest_dists = np.take(Y_train, idx) 
out = mode(nearest_dists,axis=0)[0]

来源

2017-03-16 18:23:19 Divakar

我设法使用'spatial.KDTree'来实现它，而且速度肯定更快，但是当尝试这个[示例]（http://scikit-learn.org/stable/auto_examples/neighbors/plot_classification.html）时仍然需要40秒（之前是240秒）。我无法理解'sklearn'能在0.7秒内做到这一点？！ – user5368737

@ user5368737嗯，我不知道它的内部。但是如果我不得不猜测，我会说它可能不会计算所有的距离，然后抛出除了最接近的“k”之外的所有距离，就像我们在这里所做的那样。但是，是的，我已经看到'kDtree'与任何Python/Numpy实现相比都非常快速。 – Divakar

@ user5368737只是好奇而已 - 你是否通过任何改变来剖析所提出的代码，并查看哪一步在大数据集上占用最多时间？ – Divakar

使用numpy的k最近邻分类器

回答

相关问题