This function finds all k nearest neighbors in a data matrix (including distances).
Usage
kNN(
x,
k,
query = NULL,
sort = TRUE,
search = "kdtree",
bucketSize = 10,
splitRule = "suggest",
shrinkRule = "suggest",
approx = 0
)
# S3 method for class 'kNN'
sort(x, decreasing = FALSE, ...)
# S3 method for class 'kNN'
adjacencylist(x, ...)
# S3 method for class 'kNN'
print(x, ...)Arguments
- x
a numeric data matrix (or data.frame), a dist object or a kNN object.
- k
number of neighbors to find.
- query
a data matrix with the points to query. If query is not specified, the NN for all the points in
xis returned. If query is specified thenxneeds to be a data matrix.- sort
sort the neighbors of each point by distance (ties are broken by id)?
sort = FALSEskips this step and returns the neighbors in the order found by the search, which is faster. kNN objects can be sorted later usingsort().- search
nearest neighbor search strategy (one of
"kdtree","linear","dist"or"bdtree"). See the section on the search parameters.- bucketSize
max size of the k-d or bd tree leafs.
- splitRule
rule to split the k-d or bd tree. One of
"std","midpt","fair","sl_midpt","sl_fair"or"suggest"(SL stands for sliding). The default value"suggest"uses ANNs best guess.- shrinkRule
shrinking rule used to build the box-decomposition tree (only used for
search = "bdtree"). One of"none"(no shrinking, equivalent to a k-d tree),"simple","centroid"or"suggest". The default value"suggest"uses ANNs best guess.- approx
approximation factor for the tree-based searches. The j-th neighbor found is at most
(1 + approx)times as far away as the true j-th nearest neighbor.0(default) gives exact results; larger values are faster, but some true nearest neighbors may be omitted. Ignored bysearch = "linear"and"dist".- decreasing
for
sort(), sort the neighbors by decreasing distance instead of increasing distance?- ...
further arguments (ignored).
Value
An object of class kNN (subclass of NN) containing a
list with the following components:
- dist
a matrix with distances (one row per point in
xorquery, one column per neighbor).- id
a matrix with the row numbers in
xof the neighbors.- k
number
kused.- sort
logical; are the neighbors in each row sorted by increasing distance (with ties broken by id)?
- metric
used distance metric. This is
"euclidean"for data matrices. For a dist object, it is the method stored in the object (which can beNULL).
Details
To speed up k nearest neighbors, a k-d tree is used for data matrices by default. Box-decomposition trees, linear search, and precomputing distance matrices are also available.
Using a kNN object as x
If x is a kNN object, then the first k neighbors are returned
(sorted by distance). All other arguments are ignored. An error is
raised if x contains fewer than k neighbors.
Sorting, ties and self-matches
Sorting: With
sort = TRUE(default), the neighbors of each point are ordered by distance and ties are broken by id. Withsort = FALSE, the neighbors are returned in the order found by the search (the tree-based searches return them by increasing distance, but tied neighbors are not ordered by id), which avoids the cost of sorting. AkNNobject can be sorted later usingsort().Ties: If the kth and the (k+1)th nearest neighbor are tied, then the neighbor found first is returned and the other one is ignored.
Self-matches: If no
queryis specified, then self-matches are removed. Ifqueryis specified, then a query point that is also inxis returned as its own nearest neighbor (at distance 0).
Input requirements
xcan be a numeric matrix, a data.frame with only numeric columns, a dist object or akNNobject.queryneeds to be a numeric matrix or data.frame with the same number of columns asx, and can only be used ifxis a data matrix.kneeds to be a whole number with1 <= k < nrow(x).
Non-Euclidean distances
To use non-Euclidean distances, a distance matrix needs to be precomputed
by the user and supplied as x. Note that this leads to restrictions
of the number of observations that can be used since the distance
matrix grows with \(O(n^2)\).
Details on the search parameters:
searchcontrols what method is used ifxis a data matrix. Available methods are:"kdtree"uses a Euclidean k-d tree to speed up NN search. This is the default with good overall performance."bdtree"uses a box-decomposition tree. Its spatial boxes can, in addition to splitting, also shrink. According to the ANN authors, this tree type may be faster than a k-d tree on tightly clustered data."linear"performs linear search directly on the data."dist"precomputes Euclidean distances first usingdist(). While fast for small data sets, the memory requirements for the distance matrix grow with \(O(n^2)\).
The trees and linear search use the highly optimized ANN library (Mount and Arya, 2010) for Euclidean distances.
If
xis a distance matrix, thensearchis ignored and"dist"is used.Tree specific parameters
bucketSize,splitRuleandshrinkRulecontrol how the tree is built.bucketSizeandsplitRuleapply to k-d and bd trees;shrinkRuleapplies only to bd trees ("none"gives a tree that behaves like a k-d tree).approxuses the approximate nearest neighbor search implemented in ANN. Ifapprox > 0, the distance to the j-th returned neighbor is at most(1 + approx)times the distance to the true j-th nearest neighbor, so some true nearest neighbors may be omitted. This can lead to a significant speedup. The defaultapprox = 0gives exact results.approxis only used by the tree-based searches. For more details see Mount and Arya (2010).
Handling of NAs:
The tree-based searches and search = "linear" cannot handle NA, NaN or
infinite values in the data (in x or query); an error is raised. (The ANN
library does not check its input and would silently return wrong results.)
With search = "dist", the distances are calculated by dist(), which
leaves out coordinates that are NA for a pair of points and scales up
the remaining sum. These distances are not exactly Euclidean distances.
The resulting distance matrix (and a dist object supplied as x)
cannot contain NAs, which happens, for example, if a point has only
NA values. Otherwise, remove or impute missing values before
performing the search.
References
David M. Mount and Sunil Arya (2010). ANN: A Library for Approximate Nearest Neighbor Searching, https://www.cs.umd.edu/~mount/ANN/.
Examples
data(iris)
x <- iris[, -5]
# Example 1: finding kNN for all points in a data matrix (using a k-d tree)
nn <- kNN(x, k = 5)
nn
#> k-nearest neighbors for 150 objects (k=5).
#> Distance metric: euclidean
#>
#> Available fields: dist, id, k, sort, metric
# explore neighborhood of point 10
i <- 10
nn$id[i,]
#> 1 2 3 4 5
#> 35 2 31 13 26
plot(x, col = ifelse(seq_len(nrow(iris)) %in% nn$id[i,], "red", "black"))
# visualize the 5 nearest neighbors
plot(nn, x)
# visualize a reduced 2-NN graph
plot(kNN(nn, k = 2), x)
# Example 2: find kNN for query points
q <- x[c(1,100),]
nn <- kNN(x, k = 10, query = q)
# we plot the first two features for iris
plot(nn, x[, 1:2], col = "grey")
points(q, pch = 3, lwd = 2)
# Example 3: find kNN using a precomputed (non-Euclidean) distance matrix
d <- dist(x, method = "manhattan")
nn <- kNN(d, k = 1)
plot(nn, x)