dtree.hpp

Go to the documentation of this file.

#ifndef MLPACK_METHODS_DET_DTREE_HPP
#define MLPACK_METHODS_DET_DTREE_HPP

#include <mlpack/prereqs.hpp>

namespace mlpack {
namespace det  {

template <typename MatType,
          typename TagType = int>
class DTree
{
 public:
  typedef typename MatType::elem_type     ElemType;
  typedef typename MatType::vec_type      VecType;
  typedef typename arma::Col<ElemType>    StatType;

  DTree();

  DTree(const DTree& obj);

  DTree& operator=(const DTree& obj);

  DTree(DTree&& obj);

  DTree& operator=(DTree&& obj);

  DTree(const StatType& maxVals,
        const StatType& minVals,
        const size_t totalPoints);

  DTree(MatType& data);

  DTree(const StatType& maxVals,
        const StatType& minVals,
        const size_t start,
        const size_t end,
        const double logNegError);

  DTree(const StatType& maxVals,
        const StatType& minVals,
        const size_t totalPoints,
        const size_t start,
        const size_t end);

  ~DTree();

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

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

  double ComputeValue(const VecType& query) const;

  TagType TagTree(const TagType& tag = 0);

  TagType FindBucket(const VecType& query) const;

  void ComputeVariableImportance(arma::vec& importances) const;

  double LogNegativeError(const size_t totalPoints) const;

  bool WithinRange(const VecType& query) const;

 private:
  // The indices in the complete set of points
  // (after all forms of swapping in the original data
  // matrix to align all the points in a node
  // consecutively in the matrix. The 'old_from_new' array
  // maps the points back to their original indices.

  size_t start;
  size_t end;

  StatType maxVals;
  StatType minVals;

  size_t splitDim;

  ElemType splitValue;

  double logNegError;

  double subtreeLeavesLogNegError;

  size_t subtreeLeaves;

  bool root;

  double ratio;

  double logVolume;

  TagType bucketTag;

  double alphaUpper;

  DTree* left;
  DTree* right;

 public:
  size_t Start() const { return start; }
  size_t End() const { return end; }
  size_t SplitDim() const { return splitDim; }
  ElemType SplitValue() const { return splitValue; }
  double LogNegError() const { return logNegError; }
  double SubtreeLeavesLogNegError() const { return subtreeLeavesLogNegError; }
  size_t SubtreeLeaves() const { return subtreeLeaves; }
  double Ratio() const { return ratio; }
  double LogVolume() const { return logVolume; }
  DTree* Left() const { return left; }
  DTree* Right() const { return right; }
  bool Root() const { return root; }
  double AlphaUpper() const { return alphaUpper; }
  TagType BucketTag() const { return subtreeLeaves == 1 ? bucketTag : -1; }

  const StatType& MaxVals() const { return maxVals; }

  const StatType& MinVals() const { return minVals; }

  template<typename Archive>
  void Serialize(Archive& ar, const unsigned int /* version */);

 private:

  // Utility methods.

  bool FindSplit(const MatType& data,
                 size_t& splitDim,
                 ElemType& splitValue,
                 double& leftError,
                 double& rightError,
                 const size_t minLeafSize = 5) const;

  size_t SplitData(MatType& data,
                   const size_t splitDim,
                   const ElemType splitValue,
                   arma::Col<size_t>& oldFromNew) const;

};

} // namespace det
} // namespace mlpack

#include "dtree_impl.hpp"

#endif // MLPACK_METHODS_DET_DTREE_HPP