mlpack
2.2.5

Trees and treebuilding procedures. More...
Namespaces  
split  
Classes  
class  AllCategoricalSplit 
The AllCategoricalSplit is a splitting function that will split categorical features into many children: one child for each category. More...  
class  AxisParallelProjVector 
AxisParallelProjVector defines an axisparallel projection vector. More...  
class  BestBinaryNumericSplit 
The BestBinaryNumericSplit is a splitting function for decision trees that will exhaustively search a numeric dimension for the best binary split. More...  
class  BinaryNumericSplit 
The BinaryNumericSplit class implements the numeric feature splitting strategy devised by Gama, Rocha, and Medas in the following paper: More...  
class  BinaryNumericSplitInfo 
class  BinarySpaceTree 
A binary space partitioning tree, such as a KDtree or a ball tree. More...  
class  CategoricalSplitInfo 
class  CompareCosineNode 
class  CosineTree 
class  CoverTree 
A cover tree is a tree specifically designed to speed up nearestneighbor computation in highdimensional spaces. More...  
class  DecisionTree 
This class implements a generic decision tree learner. More...  
class  DiscreteHilbertValue 
The DiscreteHilbertValue class stores Hilbert values for all of the points in a RectangleTree node, and calculates Hilbert values for new points. More...  
class  EmptyStatistic 
Empty statistic if you are not interested in storing statistics in your tree. More...  
class  ExampleTree 
This is not an actual space tree but instead an example tree that exists to show and document all the functions that mlpack trees must implement. More...  
class  FirstPointIsRoot 
This class is meant to be used as a choice for the policy class RootPointPolicy of the CoverTree class. More...  
class  GiniGain 
The Gini gain, a measure of set purity usable as a fitness function (FitnessFunction) for decision trees. More...  
class  GiniImpurity 
class  GreedySingleTreeTraverser 
class  HilbertRTreeAuxiliaryInformation 
class  HilbertRTreeDescentHeuristic 
This class chooses the best child of a node in a Hilbert R tree when inserting a new point. More...  
class  HilbertRTreeSplit 
The splitting procedure for the Hilbert R tree. More...  
class  HoeffdingCategoricalSplit 
This is the standard Hoeffdingbound categorical feature proposed in the paper below: More...  
class  HoeffdingNumericSplit 
The HoeffdingNumericSplit class implements the numeric feature splitting strategy alluded to by Domingos and Hulten in the following paper: More...  
class  HoeffdingTree 
The HoeffdingTree object represents all of the necessary information for a Hoeffdingboundbased decision tree. More...  
class  HyperplaneBase 
HyperplaneBase defines a splitting hyperplane based on a projection vector and projection value. More...  
class  InformationGain 
The standard information gain criterion, used for calculating gain in decision trees. More...  
struct  IsSpillTree 
struct  IsSpillTree< tree::SpillTree< MetricType, StatisticType, MatType, HyperplaneType, SplitType > > 
class  MeanSpaceSplit 
class  MeanSplit 
A binary space partitioning tree node is split into its left and right child. More...  
class  MidpointSpaceSplit 
class  MidpointSplit 
A binary space partitioning tree node is split into its left and right child. More...  
class  MinimalCoverageSweep 
The MinimalCoverageSweep class finds a partition along which we can split a node according to the coverage of two resulting nodes. More...  
class  MinimalSplitsNumberSweep 
The MinimalSplitsNumberSweep class finds a partition along which we can split a node according to the number of required splits of the node. More...  
class  NoAuxiliaryInformation 
class  NumericSplitInfo 
class  Octree 
class  ProjVector 
ProjVector defines a general projection vector (not necessarily axisparallel). More...  
struct  QueueFrame 
class  RectangleTree 
A rectangle type tree tree, such as an Rtree or Xtree. More...  
class  RPlusPlusTreeAuxiliaryInformation 
class  RPlusPlusTreeDescentHeuristic 
class  RPlusPlusTreeSplitPolicy 
The RPlusPlusTreeSplitPolicy helps to determine the subtree into which we should insert a child of an intermediate node that is being split. More...  
class  RPlusTreeDescentHeuristic 
class  RPlusTreeSplit 
The RPlusTreeSplit class performs the split process of a node on overflow. More...  
class  RPlusTreeSplitPolicy 
The RPlusPlusTreeSplitPolicy helps to determine the subtree into which we should insert a child of an intermediate node that is being split. More...  
class  RPTreeMaxSplit 
This class splits a node by a random hyperplane. More...  
class  RPTreeMeanSplit 
This class splits a binary space tree. More...  
class  RStarTreeDescentHeuristic 
When descending a RectangleTree to insert a point, we need to have a way to choose a child node when the point isn't enclosed by any of them. More...  
class  RStarTreeSplit 
A Rectangle Tree has new points inserted at the bottom. More...  
class  RTreeDescentHeuristic 
When descending a RectangleTree to insert a point, we need to have a way to choose a child node when the point isn't enclosed by any of them. More...  
class  RTreeSplit 
A Rectangle Tree has new points inserted at the bottom. More...  
class  SpaceSplit 
class  SpillTree 
A hybrid spill tree is a variant of binary space trees in which the children of a node can "spill over" each other, and contain shared datapoints. More...  
class  TraversalInfo 
The TraversalInfo class holds traversal information which is used in dualtree (and singletree) traversals. More...  
class  TreeTraits 
The TreeTraits class provides compiletime information on the characteristics of a given tree type. More...  
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, bound::BallBound, SplitType > > 
This is a specialization of the TreeType class to the BallTree tree type. More...  
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, bound::CellBound, SplitType > > 
This is a specialization of the TreeType class to the UBTree tree type. More...  
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, bound::HollowBallBound, SplitType > > 
This is a specialization of the TreeType class to an arbitrary tree with HollowBallBound (currently only the vantage point tree is supported). More...  
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, BoundType, RPTreeMaxSplit > > 
This is a specialization of the TreeType class to the maxsplit random projection tree. More...  
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, BoundType, RPTreeMeanSplit > > 
This is a specialization of the TreeType class to the meansplit random projection tree. More...  
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, BoundType, SplitType > > 
This is a specialization of the TreeTraits class to the BinarySpaceTree tree type. More...  
class  TreeTraits< CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > > 
The specialization of the TreeTraits class for the CoverTree tree type. More...  
class  TreeTraits< Octree< MetricType, StatisticType, MatType > > 
This is a specialization of the TreeTraits class to the Octree tree type. More...  
class  TreeTraits< RectangleTree< MetricType, StatisticType, MatType, RPlusTreeSplit< SplitPolicyType, SweepType >, DescentType, AuxiliaryInformationType > > 
Since the R+/R++ tree can not have overlapping children, we should define traits for the R+/R++ tree. More...  
class  TreeTraits< RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > > 
This is a specialization of the TreeType class to the RectangleTree tree type. More...  
class  TreeTraits< SpillTree< MetricType, StatisticType, MatType, HyperplaneType, SplitType > > 
This is a specialization of the TreeType class to the SpillTree tree type. More...  
class  UBTreeSplit 
Split a node into two parts according to the median address of points contained in the node. More...  
class  VantagePointSplit 
The class splits a binary space partitioning tree node according to the median distance to the vantage point. More...  
class  XTreeAuxiliaryInformation 
The XTreeAuxiliaryInformation class provides information specific to X trees for each node in a RectangleTree. More...  
class  XTreeSplit 
A Rectangle Tree has new points inserted at the bottom. More...  
Typedefs  
template < typename MetricType >  
using  AxisOrthogonalHyperplane = HyperplaneBase< bound::HRectBound< MetricType >, AxisParallelProjVector > 
AxisOrthogonalHyperplane represents a hyperplane orthogonal to an axis. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  BallTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::BallBound, MidpointSplit > 
A midpointsplit ball tree. More...  
template < typename FitnessFunction >  
using  BinaryDoubleNumericSplit = BinaryNumericSplit< FitnessFunction, double > 
typedef boost::heap::priority_queue< CosineTree *, boost::heap::compare< CompareCosineNode > >  CosineNodeQueue 
template < typename FitnessFunction = GiniGain , template < typename > class NumericSplitType = BestBinaryNumericSplit , template < typename > class CategoricalSplitType = AllCategoricalSplit , typename ElemType = double >  
using  DecisionStump = DecisionTree< FitnessFunction, NumericSplitType, CategoricalSplitType, ElemType, false > 
Convenience typedef for decision stumps (single level decision trees). More...  
template < typename TreeType >  
using  DiscreteHilbertRTreeAuxiliaryInformation = HilbertRTreeAuxiliaryInformation< TreeType, DiscreteHilbertValue > 
The Hilbert Rtree, a variant of the R tree with an ordering along the Hilbert curve. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  HilbertRTree = RectangleTree< MetricType, StatisticType, MatType, HilbertRTreeSplit< 2 >, HilbertRTreeDescentHeuristic, DiscreteHilbertRTreeAuxiliaryInformation > 
template < typename FitnessFunction >  
using  HoeffdingDoubleNumericSplit = HoeffdingNumericSplit< FitnessFunction, double > 
Convenience typedef. More...  
typedef StreamingDecisionTree< HoeffdingTree<> >  HoeffdingTreeType 
template < typename MetricType >  
using  Hyperplane = HyperplaneBase< bound::BallBound< MetricType >, ProjVector > 
Hyperplane represents a general hyperplane (not necessarily axisorthogonal). More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  KDTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit > 
The standard midpointsplit kdtree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  MaxRPTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, RPTreeMaxSplit > 
A maxsplit random projection tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  MeanSplitBallTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::BallBound, MeanSplit > 
A meansplit ball tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  MeanSplitKDTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MeanSplit > 
A meansplit kdtree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  MeanSPTree = SpillTree< MetricType, StatisticType, MatType, AxisOrthogonalHyperplane, MeanSpaceSplit > 
A meansplit hybrid spill tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  NonOrtMeanSPTree = SpillTree< MetricType, StatisticType, MatType, Hyperplane, MeanSpaceSplit > 
A meansplit hybrid spill tree considering general splitting hyperplanes (not necessarily axisorthogonal). More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  NonOrtSPTree = SpillTree< MetricType, StatisticType, MatType, Hyperplane, MidpointSpaceSplit > 
A hybrid spill tree considering general splitting hyperplanes (not necessarily axisorthogonal). More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  RPlusPlusTree = RectangleTree< MetricType, StatisticType, MatType, RPlusTreeSplit< RPlusPlusTreeSplitPolicy, MinimalSplitsNumberSweep >, RPlusPlusTreeDescentHeuristic, RPlusPlusTreeAuxiliaryInformation > 
The R++ tree, a variant of the R+ tree with maximum buonding rectangles. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  RPlusTree = RectangleTree< MetricType, StatisticType, MatType, RPlusTreeSplit< RPlusTreeSplitPolicy, MinimalCoverageSweep >, RPlusTreeDescentHeuristic, NoAuxiliaryInformation > 
The R+ tree, a variant of the R tree that avoids overlapping rectangles. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  RPTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, RPTreeMeanSplit > 
A meansplit random projection tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  RStarTree = RectangleTree< MetricType, StatisticType, MatType, RStarTreeSplit, RStarTreeDescentHeuristic, NoAuxiliaryInformation > 
The R*tree, a more recent variant of the R tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  RTree = RectangleTree< MetricType, StatisticType, MatType, RTreeSplit, RTreeDescentHeuristic, NoAuxiliaryInformation > 
An implementation of the R tree that satisfies the TreeType policy API. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  SPTree = SpillTree< MetricType, StatisticType, MatType, AxisOrthogonalHyperplane, MidpointSpaceSplit > 
The hybrid spill tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  StandardCoverTree = CoverTree< MetricType, StatisticType, MatType, FirstPointIsRoot > 
The standard cover tree, as detailed in the original cover tree paper: More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  UBTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::CellBound, UBTreeSplit > 
The Universal Btree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  VPTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HollowBallBound, VPTreeSplit > 
template < typename BoundType , typename MatType = arma::mat >  
using  VPTreeSplit = VantagePointSplit< BoundType, MatType, 100 > 
The vantage point tree (which is also called the metric tree. More...  
template < typename MetricType , typename StatisticType , typename MatType >  
using  XTree = RectangleTree< MetricType, StatisticType, MatType, XTreeSplit, RTreeDescentHeuristic, XTreeAuxiliaryInformation > 
The Xtree, a variant of the R tree with supernodes. More...  
Variables  
const double  MAX_OVERLAP = 0.2 
The Xtree paper says that a maximum allowable overlap of 20% works well. More...  
Detailed Description
Trees and treebuilding procedures.
Typedef Documentation
◆ AxisOrthogonalHyperplane
using AxisOrthogonalHyperplane = HyperplaneBase<bound::HRectBound<MetricType>, AxisParallelProjVector> 
AxisOrthogonalHyperplane represents a hyperplane orthogonal to an axis.
Definition at line 145 of file hyperplane.hpp.
◆ BallTree
using BallTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::BallBound, MidpointSplit> 
A midpointsplit ball tree.
This tree holds its points only in the leaves, similar to the KDTree and MeanSplitKDTree. However, the bounding shape of each node is a ball, not a hyperrectangle. This can make the ball tree advantageous in some higherdimensional situations and for some datasets. The tree construction algorithm here is the same as Omohundro's 'Kd construction algorithm', except the splitting value is the midpoint, not the median. This can result in trees that better reflect the data, although they may be unbalanced.
This template typedef satisfies the TreeType policy API.
Definition at line 112 of file typedef.hpp.
◆ BinaryDoubleNumericSplit
using BinaryDoubleNumericSplit = BinaryNumericSplit<FitnessFunction, double> 
Definition at line 128 of file binary_numeric_split.hpp.
◆ CosineNodeQueue
typedef boost::heap::priority_queue<CosineTree*, boost::heap::compare<CompareCosineNode> > CosineNodeQueue 
Definition at line 23 of file cosine_tree.hpp.
◆ DecisionStump
using DecisionStump = DecisionTree<FitnessFunction, NumericSplitType, CategoricalSplitType, ElemType, false> 
Convenience typedef for decision stumps (single level decision trees).
Definition at line 280 of file decision_tree.hpp.
◆ DiscreteHilbertRTreeAuxiliaryInformation
using DiscreteHilbertRTreeAuxiliaryInformation = HilbertRTreeAuxiliaryInformation<TreeType,DiscreteHilbertValue> 
The Hilbert Rtree, a variant of the R tree with an ordering along the Hilbert curve.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, RTree, DiscreteHilbertRTree
Definition at line 128 of file typedef.hpp.
◆ HilbertRTree
using HilbertRTree = RectangleTree<MetricType, StatisticType, MatType, HilbertRTreeSplit<2>, HilbertRTreeDescentHeuristic, DiscreteHilbertRTreeAuxiliaryInformation> 
Definition at line 136 of file typedef.hpp.
◆ HoeffdingDoubleNumericSplit
using HoeffdingDoubleNumericSplit = HoeffdingNumericSplit<FitnessFunction, double> 
Convenience typedef.
Definition at line 148 of file hoeffding_numeric_split.hpp.
◆ HoeffdingTreeType
typedef StreamingDecisionTree<HoeffdingTree<> > HoeffdingTreeType 
Definition at line 21 of file typedef.hpp.
◆ Hyperplane
using Hyperplane = HyperplaneBase<bound::BallBound<MetricType>, ProjVector> 
Hyperplane represents a general hyperplane (not necessarily axisorthogonal).
Definition at line 151 of file hyperplane.hpp.
◆ KDTree
using KDTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit> 
The standard midpointsplit kdtree.
This is not the original formulation by Bentley but instead the later formulation by Deng and Moore, which only holds points in the leaves of the tree. When recursively splitting nodes, the KDTree class select the dimension with maximum variance to split on, and picks the midpoint of the range in that dimension as the value on which to split nodes.
For more information, see the following papers.
This template typedef satisfies the TreeType policy API.
Definition at line 63 of file typedef.hpp.
◆ MaxRPTree
using MaxRPTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, RPTreeMaxSplit> 
A maxsplit random projection tree.
When recursively splitting nodes, the MaxSplitRPTree class selects a random hyperplane and splits a node by the hyperplane. The tree holds points in leaf nodes. In contrast to the kd tree, children of a MaxSplitRPTree node may overlap.
This template typedef satisfies the TreeType policy API.
Definition at line 232 of file typedef.hpp.
◆ MeanSplitBallTree
using MeanSplitBallTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::BallBound, MeanSplit> 
A meansplit ball tree.
This tree, like the BallTree, holds its points only in the leaves. The tree construction algorithm here is the same as Omohundro's 'Kdc onstruction algorithm', except the splitting value is the mean, not the median. This can result in trees that better reflect the data, although they may be unbalanced.
This template typedef satisfies the TreeType policy API.
Definition at line 141 of file typedef.hpp.
◆ MeanSplitKDTree
using MeanSplitKDTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, MeanSplit> 
A meansplit kdtree.
This is the same as the KDTree, but this particular implementation will use the mean of the data in the split dimension as the value on which to split, instead of the midpoint. This can sometimes give better performance, but it is not always clear which type of tree is best.
This template typedef satisfies the TreeType policy API.
Definition at line 80 of file typedef.hpp.
◆ MeanSPTree
using MeanSPTree = SpillTree<MetricType, StatisticType, MatType, AxisOrthogonalHyperplane, MeanSpaceSplit> 
A meansplit hybrid spill tree.
This is the same as the SPTree, but this particular implementation will use the mean of the data in the split dimension as the value on which to split, instead of the midpoint. This can sometimes give better performance, but it is not always clear which type of tree is best.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, SpillTree, SPTree
Definition at line 80 of file typedef.hpp.
◆ NonOrtMeanSPTree
using NonOrtMeanSPTree = SpillTree<MetricType, StatisticType, MatType, Hyperplane, MeanSpaceSplit> 
A meansplit hybrid spill tree considering general splitting hyperplanes (not necessarily axisorthogonal).
This is the same as the NonOrtSPTree, but this particular implementation will use the mean of the data in the split projection as the value on which to split, instead of the midpoint. This can sometimes give better performance, but it is not always clear which type of tree is best.
This template typedef satisfies the TreeType policy API.
Definition at line 119 of file typedef.hpp.
◆ NonOrtSPTree
using NonOrtSPTree = SpillTree<MetricType, StatisticType, MatType, Hyperplane, MidpointSpaceSplit> 
A hybrid spill tree considering general splitting hyperplanes (not necessarily axisorthogonal).
This particular implementation will consider the midpoint of the projection of the data in the vector determined by the farthest pair of points. This can sometimes give better performance, but generally it doesn't because it takes O(d) to calculate the projection of the query point when deciding which node to traverse, while when using a axisorthogonal hyperplane, as SPTree does, we can do it in O(1).
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, SpillTree, SPTree
Definition at line 100 of file typedef.hpp.
◆ RPlusPlusTree
using RPlusPlusTree = RectangleTree<MetricType, StatisticType, MatType, RPlusTreeSplit<RPlusPlusTreeSplitPolicy, MinimalSplitsNumberSweep>, RPlusPlusTreeDescentHeuristic, RPlusPlusTreeAuxiliaryInformation> 
The R++ tree, a variant of the R+ tree with maximum buonding rectangles.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, RTree, RTree, RPlusTree, RPlusPlusTree
Definition at line 196 of file typedef.hpp.
◆ RPlusTree
using RPlusTree = RectangleTree<MetricType, StatisticType, MatType, RPlusTreeSplit<RPlusTreeSplitPolicy, MinimalCoverageSweep>, RPlusTreeDescentHeuristic, NoAuxiliaryInformation> 
The R+ tree, a variant of the R tree that avoids overlapping rectangles.
The implementation is modified from the original paper implementation. This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, RTree, RTree, RPlusTree
Definition at line 168 of file typedef.hpp.
◆ RPTree
using RPTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, RPTreeMeanSplit> 
A meansplit random projection tree.
When recursively splitting nodes, the RPTree class may perform one of two different kinds of split. Depending on the diameter and the average distance between points, the node may be split by a random hyperplane or according to the distance from the mean point. The tree holds points in leaf nodes. In contrast to the kd tree, children of a MaxSplitRPTree node may overlap.
This template typedef satisfies the TreeType policy API.
Definition at line 266 of file typedef.hpp.
◆ RStarTree
using RStarTree = RectangleTree<MetricType, StatisticType, MatType, RStarTreeSplit, RStarTreeDescentHeuristic, NoAuxiliaryInformation> 
The R*tree, a more recent variant of the R tree.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, RTree
Definition at line 75 of file typedef.hpp.
◆ RTree
using RTree = RectangleTree<MetricType, StatisticType, MatType, RTreeSplit, RTreeDescentHeuristic, NoAuxiliaryInformation> 
An implementation of the R tree that satisfies the TreeType policy API.
This is the same Rtree structure as proposed by Guttman:
 See also
 The TreeType policy in mlpack, RStarTree
Definition at line 47 of file typedef.hpp.
◆ SPTree
using SPTree = SpillTree<MetricType, StatisticType, MatType, AxisOrthogonalHyperplane, MidpointSpaceSplit> 
The hybrid spill tree.
It is a variant of metrictrees in which the children of a node can "spill over" onto each other, and contain shared datapoints.
When recursively splitting nodes, the SPTree class select the dimension with maximum width to split on, and picks the midpoint of the range in that dimension as the value on which to split nodes.
In each case a "overlapping buffer" is defined, included points at a distance less than tau from the decision boundary defined by the midpoint.
For each node, we first split the points considering the overlapping buffer. If either of its children contains more than rho fraction of the total points we undo the overlapping splitting. Instead a conventional partition is used. In this way, we can ensure that each split reduces the number of points of a node by at least a constant factor.
For more information, see the following paper.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, SpillTree, MeanSPTree
Definition at line 62 of file typedef.hpp.
◆ StandardCoverTree
using StandardCoverTree = CoverTree<MetricType, StatisticType, MatType, FirstPointIsRoot> 
The standard cover tree, as detailed in the original cover tree paper:
This template typedef satisfies the requirements of the TreeType API.
 See also
 The TreeType policy in mlpack, CoverTree
Definition at line 42 of file typedef.hpp.
◆ UBTree
using UBTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::CellBound, UBTreeSplit> 
The Universal Btree.
When recursively splitting nodes, the class calculates addresses of all points and splits each node according to the median address. Children may overlap since the implementation of a tighter bound requires a lot of arithmetic operations. In order to get a tighter bound increase the CellBound::maxNumBounds constant.
This template typedef satisfies the TreeType policy API.
Definition at line 301 of file typedef.hpp.
◆ VPTree
using VPTree = BinarySpaceTree<MetricType, StatisticType, MatType, bound::HollowBallBound, VPTreeSplit> 
Definition at line 199 of file typedef.hpp.
◆ VPTreeSplit
using VPTreeSplit = VantagePointSplit<BoundType, MatType, 100> 
The vantage point tree (which is also called the metric tree.
Vantage point trees and metric trees were invented independently by Yianilos an Uhlmann) is a kind of the binary space tree. When recursively splitting nodes, the VPTree class selects the vantage point and splits the node according to the distance to this point. Thus, points that are closer to the vantage point form the inner subtree. Other points form the outer subtree. The vantage point is contained in the first (inner) node.
This implementation differs from the original algorithms. Namely, vantage points are not contained in intermediate nodes. The tree has points only in the leaves of the tree.
For more information, see the following papers.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, BinarySpaceTree, VantagePointTree, VPTree
Definition at line 192 of file typedef.hpp.
◆ XTree
using XTree = RectangleTree<MetricType, StatisticType, MatType, XTreeSplit, RTreeDescentHeuristic, XTreeAuxiliaryInformation> 
The Xtree, a variant of the R tree with supernodes.
This template typedef satisfies the TreeType policy API.
 See also
 The TreeType policy in mlpack, RTree, RStarTree
Definition at line 101 of file typedef.hpp.
Variable Documentation
◆ MAX_OVERLAP
const double MAX_OVERLAP = 0.2 
The Xtree paper says that a maximum allowable overlap of 20% works well.
This code should eventually be refactored so as to avoid polluting mlpack::tree with this random double.
Definition at line 29 of file x_tree_split.hpp.
Generated by 1.8.13