mst {nnclust} | R Documentation |
Minimum spanning tree by Prim's algorithm, using a fast
nearest-neighbour search to find candidate points. The variant
mst_restart
stops when the link length is greater than a
specified threshold.
mst(X, rebuild = sqrt(nrow(X))/4) mst_restart(X,rebuild=sqrt(nrow(X))/4,threshold=Inf,start=NULL)
X |
Matrix of data points |
rebuild |
How often to rebuild the k-d tree for nearest neighbour lookup. |
threshold |
Return when the next link is longer than this |
start |
Start here rather than at the first row of X |
from,to |
Row numbers of X for each link |
dist |
Squared length of link |
n |
For mst_restart only, the number of links added |
Thomas Lumley
Bentley JL, Friedman JH. "Fast algorithms for constructing minimal spanning trees in coordinate spaces" IEEE Transactions on Computers C27(2) Feb 1978
nncluster
for a wrapper for mst_restart
to do clustering.
x<-scale(faithful) a<-mst(x) plot(faithful) segments(faithful[a$from,1], faithful[a$from,2], faithful[a$to,1], faithful[a$to,2],col="blue") ## restarting plot(a$dist) a<-mst_restart(x,threshold=0.04,start=0) plot(faithful) segments(faithful[a$from,1], faithful[a$from,2], faithful[a$to,1], faithful[a$to,2],col="red") b<-mst_restart(x[-a$to,],threshold=0.04) ff<-faithful[-a$to,] segments(ff[b$from,1], ff[b$from,2], ff[b$to,1],ff[b$to,2],col="purple")