Vectorised average K-Nearest Neighbour distance in Python

Question

This is a K-nearest neighbour algorithm for points in Rn that should calculate for each point its average distance to its k-nearest neighbours. The problem is that although it's, vectorised it's inefficient in the sense that I am repeating myself. I would be happy if somebody could help me improve this code: ``` import numpy as np from scipy.spatial.distance import pdist from scipy.spatial.distance import squareform def nn_args_R_n_squared(points): """Calculate pairwise distances of points and return the matrix together with matrix of indices of the first matrix sorted""" dist_mat=squareform(pdist(points,'sqeuclidean')) return dist_mat,np.argsort(dist_mat,axis=1) def knn_avg_dist(X,k): """Calculates for points in rows of X, the average distance of each, to their k-nearest neighbours""" X_dist_mat,X_sorted_arg=nn_args_R_n_squared(X) X_matrices=(X[X_sorted_arg[:,1:k+1]]-X[...,None,...]).astype(np.float64) return np.mean(np.linalg.norm(X_matrices,axis=2)**2,axis=1) X=np.random.randn(30).…

Accepted Answer

Use `scipy.spatial.cKDTree`:

```
>>> data = np.random.rand(1000, 3)
>>> import scipy.spatial

>>> kdt = scipy.spatial.cKDTree(data) 
>>> k = 5 # number of nearest neighbors 
>>> dists, neighs = kdt.query(data, k+1)
>>> avg_dists = np.mean(dists[:, 1:], axis=1)
```

Vectorised average K-Nearest Neighbour distance in Python

Solution

Problem