Sunday, December 28, 2014

Nearest Neighbor on a plane

Fill in the following methods:
public interface PointsOnAPlane {

    /**
     * Stores a given point in an internal data structure
     */
    void addPoint(Point point);

    /**
     * For given 'center' point returns a subset of 'm' stored points that are
     * closer to the center than others.
     *
     * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)
     *
     * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3)
     */
    Collection<Point> findNearest(Point center, int m);

}
Click here for the original problem:
The last is always the best. Look how much time I spent on debugging this... -_-|||
This is actually very interesting. It reminds me of the Nearest Neighbor in unsupervised learning.

Anyway, basically I use a priorityQueue to store the m closest points to the center. The comparator compares the the distance between all points and the center. I use an arrayList to store all points added to the class. When calling findNearest() method, the array needs to be sorted. Since the array is sorted, the time complexity is O(nlog(n)).

import java.util.*;
public class Point {
 double x;
 double y;
 
 public Point() {
  this.x = 0.0;
  this.y = 0.0;
 }
 public Point(double x, double y) {
  this.x = x;
  this.y = y;
 }
 public double getX() {
  return x;
 }
 public double getY() {
  return y;
 }
 public boolean equals(Point p) {
  return (this.x == p.x && this.y == p.y);
  
 }
 public double distanceFrom(Point p) {
  return Math.sqrt(Math.pow(p.y - this.y, 2) + Math.pow(p.x - this.x, 2));
 }
 public String toString() {
  return "(" + x + ", " + y + ")";
 }
 
}
public class ThisPointsOnAPlane implements PointsOnAPlane{
 private ArrayList points;
 
 public ThisPointsOnAPlane() {
  points = new ArrayList();
 }
 public void addPoint(Point p) {
  points.add(p);
 }
 
 public PriorityQueue findNearest(Point center, int m) {
  if (center == null)
   throw new NullPointerException("Null center!");
  PointComparator pc = new PointComparator(center);
  PriorityQueue nearestNeighbor = new PriorityQueue (m, pc);
  if (m == 0) {
   nearestNeighbor.add(center);
   return nearestNeighbor;
  }
  Collections.sort(points, pc);
  Point last = null;
  for (Point p : points) {
   if (p.equals(center))
    continue;
   if (nearestNeighbor.size() < m) {
    nearestNeighbor.add(p);
    last = p;
   }
    
   else {
    if (p.distanceFrom(center) < last.distanceFrom(center)) {
     nearestNeighbor.remove(last);
     nearestNeighbor.add(p);
     last = p;
    }
   }
  }
  return nearestNeighbor;
 }
 public String toString () {
  String rst = "{ ";
  for (Point p : points) {
   rst += "(" + p.x + ", " + p.y +"), ";
  }
  rst = rst.substring(0, rst.length() - 2) + " }";
  return rst;
 }
 
 
 private class PointComparator implements Comparator {
  Point center;
  public PointComparator(Point center) {
   this.center = center;
   //System.out.println(center.x + ", " + center.y);
  }
  public int compare(Point a, Point b) {
   if (a.distanceFrom(center) - b.distanceFrom(center) < 0) {
    return -1;
   }
    
   else if (a.distanceFrom(center) - b.distanceFrom(center) > 0) {
    return 1;
   }
    
   return 0;
  }
 }
}
//Test class
public class NNTester {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  ThisPointsOnAPlane tpoap = new ThisPointsOnAPlane();
  tpoap.addPoint(new Point(0, 0));
  tpoap.addPoint(new Point(0, 2));
  tpoap.addPoint(new Point(0, 1));
  tpoap.addPoint(new Point(0, 4));
  tpoap.addPoint(new Point(0, 3));
  tpoap.addPoint(new Point(1, 3));
  tpoap.addPoint(new Point(1, 1));
  tpoap.addPoint(new Point(1, 1));
  Point center = new Point(0, 0);
  int m = 3;
  PriorityQueue nearestNeighbor = tpoap.findNearest(center, m);
  for (int i = 0; i < m; i++) {
   Point p = nearestNeighbor.poll();
   System.out.println("(" + p.x +", " + p.y +")");
  }

 }

}


However, I do see there is a comment saying using Quickselect, we can reduce the time complexity to  O(n). I am gonna think about this tomorrow.

Update about Quick select method. It won't work. First, we need an extra array to store the distances to the center of all points to do quick select. And second, we need a map to store <distance, point> pairs because after swap, the order will not be the same. So even though the the time complexity can reduce to O(n), we need O(2*n) (ah.. if you want to say O(n), is fine) extra space.

And here comes third, which actually fails the method, is that map doesn't allow duplicate key - value pairs. I am not sure if there are other containers that allow me to do that, but so far, I will stick to the priority queue method. Here is the quick select code:




public ArrayList findNearest2 (Point center, int m) {
  if (center == null)
   throw new NullPointerException("Null center!");
  ArrayList rst = new ArrayList ();
  if (m == 0) 
   return rst;
  double[] distance = new double[points.size()];
  HashMap hm = new HashMap();
  for (int i = 0; i < points.size(); i++) {
   distance[i] = points.get(i).distanceFrom(center);
   hm.put(distance[i], points.get(i));
   System.out.println(points.get(i).toString() + ": " + distance[i]);
  }
  quickSelect(distance, 0, distance.length - 1, m + 1);
  for (int i = 0; i <= m; i++) {
   if (distance[i] == 0)
    continue;
   rst.add(hm.get(distance[i]));
  }
  return rst;
 }
 
 private void quickSelect(double[] array, int start, int end, int k) {
  if (start > end)
   return;
  double pivot = array[(start + end) / 2];
  int left = start;
  int right = end;
  while (left < right) {
   if (array[left] >= pivot) {
    swap(array, left, right);
    right--;
   }
   else {
    left++;
   }
  }
  if (array[left] > pivot) 
   left--;
  if (k - 1 == left)
    return;
  else if (k - 1 < left)
   quickSelect(array, start, left - 1, k);
  else
   quickSelect(array, left + 1, end, k);
 }
 private void swap (double[] array, int left, int right) {
  double tmp = array[left];
  array[left] = array[right];
  array[right] = tmp;
 }

1 comment:


  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete