Main MRPT website > C++ reference for MRPT 1.5.7
include/mrpt/math/kmeans.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | http://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2017, Individual contributors, see AUTHORS file |
6  | See: http://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See details in http://www.mrpt.org/License |
8  +---------------------------------------------------------------------------+ */
9 #ifndef mrpt_math_kmeans_H
10 #define mrpt_math_kmeans_H
11 
14 
15 namespace mrpt
16 {
17  namespace math
18  {
19  namespace detail {
20  // Auxiliary method: templatized for working with float/double's.
21  template <typename SCALAR>
23  const bool use_kmeansplusplus_method,
24  const size_t nPoints,
25  const size_t k,
26  const size_t dims,
27  const SCALAR *points,
28  const size_t attempts,
29  SCALAR* out_center,
30  int *out_assignments
31  );
32 
33  // Auxiliary method, the actual code of the two front-end functions offered to the user below.
34  template <class LIST_OF_VECTORS1,class LIST_OF_VECTORS2>
35  double stub_kmeans(
36  const bool use_kmeansplusplus_method,
37  const size_t k,
38  const LIST_OF_VECTORS1 & points,
39  std::vector<int> &assignments,
40  LIST_OF_VECTORS2 *out_centers,
41  const size_t attempts
42  )
43  {
44  MRPT_UNUSED_PARAM(use_kmeansplusplus_method);
46  ASSERT_(k>=1)
47  const size_t N = points.size();
48  assignments.resize(N);
49  if (out_centers) out_centers->clear();
50  if (!N)
51  return 0; // No points, we're done.
52  // Parse to required format:
53  size_t dims=0;
54  const typename LIST_OF_VECTORS1::const_iterator it_first=points.begin();
55  const typename LIST_OF_VECTORS1::const_iterator it_end =points.end();
56  typedef typename LIST_OF_VECTORS1::value_type TInnerVector;
57  typedef typename LIST_OF_VECTORS2::value_type TInnerVectorCenters;
58  std::vector<typename TInnerVector::value_type> raw_vals;
59  typename TInnerVector::value_type *trg_ptr=NULL;
60  for (typename LIST_OF_VECTORS1::const_iterator it=it_first;it!=it_end;++it)
61  {
62  if (it==it_first)
63  {
64  dims = it->size();
65  ASSERTMSG_(dims>0,"Dimensionality of points can't be zero.")
66  raw_vals.resize(N*dims);
67  trg_ptr = &raw_vals[0];
68  }
69  else
70  {
71  ASSERTMSG_(size_t(dims)==size_t(it->size()),"All points must have the same dimensionality.")
72  }
73 
74  ::memcpy(trg_ptr, &(*it)[0], dims*sizeof(typename TInnerVector::value_type));
75  trg_ptr+=dims;
76  }
77  // Call the internal implementation:
78  std::vector<typename TInnerVectorCenters::value_type> centers(dims*k);
79  const double ret = detail::internal_kmeans(false,N,k,points.begin()->size(),&raw_vals[0],attempts,&centers[0],&assignments[0]);
80  // Centers:
81  if (out_centers)
82  {
83  const typename TInnerVectorCenters::value_type *center_ptr = &centers[0];
84  for (size_t i=0;i<k;i++)
85  {
86  TInnerVectorCenters c;
87  c.resize(dims);
88  for (size_t j=0;j<dims;j++) c[j]= *center_ptr++;
89  out_centers->push_back(c);
90  }
91  }
92  return ret;
93  MRPT_END
94  }
95  } // end detail namespace
96 
97 
98  /** @name k-means algorithms
99  @{ */
100 
101  /** k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters.
102  * The list of input points can be any template CONTAINER<POINT> with:
103  * - CONTAINER can be: Any STL container: std::vector,std::list,std::deque,...
104  * - POINT can be:
105  * - std::vector<double/float>
106  * - CArrayDouble<N> / CArrayFloat<N>
107  *
108  * \param k [IN] Number of cluster to look for.
109  * \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<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
110  * \param assignments [OUT] At output it will have a number [0,k-1] for each of the N input points.
111  * \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".
112  * \param attempts [IN] Number of attempts.
113  *
114  * \sa A more advanced algorithm, see: kmeanspp
115  * \note Uses the kmeans++ implementation by David Arthur (2009, http://www.stanford.edu/~darthur/kmpp.zip).
116  */
117  template <class LIST_OF_VECTORS1,class LIST_OF_VECTORS2>
118  inline double kmeans(
119  const size_t k,
120  const LIST_OF_VECTORS1 & points,
121  std::vector<int> &assignments,
122  LIST_OF_VECTORS2 *out_centers = NULL,
123  const size_t attempts = 3
124  )
125  {
126  return detail::stub_kmeans(false /* standard method */, k,points,assignments,out_centers,attempts);
127  }
128 
129  /** k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters.
130  * The list of input points can be any template CONTAINER<POINT> with:
131  * - CONTAINER can be: Any STL container: std::vector,std::list,std::deque,...
132  * - POINT can be:
133  * - std::vector<double/float>
134  * - CArrayDouble<N> / CArrayFloat<N>
135  *
136  * \param k [IN] Number of cluster to look for.
137  * \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<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
138  * \param assignments [OUT] At output it will have a number [0,k-1] for each of the N input points.
139  * \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".
140  * \param attempts [IN] Number of attempts.
141  *
142  * \sa The standard kmeans algorithm, see: kmeans
143  * \note Uses the kmeans++ implementation by David Arthur (2009, http://www.stanford.edu/~darthur/kmpp.zip).
144  */
145  template <class LIST_OF_VECTORS1,class LIST_OF_VECTORS2>
146  inline double kmeanspp(
147  const size_t k,
148  const LIST_OF_VECTORS1 & points,
149  std::vector<int> &assignments,
150  LIST_OF_VECTORS2 *out_centers = NULL,
151  const size_t attempts = 3
152  )
153  {
154  return detail::stub_kmeans(true /* kmeans++ algorithm*/, k,points,assignments,out_centers,attempts);
155  }
156 
157  /** @} */
158 
159  } // End of MATH namespace
160 } // End of namespace
161 #endif
void BASE_IMPEXP memcpy(void *dest, size_t destSize, const void *src, size_t copyCount) MRPT_NO_THROWS
An OS and compiler independent version of "memcpy".
Definition: os.cpp:358
const Scalar * const_iterator
Definition: eigen_plugins.h:24
GLsizei const GLfloat * points
Definition: glext.h:4797
double kmeanspp(const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers=NULL, const size_t attempts=3)
k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...
#define MRPT_END
#define MRPT_UNUSED_PARAM(a)
Can be used to avoid "not used parameters" warnings from the compiler.
const GLubyte * c
Definition: glext.h:5590
double kmeans(const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers=NULL, const size_t attempts=3)
k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...
#define MRPT_START
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
double BASE_IMPEXP internal_kmeans(const bool use_kmeansplusplus_method, const size_t nPoints, const size_t k, const size_t dims, const SCALAR *points, const size_t attempts, SCALAR *out_center, int *out_assignments)
double stub_kmeans(const bool use_kmeansplusplus_method, const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers, const size_t attempts)
#define ASSERT_(f)
#define ASSERTMSG_(f, __ERROR_MSG)



Page generated by Doxygen 1.8.14 for MRPT 1.5.7 Git: 5902e14cc Wed Apr 24 15:04:01 2019 +0200 at lun oct 28 01:39:17 CET 2019