pulsatrix 1.1.0
Loading...
Searching...
No Matches
nearest_neighbors.hpp
Go to the documentation of this file.
1
15#pragma once
16
17#include <cstdint>
18#include <utility>
19#include <vector>
20
21#include "pulsatrix/tensor.hpp"
22
23namespace pulsatrix {
24
26enum class NeighborMetric {
29 Cosine,
32};
33
37 int64_t k = 10;
44 bool center = false;
45};
46
48struct Neighbors {
49 int64_t rows = 0;
50 int64_t k = 0;
53 std::vector<int64_t> indices;
55 std::vector<double> scores;
56
57 [[nodiscard]] int64_t index(int64_t row, int64_t rank) const;
58 [[nodiscard]] double score(int64_t row, int64_t rank) const;
59};
60
68[[nodiscard]] Neighbors NearestNeighbors(const Tensor& points, const NeighborOptions& options = {});
69
76[[nodiscard]] Neighbors NearestNeighbors(const Tensor& queries, const Tensor& points,
77 const NeighborOptions& options = {});
78
87[[nodiscard]] std::vector<std::pair<int64_t, int64_t>> MutualNearestNeighbors(const Tensor& a, const Tensor& b,
88 const NeighborOptions& options = {});
89
99[[nodiscard]] double MutualKnnAlignment(const Tensor& a, const Tensor& b, const NeighborOptions& options = {});
100
102struct Hubness {
104 std::vector<int64_t> occurrences;
107 double skewness = 0;
109 int64_t max_occurrence = 0;
110 double max_fraction = 0;
113};
114
119[[nodiscard]] Hubness MeasureHubness(const Neighbors& neighbors, int64_t num_points);
120
121} // namespace pulsatrix
N-dimensional tensor. Owns its data buffer exclusively; a DeviceBackend* is injected (not owned) – th...
Definition tensor.hpp:29
Definition acquisition_functions.hpp:16
std::vector< std::pair< int64_t, int64_t > > MutualNearestNeighbors(const Tensor &a, const Tensor &b, const NeighborOptions &options={})
The pairs (i, j), a[i] from a and b[j] from b, where b[j] is among a[i]'s k nearest in b and a[i] is ...
Hubness MeasureHubness(const Neighbors &neighbors, int64_t num_points)
Measures hubness in neighbors, which name points 0 to num_points - 1.
Neighbors NearestNeighbors(const Tensor &points, const NeighborOptions &options={})
Each point's k nearest other points (a point is never its own neighbor).
NeighborMetric
How nearness is measured.
Definition nearest_neighbors.hpp:26
@ Euclidean
Euclidean distance. Lower is nearer.
@ Cosine
Cosine similarity: the angle between vectors, ignoring their lengths. Higher is nearer....
double MutualKnnAlignment(const Tensor &a, const Tensor &b, const NeighborOptions &options={})
Mutual-kNN alignment (Huh et al. 2024): how far two representations of the same inputs agree on which...
How unevenly points appear in each other's neighbor lists.
Definition nearest_neighbors.hpp:102
double max_fraction
Definition nearest_neighbors.hpp:110
int64_t max_occurrence
The most lists any one point is in, and its fraction of all queries.
Definition nearest_neighbors.hpp:109
std::vector< int64_t > occurrences
How many neighbor lists each point appears in (its "k-occurrence"). The mean is k.
Definition nearest_neighbors.hpp:104
double skewness
The skewness of occurrences. Near 0 when points appear about equally often; well above 1 means a few ...
Definition nearest_neighbors.hpp:107
double never_a_neighbor
The fraction of points in nobody's list.
Definition nearest_neighbors.hpp:112
Settings for the neighbor searches.
Definition nearest_neighbors.hpp:35
NeighborMetric metric
Definition nearest_neighbors.hpp:38
int64_t k
How many neighbors to find for each query.
Definition nearest_neighbors.hpp:37
bool center
Subtract the points' mean from every vector first. Activations often share a large common component,...
Definition nearest_neighbors.hpp:44
Each query's k nearest points, nearest first.
Definition nearest_neighbors.hpp:48
int64_t k
Definition nearest_neighbors.hpp:50
std::vector< double > scores
The same layout: cosine similarity, or Euclidean distance.
Definition nearest_neighbors.hpp:55
int64_t rows
the number of queries
Definition nearest_neighbors.hpp:49
std::vector< int64_t > indices
Row-major rows × k: indices[q * k + r] is query q's r-th nearest point.
Definition nearest_neighbors.hpp:53
NeighborMetric metric
Definition nearest_neighbors.hpp:51
double score(int64_t row, int64_t rank) const
int64_t index(int64_t row, int64_t rank) const
N-dimensional tensor – owns a buffer via DeviceBackend*, RAII (Rule of Five).