HierarchicalClustering.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Hierarchical Clustering.
6  *
7  *
8  *
9  * \author T. Glasmachers
10  * \date 2011
11  *
12  *
13  * \par Copyright 1995-2015 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://image.diku.dk/shark/>
18  *
19  * Shark is free software: you can redistribute it and/or modify
20  * it under the terms of the GNU Lesser General Public License as published
21  * by the Free Software Foundation, either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * Shark is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU Lesser General Public License for more details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
33 //===========================================================================
34 
35 #ifndef SHARK_MODELS_CLUSTERING_HIERARCHICALCLUSTERING_H
36 #define SHARK_MODELS_CLUSTERING_HIERARCHICALCLUSTERING_H
37 
38 
41 
42 
43 namespace shark {
44 
45 
46 ///
47 /// \brief Clusters defined by a binary space partitioning tree.
48 ///
49 /// \par
50 /// Binary space-partitioning is a simple and fast way of
51 /// clustering.
52 ///
53 /// \par
54 /// It is not clear how the unfolding of the tree can be
55 /// expressed as a flat parameter vector. Therefore, the
56 /// parameter vector of this model is empty.
57 ///
58 template < class InputT>
60 {
61 public:
66 
67  /// \brief Constructor
68  ///
69  /// \par
70  /// Construct a hierarchy of clusters from a binary tree.
71  ///
72  /// \param tree tree object underlying the clustering
73  HierarchicalClustering(const tree_type* tree)
74  : mep_tree(tree){
75  SHARK_CHECK(tree, "[HierarchicalClustering] Tree must not be NULL");
76  }
77 
78  /// \brief From INameable: return the class name.
79  std::string name() const
80  { return "HierarchicalClustering"; }
81 
82 
83  /// Return the number of clusters.
84  std::size_t numberOfClusters() const{
85  return (mep_tree->nodes() + 1) / 2;
86  }
87 
88  /// Return the best matching cluster for very pattern in the batch.
89  BatchOutputType hardMembership(BatchInputType const& patterns) const{
90  std::size_t numPatterns = boost::size(patterns);
91  BatchOutputType memberships(numPatterns);
92  for(std::size_t i = 0; i != numPatterns; ++i){
93  tree_type const* tree = mep_tree;
94  memberships(i) = 0;
95  while (tree->hasChildren()){
96  if (tree->isLeft(get(patterns,i))){
97  tree = tree->left();
98  }
99  else{
100  memberships(i) += unsigned((tree->left()->nodes() + 1) / 2);
101  tree = tree->right();
102  }
103  }
104  }
105  return memberships;
106  }
107 
108  /// from IParameterizable
109  RealVector parameterVector() const{
110  return RealVector();
111  }
112 
113  /// from IParameterizable
114  void setParameterVector(RealVector const& newParameters){
115  SHARK_ASSERT(newParameters.size() == 0);
116  }
117 
118  /// from IParameterizable
119  std::size_t numberOfParameters() const{
120  return 0;
121  }
122 
123 protected:
124  /// binary tree
125  tree_type const* mep_tree;
126 };
127 
128 
129 }
130 #endif