如何在Google colab或任何其他基于ipython的环境中使此KNN代码更快一些？

Question

我正在使用Google colaboratory对DonorsChoose数据集进行KNN分类。当我为avgw2v和tfidf数据集应用KNeighbors分类器时，以下代码需要大约4个小时才能执行。

我已经尝试过在kaggle笔记本上运行它，但问题仍然存在。

import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import roc_auc_score
train_auc_set3 = []
cv_auc_set3 = []
K = [51, 101]
for i in tqdm(K):
    neigh = KNeighborsClassifier(n_neighbors=i, n_jobs=-1)
    neigh.fit(X_tr_set3, y_train)

    y_train_set3_pred = batch_predict(neigh, X_tr_set3)    
    y_cv_set3_pred = batch_predict(neigh, X_cr_set3)        
    train_auc_set3.append(roc_auc_score(y_train,y_train_set3_pred))
    cv_auc_set3.append(roc_auc_score(y_cv, y_cv_set3_pred))

plt.plot(K, train_auc_set3, label='Train AUC')
plt.plot(K, cv_auc_set3, label='CV AUC')

plt.scatter(K, train_auc_set3, label='Train AUC points')
plt.scatter(K, cv_auc_set3, label='CV AUC points')

plt.legend()
plt.xlabel("K: hyperparameter")
plt.ylabel("AUC")
plt.title("ERROR PLOTS")
plt.grid()
plt.show()

Answer 1

这可能会很慢。我对这个数据集并不十分熟悉，但是在Kaggle上浏览了一下它，看起来它包含了超过400万个数据点。从KNN的sklearn页面：

对于每个迭代，时间复杂度为O（n_components x n_samples> x min（n_samples，n_features））。

还请记住，对于大型数据集，knn将必须测量给定数据点与训练集中所有数据点之间的距离以进行预测，这在计算上是昂贵的。

对于非常大的数据集在k上使用大数，您可能会得到非常差的性能。我可能会做的是：

1）看到用k的单个值拟合knn需要花费多少时间，并用k的单个值需要训练集进行预测。如果要花很长时间，那是我怀疑的问题。

不幸的是，有时对于非常大的数据集，我们选择算法的时间受到我们可能要使用的算法时间复杂性的限制。例如，内核岭回归是一种很棒的算法，由于需要找到具有三次时间复杂度的矩阵逆，因此无法很好地扩展到大型数据集。