A ball tree is a data structure for fast nearest-neighbor searches. In scikit-learn, `BallTree` stores the locations of training points so distance-based outlier detectors can look up nearby points without calculating every pairwise distance. It supports both k-nearest-neighbor and radius-based queries. section 3.2.1 section 5.7
Fit the tree on training points, then call `query(points, k)` to get each query point’s k nearest training points and their distances. Call `query_radius()` to find how many training points fall within a specified radius. Query points may be the training data or separate data. If a training point queries the same data, its results include the point itself at distance zero. section 5.7
For a k-nearest-neighbor outlier score, nearby distances can indicate how isolated a point is. One implementation averages the returned distances for k = 3. Scale features before interpreting distances: a comparison of inventory records uses scaled weight, cost, age in inventory, and maximum storage temperature, but excludes the inventory ID. Euclidean distance is the default metric; other metrics are available. section 3.2.1 section 5.7
Listing 3.1 Example of a KNN outlier detector
import numpy as np
import pandas as pd
from sklearn.neighbors import BallTree
import matplotlib.pyplot as plt
import seaborn as sns
np.random.seed(0)
n_per_cluster = 500
data_a = pd.Series(
np.random.laplace(size= n_per_cluster)) #1
data_b = pd.Series(np.random.laplace(size= n_per_cluster))
df1 = pd.DataFrame({"A": data_a, "B": data_b})
data_a = pd.Series(
np.random.normal(loc=5, size=n_per_cluster)) #2
data_b = pd.Series(np.random.normal(loc=15, size=n_per_cluster))
df2 = pd.DataFrame({"A": data_a, "B": data_b})
df = pd.concat([df1, df2])
fig, ax = plt.subplots(nrows=2, ncols=2, figsize=(8, 6))
s = sns.scatterplot(data=df, x="A", y="B", alpha=0.4, ax=ax[0][0])
tree = BallTree(df, leaf_size=100) #3
dist, _ = tree.query(df, k=3)
dist = [x.mean() for x in dist]
df['Score'] = dist
s = sns.scatterplot(data=df, x="A", y="B", s=50*df['Score'],
alpha=0.4, ax=ax[0][1])
cutoff = sorted(df['Score'])[-6] #4
df['Outlier'] = df['Score'] > cutoff
sns.scatterplot(data=df[df['Outlier']==False], x="A", y="B",
alpha=0.4, ax=ax[1][0])
sns.scatterplot(data=df[df['Outlier']==True], x="A", y="B", s=100,
alpha=1.0, marker='*', ax=ax[1][0])
cutoff = sorted(df['Score'])[-16] #5
df['Outlier'] = df['Score'] > cutoff
sns.scatterplot(data=df[df['Outlier']==False], x="A", y="B",
alpha=0.4, ax=ax[1][1])
sns.scatterplot(data=df[df['Outlier']==True], x="A", y="B", s=100,
alpha=1.0, marker='*', ax=ax[1][1])
plt.show()
The listing fits `BallTree` on two synthetic clusters, queries three neighbors per point, and averages the returned distances to form outlier scores. section 3.2.1
`leaf_size` changes lookup efficiency, not query results. `KDTree` offers a similar search structure, and either may be faster depending on the data; KDTree is usually more efficient with few features, BallTree with more. BallTree also supports scikit-learn tools including kernel density estimation and local outlier factor. A large distance or sparse neighborhood is evidence to investigate, not proof that a record is anomalous. section 5.7 section 5.8
