/*
* 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.
*/
/*
* 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
*
*/
package medusa.georgios.ClusteringAlgorithms;
import java.io.*;
import java.util.*;
import medusa.DemoTools;
import medusa.graph.BasicGraph;
import medusa.graph.Edge;
import medusa.graph.Graph;
import medusa.graph.GraphMatrix;
/**
* Implements the k-means algorithm
* @author Manas Somaiya mhs@cise.ufl.edu
*/
public class KMeans2 {
/** 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;
/**
* Returns a new instance of kMeans algorithm
*
* @param k number of clusters
* @param inputFileName name of the file containing input data
*/
public KMeans2(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()
public KMeans2(int k, BasicGraph g) {
this.k = k;
GraphMatrix gm = new GraphMatrix(g);
int size = g.getNodeSize();
this.kMeansPoints = new Vector();
for (int i = 0; i < size; i++) {
// System.out.println("adding "+gm.getLabelForIndex(i)+" "+gm.getRowForIndex(i));
kMeansPoints.add(new KMeansPoint(gm.getLabelForIndex(i), gm.getRowForIndex(i)));
}
this.clusters = new cluster[this.k];
this.nIterations = 0;
} // end of kMeans()
/**
* Returns a new instance of kMeans algorithm
*
* @param k number of clusters
* @param kMeansPoints List containing objects of type kMeansPoint
*/
public KMeans2(int k, List kMeansPoints) {
this.k = k;
this.clusters = new cluster[this.k];
this.nIterations = 0;
this.kMeansPoints = new Vector(kMeansPoints);
} // 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], Float.parseFloat(result[1]),
Float.parseFloat(result[2]));
dp.assignToCluster(0);
this.kMeansPoints.add(dp);
}
//System.out.println("106: "+this.kMeansPoints.size());
}
in.close();
} // end of readData()
/**
* Runs the k-means algorithm over the data set
*/
public void runKMeans() {
//System.out.println("118: "+k);
KMeansPoint km=(KMeansPoint) kMeansPoints.elementAt(0);
// 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(km.size()));
/* 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(int dim) {
boolean reply = false;
double[] x = new double[this.k];
double[] y = new double[this.k];
// create a centroid point
float[][] centroid = new float[dim][k];
int[] size = new int[this.k];
KMeansPoint[] pastMeans = new KMeansPoint[this.k];
for (int i = 0; i < this.k; i++) {
// reset everything to zero
// 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();
// this is to get the mean value of each dimension in cluster k
for (int index = 0; index < dim; index++) {
centroid[index][currentCluster] += dp.getCoordinate(index);
// y[currentCluster] += dp.getY();
}
size[currentCluster]++;
}
// the centroid is point temp
for (int j = 0; j < this.k; j++) {
if (size[j] != 0) {
double[] coords=new double[dim];
for (int index = 0; index < dim; index++) {
centroid[index][j] /= size[j];
coords[index]=centroid[index][j];
// y[currentCluster] += dp.getY();
}
// add this point as a centroid for k
KMeansPoint temp = new KMeansPoint("temp", coords);
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 String Save_To_File(String filename)
{
try {
System.out.println("General Information");
BufferedWriter outp = new BufferedWriter(new FileWriter(filename));
outp.append((this.getReport()));
outp.close();
return this.getReport();
} catch (IOException e) {}
return null;
}
private boolean updateMeansBackup() {
boolean reply = false;
double[] x = new double[this.k];
double[] y = new double[this.k];
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();
x[currentCluster] += dp.getX();
y[currentCluster] += dp.getY();
size[currentCluster]++;
}
// the centroid is point temp
for (int j = 0; j < this.k; j++) {
if (size[j] != 0) {
x[j] /= size[j];
y[j] /= size[j];
KMeansPoint temp = new KMeansPoint("temp", (float) x[j], (float) y[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()
/**
* Returns the value of k
*
* @return the value of k
*/
public int getK() {
return this.k;
} // end of getK()
/**
* Returns the specified cluster by index
*
* @param index index of the cluster to be returned
* @return return the specified cluster by index
*/
public cluster getCluster(int index) {
return getCluster(index);
} // end of getCluster()
/**
* Returns the string output of the data points
*
* @return the string output of the data points
*/
public String toString() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < kMeansPoints.size(); i++) {
sb.append(kMeansPoints.elementAt(i).toString());
sb.append("\n");
//System.out.println(kMeansPoints.elementAt(i).toString());
}
return sb.toString();
} // end of toString()
/**
* Returns the data points
*
* @return the data points
*/
public Vector getDataPoints() {
return this.kMeansPoints;
} // end of getDataPoints()
public Map 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 String getReport() {
//Map map=getClusterMap();
StringBuffer sb = new StringBuffer();
for (int i = 1; i <= k; i++) {
sb.append("----------------- Cluster: " + i + " -----------------\n");
for (int point = 0; point < kMeansPoints.size(); point++) {
KMeansPoint kpoint = (KMeansPoint) kMeansPoints.get(point);
if (kpoint.getClusterNumber() == i-1) {
sb.append(kpoint.getLabel());
sb.append("\n");
}
}
}
//System.out.println(sb);
return sb.toString();
}
public void Save_To_File(String filename, String information) {
try {
BufferedWriter outp = new BufferedWriter(new FileWriter(filename));
outp.append(information);
outp.close();
} catch (IOException e) {
}
}
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) {
DemoTools dt = new DemoTools();
//Graph g = dt.randomGraph(10, 40);
Graph g = new Graph();
g.addEdge(new Edge("a", "b", 0.4f));
g.addEdge(new Edge("c", "b", 0.8f));
g.addEdge(new Edge("a", "c", 0.0f));
//System.out.println(g.report());
KMeans2 km = new KMeans2(2, g);
km.runKMeans();
System.out.println(km.getReport());
System.out.println(km);
} // end of main()
} // end of class
//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
*
*/
/**
* 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.