newfcm.java

利用java写的快速模糊C均值算法

package ice.module.clustering;
import ice.gui.GUIUtil;
import ice.gui.InternalFrame;
import ice.module.Measurable;

import java.util.*;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.*;
import java.text.*;

import javax.swing.JScrollPane;
import javax.swing.JViewport;

/**
 * @Reference
 * "Fast accurate fuzzy clustering through data reduction"
 * @Date
 * Creation Date:06-4-20 15:47
 */

public class NewFCM implements Measurable{
	
	private int fsize;	//feature size
	private int ssize;	//sample size
	private int clsNum;	//cluster number
	private double m;	//coefficient in FCM
	private double reduceRate = 0.75;
	private double collNum = 3;	//collision number permitted
	private double E = 0.3;
	private int r = 2;	//quantized coefficient
	
	private double[][] samples;	//original sample data
	private double asize;	//sample size after aggregation
	private double[][] ds;	//sample data after aggregation
	private int[]	snum;	//number of repeated sample in ds[][]
	private double[][] centroids;
	private double[][] u;	//relationship matrix
	private int MAXROUND = 50;
	
	/**
	 * 以下定义用于GUI交互
	 */
	private double progressNum = 0;
	private InternalFrame frame;
	private JScrollPane imagePane;
	private BufferedImage segImage = null;
	private int height, width;
	private int mode;
	
	public NewFCM(double[][] data, int num, double m) {
		this.fsize = data[0].length;
		this.ssize = data.length;
		samples = new double[ssize][fsize];
		centroids = new double[num][fsize];
		this.clsNum = num;
		this.m = m;
		loadData(data);
		
//		show progress
		setProgress(2);
	}
	
	public NewFCM(double[][] data, int num, double m, int h, int w) {
		this(data,num,m);
		height = h;
		width = w;
	}
	
	public NewFCM(int fs, int ss, int num) {
		this.fsize = fs;
		this.ssize = ss;
		this.clsNum = num;
		samples = new double[ss][fs];
		centroids = new double[num][fs];
	}	
	
	public NewFCM(int fs, int ss, int num, double m) {
		this.fsize = fs;
		this.ssize = ss;
		this.asize = ss;
		this.clsNum = num;
		this.m = m;
		samples = new double[ss][fs];
		centroids = new double[num][fs];
	}
	
	public void loadData(double[][] data) {
		for(int i = 0; i < data.length; i++)
			copyArray(data[i],samples[i]);
	}
	
	public void loadDataFromFile(String fileName, int num, double m) {	
		try{
			FileInputStream in = new FileInputStream(fileName);
			DataInputStream input = new DataInputStream(in);
			String line = null;
			line = input.readLine();
			StringTokenizer tokens = new StringTokenizer(line," ");
			this.ssize = Integer.parseInt(tokens.nextToken());
			this.fsize = Integer.parseInt(tokens.nextToken());
			this.clsNum = num;
			this.m = m;
			samples = new double[ssize][fsize];
			centroids = new double[clsNum][fsize];
			
			int linecount = 0;
			while(line != null) {
				int count = 0;
				tokens = new StringTokenizer(line," ");
				while(tokens.hasMoreTokens()){
					samples[linecount][count] = Double.parseDouble(tokens.nextToken());
					count++;
				}
				linecount++;
				line = input.readLine();
			}
		}
		catch(Exception ex) {
			ex.printStackTrace();
		}
	}
	
	public void loadDataFromDB(String url) {
	}
	
	public void initCenter() {
		for(int i = 0; i < clsNum; i++) {
			int index = (int)(Math.random() * clsNum);
			for(int j = 0; j < fsize; j++)
				centroids[i][j] = samples[index][j];
		}
	}	
	
	public void bitAggregation() {
		//bitQuantization
		Vector[] vs = new Vector[samples.length];
		for(int i = 0; i < samples.length; i++)
			vs[i] = new Vector();
			
		for(int i = 0; i < ssize; i++) {
			for(int j = 0; j < fsize; j++) {
				samples[i][j] = ((int)samples[i][j]) & 0xFC;
				vs[i].add(new Integer((int)samples[i][j]));
			}
		}
		
		//aggregation
		HashMap map = new HashMap();
		for(int i = 0; i < ssize; i++) {
			Object key = vs[i];
			if(map.containsKey(key)) {
				int num = ((Integer)map.get(key)).intValue();
				num++;
				map.put(key,new Integer(num));
			}
			else {
				map.put(key,new Integer(1));
			}
		}
		
		ds = new double[map.size()][fsize];
		snum = new int[map.size()];
		Iterator iter = map.keySet().iterator();
		int count = 0;
		while(iter.hasNext()) {
			Vector v = (Vector)iter.next();
			for(int i = 0; i < v.size(); i++)
				ds[count][i] = ((Integer)v.get(i)).intValue();
			snum[count] = ((Integer)map.get(v)).intValue();
			count++;
		}
	}
	
	public void quantization() {
		double qr = 4.0D;
		
		for(int i = 0; i < ssize; i++) {
			for(int j = 0; j < fsize; j++) {
				samples[i][j] = qr * Math.floor(samples[i][j] * 1.0/qr);
			}
		}
	}
	
	public void aggregation() {
		if(m == 0) {
			m = ssize * reduceRate * 1.00 / 3;
		}
				
		HashMap map = new HashMap();
		HashMap wmap = new HashMap();
		double key = 0;
		for(int i = 0; i < ssize; i++) {
			double sum = 0;
			for(int j = 0; j < fsize; j++) {
				double a = Math.random() * m;
				sum += a * samples[i][j];
			}
			key = sum - Math.floor(sum * 1.00 / m) * m;
			key = Math.floor(key * 1000) * 1.00 / 1000;
			if(map.containsKey(new Double(key))) {
				int num = ((Integer)wmap.get(new Double(key))).intValue();
				num++;
				wmap.put(new Double(key),new Integer(num));
			}
			else {
				map.put(new Double(key), new Integer(i));
				wmap.put(new Double(key), new Integer(1)); 
			}
		}
		
		
		ds = new double[map.size()][fsize];
		snum = new int[map.size()];
		Iterator iter = map.keySet().iterator();
		int count = 0;
		while(iter.hasNext()) {
			Object obj = iter.next();
			int index = ((Integer)map.get(obj)).intValue();
			copyArray(samples[index],ds[count]);
			snum[count] = ((Integer)wmap.get(obj)).intValue();
			count++;
		}
	}
	
	public void origFCM() {
		u = new double[clsNum][ssize];
		double[][] newcen = new double[clsNum][fsize];
		double[][] temp = new double[clsNum][fsize];
		int step = 0;
		
		do {
			//calculate u[][]
			for(int i = 0; i < ssize; i++) {
				double[] v = new double[ssize];
				double sum = 0;
				for(int j = 0; j < clsNum; j++) {
					v[j] = distance(samples[i],centroids[j]);
					sum += Math.pow(v[j], -1.00/(m-1));
				}
				sum = 1.00 / sum;
			
				for(int k = 0; k < clsNum; k++) {
					double vx = distance(samples[i],centroids[k]);
					vx = Math.pow(vx, -1.00/(m-1));
					u[k][i] = vx * sum;				
				}
			}
		
			//claculate newcentroid[][]
			for(int i = 0; i < clsNum; i++) {
				double wsum = 0;
				double[] um = new double[ssize];
				for(int k = 0; k < ssize; k++) {
					um[k] = Math.pow(u[i][k], m);
					wsum += um[k];
				}
			
				for(int j = 0; j < fsize; j++) {
					newcen[i][j] = 0;
					for(int k = 0; k < ssize; k++) {
						newcen[i][j] += samples[k][j] * um[k];
					}
					newcen[i][j] = newcen[i][j] * 1.00 / wsum;
				}
			}
			
			//keep old centroids and update centroids
			for(int i = 0; i < clsNum; i++) {
				copyArray(centroids[i],temp[i]);
				copyArray(newcen[i],centroids[i]);
			}
			
			step++;
			
//			show progress
			double pb = Math.random();
			addProgress(1.2);
		} while(!terminate(temp,centroids,step));	//stop condition		
	}
	
	public void brFCM(double[][] data, double[] num) {
		asize = num.length;
		int size = num.length;
		u = new double[clsNum][size];
		double[][] newcen = new double[clsNum][fsize];
		double[][] temp = new double[clsNum][fsize];		
		int step = 0;
		
		do {
			//calculate u[][]
			for(int i = 0; i < size; i++) {
				double[] v = new double[size];
				double sum = 0;
				for(int j = 0; j < clsNum; j++) {
					v[j] = distance(data[i],centroids[j]);
					sum += Math.pow(v[j], -1.00/(m-1));
				}
				sum = 1.00 / sum;
			
				for(int k = 0; k < clsNum; k++) {
					double vx = distance(data[i],centroids[k]);
					vx = Math.pow(vx, -1.00/(m-1));
					u[k][i] = vx * sum;				
				}
			}
		
			//claculate newcentroid[][]
			for(int i = 0; i < clsNum; i++) {
				double wsum = 0;
				double[] wu = new double[size];
				double[] um = new double[size];
				for(int k = 0; k < size; k++) {
					um[k] = Math.pow(u[i][k], m);
					wu[k] = num[k] * um[k];
					wsum += wu[k];
				}
			
				for(int j = 0; j < fsize; j++) {
					newcen[i][j] = 0;
					for(int k = 0; k < size; k++) {
						newcen[i][j] += data[k][j] * wu[k];
					}
					newcen[i][j] = newcen[i][j] * 1.00 / wsum;
				}
			}
			
			//keep old centroids and update centroids
			for(int i = 0; i < clsNum; i++) {
				copyArray(centroids[i],temp[i]);
				copyArray(newcen[i],centroids[i]);
			}
						
			step++;
		} while(!terminate(temp,centroids,step)); //stop condition
	}
	
	public boolean terminate(double[][] oc, double[][] nc, int step) {
		double max = 0;
		for(int i = 0; i < oc.length; i++) {
			for(int j = 0; j < oc[i].length; j++) {
				if(Math.abs(oc[i][j] - nc[i][j]) > max)
					max = Math.abs(oc[i][j] - nc[i][j]);
			}
		}
		
		if(max < E || step > MAXROUND)
			return true;
		return false;
	}
	
	public int[] CMap() {
		int[] map = new int[ssize];
		for(int i = 0; i < ssize; i++) {
			double max = u[0][i];
			int index = 0;
			for(int j = 1; j < clsNum; j++) {
				if(max < u[j][i]) {
					max = u[j][i];
					index = j;
				}
			}
			map[i] = index;
		}
		
		return map;
	}
	
	public double[][] clusterData() {
		int[] map = CMap();
		for (int i = 0; i < ssize; i++) {
			for (int kk = 0; kk < fsize; kk++)
				samples[i][kk] = centroids[map[i]][kk];
		}
		
//		show progress
		setProgress(95);
		
		return samples;
	}
	
	/*
	 *Based on paper "A validity measure for fuzzy clustering"
	 */
	public double evaluation() {
		double S = 0;
		double dmin = distance(centroids[0],ds[0]);
		
		for(int i = 0; i < clsNum; i++) {
			for(int j = 0; j < asize; j++) {
				double d = distance(centroids[i],ds[j]);
				S += d * u[i][j];
				if(dmin > d)
					dmin = d;
			}
		}
		
		S = S * 1.00 / (asize * dmin);
		return S;
	}
	
	public double[][] getCentroids() {
		return this.centroids;
	}
	
	public void setReduceRate(double rate) {
		this.reduceRate = rate;
	}
	
	public void setCollNum(double num) {
		this.collNum = num;
	}
	
	public void setE(double ee) {
		this.E = ee;
	}
	
	public void printSamples() {
		System.out.println("FCM Samples: ");
		for(int i = 0; i < samples.length; i++) {
			for(int j = 0; j < samples[i].length; j++)
				System.out.print(samples[i][j] + " ");
			System.out.println();
		}
	}
	
	public void printCenters() {
		System.out.println("FCM Centroids: ");
		NumberFormat nf = NumberFormat.getInstance();
		nf.setMaximumFractionDigits(3);
		for(int i = 0; i < centroids.length; i++) {
			for(int j = 0; j < centroids[i].length; j++)
				System.out.print(nf.format(centroids[i][j]));
				
			System.out.println();
		}
	}
	
	public double distance(double[] a, double[] b) {
		double sum = 0;
		for(int i = 0; i < a.length; i++)
			sum += (a[i] - b[i]) * (a[i] - b[i]);
			
		return sum;
	}
	
	public void copyArray(double[] orig, double[] dest) {
		for(int i = 0; i < orig.length; i++)
			dest[i] = orig[i];
	}
	

	/**
	 * 以下方法用于GUI交互
	 */
	public void setUI(InternalFrame inf, JScrollPane sp) {
		setInternalFrame(inf);
		setPane(sp);
	}
	
	public void setInternalFrame(InternalFrame inf) {
		frame = inf;
	}
	
	public void setPane(JScrollPane sp) {
		imagePane = sp;
	}
	
	public void setHeight(int h) {
		height = h;
	}
	
	public void setWidth(int w) {
		width = w;
	}
	
	public void buildImage() {
		double[][] img = clusterData();
		segImage = new BufferedImage(width,height,BufferedImage.TYPE_INT_RGB);
		Graphics g = segImage.getGraphics();
		for(int h = 0; h < height; h++) {
			for(int w = 0; w < width; w++) {
				int loc = h*width+w;
				Color color = new Color((int)img[loc][0],(int)img[loc][1],(int)img[loc][2]);
				g.setColor(color);
				g.fillRect(w,h,1,1);
			}
		}
		
		//show progress
		setProgress(97);
	}
	
	public void updatePane() {
		if (frame != null && imagePane != null && segImage != null) {
			JViewport vp = GUIUtil.createViewport(segImage);
			imagePane.setViewport(vp);
			imagePane.validate();
			frame.log("图像初步分割完成");
		}
	}
	
	public void addProgress(int val) {
		if (val > 0)
			progressNum += val;
	}
	
	public void addProgress(double val) {
		if (val > 0)
			progressNum += val;
	}
	
	public void setProgress(int val) {
		if (val > 0)
			progressNum = val;
	}
	
	public void setProgress(double val) {
		if (val > 0)
			progressNum = val;
	}

	public int getProgress() {
		return (int)progressNum;
	}

	public String getActivity() {
		return (int)progressNum + "% Completed...";
	}

	public void stopMask() {
		System.exit(0);
	}

	public void run() {
		origFCM();
		if (mode == 0) {
			buildImage();
			updatePane();
		}
		//show progress
		setProgress(100);
	}

	public void setMode(int m) {
		mode = m;
	}
}