@Test public void testKnn() { System.out.println("knn"); double[][] data = Matrix.randn(1000, 10).toArray(); KDTree<double[]> kdtree = new KDTree<>(data, data); LinearSearch<double[]> naive = new LinearSearch<>(data, new EuclideanDistance()); for (int i = 0; i < data.length; i++) { Neighbor<double[], double[]> [] n1 = naive.knn(data[i], 10); Neighbor<double[], double[]> [] n2 = kdtree.knn(data[i], 10); for (int j = 0; j < n1.length; j++) { assertEquals(n1[j].index, n2[j].index); assertEquals(n1[j].value, n2[j].value); assertEquals(n1[j].distance, n2[j].distance, 1E-7); } } }
@Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > keys.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } HeapSelect<NeighborBuilder<double[], E>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } search(q, root, heap); heap.sort(); return Arrays.stream(heap.toArray()) .map(neighbor -> { neighbor.key = keys[neighbor.index]; neighbor.value = data[neighbor.index]; return neighbor.toNeighbor(); }).toArray(Neighbor[]::new); }
KDTree implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > keys.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } HeapSelect<NeighborBuilder<double[], E>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } search(q, root, heap); heap.sort(); return Arrays.stream(heap.toArray()) .map(neighbor -> { neighbor.key = keys[neighbor.index]; neighbor.value = data[neighbor.index]; return neighbor.toNeighbor(); }).toArray(Neighbor[]::new); } }
KDTree implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > keys.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } HeapSelect<NeighborBuilder<double[], E>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } search(q, root, heap); heap.sort(); return Arrays.stream(heap.toArray()) .map(neighbor -> { neighbor.key = keys[neighbor.index]; neighbor.value = data[neighbor.index]; return neighbor.toNeighbor(); }).toArray(Neighbor[]::new); } KDTree(double[][] key, E[] data); }
KDTree implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > keys.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } HeapSelect<NeighborBuilder<double[], E>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } search(q, root, heap); heap.sort(); return Arrays.stream(heap.toArray()) .map(neighbor -> { neighbor.key = keys[neighbor.index]; neighbor.value = data[neighbor.index]; return neighbor.toNeighbor(); }).toArray(Neighbor[]::new); } KDTree(double[][] key, E[] data); @Override String toString(); @Override Neighbor<double[], E> nearest(double[] q); @Override @SuppressWarnings("unchecked") Neighbor<double[], E>[] knn(double[] q, int k); @Override void range(double[] q, double radius, List<Neighbor<double[], E>> neighbors); }
KDTree implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > keys.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } HeapSelect<NeighborBuilder<double[], E>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } search(q, root, heap); heap.sort(); return Arrays.stream(heap.toArray()) .map(neighbor -> { neighbor.key = keys[neighbor.index]; neighbor.value = data[neighbor.index]; return neighbor.toNeighbor(); }).toArray(Neighbor[]::new); } KDTree(double[][] key, E[] data); @Override String toString(); @Override Neighbor<double[], E> nearest(double[] q); @Override @SuppressWarnings("unchecked") Neighbor<double[], E>[] knn(double[] q, int k); @Override void range(double[] q, double radius, List<Neighbor<double[], E>> neighbors);  }