我对编程还很陌生,我创建了一个函数来计算1 K最近邻居(KNN1)来进行预测。问题是,代码是如此缓慢,我无法在我真正需要的训练集上对其进行测试。我的训练集是1200 x 5600,其中有1200个数据点和5600个特征。我需要计算每一行中每个特征的平方差之和,然后选择最相似的另一行。以下代码需要HOURS,但尚未完成。我相信永远要紧的事情是距离循环(三重循环)。
我包括了来自sklearn IRIS数据集中的一小套训练集,用于测试。
[如果有人有任何建议来加快速度,以便我可以在合理的时间内测试我的其他代码,将不胜感激。
from sklearn.datasets import load_iris
import numpy as np
def l2_distance(row1, row2):
distance = 0.0
for i in range(len(row1)):
#print('row one: {}'.format(row1[i]))
#print('row two: {}'.format(row2[i]))
distance += (row1[i] - row2[i])**2
return sqrt(distance)
def KNN1(x, y):
# Create sum of square distances for each feature in each row
d_arr = []
for i in range(0,len(x)):
d_temp = []
for j in range(0,len(x)):
d = l2_distance(x[i], x[j])
d_temp.append(d)
d_arr.append(d_temp)
#del d_temp
# Find the index for the first NN
idx_arr = []
for i in range(0,len(d_arr)):
temp = list(d_arr[i])
m = min(j for j in temp if j > 0)
idx_arr.append(temp.index(m))
del temp
del d_arr
# Make a prediction based off the position in y_train for the test row
y_hat = []
for i in range(0,len(idx_arr)):
y_hat.append(float(y[idx_arr[i]]))
del idx_arr
y_hat = np.array(y_hat)
y_hat = np.reshape(y_hat,(len(y_hat),1))
a = np.where(y==y_hat, 1, 0)
accuracy = float(np.sum(a,axis=0)/float(len(a)))*100.0
return accuracy
iris = load_iris()
xtrain2 = iris.data[:, :2]
ytrain2 = (iris.target != 0) * 1
ytrain2 = np.reshape(ytrain2, (len(ytrain2),1))
acc = KNN1(xtrain2,ytrain2)
print('Accuracy for KNN (k=1) for the base dataset:\n\t{}\n'.format(acc))
如评论中所述,您需要考虑其他算法来加速KNN,例如球树(在具有大量特征的数据集上效果很好)或k-d树。算法的优化将使时间复杂度成倍降低。