/*
* Kmeans2.java
*
* Created on November 30, 2007, 12:34 PM
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
package medusa.spectral;
/*
* Implements the k-means algorithm
*
* Manas Somaiya
* Computer and Information Science and Engineering
* University of Florida
*
* Created: October 29, 2003
* Last updated: October 30, 2003
*
*/
import java.io.*;
import java.util.*;
//public static void main(String[] args) {
//
// KMeans2 km=new KMeans2(2,"/scratch/home2/testcluster.txt");
//
//// cluster c1 = new cluster(1);
//// c1.setMean(new KMeansPoint("test",3,4));
//// System.out.println(c1.getMean());
//
//
// } // end of main()
/*
* Represents an abstraction for a cluster of data points in two dimensional space
*
* Manas Somaiya
* Computer and Information Science and Engineering
* University of Florida
*
* Created: October 29, 2003
* Last updated: October 30, 2003
*
*/
/**
* Implements the k-means algorithm
* @author Manas Somaiya mhs@cise.ufl.edu
*/
public class KMeans {
/** Number of clusters */
private int k;
/** Array of clusters */
private cluster[] clusters;
/** Number of iterations */
private int nIterations;
/** Vector of data points */
private Vector kMeansPoints;
/** Name of the input file */
private String inputFileName;
/** Dimensions of the data */
int dimensions;
/**
* Returns a new instance of kMeans algorithm
*
* @param k number of clusters
* @param inputFileName name of the file containing input data
*/
public KMeans(int k, String inputFileName) {
this.k = k;
this.inputFileName = inputFileName;
this.clusters = new cluster[this.k];
this.nIterations = 0;
this.kMeansPoints = new Vector();
} // end of kMeans()
/**
* Returns a new instance of kMeans algorithm
*
* @param k number of clusters
* @param kMeansPoints List containing objects of type kMeansPoint
*/
public KMeans(int k, List kMeansPoints) {
this.k = k;
this.clusters = new cluster[this.k];
this.nIterations = 0;
this.kMeansPoints = new Vector(kMeansPoints);
this.dimensions = kMeansPoints.get(0).getDimensions();
} // end of kMeans()
/**
* Reads the input data from the file and stores the data points in the vector
*/
public void readData() throws IOException {
BufferedReader in = new BufferedReader(new FileReader(this.inputFileName));
String line = "";
while ((line = in.readLine()) != null) {
String[] result = line.split("\t");
//StringTokenizer st = new StringTokenizer(line, " \t\n\r\f,");
if (result.length == 3) {
KMeansPoint dp = new KMeansPoint(result[0], Double.parseDouble(result[1]), Double.parseDouble(result[2]));
dp.assignToCluster(0);
this.kMeansPoints.add(dp);
}
//System.out.println("106: "+this.kMeansPoints.size());
}
in.close();
} // end of readData()
public Vector getVector(){
return kMeansPoints;
}
/**
* Runs the k-means algorithm over the data set
*/
public void runKMeans() {
//System.out.println("118: "+k);
// Select k points as initial means
for (int i = 0; i < k; i++) {
this.clusters[i] = new cluster(i);
this.clusters[i].setMean((KMeansPoint) (this.kMeansPoints.get((int) (Math.random() * this.kMeansPoints.size()))));
//System.out.println("Intitial "+i+" set to"+clusters[i].getMean().getX()+" "+clusters[i].getMean().getY());
}
do {
// Form k clusters
Iterator i = this.kMeansPoints.iterator();
while (i.hasNext()) {
this.assignToCluster((KMeansPoint) (i.next()));
}
this.nIterations++;
// System.out.println(this.nIterations);
} // Repeat while centroids do not change
while (this.updateMeans());
/* for (int i=0; i < k; i++){
System.out.println("Final "+i+" set to"+clusters[i].getMean().getX()+" "+clusters[i].getMean().getY());
}*/
} // end of runKMeans()
/**
* Assigns a data point to one of the k clusters based on its distance from the means of the clusters
*
* @param dp data point to be assigned
*/
private void assignToCluster(KMeansPoint dp) {
int currentCluster = dp.getClusterNumber();
double minDistance = KMeansPoint.distance(dp, this.clusters[currentCluster].getMean());
for (int i = 0; i < this.k; i++) {
double tdist = KMeansPoint.distance(dp, this.clusters[i].getMean());
if (tdist < minDistance) {
minDistance = tdist;
currentCluster = i;
}
}
//System.out.println("assigned "+dp.toDataString()+" to "+clusters[currentCluster].getMean().toDataString());
dp.assignToCluster(currentCluster);
} // end of assignToCluster
/**
* Updates the means of all k clusters, and returns if they have changed or not
*
* @return have the updated means of the clusters changed or not
*/
private boolean updateMeans() {
boolean reply = false;
double[] x = new double[this.k];
double[] y = new double[this.k];
double[][] means = new double[this.k][dimensions];
int[] size = new int[this.k];
KMeansPoint[] pastMeans = new KMeansPoint[this.k];
for (int i = 0; i < this.k; i++) {
x[i] = 0;
y[i] = 0;
size[i] = 0;
pastMeans[i] = this.clusters[i].getMean();
}
Iterator i = this.kMeansPoints.iterator();
while (i.hasNext()) {
KMeansPoint dp = (KMeansPoint) (i.next());
int currentCluster = dp.getClusterNumber();
for (int index = 0; index < dimensions; index++) {
means[currentCluster][index] += dp.getCoords()[index];
}
// x[currentCluster] += dp.getX();
// y[currentCluster] += dp.getY();
size[currentCluster]++;
}
for (int j = 0; j < this.k; j++) {
if (size[j] != 0) {
for (int index = 0; index < dimensions; index++) {
means[j][index] /=size[j];
}
// x[j] /= size[j];
// y[j] /= size[j];
KMeansPoint temp = new KMeansPoint("temp", means[j]);
temp.assignToCluster(j);
this.clusters[j].setMean(temp);
if (KMeansPoint.distance(pastMeans[j], this.clusters[j].getMean()) != 0) {
reply = true;
}
}
}
return reply;
} // end of updateMeans()
public Vector[] getClusters(){
Vector[] myclusters=new Vector[k];
for (int i=0; i();
}
for (int i=0; i getClusterMap() {
Map map = new HashMap();
for (int i = 0; i < kMeansPoints.size(); i++) {
KMeansPoint km = (KMeansPoint) kMeansPoints.get(i);
map.put(km.getLabel(), km.getClusterNumber());
}
return map;
}
public int getSmallestClusterSize() {
Map map = new HashMap();
for (int i = 0; i < kMeansPoints.size(); i++) {
KMeansPoint km = (KMeansPoint) kMeansPoints.get(i);
Integer cluster = km.getClusterNumber();
Integer count = 1;
if (map.containsKey(cluster)) {
count = map.get(cluster) + 1;
}
map.put(cluster, count);
}
Integer min = Integer.MAX_VALUE;
// check for the smallest number
for (Iterator i = map.values().iterator(); i.hasNext();) {
Integer count = i.next();
if (min > count) {
min = count;
}
}
return min.intValue();
}
/**
* Main method -- to test the kMeans class
*
* @param args command line arguments
*/
public static void main(String[] args) {
KMeans km = new KMeans(2, "/scratch/home2/testcluster.txt");
try {
km.readData();
} catch (Exception e) {
System.err.println(e);
System.exit(-1);
}
km.runKMeans();
System.out.println(km);
} // end of main()
} // end of class
/**
* Represents an abstraction for a cluster of data points in two dimensional space
* @author Manas Somaiya mhs@cise.ufl.edu
*/
class cluster {
/** Cluster Number */
private int clusterNumber;
/** Mean data point of this cluster */
private KMeansPoint mean;
/**
* Returns a new instance of cluster
*
* @param _clusterNumber the cluster number of this cluster
*/
public cluster(int _clusterNumber) {
this.clusterNumber = _clusterNumber;
} // end of cluster()
/**
* Sets the mean data point of this cluster
*
* @param meanDataPoint the new mean data point for this cluster
*/
public void setMean(KMeansPoint meanDataPoint) {
this.mean = meanDataPoint;
} // end of setMean()
/**
* Returns the mean data point of this cluster
*
* @return the mean data point of this cluster
*/
public KMeansPoint getMean() {
return this.mean;
} // end of getMean()
/**
* Returns the cluster number of this cluster
*
* @return the cluster number of this cluster
*/
public int getClusterNumber() {
return this.clusterNumber;
} // end of getClusterNumber()
/**
* Main method -- to test the cluster class
*
* @param args command line arguments
*/
} // end of class
Ads help maintain this website.