[mlpack-svn] r16807 - in mlpack/trunk/src/mlpack/core/tree: binary_space_tree cover_tree rectangle_tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Thu Jul 10 10:02:09 EDT 2014
Author: rcurtin
Date: Thu Jul 10 10:02:09 2014
New Revision: 16807
Log:
Add MinimumBoundDistance().
This represents the minimum distance between the center of a node and any edge
of the bound. Note that for ball bounds, this is equivalent to the furthest
descendant distance.
Modified:
mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp Thu Jul 10 10:02:09 2014
@@ -66,8 +66,11 @@
size_t splitDimension;
//! The distance from the centroid of this node to the centroid of the parent.
double parentDistance;
- //! The worst possible distance to the furthest descendant, cached to speed things up.
+ //! The worst possible distance to the furthest descendant, cached to speed
+ //! things up.
double furthestDescendantDistance;
+ //! The minimum distance from the center to any edge of the bound.
+ double minimumBoundDistance;
//! The dataset.
MatType& dataset;
@@ -308,6 +311,9 @@
*/
double FurthestDescendantDistance() const;
+ //! Return the minimum distance from the center of the node to any bound edge.
+ double MinimumBoundDistance() const;
+
//! Return the distance from the center of this node to the center of the
//! parent node.
double ParentDistance() const { return parentDistance; }
Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp Thu Jul 10 10:02:09 2014
@@ -238,6 +238,7 @@
splitDimension(other.splitDimension),
parentDistance(other.parentDistance),
furthestDescendantDistance(other.furthestDescendantDistance),
+ minimumBoundDistance(other.minimumBoundDistance),
dataset(other.dataset)
{
// Create left and right children (if any).
@@ -462,6 +463,17 @@
return furthestDescendantDistance;
}
+//! Return the minimum distance from the center to any bound edge.
+template<typename BoundType,
+ typename StatisticType,
+ typename MatType,
+ typename SplitType>
+inline double BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::
+ MinimumBoundDistance() const
+{
+ return minimumBoundDistance;
+}
+
/**
* Return the specified child.
*/
@@ -560,6 +572,15 @@
// Calculate the furthest descendant distance.
furthestDescendantDistance = 0.5 * bound.Diameter();
+ // Find the minimum distance to any bound edge.
+ minimumBoundDistance = DBL_MAX;
+ for (size_t i = 0; i < bound.Dim(); ++i)
+ {
+ const double dist = std::max(bound[i].Hi() - bound[i].Lo(), 0.0);
+ if (dist < minimumBoundDistance)
+ minimumBoundDistance = dist;
+ }
+
// Now, check if we need to split at all.
if (count <= maxLeafSize)
return; // We can't split this.
@@ -616,6 +637,15 @@
// Calculate the furthest descendant distance.
furthestDescendantDistance = 0.5 * bound.Diameter();
+ // Find the minimum distance to any bound edge.
+ minimumBoundDistance = DBL_MAX;
+ for (size_t i = 0; i < bound.Dim(); ++i)
+ {
+ const double dist = std::max(bound[i].Hi() - bound[i].Lo(), 0.0);
+ if (dist < minimumBoundDistance)
+ minimumBoundDistance = dist;
+ }
+
// First, check if we need to split at all.
if (count <= maxLeafSize)
return; // We can't split this.
Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp Thu Jul 10 10:02:09 2014
@@ -320,6 +320,10 @@
//! descendant.
double& FurthestDescendantDistance() { return furthestDescendantDistance; }
+ //! Get the minimum distance from the center to any bound edge (this is the
+ //! same as furthestDescendantDistance).
+ double MinimumBoundDistance() const { return furthestDescendantDistance; }
+
//! Get the centroid of the node and store it in the given vector.
void Centroid(arma::vec& centroid) const { centroid = dataset.col(point); }
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp Thu Jul 10 10:02:09 2014
@@ -228,7 +228,7 @@
const std::vector<size_t>& Points() const { return points; }
//! Modify the points vector for this node. Be careful!
std::vector<size_t>& Points() { return points; }
-
+
//! Get the local dataset of this node.
const arma::mat& LocalDataset() const { return *localDataset; }
//! Modify the local dataset of this node.
@@ -265,6 +265,11 @@
*/
double FurthestDescendantDistance() const;
+ //! Return the minimum distance from the center to any edge of the bound.
+ //! Currently, this returns 0, which doesn't break algorithms, but it isn't
+ //! necessarily correct, either.
+ double MinimumBoundDistance() const { return 0.0; }
+
//! Return the distance from the center of this node to the center of the
//! parent node.
double ParentDistance() const { return parentDistance; }
More information about the mlpack-svn
mailing list