How do you optimize this code for nn prediction?
<p>How do you optimize this code?
At the moment it is running to slow for the amount of data that goes through this loop. This code runs 1-nearest neighbor. It will predict the label of the training_element based off the p_data_set</p>

<pre><code>#               [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]
</code></pre>

<p>You could use <a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html#scipy.spatial.distance.cdist" rel="nofollow"><code>distance.cdist</code></a> to directly get the distances <code>temp</code> and then use <code>.argmin()</code> to get min-index, like so -</p>

<pre><code>minIndex = distance.cdist(training_element[None],p_data_set).argmin()
</code></pre>

<p>Here's an alternative approach using <a href="http://docs.scipy.org/doc/numpy-1.10.4/reference/generated/numpy.einsum.html" rel="nofollow"><code>np.einsum</code></a> -</p>

<pre><code>subs = p_data_set - training_element
minIndex =  np.einsum('ij,ij-&gt;i',subs,subs).argmin()
</code></pre>

<p><strong>Runtime test</strong></p>

<p>Well I was thinking <code>cKDTree</code> would easily beat <code>cdist</code>, but I guess <code>training_element</code> being a <code>1D</code> array isn't too heavy for <code>cdist</code> and I am seeing it to beat out <code>cKDTree</code> instead by a good <strong><code>10x+</code></strong> margin! </p>

<p>Here's the timing results -</p>

<pre><code>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-&gt;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
</code></pre>

python performance numpy scipy nearest-neighbor