MRPT  1.9.9
include/mrpt/math/kmeans.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2019, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
12 #include <mrpt/math/CMatrixFixed.h>
13 
14 namespace mrpt
15 {
16 namespace math
17 {
18 namespace detail
19 {
20 // Auxiliary method: templatized for working with float/double's.
21 template <typename SCALAR>
22 double internal_kmeans(
23  const bool use_kmeansplusplus_method, const size_t nPoints, const size_t k,
24  const size_t dims, const SCALAR* points, const size_t attempts,
25  SCALAR* out_center, int* out_assignments);
26 
27 // Auxiliary method, the actual code of the two front-end functions offered to
28 // the user below.
29 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
30 double stub_kmeans(
31  const bool use_kmeansplusplus_method, const size_t k,
32  const LIST_OF_VECTORS1& points, std::vector<int>& assignments,
33  LIST_OF_VECTORS2* out_centers, const size_t attempts)
34 {
35  MRPT_UNUSED_PARAM(use_kmeansplusplus_method);
37  ASSERT_(k >= 1);
38  const size_t N = points.size();
39  assignments.resize(N);
40  if (out_centers) out_centers->clear();
41  if (!N) return 0; // No points, we're done.
42  // Parse to required format:
43  size_t dims = 0;
44  const auto it_first = points.begin();
45  const auto it_end = points.end();
46  using TInnerVector = typename LIST_OF_VECTORS1::value_type;
47  using TInnerVectorCenters = typename LIST_OF_VECTORS2::value_type;
48  std::vector<typename TInnerVector::value_type> raw_vals;
49  typename TInnerVector::value_type* trg_ptr = nullptr;
50  for (typename LIST_OF_VECTORS1::const_iterator it = it_first; it != it_end;
51  ++it)
52  {
53  if (it == it_first)
54  {
55  dims = it->size();
56  ASSERTMSG_(dims > 0, "Dimensionality of points can't be zero.");
57  raw_vals.resize(N * dims);
58  trg_ptr = &raw_vals[0];
59  }
60  else
61  {
62  ASSERTMSG_(
63  size_t(dims) == size_t(it->size()),
64  "All points must have the same dimensionality.");
65  }
66 
67  ::memcpy(
68  trg_ptr, &(*it)[0],
69  dims * sizeof(typename TInnerVector::value_type));
70  trg_ptr += dims;
71  }
72  // Call the internal implementation:
73  std::vector<typename TInnerVectorCenters::value_type> centers(dims * k);
74  const double ret = detail::internal_kmeans(
75  false, N, k, points.begin()->size(), &raw_vals[0], attempts,
76  &centers[0], &assignments[0]);
77  // Centers:
78  if (out_centers)
79  {
80  const typename TInnerVectorCenters::value_type* center_ptr =
81  &centers[0];
82  for (size_t i = 0; i < k; i++)
83  {
84  TInnerVectorCenters c;
85  c.resize(dims);
86  for (size_t j = 0; j < dims; j++) c[j] = *center_ptr++;
87  out_centers->push_back(c);
88  }
89  }
90  return ret;
91  MRPT_END
92 }
93 } // namespace detail
94 
95 /** @name k-means algorithms
96 @{ */
97 
98 /** k-means algorithm to cluster a list of N points of arbitrary dimensionality
99  *into exactly K clusters.
100  * The list of input points can be any template CONTAINER<POINT> with:
101  * - CONTAINER can be: Any STL container:
102  *std::vector,std::list,std::deque,...
103  * - POINT can be:
104  * - std::vector<double/float>
105  * - CVectorFixedDouble<N> / CVectorFixedFloat<N>
106  *
107  * \param k [IN] Number of cluster to look for.
108  * \param points [IN] The list of N input points. It can be any STL-like
109  *containers of std::vector<float/double>, for example a
110  *std::vector<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
111  * \param assignments [OUT] At output it will have a number [0,k-1] for each
112  *of the N input points.
113  * \param out_centers [OUT] If not nullptr, at output will have the centers of
114  *each group. Can be of any of the supported types of "points", but the basic
115  *coordinates should be float or double exactly as in "points".
116  * \param attempts [IN] Number of attempts.
117  *
118  * \sa A more advanced algorithm, see: kmeanspp
119  * \note Uses the kmeans++ implementation by David Arthur (2009,
120  *http://www.stanford.edu/~darthur/kmpp.zip).
121  */
122 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
123 inline double kmeans(
124  const size_t k, const LIST_OF_VECTORS1& points,
125  std::vector<int>& assignments, LIST_OF_VECTORS2* out_centers = nullptr,
126  const size_t attempts = 3)
127 {
128  return detail::stub_kmeans(
129  false /* standard method */, k, points, assignments, out_centers,
130  attempts);
131 }
132 
133 /** k-means++ algorithm to cluster a list of N points of arbitrary
134  *dimensionality into exactly K clusters.
135  * The list of input points can be any template CONTAINER<POINT> with:
136  * - CONTAINER can be: Any STL container:
137  *std::vector,std::list,std::deque,...
138  * - POINT can be:
139  * - std::vector<double/float>
140  * - CVectorFixedDouble<N> / CVectorFixedFloat<N>
141  *
142  * \param k [IN] Number of cluster to look for.
143  * \param points [IN] The list of N input points. It can be any STL-like
144  *containers of std::vector<float/double>, for example a
145  *std::vector<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
146  * \param assignments [OUT] At output it will have a number [0,k-1] for each
147  *of the N input points.
148  * \param out_centers [OUT] If not nullptr, at output will have the centers of
149  *each group. Can be of any of the supported types of "points", but the basic
150  *coordinates should be float or double exactly as in "points".
151  * \param attempts [IN] Number of attempts.
152  *
153  * \sa The standard kmeans algorithm, see: kmeans
154  * \note Uses the kmeans++ implementation by David Arthur (2009,
155  *http://www.stanford.edu/~darthur/kmpp.zip).
156  */
157 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2 = LIST_OF_VECTORS1>
158 inline double kmeanspp(
159  const size_t k, const LIST_OF_VECTORS1& points,
160  std::vector<int>& assignments, LIST_OF_VECTORS2* out_centers = nullptr,
161  const size_t attempts = 3)
162 {
163  return detail::stub_kmeans(
164  true /* kmeans++ algorithm*/, k, points, assignments, out_centers,
165  attempts);
166 }
167 
168 /** @} */
169 
170 } // namespace math
171 } // namespace mrpt
#define MRPT_START
Definition: exceptions.h:241
GLsizei const GLfloat * points
Definition: glext.h:5414
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:120
const GLubyte * c
Definition: glext.h:6406
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:108
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:245
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)
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:358
#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: 8fe78517f Sun Jul 14 19:43:28 2019 +0200 at lun oct 28 02:10:00 CET 2019