<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>kmeans.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<div align="left"><a href="http://www.mrpt.org/">Main MRPT website</a> > <b>C++ reference</b> </div>
<div align="right">
<a href="index.html"><img border="0" src="mrpt_logo.png" alt="MRPT logo"></a>
</div>
<!-- Generated by Doxygen 1.7.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<div class="left">
<form id="FSearchBox" action="search.php" method="get">
<img id="MSearchSelect" src="search/mag.png" alt=""/>
<input type="text" id="MSearchField" name="query" value="Search" size="20" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"/>
</form>
</div><div class="right"></div>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<div class="header">
<div class="headertitle">
<div class="title">kmeans.h</div> </div>
</div>
<div class="contents">
<a href="kmeans_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* +---------------------------------------------------------------------------+</span>
<a name="l00002"></a>00002 <span class="comment"> | The Mobile Robot Programming Toolkit (MRPT) C++ library |</span>
<a name="l00003"></a>00003 <span class="comment"> | |</span>
<a name="l00004"></a>00004 <span class="comment"> | http://www.mrpt.org/ |</span>
<a name="l00005"></a>00005 <span class="comment"> | |</span>
<a name="l00006"></a>00006 <span class="comment"> | Copyright (C) 2005-2011 University of Malaga |</span>
<a name="l00007"></a>00007 <span class="comment"> | |</span>
<a name="l00008"></a>00008 <span class="comment"> | This software was written by the Machine Perception and Intelligent |</span>
<a name="l00009"></a>00009 <span class="comment"> | Robotics Lab, University of Malaga (Spain). |</span>
<a name="l00010"></a>00010 <span class="comment"> | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |</span>
<a name="l00011"></a>00011 <span class="comment"> | |</span>
<a name="l00012"></a>00012 <span class="comment"> | This file is part of the MRPT project. |</span>
<a name="l00013"></a>00013 <span class="comment"> | |</span>
<a name="l00014"></a>00014 <span class="comment"> | MRPT is free software: you can redistribute it and/or modify |</span>
<a name="l00015"></a>00015 <span class="comment"> | it under the terms of the GNU General Public License as published by |</span>
<a name="l00016"></a>00016 <span class="comment"> | the Free Software Foundation, either version 3 of the License, or |</span>
<a name="l00017"></a>00017 <span class="comment"> | (at your option) any later version. |</span>
<a name="l00018"></a>00018 <span class="comment"> | |</span>
<a name="l00019"></a>00019 <span class="comment"> | MRPT is distributed in the hope that it will be useful, |</span>
<a name="l00020"></a>00020 <span class="comment"> | but WITHOUT ANY WARRANTY; without even the implied warranty of |</span>
<a name="l00021"></a>00021 <span class="comment"> | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |</span>
<a name="l00022"></a>00022 <span class="comment"> | GNU General Public License for more details. |</span>
<a name="l00023"></a>00023 <span class="comment"> | |</span>
<a name="l00024"></a>00024 <span class="comment"> | You should have received a copy of the GNU General Public License |</span>
<a name="l00025"></a>00025 <span class="comment"> | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |</span>
<a name="l00026"></a>00026 <span class="comment"> | |</span>
<a name="l00027"></a>00027 <span class="comment"> +---------------------------------------------------------------------------+ */</span>
<a name="l00028"></a>00028 <span class="preprocessor">#ifndef mrpt_math_kmeans_H</span>
<a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">#define mrpt_math_kmeans_H</span>
<a name="l00030"></a>00030 <span class="preprocessor"></span>
<a name="l00031"></a>00031 <span class="preprocessor">#include <<a class="code" href="_c_matrix_template_numeric_8h.html">mrpt/math/CMatrixTemplateNumeric.h</a>></span>
<a name="l00032"></a>00032 <span class="preprocessor">#include <<a class="code" href="_c_matrix_fixed_numeric_8h.html">mrpt/math/CMatrixFixedNumeric.h</a>></span>
<a name="l00033"></a>00033
<a name="l00034"></a>00034 <span class="keyword">namespace </span>mrpt
<a name="l00035"></a>00035 {
<a name="l00036"></a>00036 <span class="keyword">namespace </span>math
<a name="l00037"></a>00037 {
<a name="l00038"></a>00038 <span class="keyword">namespace </span>detail {
<a name="l00039"></a>00039 <span class="comment">// Auxiliary method: templatized for working with float/double's.</span>
<a name="l00040"></a>00040 <span class="keyword">template</span> <<span class="keyword">typename</span> SCALAR>
<a name="l00041"></a>00041 <span class="keywordtype">double</span> <a class="code" href="base_2include_2mrpt_2base_2link__pragmas_8h.html#a6045fa0129b1a3d6c8bf895470e66574">BASE_IMPEXP</a> <a class="code" href="namespacemrpt_1_1math_1_1detail.html#a555c07e79b3a50c0055069ba25b4a227">internal_kmeans</a>(
<a name="l00042"></a>00042 <span class="keyword">const</span> <span class="keywordtype">bool</span> use_kmeansplusplus_method,
<a name="l00043"></a>00043 <span class="keyword">const</span> <span class="keywordtype">size_t</span> nPoints,
<a name="l00044"></a>00044 <span class="keyword">const</span> <span class="keywordtype">size_t</span> k,
<a name="l00045"></a>00045 <span class="keyword">const</span> <span class="keywordtype">size_t</span> dims,
<a name="l00046"></a>00046 <span class="keyword">const</span> SCALAR *points,
<a name="l00047"></a>00047 <span class="keyword">const</span> <span class="keywordtype">size_t</span> attempts,
<a name="l00048"></a>00048 SCALAR* out_center,
<a name="l00049"></a>00049 <span class="keywordtype">int</span> *out_assignments
<a name="l00050"></a>00050 );
<a name="l00051"></a>00051
<a name="l00052"></a>00052 <span class="comment">// Auxiliary method, the actual code of the two front-end functions offered to the user below.</span>
<a name="l00053"></a>00053 <span class="keyword">template</span> <<span class="keyword">class</span> LIST_OF_VECTORS1,<span class="keyword">class</span> LIST_OF_VECTORS2>
<a name="l00054"></a><a class="code" href="namespacemrpt_1_1math_1_1detail.html#a6d87cfbda3846e628fd7c84c4921232a">00054</a> <span class="keywordtype">double</span> <a class="code" href="namespacemrpt_1_1math_1_1detail.html#a6d87cfbda3846e628fd7c84c4921232a">stub_kmeans</a>(
<a name="l00055"></a>00055 <span class="keyword">const</span> <span class="keywordtype">bool</span> use_kmeansplusplus_method,
<a name="l00056"></a>00056 <span class="keyword">const</span> <span class="keywordtype">size_t</span> k,
<a name="l00057"></a>00057 <span class="keyword">const</span> LIST_OF_VECTORS1 & points,
<a name="l00058"></a>00058 <a class="code" href="classstd_1_1vector.html">std::vector<int></a> &assignments,
<a name="l00059"></a>00059 LIST_OF_VECTORS2 *out_centers,
<a name="l00060"></a>00060 <span class="keyword">const</span> <span class="keywordtype">size_t</span> attempts
<a name="l00061"></a>00061 )
<a name="l00062"></a>00062 {
<a name="l00063"></a>00063 <a class="code" href="mrpt__macros_8h.html#a45b840af519f33816311acdbb28d7c10">MRPT_START</a>
<a name="l00064"></a>00064 <a class="code" href="mrpt__macros_8h.html#a47eb5a445c2bf3d9190396510ea9683e">ASSERT_</a>(k>=1)
<a name="l00065"></a>00065 <span class="keyword">const</span> <span class="keywordtype">size_t</span> N = points.size();
<a name="l00066"></a>00066 assignments.resize(N);
<a name="l00067"></a>00067 <span class="keywordflow">if</span> (out_centers) out_centers->clear();
<a name="l00068"></a>00068 <span class="keywordflow">if</span> (!N)
<a name="l00069"></a>00069 <span class="keywordflow">return</span> 0; <span class="comment">// No points, we're done.</span>
<a name="l00070"></a>00070 <span class="comment">// Parse to required format:</span>
<a name="l00071"></a>00071 <span class="keywordtype">size_t</span> dims=0;
<a name="l00072"></a>00072 <span class="keyword">const</span> <span class="keyword">typename</span> LIST_OF_VECTORS1<a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">::const_iterator</a> it_first=points.begin();
<a name="l00073"></a>00073 <span class="keyword">const</span> <span class="keyword">typename</span> LIST_OF_VECTORS1<a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">::const_iterator</a> it_end =points.end();
<a name="l00074"></a>00074 <span class="keyword">typedef</span> <span class="keyword">typename</span> LIST_OF_VECTORS1<a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">::value_type</a> TInnerVector;
<a name="l00075"></a>00075 <span class="keyword">typedef</span> <span class="keyword">typename</span> LIST_OF_VECTORS2<a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">::value_type</a> TInnerVectorCenters;
<a name="l00076"></a>00076 std<a class="code" href="classstd_1_1vector.html" title="STL class.">::vector<typename TInnerVector::value_type></a> raw_vals;
<a name="l00077"></a>00077 <span class="keyword">typename</span> TInnerVector<a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">::value_type</a> *trg_ptr=NULL;
<a name="l00078"></a>00078 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">LIST_OF_VECTORS1::const_iterator</a> it=it_first;it!=it_end;++it)
<a name="l00079"></a>00079 {
<a name="l00080"></a>00080 <span class="keywordflow">if</span> (it==it_first)
<a name="l00081"></a>00081 {
<a name="l00082"></a>00082 dims = it->size();
<a name="l00083"></a>00083 <a class="code" href="mrpt__macros_8h.html#ad30ea0382c594c0e2efe88212e9352b0">ASSERTMSG_</a>(dims>0,<span class="stringliteral">"Dimensionality of points can't be zero."</span>)
<a name="l00084"></a>00084 raw_vals.resize(N*dims);
<a name="l00085"></a>00085 trg_ptr = &raw_vals[0];
<a name="l00086"></a>00086 }
<a name="l00087"></a>00087 <span class="keywordflow">else</span>
<a name="l00088"></a>00088 {
<a name="l00089"></a>00089 <a class="code" href="mrpt__macros_8h.html#ad30ea0382c594c0e2efe88212e9352b0">ASSERTMSG_</a>(<span class="keywordtype">size_t</span>(dims)==<span class="keywordtype">size_t</span>(it->size()),<span class="stringliteral">"All points must have the same dimensionality."</span>)
<a name="l00090"></a>00090 }
<a name="l00091"></a>00091
<a name="l00092"></a>00092 <a class="code" href="group__mrpt__system__os.html#gae1184cfb1f617787dc4c9da98becbe3a" title="An OS and compiler independent version of "memcpy".">::memcpy</a>(trg_ptr, &(*it)[0], dims*<span class="keyword">sizeof</span>(<span class="keyword">typename</span> <a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">TInnerVector::value_type</a>));
<a name="l00093"></a>00093 trg_ptr+=dims;
<a name="l00094"></a>00094 }
<a name="l00095"></a>00095 <span class="comment">// Call the internal implementation:</span>
<a name="l00096"></a>00096 std<a class="code" href="classstd_1_1vector.html" title="STL class.">::vector<typename TInnerVectorCenters::value_type></a> centers(dims*k);
<a name="l00097"></a>00097 <span class="keyword">const</span> <span class="keywordtype">double</span> ret = <a class="code" href="namespacemrpt_1_1math_1_1detail.html#a555c07e79b3a50c0055069ba25b4a227">detail::internal_kmeans</a>(<span class="keyword">false</span>,N,k,points.begin()->size(),&raw_vals[0],attempts,&centers[0],&assignments[0]);
<a name="l00098"></a>00098 <span class="comment">// Centers:</span>
<a name="l00099"></a>00099 <span class="keywordflow">if</span> (out_centers)
<a name="l00100"></a>00100 {
<a name="l00101"></a>00101 <span class="keyword">const</span> <span class="keyword">typename</span> TInnerVectorCenters<a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">::value_type</a> *center_ptr = &centers[0];
<a name="l00102"></a>00102 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0;i<k;i++)
<a name="l00103"></a>00103 {
<a name="l00104"></a>00104 TInnerVectorCenters c;
<a name="l00105"></a>00105 c.resize(dims);
<a name="l00106"></a>00106 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> j=0;j<dims;j++) c[j]= *center_ptr++;
<a name="l00107"></a>00107 out_centers->push_back(c);
<a name="l00108"></a>00108 }
<a name="l00109"></a>00109 }
<a name="l00110"></a>00110 <span class="keywordflow">return</span> ret;
<a name="l00111"></a>00111 <a class="code" href="mrpt__macros_8h.html#a88a917260793b56abd83ad2a0d849eb1">MRPT_END</a>
<a name="l00112"></a>00112 }
<a name="l00113"></a>00113 } <span class="comment">// end detail namespace</span>
<a name="l00114"></a>00114
<a name="l00115"></a>00115 <span class="comment"></span>
<a name="l00116"></a>00116 <span class="comment"> /** @name k-means algorithms</span>
<a name="l00117"></a>00117 <span class="comment"> @{ */</span>
<a name="l00118"></a>00118 <span class="comment"></span>
<a name="l00119"></a>00119 <span class="comment"> /** k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters.</span>
<a name="l00120"></a>00120 <span class="comment"> * The list of input points can be any template CONTAINER<POINT> with:</span>
<a name="l00121"></a>00121 <span class="comment"> * - CONTAINER can be: Any STL container: std::vector,std::list,std::deque,...</span>
<a name="l00122"></a>00122 <span class="comment"> * - POINT can be:</span>
<a name="l00123"></a>00123 <span class="comment"> * - std::vector<double/float></span>
<a name="l00124"></a>00124 <span class="comment"> * - CArrayDouble<N> / CArrayFloat<N></span>
<a name="l00125"></a>00125 <span class="comment"> *</span>
<a name="l00126"></a>00126 <span class="comment"> * \param k [IN] Number of cluster to look for.</span>
<a name="l00127"></a>00127 <span class="comment"> * \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...</span>
<a name="l00128"></a>00128 <span class="comment"> * \param assignments [OUT] At output it will have a number [0,k-1] for each of the N input points.</span>
<a name="l00129"></a>00129 <span class="comment"> * \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".</span>
<a name="l00130"></a>00130 <span class="comment"> * \param attempts [IN] Number of attempts.</span>
<a name="l00131"></a>00131 <span class="comment"> *</span>
<a name="l00132"></a>00132 <span class="comment"> * \sa A more advanced algorithm, see: kmeanspp</span>
<a name="l00133"></a>00133 <span class="comment"> * \note Uses the kmeans++ implementation by David Arthur (2009, http://www.stanford.edu/~darthur/kmpp.zip).</span>
<a name="l00134"></a>00134 <span class="comment"> */</span>
<a name="l00135"></a>00135 <span class="keyword">template</span> <<span class="keyword">class</span> LIST_OF_VECTORS1,<span class="keyword">class</span> LIST_OF_VECTORS2>
<a name="l00136"></a><a class="code" href="namespacemrpt_1_1math.html#a962c37014b369b1dd1c7961e332c239d">00136</a> <span class="keyword">inline</span> <span class="keywordtype">double</span> <a class="code" href="namespacemrpt_1_1math.html#a962c37014b369b1dd1c7961e332c239d" title="k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...">kmeans</a>(
<a name="l00137"></a>00137 <span class="keyword">const</span> <span class="keywordtype">size_t</span> k,
<a name="l00138"></a>00138 <span class="keyword">const</span> LIST_OF_VECTORS1 & points,
<a name="l00139"></a>00139 <a class="code" href="classstd_1_1vector.html">std::vector<int></a> &assignments,
<a name="l00140"></a>00140 LIST_OF_VECTORS2 *out_centers = NULL,
<a name="l00141"></a>00141 <span class="keyword">const</span> <span class="keywordtype">size_t</span> attempts = 3
<a name="l00142"></a>00142 )
<a name="l00143"></a>00143 {
<a name="l00144"></a>00144 <span class="keywordflow">return</span> <a class="code" href="namespacemrpt_1_1math_1_1detail.html#a6d87cfbda3846e628fd7c84c4921232a">detail::stub_kmeans</a>(<span class="keyword">false</span> <span class="comment">/* standard method */</span>, k,points,assignments,out_centers,attempts);
<a name="l00145"></a>00145 }
<a name="l00146"></a>00146 <span class="comment"></span>
<a name="l00147"></a>00147 <span class="comment"> /** k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters.</span>
<a name="l00148"></a>00148 <span class="comment"> * The list of input points can be any template CONTAINER<POINT> with:</span>
<a name="l00149"></a>00149 <span class="comment"> * - CONTAINER can be: Any STL container: std::vector,std::list,std::deque,...</span>
<a name="l00150"></a>00150 <span class="comment"> * - POINT can be:</span>
<a name="l00151"></a>00151 <span class="comment"> * - std::vector<double/float></span>
<a name="l00152"></a>00152 <span class="comment"> * - CArrayDouble<N> / CArrayFloat<N></span>
<a name="l00153"></a>00153 <span class="comment"> *</span>
<a name="l00154"></a>00154 <span class="comment"> * \param k [IN] Number of cluster to look for.</span>
<a name="l00155"></a>00155 <span class="comment"> * \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...</span>
<a name="l00156"></a>00156 <span class="comment"> * \param assignments [OUT] At output it will have a number [0,k-1] for each of the N input points.</span>
<a name="l00157"></a>00157 <span class="comment"> * \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".</span>
<a name="l00158"></a>00158 <span class="comment"> * \param attempts [IN] Number of attempts.</span>
<a name="l00159"></a>00159 <span class="comment"> *</span>
<a name="l00160"></a>00160 <span class="comment"> * \sa The standard kmeans algorithm, see: kmeans</span>
<a name="l00161"></a>00161 <span class="comment"> * \note Uses the kmeans++ implementation by David Arthur (2009, http://www.stanford.edu/~darthur/kmpp.zip).</span>
<a name="l00162"></a>00162 <span class="comment"> */</span>
<a name="l00163"></a>00163 <span class="keyword">template</span> <<span class="keyword">class</span> LIST_OF_VECTORS1,<span class="keyword">class</span> LIST_OF_VECTORS2>
<a name="l00164"></a><a class="code" href="namespacemrpt_1_1math.html#ad0c38dff586346d5f1cfe8a9bd8a13cf">00164</a> <span class="keyword">inline</span> <span class="keywordtype">double</span> <a class="code" href="namespacemrpt_1_1math.html#ad0c38dff586346d5f1cfe8a9bd8a13cf" title="k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...">kmeanspp</a>(
<a name="l00165"></a>00165 <span class="keyword">const</span> <span class="keywordtype">size_t</span> k,
<a name="l00166"></a>00166 <span class="keyword">const</span> LIST_OF_VECTORS1 & points,
<a name="l00167"></a>00167 <a class="code" href="classstd_1_1vector.html">std::vector<int></a> &assignments,
<a name="l00168"></a>00168 LIST_OF_VECTORS2 *out_centers = NULL,
<a name="l00169"></a>00169 <span class="keyword">const</span> <span class="keywordtype">size_t</span> attempts = 3
<a name="l00170"></a>00170 )
<a name="l00171"></a>00171 {
<a name="l00172"></a>00172 <span class="keywordflow">return</span> <a class="code" href="namespacemrpt_1_1math_1_1detail.html#a6d87cfbda3846e628fd7c84c4921232a">detail::stub_kmeans</a>(<span class="keyword">true</span> <span class="comment">/* kmeans++ algorithm*/</span>, k,points,assignments,out_centers,attempts);
<a name="l00173"></a>00173 }
<a name="l00174"></a>00174 <span class="comment"></span>
<a name="l00175"></a>00175 <span class="comment"> /** @} */</span>
<a name="l00176"></a>00176
<a name="l00177"></a>00177 } <span class="comment">// End of MATH namespace</span>
<a name="l00178"></a>00178 } <span class="comment">// End of namespace</span>
<a name="l00179"></a>00179 <span class="preprocessor">#endif</span>
</pre></div></div>
</div>
<br><hr><br> <table border="0" width="100%"> <tr> <td> Page generated by <a href="http://www.doxygen.org" target="_blank">Doxygen 1.7.5</a> for MRPT 0.9.5 SVN: at Sun Sep 25 17:20:18 UTC 2011</td><td></td> <td width="100"> </td> <td width="150"> </td></tr> </table> </body></html>
