Main MRPT website > C++ reference for MRPT 1.9.9
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-2018, 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 {
21 // Auxiliary method: templatized for working with float/double's.
22 template <typename SCALAR>
23 double internal_kmeans(
24  const bool use_kmeansplusplus_method, const size_t nPoints, const size_t k,
25  const size_t dims, const SCALAR* points, const size_t attempts,
26  SCALAR* out_center, int* out_assignments);
27 
28 // Auxiliary method, the actual code of the two front-end functions offered to
29 // the user below.
30 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
31 double stub_kmeans(
32  const bool use_kmeansplusplus_method, const size_t k,
33  const LIST_OF_VECTORS1& points, std::vector<int>& assignments,
34  LIST_OF_VECTORS2* out_centers, const size_t attempts)
35 {
36  MRPT_UNUSED_PARAM(use_kmeansplusplus_method);
38  ASSERT_(k >= 1);
39  const size_t N = points.size();
40  assignments.resize(N);
41  if (out_centers) out_centers->clear();
42  if (!N) return 0; // No points, we're done.
43  // Parse to required format:
44  size_t dims = 0;
45  const typename LIST_OF_VECTORS1::const_iterator it_first = points.begin();
46  const typename LIST_OF_VECTORS1::const_iterator it_end = points.end();
47  using TInnerVector = typename LIST_OF_VECTORS1::value_type;
48  using TInnerVectorCenters = typename LIST_OF_VECTORS2::value_type;
49  std::vector<typename TInnerVector::value_type> raw_vals;
50  typename TInnerVector::value_type* trg_ptr = nullptr;
51  for (typename LIST_OF_VECTORS1::const_iterator it = it_first; it != it_end;
52  ++it)
53  {
54  if (it == it_first)
55  {
56  dims = it->size();
57  ASSERTMSG_(dims > 0, "Dimensionality of points can't be zero.");
58  raw_vals.resize(N * dims);
59  trg_ptr = &raw_vals[0];
60  }
61  else
62  {
63  ASSERTMSG_(
64  size_t(dims) == size_t(it->size()),
65  "All points must have the same dimensionality.");
66  }
67 
68  ::memcpy(
69  trg_ptr, &(*it)[0],
70  dims * sizeof(typename TInnerVector::value_type));
71  trg_ptr += dims;
72  }
73  // Call the internal implementation:
74  std::vector<typename TInnerVectorCenters::value_type> centers(dims * k);
75  const double ret = detail::internal_kmeans(
76  false, N, k, points.begin()->size(), &raw_vals[0], attempts,
77  &centers[0], &assignments[0]);
78  // Centers:
79  if (out_centers)
80  {
81  const typename TInnerVectorCenters::value_type* center_ptr =
82  &centers[0];
83  for (size_t i = 0; i < k; i++)
84  {
85  TInnerVectorCenters c;
86  c.resize(dims);
87  for (size_t j = 0; j < dims; j++) c[j] = *center_ptr++;
88  out_centers->push_back(c);
89  }
90  }
91  return ret;
92  MRPT_END
93 }
94 } // namespace detail
95 
96 /** @name k-means algorithms
97 @{ */
98 
99 /** k-means algorithm to cluster a list of N points of arbitrary dimensionality
100  *into exactly K clusters.
101  * The list of input points can be any template CONTAINER<POINT> with:
102  * - CONTAINER can be: Any STL container:
103  *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
110  *containers of std::vector<float/double>, for example a
111  *std::vector<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
112  * \param assignments [OUT] At output it will have a number [0,k-1] for each
113  *of the N input points.
114  * \param out_centers [OUT] If not nullptr, at output will have the centers of
115  *each group. Can be of any of the supported types of "points", but the basic
116  *coordinates should be float or double exactly as in "points".
117  * \param attempts [IN] Number of attempts.
118  *
119  * \sa A more advanced algorithm, see: kmeanspp
120  * \note Uses the kmeans++ implementation by David Arthur (2009,
121  *http://www.stanford.edu/~darthur/kmpp.zip).
122  */
123 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
124 inline double kmeans(
125  const size_t k, const LIST_OF_VECTORS1& points,
126  std::vector<int>& assignments, LIST_OF_VECTORS2* out_centers = nullptr,
127  const size_t attempts = 3)
128 {
129  return detail::stub_kmeans(
130  false /* standard method */, k, points, assignments, out_centers,
131  attempts);
132 }
133 
134 /** k-means++ algorithm to cluster a list of N points of arbitrary
135  *dimensionality into exactly K clusters.
136  * The list of input points can be any template CONTAINER<POINT> with:
137  * - CONTAINER can be: Any STL container:
138  *std::vector,std::list,std::deque,...
139  * - POINT can be:
140  * - std::vector<double/float>
141  * - CArrayDouble<N> / CArrayFloat<N>
142  *
143  * \param k [IN] Number of cluster to look for.
144  * \param points [IN] The list of N input points. It can be any STL-like
145  *containers of std::vector<float/double>, for example a
146  *std::vector<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
147  * \param assignments [OUT] At output it will have a number [0,k-1] for each
148  *of the N input points.
149  * \param out_centers [OUT] If not nullptr, at output will have the centers of
150  *each group. Can be of any of the supported types of "points", but the basic
151  *coordinates should be float or double exactly as in "points".
152  * \param attempts [IN] Number of attempts.
153  *
154  * \sa The standard kmeans algorithm, see: kmeans
155  * \note Uses the kmeans++ implementation by David Arthur (2009,
156  *http://www.stanford.edu/~darthur/kmpp.zip).
157  */
158 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
159 inline double kmeanspp(
160  const size_t k, const LIST_OF_VECTORS1& points,
161  std::vector<int>& assignments, LIST_OF_VECTORS2* out_centers = nullptr,
162  const size_t attempts = 3)
163 {
164  return detail::stub_kmeans(
165  true /* kmeans++ algorithm*/, k, points, assignments, out_centers,
166  attempts);
167 }
168 
169 /** @} */
170 
171 } // namespace math
172 } // namespace mrpt
173 #endif
#define MRPT_START
Definition: exceptions.h:262
GLsizei const GLfloat * points
Definition: glext.h:5339
double kmeans(const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers=nullptr, const size_t attempts=3)
k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...
#define ASSERT_(f)
Defines an assertion mechanism.
Definition: exceptions.h:113
const GLubyte * c
Definition: glext.h:6313
double kmeanspp(const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers=nullptr, const size_t attempts=3)
k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...
#define ASSERTMSG_(f, __ERROR_MSG)
Defines an assertion mechanism.
Definition: exceptions.h:101
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
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 MRPT_END
Definition: exceptions.h:266
double 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)
const Scalar * const_iterator
Definition: eigen_plugins.h:27
void memcpy(void *dest, size_t destSize, const void *src, size_t copyCount) noexcept
An OS and compiler independent version of "memcpy".
Definition: os.cpp:356
#define MRPT_UNUSED_PARAM(a)
Determines whether this is an X86 or AMD64 platform.
Definition: common.h:186



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: ad3a9d8ae Tue May 1 23:10:22 2018 -0700 at lun oct 28 00:14:14 CET 2019