mlpack  2.0.1
cosine_tree.hpp
Go to the documentation of this file.
1 
14 #ifndef __MLPACK_CORE_TREE_COSINE_TREE_COSINE_TREE_HPP
15 #define __MLPACK_CORE_TREE_COSINE_TREE_COSINE_TREE_HPP
16 
17 #include <mlpack/core.hpp>
18 #include <boost/heap/priority_queue.hpp>
19 
20 namespace mlpack {
21 namespace tree {
22 
23 // Predeclare classes for CosineNodeQueue typedef.
24 class CompareCosineNode;
25 class CosineTree;
26 
27 // CosineNodeQueue typedef.
28 typedef boost::heap::priority_queue<CosineTree*,
29  boost::heap::compare<CompareCosineNode> > CosineNodeQueue;
30 
31 class CosineTree
32 {
33  public:
42  CosineTree(const arma::mat& dataset);
43 
53  CosineTree(CosineTree& parentNode, const std::vector<size_t>& subIndices);
54 
69  CosineTree(const arma::mat& dataset,
70  const double epsilon,
71  const double delta);
72 
76  ~CosineTree();
77 
87  void ModifiedGramSchmidt(CosineNodeQueue& treeQueue,
88  arma::vec& centroid,
89  arma::vec& newBasisVector,
90  arma::vec* addBasisVector = NULL);
91 
104  double MonteCarloError(CosineTree* node,
105  CosineNodeQueue& treeQueue,
106  arma::vec* addBasisVector1 = NULL,
107  arma::vec* addBasisVector2 = NULL);
108 
114  void ConstructBasis(CosineNodeQueue& treeQueue);
115 
121  void CosineNodeSplit();
122 
129  void ColumnSamplesLS(std::vector<size_t>& sampledIndices,
130  arma::vec& probabilities, size_t numSamples);
131 
138  size_t ColumnSampleLS();
139 
152  size_t BinarySearch(arma::vec& cDistribution, double value, size_t start,
153  size_t end);
154 
162  void CalculateCosines(arma::vec& cosines);
163 
168  void CalculateCentroid();
169 
171  void GetFinalBasis(arma::mat& finalBasis) { finalBasis = basis; }
172 
174  const arma::mat& GetDataset() const { return dataset; }
175 
177  std::vector<size_t>& VectorIndices() { return indices; }
178 
180  void L2Error(const double error) { this->l2Error = error; }
182  double L2Error() const { return l2Error; }
183 
185  arma::vec& Centroid() { return centroid; }
186 
188  void BasisVector(arma::vec& bVector) { this->basisVector = bVector; }
189 
191  arma::vec& BasisVector() { return basisVector; }
192 
194  CosineTree* Parent() const { return parent; }
196  CosineTree*& Parent() { return parent; }
197 
199  CosineTree* Left() const { return left; }
201  CosineTree*& Left() { return left; }
202 
204  CosineTree* Right() const { return right; }
206  CosineTree*& Right() { return right; }
207 
209  size_t NumColumns() const { return numColumns; }
210 
212  double FrobNormSquared() const { return frobNormSquared; }
213 
215  size_t SplitPointIndex() const { return indices[splitPointIndex]; }
216 
217  private:
219  const arma::mat& dataset;
221  double delta;
223  arma::mat basis;
225  CosineTree* parent;
227  CosineTree* left;
229  CosineTree* right;
231  std::vector<size_t> indices;
233  arma::vec l2NormsSquared;
235  arma::vec centroid;
237  arma::vec basisVector;
241  size_t numColumns;
243  double l2Error;
246 };
247 
249 {
250  public:
251 
252  // Comparison function for construction of priority queue.
253  bool operator() (const CosineTree* a, const CosineTree* b) const
254  {
255  return a->L2Error() < b->L2Error();
256  }
257 };
258 
259 } // namespace tree
260 } // namespace mlpack
261 
262 #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.
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.
CosineTree * Right() const
Get pointer to the right child of 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.
CosineTree *& Parent()
Modify the pointer to the parent node.
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()
Clean up the CosineTree: release allocated memory (including children).
CosineTree * Left() const
Get pointer to the left child of the node.
bool operator()(const CosineTree *a, const CosineTree *b) const
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() const
Get pointer to the parent node.
CosineTree * parent
Parent of the node.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
arma::vec basisVector
Orthonormalized basis vector of the node.
CosineTree * right
Right child of the node.
CosineTree *& Right()
Modify the pointer to the left 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.
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:25
double l2Error
Monte Carlo error for this node.
arma::mat basis
Subspace basis of the input dataset.
CosineTree *& Left()
Modify the pointer to the left child of the node.
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.