KD- 트리를 사용하여 범위 내의 모든 이웃 찾기

Question

DBSCAN과 함께 사용하기 위해 KD-tree을 구현하려고합니다. 문제는 거리 기준을 충족하는 모든 포인트의 모든 이웃을 찾아야한다는 것입니다. 문제는 내 구현에서 nearestNeighbours 메서드를 사용할 때 순진한 검색 (원하는 출력)을 사용할 때 동일한 출력을 얻지 못하는 것입니다. 내 구현은 python implementation에서 변경되었습니다. 나는이 프로그램을 실행할 때

//Point.java 
package dbscan_gui; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashSet; 

public class Point { 

    final HashSet<Point> neighbours = new HashSet<Point>(); 
    int[] points; 
    boolean visited = false; 
    public Point(int... is) { 
     this.points = is; 
    } 
    public String toString() { 
     return Arrays.toString(points); 
    } 

    public double squareDistance(Point p) { 
     double sum = 0; 
     for (int i = 0;i < points.length;i++) { 
      sum += Math.pow(points[i] - p.points[i],2); 
     } 
     return sum; 
    } 
    public double distance(Point p) { 
     return Math.sqrt(squareDistance(p)); 
    } 
    public void addNeighbours(ArrayList<Point> ps) { 
     neighbours.addAll(ps); 
    } 
    public void addNeighbour(Point p) { 
     if (p != this) 
      neighbours.add(p); 
    } 
} 

//KDTree.java 
package dbscan_gui; 


import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 
import java.util.Iterator; 
import java.util.List; 
import java.util.Random; 
import java.util.TreeSet; 


public class KDTree { 
    KDTreeNode root; 
    PointComparator[] comps; 
    public KDTree(ArrayList<Point> list) { 
     int axes = list.get(0).points.length; 

     comps = new PointComparator[axes]; 
     for (int i = 0; i < axes; i++) { 
      comps[i] = new PointComparator(i); 
     } 
     root = new KDTreeNode(list,0); 
    } 
    private class PointComparator implements Comparator<Point> { 
     private int axis; 
     public PointComparator(int axis) { 
      this.axis = axis; 
     } 
     @Override 
     public int compare(Point p1, Point p2) { 
      return p1.points[axis] - p2.points[axis]; 
     } 
    } 

    /** 
    * Adapted from https://code.google.com/p/python-kdtree/ 
    * Stores points in a tree, sorted by axis 
    */ 
    public class KDTreeNode { 
     KDTreeNode leftChild = null; 
     KDTreeNode rightChild = null; 
     Point location; 

     public KDTreeNode(ArrayList<Point> list, int depth) { 
      if(list.isEmpty()) 
       return; 
      final int axis = depth % (list.get(0).points.length); 

      Collections.sort(list, comps[axis]); 
      int median = list.size()/2; 
      location = list.get(median); 
      List<Point> leftPoints = list.subList(0, median); 
      List<Point> rightPoints = list.subList(median+1, list.size()); 
      if(!leftPoints.isEmpty()) 
       leftChild = new KDTreeNode(new ArrayList<Point>(leftPoints), depth+1); 
      if(!rightPoints.isEmpty()) 
       rightChild = new KDTreeNode(new ArrayList<Point>(rightPoints),depth+1); 
     } 

     /** 
     * @return true if this node has no children 
     */ 
     public boolean isLeaf() { 
      return leftChild == null && rightChild == null; 
     } 

    } 
    /** 
    * Finds the nearest neighbours of a point that fall within a given distance 
    * @param queryPoint the point to find the neighbours of 
    * @param epsilon the distance threshold 
    * @return the list of points 
    */ 
    public ArrayList<Point> nearestNeighbours(Point queryPoint, int epsilon) { 
     KDNeighbours neighbours = new KDNeighbours(queryPoint); 
     nearestNeighbours_(root, queryPoint, 0, neighbours); 
     return neighbours.getBest(epsilon); 
    } 
    /** 
    * @param node 
    * @param queryPoint 
    * @param depth 
    * @param bestNeighbours 
    */ 
    private void nearestNeighbours_(KDTreeNode node, Point queryPoint, int depth, KDNeighbours bestNeighbours) { 
     if(node == null) 
      return; 
     if(node.isLeaf()) { 
      bestNeighbours.add(node.location); 
      return; 
     } 
     int axis = depth % (queryPoint.points.length); 
     KDTreeNode nearSubtree = node.rightChild; 
     KDTreeNode farSubtree = node.leftChild; 
     if(queryPoint.points[axis] < node.location.points[axis]) { 
      nearSubtree = node.leftChild; 
      farSubtree = node.rightChild; 
     } 
     nearestNeighbours_(nearSubtree, queryPoint, depth+1, bestNeighbours); 
     if(node.location != queryPoint) 
      bestNeighbours.add(node.location);  
     if(Math.pow(node.location.points[axis] - queryPoint.points[axis],2) <= bestNeighbours.largestDistance) 
      nearestNeighbours_(farSubtree, queryPoint, depth+1,bestNeighbours); 
     return; 
    } 
    /** 
    * Private datastructure for holding the neighbours of a point 
    */ 
    private class KDNeighbours { 
     Point queryPoint; 
     double largetsDistance = 0; 
     TreeSet<Tuple> currentBest = new TreeSet<Tuple>(new Comparator<Tuple>() { 

      @Override 
      public int compare(Tuple o1, Tuple o2) { 
       return (int) (o1.y-o2.y); 
      } 

     }); 
     KDNeighbours(Point queryPoint) { 
      this.queryPoint = queryPoint; 
     } 
     public ArrayList<Point> getBest(int epsilon) { 
      ArrayList<Point> best = new ArrayList<Point>(); 
      Iterator<Tuple> it = currentBest.iterator(); 
      while(it.hasNext()) { 
       Tuple t =it.next(); 
       if(t.y > epsilon*epsilon) 
        break; 
       else if(t.x != queryPoint) 
        best.add(t.x); 
      } 
      return best; 
     } 

     public void add(Point p) { 
      currentBest.add(new Tuple(p, p.squareDistance(queryPoint))); 
      largestDistance = currentBest.last().y; 
     } 
     private class Tuple { 
      Point x; 
      double y; 
      Tuple(Point x, double y) { 
       this.x = x; 
       this.y = y; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     int epsilon = 3; 

     System.out.println("Epsilon: "+epsilon); 
     ArrayList<Point> points = new ArrayList<Point>(); 
     Random r = new Random(); 
     for (int i = 0; i < 10; i++) { 
      points.add(new Point(r.nextInt(10), r.nextInt(10))); 
     } 
     System.out.println("Points "+points); 
     System.out.println("----------------"); 
     System.out.println("Neighbouring Kd"); 
     KDTree tree = new KDTree(points); 
     for (Point p : points) { 
      ArrayList<Point> neighbours = tree.nearestNeighbours(p, epsilon); 
      for (Point q : neighbours) { 
       q.addNeighbour(p); 
      } 
      p.addNeighbours(neighbours); 
      p.printNeighbours(); 
      p.neighbours.clear(); 
     } 
     System.out.println("------------------"); 
     System.out.println("Neighbouring O(n^2)"); 
     for (int i = 0; i < points.size(); i++) { 
      for (int j = i + 1; j < points.size(); j++) { 
       Point p = points.get(i), q = points.get(j); 
       if (p.distance(q) <= epsilon) { 
        p.addNeighbour(q); 
        q.addNeighbour(p); 
       } 
      } 
     } 
     for (Point point : points) { 
      point.printNeighbours(); 
     } 

    } 
} 

나는 다음과 같은 출력 (모델 출력되는 후반)를 얻을 : 여기에 지금까지있어 무엇

Epsilon: 3 
Points [[9, 5], [4, 7], [3, 1], [0, 0], [5, 7], [0, 1], [5, 5], [1, 2], [9, 2], [9, 9]] 
---------------- 
Neighbouring Kd 
Neighbours of [0, 0] are: [[0, 1]] 
Neighbours of [0, 1] are: [[1, 2], [0, 0], [3, 1]] 
Neighbours of [1, 2] are: [[0, 1], [3, 1]] 
Neighbours of [3, 1] are: [[0, 1], [1, 2]] 
Neighbours of [4, 7] are: [[5, 7]] 
Neighbours of [5, 7] are: [[4, 7]] 
Neighbours of [5, 5] are: [[4, 7], [5, 7]] 
Neighbours of [9, 5] are: [[9, 2]] 
Neighbours of [9, 2] are: [[9, 5]] 
Neighbours of [9, 9] are: [] 
------------------ 
Neighbouring O(n^2) 
Neighbours of [0, 0] are: [[0, 1], [1, 2]] 
Neighbours of [0, 1] are: [[1, 2], [0, 0], [3, 1]] 
Neighbours of [1, 2] are: [[0, 1], [0, 0], [3, 1]] 
Neighbours of [3, 1] are: [[0, 1], [1, 2]] 
Neighbours of [4, 7] are: [[5, 5], [5, 7]] 
Neighbours of [5, 7] are: [[4, 7], [5, 5]] 
Neighbours of [5, 5] are: [[4, 7], [5, 7]] 
Neighbours of [9, 5] are: [[9, 2]] 
Neighbours of [9, 2] are: [[9, 5]] 
Neighbours of [9, 9] are: [] 

알아낼 수없는 이유 이웃이 동일하지 않다면, a-> b는 이웃이지만 b-> a도 이웃이 아님을 알 수 있습니다.

Answer 1

DBSCAN과 가장 가까운 이웃 검색에 대한 R * -tree 같은 색인 구조가 포함 된 ELKI을 사용할 수 있습니다. 매개 변수화 된 오른쪽 일 때, 정말 빠릅니다. Trac에서 다음 버전에서도 KD 트리가 있음을 알았습니다.

코드를 간략하게 살펴보면 @ThomasJungblut에 동의해야합니다. 필요하면 다른 지점을 백 트레이스하지 않은 다음 시도해보십시오. 따라서 많은 이웃을 놓친 것입니다.