@Test public void testKnn1() { System.out.println("----- knn1 -----"); double[][] data = Matrix.randn(2, 10).toArray(); double[][] data1 = {data[0]}; EuclideanDistance d = new EuclideanDistance(); LinearSearch<double[]> naive = new LinearSearch<>(data1, d); Neighbor[] n1 = naive.knn(data[1], 1); assertEquals(1, n1.length); assertEquals(0, n1[0].index); assertEquals(data[0], n1[0].value); assertEquals(d.d(data[0], data[1]), n1[0].distance, 1E-7); }
@Override @SuppressWarnings("unchecked") public Neighbor<T, T>[] knn(T q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the data size"); } double[] dist = Arrays.stream(data).parallel().mapToDouble(x -> distance.d(q, x)).toArray(); HeapSelect<NeighborBuilder<T,T>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } for (int i = 0; i < dist.length; i++) { NeighborBuilder<T,T> datum = heap.peek(); if (dist[i] < datum.distance && q != data[i]) { datum.distance = dist[i]; datum.index = i; datum.key = data[i]; datum.value = data[i]; heap.heapify(); } } heap.sort(); return Arrays.stream(heap.toArray()).map(NeighborBuilder::toNeighbor).toArray(Neighbor[]::new); }
LinearSearch implements NearestNeighborSearch<T,T>, KNNSearch<T,T>, RNNSearch<T,T>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<T, T>[] knn(T q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the data size"); } double[] dist = Arrays.stream(data).parallel().mapToDouble(x -> distance.d(q, x)).toArray(); HeapSelect<NeighborBuilder<T,T>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } for (int i = 0; i < dist.length; i++) { NeighborBuilder<T,T> datum = heap.peek(); if (dist[i] < datum.distance && q != data[i]) { datum.distance = dist[i]; datum.index = i; datum.key = data[i]; datum.value = data[i]; heap.heapify(); } } heap.sort(); return Arrays.stream(heap.toArray()).map(NeighborBuilder::toNeighbor).toArray(Neighbor[]::new); } }
LinearSearch implements NearestNeighborSearch<T,T>, KNNSearch<T,T>, RNNSearch<T,T>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<T, T>[] knn(T q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the data size"); } double[] dist = Arrays.stream(data).parallel().mapToDouble(x -> distance.d(q, x)).toArray(); HeapSelect<NeighborBuilder<T,T>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } for (int i = 0; i < dist.length; i++) { NeighborBuilder<T,T> datum = heap.peek(); if (dist[i] < datum.distance && q != data[i]) { datum.distance = dist[i]; datum.index = i; datum.key = data[i]; datum.value = data[i]; heap.heapify(); } } heap.sort(); return Arrays.stream(heap.toArray()).map(NeighborBuilder::toNeighbor).toArray(Neighbor[]::new); } LinearSearch(T[] dataset, Distance<T> distance); }
LinearSearch implements NearestNeighborSearch<T,T>, KNNSearch<T,T>, RNNSearch<T,T>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<T, T>[] knn(T q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the data size"); } double[] dist = Arrays.stream(data).parallel().mapToDouble(x -> distance.d(q, x)).toArray(); HeapSelect<NeighborBuilder<T,T>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } for (int i = 0; i < dist.length; i++) { NeighborBuilder<T,T> datum = heap.peek(); if (dist[i] < datum.distance && q != data[i]) { datum.distance = dist[i]; datum.index = i; datum.key = data[i]; datum.value = data[i]; heap.heapify(); } } heap.sort(); return Arrays.stream(heap.toArray()).map(NeighborBuilder::toNeighbor).toArray(Neighbor[]::new); } LinearSearch(T[] dataset, Distance<T> distance); @Override String toString(); @Override Neighbor<T, T> nearest(T q); @Override @SuppressWarnings("unchecked") Neighbor<T, T>[] knn(T q, int k); @Override void range(T q, double radius, List<Neighbor<T, T>> neighbors); }
LinearSearch implements NearestNeighborSearch<T,T>, KNNSearch<T,T>, RNNSearch<T,T>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<T, T>[] knn(T q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the data size"); } double[] dist = Arrays.stream(data).parallel().mapToDouble(x -> distance.d(q, x)).toArray(); HeapSelect<NeighborBuilder<T,T>> heap = new HeapSelect<>(k); for (int i = 0; i < k; i++) { heap.add(new NeighborBuilder<>()); } for (int i = 0; i < dist.length; i++) { NeighborBuilder<T,T> datum = heap.peek(); if (dist[i] < datum.distance && q != data[i]) { datum.distance = dist[i]; datum.index = i; datum.key = data[i]; datum.value = data[i]; heap.heapify(); } } heap.sort(); return Arrays.stream(heap.toArray()).map(NeighborBuilder::toNeighbor).toArray(Neighbor[]::new); } LinearSearch(T[] dataset, Distance<T> distance); @Override String toString(); @Override Neighbor<T, T> nearest(T q); @Override @SuppressWarnings("unchecked") Neighbor<T, T>[] knn(T q, int k); @Override void range(T q, double radius, List<Neighbor<T, T>> neighbors);  }