您如何针对 nn 预测优化此代码？

Question

你如何优化这段代码？目前，通过此循环的数据量运行很慢。此代码运行 1-最近邻。它将根据 p_data_set

预测 training_element 的标签

#               [x] ,           [[x1],[x2],[x3]],    [l1, l2, l3]
def prediction(training_element, p_data_set, p_label_set):
    temp = np.array([], dtype=float)
    for p in p_data_set:
        temp = np.append(temp, distance.euclidean(training_element, p))

    minIndex = np.argmin(temp)
    return p_label_set[minIndex]

Answer 1

你可以使用 distance.cdist 直接获取距离 temp 然后使用 .argmin() 获取最小索引，就像这样 -

minIndex = distance.cdist(training_element[None],p_data_set).argmin()

这是使用 np.einsum -

的替代方法

subs = p_data_set - training_element
minIndex =  np.einsum('ij,ij->i',subs,subs).argmin()

运行时测试

好吧，我认为 cKDTree 会轻松击败 cdist，但我想 training_element 作为 1D 数组对 cdist 来说并不太重我看到它以 10x+ 的优势击败了 cKDTree！

这是计时结果 -

In [422]: # Setup arrays
     ...: p_data_set = np.random.randint(0,9,(40000,100))
     ...: training_element = np.random.randint(0,9,(100,))
     ...: 

In [423]: def tree_based(p_data_set,training_element): #@ali_m's soln
     ...:     tree = cKDTree(p_data_set)
     ...:     dist, idx = tree.query(training_element, k=1)
     ...:     return idx
     ...: 
     ...: def einsum_based(p_data_set,training_element):    
     ...:     subs = p_data_set - training_element
     ...:     return np.einsum('ij,ij->i',subs,subs).argmin()
     ...: 

In [424]: %timeit tree_based(p_data_set,training_element)
1 loops, best of 3: 210 ms per loop

In [425]: %timeit einsum_based(p_data_set,training_element)
100 loops, best of 3: 17.3 ms per loop

In [426]: %timeit distance.cdist(training_element[None],p_data_set).argmin()
100 loops, best of 3: 14.8 ms per loop

Answer 2

使用 k-D tree for fast nearest-neighbour lookups, e.g. scipy.spatial.cKDTree:

from scipy.spatial import cKDTree

# I assume that p_data_set is (nsamples, ndims)
tree = cKDTree(p_data_set)

# training_elements is also assumed to be (nsamples, ndims)
dist, idx = tree.query(training_elements, k=1)

predicted_labels = p_label_set[idx]

Answer 3

如果使用得当，

Python 可以成为非常快速的编程语言。这是我的建议 (faster_prediction):

import numpy as np
import time

def euclidean(a,b):
    return np.linalg.norm(a-b)

def prediction(training_element, p_data_set, p_label_set):
    temp = np.array([], dtype=float)
    for p in p_data_set:
        temp = np.append(temp, euclidean(training_element, p))

    minIndex = np.argmin(temp)
    return p_label_set[minIndex]

def faster_prediction(training_element, p_data_set, p_label_set):    
    temp = np.tile(training_element, (p_data_set.shape[0],1))
    temp = np.sqrt(np.sum( (temp - p_data_set)**2 , 1))    

    minIndex = np.argmin(temp)
    return p_label_set[minIndex]   


training_element = [1,2,3]
p_data_set = np.random.rand(100000, 3)*10
p_label_set = np.r_[0:p_data_set.shape[0]]


t1 = time.time()
result_1 = prediction(training_element, p_data_set, p_label_set)
t2 = time.time()

t3 = time.time()
result_2 = faster_prediction(training_element, p_data_set, p_label_set)
t4 = time.time()


print "Execution time 1:", t2-t1, "value: ", result_1
print "Execution time 2:", t4-t3, "value: ", result_2
print "Speed up: ", (t4-t3) / (t2-t1)

我在相当旧的笔记本电脑上得到以下结果：

Execution time 1: 21.6033108234 value:  9819
Execution time 2: 0.0176379680634 value:  9819
Speed up:  1224.81857013

这让我觉得我一定是犯了一些愚蠢的错误:)

如果数据非常大，内存可能是个问题，我建议使用 Cython 或在 C++ 中实现函数并将其包装在 python。

您如何针对 nn 预测优化此代码？

How do you optimize this code for nn prediction?

python

performance

numpy

nearest-neighbor

scipy