Main MRPT website > C++ reference for MRPT 1.4.0
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-2016, 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
15namespace 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>
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;
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
#define MRPT_START
Definition: mrpt_macros.h:349
#define ASSERT_(f)
Definition: mrpt_macros.h:261
#define MRPT_END
Definition: mrpt_macros.h:353
#define MRPT_UNUSED_PARAM(a)
Can be used to avoid "not used parameters" warnings from the compiler.
Definition: mrpt_macros.h:290
#define ASSERTMSG_(f, __ERROR_MSG)
Definition: mrpt_macros.h:260
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)
Definition: kmeans.h:35
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.
Definition: kmeans.h:118
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...
Definition: kmeans.h:146
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.



Page generated by Doxygen 1.9.5 for MRPT 1.4.0 SVN: at Tue Dec 27 00:54:45 UTC 2022