[mlpack-git] master: Add new utility functions for coalescion. Is coalescion even a word? (334d8df)

gitdub at big.cc.gt.atl.ga.us gitdub at big.cc.gt.atl.ga.us
Wed May 20 23:06:22 EDT 2015


Repository : https://github.com/mlpack/mlpack

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/77d750c8fd46140b1d6060424f68768a21c89377...7e9cd46afb53817ae93ccbd02637d7726137ce4d

>---------------------------------------------------------------

commit 334d8df46b7cfc944185cf8f37d3a5f3d2740212
Author: Ryan Curtin <ryan at ratml.org>
Date:   Wed May 20 23:01:17 2015 -0400

    Add new utility functions for coalescion.
    Is coalescion even a word?


>---------------------------------------------------------------

334d8df46b7cfc944185cf8f37d3a5f3d2740212
 src/mlpack/methods/kmeans/dual_tree_kmeans.hpp     | 36 +++++++++-
 .../methods/kmeans/dual_tree_kmeans_impl.hpp       | 82 ++++++++++++++++++----
 .../methods/kmeans/dual_tree_kmeans_statistic.hpp  |  2 +
 3 files changed, 103 insertions(+), 17 deletions(-)

diff --git a/src/mlpack/methods/kmeans/dual_tree_kmeans.hpp b/src/mlpack/methods/kmeans/dual_tree_kmeans.hpp
index ae9cb71..a0c69a7 100644
--- a/src/mlpack/methods/kmeans/dual_tree_kmeans.hpp
+++ b/src/mlpack/methods/kmeans/dual_tree_kmeans.hpp
@@ -115,12 +115,42 @@ class DualTreeKMeans
   void DecoalesceTree(TreeType& node);
 };
 
-//! A template typedef for the DualTreeKMeans algorithm with the default tree type
-//! (a kd-tree).
+//! Utility function for hiding children.  This actually does something, and is
+//! called if the tree is not a binary tree.
+template<typename TreeType>
+void HideChild(TreeType& node,
+               const size_t child,
+               const typename boost::disable_if_c<
+                   tree::TreeTraits<TreeType>::BinaryTree>::type* junk = 0);
+
+//! Utility function for hiding children.  This is called when the tree is a
+//! binary tree, and does nothing, because we don't hide binary children in this
+//! way.
+template<typename TreeType>
+void HideChild(TreeType& node,
+               const size_t child,
+               const typename boost::enable_if_c<
+                   tree::TreeTraits<TreeType>::BinaryTree>::type* junk = 0);
+
+//! Utility function for restoring children to a non-binary tree.
+template<typename TreeType>
+void RestoreChildren(TreeType& node,
+                     const typename boost::disable_if_c<tree::TreeTraits<
+                         TreeType>::BinaryTree>::type* junk = 0);
+
+//! Utility function for restoring children to a binary tree.
+template<typename TreeType>
+void RestoreChildren(TreeType& node,
+                     const typename boost::enable_if_c<tree::TreeTraits<
+                         TreeType>::BinaryTree>::type* junk = 0);
+
+//! A template typedef for the DualTreeKMeans algorithm with the default tree
+//! type (a kd-tree).
 template<typename MetricType, typename MatType>
 using DefaultDualTreeKMeans = DualTreeKMeans<MetricType, MatType>;
 
-//! A template typedef for the DualTreeKMeans algorithm with the cover tree type.
+//! A template typedef for the DualTreeKMeans algorithm with the cover tree
+//! type.
 template<typename MetricType, typename MatType>
 using CoverTreeDualTreeKMeans = DualTreeKMeans<MetricType, MatType,
     tree::CoverTree<metric::EuclideanDistance, tree::FirstPointIsRoot,
diff --git a/src/mlpack/methods/kmeans/dual_tree_kmeans_impl.hpp b/src/mlpack/methods/kmeans/dual_tree_kmeans_impl.hpp
index 71ffe2d..cee17b6 100644
--- a/src/mlpack/methods/kmeans/dual_tree_kmeans_impl.hpp
+++ b/src/mlpack/methods/kmeans/dual_tree_kmeans_impl.hpp
@@ -562,29 +562,27 @@ void DualTreeKMeans<MetricType, MatType, TreeType>::CoalesceTree(
   if (node.Parent() != NULL)
   {
     // First, we should coalesce those nodes that aren't statically pruned.
-    size_t numStaticallyPruned = 0;
-    size_t notPrunedIndex = 0;
-    for (size_t i = 0; i < node.NumChildren(); ++i)
+    for (size_t i = node.NumChildren() - 1; i > 0; --i)
     {
       if (node.Child(i).Stat().StaticPruned())
-      {
-        ++numStaticallyPruned;
-      }
+        HideChild(node, i);
       else
-      {
         CoalesceTree(node.Child(i), i);
-        notPrunedIndex = i;
-      }
     }
 
+    if (node.Child(0).Stat().StaticPruned())
+      HideChild(node, 0);
+    else
+      CoalesceTree(node.Child(0), 0);
+
     // If we've pruned all but one child, then notPrunedIndex will contain the
     // index of that child, and we can coalesce this node entirely.  Note that
     // the case where all children are statically pruned should not happen,
     // because then this node should itself be statically pruned.
-    if (numStaticallyPruned == node.NumChildren() - 1)
+    if (node.NumChildren() == 1)
     {
-      node.Child(notPrunedIndex).Parent() = node.Parent();
-      node.Parent()->ChildPtr(child) = node.ChildPtr(notPrunedIndex);
+      node.Child(0).Parent() = node.Parent();
+      node.Parent()->ChildPtr(child) = node.ChildPtr(0);
     }
   }
   else
@@ -601,13 +599,69 @@ void DualTreeKMeans<MetricType, MatType, TreeType>::DecoalesceTree(
     TreeType& node)
 {
   node.Parent() = (TreeType*) node.Stat().TrueParent();
-  for (size_t i = 0; i < node.NumChildren(); ++i)
-    node.ChildPtr(i) = (TreeType*) node.Stat().TrueChild(i);
+  RestoreChildren(node);
 
   for (size_t i = 0; i < node.NumChildren(); ++i)
     DecoalesceTree(node.Child(i));
 }
 
+//! Utility function for hiding children in a non-binary tree.
+template<typename TreeType>
+void HideChild(TreeType& node,
+               const size_t child,
+               const typename boost::disable_if_c<
+                   tree::TreeTraits<TreeType>::BinaryTree>::type*)
+{
+  // We're going to assume we have a Children() function open to us.  If we
+  // don't, then this won't work, I guess...
+  node.Children().erase(node.Children().begin() + child);
+}
+
+//! Utility function for hiding children in a binary tree.
+template<typename TreeType>
+void HideChild(TreeType& node,
+               const size_t child,
+               const typename boost::enable_if_c<
+                   tree::TreeTraits<TreeType>::BinaryTree>::type*)
+{
+  // If we're hiding the left child, then take the right child as the new left
+  // child.
+  if (child == 0)
+  {
+    node.ChildPtr(0) = node.ChildPtr(1);
+    node.ChildPtr(1) = NULL;
+  }
+  else
+  {
+    node.ChildPtr(1) = NULL;
+  }
+}
+
+//! Utility function for restoring children in a non-binary tree.
+template<typename TreeType>
+void RestoreChildren(TreeType& node,
+                     const typename boost::disable_if_c<
+                         tree::TreeTraits<TreeType>::BinaryTree>::type*)
+{
+  node.Children().clear();
+  node.Children().resize(node.Stat().NumTrueChildren());
+  for (size_t i = 0; i < node.Stat().NumTrueChildren(); ++i)
+    node.Children()[i] = (TreeType*) node.Stat().TrueChild(i);
+}
+
+//! Utility function for restoring children in a binary tree.
+template<typename TreeType>
+void RestoreChildren(TreeType& node,
+                     const typename boost::enable_if_c<
+                         tree::TreeTraits<TreeType>::BinaryTree>::type*)
+{
+  if (node.Stat().NumTrueChildren() > 0)
+  {
+    node.ChildPtr(0) = (TreeType*) node.Stat().TrueChild(0);
+    node.ChildPtr(1) = (TreeType*) node.Stat().TrueChild(1);
+  }
+}
+
 } // namespace kmeans
 } // namespace mlpack
 
diff --git a/src/mlpack/methods/kmeans/dual_tree_kmeans_statistic.hpp b/src/mlpack/methods/kmeans/dual_tree_kmeans_statistic.hpp
index 8209860..4ef586a 100644
--- a/src/mlpack/methods/kmeans/dual_tree_kmeans_statistic.hpp
+++ b/src/mlpack/methods/kmeans/dual_tree_kmeans_statistic.hpp
@@ -97,6 +97,8 @@ class DualTreeKMeansStatistic : public
   void* TrueChild(const size_t i) const { return trueChildren[i]; }
   void*& TrueChild(const size_t i) { return trueChildren[i]; }
 
+  size_t NumTrueChildren() const { return trueChildren.size(); }
+
   std::string ToString() const
   {
     std::ostringstream o;



More information about the mlpack-git mailing list