# Very simple k-NN algorithm does not work

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);
}
}
``````

1 Like

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?

1 Like

You can find a lot of resources on the web

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

1 Like

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

2 Likes

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

2 Likes

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

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
//
``````
3 Likes

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

1 Like