Expand description
§solow-neighbors
Nearest-neighbor data structures and estimators for the Solow statistical stack.
The crate ships a KDTree — the balanced k-dimensional binary
space partition tree — for O(log n) amortised nearest-neighbour
and radius queries in low-to-moderate dimensions, together with two
estimators that consume it:
KNeighborsClassifier— majority-vote classification over theknearest labelled neighbours, with optional distance-weighted voting (uniform vs1/d).KNeighborsRegressor— mean of theknearest neighbour target values (uniform or distance-weighted).
Every estimator exposes the classical the reference fit /
predict / predict_proba shape. The tree is built once at fit
time; predict on m new points is O(m · k · log n) in expectation.
§Complexity
KdTree::build:O(n · log n)time,O(n)space, using the median-split classical construction with an in-place bounding-box pruning key.KdTree::k_nearest:O(k · log n)expected time in lowd, degrades toO(n)asdgrows (the classical KD-tree curse of dimensionality).KdTree::radius:O(log n + m)wheremis the answer size.
For high-dimensional data (d ≥ 30) prefer brute-force scanning —
the KDTree still returns the correct answer but no longer beats an
O(n · d) sweep.
§Determinism
Construction is fully deterministic: the median split picks the
lower-index sample on ties, so KdTree::build on the same input
always produces the same tree. Queries are deterministic given the
tree.
§References
- Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.
- Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3), 209-226.
Re-exports§
pub use ball_tree::BallTree;pub use centroid::NearestCentroid;pub use kde::KdeKernel;pub use kde::KernelDensity;pub use kdtree::KdTree;pub use kdtree::Neighbor;pub use knn::KNeighborsClassifier;pub use knn::KNeighborsRegressor;pub use knn::WeightKind;pub use lof::LocalOutlierFactor;pub use radius::RadiusNeighborsClassifier;pub use radius::RadiusNeighborsRegressor;
Modules§
- ball_
tree - BallTree — Uhlmann-Yianilos (1991) metric-space partitioning.
- centroid
- Nearest-centroid classifier (Rocchio 1971) — a memory-cheap, parameter-free classifier that assigns each new sample to the class whose centroid is Euclidean-nearest.
- kde
KernelDensity— multivariate kernel density estimation.- kdtree
KdTree— balanced k-dimensional binary space partition tree.- knn
- K-nearest-neighbours estimators built on top of
crate::KdTree. - lof
- Local Outlier Factor (Breunig-Kriegel-Ng-Sander 2000).
- prelude
- Commonly-used imports.
- radius
- Radius-neighbours classifier and regressor. Uses brute-force scans
for correctness; downstream callers who need
O(log n)should switch toKdTree::radiusthemselves.