Robust/src/Benchmarks/Prefetch/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       for (int i = 0; i < num_elts; i++) {
  92         moments[0] += data[i];
  93       }
  94
  95       moments[0] = moments[0] / num_elts;
  96       for (int j = 1; j < num_moments; j++) {
  97         moments[j] = 0;
  98         for (int i = 0; i < num_elts; i++) {
  99           moments[j] = (float) (moments[j] + Math.pow((data[i]-moments[0]), j+1));
 100         }
 101         moments[j] = moments[j] / num_elts;
 102       }
 103       return moments;
 104     }
 105
 106
 107   /* =============================================================================
 108    * zscoreTransform
 109    * =============================================================================
 110    */
 111   public static void
 112     zscoreTransform (float[][] data, /* in & out: [numObjects][numAttributes] */
 113         int     numObjects,
 114         int     numAttributes)
 115     {
 116       float[] moments;
 117       float[] single_variable = new float[numObjects];
 118       for (int i = 0; i < numAttributes; i++) {
 119         for (int j = 0; j < numObjects; j++) {
 120           single_variable[j] = data[j][i];
 121         }
 122         moments = extractMoments(single_variable, numObjects, 2);
 123         moments[1] = (float) Math.sqrt((double)moments[1]);
 124         for (int j = 0; j < numObjects; j++) {
 125           data[j][i] = (data[j][i]-moments[0])/moments[1];
 126         }
 127       }
 128     }
 129
 130
 131   /* =============================================================================
 132    * cluster_exec
 133    * =============================================================================
 134    */
 135   public static void
 136     cluster_exec (
 137         int      nthreads,               /* in: number of threads*/
 138         int      numObjects,             /* number of input objects */
 139         int      numAttributes,          /* size of attribute of each object */
 140         float[][]  attributes,           /* [numObjects][numAttributes] */
 141         KMeans kms,                      /* KMeans class hold the inputs and outputs */
 142         GlobalArgs args                  /* Global thread arguments */
 143         )
 144     {
 145       int itime;
 146       int nclusters;
 147
 148       float[][] tmp_cluster_centres;
 149       int[] tmp_membership;
 150       atomic {
 151         int[] membership = global new int[numObjects];
 152         tmp_membership = membership;
 153       }
 154
 155       Random randomPtr = new Random();
 156       randomPtr.random_alloc();
 157
 158       atomic {
 159         if (kms.use_zscore_transform == 1) {
 160           zscoreTransform(attributes, numObjects, numAttributes);
 161         }
 162       }
 163
 164       itime = 0;
 165
 166       //
 167       // From min_nclusters to max_nclusters, find best_nclusters
 168       //
 169       for (nclusters = kms.min_nclusters; nclusters <= kms.max_nclusters; nclusters++) {
 170
 171         randomPtr.random_seed(7);
 172         Normal norm = new Normal();
 173
 174         //System.out.println("nclusters= " + nclusters + " min_nclusters= " + min_nclusters + " max_nclusters= " + max_nclusters);
 175         GlobalArgs tmp_args;
 176         atomic {
 177           tmp_args = args;
 178         }
 179
 180
 181         tmp_cluster_centres = norm.normal_exec(nthreads,
 182             attributes,
 183             numAttributes,
 184             numObjects,
 185             nclusters,
 186             kms.threshold,
 187             tmp_membership,
 188             randomPtr,
 189             tmp_args);
 190
 191         {
 192           //kms.cluster_centres = tmp_cluster_centres;
 193           kms.best_nclusters = nclusters;
 194         }
 195
 196         itime++;
 197       } // nclusters
 198     }
 199 }
 200
 201 /* =============================================================================
 202  *
 203  * End of cluster.java
 204  *
 205  * =============================================================================
 206  */