algorithmlda.java

包含了模式识别中常用的一些分类器设计算法

//--------------------------------------------------------------------------
// AlgorithmLDA.java 6.0 03/15/2005
// Created       : Phil Trasatti     Edited : Daniel May
//                                   Edited : Sanjay Patil
//                              Last Edited : Ryan Irwin
//
// Description   : Describes the LDA algorithm
// Remarks       : Code unchanged since created. Created 07/15/2003
//--------------------------------------------------------------------------


//----------------------
// import java packages
//----------------------
import java.util.*;
import java.awt.*;

/**
 * Implements the Linear Discriminant Analysis Algorithm
 */
public class AlgorithmLDA extends Algorithm
{
    // Public Data Members
    //
    Vector<MyPoint> decision_regions_d;
    Vector<MyPoint> support_vectors_d;
    int output_canvas_d[][];
    
    // declare local Matrix objects
    // covariance matrix for CLDA1
    //
    Matrix W;
    Matrix LDA;
    Matrix CLDA; 
    Matrix B;
    Matrix S;
    Matrix invW;
    
   /**
    * Overrides the initialize() method in the base class. Initializes
    * member data and prepares for execution of first step. This method
    * "resets" the algorithm.
    *
    * @return   Returns true.
    */
    public boolean initialize()
    {
	// algo_id = "AlgorithmLDA";
	
	// Debug 
	//
	// System.out.println(algo_id + " initialize()");

	step_count = 3;
	point_means_d      = new Vector<MyPoint>();
	decision_regions_d = new Vector<MyPoint>();
	support_vectors_d  = new Vector<MyPoint>();
	description_d      = new Vector<String>();
	
	// Initialize local Matrix objects
	//
	W    = new Matrix();
	LDA  = new Matrix();
	CLDA = new Matrix();
	B    = new Matrix();
	S    = new Matrix();
	invW = new Matrix();
	
	// Add the process description for the LDA algorithm
	//
	if (description_d.size() == 0)
        {
	    String str = new String("   0. Initialize the original data.");
	    description_d.addElement(str);
	    
	    str = new String("   1. Displaying the original data.");
	    description_d.addElement(str);
	    
	    str = new String("   2. Computing the means and covariance.");
	    description_d.addElement(str);
	    
	    str = new String("   3. Computing the decision regions based on the class independent LDA algorithm.");
	    description_d.addElement(str);
	}
	
	// append message to process box
	//
	pro_box_d.appendMessage("Class Independent LDA Analysis:" + "\n");
	
	// set the data points for this algorithm
	//
	//	set1_d = (Vector<MyPoint>)data_points_d.dset1.clone();
	//	set2_d = (Vector)data_points_d.dset2.clone();
	//	set3_d = data_points_d.dset3.clone();
	//	set4_d = data_points_d.dset4.clone();
	//
	set1_d = data_points_d.dset1;
	set2_d = data_points_d.dset2;
	set3_d = data_points_d.dset3;
	set4_d = data_points_d.dset4;



	// set the step index
	//
	step_index_d = 0;
	
	// append message to process box
	//
	pro_box_d.appendMessage((String)description_d.get(step_index_d));
	
	// exit initialize
	//
	return true;
    }

    /**
    * Displays data sets from input box in output box.
    *
    * @return Returns true
    */
    boolean step1()
    {
	// Debug
	//
	// System.out.println(algo_id + " step1()");
	
	pro_box_d.setProgressMin(0);
	pro_box_d.setProgressMax(20);
	pro_box_d.setProgressCurr(0);
	
	// append message to process box
	//
	output_panel_d.addOutput(set1_d, Classify.PTYPE_INPUT, 
				 data_points_d.color_dset1);
	output_panel_d.addOutput(set2_d, Classify.PTYPE_INPUT,
				 data_points_d.color_dset2);
	output_panel_d.addOutput(set3_d, Classify.PTYPE_INPUT,
				 data_points_d.color_dset3);
	output_panel_d.addOutput(set4_d, Classify.PTYPE_INPUT, 
				 data_points_d.color_dset4);
	
	// step 1 completed
	//
	pro_box_d.setProgressCurr(20);
	output_panel_d.repaint();
	
	return true;
    }
    
    /**
     * Calculates the within class and between class scatter matrix,
     * transforms the data sets ans displays the mean graphically
     * and numerically
     *
     * @return Returns true
     */
    boolean step2()
    {
	// Debug
	//
	// System.out.println(algo_id + " step2()");
	
	pro_box_d.setProgressMin(0);
	pro_box_d.setProgressMax(20);
	pro_box_d.setProgressCurr(0);
	
	computeMeans();
	
	// determine the within class scatter matrix
	//
	withinClass(W);
	
	// determine the between class scatter matrix
	//
	betweenClass(B);
	
	// determine the ratio of the between class scatter matrix
	// to the within class scatter matrix
	//
	W.invertMatrix(invW);
	invW.multMatrix(B, S);
	
	// transform the samples from all data sets
	//
	transformLDA(data_points_d, S);
	
	displayMatrices();
	
	// display means
	//
	output_panel_d.addOutput(point_means_d, 
				 Classify.PTYPE_OUTPUT_LARGE, Color.black);
	
	// display support vectors
	//
	output_panel_d.addOutput(support_vectors_d, 
				 Classify.PTYPE_INPUT, Color.black );
	
	// display support vectors
	//
	pro_box_d.setProgressCurr(20);
	output_panel_d.repaint();
	
	return true;
    }
    
    /**
     * Computes the decision regions and totals the data points in error,
     * as well displays the decision region
     *
     * @return Returns true
     */
    boolean step3()
    {
	// Debug
	//
	// System.out.println(algo_id + " step3()");
	
	
	pro_box_d.setProgressMin(0);
	pro_box_d.setProgressMax(20);
	pro_box_d.setProgressCurr(0);
	
	// compute the decision regions
	//
	computeDecisionRegions();
	
	// compute errors
	//
	computeErrors();
	
	// display support vectors
	//
	output_panel_d.addOutput( decision_regions_d, 
				  Classify.PTYPE_INPUT, 
				  new Color(255, 200, 0));
	
	output_panel_d.repaint();
	
	return true;
    }
    
    /**
     * Determines the within class scatter matrix
     *
     * @param   M Matrix for within class scatter matrix
     * @see     Matrix
     */
    public void withinClass(Matrix M)
    {
	
	// declare local variables
	//
	int size = 0;
	double x[] = null;
	double y[] = null;
	
	DisplayScale scale = output_panel_d.disp_area_d.getDisplayScale();
	
	// declare the covariance object
	//
	Covariance cov = new Covariance();
	
	// declare local matrices
	//
	Matrix M1 = new Matrix();
	Matrix M2 = new Matrix();
	Matrix M3 = new Matrix();
	Matrix M4 = new Matrix();
	
	// compute the propabilities of each data set
	//
	double maxsamples = set1_d.size() + set2_d.size() 
	                  + set3_d.size() + set4_d.size();
	
	double p1 = set1_d.size() / maxsamples;
	double p2 = set2_d.size() / maxsamples;
	double p3 = set3_d.size() / maxsamples;
	double p4 = set4_d.size() / maxsamples;
	
	// get the first data set size
	//
	size = set1_d.size();
	
	// initialize arrays to store the samples
	//
	x = new double[size];
	y = new double[size];
	
	// set up the initial random vectors i.e., the vectors of
	// X and Y coordinate points form the display
	//
	for (int i = 0; i < size; i++)
	{
	    MyPoint p = (MyPoint)set1_d.elementAt(i);
	    x[i] = p.x;
	    y[i] = p.y;
	}
	
	// compute the covariance matrix of the first data set
	//
	M1.row = M1.col = 2;
	M1.Elem = new double[2][2];
	M1.resetMatrix();
	
	if (size > 0)
	{
	    M1.Elem = cov.computeCovariance(x, y);
	}
	
	// get the second data set size
	//
	size = set2_d.size();
	
	// initialize arrays to store the samples
	//
	x = new double[size];
	y = new double[size];
	
	// set up the initial random vectors i.e., the vectors of
	// X and Y coordinate points form the display
	//
	for (int i = 0; i < size; i++)
	{
	    MyPoint p = (MyPoint)set2_d.elementAt(i);
	    x[i] = p.x;
	    y[i] = p.y;
	}
	
	// compute the covariance matrix of the second data set
	//
	M2.row = M2.col = 2;
	M2.Elem = new double[2][2];
	M2.resetMatrix();
	
	if (size > 0)
	{
	    M2.Elem = cov.computeCovariance(x, y);
	}
	
	// get the third data set size
	//
	size = set3_d.size();
	
	// initialize arrays to store the samples
	//
	x = new double[size];
	y = new double[size];
	
	// set up the initial random vectors i.e., the vectors of
	// X and Y coordinate points form the display
	//
	for (int i = 0; i < size; i++)
	{
	    MyPoint p = (MyPoint)set3_d.elementAt(i);
	    x[i] = p.x;
	    y[i] = p.y;
	}
	
	// compute the covariance matrix of the third data set
	//
	M3.row = M3.col = 2;
	M3.Elem = new double[2][2];
	M3.resetMatrix();
	
	if (size > 0)
	{
	    M3.Elem = cov.computeCovariance(x, y);
	}
	
	// get the fourth data set size
	//
	size = set4_d.size();
	
	// initialize arrays to store the samples
	//
	x = new double[size];
	y = new double[size];
	
	// set up the initial random vectors i.e., the vectors of
	// X and Y coordinate points form the display
	//
	for (int i = 0; i < size; i++)
	{
	    MyPoint p = (MyPoint)set4_d.elementAt(i);
	    x[i] = p.x;
	    y[i] = p.y;
	}
	
	// compute the covariance matrix of the fourth data set
	//
	M4.row = M4.col = 2;
	M4.Elem = new double[2][2];
	M4.resetMatrix();
	
	if (size > 0)
	{
	    M4.Elem = cov.computeCovariance(x, y);
	}
	
	// compute the within class scatter matrix
	//
	M.row = M.col = 2;
	M.Elem = new double[2][2];
	M.resetMatrix();
	M.addMatrix(M1);
	M.addMatrix(M2);
	M.addMatrix(M3);
	M.addMatrix(M4);
	CLDA = M;
    }
    
    /**    
     * Determines the between class scatter matrix for
     * the class independent linear discrimination algorithm
     *
     * @param   M Matrix for storing between class scatter matrix
     * @see     Matrix
     */
    public void betweenClass(Matrix M)
    {
	
	// declare local variables
	//
	int capacity = 0;
	int size = 0;
	
	double xmean = 0.0;
	double ymean = 0.0;
	
	double xmean1 = 0.0;
	double ymean1 = 0.0;
	double xmean2 = 0.0;
	double ymean2 = 0.0;
	double xmean3 = 0.0;
	double ymean3 = 0.0;
	double xmean4 = 0.0;
	double ymean4 = 0.0;
	
	// declare local matrices
	//
	Matrix M1 = new Matrix();
	Matrix T1 = new Matrix();
	Matrix M2 = new Matrix();
	Matrix T2 = new Matrix();
	Matrix M3 = new Matrix();
	Matrix T3 = new Matrix();
	Matrix M4 = new Matrix();
	Matrix T4 = new Matrix();
	
	// declare the covariance object
	//
	Covariance cov = new Covariance();
		
	// declare the initial random variables
	//
	double transpose[][] = new double[2][1];
	double mean[][] = new double[1][2];
	
	// compute the propabilities of each data set
	//
	double maxsamples = set1_d.size() + set2_d.size() 
	                  + set3_d.size() + set4_d.size();
	
	double pr1 = set1_d.size() / maxsamples;
	double pr2 = set2_d.size() / maxsamples;
	double pr3 = set3_d.size() / maxsamples;
	double pr4 = set4_d.size() / maxsamples;
	
	DisplayScale scale = output_panel_d.disp_area_d.getDisplayScale();

	// initialize the between class matrix
	//
	M.row = M.col = 2;
	M.Elem = new double[2][2];
	M.resetMatrix();
	
	int j = 0;

	// obtain the means of each individual class
	//
	if (set1_d.size() > 0)
	{	    
	    MyPoint p = (MyPoint)point_means_d.elementAt(j);
	    j++;
	    xmean1 = p.x;
	    ymean1 = p.y;    
	}
	
	if (set2_d.size() > 0)
	{
	    MyPoint p = (MyPoint)point_means_d.elementAt(j);
	    j++;
	    xmean2 = p.x;
	    ymean2 = p.y;    
	}
	
	if (set3_d.size() > 0)
	{
	    MyPoint p = (MyPoint)point_means_d.elementAt(j);
	    j++;
	    xmean3 = p.x;
	    ymean3 = p.y;    
	}

	if (set4_d.size() > 0)
	{
	    MyPoint p = (MyPoint)point_means_d.elementAt(j);
	    j++;
	    xmean4 = p.x;
	    ymean4 = p.y;    
	}
	
	// compute the global mean of all data sets
	//
	int samples = 0;
	
	for (int i = 0; i < set1_d.size(); samples++, i++)
	{
	    MyPoint p2 = (MyPoint)set1_d.elementAt(i);
	    xmean += p2.x;
	    ymean += p2.y;
	}
	
	for (int i = 0; i < set2_d.size(); samples++, i++)
	{
	    MyPoint p2 = (MyPoint)set2_d.elementAt(i);
	    xmean += p2.x;
	    ymean += p2.y;
	}

	for (int i = 0; i < set3_d.size(); samples++, i++)
	{
	    MyPoint p2 = (MyPoint)set3_d.elementAt(i);
	    xmean += p2.x;
	    ymean += p2.y;
	}
	
	for (int i = 0; i < set4_d.size(); samples++, i++)
	{
	    MyPoint p2 = (MyPoint)set4_d.elementAt(i);
	    xmean += p2.x;
	    ymean += p2.y;
	}

	xmean /= samples;
	ymean /= samples;
	
	// compute the between class scatter contribution of the first set
	//
	if (set1_d.size() > 0)
	{
	    Matrix S = new Matrix();
	    
	    mean[0][0] = xmean1 - xmean;
	    mean[0][1] = ymean1 - ymean;
	    M1.initMatrix(mean, 1, 2);
	    
	    transpose[0][0] = xmean1 - xmean;
	    transpose[1][0] = ymean1 - ymean;
	    T1.initMatrix(transpose, 2, 1);
	    
	    T1.multMatrix(M1, S);
	    M.addMatrix(S);
	}
	
	// compute the between class scatter contribution of the second set
	//
	if (set2_d.size() > 0)
	{
	    
	    Matrix S = new Matrix();
	    
	    mean[0][0] = xmean2 - xmean;
	    mean[0][1] = ymean2 - ymean;
	    M2.initMatrix(mean, 1, 2);
	    
	    transpose[0][0] = xmean2 - xmean;
	    transpose[1][0] = ymean2 - ymean;
	    T2.initMatrix(transpose, 2, 1);
	    
	    T2.multMatrix(M2, S);
	    M.addMatrix(S);
	}
	
	// compute the between class scatter contribution of the third set
	//