ml::BallTree Class Reference

Ball tree: an efficient tree structure for nearest-neighbour search in R^D space. More...

#include <BallTree.hpp>

Public Member Functions
	BallTree (Eigen::Ref< const Eigen::MatrixXd > X, unsigned int min_split_size)
	Constructor taking only features. More...
	BallTree (Eigen::Ref< const Eigen::MatrixXd > X, Eigen::Ref< const Eigen::VectorXd > y, unsigned int min_split_size)
	Constructor taking features and labels. More...
	BallTree (Eigen::MatrixXd &&X, unsigned int min_split_size)
	Constructor taking only features. More...
	BallTree (Eigen::MatrixXd &&X, Eigen::VectorXd &&y, unsigned int min_split_size)
	Constructor taking features and labels. More...
const Eigen::MatrixXd &	data () const
	Returns const reference to feature vectors (reordered).
const Eigen::VectorXd &	labels () const
	Returns const reference to labels (reordered).
void	find_k_nearest_neighbours (Eigen::Ref< const Eigen::VectorXd > x, unsigned int k, std::vector< unsigned int > &nn) const
	Finds up to k nearest neighbours for given target vector. Uses the KNS1 algorithm from http://people.ee.duke.edu/~lcarin/liu06a.pdf. More...
unsigned int	find_nearest_neighbour (Eigen::Ref< const Eigen::VectorXd > x) const
	Finds nearest neighbour for given target vector. Uses the KNS1 algorithm from http://people.ee.duke.edu/~lcarin/liu06a.pdf. More...
auto	size () const
	Size of the tree (number of vectors).
auto	dim () const
	Dimension of the feature vectors.

Detailed Description

Ball tree: an efficient tree structure for nearest-neighbour search in R^D space.

See https://en.wikipedia.org/wiki/Ball_tree and Omohundro, Stephen M. (1989) "Five Balltree Construction Algorithms".

Constructor & Destructor Documentation

BallTree() [1/4]

ml::BallTree::BallTree	(	Eigen::Ref< const Eigen::MatrixXd >	X,
		unsigned int	min_split_size
	)

Constructor taking only features.

Parameters

X	Feature matrix, with data points in columns. Copied internally.
min_split_size	Minimum number of points in the ball to consider splitting it into child balls.

Exceptions

std::invalid_argument

If min_split_size < 3.

BallTree() [2/4]

ml::BallTree::BallTree	(	Eigen::Ref< const Eigen::MatrixXd >	X,
		Eigen::Ref< const Eigen::VectorXd >	y,
		unsigned int	min_split_size
	)

Constructor taking features and labels.

Parameters

X	Feature matrix, with data points in columns. Copied internally.
y	Label vectors, with size equal to number of data points or empty. Copied internally.
min_split_size	Minimum number of points in the ball to consider splitting it into child balls.

Exceptions

std::invalid_argument

If min_split_size < 3 or y.size() != X.cols().

BallTree() [3/4]

ml::BallTree::BallTree	(	Eigen::MatrixXd &&	X,
		unsigned int	min_split_size
	)

Constructor taking only features.

Parameters

X	Feature matrix, with data points in columns. Moved.
min_split_size	Minimum number of points in the ball to consider splitting it into child balls.

Exceptions

std::invalid_argument

If min_split_size < 3.

BallTree() [4/4]

ml::BallTree::BallTree	(	Eigen::MatrixXd &&	X,
		Eigen::VectorXd &&	y,
		unsigned int	min_split_size
	)

Constructor taking features and labels.

Parameters

X	Feature matrix, with data points in columns. Moved.
y	Label vectors, with size equal to number of data points or empty. Moved.
min_split_size	Minimum number of points in the ball to consider splitting it into child balls.

Exceptions

std::invalid_argument

If min_split_size < 3 or y.size() != X.cols().

Member Function Documentation

find_k_nearest_neighbours()

void ml::BallTree::find_k_nearest_neighbours	(	Eigen::Ref< const Eigen::VectorXd >	x,
		unsigned int	k,
		std::vector< unsigned int > &	nn
	)		const

Finds up to k nearest neighbours for given target vector. Uses the KNS1 algorithm from http://people.ee.duke.edu/~lcarin/liu06a.pdf.

Parameters

[in]	x	Target vector.
[in]	k	Number of nearest neighbours.
[out]	nn	Upon return, has size min(k, size()) and contains the indices (in data()) of up to k nearest neighbours of x.

Exceptions

std::invalid_argument

If x.size() != #dim().

find_nearest_neighbour()

unsigned int ml::BallTree::find_nearest_neighbour

(

Eigen::Ref< const Eigen::VectorXd >

x

)

const

Finds nearest neighbour for given target vector. Uses the KNS1 algorithm from http://people.ee.duke.edu/~lcarin/liu06a.pdf.

Parameters

[in]

x

Target vector.

Returns

Index in data() of the nearest neighbour of x.

Exceptions

std::invalid_argument	If x.size() != #dim().
std::logic_error	If tree is empty.

---

The documentation for this class was generated from the following file:

• ML/BallTree.hpp