Find approximate nearest neighbors
Description
This function builds an approximate nearest neighbors graph of the provided
data using convenient defaults. It does not return an index for later
querying, to speed the graph construction and reduce the size and complexity
of the return value.
Usage
rnnd_knn(
data,
k = 30,
metric = "euclidean",
use_alt_metric = TRUE,
init = "tree",
n_trees = NULL,
leaf_size = NULL,
max_tree_depth = 200,
margin = "auto",
n_iters = NULL,
delta = 0.001,
max_candidates = NULL,
weight_by_degree = FALSE,
low_memory = TRUE,
n_threads = 0,
verbose = FALSE,
progress = "bar",
obs = "R"
)
Arguments
data 
Matrix of n items to generate neighbors for, with observations
in the rows and features in the columns. Optionally, input can be passed
with observations in the columns, by setting obs = "C" , which should be
more efficient. Possible formats are base::data.frame() , base::matrix()
or Matrix::sparseMatrix() . Sparse matrices should be in dgCMatrix
format. Dataframes will be converted to numerical matrix format
internally, so if your data columns are logical and intended to be used
with the specialized binary metric s, you should convert it to a logical
matrix first (otherwise you will get the slower dense numerical version).

k 
Number of nearest neighbors to return. Optional if init is
specified.

metric 
Type of distance calculation to use. One of:

"braycurtis"

"canberra"

"chebyshev"

"correlation" (1 minus the Pearson correlation)

"cosine"

"dice"

"euclidean"

"hamming"

"hellinger"

"jaccard"

"jensenshannon"

"kulsinski"

"sqeuclidean" (squared Euclidean)

"manhattan"

"rogerstanimoto"

"russellrao"

"sokalmichener"

"sokalsneath"

"spearmanr" (1 minus the Spearman rank correlation)

"symmetrickl" (symmetric KullbackLeibler divergence)

"tsss" (Triangle Area SimilaritySector Area Similarity or TSSS
metric)

"yule"
For nonsparse data, the following variants are available with
preprocessing: this trades memory for a potential speed up during the
distance calculation. Some minor numerical differences should be expected
compared to the nonpreprocessed versions:
For nonsparse binary data passed as a logical matrix, the following
metrics have specialized variants which should be substantially faster than
the nonbinary variants (in other cases the logical data will be treated as
a dense numeric vector of 0s and 1s):

"dice"

"hamming"

"jaccard"

"kulsinski"

"matching"

"rogerstanimoto"

"russellrao"

"sokalmichener"

"sokalsneath"

"yule"

use_alt_metric 
If TRUE , use faster metrics that maintain the
ordering of distances internally (e.g. squared Euclidean distances if using
metric = "euclidean" ), then apply a correction at the end. Probably
the only reason to set this to FALSE is if you suspect that some
sort of numeric issue is occurring with your data in the alternative code
path.

init 
Name of the initialization strategy or initial data neighbor
graph to optimize. One of:

"rand" random initialization (the default).

"tree" use the random projection tree method of Dasgupta and Freund
(2008).
a precalculated neighbor graph. A list containing:

idx an n by k matrix containing the nearest neighbor indices.

dist (optional) an n by k matrix containing the nearest
neighbor distances. If the input distances are omitted, they will be
calculated for you.'
If k and init are specified as arguments to this function, and the
number of neighbors provided in init is not equal to k then:
if k is smaller, only the k closest values in init are retained.
if k is larger, then random neighbors will be chosen to fill init to
the size of k . Note that there is no checking if any of the random
neighbors are duplicates of what is already in init so effectively fewer
than k neighbors may be chosen for some observations under these
circumstances.

n_trees 
The number of trees to use in the RP forest. A larger number
will give more accurate results at the cost of a longer computation time.
The default of NULL means that the number is chosen based on the number
of observations in data . Only used if init = "tree" .

leaf_size 
The maximum number of items that can appear in a leaf. This
value should be chosen to match the expected number of neighbors you will
want to retrieve when running queries (e.g. if you want find 50 nearest
neighbors set leaf_size = 50 ) and should not be set to a value smaller
than 10 . Only used if init = "tree" .

max_tree_depth 
The maximum depth of the tree to build (default = 200).
If the maximum tree depth is exceeded then the leaf size of a tree may
exceed leaf_size which can result in a large number of neighbor distances
being calculated. If verbose = TRUE a message will be logged to indicate
that the leaf size is large. However, increasing the max_tree_depth may
not help: it may be that there is something unusual about the distribution
of your data set under your chose metric that makes a treebased
initialization inappropriate. Only used if init = "tree" .

margin 
A character string specifying the method used to assign points
to one side of the hyperplane or the other. Possible values are:

"explicit" categorizes all distance metrics as either Euclidean or
Angular (Euclidean after normalization), explicitly calculates a hyperplane
and offset, and then calculates the margin based on the dot product with
the hyperplane.

"implicit" calculates the distance from a point to each of the
points defining the normal vector. The margin is calculated by comparing the
two distances: the point is assigned to the side of the hyperplane that
the normal vector point with the closest distance belongs to.

"auto" (the default) picks the margin method depending on whether a
binaryspecific metric such as "bhammming" is chosen, in which case
"implicit" is used, and "explicit" otherwise: binaryspecific metrics
involve storing the data in a way that isn't very efficient for the
"explicit" method and the binaryspecific metric is usually a lot faster
than the generic equivalent such that the cost of two distance calculations
for the margin method is still faster.
Only used if init = "tree" .

n_iters 
Number of iterations of nearest neighbor descent to carry out.
By default, this will be chosen based on the number of observations in
data .

delta 
The minimum relative change in the neighbor graph allowed before
early stopping. Should be a value between 0 and 1. The smaller the value,
the smaller the amount of progress between iterations is allowed. Default
value of 0.001 means that at least 0.1% of the neighbor graph must
be updated at each iteration.

max_candidates 
Maximum number of candidate neighbors to try for each
item in each iteration. Use relative to k to emulate the "rho"
sampling parameter in the nearest neighbor descent paper. By default, this
is set to k or 60 , whichever is smaller.

weight_by_degree 
If TRUE , then candidates for the local join are
weighted according to their indegree, so that if there are more than
max_candidates in a candidate list, candidates with a smaller degree are
favored for retention. This prevents items with large numbers of edges
crowding out other items and for highdimensional data is likely to provide
a small improvement in accuracy. Because this incurs a small extra cost of
counting the degree of each node, and because it tends to delay early
convergence, by default this is FALSE .

low_memory 
If TRUE , use a lower memory, but more
computationally expensive approach to index construction. If set to
FALSE , you should see a noticeable speed improvement, especially when
using a smaller number of threads, so this is worth trying if you have the
memory to spare.

n_threads 
Number of threads to use.

verbose 
If TRUE , log information to the console.

progress 
Determines the type of progress information logged during the
nearest neighbor descent stage when verbose = TRUE . Options are:

obs 
set to "C" to indicate that the input data orientation stores
each observation as a column. The default "R" means that observations are
stored in each row. Storing the data by row is usually more convenient, but
internally your data will be converted to column storage. Passing it
already columnoriented will save some memory and (a small amount of) CPU
usage.

Details
The process of knearest neighbor graph construction using Random Projection
Forests (Dasgupta and Freund, 2008) for initialization and Nearest Neighbor
Descent (Dong and coworkers, 2011) for refinement. If you are sure you will
not want to query new data then compared to rnnd_build()
this function has
the advantage of not storing the index, which can be very large.
Value
the approximate nearest neighbor index, a list containing:
References
Dasgupta, S., & Freund, Y. (2008, May).
Random projection trees and low dimensional manifolds.
In Proceedings of the fortieth annual ACM symposium on Theory of computing
(pp. 537546).
\Sexpr[results=rd]{tools:::Rd_expr_doi("10.1145/1374376.1374452")}.
Dong, W., Moses, C., & Li, K. (2011, March).
Efficient knearest neighbor graph construction for generic similarity measures.
In Proceedings of the 20th international conference on World Wide Web
(pp. 577586).
ACM.
\Sexpr[results=rd]{tools:::Rd_expr_doi("10.1145/1963405.1963487")}.
See Also
rnnd_build()
, rnnd_query()
Examples
# Find 4 (approximate) nearest neighbors using Euclidean distance
iris_knn < rnnd_knn(iris, k = 4)