Robust/src/Benchmarks/oooJava/kmeans/KMeans.java

   1  /* =============================================================================
   2  *
   3  * kmeans.java
   4  *
   5  * =============================================================================
   6  *
   7  * Description:
   8  *
   9  * Takes as input a file:
  10  *   ascii  file: containing 1 data point per line
  11  *   binary file: first int is the number of objects
  12  *                2nd int is the no. of features of each object
  13  *
  14  * This example performs a fuzzy c-means clustering on the data. Fuzzy clustering
  15  * is performed using min to max clusters and the clustering that gets the best
  16  * score according to a compactness and separation criterion are returned.
  17  *
  18  *
  19  * Author:
  20  *
  21  * Wei-keng Liao
  22  * ECE Department Northwestern University
  23  * email: wkliao@ece.northwestern.edu
  24  *
  25  *
  26  * Edited by:
  27  *
  28  * Jay Pisharath
  29  * Northwestern University
  30  *
  31  * Chi Cao Minh
  32  * Stanford University
  33  *
  34  * Port to Java version
  35  * Alokika Dash
  36  * University of California, Irvine
  37  *
  38  * =============================================================================
  39  *
  40  * ------------------------------------------------------------------------
  41  *
  42  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  43  *
  44  * ------------------------------------------------------------------------
  45  *
  46  * Unless otherwise noted, the following license applies to STAMP files:
  47  *
  48  * Copyright (c) 2007, Stanford University
  49  * All rights reserved.
  50  *
  51  * Redistribution and use in source and binary forms, with or without
  52  * modification, are permitted provided that the following conditions are
  53  * met:
  54  *
  55  *     * Redistributions of source code must retain the above copyright
  56  *       notice, this list of conditions and the following disclaimer.
  57  *
  58  *     * Redistributions in binary form must reproduce the above copyright
  59  *       notice, this list of conditions and the following disclaimer in
  60  *       the documentation and/or other materials provided with the
  61  *       distribution.
  62  *
  63  *     * Neither the name of Stanford University nor the names of its
  64  *       contributors may be used to endorse or promote products derived
  65  *       from this software without specific prior written permission.
  66  *
  67  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  68  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  69  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  70  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  71  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  72  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  73  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  74  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  75  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  76  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  77  * THE POSSIBILITY OF SUCH DAMAGE.
  78  *
  79  * =============================================================================
  80  */
  81
  82 public class KMeans /*extends Thread*/ {
  83   /**
  84    * User input for max clusters
  85    **/
  86   int max_nclusters;
  87
  88   /**
  89    * User input for min clusters
  90    **/
  91   int min_nclusters;
  92
  93   /**
  94    * Check for Binary file
  95    **/
  96   int isBinaryFile;
  97
  98   /**
  99    * Using zscore transformation for cluster center
 100    * deviating from distribution's mean
 101    **/
 102   int use_zscore_transform;
 103
 104   /**
 105    * Input file name used for clustering
 106    **/
 107   String filename;
 108
 109   /**
 110    * Total number of threads
 111    **/
 112   int nthreads;
 113
 114   /**
 115    * threshold until which kmeans cluster continues
 116    **/
 117   float threshold;
 118
 119   /**
 120    * thread id
 121    **/
 122   int threadid;
 123
 124   /**
 125    * Global arguments for threads
 126    **/
 127   GlobalArgs g_args;
 128
 129   /**
 130    * Output:  Number of best clusters
 131    **/
 132   int best_nclusters;
 133
 134   /**
 135    * Output: Cluster centers
 136    **/
 137   float[][] cluster_centres;
 138
 139   public boolean validationTest;
 140
 141   public KMeans() {
 142     max_nclusters = 13;
 143     min_nclusters = 4;
 144     isBinaryFile = 0;
 145     use_zscore_transform = 1;
 146     threshold = (float) 0.001;
 147     best_nclusters=0;
 148     validationTest=false;
 149   }
 150
 151   public KMeans(int threadid, GlobalArgs g_args) {
 152     this.threadid = threadid;
 153     this.g_args = g_args;
 154   }
 155
 156   public void run() {
 157     while(true) {
 158 //      Barrier.enterBarrier();
 159       Normal.work(threadid, g_args);
 160 //      Barrier.enterBarrier();
 161     }
 162   }
 163
 164   /* =============================================================================
 165    * main
 166    * =============================================================================
 167    */
 168   public static void main(String[] args) {
 169     int nthreads;
 170     int MAX_LINE_LENGTH = 1000000; /* max input is 400000 one digit input + spaces */
 171
 172     /**
 173      * Read options fron the command prompt
 174      **/
 175     KMeans kms = new KMeans();
 176     KMeans.parseCmdLine(args, kms);
 177     nthreads = kms.nthreads;
 178
 179     /* Initiate Barriers */
 180 //    Barrier.setBarrier(nthreads);
 181
 182     if (kms.max_nclusters < kms.min_nclusters) {
 183       System.out.println("Error: max_clusters must be >= min_clusters\n");
 184       System.exit(0);
 185     }
 186
 187     float[][] buf;
 188     float[][] attributes;
 189     int numAttributes = 0;
 190     int numObjects = 0;
 191
 192     /*
 193      * From the input file, get the numAttributes (columns in txt file) and numObjects (rows in txt file)
 194      */
 195     if (kms.isBinaryFile == 1) {
 196       System.out.println("TODO: Unimplemented Binary file option\n");
 197       System.exit(0);
 198     }
 199
 200     FileInputStream inputFile = new FileInputStream(kms.filename);
 201     byte b[] = new byte[MAX_LINE_LENGTH];
 202     int n;
 203     while ((n = inputFile.read(b)) != 0) {
 204       for (int i = 0; i < n; i++) {
 205         if (b[i] == '\n')
 206           numObjects++;
 207       }
 208     }
 209     inputFile.close();
 210     inputFile = new FileInputStream(kms.filename);
 211     String line = null;
 212     if((line = inputFile.readLine()) != null) {
 213       int index = 0;
 214       boolean prevWhiteSpace = true;
 215       while(index < line.length()) {
 216         char c = line.charAt(index++);
 217         boolean currWhiteSpace = Character.isWhitespace(c);
 218         if(prevWhiteSpace && !currWhiteSpace){
 219           numAttributes++;
 220         }
 221         prevWhiteSpace = currWhiteSpace;
 222       }
 223     }
 224     inputFile.close();
 225
 226     /* Ignore the first attribute: numAttributes = 1; */
 227     numAttributes = numAttributes - 1;
 228     System.out.println("numObjects= " + numObjects + " numAttributes= " + numAttributes);
 229
 230     /* Allocate new shared objects and read attributes of all objects */
 231     buf = new float[numObjects][numAttributes];
 232     attributes = new float[numObjects][numAttributes];
 233     KMeans.readFromFile(inputFile, kms.filename, buf, MAX_LINE_LENGTH);
 234     System.out.println("Finished Reading from file ......");
 235     long startT=System.currentTimeMillis();
 236     /*
 237      * The core of the clustering
 238      */
 239
 240     int nloops = 1;
 241     int len = kms.max_nclusters - kms.min_nclusters + 1;
 242
 243     KMeans[] km = new KMeans[nthreads];
 244     GlobalArgs g_args = new GlobalArgs();
 245     g_args.nthreads = nthreads;
 246
 247     /* Create and Start Threads */
 248     for(int i = 1; i<nthreads; i++) {
 249       km[i] = new KMeans(i, g_args);
 250     }
 251
 252     for(int i = 1; i<nthreads; i++) {
 253       km[i].run();
 254     }
 255
 256     System.out.println("Finished Starting threads......");
 257
 258     for (int i = 0; i < nloops; i++) {
 259       /*
 260        * Since zscore transform may perform in cluster() which modifies the
 261        * contents of attributes[][], we need to re-store the originals
 262        */
 263       for(int x = 0; x < numObjects; x++) {
 264         for(int y = 0; y < numAttributes; y++) {
 265           attributes[x][y] = buf[x][y];
 266         }
 267       }
 268
 269       Cluster.cluster_exec(nthreads,
 270           numObjects,
 271           numAttributes,
 272           attributes,             // [numObjects][numAttributes]
 273           kms,                    //main class that holds users inputs from command prompt and output arrays that need to be filled
 274           g_args);                // Global arguments common to all threads
 275     }
 276
 277     long endT=System.currentTimeMillis();
 278     if(!kms.validationTest){
 279     System.out.println("running time="+(endT-startT));
 280     }
 281 //    System.out.println("TIME="+g_args.global_time);
 282
 283     System.out.println("Printing output......");
 284     System.out.println("Best_nclusters= " + kms.best_nclusters);
 285
 286     /* Output: the coordinates of the cluster centres */
 287     if(kms.validationTest){
 288         for (int i = 0; i < kms.best_nclusters; i++) {
 289           System.out.print(i + " ");
 290           for (int j = 0; j < numAttributes; j++) {
 291             System.out.print(kms.cluster_centres[i][j] + " ");
 292           }
 293           System.out.println("\n");
 294         }
 295     }
 296
 297     System.out.println("Finished......");
 298
 299   }
 300
 301   public static void parseCmdLine(String args[], KMeans km) {
 302     int i = 0;
 303     String arg;
 304     while (i < args.length && args[i].startsWith("-")) {
 305       arg = args[i++];
 306       //check options
 307       if(arg.equals("-m")) {
 308         if(i < args.length) {
 309           km.max_nclusters = new Integer(args[i++]).intValue();
 310         }
 311       } else if(arg.equals("-n")) {
 312         if(i < args.length) {
 313           km.min_nclusters = new Integer(args[i++]).intValue();
 314         }
 315       } else if(arg.equals("-t")) {
 316         if(i < args.length) {
 317           km.threshold = (float) Double.parseDouble(args[i++]);
 318         }
 319       } else if(arg.equals("-i")) {
 320         if(i < args.length) {
 321           km.filename = args[i++];
 322         }
 323       } else if(arg.equals("-b")) {
 324         if(i < args.length) {
 325           km.isBinaryFile = new Integer(args[i++]).intValue();
 326         }
 327       } else if(arg.equals("-z")) {
 328         km.use_zscore_transform=0;
 329       } else if(arg.equals("-nthreads")) {
 330         if(i < args.length) {
 331           km.nthreads = new Integer(args[i++]).intValue();
 332         }
 333       } else if(arg.equals("-h")) {
 334         km.usage();
 335       } else if(arg.equals("-v")){
 336         km.validationTest=true;
 337       }
 338     }
 339     if(km.nthreads == 0 || km.filename == null) {
 340       km.usage();
 341     }
 342   }
 343
 344   /**
 345    * The usage routine which describes the program options.
 346    **/
 347   public void usage() {
 348     System.out.println("usage: ./kmeans -m <max_clusters> -n <min_clusters> -t <threshold> -i <filename> -nthreads <threads>\n");
 349     System.out.println(                   "  -i filename:     file containing data to be clustered\n");
 350     System.out.println(                   "  -b               input file is in binary format\n");
 351     System.out.println(                   "  -m max_clusters: maximum number of clusters allowed\n");
 352     System.out.println(                   "  -n min_clusters: minimum number of clusters allowed\n");
 353     System.out.println(                   "  -z             : don't zscore transform data\n");
 354     System.out.println(                   "  -t threshold   : threshold value\n");
 355     System.out.println(                   "  -nthreads      : number of threads\n");
 356   }
 357
 358   /**
 359    * readFromFile()
 360    * Read attributes from the input file into an array
 361    **/
 362   public static void readFromFile(FileInputStream inputFile, String filename, float[][] buf, int MAX_LINE_LENGTH) {
 363     inputFile = new FileInputStream(filename);
 364     int j;
 365     int i = 0;
 366
 367     byte b[] = new byte[MAX_LINE_LENGTH];
 368     int n;
 369     byte oldbytes[]=null;
 370
 371
 372     j = -1;
 373     while ((n = inputFile.read(b)) != 0) {
 374       int x=0;
 375
 376       if (oldbytes!=null) {
 377         //find space
 378         boolean cr=false;
 379         for (;x < n; x++) {
 380           if (b[x] == ' ')
 381             break;
 382           if (b[x] == '\n') {
 383             cr=true;
 384             break;
 385           }
 386         }
 387         byte newbytes[]=new byte[x+oldbytes.length];
 388         boolean isnumber=false;
 389         for(int ii=0;ii<oldbytes.length;ii++) {
 390           if (oldbytes[ii]>='0'&&oldbytes[ii]<='9')
 391             isnumber=true;
 392           newbytes[ii]=oldbytes[ii];
 393         }
 394         for(int ii=0;ii<x;ii++) {
 395           if (b[ii]>='0'&&b[ii]<='9')
 396             isnumber=true;
 397           newbytes[ii+oldbytes.length]=b[ii];
 398         }
 399         if (x!=n)
 400           x++; //skip past space or cr
 401         if (isnumber) {
 402           if (j>=0) {
 403             buf[i][j]=(float)Double.parseDouble(new String(newbytes, 0, newbytes.length));
 404           }
 405           j++;
 406         }
 407         if (cr) {
 408           j=-1;
 409           i++;
 410         }
 411         oldbytes=null;
 412       }
 413
 414       while (x < n) {
 415         int y=x;
 416         boolean cr=false;
 417         boolean isnumber=false;
 418         for(y=x;y<n;y++) {
 419           if ((b[y]>='0')&&(b[y]<='9'))
 420             isnumber=true;
 421           if (b[y]==' ')
 422             break;
 423           if (b[y]=='\n') {
 424             cr=true;
 425             break;
 426           }
 427         }
 428         if (y==n) {
 429           //need to continue for another read
 430           oldbytes=new byte[y-x];
 431           for(int ii=0;ii<(y-x);ii++)
 432             oldbytes[ii]=b[ii+x];
 433           break;
 434         }
 435
 436         //otherwise x is beginning of character string, y is end
 437         if (isnumber) {
 438           if (j>=0) {
 439             buf[i][j]=(float)Double.parseDouble(new String(b,x,y-x));
 440           }
 441           j++;
 442         }
 443         if (cr) {
 444           i++;//skip to next line
 445           j = -1;//don't store line number
 446           x=y;//skip to end of number
 447           x++;//skip past return
 448         } else {
 449           x=y;//skip to end of number
 450           x++;//skip past space
 451         }
 452       }
 453     }
 454     inputFile.close();
 455   }
 456 }
 457
 458 /* =============================================================================
 459  *
 460  * End of kmeans.java
 461  *
 462  * =============================================================================
 463  */