package jminhep.algorithms;
import jminhep.utils.*;
import java.util.Random;
import jminhep.cluster.DataHolder;
import jminhep.cluster.DataPoint;
import jminhep.cluster.Get;
import jminhep.gui.SetEnv;
import java.util.Arrays;
import org.apache.commons.math3.util.FastMath;
/**
* The standard K-means algorithm.
*
* @author S.Chekanov
*
*/
public class KMeansAlg {
private double[][] indat;
private int nrow, ncol;
private int Ierr = 0; // error statement
// cluster centers
private DataHolder cMeans;
private DataHolder data;
private DataPoint DMin;
private DataPoint DMax;
private String description;
private int maxIterations, numClusters;
// The iteration counter will be global so we can get its value on the
// middle of the clustering process.
private int iteration;
// A small value, if the difference of the cluster "quality" does not
// changes beyond this value, we consider the clustering converged.
private double epsilon;
// The cluster centers.
private double[][] clusterCenters;
// seed values
private double[][] clusterSeed;
// A big array with all the input data and a small one for a single pixel.
private double[] aPixel;
private double compactness;
// The cluster assignment counter.
private int[] clusterAssignmentCount;
// A big array with the output data (cluster indexes).
private int[] outputData;
// A metric of clustering "quality".
private double sumOfDistances;
// private Random generator;
/**
* Initialize the standard K-means algorithm
* @param data input data
*/
public KMeansAlg(DataHolder data) {
this.data=data;
this.nrow = data.getSize();
this.ncol = data.getDimention();
data.analyseSet(); // get min and max
this.DMin = data.getMin();
this.DMax = data.getMax();
SetEnv.NRow=nrow;
SetEnv.Dim=ncol;
Ierr = 0;
numClusters = 0;
maxIterations = 100;
epsilon = 0.000001;
compactness = 0;
description = "kmeans algorithm";
// System.out.println("No row "+nrow+ " ncol "+ncol);
indat = new double[nrow][ncol]; // hold data
aPixel = new double[ncol];
outputData = new int[nrow];
// Input array, values to be read in successively, float
for (int i = 0; i < nrow; i++) {
DataPoint dp = data.getRow(i);
for (int i2 = 0; i2 < ncol; i2++)
indat[i][i2] = dp.getAttribute(i2);
}
}
/**
* Set the designed number of clusters
* @param numClusters expected number of clusters
*/
public void setClusters(int numClusters) {
if (numClusters > this.nrow) {
System.out.println("Too many clusters! Set to number of points");
numClusters = this.nrow;
}
this.numClusters = numClusters;
}
/**
* Get number of clusters
* @return number of clusters
*/
public int getClusters() {
return this.numClusters;
}
/**
* Generate random seeds for initial centroids
*/
public void generateSeed() {
// System.out.println(" No. of rows, nrow = " + nrow);
// System.out.println(" No. of columns, ncol = " + ncol);
// System.out.println(" No. of clusters = " + numClusters);
// System.out.println(" Min DataHolder="+DMin.toString());
// System.out.println(" Max DataHolder = "+DMax.toString());
clusterSeed = new double[numClusters][ncol];
Random gen = new Random();
double[] a = new double[ncol];
for (int j = 0; j < numClusters; j++) { // loop over clusters
for (int m = 0; m < ncol; m++) { // loop over dimensions
// System.out.println(" print Min="+DMin.getAttribute(m));
// System.out.println(" print Max="+DMax.getAttribute(m));
a[m] = DMin.getAttribute(m) + gen.nextDouble()
* (DMax.getAttribute(m) - DMin.getAttribute(m));
clusterSeed[j][m] = a[m];
}
}
}
/**
* Set seeds by hand
* @param seed positions of seeds
*/
public void setSeed(double[][] seed) {
// System.out.println(" No. of rows, nrow = " + nrow);
// System.out.println(" No. of columns, ncol = " + ncol);
clusterSeed = new double[numClusters][ncol];
for (int j = 0; j < numClusters; j++) { // loop over clusters
for (int m = 0; m < ncol; m++) { // loop over dimensions
clusterSeed[j][m] = seed[j][m];
}
}
}
/**
* Return seeds
* @return seeds
*/
public double[][] getSeed() {
return this.clusterSeed;
}
/**
* Set initial options for calculations
* @param maxIterations
* the maximum number of iterations.
* @param epsilon
* a small value used to verify if clustering has converged.
*/
public void setOptions(int maxIterations, double epsilon) {
this.maxIterations = maxIterations;
this.epsilon = epsilon;
}
/**
* Clear
*/
public void delete() {
this.numClusters = 0;
this.maxIterations = 0;
this.epsilon = 0;
this.nrow = 0;
this.ncol = 0;
this.indat = null;
this.clusterCenters = null;
// this.generator = null;
this.aPixel = null;
}
/**
* Returns cluster centers
*
* @return DataHolder with center positions
*/
public DataHolder getCenters() {
cMeans = new DataHolder();
for (int i = 0; i < this.numClusters; i++) {
double[] a = new double[this.ncol];
for (int j = 0; j < this.ncol; j++)
a[j] = clusterCenters[i][j];
DataPoint c = new DataPoint(a, this.ncol);
// c.showAttributes();
cMeans.add(c);
}
return cMeans;
}
/**
* Get positions of seeds
* @return seed positions
*/
public DataHolder getSeedHolder() {
DataHolder tmp = new DataHolder();
for (int i = 0; i < this.numClusters; i++) {
double[] a = new double[this.ncol];
for (int j = 0; j < this.ncol; j++)
a[j] = clusterSeed[i][j];
DataPoint c = new DataPoint(a, this.ncol);
tmp.add(c);
}
return tmp;
}
/**
* Returns the number of points in each cluster
*
* @return int[] getNumberPoints
*/
public int[] getNumberPoints() {
return this.clusterAssignmentCount;
} // end
/**
* Run classic K-Means clustering algorithm. Seeds
* will be generated automatically
*/
public void run() {
generateSeed();
runKM();
description = "kmeans algorithm fixed cluster mode with single seed event";
}
/**
* Classic K-Means clustering algorithm. Seeds are not set.
* Instead, consider the method run()
*/
public void runKM() {
iteration = 0;
clusterCenters = new double[numClusters][ncol];
clusterAssignmentCount = new int[numClusters];
for (int j = 0; j < numClusters; j++) { // loop over clusters
for (int m = 0; m < ncol; m++) { // loop over dimensions
clusterCenters[j][m] = clusterSeed[j][m];
}
}
// System.out.println("random:");
// VEC.printMatrix(numClusters,ncol,clusterCenters,5,5);
double lastSumOfDistances = 0;
iterations: // Label for main loop.
for (iteration = 0; iteration < maxIterations; iteration++) {
// 0 - Clean the cluster assignment vector.
Arrays.fill(clusterAssignmentCount, 0);
// 1 - Scan the image and calculate the assignment vector.
for (int h = 0; h < nrow; h++) {
// Gets the class for this pixel.
for (int b = 0; b < ncol; b++)
aPixel[b] = indat[h][b];
int aClass = getClassFor(aPixel);
outputData[h] = aClass;
clusterAssignmentCount[aClass]++;
}
// 2 - Scan the assignment vector and recalculate the cluster
// centers.
for (int cluster = 0; cluster < numClusters; cluster++)
Arrays.fill(clusterCenters[cluster], 0f);
// Update the position index.
for (int h = 0; h < nrow; h++) {
for (int b = 0; b < ncol; b++) {
int theCluster = outputData[h];
clusterCenters[theCluster][b] += indat[h][b];
}
// Update the position index.
}
// 2a - Recalculate the centers.
for (int cluster = 0; cluster < numClusters; cluster++)
if (clusterAssignmentCount[cluster] > 0)
for (int b = 0; b < ncol; b++)
clusterCenters[cluster][b] /= clusterAssignmentCount[cluster];
sumOfDistances = 0;
for (int h = 0; h < nrow; h++) {
// To which class does this pixel belong ?
int pixelsClass = outputData[h];
// Calculate the distance between this pixel's values and its
// assigned cluster center values.
double distance = 0;
for (int b = 0; b < this.ncol; b++) {
double e1 = indat[h][b];
double e2 = clusterCenters[pixelsClass][b];
double diff = (e1 - e2) * (e1 - e2);
distance += diff;
}
distance = FastMath.sqrt(distance);
sumOfDistances += distance;
}
// Is it converging ?
if (iteration > 0)
if (FastMath.abs(lastSumOfDistances - sumOfDistances) < epsilon)
break iterations;
lastSumOfDistances = sumOfDistances;
} // end of the iterations loop.
// VEC.printMatrix(nrow,numClusters,membership,5,5);
// VEC.printMatrix(numClusters,ncol,clusterCenters,5,5);
// VEC.printVect(outputData, 5, 5);
// VEC.printVect(clusterAssignmentCount, 5, 5);
// fill this
for (int i=0; i
Ads help maintain this website.