analyze_nn_euclidea​n_data

Clusters data (with optional initial outlier detection) based on shortest path distances of minimum spanning tree.

This function is designed to cluster location data. In such data, the quickest way between two points is not necessarily "as the crow flies" but is typically the shortest path along existing roads. In the case of a street grid oriented north/south and east/west, the shortest distance is the city-block distance, but for more complicated street layouts, the city-block distance may not be applicable.

This function assumes that the distance at least between close neighbors in reasonably dense regions of your dataset (less dense regions can be optionally removed with dbscan) will be a Euclidean distance (as such neighbors will likely be on the same street in a relatively straight stretch of that street). The method begins by constructing a minimum spanning tree for the data to identify all nearest neighbors. Distances are thus reconstructed using the shortest path for each pair of points through the minimum spanning tree. SAHN clustering (with choice of linkage) is then used with a distance based clustering cutoff (the user specifies the number of clusters to produce) to obtain the final clustering. This function optionally produces plots (with gscatter) to allow users to visualize the clustering at different steps.

This program was developed and tested (only) in MATLAB R2022b, but uses functions that should remain usable through the current version of MATLAB and which were first added in R2015b (or earlier). The only potential hiccup I see is that I do not know if the earlier (pre R2022a) version of gscatter will work as I call it in this function. It does require the Statistics and Machine Learning Toolbox, but that should be all (optional) toolbox-wise.