MOA 12.03
Real Time Analytics for Data Streams
|
00001 package moa.cluster; 00002 00003 import java.util.ArrayList; 00004 00061 public class Miniball { 00062 00063 int d; 00064 ArrayList L; 00065 Miniball_b B; 00066 int support_end = 0; 00067 00068 public Miniball(int dim) { 00069 d = dim; 00070 L = new ArrayList(); 00071 B = new Miniball_b(); 00072 } 00073 00074 class pvt { 00075 int val; 00076 00077 pvt() { 00078 val = 0; 00079 } 00080 00081 void setVal(int i) { 00082 val = i; 00083 } 00084 00085 int getVal() { 00086 return (val); 00087 } 00088 } 00089 00090 class Miniball_b { 00091 00092 int m, s; // size and number of support points 00093 double[] q0 = new double[d]; 00094 double[] z = new double[d + 1]; 00095 double[] f = new double[d + 1]; 00096 double[][] v = new double[d + 1][d]; 00097 double[][] a = new double[d + 1][d]; 00098 double[][] c = new double[d + 1][d]; 00099 double[] sqr_r = new double[d + 1]; 00100 double[] current_c = new double[d]; // refers to some c[j] 00101 double current_sqr_r; 00102 00103 00104 double[] getCenter() { 00105 return (current_c); 00106 } 00107 00108 double squared_radius() { 00109 return current_sqr_r; 00110 } 00111 00112 int size() { 00113 return m; 00114 } 00115 00116 int support_size() { 00117 return s; 00118 } 00119 00120 double excess(double[] p) { 00121 double e = -current_sqr_r; 00122 for (int k = 0; k < d; ++k) { 00123 e += mb_sqr(p[k] - current_c[k]); 00124 } 00125 return e; 00126 } 00127 00128 void reset() { 00129 m = 0; 00130 s = 0; 00131 // we misuse c[0] for the center of the empty sphere 00132 for (int j = 0; j < d; j++) { 00133 c[0][j] = 0; 00134 } 00135 current_c = c[0]; 00136 current_sqr_r = -1; 00137 } 00138 00139 void pop() { 00140 --m; 00141 } 00142 00143 boolean push(double[] p) { 00144 //System.out.println("Miniball_b:push"); 00145 int i, j; 00146 double eps = 1e-32; 00147 00148 if (m == 0) { 00149 for (i = 0; i < d; ++i) { 00150 q0[i] = p[i]; 00151 } 00152 for (i = 0; i < d; ++i) { 00153 c[0][i] = q0[i]; 00154 } 00155 sqr_r[0] = 0; 00156 } else { 00157 // set v_m to Q_m 00158 for (i = 0; i < d; ++i) { 00159 v[m][i] = p[i] - q0[i]; 00160 } 00161 00162 // compute the a_{m,i}, i< m 00163 for (i = 1; i < m; ++i) { 00164 a[m][i] = 0; 00165 for (j = 0; j < d; ++j) { 00166 a[m][i] += v[i][j] * v[m][j]; 00167 } 00168 a[m][i] *= (2 / z[i]); 00169 } 00170 00171 // update v_m to Q_m-\bar{Q}_m 00172 for (i = 1; i < m; ++i) { 00173 for (j = 0; j < d; ++j) { 00174 v[m][j] -= a[m][i] * v[i][j]; 00175 } 00176 } 00177 00178 // compute z_m 00179 z[m] = 0; 00180 for (j = 0; j < d; ++j) { 00181 z[m] += mb_sqr(v[m][j]); 00182 } 00183 z[m] *= 2; 00184 00185 // reject push if z_m too small 00186 if (z[m] < eps * current_sqr_r) { 00187 return false; 00188 } 00189 00190 // update c, sqr_r 00191 double e = -sqr_r[m - 1]; 00192 for (i = 0; i < d; ++i) { 00193 e += mb_sqr(p[i] - c[m - 1][i]); 00194 } 00195 f[m] = e / z[m]; 00196 00197 for (i = 0; i < d; ++i) { 00198 c[m][i] = c[m - 1][i] + f[m] * v[m][i]; 00199 } 00200 sqr_r[m] = sqr_r[m - 1] + e * f[m] / 2; 00201 } 00202 current_c = c[m]; 00203 current_sqr_r = sqr_r[m]; 00204 s = ++m; 00205 return true; 00206 } 00207 00208 double slack() { 00209 double min_l = 0; 00210 double[] l = new double[d + 1]; 00211 l[0] = 1; 00212 for (int i = s - 1; i > 0; --i) { 00213 l[i] = f[i]; 00214 for (int k = s - 1; k > i; --k) { 00215 l[i] -= a[k][i] * l[k]; 00216 } 00217 if (l[i] < min_l) { 00218 min_l = l[i]; 00219 } 00220 l[0] -= l[i]; 00221 } 00222 if (l[0] < min_l) { 00223 min_l = l[0]; 00224 } 00225 return ((min_l < 0) ? -min_l : 0); 00226 } 00227 } 00228 00236 public void clear() { 00237 L.clear(); 00238 } 00239 00245 public void check_in(double[] p) { 00246 if (p != null) { 00247 L.add(p); 00248 } else { 00249 System.out.println("Miniball.check_in WARNING: Skipping null point"); 00250 } 00251 } 00252 00253 00258 public void build() { 00259 B.reset(); 00260 support_end = 0; 00261 pivot_mb(points_end()); 00262 } 00263 00264 void mtf_mb(int i) { 00265 int pj = 0; 00266 support_end = points_begin(); 00267 if ((B.size()) == d + 1) { 00268 return; 00269 } 00270 for (int k = points_begin(); k != i;) { 00271 pj = pj + 1; 00272 int j = k++; 00273 double[] sp = (double[]) L.get(j); 00274 if (B.excess(sp) > 0) { 00275 if (B.push(sp)) { 00276 mtf_mb(j); 00277 B.pop(); 00278 move_to_front(j); 00279 } 00280 } 00281 } 00282 } 00283 00284 void move_to_front(int j) { 00285 00286 if (support_end <= j) { 00287 support_end++; 00288 } 00289 // L.splice (L.begin(), L, j); 00290 double[] sp = (double[]) L.get(j); 00291 L.remove(j); 00292 L.add(0, sp); 00293 } 00294 00295 void pivot_mb(int i) { 00296 int t = 1; 00297 mtf_mb(t); 00298 double max_e = 0.0, old_sqr_r = -1; 00299 pvt pivot = new pvt(); 00300 do { 00301 max_e = max_excess(t, i, pivot); 00302 if (max_e > 0) { 00303 t = support_end; 00304 if (t == pivot.getVal()) { 00305 ++t; 00306 } 00307 old_sqr_r = B.squared_radius(); 00308 double[] sp = (double[]) L.get(pivot.getVal()); 00309 B.push(sp); 00310 mtf_mb(support_end); 00311 B.pop(); 00312 move_to_front(pivot.getVal()); 00313 } 00314 } while ((max_e > 0) && (B.squared_radius() > old_sqr_r)); 00315 } 00316 00317 double max_excess(int t, int i, pvt pivot) { 00318 double[] c = B.getCenter(); 00319 double sqr_r = B.squared_radius(); 00320 double e, max_e = 0; 00321 for (int k = t; k != i; ++k) { 00322 double[] p = (double[]) L.get(k); 00323 00324 e = -sqr_r; 00325 for (int j = 0; j < d; ++j) { 00326 e += mb_sqr(p[j] - c[j]); 00327 } 00328 if (e > max_e) { 00329 max_e = e; 00330 pivot.setVal(k); 00331 } 00332 } 00333 return max_e; 00334 } 00335 00340 public double[] center() { 00341 return B.getCenter(); 00342 } 00343 00348 public double squared_radius() { 00349 return B.squared_radius(); 00350 } 00351 00356 public double radius() { 00357 return ((1 + 0.00001) * Math.sqrt(B.squared_radius())); 00358 } 00359 00364 public int nr_points() { 00365 return L.size(); 00366 } 00367 00368 int points_begin() { 00369 return (0); 00370 } 00371 00372 int points_end() { 00373 return (L.size()); 00374 } 00375 00381 public int nr_support_points() { 00382 return B.support_size(); 00383 } 00384 00385 int support_points_begin() { 00386 return (0); 00387 } 00388 00389 int support_points_end() { 00390 return support_end; 00391 } 00392 00393 double accuracy(double slack) { 00394 double e, max_e = 0; 00395 int n_supp = 0; 00396 00397 int i; 00398 for (i = points_begin(); i != support_end; ++i, ++n_supp) { 00399 double[] sp = (double[]) L.get(i); 00400 if ((e = Math.abs(B.excess(sp))) > max_e) { 00401 max_e = e; 00402 } 00403 } 00404 if (n_supp == nr_support_points()) { 00405 System.out.println("Miniball.accuracy WARNING: STRANGE PROBLEM HERE!"); 00406 } 00407 for (i = support_end; i != points_end(); ++i) { 00408 double[] sp = (double[]) L.get(i); 00409 if ((e = B.excess(sp)) > max_e) { 00410 max_e = e; 00411 } 00412 } 00413 slack = B.slack(); 00414 return (max_e / squared_radius()); 00415 } 00416 00417 boolean is_valid(double tolerance) { 00418 double slack = 0.0; 00419 return ((accuracy(slack) < tolerance) && (slack == 0)); 00420 } 00421 00422 double mb_sqr(double r) { 00423 return r * r; 00424 } 00425 }