[mlpack-svn] r13401 - mlpack/trunk/src/mlpack/core/tree/cover_tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Aug 15 13:29:25 EDT 2012
Author: rcurtin
Date: 2012-08-15 13:29:25 -0400 (Wed, 15 Aug 2012)
New Revision: 13401
Modified:
mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
Log:
Change expansion constant to base (#240).
Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp 2012-08-15 17:09:11 UTC (rev 13400)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp 2012-08-15 17:29:25 UTC (rev 13401)
@@ -32,7 +32,7 @@
* - separation: all nodes in level C_i have distance greater than EC^i to all
* other nodes in level C_i.
*
- * The value 'EC' refers to the expansion constant, which is a parameter of the
+ * The value 'EC' refers to the base, which is a parameter of the
* tree. These three properties make the cover tree very good for fast,
* high-dimensional nearest-neighbor search.
*
@@ -91,16 +91,15 @@
typedef arma::mat Mat;
/**
- * Create the cover tree with the given dataset and given expansion constant.
+ * Create the cover tree with the given dataset and given base.
* The dataset will not be modified during the building procedure (unlike
* BinarySpaceTree).
*
* @param dataset Reference to the dataset to build a tree on.
- * @param expansionConstant Expansion constant (EC) to use during tree
- * building (default 2.0).
+ * @param base Base to use during tree building (default 2.0).
*/
CoverTree(const arma::mat& dataset,
- const double expansionConstant = 2.0,
+ const double base = 2.0,
MetricType* metric = NULL);
/**
@@ -119,8 +118,7 @@
* as small as possible, or you may be creating an implicit node in your tree.
*
* @param dataset Reference to the dataset to build a tree on.
- * @param expansionConstant Expansion constant (EC) to use during tree
- * building.
+ * @param base Base to use during tree building.
* @param pointIndex Index of the point this node references.
* @param scale Scale of this level in the tree.
* @param indices Array of indices, ordered [ nearSet | farSet | usedSet ];
@@ -134,7 +132,7 @@
* @param usedSetSize The number of points used will be added to this number.
*/
CoverTree(const arma::mat& dataset,
- const double expansionConstant,
+ const double base,
const size_t pointIndex,
const int scale,
const double parentDistance,
@@ -194,10 +192,10 @@
//! Modify the scale of this node. Be careful...
int& Scale() { return scale; }
- //! Get the expansion constant.
- double ExpansionConstant() const { return expansionConstant; }
- //! Modify the expansion constant; don't do this, you'll break everything.
- double& ExpansionConstant() { return expansionConstant; }
+ //! Get the base.
+ double Base() const { return base; }
+ //! Modify the base; don't do this, you'll break everything.
+ double& Base() { return base; }
//! Get the statistic for this node.
const StatisticType& Stat() const { return stat; }
@@ -255,8 +253,8 @@
//! Scale level of the node.
int scale;
- //! The expansion constant used to construct the tree.
- double expansionConstant;
+ //! The base used to construct the tree.
+ double base;
//! The instantiated statistic.
StatisticType stat;
Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp 2012-08-15 17:09:11 UTC (rev 13400)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp 2012-08-15 17:29:25 UTC (rev 13401)
@@ -17,11 +17,11 @@
template<typename MetricType, typename RootPointPolicy, typename StatisticType>
CoverTree<MetricType, RootPointPolicy, StatisticType>::CoverTree(
const arma::mat& dataset,
- const double expansionConstant,
+ const double base,
MetricType* metric) :
dataset(dataset),
point(RootPointPolicy::ChooseRoot(dataset)),
- expansionConstant(expansionConstant),
+ base(base),
parentDistance(0),
furthestDescendantDistance(0)
{
@@ -48,8 +48,8 @@
// Now determine the scale factor of the root node.
const double maxDistance = max(distances);
- scale = (int) ceil(log(maxDistance) / log(expansionConstant));
- const double bound = pow(expansionConstant, scale - 1);
+ scale = (int) ceil(log(maxDistance) / log(base));
+ const double bound = pow(base, scale - 1);
// Unfortunately, we can't call out to other constructors, so we have to copy
// a little bit of code from the other constructor. First we build the self
@@ -58,7 +58,7 @@
dataset.n_cols - 1);
size_t childFarSetSize = (dataset.n_cols - 1) - childNearSetSize;
size_t usedSetSize = 0;
- children.push_back(new CoverTree(dataset, expansionConstant, point, scale - 1,
+ children.push_back(new CoverTree(dataset, base, point, scale - 1,
0, indices, distances, childNearSetSize, childFarSetSize, usedSetSize,
*metric));
@@ -114,7 +114,7 @@
{
size_t childNearSetSize = 0;
size_t childFarSetSize = 0;
- children.push_back(new CoverTree(dataset, expansionConstant,
+ children.push_back(new CoverTree(dataset, base,
indices[0], scale - 1, distances[0], indices, distances,
childNearSetSize, childFarSetSize, usedSetSize, *metric));
@@ -142,7 +142,7 @@
// Build this child (recursively).
childUsedSetSize = 1; // Mark self point as used.
childFarSetSize = ((nearSetSize - 1) - childNearSetSize);
- children.push_back(new CoverTree(dataset, expansionConstant, indices[0],
+ children.push_back(new CoverTree(dataset, base, indices[0],
scale - 1, distances[0], childIndices, childDistances, childNearSetSize,
childFarSetSize, childUsedSetSize, *metric));
@@ -179,7 +179,7 @@
if (distances[i] > furthestDescendantDistance)
furthestDescendantDistance = distances[i];
- Log::Assert(furthestDescendantDistance <= pow(expansionConstant, scale + 1));
+ Log::Assert(furthestDescendantDistance <= pow(base, scale + 1));
if (localMetric)
delete metric;
@@ -188,7 +188,7 @@
template<typename MetricType, typename RootPointPolicy, typename StatisticType>
CoverTree<MetricType, RootPointPolicy, StatisticType>::CoverTree(
const arma::mat& dataset,
- const double expansionConstant,
+ const double base,
const size_t pointIndex,
const int scale,
const double parentDistance,
@@ -201,7 +201,7 @@
dataset(dataset),
point(pointIndex),
scale(scale),
- expansionConstant(expansionConstant),
+ base(base),
parentDistance(parentDistance),
furthestDescendantDistance(0)
{
@@ -227,14 +227,14 @@
// Make the self child at the lowest possible level.
// This should not modify farSetSize or usedSetSize.
size_t tempSize = 0;
- children.push_back(new CoverTree(dataset, expansionConstant, pointIndex,
+ children.push_back(new CoverTree(dataset, base, pointIndex,
INT_MIN, 0, indices, distances, 0, tempSize, usedSetSize, metric));
// Every point in the near set should be a leaf.
for (size_t i = 0; i < nearSetSize; ++i)
{
// farSetSize and usedSetSize will not be modified.
- children.push_back(new CoverTree(dataset, expansionConstant, indices[i],
+ children.push_back(new CoverTree(dataset, base, indices[i],
INT_MIN, 0, indices, distances, 0, tempSize, usedSetSize, metric));
usedSetSize++;
}
@@ -249,8 +249,8 @@
}
const int nextScale = std::min(scale,
- (int) ceil(log(maxDistance) / log(expansionConstant))) - 1;
- const double bound = pow(expansionConstant, nextScale);
+ (int) ceil(log(maxDistance) / log(base))) - 1;
+ const double bound = pow(base, nextScale);
// This needs to be taken out. It's a sanity check for now.
Log::Assert(nextScale < scale);
@@ -263,7 +263,7 @@
// Build the self child (recursively).
size_t childFarSetSize = nearSetSize - childNearSetSize;
size_t childUsedSetSize = 0;
- children.push_back(new CoverTree(dataset, expansionConstant, pointIndex,
+ children.push_back(new CoverTree(dataset, base, pointIndex,
nextScale, 0, indices, distances, childNearSetSize, childFarSetSize,
childUsedSetSize, metric));
@@ -331,7 +331,7 @@
if ((nearSetSize == 1) && (farSetSize == 0))
{
size_t childNearSetSize = 0;
- children.push_back(new CoverTree(dataset, expansionConstant,
+ children.push_back(new CoverTree(dataset, base,
indices[0], nextScale, distances[0], indices, distances,
childNearSetSize, farSetSize, usedSetSize, metric));
@@ -359,7 +359,7 @@
childNearSetSize = SplitNearFar(childIndices, childDistances, bound,
nearSetSize + farSetSize - 1);
childFarSetSize = PruneFarSet(childIndices, childDistances,
- expansionConstant * bound, childNearSetSize,
+ base * bound, childNearSetSize,
(nearSetSize + farSetSize - 1));
// Now that we know the near and far set sizes, we can put the used point
@@ -371,7 +371,7 @@
// Build this child (recursively).
childUsedSetSize = 1; // Mark self point as used.
- children.push_back(new CoverTree(dataset, expansionConstant, indices[0],
+ children.push_back(new CoverTree(dataset, base, indices[0],
nextScale, distances[0], childIndices, childDistances, childNearSetSize,
childFarSetSize, childUsedSetSize, metric));
@@ -408,7 +408,7 @@
if (distances[i] > furthestDescendantDistance)
furthestDescendantDistance = distances[i];
- Log::Assert(furthestDescendantDistance <= pow(expansionConstant, scale + 1));
+ Log::Assert(furthestDescendantDistance <= pow(base, scale + 1));
}
template<typename MetricType, typename RootPointPolicy, typename StatisticType>
More information about the mlpack-svn
mailing list