Very simple k-NN algorithm does not work

anna_mei · April 15, 2019, 5:51pm

hi everybody,

today I tried to write a very simple k-NN algorithm for class. unfortunetally I did not succeed so far. can someone see where the code is erroneous? my best guess is that the error occurs in the colour assignment.
also if someone has a simple k-NN code model, I would be greateful to take an educational look.

with best regards
anna

// a simple knn algorithm 

int[][] balls = new int[3][200];
int[] abstand = new int[200];
int[] minabstand = new int[3];
int l = 0;

/*
Definition:
 rot hat den Wert 0 --> red is 0
 blau hat den Wert 1 --> blue is 1
 */

int ballanzahl = 10;

void setup() {
  size (800, 800);
  frameRate(1);
}

void ballsfunction() {
  for (int i=0; i <10; i=i+1) { // die Koordinaten der Bälle werden erzeugt zufällig 
    balls[0][i]=10+ int(random(0, 790));
    balls[1][i]=10+ int(random(0, 790));
    balls[2][i]=int(random(0, 2));
    //println(balls[2][i]);
  }
  for (int i=0; i <10; i=i+1) { // die Bälle werden gezeichnet
    if (balls[2][i]==0)
    {
      fill(255, 0, 0);
      ellipse(balls[0][i], balls[1][i], 10, 10);
    } else
    {
      fill(0, 0, 255);
      ellipse(balls[0][i], balls[1][i], 10, 10);
    }
  }
}


/*void drawballs()
 {
 for (int i=0; i <ballanzahl; i=i+1) { // die Bälle werden gezeichnet
 if (balls[2][i]==0)
 {
 fill(255, 0, 0);
 ellipse(balls[0][i], balls[1][i], 10, 10);
 } else
 {
 fill(0, 0, 255);
 ellipse(balls[0][i], balls[1][i], 10, 10);
 }
 } 
 //println(ballanzahl);
 }
 */


void draw() { 
  l = l +1;
  if (l == 1)
    ballsfunction();
  else if (l==2) {
        balls[0][11]=10+ int(random(0, 790));
    balls[1][11]=10+ int(random(0, 790));
    fill(255);
    ellipse(balls[0][11], balls[1][11], 10, 10);
  } else if (l==3)
  action();
}

void bubbleSort()
{
  int tausch;
  for (int n=ballanzahl-1; n>1; n=n-1)
  {
    for (int i=0; i<n-1; i=i+1)
    {
      if (abstand[i] < abstand[i+1])
      {
        tausch = abstand[i];
        abstand[i]=abstand[i+1];
        abstand[i+1]=tausch;
      } // Ende if
    } // Ende innere for-Schleife
  } // Ende äußere for-Schleife
  
}

void regel() // error here?
{
  int rot=0;
  int blau=0;
  for (int i=1; i<=3; i=i+1)
  {
    if (balls[2][ballanzahl-i] > 0)
      blau=blau+1;
    else 
    rot=rot+1;
    println(rot);
  }
  if (rot > blau)
    balls[2][ballanzahl]=0;
  else balls[2][ballanzahl]=1;
  //println(balls[2][ballanzahl]);
}

//void mouseClicked()
void action()
{
  ballanzahl=ballanzahl+1;
  //balls[0][ballanzahl]=mouseX;
  //balls[1][ballanzahl]=mouseY;
  for (int k = 0; k<ballanzahl-1; k=k+1) {
    abstand[k]=int(sqrt(sq(balls[0][k]-balls[0][ballanzahl])+sq(balls[1][k]- balls[1][ballanzahl])));
  }
  bubbleSort();
  regel(); 
  if (balls[2][ballanzahl]>0)
  {
    fill(0, 0, 255);
    ellipse(balls[0][ballanzahl], balls[1][ballanzahl], 10, 10);
  } else
  {
    fill(255, 0, 0);
    ellipse(balls[0][ballanzahl], balls[1][ballanzahl], 10, 10);
  }
}

jeremydouglass · April 20, 2019, 4:19am

Did you resolve this issue?

When you say “the error occurs” – what are you expecting to happen? What happens instead? Do you get an error message? If so, what is it?

Chrisir · April 20, 2019, 7:41am

You can find a lot of resources on the web

Just google it

Your code: remember to click ctrl-t regularly in processing

It’s not very well commented I have to say

I‘ll take a look later maybe

Chrisir · April 20, 2019, 10:41am

some remarks:

The var l is a state? The letter l is hard to read better use state as variable name

you don’t use background at the start of draw

action is only executed once since l / state is incremented each frame in draw

I understand that you sort by the distance and compare a new ball with the 3 nearest

1. Does the bubble sort work?
1. Does function regel work?

I wasn’t really able to solve it.

When the test data are evenly distributed red and blue balls, it’s hard to judge what the outcome of a new ball should be

anna_mei · April 23, 2019, 7:38am

Dear Chrisir,

thank you very much for your answer and the constructive criticism. I will work on my documentation skills!

I was trying exactly what you wrote: “sort by the distance and compare a new ball with the 3 nearest” and THEN it should take on the colour that appears 2 out of 3 times. … Maybe you are right and sometimes more than 3 balls are equally close – since the algorithm seems to work half the time and the other half it seems to be random.

I saw the Wikipedia site but wanted to see an kNN algorithm actually written down, not just in math but in code, to get an understanding how much code it is and how it is structured logically. I am very new to programming and processing is the only language / environment that I know. I tried to look for some code on Github but could not follow the code that I found there.

But all is well that ends well :). I have learned a lot (!) while working on this little peace of code, even though it does not work 100% of the time .

Thank you again very much for looking into it.

Best Regards
Anna

anna_mei · April 23, 2019, 7:42am

Dear Jeremy,

thank you very much for your answer. I haven’t been able to solve the issue yet, but I got an idea of where the mistake could be. It might be the distribution of data, here the red and blue coloured balls. If it is too even, than the algorithm rules do not apply.

I have learned a lot from working on this little peace of code and the result as such is sufficient for now.

Best Regards
Anna

Chrisir · April 23, 2019, 5:19pm

Hello again,

I did a bit of rewriting your code.

You can click any key to restart the sketch (new distribution of 10 balls).
You can now click the mouse anywhere and a new ball is added at mouse position and immediately classified as red or blue.You can click the mouse as often as you like.
Also, the ball’s number in the array is displayed so we can see whether the bubbleSort is working correctly

One of the major mistakes was that you sort the array abstand but not the array balls. But regel() uses the array balls so it worked in vain. I made it so that the sketch now sorts abstand AND the array balls.

I also changed some minor stuff, e.g.

I put { in the same line, not on the next line and
I replaced i=i+1 by i++.
The var l is called state now but it’s not used anymore.
New balls are treated like old balls in the next round. So they are seen as members of the initial data.

I speak also German.

I hope it helps.

Regards Chrisir


// a simple knn algorithm 

// https://discourse.processing.org/t/very-simple-k-nn-algorithm-does-not-work/10305

// no classes / oop 

/*
Definition:
 rot hat den Wert 0 --> red is 0
 blau hat den Wert 1 --> blue is 1
 (--> im ersten array von balls ist dies der Wert in slot 2)
 */

int[][] balls = new int[3][200];   // 2D array: the first array holds x,y,red/blue (0/1), the 2nd array just the index of the ball [normally we would have it [200][3] I guess]

// using float here 
float[] abstand = new float[200];
float[] minabstand = new float[3];

// not used anymore !!!!!!!!!!!!!!!!!!!!!!!
int state = 0;

int ballanzahl;

boolean sortingWasExecutedOnce = false; 

// ------------------------------------------------------------------------------

void setup() {
  size (800, 800);

  ballsInit();
}

void draw() {
  // delete screen
  background(0);  
  noStroke(); 
  // draw all balls 
  ballsDraw();

  // show a help text 
  fill(255); 
  text("Hit any key for new distribution", 23, 23); 
  if (sortingWasExecutedOnce) {
    text("The numbers show the sequence of the balls (in terms of their distance to the new ball)", 23, 43);
  }

  state++;
  if (state == 1) {
    // ballsDraw();
  } else if (state==2) {
    //balls[0][11]=10+ int(random(0, 790));
    //balls[1][11]=10+ int(random(0, 790));
    //fill(255);
    //ellipse(balls[0][11], balls[1][11], 10, 10);
  } else if (state==3) {
    // action();
  }
}

// ------------------------------------------------------------------------------
// Inputs 

void keyPressed() {
  // reset 
  ballsInit();
}

void mousePressed() {
  // was formerly called : void action() {
  // add a new ball and decide its kind. 
  // This simulate a new item that has to be classified by the AI in the vector space 

  // add ball at mouse position 
  balls[0][ballanzahl]=mouseX;
  balls[1][ballanzahl]=mouseY;
  balls[2][ballanzahl]=3; // 3 = unknown

  // define abstand[] in relation to the new ball 
  for (int k = 0; k<ballanzahl; k++) {
    abstand[k] = dist ( balls[0][k], balls[1][k], 
      balls[0][ballanzahl], balls[1][ballanzahl] ); // using dist() here
  }//for 

  // the core idea 
  bubbleSort();
  regel();

  // increase ballanzahl (after all that has happened) 
  ballanzahl++;
}

// ------------------------------------------------------------------------------
// other functions 

void ballsInit() { 
  // die Koordinaten der Bälle werden zufällig erzeugt  
  // init (and reset on keyPressed)
  ballanzahl = 10; // reset 
  for (int i=0; i < ballanzahl; i++) { 
    balls[0][i]= 10 + int(random(0, width-20)); // 10 is the diameter of the balls 
    balls[1][i]= 10 + int(random(0, width-20));
    balls[2][i]= int(random(0, 2));
    //println(balls[2][i]);
  }
}

void ballsDraw() {
  // die Bälle werden gezeichnet
  for (int i=0; i < ballanzahl; i++) {  // in for-loop we must use ballanzahl (and not 10) so that new balls are displayed !!!!!!!!!!!!!!!!!! 

    // show new bal with white
    if (sortingWasExecutedOnce && i==ballanzahl-1) {
      stroke(255);
      noFill(); 
      ellipse(balls[0][i], balls[1][i], 14, 14);
      ellipse(balls[0][i], balls[1][i], 18, 18);
      noStroke();
    }

    // check type red/blue and set color  
    if (balls[2][i]==0) {
      fill(255, 0, 0);//red
    } else {
      fill(0, 0, 255); // blue
    }//else

    // show ball at x,y
    ellipse(balls[0][i], balls[1][i], 10, 10);
    // show the number in the array sequence 
    if (sortingWasExecutedOnce) {
      text(i, balls[0][i]+10.5, balls[1][i]);
    }
  }//for
}//func 

void bubbleSort() {
  // sort abstand 
  float tausch; // swap var for abstand/dist
  int[] tauschBall = new int[3];  // swap var for a ball

  for (int n=ballanzahl; n>0; n--) {
    for (int i=0; i<n; i++) {
      if (abstand[i] < abstand[i+1]) {
        tausch = abstand[i];
        abstand[i]=abstand[i+1];
        abstand[i+1]=tausch;

        // also swap the ball !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! THAT WAS THE MAJOR MISTAKE  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! The function regel() uses balls[][], not abstand[] !!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        tauschBall[0] = balls[0][i];
        tauschBall[1] = balls[1][i];
        tauschBall[2] = balls[2][i];

        balls[0][i] = balls[0][i+1];
        balls[1][i] = balls[1][i+1];
        balls[2][i] = balls[2][i+1];

        balls[0][i+1] = tauschBall[0];
        balls[1][i+1] = tauschBall[1];
        balls[2][i+1] = tauschBall[2];
      } // Ende if
    } // Ende innere for-Schleife
  } // Ende äußere for-Schleife

  // set flag 
  sortingWasExecutedOnce = true;
}// ENDE func 

void regel() {
  int rot=0;
  int blau=0;

  // we try to count the types/colors of the nearest three balls  
  for (int i=1; i<=3; i++) {
    if (balls[2][ballanzahl-i] > 0)
      blau++;
    else 
    rot++;
  }//for 

  // eval result and classify the new ball accordingly 
  if (rot > blau)
    balls[2][ballanzahl]=0;
  else balls[2][ballanzahl]=1;
  //println(balls[2][ballanzahl]);
}//func
//

anna_mei · April 30, 2019, 2:07pm

Dear Chrisir,

thank you very much! Dankeschön :).
I just tried out your code and it worked flaweless on my computer too.
Thank you for helping me to understand (simple, yes :)) machine learning and also how to comment correctly :D.

Regards
Anna

Topic		Replies	Views
Blob tracking and collision detection Libraries	17	1892	August 1, 2019
Agents coding work but need add on two variable data Coding Questions	28	1521	May 25, 2018
NullPointerException Coding Questions	20	649	November 1, 2018
N-dimensional sorting and color Coding Questions	25	1864	April 19, 2020
Changing webcam-pixels to "nearest" color from color palette array Libraries	29	1863	November 17, 2019

Very simple k-NN algorithm does not work

Related topics