# k nearest neighbor algorithmus



## Guest (24. Jan 2007)

Hallo,
ich habe da ein Problem mit dem "k-nearest-neighbor" algorithmus. Gegeben ist eine Punktmenge im 3D. Weiterhin ist gegeben ein Testpunkt, ebenfalls im 3D. Gesucht sind k Punkte aus der Punktmenge, die am nächsten am Testpunkt liegen, also den kleinsten Abstand zu diesem haben.
Theoretisch könnte man nun den Testpunkt nehmen und zu allen Punkten der Punktmenge den Abstand berechnen und dann die k nächsten auswählen. Da ich aber nicht nur einen Testpunkt habe und auch die Punktemenge sehr gross ist, dauert das ziemlich lange, sehr lange...
Ich habe schon gegoogelt und auch ein paar bessere Lösungsansätze gefunden, die ich jedoch leider nicht richtig verstanden habe, sodass ich sie auch nicht in java umsetzen kann. Viele waren auch nur skizzenhaft beschrieben.
Hat vielleicht einer von euch eine Idee, wie man den Algorithmus besser umsetzen kann oder kennt jemand einen guten Link mit möglichst wenig Fachchinesisch.
Ich danke euch schon mal im Voraus für eure Mühen.


----------



## Gelöschtes Mitglied 5909 (24. Jan 2007)

das hört sich nach vektorrechnung an
ich weiß zwar nicht genau wie du den punkt gegeben hast, aber des is eigentlich recht einfach
http://www.mathe-online.at/mathint/vect1/i.html#Abstand
des is sollte auch von der performance her ganz ok sein denk ich
oder du verwendest euklid:
http://de.wikipedia.org/wiki/Euklidischer_Abstand


----------



## Gast (24. Jan 2007)

Hallo raiL,
danke für deine Antwort, aber das Problem ist nicht die Berechnung des Abstandes, ich verwende übrigens den euklidischen, sondern die Zeit, die der Rechner dafür benötigt alle Abstände zu berechnen. 
Ich suche einen anderen Weg, als den alle Abstände einzeln auszurechnen und dann die k kürzesten zu bestimmen. Ideen?


----------



## Marco13 (24. Jan 2007)

Wenn du z.B. insgesamt 10 Millionen Punkte hast, und dann für EINEN Punkt die 100 nächsten Nachbarn finden mußt, ist das schwierig. Wenn du aber 10 Millionen Punkte hast, und dann nacheinander z.B. für 100000 Punkte _jeweils_ die 100 nächsten Nachbarn finden mußt, kann es sich lohnen, da eine passende Datenstuktur drüber aufzubauen (die Punkte z.B. in einen Octree oder kD-tree oder so einsortieren - das dauert erstmal einen Moment, aber danach gehen die Abfragen vermutlich wesentlich schneller). 
Eine andere (algorithmische) Optimierung wüßte ich jetzt nicht. 
Und dass du nur die _quadrierten_ Distanzen verwenden solltest, weißt du wahrscheinlich.


----------



## Gast (24. Jan 2007)

Ja, das mit den trees hab ich auch schon gelesen, aber ich weiss einfach nicht, wie ich diese Datenstruktur aufbauen soll. Wie du schon schreibst, es würde sich lohnen 
Kannst du mir bitte einen Tip geben, wie ich die Daten sinnvoll in einen tree einsortieren kann? Vielleicht sogar an einem ganz klitzekleinen Beispiel? Das wäre echt klasse.


----------



## Marco13 (25. Jan 2007)

Es KÖNNTE sich lohnen - das kommt darauf an, wie viele Abfragen du nachher machen willst. 

Auf http://en.wikipedia.org/wiki/Kd-tree gibt es ein bißchen Pseudocode für die Erstellung eines kd-Trees, und weiter unten auch eine Beschreibung, wie man einen nearest Neighbor findet. Notfalls gibts auch gleich Fertigen code dafür http://www.google.de/search?hl=de&lr=&q=+site:www.cs.wlu.edu+java+kd+tree (4. Ergebnis) - Schau vielleicht mal drüber, und frag dann nochmal etwas konkreter nach.


----------



## Zunera (25. Jan 2007)

Hi, 

also so einen Baum aufzubauen lohnt in jedem Fall (ok, außer man hat wirklich nur wenig (ich sag mal <50) Punkte). Für die Uni musste ich mal so ein Projekt angehen - aber in C++. Zwar bin ich weder ein versierter C++ Programmierer noch weiß ich, ob du was damit anfangen kannst, aber ich poste mal meine komplette kdTree Klasse in C++ Code.

Wichtige Funktionen sind:
setCellsize(int size) - legt die Anzahl der Punkte pro "Blatt" fest
setPoints(const vector<Point>& pt) - baut den kdTree mit der gegebenen Punktmenge auf
collectInRadius(Point& p, float radius) - gibt alle Punkte im gegebenen Radius um den gegebenen Punkt zurück
collectKNearest(Point& p, int knearest) - gibt die k-nächsten Punkte um den gegebenen Punkt zurück


```
#include "kdDS.h"
#include <GL/glut.h>


// -------------------------------kdNode Implementation -----------------------

//-----------------------------------------------------------------------------
kdNode::kdNode()
//-----------------------------------------------------------------------------
{
}

//-----------------------------------------------------------------------------
//plist ist die Punktmenge des Knotens
//nrPoints gibt an, wieviel Punkte maximal in einen Knoten (Zelle) gehören
kdNode::kdNode(vector<Point>& plist, int nrPoints)
//-----------------------------------------------------------------------------
{
    leaf = false;

    unsigned int nrOfElements = plist.size();

    //finde die Begrenzungspunkte für diese Zelle/Knoten
    pMin = plist.at(0);
    pMax = plist.at(0);
    for(int i = 0; i < nrOfElements; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            //suche nach kleinstem Wert in jeder Dimension        
            if((plist.at(i)).p[j] < pMin.p[j])
            {
                pMin.p[j] = (plist.at(i)).p[j];
            }
            //suche nach größtem Wert in jeder Dimension
            if((plist.at(i)).p[j] > pMax.p[j])
            {
                pMax.p[j] = (plist.at(i)).p[j];
            }
        }
    }
    
    //unterteile, falls mehr Punkte in Knoten als gewünscht
    if(plist.size() > nrPoints)
    {
        Point diff = pMax - pMin;
        
        //printf("Diff: %f/%f/%f\n", diff.p[0], diff.p[1], diff.p[2]);
        
        vector<Point> leftList, rightList;
        
        //Teile Zelle/Knoten entlang der weitesten Ausdehnung
        if(diff.p[0] > diff.p[1] && diff.p[0] > diff.p[2])
        {
                //median cut on x-axis
                doMedianCut(plist, leftList, rightList, 0);
        } else
        if(diff.p[1] > diff.p[2])
        {
                //median cut on y-axis
                doMedianCut(plist, leftList, rightList, 1);
        } else
        {
                //median cut on z-axis
                doMedianCut(plist, leftList, rightList, 2);
        }

        left = new kdNode(leftList, nrPoints);
        right = new kdNode(rightList, nrPoints);
    } else
    //falls Punktmenge des Knotens klein genug, wird Knoten zu einem Blatt
    //und die Punkte werden gesichert
    {
        points = plist;
        leaf = true;
    }
}

//-----------------------------------------------------------------------------
//berechnet die Entfernung eines Punktes zu dieser Zelle/Knoten
float kdNode::distance(const Point& p)
//-----------------------------------------------------------------------------
{
    Point a = pMin - p;
    Point b = p - pMax;
    
    int i;
    for(i = 0; i < 3; i++)
    {
        //prüfe, wo p[i] liegt - Annahme: 'links' von pMin
        //Abstand Zelle-Punkt: pMin - p
        if(a.p[i] < 0.0)
        //p[i] liegt 'rechts' von pMin - aber wo genau? (Annahme revidiert)
        {
            if(b.p[i] < 0.0)
            //p[i] liegt zwischen pMin und pMax - Abstand Zelle-Punkt: 0
            {
                a.p[i] = 0.0;
            }
            else
            //p[i] liegt 'rechts' von pMax - Abstand Zelle-Punkt: p - pMax
            {
                a.p[i] = b.p[i];
            }
        }
    }
    
    //printf("Distance function finished!\n");
    return a.length();

}

//-----------------------------------------------------------------------------
void kdNode::collectInRadius(vector<Point>& plist, Point& p, float radius)
//-----------------------------------------------------------------------------
{
    if(distance(p) <= radius)
    {
        if(!leaf)
        {
            left->collectInRadius(plist, p, radius);
            right->collectInRadius(plist, p, radius);
        } else
        {
            Point distVect;
            float dist;
            for(int i = 0; i < points.size(); i++)
            {
                //use distance funktion
                //temporal verwende einfache Distanzberechnung
                distVect = p - points.at(i);
                dist = distVect.length();
                
                if(dist <= radius)
                {
                    plist.push_back(points.at(i));
                }
            }
        }
    }
}

//-----------------------------------------------------------------------------
//berechnet die Entfernung eines Punktes zu dieser Zelle/Knoten
float kdNode::distance2D(const Point& p)
//-----------------------------------------------------------------------------
{
    Point a = pMin - p;
    Point b = p - pMax;
    
    int i;
    for(i = 0; i < 2; i++)
    {
        //prüfe, wo p[i] liegt - Annahme: 'links' von pMin
        //Abstand Zelle-Punkt: pMin - p
        if(a.p[i] < 0.0)
        //p[i] liegt 'rechts' von pMin - aber wo genau? (Annahme revidiert)
        {
            if(b.p[i] < 0.0)
            //p[i] liegt zwischen pMin und pMax - Abstand Zelle-Punkt: 0
            {
                a.p[i] = 0.0;
            }
            else
            //p[i] liegt 'rechts' von pMax - Abstand Zelle-Punkt: p - pMax
            {
                a.p[i] = b.p[i];
            }
        }
    }
    a.p[2] = 0.0;
    //printf("Distance function finished!\n");
    return a.length();

}

//-----------------------------------------------------------------------------
void kdNode::collectInRadius2D(vector<Point>& plist, Point& p, float radius)
//-----------------------------------------------------------------------------
{
    if(distance2D(p) <= radius)
    {
        if(!leaf)
        {
            left->collectInRadius2D(plist, p, radius);
            right->collectInRadius2D(plist, p, radius);
        } else
        {
            Point distVect;
            float dist;
            for(int i = 0; i < points.size(); i++)
            {
                //use distance funktion
                //temporal verwende einfache Distanzberechnung
                distVect = p - points.at(i);
                distVect.p[2] = 0.0;
                dist = distVect.length();
                
                if(dist <= radius)
                {
                    plist.push_back(points.at(i));
                }
            }
        }
    }
}

//-----------------------------------------------------------------------------
Point kdNode::getMin()
//-----------------------------------------------------------------------------
{
    return pMin;
}

//-----------------------------------------------------------------------------
Point kdNode::getMax()
//-----------------------------------------------------------------------------
{
    return pMax;
}

//-----------------------------------------------------------------------------
void kdNode::draw(bool colored)
//-----------------------------------------------------------------------------
{
    //zeichne den kdTree rekursiv
    if(!leaf){
        left->draw(colored);
        right->draw(colored);
    } else
    {
        //glEnable(GL_LIGHTING);
        glDisable(GL_LIGHTING);
        
        glColor3f(1.0, 1.0, 0.0);
        
        if(colored)
        {
            Point col = pMin;
            
            col.normalize();
            col = col / 2.0;
            
        	glColor3f(0.5 + col.p[0], 0.5 + col.p[1], 0.5 + col.p[2]);
    	}
    
        glBegin(GL_POINTS);
    
        //start painting model
    	for(int i = 0; i < points.size(); i++)
    	{
            //set point of triangle
            glVertex3fv(points.at(i).p);
            
        } //end painting model
        
        glEnd();
        
        glEnable(GL_LIGHTING);
    }
}

//-----------------------------------------------------------------------------
void kdNode::sort(vector<Point>& pts, int key)
//-----------------------------------------------------------------------------
{
    int minIndex;
    Point p;
    int i;
    for(i = 0; i < pts.size() - 1; i++)
    {
        minIndex = i;
        for(int j = i + 1; j < pts.size(); j++)
        {
            if(pts.at(j).p[key] < pts.at(minIndex).p[key])
            {
                minIndex = j;
            }
        }
        p = pts.at(i);
        pts.at(i) = pts.at(minIndex);
        pts.at(minIndex) = p;
       /* 
        if(i!=minIndex)
        printf("Punkte vertauscht: i=%d minIndex=%d\nmin(%f/%f/%f), anderer (%f/%f/%f)\n",
            i, minIndex, pts.at(minIndex).p[0], pts.at(minIndex).p[1], pts.at(minIndex).p[2],
            pts.at(i).p[0], pts.at(i).p[1], pts.at(i).p[2]);
            */
    }

}

// -------------------------------kdDS Implementation -------------------------

//-----------------------------------------------------------------------------
kdDS::kdDS()
//-----------------------------------------------------------------------------
{
    cellSize = 10;
}

//-----------------------------------------------------------------------------
kdDS::kdDS(int size)
//-----------------------------------------------------------------------------
{
    cellSize = size;
}

//-----------------------------------------------------------------------------
kdDS::~kdDS()
//-----------------------------------------------------------------------------
{
}
//-----------------------------------------------------------------------------
vector<Point> kdDS::collectKNearest(Point& p, int knearest)
//-----------------------------------------------------------------------------
{

    vector<Point> pts;

    //berechne Diagonalenlänge der BigBox
    Point diff = root->getMax() - root->getMin();
    float dimension = diff.length();
    
    //berechne  Entfernung des ggb. Punktes zur Punktmenge (BigBox)
    float dist = root->distance(p);
    
    //falls mehr Pkte gefordert als vorhanden, gib gleich zurück
    if(knearest >= nrOfPoints)
    {
        root->collectInRadius(pts, p, dist + dimension);
        //Sortierung wird für korrekte Frameworkdarstellung gebraucht
        //quickSortDistance(pts, p, 0, pts.size());
        return pts;
    }
    
    //extra secret speed code!!!
    float multiplikator;
    if(dist == 0)
    {
        Point middle = root->getMin() + (diff / 2);
        diff = p - middle;
        multiplikator = 0.5 + 0.8 * diff.length() / (dimension);
    } else
    {
        multiplikator = 1.0;
    }


    float aspect;
    //printf("Im searching k-nearest Pts! Distance: %f Size: %d\n Dimension: %f Aspect: %f\n",
    //     dist, pts.size(), dimension, aspect);
     
    int range;
    //Schleife, um günstig viele (ausreichend) Punkte zu erhalten
    do {

        //prozentualer Anteil von gesuchten Punkten zu Gesamtpunkten
        //ist Grundlage für die Radiusbestimmung
        aspect = multiplikator * (knearest - pts.size()) / nrOfPoints;
        //falls p ausserhalb, vergrößere Suchradius
        //if(dist > 0) aspect = 2.0 * aspect;

        //vergrößere den Radius schrittweise
        dist = dist + dimension * aspect;

        pts.clear();
        root->collectInRadius(pts, p, dist);
        //root->collectKNearest(pts, p, dist);
        //verkleinere den zu durchsuchenden Raum
        //dimension = dimension - dimension * aspect;
        
        //printf("Im in the k-Nearest Loop! Distance: %f Size: %d\n", dist, pts.size());

    } while((range = pts.size() - knearest) < 0);
   
    //sortiere die Liste ...
    quickSortDistance(pts, p, 0, pts.size());
    //printf("Did Distance-Quicksort!\n");
    
    //...um überschüssige rauszuschmeissen!
    //(bessere implemtierung!?);
    for(int i = 0; i < range; i++)
    {
        pts.pop_back();
    }
    
    return pts;
}
//-----------------------------------------------------------------------------
vector<Point> kdDS::collectInRadius(Point& p, float radius)
//-----------------------------------------------------------------------------
{
    vector<Point> pts;
    root->collectInRadius(pts, p, radius);
    return pts;
}

//-----------------------------------------------------------------------------
vector<Point> kdDS::collectInRadius2D(Point& p, float radius)
//-----------------------------------------------------------------------------
{
    vector<Point> pts;
    root->collectInRadius2D(pts, p, radius);
    return pts;
}

//-----------------------------------------------------------------------------
void kdDS::draw()
//-----------------------------------------------------------------------------
{
    draw(false);
}

//-----------------------------------------------------------------------------
void kdDS::draw(bool colored)
//-----------------------------------------------------------------------------
{
    root->draw(colored);
}

//-----------------------------------------------------------------------------
void kdDS::draw(const vector<Point>& plist)
//-----------------------------------------------------------------------------
{
    //glEnable(GL_LIGHTING);
    glDisable(GL_LIGHTING);
    
	glColor3f(1.0, 1.0, 1.0);

    glBegin(GL_POINTS);

    //start painting model
	for(int i = 0; i < plist.size(); i++)
	{
        //set point of triangle
        glVertex3fv(plist.at(i).p);
        
    } //end painting model
    
    glEnd();
    
    glEnable(GL_LIGHTING);

}

//-----------------------------------------------------------------------------
int kdDS::size()
//-----------------------------------------------------------------------------
{
    return nrOfPoints;
}

//-----------------------------------------------------------------------------
void kdDS::setPoints(const vector<Point>& pt)
//-----------------------------------------------------------------------------
{
    nrOfPoints = pt.size();
    
    vector<Point> points = pt;
    
    //clock_t start, stop;
    //start = clock();
    
    root = new kdNode(points, cellSize);
/*    
    stop = clock();
    clock_t diff = stop - start;
    printf("Es dauerte %f sekunden.\n", 1.0 * diff / CLOCKS_PER_SEC);
    */
}

//-----------------------------------------------------------------------------
void kdDS::setCellsize(int size)
//-----------------------------------------------------------------------------
{
    cellSize = size;
}


Point kdDS::getMin()
{
    return root->getMin();
}

Point kdDS::getMax()
{
    return root->getMax();
}

vector<Point> kdDS::getPoints(void)
{
    Point p(0,0,0);
    return collectKNearest(p, size());
}
```
(eigentlich fast 1:1 nach JAVA umschreibbar - und ggf. verbesserbar )

Falls du mal eine Implementierung in JAVA hast, bin sehr interessiert daran! Hab einfach keine Zeit und keine Not, das mal in JAVA umzusetzen...


----------



## Gast (27. Jan 2007)

Hallo,
erst mal ein RIESEN Dankeschön, das waren echt super Tipps.
Zunera, tut mir leid, aber ich hatte einfach keine Zeit den Code umzuschreiben, musst also selbst ran 
Stattdessen habe ich den Tipp von Marco13 verfolgt und die Demodatei meinen Bedürfnissen angepasst. Kann ich dir, Zunera, falls dus mal brauchst auch nur empfehlen. 
Auf jeden Fall hab ichs jetzt geschafft und es geht viiiiiiieeeeel schneller. Vielen, vielen Dank für die Hilfe!


----------

