find.radius: Adaptive Radius Selection by Natural Neighbours
Description
Implements a Natural Neighbour search to adaptively determine a neighbourhood
radius \(r\) from a general distance matrix. The algorithm increases \(r\)
until the number of points with zero in-degree in the \(r\)-nearest-neighbour
graph no longer decreases, and returns this radius \(r\).
Usage
find.radius(D)
Value
A single integer \(r\), the selected neighbourhood radius.
Arguments
D
An \(n \times n\) numeric (symmetric) distance matrix.
Details
This procedure is adapted from the Natural Neighbor (NaN)
algorithm by Zhu, Feng and Huang (2016). The algorithm works as follows:
For each integer \(r\), build the directed \(r\)-nearest-neighbour graph from D.
Compute the in-degree counts, i.e., how many times each observation
appears among others' first \(r\) neighbours.
Track the number of zero in-degree points; if this number stops
decreasing when \(r\) increases, the algorithm stops and returns the
current \(r\), interpreted as the natural neighbour radius.
This provides a parameter-free way to adaptively set the neighbourhood size.
References
Zhu, Q., Feng, J., and J. Huang (2016). Natural neighbor: A self-adaptive neighborhood method without parameter K. Pattern recognition letters, 80, 30-36.
set.seed(1)
X <- matrix(rnorm(100), nrow = 20)
D <- as.matrix(dist(X))
r <- find.radius(D) # Estimate the natural neighbour radiusr
rNN.dist(D, r) # use selected r for rNN.dist