mlpack  2.0.1
Classes | Typedefs | Variables
mlpack::tree Namespace Reference

Trees and tree-building procedures. More...

Classes

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 KD-tree or a ball tree. More...
 
class  CategoricalSplitInfo
 
class  CompareCosineNode
 
class  CosineTree
 
class  CoverTree
 A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensional spaces. 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  GiniImpurity
 
class  HoeffdingCategoricalSplit
 This is the standard Hoeffding-bound 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 Hoeffding-bound-based decision tree. More...
 
class  InformationGain
 
class  MeanSplit
 A binary space partitioning tree node is split into its left and right child. More...
 
class  MidpointSplit
 A binary space partitioning tree node is split into its left and right child. More...
 
class  NumericSplitInfo
 
struct  QueueFrame
 
class  RectangleTree
 A rectangle type tree tree, such as an R-tree or X-tree. More...
 
class  RStarTreeDescentHeuristic
 When descending a Rectangle tree 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  TreeTraits
 The TreeTraits class provides compile-time information on the characteristics of a given tree type. More...
 
class  TreeTraits< BinarySpaceTree< MetricType, StatisticType, MatType, BoundType, SplitType > >
 This is a specialization of the TreeType 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< RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType > >
 This is a specialization of the TreeType class to the RectangleTree tree type. More...
 
class  XTreeSplit
 A Rectangle Tree has new points inserted at the bottom. More...
 

Typedefs

template<typename MetricType , typename StatisticType , typename MatType >
using BallTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit >
 A midpoint-split 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 >
using HoeffdingDoubleNumericSplit = HoeffdingNumericSplit< FitnessFunction, double >
 Convenience typedef. More...
 
typedef StreamingDecisionTree< HoeffdingTree<> > HoeffdingTreeType
 
template<typename MetricType , typename StatisticType , typename MatType >
using KDTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit >
 The standard midpoint-split kd-tree. More...
 
template<typename MetricType , typename StatisticType , typename MatType >
using MeanSplitBallTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MeanSplit >
 A mean-split ball tree. More...
 
template<typename MetricType , typename StatisticType , typename MatType >
using MeanSplitKDTree = BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MeanSplit >
 A mean-split kd-tree. More...
 
template<typename MetricType , typename StatisticType , typename MatType >
using RStarTree = RectangleTree< MetricType, StatisticType, MatType, RStarTreeSplit, RStarTreeDescentHeuristic >
 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 >
 An implementation of the R tree that satisfies the TreeType policy API. 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...
 

Variables

const double MAX_OVERLAP = 0.2
 The X-tree paper says that a maximum allowable overlap of 20% works well. More...
 

Detailed Description

Trees and tree-building procedures.

Typedef Documentation

◆ BallTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::BallTree = typedef BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit>

A midpoint-split 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 hyper-rectangle. This can make the ball tree advantageous in some higher-dimensional situations and for some datasets. The tree construction algorithm here is the same as Omohundro's 'K-d 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.

@techreport{omohundro1989five,
author={S.M. Omohundro},
title={Five balltree construction algorithms},
year={1989},
institution={University of California, Berkeley International Computer
Science Institute Technical Reports},
number={TR-89-063}
}

This template typedef satisfies the TreeType policy API.

See also
The TreeType policy in mlpack, BinarySpaceTree, KDTree, MeanSplitBallTree

Definition at line 114 of file typedef.hpp.

◆ BinaryDoubleNumericSplit

template<typename FitnessFunction >
using mlpack::tree::BinaryDoubleNumericSplit = typedef BinaryNumericSplit<FitnessFunction, double>

Definition at line 130 of file binary_numeric_split.hpp.

◆ CosineNodeQueue

typedef boost::heap::priority_queue<CosineTree*, boost::heap::compare<CompareCosineNode> > mlpack::tree::CosineNodeQueue

Definition at line 25 of file cosine_tree.hpp.

◆ HoeffdingDoubleNumericSplit

template<typename FitnessFunction >
using mlpack::tree::HoeffdingDoubleNumericSplit = typedef HoeffdingNumericSplit<FitnessFunction, double>

Convenience typedef.

Definition at line 150 of file hoeffding_numeric_split.hpp.

◆ HoeffdingTreeType

typedef StreamingDecisionTree<HoeffdingTree<> > mlpack::tree::HoeffdingTreeType

Definition at line 23 of file typedef.hpp.

◆ KDTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::KDTree = typedef BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit>

The standard midpoint-split kd-tree.

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.

@article{bentley1975multidimensional,
title={Multidimensional binary search trees used for associative searching},
author={Bentley, J.L.},
journal={Communications of the ACM},
volume={18},
number={9},
pages={509--517},
year={1975},
publisher={ACM}
}
@inproceedings{deng1995multiresolution,
title={Multiresolution instance-based learning},
author={Deng, K. and Moore, A.W.},
booktitle={Proceedings of the 1995 International Joint Conference on AI
(IJCAI-95)},
pages={1233--1239},
year={1995}
}

This template typedef satisfies the TreeType policy API.

See also
The TreeType policy in mlpack, BinarySpaceTree, MeanSplitKDTree

Definition at line 65 of file typedef.hpp.

◆ MeanSplitBallTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::MeanSplitBallTree = typedef BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, MeanSplit>

A mean-split 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 'K-dc 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.

@techreport{omohundro1989five,
author={S.M. Omohundro},
title={Five balltree construction algorithms},
year={1989},
institution={University of California, Berkeley International Computer
Science Institute Technical Reports},
number={TR-89-063}
}

This template typedef satisfies the TreeType policy API.

See also
The TreeType policy in mlpack, BinarySpaceTree, BallTree, MeanSplitKDTree

Definition at line 143 of file typedef.hpp.

◆ MeanSplitKDTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::MeanSplitKDTree = typedef BinarySpaceTree<MetricType, StatisticType, MatType, bound::HRectBound, MeanSplit>

A mean-split kd-tree.

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.

See also
The TreeType policy in mlpack, BinarySpaceTree, KDTree

Definition at line 82 of file typedef.hpp.

◆ RStarTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::RStarTree = typedef RectangleTree<MetricType, StatisticType, MatType, RStarTreeSplit, RStarTreeDescentHeuristic>

The R*-tree, a more recent variant of the R tree.

This template typedef satisfies the TreeType policy API.

@inproceedings{beckmann1990r,
title={The R*-tree: an efficient and robust access method for points and
rectangles},
author={Beckmann, N. and Kriegel, H.-P. and Schneider, R. and Seeger, B.},
booktitle={Proceedings of the 1990 ACM SIGMOD International Conference on
Management of Data (SIGMOD '90)},
volume={19},
number={2},
year={1990},
publisher={ACM}
}
See also
The TreeType policy in mlpack, RTree

Definition at line 75 of file typedef.hpp.

◆ RTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::RTree = typedef RectangleTree<MetricType, StatisticType, MatType, RTreeSplit, RTreeDescentHeuristic>

An implementation of the R tree that satisfies the TreeType policy API.

This is the same R-tree structure as proposed by Guttman:

@inproceedings{guttman1984r,
title={R-trees: a dynamic index structure for spatial searching},
author={Guttman, A.},
booktitle={Proceedings of the 1984 ACM SIGMOD International Conference on
Management of Data (SIGMOD '84)},
volume={14},
number={2},
year={1984},
publisher={ACM}
}
See also
The TreeType policy in mlpack, RStarTree

Definition at line 48 of file typedef.hpp.

◆ StandardCoverTree

template<typename MetricType , typename StatisticType , typename MatType >
using mlpack::tree::StandardCoverTree = typedef CoverTree<MetricType, StatisticType, MatType, FirstPointIsRoot>

The standard cover tree, as detailed in the original cover tree paper:

@inproceedings{
author={Beygelzimer, A. and Kakade, S. and Langford, J.},
title={Cover trees for nearest neighbor},
booktitle={Proceedings of the 23rd International Conference on Machine
Learning (ICML 2006)},
pages={97--104},
year={2006}
}

This template typedef satisfies the requirements of the TreeType API.

See also
The TreeType policy in mlpack, CoverTree

Definition at line 44 of file typedef.hpp.

Variable Documentation

◆ MAX_OVERLAP

const double mlpack::tree::MAX_OVERLAP = 0.2

The X-tree 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 31 of file x_tree_split.hpp.