A k-d tree is a binary space-partitioning structure that recursively divides points by coordinate dimensions. It organizes feature locations for fast nearest-neighbor queries and can support range-based searches. section 5.7
In outlier detection, nearest-neighbor distance and local density provide useful signals: points with few close neighbors or positions in especially low-density regions may be anomalous. A k-d tree accelerates the searches used to find those relationships. section 5.7
Practical considerations include:
- Use k-d trees for fast nearest-neighbor queries, while recognizing that efficiency depends on the dataset. section 5.7
- Compare k-d trees with BallTrees rather than assuming one structure is always faster; k-d trees are usually more efficient with few features, while BallTrees often suit more features. section 5.8
- Treat tree-based distance or density signals as evidence for investigation, not as automatic proof that a point is an outlier. section 5.7 section 5.0
Nearest-neighbor and range searches
Fit a tree on training points, query a location for its nearest training points, and use distances or the number of points inside a radius to assess local sparsity. SciPy also provides a KDTree and Rectangle structures for representing subspaces as hyperrectangles. section 5.7
