mlpack  2.2.5
DTree Class Reference

A density estimation tree is similar to both a decision tree and a space partitioning tree (like a kd-tree). More...

## Public Member Functions

DTree ()
Create an empty density estimation tree. More...

DTree (const arma::vec &maxVals, const arma::vec &minVals, const size_t totalPoints)
Create a density estimation tree with the given bounds and the given number of total points. More...

DTree (arma::mat &data)
Create a density estimation tree on the given data. More...

DTree (const arma::vec &maxVals, const arma::vec &minVals, const size_t start, const size_t end, const double logNegError)
Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end and the specified error. More...

DTree (const arma::vec &maxVals, const arma::vec &minVals, const size_t totalPoints, const size_t start, const size_t end)
Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end, and calculating the error with the total number of points given. More...

~DTree ()
Clean up memory allocated by the tree. More...

double AlphaUpper () const
Return the upper part of the alpha sum. More...

double ComputeValue (const arma::vec &query) const
Compute the logarithm of the density estimate of a given query point. More...

void ComputeVariableImportance (arma::vec &importances) const
Compute the variable importance of each dimension in the learned tree. More...

size_t End () const
Return the first index of a point not contained in this node. More...

int FindBucket (const arma::vec &query) const
Return the tag of the leaf containing the query. More...

double Grow (arma::mat &data, arma::Col< size_t > &oldFromNew, const bool useVolReg=false, const size_t maxLeafSize=10, const size_t minLeafSize=5)
Greedily expand the tree. More...

DTreeLeft () const
Return the left child. More...

double LogNegativeError (const size_t totalPoints) const
Compute the log-negative-error for this point, given the total number of points in the dataset. More...

double LogNegError () const
Return the log negative error of this node. More...

double LogVolume () const
Return the inverse of the volume of this node. More...

const arma::vec & MaxVals () const
Return the maximum values. More...

arma::vec & MaxVals ()
Modify the maximum values. More...

const arma::vec & MinVals () const
Return the minimum values. More...

arma::vec & MinVals ()
Modify the minimum values. More...

double PruneAndUpdate (const double oldAlpha, const size_t points, const bool useVolReg=false)
Perform alpha pruning on a tree. More...

double Ratio () const
Return the ratio of points in this node to the points in the whole dataset. More...

DTreeRight () const
Return the right child. More...

bool Root () const
Return whether or not this is the root of the tree. More...

template
<
typename
Archive
>
void Serialize (Archive &ar, const unsigned int)
Serialize the density estimation tree. More...

size_t SplitDim () const
Return the split dimension of this node. More...

double SplitValue () const
Return the split value of this node. More...

size_t Start () const
Return the starting index of points contained in this node. More...

size_t SubtreeLeaves () const
Return the number of leaves which are descendants of this node. More...

double SubtreeLeavesLogNegError () const
Return the log negative error of all descendants of this node. More...

int TagTree (const int tag=0)
Index the buckets for possible usage later; this results in every leaf in the tree having a specific tag (accessible with BucketTag()). More...

bool WithinRange (const arma::vec &query) const
Return whether a query point is within the range of this node. More...

void WriteTree (FILE *fp, const size_t level=0) const
Print the tree in a depth-first manner (this function is called recursively). More...

## Detailed Description

A density estimation tree is similar to both a decision tree and a space partitioning tree (like a kd-tree).

Each leaf represents a constant-density hyper-rectangle. The tree is constructed in such a way as to minimize the integrated square error between the probability distribution of the tree and the observed probability distribution of the data. Because the tree is similar to a decision tree, the density estimation tree can provide very fast density estimates for a given point.

@incollection{ram2011,
author = {Ram, Parikshit and Gray, Alexander G.},
title = {Density estimation trees},
booktitle = {{Proceedings of the 17th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining}},
series = {KDD '11},
year = {2011},
pages = {627--635}
}

Definition at line 44 of file dtree.hpp.

## ◆ DTree() [1/5]

 DTree ( )

Create an empty density estimation tree.

## ◆ DTree() [2/5]

 DTree ( const arma::vec & maxVals, const arma::vec & minVals, const size_t totalPoints )

Create a density estimation tree with the given bounds and the given number of total points.

Children will not be created.

Parameters
 maxVals Maximum values of the bounding box. minVals Minimum values of the bounding box. totalPoints Total number of points in the dataset.

## ◆ DTree() [3/5]

 DTree ( arma::mat & data )

Create a density estimation tree on the given data.

Children will be created following the procedure outlined in the paper. The data will be modified; it will be reordered similar to the way BinarySpaceTree modifies datasets.

Parameters
 data Dataset to build tree on.

## ◆ DTree() [4/5]

 DTree ( const arma::vec & maxVals, const arma::vec & minVals, const size_t start, const size_t end, const double logNegError )

Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end and the specified error.

Children of this node will not be created recursively.

Parameters
 maxVals Upper bound of bounding box. minVals Lower bound of bounding box. start Start of points represented by this node in the data matrix. end End of points represented by this node in the data matrix. error log-negative error of this node.

## ◆ DTree() [5/5]

 DTree ( const arma::vec & maxVals, const arma::vec & minVals, const size_t totalPoints, const size_t start, const size_t end )

Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end, and calculating the error with the total number of points given.

Children of this node will not be created recursively.

Parameters
 maxVals Upper bound of bounding box. minVals Lower bound of bounding box. start Start of points represented by this node in the data matrix. end End of points represented by this node in the data matrix.

## ◆ ~DTree()

 ~DTree ( )

Clean up memory allocated by the tree.

## ◆ AlphaUpper()

 double AlphaUpper ( ) const
inline

Return the upper part of the alpha sum.

Definition at line 274 of file dtree.hpp.

## ◆ ComputeValue()

 double ComputeValue ( const arma::vec & query ) const

Compute the logarithm of the density estimate of a given query point.

Parameters
 query Point to estimate density of.

## ◆ ComputeVariableImportance()

 void ComputeVariableImportance ( arma::vec & importances ) const

Compute the variable importance of each dimension in the learned tree.

Parameters
 importances Vector to store the calculated importances in.

## ◆ End()

 size_t End ( ) const
inline

Return the first index of a point not contained in this node.

Definition at line 251 of file dtree.hpp.

## ◆ FindBucket()

 int FindBucket ( const arma::vec & query ) const

Return the tag of the leaf containing the query.

This is useful for generating class memberships.

Parameters
 query Query to search for.

## ◆ Grow()

 double Grow ( arma::mat & data, arma::Col< size_t > & oldFromNew, const bool useVolReg = `false`, const size_t maxLeafSize = `10`, const size_t minLeafSize = `5` )

Greedily expand the tree.

The points in the dataset will be reordered during tree growth.

Parameters
 data Dataset to build tree on. oldFromNew Mappings from old points to new points. useVolReg If true, volume regularization is used. maxLeafSize Maximum size of a leaf. minLeafSize Minimum size of a leaf.

## ◆ Left()

 DTree* Left ( ) const
inline

Return the left child.

Definition at line 268 of file dtree.hpp.

## ◆ LogNegativeError()

 double LogNegativeError ( const size_t totalPoints ) const

Compute the log-negative-error for this point, given the total number of points in the dataset.

Parameters
 totalPoints Total number of points in the dataset.

## ◆ LogNegError()

 double LogNegError ( ) const
inline

Return the log negative error of this node.

Definition at line 257 of file dtree.hpp.

## ◆ LogVolume()

 double LogVolume ( ) const
inline

Return the inverse of the volume of this node.

Definition at line 266 of file dtree.hpp.

## ◆ MaxVals() [1/2]

 const arma::vec& MaxVals ( ) const
inline

Return the maximum values.

Definition at line 277 of file dtree.hpp.

## ◆ MaxVals() [2/2]

 arma::vec& MaxVals ( )
inline

Modify the maximum values.

Definition at line 279 of file dtree.hpp.

## ◆ MinVals() [1/2]

 const arma::vec& MinVals ( ) const
inline

Return the minimum values.

Definition at line 282 of file dtree.hpp.

## ◆ MinVals() [2/2]

 arma::vec& MinVals ( )
inline

Modify the minimum values.

Definition at line 284 of file dtree.hpp.

## ◆ PruneAndUpdate()

 double PruneAndUpdate ( const double oldAlpha, const size_t points, const bool useVolReg = `false` )

Perform alpha pruning on a tree.

Returns the new value of alpha.

Parameters
 oldAlpha Old value of alpha. points Total number of points in dataset. useVolReg If true, volume regularization is used.
Returns
New value of alpha.

## ◆ Ratio()

 double Ratio ( ) const
inline

Return the ratio of points in this node to the points in the whole dataset.

Definition at line 264 of file dtree.hpp.

## ◆ Right()

 DTree* Right ( ) const
inline

Return the right child.

Definition at line 270 of file dtree.hpp.

## ◆ Root()

 bool Root ( ) const
inline

Return whether or not this is the root of the tree.

Definition at line 272 of file dtree.hpp.

## ◆ Serialize()

 void Serialize ( Archive & ar, const unsigned int )
inline

Serialize the density estimation tree.

Definition at line 290 of file dtree.hpp.

References mlpack::data::CreateNVP().

## ◆ SplitDim()

 size_t SplitDim ( ) const
inline

Return the split dimension of this node.

Definition at line 253 of file dtree.hpp.

## ◆ SplitValue()

 double SplitValue ( ) const
inline

Return the split value of this node.

Definition at line 255 of file dtree.hpp.

## ◆ Start()

 size_t Start ( ) const
inline

Return the starting index of points contained in this node.

Definition at line 249 of file dtree.hpp.

## ◆ SubtreeLeaves()

 size_t SubtreeLeaves ( ) const
inline

Return the number of leaves which are descendants of this node.

Definition at line 261 of file dtree.hpp.

## ◆ SubtreeLeavesLogNegError()

 double SubtreeLeavesLogNegError ( ) const
inline

Return the log negative error of all descendants of this node.

Definition at line 259 of file dtree.hpp.

## ◆ TagTree()

 int TagTree ( const int tag = `0` )

Index the buckets for possible usage later; this results in every leaf in the tree having a specific tag (accessible with BucketTag()).

This function calls itself recursively.

Parameters
 tag Tag for the next leaf; leave at 0 for the initial call.

## ◆ WithinRange()

 bool WithinRange ( const arma::vec & query ) const

Return whether a query point is within the range of this node.

## ◆ WriteTree()

 void WriteTree ( FILE * fp, const size_t level = `0` ) const

Print the tree in a depth-first manner (this function is called recursively).

Parameters
 fp File to write the tree to. level Level of the tree (should start at 0).

The documentation for this class was generated from the following file: