Main MRPT website > C++ reference
MRPT logo
kmeans.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 #ifndef mrpt_math_kmeans_H
29 #define mrpt_math_kmeans_H
30 
31 #include <mrpt/math/CMatrixTemplateNumeric.h>
32 #include <mrpt/math/CMatrixFixedNumeric.h>
33 
34 namespace mrpt
35 {
36  namespace math
37  {
38  namespace detail {
39  // Auxiliary method: templatized for working with float/double's.
40  template <typename SCALAR>
41  double BASE_IMPEXP internal_kmeans(
42  const bool use_kmeansplusplus_method,
43  const size_t nPoints,
44  const size_t k,
45  const size_t dims,
46  const SCALAR *points,
47  const size_t attempts,
48  SCALAR* out_center,
49  int *out_assignments
50  );
51 
52  // Auxiliary method, the actual code of the two front-end functions offered to the user below.
53  template <class LIST_OF_VECTORS1,class LIST_OF_VECTORS2>
54  double stub_kmeans(
55  const bool use_kmeansplusplus_method,
56  const size_t k,
57  const LIST_OF_VECTORS1 & points,
58  std::vector<int> &assignments,
59  LIST_OF_VECTORS2 *out_centers,
60  const size_t attempts
61  )
62  {
63  MRPT_START
64  ASSERT_(k>=1)
65  const size_t N = points.size();
66  assignments.resize(N);
67  if (out_centers) out_centers->clear();
68  if (!N)
69  return 0; // No points, we're done.
70  // Parse to required format:
71  size_t dims=0;
72  const typename LIST_OF_VECTORS1::const_iterator it_first=points.begin();
73  const typename LIST_OF_VECTORS1::const_iterator it_end =points.end();
74  typedef typename LIST_OF_VECTORS1::value_type TInnerVector;
75  typedef typename LIST_OF_VECTORS2::value_type TInnerVectorCenters;
76  std::vector<typename TInnerVector::value_type> raw_vals;
77  typename TInnerVector::value_type *trg_ptr=NULL;
78  for (typename LIST_OF_VECTORS1::const_iterator it=it_first;it!=it_end;++it)
79  {
80  if (it==it_first)
81  {
82  dims = it->size();
83  ASSERTMSG_(dims>0,"Dimensionality of points can't be zero.")
84  raw_vals.resize(N*dims);
85  trg_ptr = &raw_vals[0];
86  }
87  else
88  {
89  ASSERTMSG_(size_t(dims)==size_t(it->size()),"All points must have the same dimensionality.")
90  }
91 
92  ::memcpy(trg_ptr, &(*it)[0], dims*sizeof(typename TInnerVector::value_type));
93  trg_ptr+=dims;
94  }
95  // Call the internal implementation:
96  std::vector<typename TInnerVectorCenters::value_type> centers(dims*k);
97  const double ret = detail::internal_kmeans(false,N,k,points.begin()->size(),&raw_vals[0],attempts,&centers[0],&assignments[0]);
98  // Centers:
99  if (out_centers)
100  {
101  const typename TInnerVectorCenters::value_type *center_ptr = &centers[0];
102  for (size_t i=0;i<k;i++)
103  {
104  TInnerVectorCenters c;
105  c.resize(dims);
106  for (size_t j=0;j<dims;j++) c[j]= *center_ptr++;
107  out_centers->push_back(c);
108  }
109  }
110  return ret;
111  MRPT_END
112  }
113  } // end detail namespace
114 
115 
116  /** @name k-means algorithms
117  @{ */
118 
119  /** k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters.
120  * The list of input points can be any template CONTAINER<POINT> with:
121  * - CONTAINER can be: Any STL container: std::vector,std::list,std::deque,...
122  * - POINT can be:
123  * - std::vector<double/float>
124  * - CArrayDouble<N> / CArrayFloat<N>
125  *
126  * \param k [IN] Number of cluster to look for.
127  * \param points [IN] The list of N input points. It can be any STL-like containers of std::vector<float/double>, for example a std::vector<vector_double>, a std::list<vector_float>, etc...
128  * \param assignments [OUT] At output it will have a number [0,k-1] for each of the N input points.
129  * \param out_centers [OUT] If not NULL, at output will have the centers of each group. Can be of any of the supported types of "points", but the basic coordinates should be float or double exactly as in "points".
130  * \param attempts [IN] Number of attempts.
131  *
132  * \sa A more advanced algorithm, see: kmeanspp
133  * \note Uses the kmeans++ implementation by David Arthur (2009, http://www.stanford.edu/~darthur/kmpp.zip).
134  */
135  template <class LIST_OF_VECTORS1,class LIST_OF_VECTORS2>
136  inline double kmeans(
137  const size_t k,
138  const LIST_OF_VECTORS1 & points,
139  std::vector<int> &assignments,
140  LIST_OF_VECTORS2 *out_centers = NULL,
141  const size_t attempts = 3
142  )
143  {
144  return detail::stub_kmeans(false /* standard method */, k,points,assignments,out_centers,attempts);
145  }
146 
147  /** k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters.
148  * The list of input points can be any template CONTAINER<POINT> with:
149  * - CONTAINER can be: Any STL container: std::vector,std::list,std::deque,...
150  * - POINT can be:
151  * - std::vector<double/float>
152  * - CArrayDouble<N> / CArrayFloat<N>
153  *
154  * \param k [IN] Number of cluster to look for.
155  * \param points [IN] The list of N input points. It can be any STL-like containers of std::vector<float/double>, for example a std::vector<vector_double>, a std::list<vector_float>, etc...
156  * \param assignments [OUT] At output it will have a number [0,k-1] for each of the N input points.
157  * \param out_centers [OUT] If not NULL, at output will have the centers of each group. Can be of any of the supported types of "points", but the basic coordinates should be float or double exactly as in "points".
158  * \param attempts [IN] Number of attempts.
159  *
160  * \sa The standard kmeans algorithm, see: kmeans
161  * \note Uses the kmeans++ implementation by David Arthur (2009, http://www.stanford.edu/~darthur/kmpp.zip).
162  */
163  template <class LIST_OF_VECTORS1,class LIST_OF_VECTORS2>
164  inline double kmeanspp(
165  const size_t k,
166  const LIST_OF_VECTORS1 & points,
167  std::vector<int> &assignments,
168  LIST_OF_VECTORS2 *out_centers = NULL,
169  const size_t attempts = 3
170  )
171  {
172  return detail::stub_kmeans(true /* kmeans++ algorithm*/, k,points,assignments,out_centers,attempts);
173  }
174 
175  /** @} */
176 
177  } // End of MATH namespace
178 } // End of namespace
179 #endif


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013