kd-tree

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
theotter
User
Beiträge: 27
Registriert: Mittwoch 30. Juni 2010, 16:08

Dienstag 12. Juli 2011, 20:05

Ich versuche einen 2d-tree zu erstellen und mithilfen dessen, dass nearestNeighbour-Porblem anzugehen.
Sprich:
Ich habe eine n Zahl an Punkten mit k Dimensionen und einen Punkt zu dem der nächst gelegende gefunden werden soll.
Er funktioniert auch eigentlich, bloß es kommen nur ungefähr die richtigen Punkte raus und nicht die absolut Nächsten.

Code: Alles auswählen

class kd_Tree:
    def __init__(self,k):
        self.firstNode = None
        self.k = k
    def createTree(self,points,axis=0):
        class Node:
            def __init__(self,pointList,t):
                self.pointList = pointList
                self.lowNode = None
                self.highNode = None
                self.mAxis = 0
                self.t = t
                
        pointList = points+[]
        placedPoints = []
        n = 1
        t = 1
        k = self.k
        while len(placedPoints) != len(points):           
            if n == 1:
                firstNode = node = Node(points,t)
                currentNodes = [node]
                newNodes = []
            elif n > 5:
                break
            else:
                newNodes = []
             
            for node in currentNodes:                
                pointList = node.pointList
                
                if len(pointList) == 1:
                    placedPoints.append(pointList[0])
                elif len(pointList) == 0:
                    continue
                mAxis = 0#Achse die die Punktmenge unterteilt
                for point in pointList:
                    mAxis += point[axis]
                mAxis /= len(pointList)
                node.mAxis = mAxis
                
                pointsLow = []
                pointsHigh = []
         
                for point in pointList:                   
                    if point[axis] < mAxis:
                        pointsLow.append(point)                     
                    else:
                        pointsHigh.append(point)                    
       
                node.lowNode = Node(pointsLow,t)
                node.highNode = Node(pointsHigh,t)
                               
                newNodes.append(node.lowNode)
                newNodes.append(node.highNode)
                
            t += 1
            axis += 1
            if axis > k-1:
                axis = 0
                
            currentNodes = newNodes+[]             
            n += 1
           
        kd_Tree.firstNode = firstNode
        
    def nearestNeighbour(self,point):
        node = self.firstNode
        axis = 0
        k = self.k
        while len(node.pointList) > 1:           
            if point[axis] < node.mAxis:
                node = node.lowNode
            else:
                node = node.highNode
            bestNode = node
            axis += 1
            if axis > k-1:
                axis = 0
        return bestNode.pointList
                  
kd_Tree = kd_Tree(2)

kd_Tree.createTree(points)

testPoint = (0,4)
neighbour = kd_Tree.nearestNeighbour(testPoint)
Findet ihr den "Fehler"??
lg theotter
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Dienstag 12. Juli 2011, 20:49

theotter hat geschrieben:Findet ihr den "Fehler"??
lg theotter
Ja ;-)
Das Leben ist wie ein Tennisball.
theotter
User
Beiträge: 27
Registriert: Mittwoch 30. Juni 2010, 16:08

Dienstag 12. Juli 2011, 20:50

Nennst du ihn mir dann auch??
(erinnert mich nen bisschen an meinen Physiklehrer)
lg theotter
BlackJack

Dienstag 12. Juli 2011, 22:04

@theotter: Ich denke mal der Link soll darauf hindeuten, dass Du das Rad neu erfindest.
theotter
User
Beiträge: 27
Registriert: Mittwoch 30. Juni 2010, 16:08

Mittwoch 13. Juli 2011, 15:57

Ok, aber ich finde keinen Code bei dem ich genau weiß, was ich als Input hineingeben soll.
Bsp:
http://www.scipy.org/Cookbook/KDTree
Was muss da genau bei data rein??
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Mittwoch 13. Juli 2011, 16:01

Warum suchst du jetzt im Cookbook und verwendest nicht einfach den von mir gezeigten Link? Dort steht doch ganz deutlich was erwartet wird:
data : array-like, shape (n,m)

The n data points of dimension mto be indexed. This array is not copied unless this is necessary to produce a contiguous array of doubles, and so modifying this data will result in bogus results
Das Leben ist wie ein Tennisball.
theotter
User
Beiträge: 27
Registriert: Mittwoch 30. Juni 2010, 16:08

Donnerstag 14. Juli 2011, 11:38

Sorry, ich wusste nicht das das nen Link ist. :oops:
theotter
User
Beiträge: 27
Registriert: Mittwoch 30. Juni 2010, 16:08

Freitag 15. Juli 2011, 00:29

Also, ich habe mir numpy und scipy runtergeladen und ihre Ordner in den Ordner kopiert inder auch die Pythonfiles sind.
Ich versuche scipy zu importieren, aber es scheitert mit folgendem Fehler:
ImportError:
Error importing numpy:you should not try to import numpy from its source directory;
please exit the numpy source tree, and relaunch your intepreter from there.
Ich verstehe den Fehler nicht wirklich bzw. was ich machen soll.
lg theotter
deets

Freitag 15. Juli 2011, 07:57

Das sagt es doch. Du sollst nicht einfach die runtergeladene Distribution nehmen & importieren. Es gibt Anleitungen, wie man das *richtig* installiert - die sind dabei, und denen solltest du auch folgen.
Antworten