MLPACK  1.0.11
cosine_tree.hpp
Go to the documentation of this file.
1 
23 #ifndef __MLPACK_CORE_TREE_COSINE_TREE_COSINE_TREE_HPP
24 #define __MLPACK_CORE_TREE_COSINE_TREE_COSINE_TREE_HPP
25 
26 #include <mlpack/core.hpp>
27 #include <boost/heap/priority_queue.hpp>
28 
29 namespace mlpack {
30 namespace tree {
31 
32 // Predeclare classes for CosineNodeQueue typedef.
33 class CompareCosineNode;
34 class CosineTree;
35 
36 // CosineNodeQueue typedef.
37 typedef boost::heap::priority_queue<CosineTree*,
38  boost::heap::compare<CompareCosineNode> > CosineNodeQueue;
39 
40 class CosineTree
41 {
42  public:
43 
52  CosineTree(const arma::mat& dataset);
53 
63  CosineTree(CosineTree& parentNode, const std::vector<size_t>& subIndices);
64 
79  CosineTree(const arma::mat& dataset,
80  const double epsilon,
81  const double delta);
82 
87  ~CosineTree();
88 
98  void ModifiedGramSchmidt(CosineNodeQueue& treeQueue,
99  arma::vec& centroid,
100  arma::vec& newBasisVector,
101  arma::vec* addBasisVector = NULL);
102 
115  double MonteCarloError(CosineTree* node,
116  CosineNodeQueue& treeQueue,
117  arma::vec* addBasisVector1 = NULL,
118  arma::vec* addBasisVector2 = NULL);
119 
125  void ConstructBasis(CosineNodeQueue& treeQueue);
126 
132  void CosineNodeSplit();
133 
140  void ColumnSamplesLS(std::vector<size_t>& sampledIndices,
141  arma::vec& probabilities, size_t numSamples);
142 
149  size_t ColumnSampleLS();
150 
163  size_t BinarySearch(arma::vec& cDistribution, double value, size_t start,
164  size_t end);
165 
173  void CalculateCosines(arma::vec& cosines);
174 
179  void CalculateCentroid();
180 
182  void GetFinalBasis(arma::mat& finalBasis) { finalBasis = basis; }
183 
185  const arma::mat& GetDataset() const { return dataset; }
186 
188  std::vector<size_t>& VectorIndices() { return indices; }
189 
191  void L2Error(const double error) { this->l2Error = error; }
192 
194  double L2Error() const { return l2Error; }
195 
197  arma::vec& Centroid() { return centroid; }
198 
200  void BasisVector(arma::vec& bVector) { this->basisVector = bVector; }
201 
203  arma::vec& BasisVector() { return basisVector; }
204 
206  CosineTree* Left() { return left; }
207 
209  CosineTree* Right() { return right; }
210 
212  size_t NumColumns() const { return numColumns; }
213 
215  double FrobNormSquared() const { return frobNormSquared; }
216 
218  size_t SplitPointIndex() const { return indices[splitPointIndex]; }
219 
220  private:
222  const arma::mat& dataset;
224  double epsilon;
226  double delta;
228  arma::mat basis;
230  CosineTree* parent;
232  CosineTree* left;
234  CosineTree* right;
236  std::vector<size_t> indices;
238  arma::vec l2NormsSquared;
240  arma::vec centroid;
242  arma::vec basisVector;
246  size_t numColumns;
248  double l2Error;
251 };
252 
254 {
255  public:
256 
257  // Comparison function for construction of priority queue.
258  bool operator() (const CosineTree* a, const CosineTree* b) const
259  {
260  return a->L2Error() < b->L2Error();
261  }
262 };
263 
264 }; // namespace tree
265 }; // namespace mlpack
266 
267 #endif
void CalculateCosines(arma::vec &cosines)
Calculate cosines of the columns present in the node, with respect to the sampled splitting point...
CosineTree * left
Left child of the node.
std::vector< size_t > indices
Indices of columns of input matrix in the node.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:31
size_t numColumns
Number of columns of input matrix in the node.
arma::vec l2NormsSquared
L2-norm squared of columns in the node.
size_t SplitPointIndex() const
Get the column index of split point of the node.
double FrobNormSquared() const
Get the Frobenius norm squared of columns in the node.
void CosineNodeSplit()
This function splits the cosine node into two children based on the cosines of the columns contained ...
double MonteCarloError(CosineTree *node, CosineNodeQueue &treeQueue, arma::vec *addBasisVector1=NULL, arma::vec *addBasisVector2=NULL)
Estimates the squared error of the projection of the input node's matrix onto the current vector subs...
size_t splitPointIndex
Index of split point of cosine node.
void GetFinalBasis(arma::mat &finalBasis)
Returns the basis of the constructed subspace.
size_t ColumnSampleLS()
Sample a point from the Length-Squared distribution of the cosine node.
arma::vec centroid
Centroid of columns of input matrix in the node.
const arma::mat & dataset
Matrix for which cosine tree is constructed.
arma::vec & Centroid()
Get pointer to the centroid vector.
void ConstructBasis(CosineNodeQueue &treeQueue)
Constructs the final basis matrix, after the cosine tree construction.
~CosineTree()
Destroy the cosine tree and all of its children (take care of the memory allocations too)...
double epsilon
Error tolerance fraction for calculated subspace.
bool operator()(const CosineTree *a, const CosineTree *b) const
CosineTree * Left()
Get pointer to the left child of the node.
CosineTree(const arma::mat &dataset)
CosineTree constructor for the root node of the tree.
void BasisVector(arma::vec &bVector)
Set the basis vector of the node.
size_t BinarySearch(arma::vec &cDistribution, double value, size_t start, size_t end)
Sample a column based on the cumulative Length-Squared distribution of the cosine node...
arma::vec & BasisVector()
Get the basis vector of the node.
void CalculateCentroid()
Calculate centroid of the columns present in the node.
CosineTree * parent
Parent of the node.
arma::vec basisVector
Orthonormalized basis vector of the node.
CosineTree * right
Right child of the node.
double L2Error() const
Get the Monte Carlo error.
size_t NumColumns() const
Get number of columns of input matrix in the node.
CosineTree * Right()
Get pointer to the right child of the node.
void ModifiedGramSchmidt(CosineNodeQueue &treeQueue, arma::vec &centroid, arma::vec &newBasisVector, arma::vec *addBasisVector=NULL)
Calculates the orthonormalization of the passed centroid, with respect to the current vector subspace...
boost::heap::priority_queue< CosineTree *, boost::heap::compare< CompareCosineNode > > CosineNodeQueue
Definition: cosine_tree.hpp:34
double l2Error
Monte Carlo error for this node.
arma::mat basis
Subspace basis of the input dataset.
double frobNormSquared
Frobenius norm squared of columns in the node.
void ColumnSamplesLS(std::vector< size_t > &sampledIndices, arma::vec &probabilities, size_t numSamples)
Sample 'numSamples' points from the Length-Squared distribution of the cosine node.
void L2Error(const double error)
Set the Monte Carlo error.
const arma::mat & GetDataset() const
Get pointer to the dataset matrix.
std::vector< size_t > & VectorIndices()
Get the indices of columns in the node.
double delta
Cumulative probability for Monte Carlo error lower bound.