[mlpack-git] master: Add GetNearestChild() and GetFurthestChild() methods. (632bd37)
gitdub at mlpack.org
gitdub at mlpack.org
Sat Aug 20 14:56:06 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/3274b05fcc545c3b36f783316fea2e22f79c3d03...1c77230c7d3b9c45fb102cd3c632d9c7248e085e
>---------------------------------------------------------------
commit 632bd37f3bb37d6c738e6f9932fa59d734063f58
Author: MarcosPividori <marcos.pividori at gmail.com>
Date: Tue Aug 16 01:47:06 2016 -0300
Add GetNearestChild() and GetFurthestChild() methods.
>---------------------------------------------------------------
632bd37f3bb37d6c738e6f9932fa59d734063f58
.../tree/binary_space_tree/binary_space_tree.hpp | 18 ++++++
.../binary_space_tree/binary_space_tree_impl.hpp | 48 +++++++++++++++
src/mlpack/core/tree/cover_tree/cover_tree.hpp | 18 ++++++
.../core/tree/cover_tree/cover_tree_impl.hpp | 63 +++++++++++++++++++
.../core/tree/rectangle_tree/rectangle_tree.hpp | 18 ++++++
.../tree/rectangle_tree/rectangle_tree_impl.hpp | 70 ++++++++++++++++++++++
src/mlpack/core/tree/spill_tree/spill_tree.hpp | 19 ++++++
.../core/tree/spill_tree/spill_tree_impl.hpp | 48 +++++++++++++++
8 files changed, 302 insertions(+)
diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
index 31f8c04..d7aceca 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
@@ -333,6 +333,24 @@ class BinarySpaceTree
size_t NumChildren() const;
/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ BinarySpaceTree& GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0) const;
+
+ /**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ BinarySpaceTree& GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0) const;
+
+ /**
* Return the furthest distance to a point held in this node. If this is not
* a leaf node, then the distance is 0 because the node holds no points.
*/
diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
index 6059a3c..825d6c0 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
@@ -485,6 +485,54 @@ inline size_t BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
}
/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename BoundMetricType, typename...> class BoundType,
+ template<typename SplitBoundType, typename SplitMatType>
+ class SplitType>
+template<typename VecType>
+BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>&
+BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
+ GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*) const
+{
+ if (IsLeaf())
+ return *this;
+ if (left && (!right || left->MinDistance(point) <= right->MinDistance(point)))
+ return *left;
+ return *right;
+}
+
+/**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename BoundMetricType, typename...> class BoundType,
+ template<typename SplitBoundType, typename SplitMatType>
+ class SplitType>
+template<typename VecType>
+BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>&
+BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
+ GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*) const
+{
+ if (IsLeaf())
+ return *this;
+ if (left && (!right || left->MaxDistance(point) > right->MaxDistance(point)))
+ return *left;
+ return *right;
+}
+
+/**
* Return a bound on the furthest point in the node from the center. This
* returns 0 unless the node is a leaf.
*/
diff --git a/src/mlpack/core/tree/cover_tree/cover_tree.hpp b/src/mlpack/core/tree/cover_tree/cover_tree.hpp
index f75250e..736d432 100644
--- a/src/mlpack/core/tree/cover_tree/cover_tree.hpp
+++ b/src/mlpack/core/tree/cover_tree/cover_tree.hpp
@@ -294,6 +294,24 @@ class CoverTree
//! Modify the statistic for this node.
StatisticType& Stat() { return stat; }
+ /**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ CoverTree& GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0) const;
+
+ /**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ CoverTree& GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0) const;
+
//! Return the minimum distance to another node.
ElemType MinDistance(const CoverTree* other) const;
diff --git a/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp b/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
index 3054324..36ee310 100644
--- a/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
+++ b/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
@@ -606,6 +606,69 @@ CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::Descendant(
return (size_t() - 1);
}
+/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ typename RootPointPolicy>
+template<typename VecType>
+CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>&
+CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*) const
+{
+ if (IsLeaf())
+ return *this;
+
+ double bestDistance = DBL_MAX;
+ size_t bestIndex = 0;
+ for (size_t i = 0; i < children.size(); ++i)
+ {
+ double distance = children[i]->MinDistance(point);
+ if (distance <= bestDistance)
+ {
+ bestDistance = distance;
+ bestIndex = i;
+ }
+ }
+ return *children[bestIndex];
+}
+
+/**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ typename RootPointPolicy>
+template<typename VecType>
+CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>&
+CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::
+ GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*) const
+{
+ if (IsLeaf())
+ return *this;
+
+ double bestDistance = 0;
+ size_t bestIndex = 0;
+ for (size_t i = 0; i < children.size(); ++i)
+ {
+ double distance = children[i]->MaxDistance(point);
+ if (distance >= bestDistance)
+ {
+ bestDistance = distance;
+ bestIndex = i;
+ }
+ }
+ return *children[bestIndex];
+}
+
template<
typename MetricType,
typename StatisticType,
diff --git a/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp b/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
index c694337..b00b572 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
@@ -343,6 +343,24 @@ class RectangleTree
size_t& NumChildren() { return numChildren; }
/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ RectangleTree& GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0) const;
+
+ /**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ RectangleTree& GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0) const;
+
+ /**
* Return the furthest distance to a point held in this node. If this is not
* a leaf node, then the distance is 0 because the node holds no points.
*/
diff --git a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
index 81842ac..6d408d0 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
@@ -564,6 +564,76 @@ inline bool RectangleTree<MetricType, StatisticType, MatType, SplitType,
}
/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ typename SplitType,
+ typename DescentType,
+ template<typename> class AuxiliaryInformationType>
+template<typename VecType>
+RectangleTree<MetricType, StatisticType, MatType, SplitType, DescentType,
+ AuxiliaryInformationType>&
+RectangleTree<MetricType, StatisticType, MatType, SplitType, DescentType,
+ AuxiliaryInformationType>::GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*) const
+{
+ if (IsLeaf())
+ return *this;
+
+ double bestDistance = DBL_MAX;
+ size_t bestIndex = 0;
+ for (size_t i = 0; i < NumChildren(); ++i)
+ {
+ double distance = Child(i).MinDistance(point);
+ if (distance <= bestDistance)
+ {
+ bestDistance = distance;
+ bestIndex = i;
+ }
+ }
+ return Child(bestIndex);
+}
+
+/**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ typename SplitType,
+ typename DescentType,
+ template<typename> class AuxiliaryInformationType>
+template<typename VecType>
+RectangleTree<MetricType, StatisticType, MatType, SplitType, DescentType,
+ AuxiliaryInformationType>&
+RectangleTree<MetricType, StatisticType, MatType, SplitType, DescentType,
+ AuxiliaryInformationType>::GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*) const
+{
+ if (IsLeaf())
+ return *this;
+
+ double bestDistance = 0;
+ size_t bestIndex = 0;
+ for (size_t i = 0; i < NumChildren(); ++i)
+ {
+ double distance = Child(i).MaxDistance(point);
+ if (distance >= bestDistance)
+ {
+ bestDistance = distance;
+ bestIndex = i;
+ }
+ }
+ return Child(bestIndex);
+}
+
+/**
* Return a bound on the furthest point in the node form the centroid.
* This returns 0 unless the node is a leaf.
*/
diff --git a/src/mlpack/core/tree/spill_tree/spill_tree.hpp b/src/mlpack/core/tree/spill_tree/spill_tree.hpp
index e45830f..4a81512 100644
--- a/src/mlpack/core/tree/spill_tree/spill_tree.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_tree.hpp
@@ -265,6 +265,25 @@ class SpillTree
size_t NumChildren() const;
/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ SpillTree& GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0);
+
+ /**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+ template<typename VecType>
+ SpillTree& GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type* = 0);
+
+
+ /**
* Return the furthest distance to a point held in this node. If this is not
* a leaf node, then the distance is 0 because the node holds no points.
*/
diff --git a/src/mlpack/core/tree/spill_tree/spill_tree_impl.hpp b/src/mlpack/core/tree/spill_tree/spill_tree_impl.hpp
index 1776cff..a5774af 100644
--- a/src/mlpack/core/tree/spill_tree/spill_tree_impl.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_tree_impl.hpp
@@ -307,6 +307,54 @@ inline size_t SpillTree<MetricType, StatisticType, MatType, HyperplaneType,
}
/**
+ * Return the nearest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename HyperplaneMetricType> class HyperplaneType,
+ template<typename SplitMetricType, typename SplitMatType>
+ class SplitType>
+template<typename VecType>
+SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>&
+SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
+ GetNearestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*)
+{
+ if (IsLeaf())
+ return *this;
+ if (left && (!right || left->MinDistance(point) <= right->MinDistance(point)))
+ return *left;
+ return *right;
+}
+
+/**
+ * Return the furthest child node to the given query point. If this is a leaf
+ * node, it will return a reference to itself.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename HyperplaneMetricType> class HyperplaneType,
+ template<typename SplitMetricType, typename SplitMatType>
+ class SplitType>
+template<typename VecType>
+SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>&
+SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
+ GetFurthestChild(
+ const VecType& point,
+ typename boost::enable_if<IsVector<VecType> >::type*)
+{
+ if (IsLeaf())
+ return *this;
+ if (left && (!right || left->MaxDistance(point) > right->MaxDistance(point)))
+ return *left;
+ return *right;
+}
+
+/**
* Return a bound on the furthest point in the node from the center. This
* returns 0 unless the node is a leaf.
*/
More information about the mlpack-git
mailing list