mlpack (version 4.5.1)

kfn: k-Furthest-Neighbors Search

Description

An implementation of k-furthest-neighbor search using single-tree and dual-tree algorithms. Given a set of reference points and query points, this can find the k furthest neighbors in the reference set of each query point using trees; trees that are built can be saved for future use.

Usage

kfn(
  algorithm = NA,
  epsilon = NA,
  input_model = NA,
  k = NA,
  leaf_size = NA,
  percentage = NA,
  query = NA,
  random_basis = FALSE,
  reference = NA,
  seed = NA,
  tree_type = NA,
  true_distances = NA,
  true_neighbors = NA,
  verbose = getOption("mlpack.verbose", FALSE)
)

Value

A list with several components:

distances

Matrix to output distances into (numeric matrix).

neighbors

Matrix to output neighbors into (integer matrix).

output_model

If specified, the kFN model will be output here (KFNModel).

Arguments

algorithm

Type of neighbor search: 'naive', 'single_tree', 'dual_tree', 'greedy'. Default value "dual_tree" (character).

epsilon

If specified, will do approximate furthest neighbor search with given relative error. Must be in the range [0,1). Default value "0" (numeric).

input_model

Pre-trained kFN model (KFNModel).

k

Number of furthest neighbors to find. Default value "0" (integer).

leaf_size

Leaf size for tree building (used for kd-trees, vp trees, random projection trees, UB trees, R trees, R* trees, X trees, Hilbert R trees, R+ trees, R++ trees, and octrees). Default value "20" (integer).

percentage

If specified, will do approximate furthest neighbor search. Must be in the range (0,1] (decimal form). Resultant neighbors will be at least (p*100) Default value "1" (numeric).

query

Matrix containing query points (optional) (numeric matrix).

random_basis

Before tree-building, project the data onto a random orthogonal basis. Default value "FALSE" (logical).

reference

Matrix containing the reference dataset (numeric matrix).

seed

Random seed (if 0, std::time(NULL) is used). Default value "0" (integer).

tree_type

Type of tree to use: 'kd', 'vp', 'rp', 'max-rp', 'ub', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', 'r-plus-plus', 'oct'. Default value "kd" (character).

true_distances

Matrix of true distances to compute the effective error (average relative error) (it is printed when -v is specified) (numeric matrix).

true_neighbors

Matrix of true neighbors to compute the recall (it is printed when -v is specified) (integer matrix).

verbose

Display informational messages and the full list of parameters and timers at the end of execution. Default value "getOption("mlpack.verbose", FALSE)" (logical).

Author

mlpack developers

Details

This program will calculate the k-furthest-neighbors of a set of points. You may specify a separate set of reference points and query points, or just a reference set which will be used as both the reference and query set.

Examples

# For example, the following will calculate the 5 furthest neighbors of
# eachpoint in "input" and store the distances in "distances" and the
# neighbors in "neighbors": 

if (FALSE) {
output <- kfn(k=5, reference=input)
distances <- output$distances
neighbors <- output$neighbors
}

# The output files are organized such that row i and column j in the
# neighbors output matrix corresponds to the index of the point in the
# reference set which is the j'th furthest neighbor from the point in the
# query set with index i.  Row i and column j in the distances output file
# corresponds to the distance between those two points.