[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