SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
KMeansLloydImpl.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2014 Parijat Mazumdar
8  */
9 
14 #include <shogun/io/SGIO.h>
15 
16 using namespace shogun;
17 
18 namespace shogun
19 {
20 void CKMeansLloydImpl::Lloyd_KMeans(int32_t k, CDistance* distance, int32_t max_iter, SGMatrix<float64_t> mus,
21  SGVector<int32_t> ClList, SGVector<float64_t> weights_set, bool fixed_centers)
22 {
25  int32_t XSize=lhs->get_num_vectors();
26  int32_t dimensions=lhs->get_num_features();
27 
29  CFeatures* rhs_cache=distance->replace_rhs(rhs_mus);
30 
32  dists.zero();
33 
34  int32_t changed=1;
35  int32_t iter=0;
36  int32_t vlen=0;
37  bool vfree=false;
38  float64_t* vec=NULL;
39 
40  while (changed && (iter<max_iter))
41  {
42  iter++;
43  if (iter==max_iter-1)
44  SG_SWARNING("kmeans clustering changed throughout %d iterations stopping...\n", max_iter-1)
45 
46  if (iter%1000 == 0)
47  SG_SINFO("Iteration[%d/%d]: Assignment of %i patterns changed.\n", iter, max_iter, changed)
48  changed=0;
49 
50  if (!fixed_centers)
51  {
52  /* mus=zeros(dimensions, k) ; */
53  mus.zero();
54  for (int32_t i=0; i<XSize; i++)
55  {
56  int32_t Cl=ClList[i];
57 
58  vec=lhs->get_feature_vector(i, vlen, vfree);
59 
60  for (int32_t j=0; j<dimensions; j++)
61  mus.matrix[Cl*dimensions+j] += vec[j];
62 
63  lhs->free_feature_vector(vec, i, vfree);
64  }
65 
66  for (int32_t i=0; i<k; i++)
67  {
68  if (weights_set[i]!=0.0)
69  {
70  for (int32_t j=0; j<dimensions; j++)
71  mus.matrix[i*dimensions+j] /= weights_set[i];
72  }
73  }
74  }
75  rhs_mus->copy_feature_matrix(mus);
76  for (int32_t i=0; i<XSize; i++)
77  {
78  /* ks=ceil(rand(1,XSize)*XSize) ; */
79  const int32_t Pat=CMath::random(0, XSize-1);
80  const int32_t ClList_Pat=ClList[Pat];
81  int32_t imini, j;
82  float64_t mini;
83 
84  /* compute the distance of this point to all centers */
85  for(int32_t idx_k=0;idx_k<k;idx_k++)
86  dists[idx_k]=distance->distance(Pat,idx_k);
87 
88  /* [mini,imini]=min(dists(:,i)) ; */
89  imini=0 ; mini=dists[0];
90  for (j=1; j<k; j++)
91  if (dists[j]<mini)
92  {
93  mini=dists[j];
94  imini=j;
95  }
96 
97  if (imini!=ClList_Pat)
98  {
99  changed++;
100 
101  /* weights_set(imini) = weights_set(imini) + 1.0 ; */
102  weights_set[imini]+= 1.0;
103  /* weights_set(j) = weights_set(j) - 1.0 ; */
104  weights_set[ClList_Pat]-= 1.0;
105 
106  vec=lhs->get_feature_vector(Pat, vlen, vfree);
107 
108  for (j=0; j<dimensions; j++)
109  {
110  mus.matrix[imini*dimensions+j]-=
111  (vec[j]-mus.matrix[imini*dimensions+j]) / weights_set[imini];
112  }
113 
114  lhs->free_feature_vector(vec, Pat, vfree);
115 
116  /* mu_new = mu_old - (x - mu_old)/(n-1) */
117  /* if weights_set(j)~=0 */
118  if (weights_set[ClList_Pat]!=0.0)
119  {
120  vec=lhs->get_feature_vector(Pat, vlen, vfree);
121 
122  for (j=0; j<dimensions; j++)
123  {
124  mus.matrix[ClList_Pat*dimensions+j]-=
125  (vec[j]-mus.matrix[ClList_Pat*dimensions+j]) / weights_set[ClList_Pat];
126  }
127  lhs->free_feature_vector(vec, Pat, vfree);
128  }
129  else
130  {
131  /* mus(:,j)=zeros(dimensions,1) ; */
132  for (j=0; j<dimensions; j++)
133  mus.matrix[ClList_Pat*dimensions+j]=0;
134  }
135 
136  /* ClList(i)= imini ; */
137  ClList[Pat] = imini;
138  }
139  }
140  }
141  distance->replace_rhs(rhs_cache);
142  delete rhs_mus;
143  SG_UNREF(lhs);
144 }
145 }

SHOGUN Machine Learning Toolbox - Documentation