MOA 12.03
Real Time Analytics for Data Streams
Miniball.java
Go to the documentation of this file.
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 }
 All Classes Namespaces Files Functions Variables Enumerations