KHC-tree, a binary space-partitioning tree. More...

#include <shark/Models/Trees/KHCTree.h>

Inheritance diagram for shark::KHCTree< Container, CuttingAccuracy >:

Public Types
typedef IndexedIterator< typename boost::range_iterator< Container const >::type >	const_iterator

Public Member Functions
	KHCTree (Container const &points, kernel_type const *kernel, TreeConstruction tc=TreeConstruction())

double	squaredDistanceLowerBound (value_type const &reference) const

Protected Member Functions
	KHCTree (KHCTree parent, std::size_t list, std::size_t size)
	(internal) construction of a non-root node

template<class Range >
void	buildTree (TreeConstruction tc, Range &points)

template<class Range >
void	calculateNormal (Range const &samples)

double	funct (value_type const &reference) const
	function describing the separating hyperplane

Protected Attributes
kernel_type const *	mep_kernel
	kernel function

const_iterator	mep_positive
	"positive" side cluster center

const_iterator	mep_negative
	"negative" side cluster center

double	m_normalInvNorm
	one divided by squared distance between "positive" and "negative" cluster center

BinaryTree *	mep_parent
	parent node

BinaryTree *	mp_left
	"left" child node

BinaryTree *	mp_right
	"right" child node

std::size_t *	mp_indexList
	list of indices to points in the dataset

std::size_t	m_size
	number of points in this node

std::size_t	m_nodes
	number of nodes in the sub-tree represented by this node

Detailed Description

template<class Container, int CuttingAccuracy = 25>
class shark::KHCTree< Container, CuttingAccuracy >

KHC-tree, a binary space-partitioning tree.

: KHC-tree data structure for efficient nearest neighbor searches in kernel-induced feature spaces. "KHC" stands for Kernel Hierarchical Clustering. The space separation is based on distances to cluster centers.

: The tree is constructed from data by splitting along the pair of data points with largest distance. This quantity is approximated using a given number of randomly sampled pairs, which is controlled by the template parameter CuttingAccuracy.

: The bucket size for the tree is always one, such that there is a unique point in each leaf cell.

Since the KHCTree needs direct access to the elements, it's template parameter is not the actual point type But the Range, the points are stored in. Be aware that this range should be a View when a Dataset is used as storage, since during construction, the KHC-Tree needs random access to the elements.

Definition at line 75 of file KHCTree.h.

Member Typedef Documentation

◆ const_iterator

template<class Container , int CuttingAccuracy = 25>

typedef IndexedIterator<typename boost::range_iterator<Container const>::type> shark::KHCTree< Container, CuttingAccuracy >::const_iterator

Definition at line 78 of file KHCTree.h.

Constructor & Destructor Documentation

◆ KHCTree() [1/2]

template<class Container , int CuttingAccuracy = 25>

shark::KHCTree< Container, CuttingAccuracy >::KHCTree	(	Container const &	points,
		kernel_type const *	kernel,
		TreeConstruction	tc = `TreeConstruction()`
	)

inline

Construct the tree from data. It is assumed that the container exceeds the lifetime of the KHCTree (which holds only references to the points), and that the memory locations of the points remain unchanged.

Definition at line 89 of file KHCTree.h.

References shark::KHCTree< Container, CuttingAccuracy >::buildTree(), shark::KHCTree< Container, CuttingAccuracy >::m_size, and shark::KHCTree< Container, CuttingAccuracy >::mp_indexList.