mlpack
2.0.1
|
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... | |
Trees and tree-building procedures.
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.
This template typedef satisfies the TreeType policy API.
Definition at line 114 of file typedef.hpp.
using mlpack::tree::BinaryDoubleNumericSplit = typedef BinaryNumericSplit<FitnessFunction, double> |
Definition at line 130 of file binary_numeric_split.hpp.
typedef boost::heap::priority_queue<CosineTree*, boost::heap::compare<CompareCosineNode> > mlpack::tree::CosineNodeQueue |
Definition at line 25 of file cosine_tree.hpp.
using mlpack::tree::HoeffdingDoubleNumericSplit = typedef HoeffdingNumericSplit<FitnessFunction, double> |
Convenience typedef.
Definition at line 150 of file hoeffding_numeric_split.hpp.
typedef StreamingDecisionTree<HoeffdingTree<> > mlpack::tree::HoeffdingTreeType |
Definition at line 23 of file typedef.hpp.
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.
This template typedef satisfies the TreeType policy API.
Definition at line 65 of file typedef.hpp.
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.
This template typedef satisfies the TreeType policy API.
Definition at line 143 of file typedef.hpp.
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.
Definition at line 82 of file typedef.hpp.
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.
Definition at line 75 of file typedef.hpp.
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:
Definition at line 48 of file typedef.hpp.
using mlpack::tree::StandardCoverTree = typedef 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.
Definition at line 44 of file typedef.hpp.
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.