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 More... | |
| 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 More... | |
Protected Attributes | |
| kernel_type const * | mep_kernel |
| kernel function More... | |
| const_iterator | mep_positive |
| "positive" side cluster center More... | |
| const_iterator | mep_negative |
| "negative" side cluster center More... | |
| double | m_normalInvNorm |
| one divided by squared distance between "positive" and "negative" cluster center More... | |
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.
Member Typedef Documentation
◆ const_iterator
| typedef IndexedIterator<typename boost::range_iterator<Container const>::type> shark::KHCTree< Container, CuttingAccuracy >::const_iterator |
Constructor & Destructor Documentation
◆ KHCTree() [1/2]
|
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 88 of file KHCTree.h.
References shark::KHCTree< Container, CuttingAccuracy >::buildTree(), shark::BinaryTree< Container::value_type >::m_size, and shark::BinaryTree< Container::value_type >::mp_indexList.
◆ KHCTree() [2/2]
|
inlineprotected |
Member Function Documentation
◆ buildTree()
|
inlineprotected |
(internal) construction method: median-cuts of the dimension with widest spread
Definition at line 146 of file KHCTree.h.
References shark::KHCTree< Container, CuttingAccuracy >::calculateNormal(), shark::BinaryTree< Container::value_type >::m_nodes, shark::BinaryTree< Container::value_type >::m_size, shark::TreeConstruction::maxBucketSize(), and shark::TreeConstruction::maxDepth().
Referenced by shark::KHCTree< Container, CuttingAccuracy >::KHCTree().
◆ calculateNormal()
|
inlineprotected |
Definition at line 199 of file KHCTree.h.
References shark::batchSize(), shark::AbstractKernelFunction< InputTypeT >::featureDistanceSqr(), shark::KHCTree< Container, CuttingAccuracy >::m_normalInvNorm, shark::KHCTree< Container, CuttingAccuracy >::mep_kernel, shark::KHCTree< Container, CuttingAccuracy >::mep_negative, and shark::KHCTree< Container, CuttingAccuracy >::mep_positive.
Referenced by shark::KHCTree< Container, CuttingAccuracy >::buildTree().
◆ funct()
|
inlineprotected |
function describing the separating hyperplane
Definition at line 220 of file KHCTree.h.
References shark::AbstractKernelFunction< InputTypeT >::eval(), shark::KHCTree< Container, CuttingAccuracy >::m_normalInvNorm, shark::KHCTree< Container, CuttingAccuracy >::mep_kernel, shark::KHCTree< Container, CuttingAccuracy >::mep_negative, and shark::KHCTree< Container, CuttingAccuracy >::mep_positive.
◆ squaredDistanceLowerBound()
|
inline |
- Compute the squared distance of this cell to the given reference point, or alternatively a lower bound on this value.
Definition at line 112 of file KHCTree.h.
References shark::BinaryTree< InputT >::m_nodes, shark::BinaryTree< InputT >::m_size, shark::BinaryTree< InputT >::mep_parent, shark::BinaryTree< Container::value_type >::mep_parent, shark::BinaryTree< InputT >::mp_indexList, shark::BinaryTree< InputT >::mp_left, and shark::BinaryTree< InputT >::mp_right.
Member Data Documentation
◆ m_normalInvNorm
|
protected |
one divided by squared distance between "positive" and "negative" cluster center
Definition at line 237 of file KHCTree.h.
Referenced by shark::KHCTree< Container, CuttingAccuracy >::calculateNormal(), and shark::KHCTree< Container, CuttingAccuracy >::funct().
◆ mep_kernel
|
protected |
kernel function
Definition at line 228 of file KHCTree.h.
Referenced by shark::KHCTree< Container, CuttingAccuracy >::calculateNormal(), and shark::KHCTree< Container, CuttingAccuracy >::funct().
◆ mep_negative
|
protected |
"negative" side cluster center
Definition at line 234 of file KHCTree.h.
Referenced by shark::KHCTree< Container, CuttingAccuracy >::calculateNormal(), and shark::KHCTree< Container, CuttingAccuracy >::funct().
◆ mep_positive
|
protected |
"positive" side cluster center
Definition at line 231 of file KHCTree.h.
Referenced by shark::KHCTree< Container, CuttingAccuracy >::calculateNormal(), and shark::KHCTree< Container, CuttingAccuracy >::funct().
The documentation for this class was generated from the following file:
- include/shark/Models/Trees/KHCTree.h