ensmallen
mlpack
fast, flexible C++ machine learning library
HoeffdingTree< FitnessFunction, NumericSplitType, CategoricalSplitType > Class Template Reference

The HoeffdingTree object represents all of the necessary information for a Hoeffding-bound-based decision tree. More...

Public Types

typedef CategoricalSplitType< FitnessFunction > CategoricalSplit
 Allow access to the categorical split type. More...

 
typedef NumericSplitType< FitnessFunction > NumericSplit
 Allow access to the numeric split type. More...

 

Public Member Functions

template
<
typename
MatType
>
 HoeffdingTree (const MatType &data, const data::DatasetInfo &datasetInfo, const arma::Row< size_t > &labels, const size_t numClasses, const bool batchTraining=true, const double successProbability=0.95, const size_t maxSamples=0, const size_t checkInterval=100, const size_t minSamples=100, const CategoricalSplitType< FitnessFunction > &categoricalSplitIn=CategoricalSplitType< FitnessFunction >(0, 0), const NumericSplitType< FitnessFunction > &numericSplitIn=NumericSplitType< FitnessFunction >(0))
 Construct the Hoeffding tree with the given parameters and given training data. More...

 
 HoeffdingTree (const data::DatasetInfo &datasetInfo, const size_t numClasses, const double successProbability=0.95, const size_t maxSamples=0, const size_t checkInterval=100, const size_t minSamples=100, const CategoricalSplitType< FitnessFunction > &categoricalSplitIn=CategoricalSplitType< FitnessFunction >(0, 0), const NumericSplitType< FitnessFunction > &numericSplitIn=NumericSplitType< FitnessFunction >(0), std::unordered_map< size_t, std::pair< size_t, size_t >> *dimensionMappings=NULL)
 Construct the Hoeffding tree with the given parameters, but training on no data. More...

 
 HoeffdingTree ()
 Construct a Hoeffding tree with no data and no information. More...

 
 HoeffdingTree (const HoeffdingTree &other)
 Copy another tree (warning: this will duplicate the tree entirely, and may use a lot of memory. More...

 
 ~HoeffdingTree ()
 Clean up memory. More...

 
template
<
typename
VecType
>
size_t CalculateDirection (const VecType &point) const
 Given a point and that this node is not a leaf, calculate the index of the child node this point would go towards. More...

 
size_t CheckInterval () const
 Get the number of samples before a split check is performed. More...

 
void CheckInterval (const size_t checkInterval)
 Modify the number of samples before a split check is performed. More...

 
const HoeffdingTreeChild (const size_t i) const
 Get a child. More...

 
HoeffdingTreeChild (const size_t i)
 Modify a child. More...

 
template
<
typename
VecType
>
size_t Classify (const VecType &point) const
 Classify the given point, using this node and the entire (sub)tree beneath it. More...

 
template
<
typename
VecType
>
void Classify (const VecType &point, size_t &prediction, double &probability) const
 Classify the given point and also return an estimate of the probability that the prediction is correct. More...

 
template
<
typename
MatType
>
void Classify (const MatType &data, arma::Row< size_t > &predictions) const
 Classify the given points, using this node and the entire (sub)tree beneath it. More...

 
template
<
typename
MatType
>
void Classify (const MatType &data, arma::Row< size_t > &predictions, arma::rowvec &probabilities) const
 Classify the given points, using this node and the entire (sub)tree beneath it. More...

 
void CreateChildren ()
 Given that this node should split, create the children. More...

 
size_t MajorityClass () const
 Get the majority class. More...

 
size_t & MajorityClass ()
 Modify the majority class. More...

 
double MajorityProbability () const
 Get the probability of the majority class (based on training samples). More...

 
double & MajorityProbability ()
 Modify the probability of the majority class. More...

 
size_t MaxSamples () const
 Get the maximum number of samples before a split is forced. More...

 
void MaxSamples (const size_t maxSamples)
 Modify the maximum number of samples before a split is forced. More...

 
size_t MinSamples () const
 Get the minimum number of samples for a split. More...

 
void MinSamples (const size_t minSamples)
 Modify the minimum number of samples for a split. More...

 
size_t NumChildren () const
 Get the number of children. More...

 
size_t NumDescendants () const
 Get the size of the Hoeffding Tree. More...

 
template
<
typename
Archive
>
void serialize (Archive &ar, const unsigned int)
 Serialize the split. More...

 
size_t SplitCheck ()
 Check if a split would satisfy the conditions of the Hoeffding bound with the node's specified success probability. More...

 
size_t SplitDimension () const
 Get the splitting dimension (size_t(-1) if no split). More...

 
double SuccessProbability () const
 Get the confidence required for a split. More...

 
void SuccessProbability (const double successProbability)
 Modify the confidence required for a split. More...

 
template
<
typename
MatType
>
void Train (const MatType &data, const arma::Row< size_t > &labels, const bool batchTraining=true)
 Train on a set of points, either in streaming mode or in batch mode, with the given labels. More...

 
template
<
typename
MatType
>
void Train (const MatType &data, const data::DatasetInfo &info, const arma::Row< size_t > &labels, const bool batchTraining=true)
 Train on a set of points, either in streaming mode or in batch mode, with the given labels and the given DatasetInfo. More...

 
template
<
typename
VecType
>
void Train (const VecType &point, const size_t label)
 Train on a single point in streaming mode, with the given label. More...

 

Detailed Description


template
<
typename
FitnessFunction
=
GiniImpurity
,
template
<
typename
>
class
NumericSplitType
=
HoeffdingDoubleNumericSplit
,
template
<
typename
>
class
CategoricalSplitType
=
HoeffdingCategoricalSplit
>

class mlpack::tree::HoeffdingTree< FitnessFunction, NumericSplitType, CategoricalSplitType >

The HoeffdingTree object represents all of the necessary information for a Hoeffding-bound-based decision tree.

This class is able to train on samples in streaming settings and batch settings, and perform splits based on the Hoeffding bound. The Hoeffding tree (also known as the "very fast decision tree" – VFDT) is described in the following paper:

@inproceedings{domingos2000mining,
title={{Mining High-Speed Data Streams}},
author={Domingos, P. and Hulten, G.},
year={2000},
booktitle={Proceedings of the Sixth ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining (KDD '00)},
pages={71--80}
}

The class is modular, and takes three template parameters. The first, FitnessFunction, is the fitness function that should be used to determine whether a split is beneficial; examples might be GiniImpurity or InformationGain. The NumericSplitType determines how numeric attributes are handled, and the CategoricalSplitType determines how categorical attributes are handled. As far as the actual splitting goes, the meat of the splitting procedure will be contained in those two classes.

Template Parameters
FitnessFunctionFitness function to use.
NumericSplitTypeTechnique for splitting numeric features.
CategoricalSplitTypeTechnique for splitting categorical features.

Definition at line 61 of file hoeffding_tree.hpp.

Member Typedef Documentation

◆ CategoricalSplit

typedef CategoricalSplitType<FitnessFunction> CategoricalSplit

Allow access to the categorical split type.

Definition at line 67 of file hoeffding_tree.hpp.

◆ NumericSplit

typedef NumericSplitType<FitnessFunction> NumericSplit

Allow access to the numeric split type.

Definition at line 65 of file hoeffding_tree.hpp.

Constructor & Destructor Documentation

◆ HoeffdingTree() [1/4]

HoeffdingTree ( const MatType &  data,
const data::DatasetInfo datasetInfo,
const arma::Row< size_t > &  labels,
const size_t  numClasses,
const bool  batchTraining = true,
const double  successProbability = 0.95,
const size_t  maxSamples = 0,
const size_t  checkInterval = 100,
const size_t  minSamples = 100,
const CategoricalSplitType< FitnessFunction > &  categoricalSplitIn = CategoricalSplitType< FitnessFunction >(0, 0),
const NumericSplitType< FitnessFunction > &  numericSplitIn = NumericSplitType< FitnessFunction >(0) 
)

Construct the Hoeffding tree with the given parameters and given training data.

The tree may be trained either in batch mode (which looks at all points before splitting, and propagates these points to the created children for further training), or in streaming mode, where each point is only considered once. (In general, batch mode will give better-performing trees, but will have higher memory and runtime costs for the same dataset.)

Parameters
dataDataset to train on.
datasetInfoInformation on the dataset (types of each feature).
labelsLabels of each point in the dataset.
numClassesNumber of classes in the dataset.
batchTrainingWhether or not to train in batch.
successProbabilityProbability of success required in Hoeffding bounds before a split can happen.
maxSamplesMaximum number of samples before a split is forced (0 never forces a split); ignored in batch training mode.
checkIntervalNumber of samples required before each split; ignored in batch training mode.
minSamplesIf the node has seen this many points or fewer, no split will be allowed.

◆ HoeffdingTree() [2/4]

HoeffdingTree ( const data::DatasetInfo datasetInfo,
const size_t  numClasses,
const double  successProbability = 0.95,
const size_t  maxSamples = 0,
const size_t  checkInterval = 100,
const size_t  minSamples = 100,
const CategoricalSplitType< FitnessFunction > &  categoricalSplitIn = CategoricalSplitType< FitnessFunction >(0, 0),
const NumericSplitType< FitnessFunction > &  numericSplitIn = NumericSplitType< FitnessFunction >(0),
std::unordered_map< size_t, std::pair< size_t, size_t >> *  dimensionMappings = NULL 
)

Construct the Hoeffding tree with the given parameters, but training on no data.

The dimensionMappings parameter is only used if it is desired that this node does not create its own dimensionMappings object (for instance, if this is a child of another node in the tree).

Parameters
dimensionalityDimensionality of the dataset.
numClassesNumber of classes in the dataset.
datasetInfoInformation on the dataset (types of each feature).
successProbabilityProbability of success required in Hoeffding bound before a split can happen.
maxSamplesMaximum number of samples before a split is forced.
checkIntervalNumber of samples required before each split check.
minSamplesIf the node has seen this many points or fewer, no split will be allowed.
dimensionMappingsMappings from dimension indices to positions in numeric and categorical split vectors. If left NULL, a new one will be created.

◆ HoeffdingTree() [3/4]

Construct a Hoeffding tree with no data and no information.

Be sure to call Train() before trying to use the tree.

◆ HoeffdingTree() [4/4]

HoeffdingTree ( const HoeffdingTree< FitnessFunction, NumericSplitType, CategoricalSplitType > &  other)

Copy another tree (warning: this will duplicate the tree entirely, and may use a lot of memory.

Make sure it's what you want before you do it).

Parameters
otherTree to copy.

◆ ~HoeffdingTree()

Clean up memory.

Member Function Documentation

◆ CalculateDirection()

size_t CalculateDirection ( const VecType &  point) const

Given a point and that this node is not a leaf, calculate the index of the child node this point would go towards.

This method is primarily used by the Classify() function, but it can be used in a standalone sense too.

Parameters
pointPoint to classify.

Referenced by HoeffdingTree< FitnessFunction, NumericSplitType, CategoricalSplitType >::CheckInterval().

◆ CheckInterval() [1/2]

◆ CheckInterval() [2/2]

void CheckInterval ( const size_t  checkInterval)

Modify the number of samples before a split check is performed.

◆ Child() [1/2]

const HoeffdingTree& Child ( const size_t  i) const
inline

Get a child.

Definition at line 213 of file hoeffding_tree.hpp.

◆ Child() [2/2]

HoeffdingTree& Child ( const size_t  i)
inline

Modify a child.

Definition at line 215 of file hoeffding_tree.hpp.

◆ Classify() [1/4]

size_t Classify ( const VecType &  point) const

Classify the given point, using this node and the entire (sub)tree beneath it.

The predicted label is returned.

Parameters
pointPoint to classify.
Returns
Predicted label of point.

Referenced by HoeffdingTree< FitnessFunction, NumericSplitType, CategoricalSplitType >::CheckInterval().

◆ Classify() [2/4]

void Classify ( const VecType &  point,
size_t &  prediction,
double &  probability 
) const

Classify the given point and also return an estimate of the probability that the prediction is correct.

(This estimate is simply the probability that a training point was from the majority class in the leaf that this point binned to.)

Parameters
pointPoint to classify.
predictionPredicted label of point.
probabilityAn estimate of the probability that the prediction is correct.

◆ Classify() [3/4]

void Classify ( const MatType &  data,
arma::Row< size_t > &  predictions 
) const

Classify the given points, using this node and the entire (sub)tree beneath it.

The predicted labels for each point are returned.

Parameters
dataPoints to classify.
predictionsPredicted labels for each point.

◆ Classify() [4/4]

void Classify ( const MatType &  data,
arma::Row< size_t > &  predictions,
arma::rowvec &  probabilities 
) const

Classify the given points, using this node and the entire (sub)tree beneath it.

The predicted labels for each point are returned, as well as an estimate of the probability that the prediction is correct for each point. This estimate is simply the MajorityProbability() for the leaf that each point bins to.

Parameters
dataPoints to classify.
predictionsPredicted labels for each point.
probabilitiesProbability estimates for each predicted label.

◆ CreateChildren()

void CreateChildren ( )

Given that this node should split, create the children.

Referenced by HoeffdingTree< FitnessFunction, NumericSplitType, CategoricalSplitType >::CheckInterval().

◆ MajorityClass() [1/2]

size_t MajorityClass ( ) const
inline

Get the majority class.

Definition at line 200 of file hoeffding_tree.hpp.

◆ MajorityClass() [2/2]

size_t& MajorityClass ( )
inline

Modify the majority class.

Definition at line 202 of file hoeffding_tree.hpp.

◆ MajorityProbability() [1/2]

double MajorityProbability ( ) const
inline

Get the probability of the majority class (based on training samples).

Definition at line 205 of file hoeffding_tree.hpp.

◆ MajorityProbability() [2/2]

double& MajorityProbability ( )
inline

Modify the probability of the majority class.

Definition at line 207 of file hoeffding_tree.hpp.

◆ MaxSamples() [1/2]

size_t MaxSamples ( ) const
inline

Get the maximum number of samples before a split is forced.

Definition at line 228 of file hoeffding_tree.hpp.

◆ MaxSamples() [2/2]

void MaxSamples ( const size_t  maxSamples)

Modify the maximum number of samples before a split is forced.

◆ MinSamples() [1/2]

size_t MinSamples ( ) const
inline

Get the minimum number of samples for a split.

Definition at line 223 of file hoeffding_tree.hpp.

◆ MinSamples() [2/2]

void MinSamples ( const size_t  minSamples)

Modify the minimum number of samples for a split.

◆ NumChildren()

size_t NumChildren ( ) const
inline

Get the number of children.

Definition at line 210 of file hoeffding_tree.hpp.

◆ NumDescendants()

size_t NumDescendants ( ) const

◆ serialize()

void serialize ( Archive &  ar,
const unsigned  int 
)

◆ SplitCheck()

size_t SplitCheck ( )

Check if a split would satisfy the conditions of the Hoeffding bound with the node's specified success probability.

If so, the number of children that would be created is returned. If not, 0 is returned.

◆ SplitDimension()

size_t SplitDimension ( ) const
inline

Get the splitting dimension (size_t(-1) if no split).

Definition at line 197 of file hoeffding_tree.hpp.

◆ SuccessProbability() [1/2]

double SuccessProbability ( ) const
inline

Get the confidence required for a split.

Definition at line 218 of file hoeffding_tree.hpp.

◆ SuccessProbability() [2/2]

void SuccessProbability ( const double  successProbability)

Modify the confidence required for a split.

◆ Train() [1/3]

void Train ( const MatType &  data,
const arma::Row< size_t > &  labels,
const bool  batchTraining = true 
)

Train on a set of points, either in streaming mode or in batch mode, with the given labels.

Parameters
dataData points to train on.
labelLabels of data points.
batchTrainingIf true, perform training in batch.

◆ Train() [2/3]

void Train ( const MatType &  data,
const data::DatasetInfo info,
const arma::Row< size_t > &  labels,
const bool  batchTraining = true 
)

Train on a set of points, either in streaming mode or in batch mode, with the given labels and the given DatasetInfo.

This will reset the tree.

◆ Train() [3/3]

void Train ( const VecType &  point,
const size_t  label 
)

Train on a single point in streaming mode, with the given label.

Parameters
pointPoint to train on.
labelLabel of point to train on.

The documentation for this class was generated from the following file:
  • /home/ryan/src/mlpack.org/_src/mlpack-git/src/mlpack/methods/hoeffding_trees/hoeffding_tree.hpp