MLPACK  1.0.8
dtree.hpp
Go to the documentation of this file.
1 
23 #ifndef __MLPACK_METHODS_DET_DTREE_HPP
24 #define __MLPACK_METHODS_DET_DTREE_HPP
25 
26 #include <mlpack/core.hpp>
27 
28 namespace mlpack {
29 namespace det {
30 
54 class DTree
55 {
56  public:
60  DTree();
61 
70  DTree(const arma::vec& maxVals,
71  const arma::vec& minVals,
72  const size_t totalPoints);
73 
82  DTree(arma::mat& data);
83 
96  DTree(const arma::vec& maxVals,
97  const arma::vec& minVals,
98  const size_t start,
99  const size_t end,
100  const double logNegError);
101 
113  DTree(const arma::vec& maxVals,
114  const arma::vec& minVals,
115  const size_t totalPoints,
116  const size_t start,
117  const size_t end);
118 
120  ~DTree();
121 
132  double Grow(arma::mat& data,
133  arma::Col<size_t>& oldFromNew,
134  const bool useVolReg = false,
135  const size_t maxLeafSize = 10,
136  const size_t minLeafSize = 5);
137 
146  double PruneAndUpdate(const double oldAlpha,
147  const size_t points,
148  const bool useVolReg = false);
149 
155  double ComputeValue(const arma::vec& query) const;
156 
164  void WriteTree(FILE *fp, const size_t level = 0) const;
165 
173  int TagTree(const int tag = 0);
174 
181  int FindBucket(const arma::vec& query) const;
182 
188  void ComputeVariableImportance(arma::vec& importances) const;
189 
196  double LogNegativeError(const size_t totalPoints) const;
197 
201  bool WithinRange(const arma::vec& query) const;
202 
203  private:
204  // The indices in the complete set of points
205  // (after all forms of swapping in the original data
206  // matrix to align all the points in a node
207  // consecutively in the matrix. The 'old_from_new' array
208  // maps the points back to their original indices.
209 
212  size_t start;
215  size_t end;
216 
218  arma::vec maxVals;
220  arma::vec minVals;
221 
223  size_t splitDim;
224 
226  double splitValue;
227 
229  double logNegError;
230 
233 
236 
238  bool root;
239 
241  double ratio;
242 
244  double logVolume;
245 
248 
250  double alphaUpper;
251 
256 
257  public:
259  size_t Start() const { return start; }
261  size_t End() const { return end; }
263  size_t SplitDim() const { return splitDim; }
265  double SplitValue() const { return splitValue; }
267  double LogNegError() const { return logNegError; }
271  size_t SubtreeLeaves() const { return subtreeLeaves; }
274  double Ratio() const { return ratio; }
276  double LogVolume() const { return logVolume; }
278  DTree* Left() const { return left; }
280  DTree* Right() const { return right; }
282  bool Root() const { return root; }
284  double AlphaUpper() const { return alphaUpper; }
285 
287  const arma::vec& MaxVals() const { return maxVals; }
289  arma::vec& MaxVals() { return maxVals; }
290 
292  const arma::vec& MinVals() const { return minVals; }
294  arma::vec& MinVals() { return minVals; }
295 
296  private:
297 
298  // Utility methods.
299 
303  bool FindSplit(const arma::mat& data,
304  size_t& splitDim,
305  double& splitValue,
306  double& leftError,
307  double& rightError,
308  const size_t maxLeafSize = 10,
309  const size_t minLeafSize = 5) const;
310 
314  size_t SplitData(arma::mat& data,
315  const size_t splitDim,
316  const double splitValue,
317  arma::Col<size_t>& oldFromNew) const;
318 
319 };
320 
321 }; // namespace det
322 }; // namespace mlpack
323 
324 #endif // __MLPACK_METHODS_DET_DTREE_HPP
arma::vec & MaxVals()
Modify the maximum values.
Definition: dtree.hpp:289
double ComputeValue(const arma::vec &query) const
Compute the logarithm of the density estimate of a given query point.
double LogNegativeError(const size_t totalPoints) const
Compute the log-negative-error for this point, given the total number of points in the dataset...
size_t SplitDim() const
Return the split dimension of this node.
Definition: dtree.hpp:263
int FindBucket(const arma::vec &query) const
Return the tag of the leaf containing the query.
double splitValue
The split value on the splitting dimension for this node.
Definition: dtree.hpp:226
double logNegError
log-negative-L2-error of the node.
Definition: dtree.hpp:229
void WriteTree(FILE *fp, const size_t level=0) const
Print the tree in a depth-first manner (this function is called recursively).
size_t Start() const
Return the starting index of points contained in this node.
Definition: dtree.hpp:259
~DTree()
Clean up memory allocated by the tree.
DTree * left
The left child.
Definition: dtree.hpp:253
arma::vec maxVals
Upper half of bounding box for this node.
Definition: dtree.hpp:218
size_t SubtreeLeaves() const
Return the number of leaves which are descendants of this node.
Definition: dtree.hpp:271
void ComputeVariableImportance(arma::vec &importances) const
Compute the variable importance of each dimension in the learned tree.
size_t End() const
Return the first index of a point not contained in this node.
Definition: dtree.hpp:261
size_t subtreeLeaves
Number of leaves of the subtree.
Definition: dtree.hpp:235
DTree * Left() const
Return the left child.
Definition: dtree.hpp:278
double LogVolume() const
Return the inverse of the volume of this node.
Definition: dtree.hpp:276
size_t start
The index of the first point in the dataset contained in this node (and its children).
Definition: dtree.hpp:212
arma::vec & MinVals()
Modify the minimum values.
Definition: dtree.hpp:294
size_t splitDim
The splitting dimension for this node.
Definition: dtree.hpp:223
const arma::vec & MaxVals() const
Return the maximum values.
Definition: dtree.hpp:287
DTree * Right() const
Return the right child.
Definition: dtree.hpp:280
double AlphaUpper() const
Return the upper part of the alpha sum.
Definition: dtree.hpp:284
double PruneAndUpdate(const double oldAlpha, const size_t points, const bool useVolReg=false)
Perform alpha pruning on a tree.
bool FindSplit(const arma::mat &data, size_t &splitDim, double &splitValue, double &leftError, double &rightError, const size_t maxLeafSize=10, const size_t minLeafSize=5) const
Find the dimension to split on.
bool root
If true, this node is the root of the tree.
Definition: dtree.hpp:238
double LogNegError() const
Return the log negative error of this node.
Definition: dtree.hpp:267
DTree * right
The right child.
Definition: dtree.hpp:255
A density estimation tree is similar to both a decision tree and a space partitioning tree (like a kd...
Definition: dtree.hpp:54
double alphaUpper
Upper part of alpha sum; used for pruning.
Definition: dtree.hpp:250
double ratio
Ratio of the number of points in the node to the total number of points.
Definition: dtree.hpp:241
int bucketTag
The tag for the leaf, used for hashing points.
Definition: dtree.hpp:247
double subtreeLeavesLogNegError
Sum of the error of the leaves of the subtree.
Definition: dtree.hpp:232
double logVolume
The logarithm of the volume of the node.
Definition: dtree.hpp:244
bool WithinRange(const arma::vec &query) const
Return whether a query point is within the range of this node.
size_t SplitData(arma::mat &data, const size_t splitDim, const double splitValue, arma::Col< size_t > &oldFromNew) const
Split the data, returning the number of points left of the split.
arma::vec minVals
Lower half of bounding box for this node.
Definition: dtree.hpp:220
double SplitValue() const
Return the split value of this node.
Definition: dtree.hpp:265
double Ratio() const
Return the ratio of points in this node to the points in the whole dataset.
Definition: dtree.hpp:274
DTree()
Create an empty density estimation tree.
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.
bool Root() const
Return whether or not this is the root of the tree.
Definition: dtree.hpp:282
int TagTree(const int tag=0)
Index the buckets for possible usage later; this results in every leaf in the tree having a specific ...
size_t end
The index of the last point in the dataset contained in this node (and its children).
Definition: dtree.hpp:215
const arma::vec & MinVals() const
Return the minimum values.
Definition: dtree.hpp:292
double SubtreeLeavesLogNegError() const
Return the log negative error of all descendants of this node.
Definition: dtree.hpp:269