nearest.java

knn算法演示代码

import java.awt.event.*;
import java.awt.*;
import java.applet.*;
import java.lang.Math;

import java.util.Vector;

public class Nearest extends Applet implements ActionListener
{
    DrawCanvas canvas;  // Main canvas
    TextField MessageText;  // Text field used to display messages
    TextField knnText;      // Text field to show the number of Nearest neighbor to search
    TextField nPointText;   // Text field to show the number of points in the data set
    Button ResetButton;
    Button RandomButton;
    Button NormalRandomButton;
    Button NNButton;        // Button to switch mode between Search NN/edit point
    Button AddNNButton;     // Increase Nearest neighbor to search
    Button RemoveNNButton;  // Decrease Nearest neighbor to search
    Button SimButton;       // Activate a simulation

    public void init() 
    {
        Rectangle bound = getBounds();
        
        add(new Label("Number of points:"));
        nPointText = new TextField(4);
        nPointText.setText("0");
        nPointText.setEditable(false);
        add(nPointText);
        
        add(new Label("Number of Nearest neighbor to search:"));
        knnText = new TextField(3);
        knnText.setText("1");
        knnText.setEditable(false);
        add(knnText);
        
        AddNNButton = new Button("+");
        RemoveNNButton = new Button("-");
        AddNNButton.addActionListener(this);
        RemoveNNButton.addActionListener(this);
        add(AddNNButton);
        add(RemoveNNButton);

        MessageText = new TextField("Welcome to the nearest neighbor applet!!");
        MessageText.setEditable(false);        
        canvas = new DrawCanvas(MessageText, nPointText);
        canvas.setSize(bound.width-10,bound.height-140);
        add(canvas);

        ResetButton = new Button("Reset Points");
        add(ResetButton);
        ResetButton.addActionListener(this);
        
        RandomButton = new Button("Uniform Dist");
        add(RandomButton);
        RandomButton.addActionListener(this);
        
        NormalRandomButton = new Button("Normal Dist");
        add(NormalRandomButton);
        NormalRandomButton.addActionListener(this);
        
        add(new Label("Switch mode:"));
        NNButton = new Button("Nearest Neighbor");
        add(NNButton);
        NNButton.addActionListener(this);

        add(new Label("Simulate a 1000 random tests points:"));
        SimButton = new Button("Go Simulation!!!");
        add(SimButton);
        SimButton.addActionListener(this);

        add(MessageText);
    }
    
    public void destroy() 
    {
        remove(canvas);
    }

    public void paint(Graphics g) 
    {
       	Rectangle bound = getBounds();

    	g.setColor(Color.lightGray);
	    g.draw3DRect(0, 0, bound.width-1, bound.height-1, true);
    }
    
    public void actionPerformed(ActionEvent e)
    {
        if(e.getSource() == ResetButton)
        {
            MessageText.setText("Points reset");
            canvas.resetPoints();
        }
        else if(e.getSource() == SimButton)
        {
            canvas.DoSimulation();
        }
        else if(e.getSource() == RandomButton)
        {
            MessageText.setText("Random Points generated");
            canvas.randomPoints(100);
        }
        else if(e.getSource() == NormalRandomButton)
        {
            MessageText.setText("Normal Random points generated");
            canvas.normalRandomPoints(100);
        }
        else if(e.getSource() == NNButton)
        {
            if(canvas.getClickMode() == DrawCanvas.ADDPOINTS)
            {
                MessageText.setText("Search mode");
                canvas.setClickMode(DrawCanvas.FINDNEAREST);
                NNButton.setLabel("Edit Points");
                ResetButton.setEnabled(false);
                RandomButton.setEnabled(false);
                NormalRandomButton.setEnabled(false);
            }
            else
            {
                MessageText.setText("Edit mode");
                canvas.setClickMode(DrawCanvas.ADDPOINTS);
                NNButton.setLabel("Nearest Neighbor");
                ResetButton.setEnabled(true);
                RandomButton.setEnabled(true);
                NormalRandomButton.setEnabled(true);
            }                
        }
        else if(e.getSource() == AddNNButton)
        {
            canvas.setKN(canvas.getKN()+1);
            knnText.setText(String.valueOf(canvas.getKN()));
        }
        else if(e.getSource() == RemoveNNButton)
        {
            canvas.setKN(canvas.getKN()-1);
            knnText.setText(String.valueOf(canvas.getKN()));
        }
    }   

    public String getAppletInfo() 
    {
        return "A simple drawing program.";
    }
}

class DrawCanvas extends Canvas implements MouseListener 
{
    // Define the constant we will need
    public static final int FINDNEAREST = 0;
    public static final int ADDPOINTS = 1;
 
    // Nearest Neighbor finder
    NNFinder nnfind;
    int kn;
    // Flag to indicate the mode of operation (state)
    int mode;
    boolean DrawAllFlag;
    // Dynamic array of points
    Vector points;
    // Current point (for nearest neighbor)
    Point point;
    
    TextField MessageText;
    TextField nPointText;
    
    public DrawCanvas(TextField mtext, TextField nptstext) 
    {
        mode = ADDPOINTS;
        DrawAllFlag = false;
        points = new Vector();
        MessageText = mtext;
        nPointText = nptstext;
        kn = 1;
        setBackground(Color.white);
        addMouseListener(this);
    }
    
    public void setKN(int k)
    {
        if(k > 0 && k < points.size()) kn = k;
    }
    
    public int getKN()
    {
        return kn;
    }
    
    public void setClickMode(int newmode) 
    {
        // Erase the current point
        point = null;
        mode = newmode;
        if(mode == FINDNEAREST)
        {
            nnfind = new NNFinder(points);
        }
        // Redraw all the DrawPanel
        DrawAllFlag = true;
        repaint();
    }

    public void DoSimulation()
    {
        Dimension dim = getSize();
        Point pc, point;
        int k, i;
        double res = 0.0, brute;
        nnfind = new NNFinder(points);
        for(i=0; i < 1000; i++)
        {
            point = new Point(  (int)(Math.random()*(double)dim.width), 
                                (int)(Math.random()*(double)dim.height));
            // Find the first nearest neighbor
            pc = nnfind.FindFirstNN(point);
            if(kn > 1)
            {
                for(k = 1; k < kn; k++)
                    // Find the next nearest neighbor
                    pc = nnfind.FindNextNN();
            }
            res += (double)nnfind.getCompare();
        }
        res /= 1000.0;
        // We compute the brute force number
        for(k=0,brute=0.0; k < kn; k++) brute += (double)(nnfind.ndata - k);
        MessageText.setText("Average Number Of Compare: "+(int)res+"/"+(int)brute+" ("
            + (int)(res*100/brute)+"%)");
    }

    public int getClickMode()
    {
        return mode;
    }
    
    public void resetPoints()
    {
        points.removeAllElements();
        point = null;
        DrawAllFlag = true;
        // Update the number of point text field
        nPointText.setText("0");
        repaint();
    }
    public void randomPoints(int npts)
    {
        Dimension dim = getSize();
        int npoints = points.size();
        //points.removeAllElements();
        points.ensureCapacity(npoints+npts);
        for(int i = 0; i < npts; i++)
        {
            Point p = new Point((int)(Math.random()*(double)dim.width), 
                                (int)(Math.random()*(double)dim.height));
            points.addElement(p);
        }
        // Set the redraw of all points
        DrawAllFlag = true;
        point = null;
        // Update the number of point text field
        nPointText.setText(String.valueOf(npoints+npts));
        repaint();
    }
    
    // Return a random value according to the normal distribution
    // Code taken from : http://jeff.cs.mcgill.ca/~luc/rng.html
    public double randNorm(double mean, double sigma)
    {
        double u = Math.sqrt(-2.0*Math.log(Math.random()));
        return (u+mean)*sigma;
    }
    
    public void normalRandomPoints(int npts)
    {
        double R, Theta, x,y;
        Dimension dim = getSize();
        int npoints = points.size();
        points.ensureCapacity(npoints+npts);
        // Create a new bunch of points using the normal distribution
        int i = 0, u, v;
        while(i < npts)
        {
            R = randNorm(0.0, 1.0)*(double)dim.height/4.0;
            Theta = Math.random()*Math.PI*2.0;
            x = dim.width/2 + R*Math.cos(Theta);
            y = dim.height/2 + R*Math.sin(Theta);
            u = (int)x; v = (int)y;
            if(u > 0 && u < dim.width && v > 0 && v < dim.height)
            {
                Point p = new Point((int)u,(int)v);
                points.addElement(p);
                i++;
            }
        }
        // Set the redraw of all points
        DrawAllFlag = true;
        point = null;
        // Update the number of point text field
        nPointText.setText(String.valueOf(npoints+npts));
        repaint();
    }
    
    public void mousePressed(MouseEvent e) 
    {
        e.consume();
        switch (mode) 
        {
            case FINDNEAREST:
                point = new Point(e.getX(), e.getY());                
                // Tell the repaint routine to redraw all
                DrawAllFlag = true;
                repaint();
                break;
            case ADDPOINTS:
                point = new Point(e.getX(), e.getY());
                points.addElement(point);
                // Update the number of point text field
                nPointText.setText(String.valueOf(points.size()));
                repaint();         
            break;
        }
    }
    public void mouseReleased(MouseEvent e) {}
    public void mouseEntered(MouseEvent e) {}
    public void mouseExited(MouseEvent e) {}
    public void mouseClicked(MouseEvent e) {}
    
    public void update(Graphics g)
    {
        if(DrawAllFlag)
        {
            // Clear the panel surface to clearing color
            Rectangle bound = getBounds();
            g.clearRect(0,0,bound.width,bound.height);
            // Set the clip rect so that nothing goes outside
            // of the canvas
            //g.clipRect(0,0,bound.width,bound.height);
        }
        paint(g);
    }
    
    public void paint(Graphics g) 
    {
       	Rectangle bound = getBounds();

    	g.setColor(Color.lightGray);
	    g.draw3DRect(0, 0, bound.width, bound.height, false);

        if(DrawAllFlag)
        {
            DrawAllFlag = false;
            int np = points.size();        
            // draw each points
            g.setColor(Color.blue);
            g.setPaintMode();
            for (int i=0; i < np; i++) 
            {
                Point p = (Point)points.elementAt(i);
                g.drawOval(p.x-2, p.y-2, 4,4);
            }
        }
        if(mode == ADDPOINTS)
        {