improve linear search for KNN efficiency w/ NumPY
<p>I am trying to calculate the distance of each point in the testing set from each point in the training set:</p>

<p>This is what my loop looks like right now:</p>

<pre><code> for x in testingSet
    for y in trainingSet
        print numpy.linalg.norm(x-y)
</code></pre>

<p>Where testingSet and trainingSet are numpy arrays where each row of the two sets hold the feature data for one example.</p>

<p>However, it's running extremely slowly, taking more than 10 minutes since my data set is bigger (testing set of 3000, training set of ~10,000). Does this have to do with my method or am I utilizing numPY incorrectly?</p>

<p>This is because you naively iterate over your data, and loops are slow in python. Instead, use sklearn <a href="http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.pairwise_distances.html" rel="nofollow">pairwise distance functions</a>, or even better - use sklearn <a href="http://scikit-learn.org/stable/modules/neighbors.html" rel="nofollow">efficient nearest neighbour</a> search (like BallTree or KDTree). If you do not want to use sklearn, there is also a <a href="http://docs.scipy.org/doc/scipy/reference/spatial.distance.html" rel="nofollow">module in scipy</a>. Finally you can do "matrix tricks" to compute this, since</p>

<pre><code>|| x - y ||^2 = &lt;x-y, x-y&gt; = &lt;x,x&gt; + &lt;y,y&gt; - 2&lt;x,y&gt;
</code></pre>

<p>you can do (assuming your data is in matrix form given as X and Y):</p>

<pre><code>X2 = (X**2).sum(axis=1).reshape((-1, 1))
Y2 = (Y**2).sum(axis=1).reshape((1, -1))
distances = np.sqrt(X2 + Y2 - 2*X.dot(Y.T))
</code></pre>

python numpy machine-learning