A.I.M.S algorithms


kmeansstrategy_d.h
Go to the documentation of this file.
1 /* This software and supporting documentation are distributed by
2  * Institut Federatif de Recherche 49
3  * CEA/NeuroSpin, Batiment 145,
4  * 91191 Gif-sur-Yvette cedex
5  * France
6  *
7  * This software is governed by the CeCILL-B license under
8  * French law and abiding by the rules of distribution of free software.
9  * You can use, modify and/or redistribute the software under the
10  * terms of the CeCILL-B license as circulated by CEA, CNRS
11  * and INRIA at the following URL "http://www.cecill.info".
12  *
13  * As a counterpart to the access to the source code and rights to copy,
14  * modify and redistribute granted by the license, users are provided only
15  * with a limited warranty and the software's author, the holder of the
16  * economic rights, and the successive licensors have only limited
17  * liability.
18  *
19  * In this respect, the user's attention is drawn to the risks associated
20  * with loading, using, modifying and/or developing or reproducing the
21  * software by the user in light of its specific status of free software,
22  * that may mean that it is complicated to manipulate, and that also
23  * therefore means that it is reserved for developers and experienced
24  * professionals having in-depth computer knowledge. Users are therefore
25  * encouraged to load and test the software's suitability as regards their
26  * requirements in conditions enabling the security of their systems and/or
27  * data to be ensured and, more generally, to use and operate it in the
28  * same conditions as regards security.
29  *
30  * The fact that you are presently reading this means that you have had
31  * knowledge of the CeCILL-B license and that you accept its terms.
32  */
33 
34 
35 #ifndef KMEANSSTRATEGY_D_H
36 #define KMEANSSTRATEGY_D_H
37 
38 #include <cstdlib>
44 #include <vector>
45 #include <list>
46 #include <stdlib.h>
47 
48 
49 template <class T>
51  aims::ClassifStrategy<T>( kmeanStrat )
52 {
53  myMeanVector = kmeanStrat.myMeanVector ;
54  myVarianceVector = kmeanStrat.myVarianceVector ;
55  myDistance = kmeanStrat.myDistance ;
56  myBeginIndex = kmeanStrat.myBeginIndex ;
57  myEndIndex = kmeanStrat.myEndIndex ;
58 }
59 
60 
61 template <class T>
62 aims::KmeansStrategy<T>::KmeansStrategy( int nbIterations, DistanceType distanceType,
63  int beginIndex , int endIndex ,
64  const std::vector< aims::Individuals<T> >& codeVector ) :
65  aims::ClassifStrategy<T>( nbIterations )
66 {
67  switch( distanceType ){
68  case NORM1 :
70  break ;
71  case NORM2 :
73  break ;
74  case NORM2SQR :
76  break ;
77  case INFNORM :
79  break ;
80  }
81 
82  ASSERT( beginIndex >= 0 && endIndex >= -1 ) ;
83  myBeginIndex = beginIndex ;
84  myEndIndex = endIndex ;
85  myMeanVector = codeVector ;
86  if( !codeVector.empty() ) // si codeVector non vide
87  this->myCodeVectorsGiven = true ;
88 }
89 
90 
91 template <class T>
93 {
94 }
95 
96 
97 template <class T>
99 {
100  return new aims::KmeansStrategy<T>( *this ) ;
101 }
102 
103 
104 template <class T>
105 void aims::KmeansStrategy<T>::init( std::string initializationType, int nbOfClasses,
106  std::vector< std::list< aims::Individuals<T> > >& classes )
107 {
108  if( initializationType == "CodeVectorsGiven" ){
109  std::cout << " vecteurs codes donnes" << std::endl << std::endl ;
110  // vérifier : taille de codeVector = nb de classes, et compatible avec taille de Individus<T>
111  if( int(myMeanVector.size()) != nbOfClasses ) // compatibilité avec nb de classes
112  this->myValidStrategy = false ;
113  for( int i = 0 ; i < nbOfClasses ; ++i ){
114  if( myMeanVector[i].value().size() != myMeanVector[1].value().size() ) // &taille des individus
115  this->myValidStrategy = false ;
116  }
117  }
118  else if( initializationType == "InitialClasses" ){
119  std::cout << " classes initiales" << std::endl << std::endl ;
120  std::vector< aims::Individuals<T> > myMeanVector( nbOfClasses + 1 ) ;
121  // nbOfClasses ne prend pas en compte la classe 0, contrairement à "analyse",
122  // d'où le +1 pour cohérence
123  analyse( classes ) ;
124  }
125  else {
126  // initialisation des vecteurs codes aléatoire (tirer au hasard 1 individu par classe)
127  std::cout << " individus donnes (tous ds la classe 0)" << std::endl ;
128  int randInd ;
129  bool change = false ;
130  // création d'1 vecteur de dimension nbOfClasses:
131  std::vector< Individuals<T> > meanVector( nbOfClasses + 1 ) ;
132  int tabRandInd[nbOfClasses] ;
133  std::cout << "Tirage des individus: " ;
134 
135  for( int c = 1 ; c <= nbOfClasses ; ++c ){
136  //cout << "class " << c << " : nb of ind = " << classes[c].size() << endl ;
137  // tirage aléatoire d'un individu ds la classe 0
138  randInd = (int) ( ( (double)rand() / (double)(RAND_MAX+1.0) ) * (double)(classes[0].size()) ) ;
139  tabRandInd[c] = randInd ;
140  std::cout << randInd << " " ;
141  do{
142  change = false ;
143  for( int i = 1 ; i < c ; ++i ){
144  if( randInd == tabRandInd[i] ){
145  // nouveau tirage au sort si randInd a deja ete tire
146  randInd = (int) ( ((double)rand() / (double)(RAND_MAX+1.0)) * (double)(classes[0].size()) ) ;
147  change = true ;
148  std::cout << "(" << randInd << ")" << " " ;
149  }
150  }
151  } while( change == true ) ;
152 
153  // copie des valeurs de l'individu choisi ds myMeanVector
154  typename std::list< aims::Individuals<T> >::const_iterator iter( classes[0].begin() ),
155  last( classes[0].end() ) ;
156  int count = 0 ;
157  while ( iter != last && count < randInd ){
158  ++count ;
159  ++iter ;
160  }
161  meanVector[c] = *iter ;
162  }
163  std::cout << std::endl << std::endl ;
164  myMeanVector = meanVector ;
165  }
166 
167  unsigned int maxIndex = myMeanVector[1].value().size() ;
168  if( ( myEndIndex == -1 ) || ( (unsigned int)myEndIndex >= maxIndex ) )
169  myEndIndex = maxIndex - 1 ;
170 }
171 
172 
173 template <class T>
174 double aims::KmeansStrategy<T>::iterate( int& nbOfIterations,
175  std::vector< std::list< Individuals<T> > >& classes )
176 {
177  std::cout << "Kmeans clustering - Iteration n° " << nbOfIterations << std::endl ;
178  int nbOfClasses = classes.size() ;
179  std::vector< std::list< aims::Individuals<T> > > newClasses( nbOfClasses ) ;
180 
181 /* std::cout << "nb d'individus ds les classes en entrant ds iterate:" ; */
182 /* for( int c = 0 ; c < nbOfClasses ; ++c ) */
183 /* std::cout << " " << classes[c].size() ; */
184 /* std::cout << std::endl ; */
185 
186 // std::cout << " agregation des individus" << std::endl ;
187  for( int c = 0 ; c < nbOfClasses ; ++c ){
188  typename std::list< aims::Individuals<T> >::const_iterator iter( classes[c].begin() ),
189  last( classes[c].end() ) ;
190  while( iter != last ){
191  int indMin = aggregate( *iter ) ;
192  newClasses[indMin].push_back( *iter ) ;
193  ++iter ;
194  }
195  classes[c].clear() ;
196  }
197 // delete classes ;
198  classes = newClasses ;
199 
200  std::cout << "nb d'individus - iterate end:" ;
201  for( int c = 0 ; c < nbOfClasses ; ++c )
202  std::cout << " " << classes[c].size() ;
203  std::cout << std::endl ;
204 
205  analyse( classes ) ; // faire l'analyse des classes
206  double new_inertia = globInertia( classes ) ; // calcul de l'inertie globale
207 
208  ++nbOfIterations ; // compteur nb d'iterations
209 
210  return new_inertia ;
211 }
212 
213 
214 template <class T>
215 void aims::KmeansStrategy<T>::analyse( const std::vector< std::list< aims::Individuals<T> > >& classes )
216 {
217 // std::cout << " analyse des classes..." << std::endl ;
218  unsigned int nbOfClasses = classes.size() ;
219 
220  // calculer myMeanVector (vecteur moyenne) et myVarVector (vecteur variance) pour chaque classe
221  std::vector< aims::Individuals<T> > meanVector( nbOfClasses ) ;
222  std::vector< aims::Individuals<T> > myVarianceVector( nbOfClasses ) ;
223  Point3df meanPos( 0., 0., 0. ) ;
224  Point3df varPos( 0., 0., 0. ) ;
225  unsigned int valIndSize = classes[1].front().value().size() ;
226  std::vector<T> meanVal( valIndSize ) ;
227  std::vector<T> varVal( valIndSize ) ;
228 
229  for( unsigned int cl = 1 ; cl < nbOfClasses ; ++cl ){
230  unsigned int nbOfInd = classes[cl].size() ;
231  typename std::list< aims::Individuals<T> >::const_iterator iter( classes[cl].begin() ),
232  last( classes[cl].end() ) ;
233  while ( iter != last){
234  Point3df indPos = iter->position() ;
235  meanPos[0] += indPos[0];
236  meanPos[1] += indPos[1];
237  meanPos[2] += indPos[2];
238  ++iter ;
239  }
240  meanPos[0] = meanPos[0] / nbOfInd ;
241  meanPos[1] = meanPos[1] / nbOfInd ;
242  meanPos[2] = meanPos[2] / nbOfInd ;
243 
244  for( unsigned int k = 0 ; k < valIndSize ; ++k ){
245  typename std::list< aims::Individuals<T> >::const_iterator iter( classes[cl].begin() ),
246  last( classes[cl].end() ) ;
247  float sumVal = 0., prodVal = 0. ;
248  while ( iter != last){
249  std::vector<T> indVal = iter->value() ;
250  sumVal += indVal[k] ;
251  prodVal += indVal[k] * indVal[k] ;
252  ++iter ;
253  }
254  meanVal[k] = sumVal / nbOfInd ;
255  varVal[k] = prodVal / nbOfInd - meanVal[k] * meanVal[k] ;
256  }
257  Individuals<T> meanIndiv( meanPos, meanVal ) ;
258  Individuals<T> varIndiv( meanPos, varVal ) ;
259 
260  meanVector[cl] = meanIndiv ;
261  myVarianceVector[cl] = varIndiv ;
262  }
263  myMeanVector = meanVector ;
264 }
265 
266 
267 template <class T>
269 {
270  // parcourir les classes et mettre l'individu dans la classe la plus proche
271  float distanceToClass ;
272  int nbOfClasses = myMeanVector.size() ;
273  int indMin = 1 ;
274 
275  float min = myDistance( individual.value(), myMeanVector[1].value(),
276  myBeginIndex, myEndIndex ) ;
277  for( int newC = 2 ; newC < nbOfClasses ; ++newC ){
278  distanceToClass = myDistance( individual.value(), myMeanVector[newC].value(),
279  myBeginIndex, myEndIndex ) ;
280  if( distanceToClass < min ){
281  indMin = newC ;
282  min = distanceToClass ;
283  }
284  }
285  return indMin ;
286 }
287 
288 
289 template <class T>
290 double aims::KmeansStrategy<T>::globInertia( const std::vector< std::list< aims::Individuals<T> > >& classes )
291 {
292 // std::cout << " calcul de l'inertie globale..." << std::endl ;
293 
294  int nbOfClasses = classes.size() ;
295  float dist = 0. ;
296  double glob_dist = 0. ;
297 
298  for( int c = 1 ; c < nbOfClasses ; ++c ){
299  typename std::list< aims::Individuals<T> >::const_iterator iter( classes[c].begin() ),
300  last( classes[c].end() ) ;
301  while( iter != last ){
302  dist = myDistance( iter->value(), myMeanVector[c].value(), myBeginIndex, myEndIndex ) ;
303  glob_dist += (double) dist ;
304  ++iter ;
305  }
306  }
307  return glob_dist ;
308 }
309 
310 
311 template <class T>
312 float aims::KmeansStrategy<T>::distance( const aims::Individuals<T>& individual, int classe )
313 {
314  // calculer la distance entre l'individu et le vecteur moyen de la classe
315  float distanceToClass = 0. ;
316  distanceToClass = myDistance( individual.value(), myMeanVector[classe].value(),
317  myBeginIndex, myEndIndex ) ;
318  return distanceToClass ;
319 }
320 
321 #endif
virtual double globInertia(const std::vector< std::list< Individuals< T > > > &classes)
float min(float x, float y)
Definition: thickness.h:105
KmeansStrategy(const KmeansStrategy< T > &kmeanStrat)
virtual void init(std::string initializationType, int nbOfClasses, std::vector< std::list< Individuals< T > > > &classes)
std::vector< Individuals< T > > myMeanVector
virtual ClassifStrategy< T > * clone() const
virtual void analyse(const std::vector< std::list< Individuals< T > > > &classes)
virtual float distance(const Individuals< T > &individual, int classe)
std::vector< Individuals< T > > myVarianceVector
const std::vector< T > & value() const
Definition: individuals.h:51
virtual int aggregate(const Individuals< T > &individual)
float(* myDistance)(const std::vector< T > &ind1, const std::vector< T > &ind2, unsigned int beginIndex, unsigned int endIndex)
#define ASSERT(EX)
virtual double iterate(int &nbOfIterations, std::vector< std::list< Individuals< T > > > &classes)