使用numpy实现k最近邻分类器

Question

我正在尝试实现自己的kNN分类器。我已经实现了一些东西，但速度非常慢...

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.]

显然，如果我不使用任何for循环，速度会更快，但是我不知道如何在没有它们的情况下使其工作。有没有一种方法可以在不使用for循环/列表推导的情况下完成这个任务？

- user5368737

---

X_train 是什么？ - Divakar

@Divakar，你将X分成了训练集和测试集。假设X实际上是200行的x, y值，而不仅仅是2个。然后将其分成X_train和X_test。 - user5368737

Answer 1

这里提供一种向量化方法 -

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]

- Divakar

---

我成功地使用了 spatial.KDTree 来实现它，速度明显更快，但是当尝试这个示例时，仍然需要40秒（之前是240秒）。我不明白为什么 sklearn 可以在0.7秒内完成这个任务？！ - user5368737

@user5368737，我不了解它的内部情况。但是如果我要猜测的话，我会说它可能不会计算所有距离，然后扔掉除最近的“k”个之外的所有距离，就像我们在这里做的一样。但是，我确实看到kDtree比任何Python/Numpy实现都要快得多。 - Divakar

@user5368737 只是好奇 - 你是否对建议的代码进行了分析，看看在更大的数据集上哪个步骤花费了最多的时间？ - Divakar

我没有使用你的代码，而是使用了spatial.KDTree写了我的代码。这里我的查询操作是这样的(X = Y_train[tree.query(X_test, k=k)[1]])，但由于X_train.shape = (268288, 2)，所以查询非常耗时间。不幸的是，我不知道如何让它更快...... - user5368737