// kNN demo // Jerry Zhu, Carnegie Mellon University, 2000/12 // My first Java program. import java.applet.Applet; import java.awt.*; import java.awt.event.ActionListener; import java.awt.event.ActionEvent; public class KNN extends Applet implements ActionListener { private TextField inputN, inputComplexity, inputK, inputKNN; private Button Step1Button, Step2Button, Step3Button; private Label errLabel; private KNNCanvas theKNNCanvas; private Canvas theTruthCanvas; private int n, complexity, k, knn; private boolean[][] truth; private class Sample { int x; int y; boolean label; } Sample[] samples; private class Distance { double d; boolean label; } Distance[] distances; public void init() { GridBagLayout bag = new GridBagLayout(); GridBagConstraints c = new GridBagConstraints(); this.setLayout(bag); // create input fields for // N: the size of the area is N*N Label label = new Label("Step 1: Field size(10--80):"); bag.setConstraints(label, c); this.add(label); inputN = new TextField("80", 2); bag.setConstraints(inputN, c); this.add(inputN); // Complexity: of the true distribution label = new Label(" complexity(1--100):"); bag.setConstraints(label, c); this.add(label); inputComplexity = new TextField("5", 2); bag.setConstraints(inputComplexity, c); this.add(inputComplexity); Step1Button = new Button("Create Truth"); Step1Button.addActionListener(this); c.anchor = GridBagConstraints.WEST; c.gridwidth = GridBagConstraints.REMAINDER; // last component in a row bag.setConstraints(Step1Button, c); c.anchor = GridBagConstraints.CENTER; this.add(Step1Button); // k: number of positive or negative examples label = new Label("Step 2: samples(1--2000):"); c.gridwidth = 1; // reset to default bag.setConstraints(label, c); this.add(label); inputK = new TextField("10", 2); bag.setConstraints(inputK, c); this.add(inputK); Step2Button = new Button("Generate Samples"); Step2Button.addActionListener(this); c.anchor = GridBagConstraints.WEST; c.gridwidth = GridBagConstraints.REMAINDER; // last component in a row bag.setConstraints(Step2Button, c); c.anchor = GridBagConstraints.CENTER; this.add(Step2Button); // kNN: the number of neighbors considered in kNN. label = new Label("Step 3: kNN(1--100):"); c.anchor = GridBagConstraints.WEST; c.gridwidth = 1; // reset to default bag.setConstraints(label, c); c.anchor = GridBagConstraints.CENTER; this.add(label); inputKNN = new TextField("1", 2); bag.setConstraints(inputKNN, c); this.add(inputKNN); Step3Button = new Button("Classify"); Step3Button.addActionListener(this); this.add(Step3Button); errLabel = new Label(" "); c.anchor = GridBagConstraints.WEST; c.fill = GridBagConstraints.BOTH; c.gridwidth = GridBagConstraints.REMAINDER; // last component in a row bag.setConstraints(errLabel, c); this.add(errLabel); // the truth canvas theTruthCanvas = new TruthCanvas(); theTruthCanvas.setSize(404, 404); c.fill = GridBagConstraints.BOTH; c.weightx = 0; c.weighty = 1; c.gridwidth = 1; c.gridwidth = GridBagConstraints.RELATIVE; // last component in a row c.gridheight = GridBagConstraints.REMAINDER; // last component in a column bag.setConstraints(theTruthCanvas, c); this.add(theTruthCanvas); // the KNN canvas theKNNCanvas = new KNNCanvas(); theKNNCanvas.setSize(404, 404); c.fill = GridBagConstraints.BOTH; c.weightx = 1; c.weighty = 1; c.gridwidth = GridBagConstraints.REMAINDER; // last component in a row c.gridheight = GridBagConstraints.REMAINDER; // last component in a column bag.setConstraints(theKNNCanvas, c); this.add(theKNNCanvas); } public void actionPerformed(ActionEvent e) { if (e.getSource() == Step1Button) { n = new Integer(inputN.getText()).intValue(); complexity = new Integer(inputComplexity.getText()).intValue(); k=0; // remove previous samples truth = new boolean[n][n]; int x, y; for (x=0; x0) truth[x][y] = !truth[x][y]; } theTruthCanvas.repaint(); } else if (e.getSource() == Step2Button) { k = new Integer(inputK.getText()).intValue(); samples = new Sample[k]; int i; for (i=0; i biggestd) {biggestd = distances[a].d; biggestindex = a; } if (dist < biggestd) {distances[biggestindex].d = dist; distances[biggestindex].label = samples[i].label; } } } // count which label in knn occurs most, this is the classification of (x,y) int nT=0, nF=0; boolean classification; for (int i=0; inF) classification = true; else classification = Math.random() < 0.5; // if tie, randomly break it if (classification == false) g.setColor(Color.white); else g.setColor(Color.green); g.fillRect(m*x+1, m*y+1, m, m); // count classification errors if (classification != truth[x][y]) error ++; } // update error label if (n>0) errLabel.setText(" Error rate = " + (float)error/n/n*100 + "%"); // draw labeled samples g.setColor(Color.black); for (int i=0; i