Robust/src/Benchmarks/SingleTM/KMeans/Cluster.java

   1 /* =============================================================================
   2  *
   3  * cluster.java
   4  *
   5  * =============================================================================
   6  *
   7  * Description:
   8  *
   9  * Takes as input a file, containing 1 data point per per line, and performs a
  10  * fuzzy c-means clustering on the data. Fuzzy clustering is performed using
  11  * min to max clusters and the clustering that gets the best score according to
  12  * a compactness and separation criterion are returned.
  13  *
  14  *
  15  * Author:
  16  *
  17  * Brendan McCane
  18  * James Cook University of North Queensland. Australia.
  19  * email: mccane@cs.jcu.edu.au
  20  *
  21  *
  22  * Edited by:
  23  *
  24  * Jay Pisharath, Wei-keng Liao
  25  * Northwestern University
  26  *
  27  * Chi Cao Minh
  28  * Stanford University
  29  *
  30  * Ported to Java:
  31  * Alokika Dash
  32  * University of California, Irvine
  33  *
  34  * =============================================================================
  35  *
  36  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  37  *
  38  * ------------------------------------------------------------------------
  39  *
  40  * Unless otherwise noted, the following license applies to STAMP files:
  41  *
  42  * Copyright (c) 2007, Stanford University
  43  * All rights reserved.
  44  *
  45  * Redistribution and use in source and binary forms, with or without
  46  * modification, are permitted provided that the following conditions are
  47  * met:
  48  *
  49  *     * Redistributions of source code must retain the above copyright
  50  *       notice, this list of conditions and the following disclaimer.
  51  *
  52  *     * Redistributions in binary form must reproduce the above copyright
  53  *       notice, this list of conditions and the following disclaimer in
  54  *       the documentation and/or other materials provided with the
  55  *       distribution.
  56  *
  57  *     * Neither the name of Stanford University nor the names of its
  58  *       contributors may be used to endorse or promote products derived
  59  *       from this software without specific prior written permission.
  60  *
  61  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  62  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  63  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  64  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  65  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  66  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  67  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  68  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  69  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  70  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  71  * THE POSSIBILITY OF SUCH DAMAGE.
  72 *
  73 * =============================================================================
  74 */
  75
  76 public class Cluster {
  77
  78   public Cluster() {
  79
  80   }
  81
  82   /* =============================================================================
  83    * extractMoments
  84    * =============================================================================
  85    */
  86   public static float[]
  87     extractMoments (float []data, int num_elts, int num_moments)
  88     {
  89       float[] moments = new float[num_moments];
  90
  91       float mzero=0.0f;
  92       for (int i = 0; i < num_elts; i++) {
  93         mzero += data[i];
  94       }
  95
  96       moments[0] = mzero / num_elts;
  97       for (int j = 1; j < num_moments; j++) {
  98         moments[j] = 0;
  99         for (int i = 0; i < num_elts; i++) {
 100           moments[j] += (float) Math.pow((data[i]-moments[0]), j+1);
 101         }
 102         moments[j] = moments[j] / num_elts;
 103       }
 104       return moments;
 105     }
 106
 107
 108   /* =============================================================================
 109    * zscoreTransform
 110    * =============================================================================
 111    */
 112   public static void
 113     zscoreTransform (float[][] data, /* in & out: [numObjects][numAttributes] */
 114         int     numObjects,
 115         int     numAttributes)
 116     {
 117       float[] moments;
 118       float[] single_variable = new float[numObjects];
 119       for (int i = 0; i < numAttributes; i++) {
 120         for (int j = 0; j < numObjects; j++) {
 121           single_variable[j] = data[j][i];
 122         }
 123         moments = extractMoments(single_variable, numObjects, 2);
 124         moments[1] = (float) Math.sqrt((double)moments[1]);
 125         for (int j = 0; j < numObjects; j++) {
 126           data[j][i] = (data[j][i]-moments[0])/moments[1];
 127         }
 128       }
 129     }
 130
 131
 132   /* =============================================================================
 133    * cluster_exec
 134    * =============================================================================
 135    */
 136   public static void
 137     cluster_exec (
 138         int      nthreads,               /* in: number of threads*/
 139         int      numObjects,             /* number of input objects */
 140         int      numAttributes,          /* size of attribute of each object */
 141         float[][]  attributes,           /* [numObjects][numAttributes] */
 142         KMeans kms,                       /* KMeans class hold the inputs and outputs */
 143         GlobalArgs args                 /* Global thread arguments */
 144         )
 145     {
 146       int itime;
 147       int nclusters;
 148
 149       float[][] tmp_cluster_centres;
 150       int[] membership = new int[numObjects];
 151
 152       Random randomPtr = new Random();
 153       randomPtr.random_alloc();
 154
 155       if (kms.use_zscore_transform == 1) {
 156         zscoreTransform(attributes, numObjects, numAttributes);
 157       }
 158
 159       itime = 0;
 160
 161       /*
 162        * From min_nclusters to max_nclusters, find best_nclusters
 163        */
 164       for (nclusters = kms.min_nclusters; nclusters <= kms.max_nclusters; nclusters++) {
 165
 166         randomPtr.random_seed(7);
 167         args.nclusters = nclusters;
 168
 169         Normal norm = new Normal();
 170
 171         tmp_cluster_centres = norm.normal_exec(nthreads,
 172             attributes,
 173             numAttributes,
 174             numObjects,
 175             nclusters,
 176             kms.threshold,
 177             membership,
 178             randomPtr,
 179             args);
 180
 181         {
 182           kms.cluster_centres = tmp_cluster_centres;
 183           kms.best_nclusters = nclusters;
 184         }
 185
 186         itime++;
 187       } /* nclusters */
 188     }
 189 }
 190
 191 /* =============================================================================
 192  *
 193  * End of cluster.java
 194  *
 195  * =============================================================================
 196  */