This function generates a kNN graph based on a given numeric matrix. Seven different algorithms are implemented with different speed and accuracy trade-offs:
"hnsw"- Hierarchical Navigable Small Worlds vector search with slower index generation (which ammortises on larger data sets) and high precision."annoy"- Approximate Nearest Neighbours Oh Yeah algorithm, faster to index but querying on large data sets can be slow."nndescent"- Rust-based implementation of the PyNNDescent algorithm, a good all-rounder that performs well on very large data sets."balltree"- Ball tree structure for exact search with a configurable budget."ivf"- Inverted file index that leverages k-means clustering and probing a few of the clusters."exhaustive"- Exact nearest neighbour search."kmknn"- Fast exact nearest neighbour search using triangle inequality
Arguments
- data
Numeric matrix. The embedding or feature matrix to compute neighbours on. Rows are observations, columns are features.
- k
Integer. The number of nearest neighbours to compute.
- knn_method
Character. The algorithm to use for nearest neighbour search. One of
c("kmknn", "hnsw", "annoy", "nndescent", "balltree", "ivf", "exhaustive"). Defaults to"kmknn".- nn_params
List. Output of
params_nn(). Controls algorithm-specific parameters.- seed
Integer. For reproducibility. Defaults to
42L.- .verbose
Logical or integer
0Lto2L. Controls verbosity.
Value
A nearest neighbours class object with 1-indexed neighbour indices
and distances. Distances are on the scale of the metric they are named
after, so dist_metric = "euclidean" returns Euclidean distance, not the
squared Euclidean the backends sort on internally.
Examples
d <- manifold_synthetic_data(type = "clusters", n_samples = 500L)
knn <- generate_knn_graph(d$data, k = 15L, .verbose = FALSE)
knn
#> NearestNeighbours
#> n_samples: 500
#> k_neighbours: 15
