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 double[]
  87     extractMoments (double []data, int num_elts, int num_moments)
  88     {
  89       double[] moments = new double[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] += 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 void
 112     zscoreTransform (double[][] data, /* in & out: [numObjects][numAttributes] */
 113         int     numObjects,
 114         int     numAttributes)
 115     {
 116       double[] moments;
 117       double[] single_variable = new double[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] = 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 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         double[][]  attributes,           /* [numObjects][numAttributes] */
 141         int      use_zscore_transform,
 142         int      min_nclusters,          /* testing k range from min to max */
 143         int      max_nclusters,
 144         double    threshold,              /* in:   */
 145         int     best_nclusters,          /* out: number between min and max */
 146         double[][] cluster_centres,       /* out: [best_nclusters][numAttributes] */
 147         int[]     cluster_assign,        /* out: [numObjects] */
 148         GlobalArgs args                 /* Thread arguments */
 149         )
 150     {
 151       int itime;
 152       int nclusters;
 153       //random_t* randomPtr;
 154       //Random randomPtr = null;
 155
 156       double[][] tmp_cluster_centres = null;
 157       int[] membership = new int[numObjects];
 158
 159       Random randomPtr = new Random();
 160       randomPtr = randomPtr.random_alloc(randomPtr);
 161
 162       if (use_zscore_transform == 1) {
 163         zscoreTransform(attributes, numObjects, numAttributes);
 164       }
 165
 166       itime = 0;
 167
 168       /*
 169        * From min_nclusters to max_nclusters, find best_nclusters
 170        */
 171       for (nclusters = min_nclusters; nclusters <= max_nclusters; nclusters++) {
 172
 173         randomPtr.random_seed(randomPtr, 7);
 174         args.nclusters = nclusters;
 175
 176         Normal norm = new Normal();
 177
 178         tmp_cluster_centres = norm.normal_exec(nthreads,
 179             attributes,
 180             numAttributes,
 181             numObjects,
 182             nclusters,
 183             threshold,
 184             membership,
 185             randomPtr,
 186             args);
 187
 188         {
 189           cluster_centres = tmp_cluster_centres;
 190           best_nclusters = nclusters;
 191         }
 192
 193         itime++;
 194       } /* nclusters */
 195
 196       randomPtr = null;
 197     }
 198 }
 199
 200
 201 /* =============================================================================
 202  *
 203  * End of cluster.java
 204  *
 205  * =============================================================================
 206  */