algorithmkmeans.java

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

		
		// determine the distance of the point from the mean
		//
		dist = MathUtil.distance(point.x, point.y, mean.x, mean.y); 
		
		// store the smallest distance
		//
		if(dist < smallestSoFar) 
		{
		    associated = j;
		    smallestSoFar = dist;
		}
	    }
	    
	    // store the point based on the classification
	    //
	    String name = new String("cluster");
	    name = name + associated;
	    region.addPoint(point, name);
	}
    }

    /**
    * Computes the means of the data sets after each iteraion
    * 
    * @param  region - classified data sets
    * @see    DecisionRegion
    */
    public void computeMeans(DecisionRegion region) 
    {
       	// determine the number of classified data sets
	//
	int numsets = region.getNumRegions();

	// remove all previous guesses - mean points
	//
	guesses.removeAllElements();
	
	// iterate over the data sets to determine the new means
	//
	for (int i = 0; i < numsets; i++) 
	{

	    // retrieve the classified region
	    //
	    Vector dataset = (Vector)region.getRegion(i);
	    
	    // determine the mean of the classified region
	    //
	    MyPoint mean = MathUtil.computeClusterMean(dataset);

	    // add the computed mean as one of the new guesses
	    //
	    guesses.addElement(new MyPoint(mean.x, mean.y));
	}

	// add the newly determined guesses to the region
	//
	region.setGuesses(guesses);
    }

    /**
    * Determines the closest data sets to the cluster
    *
    * @param   mean mean point of the cluster
    * 
    * @return  closest data set to the cluster
    * @see     MyPoint
    */
    public int getClosestSet(MyPoint mean) 
    {
	// declare local variables
	//
	double dist1 = 0.0;
	double dist2 = 0.0;
	double dist3 = 0.0;
	double dist4 = 0.0;

	MyPoint mean1;
	MyPoint mean2;
	MyPoint mean3;
	MyPoint mean4;
	int i=0;

	// determine the distance for the cluster to each data set
	//
	if (set1_d.size() > 0)
	{
	    mean1 = (MyPoint)point_means_d.elementAt(i);
	    i++;
	    dist1 = MathUtil.distance(mean.x, mean.y, 
				      mean1.x, mean1.y);
	}
	else
	    dist1 = Float.MAX_VALUE;

	if (set2_d.size() > 0)
	{
	    mean2 = (MyPoint)point_means_d.elementAt(i);
	    i++;
	    dist2 = MathUtil.distance(mean.x, mean.y, 
				      mean2.x, mean2.y);
	}
	else
	    dist2 = Float.MAX_VALUE;

	if (set3_d.size() > 0)
	{
	    mean3 = (MyPoint)point_means_d.elementAt(i);
	    i++;
	    dist3 = MathUtil.distance(mean.x, mean.y, 
				      mean3.x, mean3.y);
	}
	else
	    dist3 = Float.MAX_VALUE;

	if (set4_d.size() > 0)
	{
	    mean4 = (MyPoint)point_means_d.elementAt(i);
	    i++;
	    dist4 = MathUtil.distance(mean.x, mean.y, 
				      mean4.x, mean4.y);
	}
	else
	    dist4 = Float.MAX_VALUE;

	// the first data set is the closest one
	//
	if (dist1 < dist2 && dist1 < dist3 && dist1 < dist4) 
	{
	    return 1;
	}

	// the second data set is the closest one
	//
	if (dist2 < dist1 && dist2 < dist3 && dist2 < dist4) 
	{
	    return 2;
	}

	// the third data set is the closest one
	//
	if (dist3 < dist1 && dist3 < dist2 && dist3 < dist4) 
	{
	    return 3;
	}

	// the forth data set is the closest one
	//
	return 4;
    }

    /**
     * determines the number of points in error, i.e, not classified
     * by finding the distance of the datapoints from the closest of
     * the vector set
     *
     * @param   closest the data specifying which of the dataset is the
     *                  closest.
     * @param   cluster the data points which form a closest cluster
     * @param   id      unused in current implementation
     * @return  error   number of data points which lie out of the 
     *                  classification
     */
    public int displayClusterError(int closest, Vector cluster, int id) 
    {

	// declare local vaiables
	//
	int total = 0;
	int error = 0;
	boolean present = false;
	double classification = 0.0;

	// the first set is the closest one - determine the error
	//
	if (closest == 1) 
	{
	    for (int i = 0; i < cluster.size(); total++, i++) 
	    {

		// reset the present flag
		//
		present = false;

		// retrieve the next cluster point
		//
		MyPoint cst = (MyPoint)cluster.elementAt(i);

		for (int j = 0; j < set1_d.size(); j++) 
		{

		    // retrieve the next point from the data set
		    //
		    MyPoint pnt = (MyPoint)set1_d.elementAt(j);

		    // check if the point is present
		    //
		    if (cst.x == pnt.x && cst.y == pnt.y) 
		    {
			present = true;
		    }
		}

		// error if the point is not found in the set
		//
		if (!present) 
		{
		    error++;
		}
	    }
	}

	// the second set is the closest one - determine the error
	//
	if (closest == 2) 
	{
	    for (int i = 0; i < cluster.size(); total++, i++) 
	    {

		// reset the present flag
		//
		present = false;

		// retrieve the next cluster point
		//
		MyPoint cst = (MyPoint)cluster.elementAt(i);

		for (int j = 0; j < set2_d.size(); j++) 
		{

		    // retrieve the next point from the data set
		    //
		    MyPoint pnt = (MyPoint)set2_d.elementAt(j);

		    // check if the point is present
		    //
		    if (cst.x == pnt.x && cst.y == pnt.y) 
		    {
			present = true;
		    }
		}

		// error if the point is not found in the set
		//
		if (!present) 
		{
		    error++;
		}
	    }
	}

	// the third set is the closest one - determine the error
	//
	if (closest == 3) 
	{
	    for (int i = 0; i < cluster.size(); total++, i++) 
	    {

		// reset the present flag
		//
		present = false;

		// retrieve the next cluster point
		//
		MyPoint cst = (MyPoint)cluster.elementAt(i);

		for (int j = 0; j < set3_d.size(); j++) 
		{

		    // retrieve the next point from the data set
		    //
		    MyPoint pnt = (MyPoint)set3_d.elementAt(j);

		    // check if the point is present
		    //
		    if (cst.x == pnt.x && cst.y == pnt.y) 
		    {
			present = true;
		    }
		}

		// error if the point is not found in the set
		//
		if (!present) 
		{
		    error++;
		}
	    }
	}

	// the forth set is the closest one - determine the error
	//
	if (closest == 4) 
	{
	    for (int i = 0; i < cluster.size(); total++, i++) 
	    {

		// reset the present flag
		//
		present = false;

		// retrieve the next cluster point
		//
		MyPoint cst = (MyPoint)cluster.elementAt(i);

		for (int j = 0; j < set4_d.size(); j++) 
		{

		    // retrieve the next point from the data set
		    //
		    MyPoint pnt = (MyPoint)set4_d.elementAt(j);

		    // check if the point is present
		    //
		    if (cst.x == pnt.x && cst.y == pnt.y) 
		    {
			present = true;
		    }
		}

		// error if the point is not found in the set
		//
		if (!present) 
		{
		    error++;
		}
	    }
	}

	// return the misclassified samples
	//
	return (int)error;
    }

    /**
    * Computes the k-mean decision region - nearest neighbor algorithm
    *
    * @param  vec vector of initial guesses
    *
    * @return vector of desision region points
    */
    public Vector<MyPoint> getDecisionRegion(Vector<MyPoint> vec) 
    {

	// declare local variables
	//

	double currentX = scale.xmin;
	double currentY = scale.ymin;
	
	MyPoint point;

	int outputHeight = output_panel_d.disp_area_d.getYPrecision();
	int outputWidth = output_panel_d.disp_area_d.getXPrecision();

	double dist = 0.0;
	double cdist = 0.0;
	double smallestSoFar = Double.MAX_VALUE;

	double incrementY = (scale.ymax-scale.ymin) / outputHeight;
	double incrementX = (scale.xmax-scale.xmin) / outputWidth;

	int associated = 0;
	int outputCanvas[][] = new int[outputWidth][outputHeight];

	Vector<MyPoint> decision = new Vector<MyPoint>(100, 10);

	pro_box_d.setProgressMin(0);
	pro_box_d.setProgressMax(outputWidth);
	pro_box_d.setProgressCurr(0);

	for(int i = 0; i < outputWidth; i++) 
	{
	    
	    currentX += incrementX;
	    currentY = scale.ymin;	    	    

	    pro_box_d.setProgressCurr(i);  

	    for(int j = 0; j < outputHeight; j++) 
	    {
		
		currentY += incrementY;	
		
		MyPoint pixel = new MyPoint(currentX, currentY);	                       smallestSoFar = Double.MAX_VALUE;

		// find the closest point from the guesses
		//
		for (int k = 0; k < vec.size(); k++) 
		{

		    double smallest = Double.MAX_VALUE;

		    point = (MyPoint)vec.elementAt(k);
		    dist = MathUtil.distance(pixel.x, pixel.y, 
					     point.x, point.y); 

		    if(dist < smallestSoFar) 
		    {
			
			int l = 0;

			// find the distance between the cluster mean 
			// and the global mean of the first class
			//			
			if(set1_d.size() > 0) 
			{
			    MyPoint mean1 = (MyPoint)
				            point_means_d.elementAt(l);
			    l++;
			    cdist = MathUtil.distance(point.x, point.y, 
						      mean1.x, mean1.y); 
			    if(cdist < smallest) 
			    {			    
				associated = 0;
				smallest = cdist;
			    }
			}

			// find the distance between the cluster mean 
			// and the global mean of the second class
			//			
			if(set2_d.size() > 0) 
			{
			    MyPoint mean2 = (MyPoint)
				            point_means_d.elementAt(l);
			    l++;
			    cdist = MathUtil.distance(point.x, point.y, 
						      mean2.x, mean2.y); 
			    if(cdist < smallest) 
			    {
				associated = 1;
				smallest = cdist;
			    }
			}

			// find the distance between the cluster mean 
			// and the global mean of the third class
			//			
			if(set3_d.size() > 0) 
			{
			    MyPoint mean3 = (MyPoint)
				            point_means_d.elementAt(l);
			    l++;
			    cdist = MathUtil.distance(point.x, point.y,
						      mean3.x, mean3.y); 
			    if(cdist < smallest) 
			    {
				associated = 2;
				smallest = cdist;
			    }
			}

			// find the distance between the cluster mean 
			// and the global mean of the forth class
			//			
			if(set4_d.size() > 0) 
			{
			    MyPoint mean4 = (MyPoint)
				            point_means_d.elementAt(l);
			    l++;
			    cdist = MathUtil.distance(point.x, point.y,
						      mean4.x, mean4.y); 
			    if(cdist < smallest) 
			    {
				associated = 3;
				smallest = cdist;
			    }
			}
			// set the smallest distance so far
			//
			smallestSoFar = dist;
		    }
		}		

		// put and entry in the output canvas array to
		// indicate which class the current pixel is closest to
		//
		outputCanvas[i][j] = associated;

		// add a point to the vector of decision
		// region points if the class that the current
		// point is associated with is different for
		// the class what the previous point was
		// associated with i.e., a transition point
		//
		if(j > 0 && i > 0) {
		    if(associated != outputCanvas[i][j - 1] || 
		       associated != outputCanvas[i - 1][j]) 
		    {
			decision.addElement(pixel);
		    }
		}
	    }
	}

	// return the vector of decision region points
	//
	return decision;
    }

    /**
     * displays the decision region on the output panel
     */
    public void outputDecisionRegion()
    {
	output_panel_d.clear();
	
	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);
	
  	output_panel_d.addOutput(decision_regions_d.getGuesses(), 
				 Classify.PTYPE_OUTPUT_LARGE, 
				 Color.black);

	Vector<MyPoint> decision = getDecisionRegion(guesses);

  	output_panel_d.addOutput(decision, 
				 Classify.PTYPE_INPUT, 
				 Color.black);

	output_panel_d.repaint();
    }    
}